3 Симплекс алгоритъм
3.1 Каноничен вид
Пример 1
\[\begin{align*} & \min z = x_1 - x_2 + 3x_3\\ & 2x_1 - x_2 + 3x_3 \leq 5\\ & x_1 + 2x_3 = 8 \\ & -x_1 - 2x_2 \geq 1 \\ & x_1, x_2, x_3 \geq 0 \end{align*}\]
\[ \begin{align*} & \max z = -x_1 + x_2 - 3x_3\\ & 2x_1 - x_2 + 3x_3 + s_1 = 5\\ & x_1 + 2 x_2 = 8\\ & -x_1 - 2x_2 -s_3 = 1\\ & x_1, x_2, x_3, s_1, s_2 \geq 0 \end{align*} \]
Пример 2
\[ \begin{align*} & \max z = 2x_1 + 3x_2 - x_3\\ & x_1 - 2x_2 + x_3 \geq 4\\ & x_1 + x2 - 3x_3 \leq 9 \\ & x_1 + 3x2 + 2x_3 = 10 \\ & x_1, x_3 \geq 0 \end{align*} \]
Променливата \(x_2\) е свободна, следователно я представяме като разлика на две неотрицателни променливи:
\[ x_2 = x_2^{+} - x_{2}^{-} \]
\[ \begin{align*} & \max z = 2x_1 + 3(x_2^{+} - x_{2}^{-}) - x_3\\ & x_1 - 2(x_2^{+} - x_{2}^{-}) + x_3 - s_1 = 4\\ & x_1 + (x_2^{+} - x_{2}^{-}) - 3x_3 + s_2 = 9 \\ & x_1 + 3(x_2^{+} - x_{2}^{-}) + 2x_3 = 10 \\ & x_1, x_2^{+}, x_{2}^{-}, x_3, s_1, s_2 \geq 0 \end{align*} \]
3.2 Опорни планове
3.2.1 Пример 1
Дадена е задачата
\[\begin{align} & 3 x_1 + x_2 + x_3 = 1 \\ & 2 x_1 + x_4 = 1 \end{align}\]
Запишете задачата в матричен вид: \(\mathbf{A} \mathbf{x} = \mathbf{b}\) и проверете дали x^{(1)} = (0, 0, 1, 1) е опорен план.
\[\begin{align*} & \mathbf{A} = \begin{pmatrix} & 3 & 1 & 1 & 0\\ 2 & 0 & 0 & 1 \end{pmatrix} \\ & \mathbf{b} = (0, 1)^T \\ & \mathbf{x} = (x_1, x_2, x_3, x_4)^T \end{align*}\]
3.2.2 Пример 2
Дадена е задачата
\[\begin{align*} & 3 x_1 + x_2 = 1 \\ & 2 x_1 + x_4 = 1 \\ & -2 x_1 + x_3 - 3 x_4 = 0 \end{align*}\]
Запишете задачата в матричен вид: \(\mathbf{A} \mathbf{x} = \mathbf{b}\) и проверете дали \(x^{(1)} = (0, 2, 0, 0)^T\) е опорен план. Кои са възможните базисни променливи за \(x^{(2)} = (0, 1, 0, 0)\).
\[\begin{align*} & \mathbf{A} = \begin{pmatrix} 3 & 1 & 1 & 0\\ 2 & 0 & 0 & 1 \end{pmatrix} \\ & \mathbf{b} = (0, 1)^T \\ & \mathbf{x} = (x_1, x_2, x_3, x_4)^T \end{align*}\]
3.3 Базисно представяне на каноничната задача
- Неотрицателни десни страни
- Една базисна променлива във всяко уравнение уравнение с коефициент 1
3.3.1 Пример 1
\[\begin{align*} & x_1 + x_2 \leq 2 \\ & x_3 + x_4 \leq 8 \\ & x_4 \leq 8 \end{align*}\]
3.3.2 Пример 2
Намерете базисното представяне на каноничния вид на следните две ограничения при базисни променливи \(x_1\) и \(x_3\).
\[\begin{align*} & 2x_1 + 3 x_2 = 0 \\ & x_1 - x_3 + s_2 = -4 \end{align*}\]
3.3.3 Пример 3
Намерете базисното представяне при базисни променливи \(x_1\) и \(x_3\).
\[\begin{align*} & 2x_1 + x_2 + x_3 = 2 \\ & x_1 + x_3 + s_2 = 1 \end{align*}\]
3.4 Симплекс алгоритъм (1)
\[\begin{align*} & x_1: \text{ светла бира (л.)}\\ & x_2: \text{ тъмна бира (л.)} \end{align*}\]
\[\begin{align*} & \max Z(x) = 5x_1 + 5x_2\\ & 2x_1 + x_2 \leq 10 \text{ Хмел}\\ & x_1 + 2x_2 \leq 8 \text{ Малц}\\ & x_1, x_2 \ge 0\\ \end{align*}\]
Каноничният вид на задачата е:
\[\begin{align} \begin{split} \max Z(x) = 5x_1 + 5x_2\\ 2x_1 + x_2 + s_1 = 10 \text{ Хмел}\\ x_1 + 2x_2 + s_2 = 8 \text{ Малц}\\ x_1, x_2, s_1, s_2 \geq 0 \end{split} \label{eq:bier-canonical} \end{align}\]
където \(s_1, s_2\) са допълнителни неотрицателни променливи. В матричен вид каноничната задача изглежда така:
\[\begin{align*} \begin{pmatrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ s_1 \\ s_2 \\ \end{pmatrix} = \begin{pmatrix} 10 \\ 8 \end{pmatrix} \end{align*}\]
Първоначален опорен план намираме, като фиксираме \(x_1, x_2 = 0\) и решаваме системата от уравнения \(\eqref{eq:bier-canonical}\) за \(s_1\) и \(s_2\).
Опорен план ли е \(x^{0} = (0, 0, 10, 8)^T\)? Заместваме с \(x_0\) и получаваме, че е допустим план, тъй като системата уравнения е изпълнена:
\[\begin{align*} \begin{pmatrix} 2 & 1 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{pmatrix} \begin{pmatrix} 0\\ 0\\ 10\\ 8 \end{pmatrix} = \begin{pmatrix} 10\\ 8 \end{pmatrix} \end{align*}\]
\[\begin{align*} \begin{vmatrix} 1 & 0\\ 0 & 1 \end{vmatrix} = 1 - 0 = 1 \neq 0 \end{align*}\]
След като имаме първоначален опорен план (и следователно базисни променливи) е удобно да напишем системата уравнения (eq:bier-canonical) като изразим базисните променливи чрез не-базисните променливи:
\[\begin{align} s_1 = 10 - (2x_1 + x_2) \label{eq:bier-malt}\\ s_2 = 8 - (x_1 + 2x_2) \label{eq:bier-hop}\\ \end{align}\]
същото можем да направим и с целевата функция:
\[ \begin{align} Z = 0 - (-5x_1 - 5x_2) \label{eq:bier-obj} \end{align} \]
След като вече имаме първоначален опорен план, попълваме първата симплекс таблица:
| Таблица 1 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 5 | 5 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(X_B/x_1\) |
| \(s_1\) | 0 | 10 | 2 | 1 | 1 | 0 | 10 / 2 = 5 |
| \(s_2\) | 0 | 8 | 1 | 2 | 0 | 1 | 8 / 1 = 8 |
| \(Z\) | \(Z_j\) | 0 | 0 | 0 | 0 | ||
| \(\Delta_j = Z_j - C_j\) | 0 -5 = 0 | 0 -5 = 0 | 0 | 0 |
където \(C_j\) са коефициентите на променливите в целевата функция, \(C_B\) са коефициентите на базисните променливи в целевата функция. Редът \(Z_j\) получаваме, като образуваме сумата на произведенията на коефициентите на променливите в системата уравнения и коефициентите на базисните променливи в целевата функция. За \(x_1\) получаваме: \(0 \cdot 2 + 0 \cdot 1 = 0\). Индексната оценка на \(x_1\) получаваме, като от \(Z_j\) извадим коефициента на \(x_1\) в целевата функция: \(\Delta_j = Z_j - C_j = 0 - 5 = -5\). По същия начин изчисляваме индексните оценки и на останалите променливи. Обърнете внимание, че тези индексни оценки съответстват на коефициентите на не-базисните променливи в целевата функция в \(\eqref{eq:bier-obj}\). Стойността на целевата функция получаваме, като съберем произведението на \(X_B\) и \(C_B\): \(10 \cdot 0 + 8 \cdot 0 = 0\).
Индексните оценки ни показват с колко би се променила целевата функция, ако увеличим променливата с една единица. Отрицателни индексни оценки означават увеличение на целевата функция. В настоящия пример индексните оценки са отрицателни за \(x_1\) и \(x_2\), което означава, че печалбата на фирмата би нарастнала, ако увеличим производството на светла или тъмна бира. Тъй като нарастването на печалбата е еднакво и за двата продукта (произволно) избираме да увеличим \(x_1\). Въпросът е с колко най-много можем да увеличим производството на светла бира без да нарушаваме ограниченията. Отговор на този въпрос ни дава колконката \(X_B / x_1\). Най-малката стойност в тази колконка е 5, което означава, че можем да увеличим \(x_1\) най-много до 5. За да се убедим, че това е така, можем да заместим с \(x_1 = 8\) в първото уравнение от Системата \(\eqref{eq:bier-malt}\):
\[ s_1 = 10 - (2 \cdot 8 + \underbrace{x_2}_{=0}) = -6 \]
Това уравнение е изпълнено за \(s_1 = -6\), но това нарушава ограничението за неотрицателност на \(s_1\). Избрахме да увеличим \(x_1\) от \(0\) в настоящото решение на 5, т.е. \(x_1\) става базисна променлива. Видяхме, че най-малката стойност на \(X_B / x_1\) е в първия ред на таблицата, който съответства на \(s_1\). Това означава, че \(s_1\) излиза от базиса и в следващото решение на системата ще е нула.
\[ s_1 = 10 - (2 \cdot 5 - \underbrace{x_2}_{= 0}) \implies s_1 = 0. \]
За да видим, дали върхът \((5, 0, 0, 4)\) е оптимален, изразяваме всяка базисна променлива (\(x_1\) и \(s_2\)), както и целевата функция отново с не-базисни променливи:
От
\[\begin{align*} & s_1 = 10 - 2x_1 - x_2\\ & s_2 = 8 - x_1 - 2x_2\\ \end{align*}\]
получаваме
\[\begin{align*} & x_1 = 5 - \frac{1}{2}s_1 - \frac{1}{2}x_2 \\ & s_2 = 8 - \left(5 - \frac{1}{2}s_1 - \frac{1}{2}x_2\right) - 2x_2 \end{align*}\]
\[\begin{align} \begin{split} x_1 = 5 - \frac{1}{2}s_1 - \frac{1}{2}x_2\\ s_2 = 3 + \frac{1}{2}s_1 -\frac{3}{2}x_2 \end{split} \label{eq:bier-canonical-1} \end{align}\]
Изразяваме и целевата функция само с небазисни променливи:
\[\begin{align*} & z = 5\left(5 - \frac{1}{2}s_1 - \frac{1}{2}x_2\right) + 5x_2 \implies \\ & z = 25 - \left(- \frac{5}{2} x_2 + \frac{5}{2}s_1 \right) \end{align*}\]
| Таблица 2 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 5 | 5 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(X_B/x_2\) |
| \(x_1\) | 5 | 5 | 1 | 1/2 | 1/2 | 0 | 5 / (1/2) = 10 |
| \(s_2\) | 0 | 3 | 0 | 3/2 | -1/2 | 1 | 3 / (3/2) = 2 |
| \(Z = 25\) | \(Z_j\) | 5 | 5/2 | 5/2 | 0 | ||
| \(\Delta_j\) | 0 | -5/2 | 5/2 | 0 |
От индексните оценки виждаме, че планът \((5, 0, 0, 3)\) не е оптимален, защото \(x_2\) е не-базисна променлива с отрицателна индексна оценка. Най-гомялото възможно увеличение на \(x_2\) е 2 (втори ред), следователно \(x_2\) влиза в базиса на мястото на \(s_2\).
Преобразуваме системата уравнения \(\eqref{eq:bier-canonical-1}\), така че новите базисни променливи да са от лявата страна на уравненията с коефициент \(1\) и изразяваме целевата функция с небазисните променливи:
\[\begin{align*} & x_1 = 5 - \frac{1}{2}s_1 - \frac{1}{2}x_2 \\ & x_2 = \frac{3}{1.5} + \frac{1}{2\cdot 1.5}s_1 - \frac{1}{1.5}s_2 \end{align*}\]
\[\begin{align*} & x_1 = 5 - \frac{1}{2}s_1 - \frac{1}{2}\left(2 + \frac{1}{3}s_1 - \frac{1}{1.5}s_2\right) \\ & x_2 = 2 + \frac{1}{3}s_1 - \frac{1}{1.5}s_2 \end{align*}\]
\[\begin{align*} & x_1 = 4 - 0.66s_1 + \frac{1}{3}s_2\\ & x_2 = 2 + \frac{1}{3}s_1 - \frac{1}{1.5}s_2 \end{align*}\]
Изразяваме целевата функция само с нулеви променливи:
\[\begin{align*} z = 25 - \frac{5}{2}s_1 + 2.5\left(\frac{1}{3}s_1 - \frac{1}{1.5}s_2\right)\\ z = 30 - (1.66s_1 + 1.66s_2) \end{align*}\]
| Таблица 3 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 5 | 5 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | |
| \(x_1\) | 5 | 4 | 1 | 0 | 2/3 | -1/3 | |
| \(x_2\) | 5 | 2 | 0 | 1 | -1/3 | 2/3 | |
| \(Z = 30\) | \(Z_j\) | 5 | 5 | 1.667 | 1.667 | ||
| \(\Delta_j\) | 0 | 0 | 1.667 | 1.667 |
Планът е оптимален, защото няма небазисни променливи с отрицателни индексни оценки. Така получаваме, че решението на оптимизационната задача е: \((4, 2, 0, 0)\) при стойност на целевата функция \(Z^{*} = 30\). Дефицитни са и двата ресурса: \(s_1 = 0\), \(s_2 = 0\).
3.5 Неограничено решение
Решете задачата с помощта на симплекс алгоритъма.
\[\begin{align*} & \max z = 2x_1 + x_2 \\ & -x_1 + x_2 + s_1 = 10 \\ & -2x_1 + s_2 = 40\\ & x_1, x_2, s_1, s_2 \geq 0 \end{align*}\]
| Таблица 1 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | |||||||
| Базисни пр. | \(C_B\) | \(X_B\) | _ | _ | _ | _ | _ |
| _ | |||||||
| _ | |||||||
| \(Z\) | \(Z_j\) | ||||||
| \(\Delta_j\) |
| Таблица 1 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 2 | 1 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | |
| \(s_1\) | 0 | 10 | -1 | 1 | 1 | 0 | — |
| \(s_2\) | 0 | 40 | -2 | 0 | 0 | 1 | — |
| \(Z\) | \(Z_j\) | 0 | 0 | 0 | 0 | ||
| \(\Delta_j\) | -2 | -1 | 0 | 0 |
\(x_1\) е не-базисна променлива с отрицателна индексна оценка и трябва да стане базисна, но има отрицателни коефициенти, следователно целевата функция е неограничена.
3.6 Празно допустимо множество
Решете задачата с помощта на симплекс алгоритъма.
\[\begin{align*} & \max z = 3x_1 + 2x_2 \\ & 2x_1 + x_2 \leq 2 \\ & 3x_1 + 4x_2 \geq 12 \\ & x_1, x_2 \geq 0 \end{align*}\]
| Таблица 1 | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| \(C_j\) | |||||||||
| Базисни пр. | \(C_B\) | \(X_B\) | _ | _ | _ | _ | _ | _ | _ |
| _ | |||||||||
| _ | |||||||||
| \(Z\) | \(Z_j\) | ||||||||
| \(\Delta_j\) |
| Таблица 1 | ||||||||
|---|---|---|---|---|---|---|---|---|
| \(C_j\) | 3 | 2 | 0 | 0 | -М | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(А_2\) | |
| \(s_1\) | 0 | 2 | 2 | 1 | 1 | 0 | 0 | |
| \(А_2\) | -М | 12 | 3 | 4 | 0 | -1 | 1 | |
| \(Z\) | \(Z_j\) | -3M | -4M | 0 | M | -M | ||
| \(\Delta_j\) | -2M - 3 | -4M - 2 | 0 | M | 0 |
- <- (1) / 1
- <- (2) - 4(1)
| Таблица 2 | ||||||||
|---|---|---|---|---|---|---|---|---|
| \(C_j\) | 3 | 2 | 0 | 0 | -М | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(А_2\) | |
| \(x_2\) | 2 | 2 | 2 | 1 | 1 | 0 | 0 | |
| \(А_2\) | -М | 4 | -5 | 0 | -4 | -1 | 1 | |
| \(Z\) | \(Z_j\) | 5M + 4 | 2 | 4M + 2 | M | -M | ||
| \(\Delta_j\) | 5M + 1 | 0 | 4M + 2 | M | 0 |
Всички индексни оценки са неотрицателни, следователно оптималното решение е \(x_1 = 0, x_2 = 2, A_2 = 4, s_1 = 0, s_2 = 0\). Тъй като решението включва положителна стойност на \(А_2\), задачата няма допустимо решение, тъй като е нарушено второто ограничение:
\[\begin{align*} & 3 x_1 + 4x_2 -s_2 - A_2 = 12\\ & 3 \cdot 0 + 4 \cdot 2 - 0 - 4 = 12\\ & 8 - 4 = 12 \end{align*}\]
3.7 Множество решения
Решете задачата с помощта на симплекс алгоритъма.
\[\begin{align*} & \max z = 2x_1 + 4x_2 \\ & x_1 + 2x_2 \leq 5 \\ & x_1 + x_2 \leq 4 \\ & x_1, x_2 \geq 0 \end{align*}\]
| Таблица 1 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 2 | 4 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | _ |
| \(s_1\) | 0 | 5 | 1 | 2 | 1 | 0 | |
| \(s_2\) | 0 | 4 | 1 | 1 | 0 | 1 | |
| \(Z\) | \(Z_j\) | 0 | 0 | 0 | 0 | ||
| \(\Delta_j\) | -2 | -4 | 0 | 0 |
- <- (1) / 2
- <- (2) - (1)
| Таблица 2 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 2 | 4 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | _ |
| \(x_2\) | 4 | 5/2 | 1/2 | 1 | 1/2 | 0 | |
| \(s_2\) | 0 | 3/2 | 1/2 | 0 | -1/2 | 1 | |
| \(Z\) | \(Z_j\) | 2 | 4 | 2 | 0 | ||
| \(\Delta_j\) | 0 | 0 | 2 | 0 |
- <- (2) / (1/2)
- <- (1) - (2)/2
| Таблица 3 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 2 | 4 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | _ |
| \(x_2\) | 4 | 1 | 0 | 1 | 1 | -1 | |
| \(x_1\) | 2 | 3 | 1 | 0 | -1 | 2 | |
| \(Z\) | \(Z_j\) | 2 | 4 | 2 | 0 | ||
| \(\Delta_j\) | 0 | 0 | 2 | 0 |
Всички оптимални решения са дадени от:
\[ x^* = \alpha \begin{pmatrix} 0 \\ 5/2 \\ 0 \\ 3/2 \end{pmatrix} + (1 -\alpha) \begin{pmatrix} 3 \\ 1 \\ 0 \\ 0 \end{pmatrix},\quad \alpha \in [0, 1] \]
3.8 Изродено решение
Решете задачата с помощта на симплекс алгоритъма.
\[\begin{align*} & \max z = x_1 + 3x_2 \\ & x_1 + 4x_2 \leq 8 \\ & x_1 + 2x_2 \leq 4 \\ & x_1, x_2 \geq 0 \end{align*}\]
| Таблица 1 | ||||||||
|---|---|---|---|---|---|---|---|---|
| \(C_j\) | ||||||||
| Базисни пр. | \(C_B\) | \(X_B\) | _ | _ | _ | _ | _ | _ |
| _ | ||||||||
| _ | ||||||||
| \(Z\) | \(Z_j\) | |||||||
| \(\Delta_j\) |
| Таблица 1 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 1 | 3 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | _ |
| \(s_1\) | 0 | 8 | 1 | 4 | 1 | 0 | |
| \(s_2\) | 0 | 4 | 1 | 2 | 0 | 1 | |
| \(Z\) | \(Z_j\) | 0 | 0 | 0 | 0 | ||
| \(\Delta_j\) | -1 | -3 | 0 | 0 |
- <- (2) / 2
- <- (1) - 4(2)
| Таблица 2 | |||||||
|---|---|---|---|---|---|---|---|
| \(C_j\) | 1 | 3 | 0 | 0 | |||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | _ |
| \(s_1\) | 0 | 0 | -1 | 0 | 1 | -2 | |
| \(x_2\) | 3 | 2 | 1/2 | 1 | 0 | 1/2 | |
| \(Z\) | \(Z_j\) | 3/2 | 3 | 0 | 3/2 | ||
| \(\Delta_j\) | 1/2 | 0 | 0 | 3/2 |
Оптималният план е \((0, 3, 0, 0)\), който е изроден.