Загрузка

Симплексный метод

Приведите к предпочтительному виду модель задачи:

$$maxf(X)=3x_1-x_2+5x_3$$;

$$\left\{\begin{matrix} x_1+3x_2=5, \\ x_2-x_3=16;\end{matrix}\right. $$

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Каноническая модель ЗЛП имеет предпочтительный вид, если в каждом из уравнений системы ограничений присутствует предпочтительная переменная.

Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.

Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные.

В целевую функцию искусственные переменные в случае ее максимизации вводим с коэффициентом, равным $$-M$$.

Поскольку во втором уравнении системы ограничений отсутствует предпочтительная переменная, то вводим искусственную переменную $$\omega \geq0$$.

Получим:

$$maxf(X)=3x_1-x_2+5x_3-M\omega$$;

$$\left\{\begin{array}{lr} \underline{x_1}+3x_2=5, \\ x_2-x_3+\underline{\omega}=16. \end{array}\right. $$

Во втором уравнении $$x_2-x_3=16$$ переменная $$x_3$$ не является предпочтительной, так как она имеет коэффициент $$-1$$.

Выберите несколько вариантов ответов
Приведите к предпочтительному виду модель задачи:
$$minf(X)=x_1+5x_3$$
;
$$\left\{\begin{array}{lr} x_1+6x_3=11,\\ 15x_1+x_2\geq0,\\ x_1+3x_3\leq-7; \end{array}\right.$$

$$x_i\geq0$$, $$i=\overline{1;3}$$.

Переменная называется предпочтительной, если она присутствует только в одном из уравнений системы ограничений и только с коэффициентом, равным единице.

Если в канонической модели задачи отсутствуют предпочтительные переменные, то вводим неотрицательные искусственные переменные. В целевую функцию искусственные переменные в случае ее минимизации вводим с коэффициентом, равным $$+M$$.

  1. Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$x_4$$ и $$x_5$$.

    Целевая функция:

    $$f(X)=x_1+5x_3+0 \cdot x_4+0 \cdot x_5$$.

    Система ограничений:

    $$\left\{\begin{array}{lr} x_1+6x_3=11, \\ 15x_1+x_2\geq0, \\ -x_1-3x_3\geq7; \end{array}\right.$$$$\left\{\begin{array}{lr} x_1+6x_3=11, \\ 15x_1+x_2-x_4=0, \\ -x_1-3x_3-x_5=7. \end{array}\right.$$

  2. Приведем модель задачи к предпочтительному виду с помощью искусственных переменных $$\omega_1$$ и $$\omega_2$$.

    Целевая функция:

    $$minf(X)=x_1+5x_3+0 \cdot x_4+0 \cdot x_5+M\omega_1+M\omega_2$$.

    Система ограничений:

    $$\left\{\begin{array}{lr} x_1+6x_3+\underline{\omega_1}=11, \\ 15x_1+\underline{x_2}-x_4=0, \\ -x_1-3x_3-x_5+\underline{\omega_2}=7. \end{array}\right.$$

    Условия неотрицательности переменных:

    $$x_i\geq0$$, $$i=\overline{1; 5}$$; $$w_1\geq0$$, $$w_2\geq0$$.

В целевую функцию обе искусственные переменные входят с одним и тем же коэффициентом $$+M$$.

Выберите несколько вариантов ответов

Составьте задачу, двойственную к задаче:

$$minf(X)=x_1+7x_2$$,

$$\left\{\begin{array}{lr} x_1+4x_2\geq3, \\ 6x_1-x_2\geq8; \end{array}\right.$$

$$x_i\geq0$$, $$i=\overline{1; 2}$$.

Пара симметричных двойственных задач

Задача 1

$$maxf(X)\sum_{i=1}^{n}c_ix_i$$;

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1, m}$$;

$$x_i\geq 0$$, $$i=\overline{1, n}$$.

Задача 2

$$minf(Y)\sum_{j=1}^{m}b_jy_j$$;

$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$, $$i=\overline{1, n}$$;

$$y_{j}\geq 0$$, $$j=\overline {1, m}$$.

$$maxf(Y)=3y_1+8y_2$$;

$$\left\{\begin{array}{lr} y_1+6y_2\leq1, \\ 4y_1-y_2\leq7; \end{array}\right.$$

$$y_j\geq0$$, $$j=\overline{1; 2}$$.

Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение, причем оптимальные значения целевых функций совпадают.

Выберите несколько вариантов ответов

Составьте задачу, двойственную к задаче:

$$maxf(X)=3x_1+5x_2$$;

$$\left\{\begin{array}{lr} x_1-5x_2\leq1, \\ 5x_1+x_2\leq4, \\ 6x_1+x_2\leq7; \end{array}\right.$$

$$x_1\geq0$$, $$x_2\geq0$$.

Пара симметричных двойственных задач
Задача 1
$$maxf(X)\sum_{i=1}^{n}c_ix_i$$

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$$$j=\overline {1,m}$$;

$$x_i\geq 0$$$$i=\overline{1,n}$$.

Задача 2
$$minf(Y)\sum_{j=1}^{m}b_jy_j$$

$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$$$i=\overline{1,n}$$

$$y_{j}\geq 0$$$$j=\overline {1,m}$$.

$$minf(Y)=y_1+4y_2+7y_3$$;

$$\left\{\begin{array}{lr} y_1+5y_2+6y_3\geq3, \\ -5y_1+y_2+y_3\geq5; \end{array}\right.$$

$$y_j\geq0$$, $$j=\overline{1; 3}$$.

Если мы имеем задачу об оптимальном выпуске продукции (Задача 1), то переменные (Задача 2) $$y_1$$, $$y_2$$, $$. . . $$, $$y_m$$, называют оценками ресурсов.

Оценки должны быть установлены исходя из следующих соображений:

  1. общая стоимость ресурсов должна быть минимизирована;
  2. в случае продажи ресурса выручка должна быть не меньше стоимости продукции при организации производства.
Выберите несколько вариантов ответов

Решите симплексным методом задачу:

$$minf(X)=x_1+5x_2+2x_3$$;

$$\left\{\begin{matrix} x_1-x_2=50, \\ 2x_2+x_3=5; \end{matrix}\right.$$.

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Предпочтительные переменные являются базисными, а остальные переменные – свободными. Свободные переменные считаем равными нулю. 
Чтобы найти значения базисных переменных, необходимо в систему ограничений подставить значения свободных переменных.
Задача: 

$$minf(X)=c_1x_1+c_2x_2+c_3x_3$$;

 $$\left\{\begin{matrix} \underline{x_1}+a_{12}x_2=b_1,\\ a_{21}x_2+\underline{x_3}=b_2. \end{matrix}\right.$$ 

Симплексная таблица:

Оценка целевой функции (значение целевой функции): 

$$\Delta_0=c_1 \cdot b_1+ c_3 \cdot b_3$$
Оценки переменных: 
$$\Delta_1=c_1 \cdot a_{11}+ c_3 \cdot a_{21}-c_1$$
$$\Delta_2=c_1 \cdot a_{12}+ c_3 \cdot a_{22}-c_2$$
$$\Delta_3=c_1 \cdot a_{13}+ c_3 \cdot a_{23}-c_3$$.
Критерий оптимальности опорного плана задачи:

если при минимизации целевой функции все оценки переменных неположительные, то план оптимальный.


Базисные переменные: $$x_1=50$$$$x_3=5$$.
Свободные переменные: $$x_2=0$$.
Составим симплексную таблицу:

Найдем оценки переменных: 

$$\Delta_1=1 \cdot 1+ 2 \cdot 0 -1=0$$
$$\Delta_2=1 \cdot (-1)+ 2 \cdot 2 -5=-2$$
$$\Delta_3=1 \cdot 0+ 2 \cdot 1 -2=0$$.
Поскольку все оценки переменных неположительные, то опорный план оптимальный: 
$$X^*=(50;0;5)$$$$f(X^*)=60$$.

Оценки базисных переменных всегда равны нулю.

Выберите несколько вариантов ответов

Решите симплексным методом задачу:

$$maxf(X)=x_1+5x_2+2x_3$$;

$$\left\{\begin{matrix} x_1-x_2=50, \\ 2x_2+x_3=5; \end{matrix}\right.$$.

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Оценка целевой функции (значение целевой функции):

$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$.

Оценки переменных:

$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$.

Критерий оптимальности опорного плана задачи: если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимальный. Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия.

  1. Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим.
  2. Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца $$A_0$$ и соответствующих элементов разрешающего столбца. Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей.

    Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом $$a_{pp}^{0}$$.

  3. Переходим к первой итерации симплексной таблицы.

    Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации, заменяем переменной из разрешающего столбца.

    Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации).

    Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю.

    Остальные элементы таблицы находим по правилу прямоугольника (рис. 10. 8):

    $$a_{ji}^{1}=\frac{a_{ji}^{0} \cdot a_{pp}^{0}-a_{jP}^{0} \cdot a_{Pi}^{0}}{a_{PP}^{0}}$$.

Базисные переменные: $$x_1=50$$$$x_3=5$$.
Свободные переменные: $$x_2=0$$.
Составим симплексную таблицу и выполним симплексные преобразования: 

Пояснения к нулевой итерации

Индексная строка: 
$$\Delta_0=1 \cdot 50+ 2 \cdot 5 =60$$;
$$\Delta_1=1 \cdot 1+ 2 \cdot 0 -1 =0$$
$$\Delta_2=1 \cdot (-1)+ 2 \cdot 2 -5 =-2$$
$$\Delta_3=1 \cdot 0+ 2 \cdot 1 -2 =0$$.
Поскольку присутствуют отрицательные оценки переменных, то опорный план задачи не оптимальный. В качестве разрешающего столбца выбираем столбец $$A_2$$
Симплексные отношения: 

$$\theta_1$$ не существует, так как $$a_{12}=-1<0$$

$$\theta_2=5:2=2,5$$

Вторая строка будет разрешающей.

Разрешающий элемент $$a_{pp}=2$$.

Пояснения к первой итерации
Вносим изменения в базис: переменную $$x_3$$ заменяем переменной $$x_2$$
Все элементы разрешающей строки нулевой итерации делим на $$a_{pp}=2$$ и результаты записываем во вторую строку первой итерации. Элемент $$a_{12}^{1}$$ считаем равным нулю. 
Остальные элементы первой строки находим по правилу прямоугольника: 

$$a_{10}^{1}=\frac{50 \cdot 2+5 \cdot 1}{2}=52,5$$

$$a_{11}^{1}=\frac{1 \cdot 2+0 \cdot 1}{2}=1$$

$$a_{13}^{1}=\frac{0 \cdot 2+1 \cdot 1}{2}=0,5$$.

Заполняем индексную строку. Поскольку все оценки переменных первой итерации неотрицательные, то опорный план оптимальный: 
$$X^*=(52,5;2,5;0)$$$$f(X^*)=65$$.

Симплексные отношения:

$$\theta_j=\frac{b_{j}^{0}}{a_{jP}^{0}}$$.

Отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений.

Выберите несколько вариантов ответов

Решите симплексным методом задачу:

$$minf(X)=5x_1+3x_2$$;

$$\left\{\begin{matrix} x_1-2x_2=2, \\ x_2+5x_3=2; \end{matrix}\right. $$

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Оценка целевой функции (значение целевой функции):

$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$.

Оценки переменных:

$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$.

Симплексные отношения:

$$\theta_j=\frac{b_j^0}{a_{jP}^0}$$.

Предпочтительный вид ЗЛП: 
$$minf(X)=5x_1+3x_2+M\omega$$
$$\left\{\begin{array}{lr} \underline{x_1}-2x_2=2,\\ x_2+5x_3+\underline{\omega}=2; \end{array}\right.$$ 

$$x_i \geq0$$$$i=\overline{1;3}$$$$\omega \geq0$$.

Базисные переменные: $$x_1=2$$$$\omega=2$$
Свободные переменные: $$x_2=0$$$$x_3=0$$.
Составим симплексную таблицу и выполним симплексные преобразования: 

Поскольку все оценки переменных неположительные, то опорный план первой итерации оптимальный: 
$$X^*=(2;0;0,4)$$$$f(X^*)=10$$.


Задача с искусственным базисом называется $$M$$-задачей.

При решении $$M$$-задачи по мере выведения искусственных переменных из базиса они выводятся и из симплексной таблицы.

Выберите несколько вариантов ответов

Решите симплексным методом задачу:

$$maxf(X)=5x_1+3x_2+x_3$$;

$$\left\{\begin{array}{lr} x_1-2x_2-x_3=2, \\ x_2+5x_3=2; \end{array}\right. $$

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Оценка целевой функции (значение целевой функции):

$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$.

Оценки переменных:

$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$.

Симплексные отношения:

$$\theta_j=\frac{b_j^0}{a_{jP}^0}$$.

Предпочтительный вид ЗЛП:
$$maxf(X)=5x_1+3x_2+x_3-M\omega$$

$$\left\{\begin{array}{lr} \underline{x_1}-2x_2-x_3=2,\\ x_2+5x_3+\underline{\omega}=2; \end{array}\right.$$ 

$$x_i \geq0$$$$i=\overline{1;3}$$.

Базисные переменные: $$x_1=2$$$$\omega=2$$.
Свободные переменные: $$x_2=0$$$$x_3=0$$.
Составим симплексную таблицу и выполним симплексные преобразования: 

Поскольку все оценки переменных неотрицательные, то опорный план второй итерации оптимальный: 
$$X^*=(6;2;0)$$$$f(X^*)=36$$.


Сиплексные преобразования можно выполнить иначе:

Выберите несколько вариантов ответов

Решите задачу, двойственную к задаче:

$$maxf(X)=x_1+5x_2+2x_3$$;

$$\left\{\begin{array}{lr} 3x_1+x_2\leq5, \\ x_2+2x_3\leq1; \end{array}\right.$$

$$x_i \geq0$$, $$i=\overline{1; 3}$$.

Пара симметричных двойственных задач

Задача 1

$$maxf(X)\sum_{i=1}^{n}c_ix_i$$;

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1, m}$$;

$$x_i\geq 0$$, $$i=\overline{1, n}$$.

Задача 2

$$minf(Y)\sum_{j=1}^{m}b_jy_j$$;

$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$, $$i=\overline{1, n}$$;

$$y_{j}\geq 0$$, $$j=\overline {1, m}$$.

Соответствие между переменными двойственных задач:

$$x_1\leftrightarrow y_{m+1}$$

$$x_2\leftrightarrow y_{m+2}$$

$$. . . $$

$$x_n\leftrightarrow y_{m+n}$$

$$x_{n+1}\leftrightarrow y_1$$

$$. . . $$

$$x_{n+m}\leftrightarrow y_m$$

Значения переменных $$y_j$$ равны оценкам переменных $$x_i$$:

$$y_1=\Delta_{n+1}$$, $$y_2=\Delta_{n+2}$$, ...,  $$y_{n+1}=\Delta_1$$, ..., $$y_{n+m}=\Delta_n$$.

$$maxf(X)=x_1+5x_2+2x_3$$

$$\left\{\begin{array}{lr} 3x_1+x_2+\underline{x_4}=5,\\ x_2+2x_3+\underline{x_5}=1; \end{array}\right.$$

$$x_i \geq0$$$$i=\overline{1;5}$$.

Базисные переменные: $$x_4=5$$$$x_5=1$$.
Свободные переменные: $$x_1=0$$$$x_2=0$$$$x_3=0$$.
Составим симплексную таблицу и выполним симплексные преобразования: 

Установим соответствие между двойственными переменными:

$$x_1\leftrightarrow y_3$$
$$x_2\leftrightarrow y_4$$
$$x_3\leftrightarrow y_5$$
$$x_4\leftrightarrow y_1$$
$$x_5\leftrightarrow y_2$$
Следовательно, 

$$y_1=\Delta_4=\frac{1}{3}$$$$y_2=\Delta_5=4\frac{2}{3}$$$$y_3=\Delta_1=0$$$$y_4=\Delta_2=0$$$$y_5=\Delta_3=7\frac{1}{3}$$.

Тогда: $$Y^*=(\frac{1}{3};4\frac{2}{3};0;0;7\frac{1}{3})$$$$f(Y^*)=6\frac{1}{3}$$.

Соответствие между переменными двойственных задач устанавливается по правилу: основным переменным первой задачи соответствуют дополнительные переменные второй задачи, а дополнительным переменным первой задачи соответствуют основные переменные второй задачи.

Выберите несколько вариантов ответов

Решите симплексным методом задачу:

$$minf(X)=4x_1+x_2$$;

$$\left\{\begin{array}{lr} 2x_1+x_2\geq3, \\ 4x_1+x_2\geq4; \end{array}\right. $$

$$x_1\geq0$$, $$x_2\geq0$$.

  1. Составьте двойственную задачу и решите ее.
  2. Установите соответствие между переменными двойственных задач.

Пара симметричных двойственных задач
Задача 1
$$maxf(X)\sum_{i=1}^{n}c_ix_i$$

$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$$$j=\overline {1,m}$$

$$x_i\geq 0$$$$i=\overline{1,n}$$.

Задача 2

$$minf(Y)\sum_{j=1}^{m}b_jy_j$$

$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$$$i=\overline{1,n}$$

$$y_{j}\geq 0$$, $$j=\overline {1,m}$$.

Соответствие между переменными двойственных задач:

$$x_1\leftrightarrow y_{m+1}$$

$$x_2\leftrightarrow y_{m+2}$$

$$...$$

$$x_n\leftrightarrow y_{m+n}$$

$$x_{n+1}\leftrightarrow y_1$$

$$...$$

$$x_{n+m}\leftrightarrow y_m$$

Значения переменных $$y_i$$ равны оценкам переменных $$x_i$$:
$$y_1=\Delta_{n+1}$$$$y_2=\Delta_{n+2}$$, $$y_{n+1}=\Delta_1$$$$...$$$$y_{n+m}=\Delta_n$$.

Составим двойственную задачу: 

$$maxf(Y)=3y_1+4y_2$$

$$\left\{\begin{array}{lr} 2y_1+4y_2\leq4,\\ y_1+y_2\leq1; \end{array}\right.$$ $$y_j\geq0$$$$j=\overline{1;2}$$.
Предпочтительный вид: 

$$maxf(Y)=3y_1+4y_2$$

$$\left\{\begin{array}{lr} 2y_1+4y_2+\underline{y_3}=4,\\ y_1+y_2+\underline{y_4}=1; \end{array}\right.$$

$$y_j\geq0$$$$j=\overline{1;4}$$.

Базисные переменные: $$y_3=4$$$$y_4=1$$.
Свободные переменные: $$y_1=0$$$$y_2=0$$.
Составим симплексную таблицу и выполним симплексные преобразования: 

Поскольку все оценки переменных неотрицательные, то опорный план первой итерации оптимальный.
Установим соответствие между двойственными переменными:
$$y_1\leftrightarrow x_3$$
$$y_2\leftrightarrow x_4$$
$$y_3\leftrightarrow x_1$$
$$y_4\leftrightarrow x_2$$
Следовательно,

 $$x_1=\Delta_3=0$$$$x_2=\Delta_4=4$$$$x_3=\Delta_1=1$$$$x_4=\Delta_2=0$$.

$$X^*=(0;4;1;0)$$$$f(X^*)=4$$.

Данную задачу можно решать иначе.

Канонический вид:

$$minf(X)=4x_1+x_2+0 \cdot x_3+ 0 \cdot x_4$$;

$$\left\{\begin{array}{lr} 2x_1+x_2-x_3=3, \\ 4x_1+x_2-x_4=4. \end{array}\right.$$

Предпочтительный вид:

$$minf(X)=4x_1+x_2+0 \cdot x_3+ 0 \cdot x_4+M\omega_1+M\omega_2$$;

$$\left\{\begin{array}{lr} 2x_1+x_2-x_3+\underline{\omega_1}=3, \\ 4x_1+x_2-x_4+\underline{\omega_2}=4; \end{array}\right.$$

$$x_1 \geq0$$, $$i=\overline{1; 4}$$; $$\omega_1 \geq0$$, $$\omega_2 \geq0$$.

Дальше решаем $$M$$-задачу.

Выберите несколько вариантов ответов