Симплексный метод ИТ
Решите задачу, двойственную к задаче:
$$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$$.
$$\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}$$.
$$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}$$.
Соответствие между переменными двойственных задач устанавливается по правилу: основным переменным первой задачи соответствуют дополнительные переменные второй задачи, а дополнительным переменным первой задачи соответствуют основные переменные второй задачи.
Составьте задачу, двойственную к задаче:
$$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-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$$.
- Приведем модель задачи к каноническому виду с помощью дополнительных переменных $$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.$$
- Приведем модель задачи к предпочтительному виду с помощью искусственных переменных $$\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$$.
Решите симплексным методом задачу:
$$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}$$.
$$\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}$$.
Сиплексные преобразования можно выполнить иначе:
Составьте задачу, двойственную к задаче:
$$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$$.
$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1,m}$$;
$$x_i\geq 0$$, $$i=\overline{1,n}$$.
$$\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)=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}$$.
$$x_i \geq0$$, $$i=\overline{1;3}$$; $$\omega \geq0$$.
Задача с искусственным базисом называется $$M$$-задачей.
При решении $$M$$-задачи по мере выведения искусственных переменных из базиса они выводятся и из симплексной таблицы.
Решите симплексным методом задачу:
$$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$$.
- Составьте двойственную задачу и решите ее.
- Установите соответствие между переменными двойственных задач.
$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1,m}$$;
$$x_i\geq 0$$, $$i=\overline{1,n}$$.
$$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_2\leftrightarrow y_{m+2}$$
$$...$$
$$maxf(Y)=3y_1+4y_2$$;
$$\left\{\begin{array}{lr} 2y_1+4y_2\leq4,\\ y_1+y_2\leq1; \end{array}\right.$$$$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}$$.
$$x_1=\Delta_3=0$$, $$x_2=\Delta_4=4$$, $$x_3=\Delta_1=1$$, $$x_4=\Delta_2=0$$.
Данную задачу можно решать иначе.
Канонический вид:
$$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$$-задачу.
Решите симплексным методом задачу:
$$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$$.
Критерий оптимальности опорного плана задачи: если при максимизации целевой функции все оценки переменных неотрицательные, то план оптимальный. Если опорный план задачи не удовлетворяет критерию оптимальности, то выполняем следующие действия.
- Выбираем наихудшую оценку переменной. В случае максимизации целевой функции – наименьшую отрицательную, а в случае минимизации – наибольшую положительную. Столбец, в которой находится эта переменная, называется разрешающим.
- Для каждой базисной переменной составляем симплексные отношения – находим отношения элементов столбца $$A_0$$ и соответствующих элементов разрешающего столбца. Из полученных отношений выбираем наименьшее. Строку, которой соответствует это отношение, называем разрешающей.
Элемент, который находится на пересечении разрешающих столбца и строки, называется разрешающим элементом $$a_{pp}^{0}$$.
- Переходим к первой итерации симплексной таблицы.
Вносим изменения в базис: переменную, находящуюся в разрешающей строке нулевой итерации, заменяем переменной из разрешающего столбца.
Все элементы разрешающей строки делим на разрешающий элемент и записываем в строку первой итерации (номер строки совпадает с номером строки нулевой итерации).
Все остальные элементы столбца, номер которого совпадает с номером разрешающего столбца нулевой итерации, считаем равными нулю.
Остальные элементы таблицы находим по правилу прямоугольника (рис. 10. 8):
$$a_{ji}^{1}=\frac{a_{ji}^{0} \cdot a_{pp}^{0}-a_{jP}^{0} \cdot a_{Pi}^{0}}{a_{PP}^{0}}$$.
Пояснения к нулевой итерации.
$$\theta_1$$ не существует, так как $$a_{12}=-1<0$$;
$$\theta_2=5:2=2,5$$.
Разрешающий элемент $$a_{pp}=2$$.
$$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$$.
Симплексные отношения:
$$\theta_j=\frac{b_{j}^{0}}{a_{jP}^{0}}$$.
Отрицательные элементы разрешающего столбца и элементы, равные нулю, не образуют симплексных отношений.
Решите симплексным методом задачу:
$$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.$$
Оценка целевой функции (значение целевой функции):
если при минимизации целевой функции все оценки переменных неположительные, то план оптимальный.
Найдем оценки переменных:
Оценки базисных переменных всегда равны нулю.