4 Дуални задачи и постоптимален анализ
Да разгледаме следната задача:
\[\begin{align} \begin{split} \max z = 5x_1 + 7x_2\\ x_1 + 2x_2 \leq 10 \\ 2x_1 + x_2 \leq 8 \\ x_1 , x_2 \geq 0 \end{split} \label{eq:duals-proof-ex} \end{align}\]
Оптимумът в тази задача се постига при \(x_1 = 2, x_2 = 4\) със стойност на целевата функция \(z^* = 38\). Искаме да използваме неравенствата в \(\eqref{eq:duals-proof-ex}\), за да докажем, че това е възможно най-голямата стойност на целевата функция.
| Последна таблица | ||||||
|---|---|---|---|---|---|---|
| \(C_j\) | 2 | 1 | 0 | 0 | ||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) |
| \(x_2\) | 7 | 4 | 0 | 1 | 2/3 | -1/3 |
| \(x_1\) | 5 | 2 | 1 | 0 | -1/3 | 2/3 |
| \(Z\) | \(Z_j\) | 5 | 7 | 3 | 1 | |
| \(\Delta_j\) | 0 | 0 | 3 | 1 |
Въпрос: възможно ли е да намерим най-малката горна граница на целевата функция без да налучкваме коефициентите, с които да комбинираме уравненията?
4.1 Дуална задача (0)
Намерете дуалната задача за следната първична задача:
\[\begin{align*} & \max 5 x_1 + 12 x_2 + 4 x_33 \\ & x_1 + 2x_2 + x_3 \leq 10 \\ & 2x_1 - x_2 + 3x_3 \leq 8 \\ & x_1, x_2, x_3 \geq 0 \end{align*}\]
Каноничен вид на задачата:
\[ \max 5 x_1 + 12 x_2 + 4 x_33 + 0 s_1 + 0 s_2\\ \]
\[\begin{align*} x_1 + 2x_2 + x_3 + s_1& = 10 \quad \text{дуална променлива } y_1 \\ 2x_1 - x_2 + 3x_3 + s_2 & = 8 \quad \text{дуална променлива } y_2\\ x_1, x_2, x_3, s_1, s_2 & \geq 0 \end{align*}\]
Дуалната задача ще има 2 целеви променливи \(y_1\) и \(y_2\), по една за всяко ограничение.
Ограничения на дуалната задача
\[\begin{align*} & y_1 + 2 y_2 \geq 5 \\ & 2y_1 - y_2 \geq 12 \\ & y_1 + 3 y_2 \geq 4 \\ & y_1 + 0 y_2 \geq 0 \\ & 0y_1 + y_2 \geq 0 \end{align*}\]
Целева функция на дуалната задача:
\[ \min 10 y_1 + 8 y_2 \]
Същото представяне можем да получим чрез транспониране на матрицата от коефициентите на каноничната задача.
Ограничения на каноничната задача:
\[ \underbrace{\begin{pmatrix} 1 & 2 & 1 & 1 & 0 \\ 2 & -1 & 3 & 0 & 1 \end{pmatrix}}_{A} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ s_1 \\ s_2 \end{pmatrix} = \begin{pmatrix} 10 \\ 8 \end{pmatrix} \]
\[ А^T = \begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 1 & 3 \\ 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \]
\[ \begin{pmatrix} 1 & 2 \\ 2 & -1 \\ 1 & 3 \\ 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \geq \begin{pmatrix} 5 \\ 12 \\ 4 \\ 0 \\ 0 \end{pmatrix} \]
4.2 Дуална задача (1)
\[\begin{align*} & \max z = 5x_1 + 12x_2 + 4x_3\\ & x_1 + 2x_2 + x_3 \leq 10 \\ & 2x_1 - x_2 + 3x_3 = 8 \\ & x_1 , x_2 , x_3 \geq 0 \end{align*}\]
Каноничен вид:
\[\begin{align*} & \max z = 5x_1 + 12x_2 + 4x_3 + 0s_1 \\ & x_1 + 2x_2 + x_3 + s_1 = 10 \\ & 2x_1 - x_2 + 3x_3 = 8 \\ & x_1 , x_2 , x_3 \geq 0 \end{align*}\]
Ограничения на дуалната задача
\[\begin{align*} & y_1 + 2y_2 \geq 5 \\ & 2 y_1 - y_2 \geq 12 \\ & y_1 + 3y_2 \geq 4 \\ & y_1 + 0 y_2 \geq 0 \\ & y_2 \text{ неограничена} \end{align*}\]
Целева функция на дуалната задача
\[ \min 10 y_1 + 8 y_2 \]
4.3 Дуална задача (2)
\[\begin{align*} & \max z = 15x_1 + 12x_2\\ & x_1 + 2x_2 \leq 3 \\ & 2x_1 - 4x_2 \geq 5 \\ & x_1, x_2 \geq 0 \end{align*}\]
Каноничен вид на задачата
\[\begin{align*} & \max z = 15x_1 + 12x_2 + 0s_1 + 0s_2\\ & x_1 + 2x_2 - s_1 = 3 \\ & 2x_1 - 4x_2 + s_2 = 5 \\ & x_1, x_2, s_1, s_2 \geq 0 \end{align*}\]
Ограничения на дуалната задача
\[\begin{align*} & y_1 + 2y_2 \geq 15 \\ & 2 y_1 + 4 y_2 \geq 12 \\ & -y_1 + 0y_2 \geq 0 \implies y_1 \leq 0 \\ & 0y_1 + y_2 \geq 0 \implies y_2 \geq 0 \end{align*}\]
Целева функция на дуалната задача:
\[ \min 3 y_1 + 5 y_2 \]
4.4 Дуална задача (3)
\[\begin{align*} & \max z = 5x_1 + 6x_2\\ & x_1 + 2x_2 = 5 \\ & -x_1 + 5x_2 \geq 3 \\ & 4x_1 + 7x_2 \leq 8 \\ & x_1 \text{ неограничена}, x_2 \geq 0 \end{align*}\]
\[\begin{align*} & \max z = 5x_1^{-} - 5 x_1^{+} + 6x_2 + 0s_1 + 0s_2\\ & x_1^{-} - x_1^{+} + 2x_2 = 5 \\ & -x_1^{-} + x_1^{+} + 5x_2 - s_1 = 3 \\ & 4x_1^{-} - 4 x_1^{+} + 7x_2 + s_2 = 8 \\ & x_1^{-}, x_{1}^{+}, x_2, s_1, s_2 \geq 0 \end{align*}\]
Ограничения на дуалната задача:
\[\begin{align*} & y_1 - y_2 + 4y_3 \geq 5\\ & -y_1 + y_2 - 4y_3 \geq -5 \\ & 2y_1 + 5 y_2 + 7 y_3 \geq 6 \\ & 0 y_1 + 0y_2 + 0 y_3 \geq 0 \\ & -y_1 + 0y_2 + 0 y_3 \geq 0 \implies y_1 \leq 0 \\ & 0y_1 - y_2 + 0 y_3 \geq 0 \implies y_2 \geq 0 \end{align*}\]
\[\begin{align*} & y_1 - y_2 + 4y_3 = 5\\ & 2y_1 + 5 y_2 + 7 y_3 \geq 6 \\ & 0 y_1 + 0y_2 + 0 y_3 \geq 0 \\ & y_1 \leq 0 \\ & y_2 \geq 0 \end{align*}\]
4.5 Дуална задача (4)
\[\begin{align*} & \max 5x_1 + 4x_2\\ & 6x_1 + 4x_2 \leq 24 \quad \text{ресурс 1}\\ & x_1 + 2x_2 \leq 6 \quad \text{ресурс 2} \\ & -x_1 + x_2 \leq 1 \quad \text{ресурс 3} \\ & x_2 \leq 2 \quad \text{ресурс 4} \end{align*}\]
Оптимумът се постига при \(x_1 = 3, x_2 = 1.5\) и стойност на целевата функция \(z = 21\). Проверете дали \(y_1 = 0.75, y_2 = 0.5, y_3 = y_4 = 0\) е оптимум на дуалната задача.
Целевата функция на дуалната задача е
\[ g = 24 y_1 + 6 y_2 + y_3 + 2 y_4 \]
Стойността й за \(y_1 = 0.75, y_2 = 0.5, y_3 = y_4 = 0\) е:
\[g = 24 \cdot 0.75 + 6 \cdot 0.5 + 0 + 2 \cdot 0 = 21\]
Това е и оптимум на дуалната задача, тъй като стойностите на първичната и на целевата функция съвпадат.
4.6 Дуална задача (5)
Предприятие произвежда три вида детски играчки: влакчета (\(x_1\) на брой), камиончета (\(x_2\) на брой) и коли (\(x_3\) на брой). Целевата функция при оптимизацията е прогнозираната печалба (в лв.) от продажбата на тези играчки.
\[\begin{align*} & \max z = 3x_1 + 2x_2 + 5x_3 \\ & x_1 + 2x_2 + x_3 \leq 430 \quad \text{Персонал} \\ & 3x_1 + 2x_3 \leq 460 \quad \text{Пластмаса} \\ & x_1 + 4x_2 \leq 420 \quad \text{Метал} \\ & x_1, x_2, x_3 \geq 0 \end{align*}\]
Оптималния производствен план се постига при \(x_1 = 0, x_2 = 100, x_3 = 230, z = 1350\). Оптималното решение на дуалната задача е \(y_1 = 1, y_2 = 2, y_3 = 0\).
- Кои са дефицитните ресурси в оптималното решение?
- В оптималното решение предприятието не произвежда влакчета. С колко лева би намаляла печалбата на предприятието, ако то реши да произведе една единица от този продукт?
- Управителният съвет на предприятието обмисля да продаде десет единици от третия ресурс (метал) за 2 лв./единица. Изгоден ли е този ход за предприятието?
- Управителният съвет обмисля производството на нов продукт с прогнозна печалба на единица от 3 лв. За производството му са нужни една единица персонал и две единици метал. Преценете дали този ход ще е изгоден за предприятието.
4.7 Връзка между решенията на първичната и дуалната задача
| Първична задача | Дуална задача |
|---|---|
| Множество решения | Изродено решение |
| Едно неизродено решение | Едно неизродено решение |
| Множество неизродени решения | Едно изродено решение |
| Едно изродено решение | Множество решения |
4.8 Анализ на чувствителността
Определете допустимите граници на промяна на трите ресурса в следната задача:
\[\begin{align*} & \max z = 3x_1 + 2x_2 + 5x_3\\ & x_1 + 2x_2 + x_3 \leq 20 \\ & 3x_1 + 2x_3 \leq 30 \\ & x_1 + 4x_2 \leq 40 \end{align*}\]
Нека да изразим промяната в трите ресурса съответно с \(d_1, d_2, d_3\). Тогава първоначалната задача изглежда по следния начин:
\[\begin{align*} & \max z = 3x_1 + 2x_2 + 5x_3\\ & x_1 + 2x_2 + x_3 \leq 20 + d_1 \\ & 3x_1 + 2x_3 \leq 30 + d_2 \\ & x_1 + 4x_2 \leq 40 + d_3 \end{align*}\]
и има каноничен вид:
\[\begin{align*} & \max z = 3x_1 + 2x_2 + 5x_3\\ & x_1 + 2x_2 + x_3 + s_1 = 20 + d_1 \\ & 3x_1 + 2x_3 + s_2 = 30 + d_2 \\ & x_1 + 4x_2 + s_3 = 40 + d_3 \end{align*}\]
Първоначалната симплекс таблица е:
| Таблица 1 | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(C_j\) | ||||||||||||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | Съотн. | \(d_1\) | \(d_2\) | \(d_3\) |
| \(s_1\) | 0 | 20 | 1 | 2 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | |
| \(s_2\) | 0 | 30 | 3 | 0 | 2 | 0 | 1 | 0 | 0 | 1 | 0 | |
| \(s_3\) | 0 | 40 | 1 | 4 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | |
| \(Z\) | \(Z_j\) | |||||||||||
| \(\Delta_j\) |
Таблицата при оптималния план е:
| Таблица опт. | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| \(C_j\) | ||||||||||||
| Базисни пр. | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(x_3\) | \(s_1\) | \(s_2\) | \(s_3\) | Съотн. | \(d_1\) | \(d_2\) | \(d_3\) |
| \(x_2\) | 2 | 2.5 | -1/4 | 1 | 0 | 1/2 | -1/4 | 0 | 1/2 | -1/4 | 0 | |
| \(x_3\) | 5 | 15 | 3/2 | 0 | 1 | 0 | 1/2 | 0 | 0 | 1/2 | 0 | |
| \(s_3\) | 0 | 30 | 2 | 0 | 0 | -2 | 1 | 1 | -2 | 1 | 1 | |
| \(Z = 80\) | \(Z_j\) | 7 | 2 | 5 | 1 | 2 | 0 | |||||
| \(\Delta_j\) | 4 | 0 | 0 | 1 | 2 | 0 |
Оптималният план е \(x_1 = 0, x_2 = 2.5, x_3 = 15, s_1 = 0, s_2 = 0, s_3 = 30\). Кои ресурси са дефицитни? Какви са скритите цени на ресурсите? Ако трябва да се лишим от една единица от втория ресурс, колко допълнителни единици от първия ще са ни нужни, за да запазим една и съща стойност на целевата функция?
Можем да изразим оптималното решение по следния начин:
\[\begin{align*} & z = 80 - (-d_1 - 2d_2 - 0 \cdot d3)\\ & x_2 = 2.5 + \frac{1}{2}d_1 - \frac{1}{4}d_2 \\ & x_3 = 15 + \frac{1}{2}d_2 \\ & s_3 = 30 - 2 d_1 + d_2 + d_3 \end{align*}\]
Настоящото решение остава допустимо, ако всички базисни променливи са неотрицателни, когато варираме наличността на ресурсите.
\[\begin{align} z = 80 + d_1 + 2d_2 + 0 \cdot d3 \label{eq:simplex-postopt-obj} \\ x_2 = 2.5 + \frac{1}{2}d_1 - \frac{1}{4}d_2 \geq 0 \label{eq:simplex-postopt-constr-1} \\ x_3 = 15 + \frac{1}{2}d_2 \geq 0 \label{eq:simplex-postopt-constr-2} \\ s_3 = 30 - 2 d_1 + d_2 + d_3 \label{eq:simplex-postopt-constr-3} \geq 0 \end{align}\]
От \(\eqref{eq:simplex-postopt-obj}\) директно можем да видим скритите цени на ресурсите. От неравенствата \(\eqref{eq:simplex-postopt-constr-1}\) до \(\eqref{eq:simplex-postopt-constr-3}\) можем да изведем граници на допустимата промяна на ресурсите, когато променяме наличността само на един от тях. Ако променяме само първия ресурс (и не променяме другите два):
\[ x_2 = 2.5 + \frac{1}{2}d_1 \geq 0 \implies d_1 \geq -5 \\ x_3 = 15 \geq 0 \\ s_3 = 30 - 2 d_1 \geq 0 \implies d_1 \leq 15 \]
4.9 Пример 1
Дадена е последната симплекс таблица. Определете алгебрично допустимата промяна на двата ресурса.
| Таблица 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 |
\[\begin{align*} x^* = \begin{pmatrix} 4 \\ 2 \\ 0 \\ 0 \end{pmatrix}, v_1^{*} = \begin{pmatrix} 2/3 \\ -1/3 \\ 0 \\ 0 \\ \end{pmatrix} \\ x^* + \epsilon v_1(x^*) \geq 0 \implies \\ \begin{pmatrix} 4 + 2 \epsilon / 3 \\ 2 -\epsilon/3 \\ 0 \\ 0 \\ \end{pmatrix} \geq 0 \end{align*}\]
От първото неравенство получаваме:
\[ 4 + 2 \epsilon / 3 \geq 0 \implies \epsilon \geq -6 \]
От второто неравенство получаваме:
\[ 2 - \epsilon / 3 \geq 0 \implies \epsilon \leq 6 \] Така получаваме допустими граници на промяна \(\epsilon \in [-6, 6]\).
4.10 Пример 2
При дадени последни две таблици на симплекс метода, определете допустимите граници на промяна на ресурсите за всички стойности на \(\alpha\).
| Таблица 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 |
| Таблица 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 |
Всички оптимални решения са дадени от:
\[\begin{align*} 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] \\ x^* = \begin{pmatrix} 3(1 - \alpha) \\ 7/2 - \alpha \\ 0 \\ 3/2 \end{pmatrix} \end{align*}\]
За втория ресурс претегленото средно от вектор-стълбовете е дадено от:
\[\begin{align*} v_1(x^*) = \alpha \begin{pmatrix} 0 \\ 1/2 \\ 0 \\ -1/2 \end{pmatrix} + (1 - \alpha) \begin{pmatrix} -1 \\ 1 \\ 0 \\ 0 \end{pmatrix} \\ v_1(x^*) = \begin{pmatrix} \alpha - 1 \\ 1 - \alpha / 2 \\ 0 \\ -\alpha / 2 \end{pmatrix} \end{align*}\]
\[\begin{align*} x^* + \epsilon v_1(x^*) \geq 0 \implies \\ \begin{pmatrix} 3(1 - \alpha) \\ 7/2 - \alpha \\ 0 \\ 3/2 \end{pmatrix} + \epsilon \begin{pmatrix} \alpha - 1 \\ 1 - \alpha / 2 \\ 0 \\ -\alpha / 2 \end{pmatrix} \geq 0 \implies \\ \begin{pmatrix} 3(1 - \alpha) + \epsilon (\alpha - 1) \\ 7/2 - \alpha + \epsilon (1 - \alpha / 2) \\ 0 \\ 3/2 - \epsilon \alpha / 2 \end{pmatrix} \geq 0 \end{align*}\]
От първото неравенство получаваме за \(\alpha \neq 1\).
\[\begin{align*} 3 - 3\alpha + \epsilon (\alpha - 1) \geq 0\\ \epsilon (\alpha - 1) \geq 3(\alpha - 1) \\ \epsilon \leq 3 \end{align*}\]
В последната стъпка делим на \(1 - \alpha < 0\) и трябва да посоката на неравенството. От последното неравенство получаваме за \(\alpha \neq 0\):
\[\begin{align*} 3/2 - \epsilon \alpha / 2 \geq 0 \\ \epsilon \alpha \leq 3 \\ \epsilon \leq 3 / \alpha \end{align*}\]
Третото неравенство е:
\[\begin{align*} 7/2 - \alpha + \epsilon (1 - \alpha / 2) \geq 0 \\ \epsilon (1 - \alpha / 2) \geq \alpha - 7/2 \\ \epsilon (2 - \alpha ) \geq 2\alpha - 7 \\ \epsilon \geq \frac{2 \alpha - 7}{2 - \alpha} \end{align*}\]
4.11 Пример дуална зазача
Дадена е задачата:
\[\begin{align} \min z = -x_2 \\ x_1 - x_2 \leq 1 \\ x_1 + x_2 \leq 4 \\ x_1 - x_2 \geq -1 \\ x_1 \leq 2 \\ x_2 \leq 2 \\ x_1, x_2 \geq 0 \end{align}\]
и симплекс таблицата в последната итерация на алгоритъма.
| \(C_J\) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | ||
| B | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) |
| \(s_1\) | 0 | 2 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
| \(s_2\) | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | -2 |
| \(x_2\) | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| \(s_4\) | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | -1 |
| \(x_1\) | 0 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 1 |
| z | 2 | \(Z_j\) | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| \(\Delta_j = Z_j - C_j\) | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
В тази таблица \(\Delta_5 = Z_5-C_5=0\) и \(s_3\) не е в базиса (т.е. \(s_3=0\)).
Това сочи, че е възможно да съществува повече от едно оптимално решение. Когато сложим \(s_3\) в базиса можем да получим друг оптимум при една и съща стойност на целевата функция.
Трансформираме таблицата в новия базисен вид:
- <- (2)
- <- (1) - (2)
- <- (3)
- <- (4) - (2)
- <- (5) - (2)
| \(C_J\) | 0 | 1 | 0 | 0 | 0 | 0 | 0 | ||
| B | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | \(s_4\) | \(s_5\) |
| \(s_1\) | 0 | 1 | 0 | 0 | 1 | -1 | 0 | 0 | 2 |
| \(s_3\) | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | -2 |
| \(x_2\) | 1 | 2 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| \(s_4\) | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 1 |
| \(x_1\) | 0 | 2 | 1 | 0 | 0 | 1 | -1 | 0 | -1 |
| z | 2 | \(Z_j\) | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| \(\Delta_j = Z_j - C_j\) | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
4.12 Дуална задача - изродено решение на първичната задача
Дадена е задачата
\[ \begin{align} & \max z = 3x1 + 2x2 \\ & x1 + x2 \leq 10 \\ & x1 \leq 5 \\ & x2 \leq 5 \\ & x1,x2 \geq 0 \end{align} \]
Дадени са и таблиците на симплекс алгоритъма
| Iteration-2 | \(C_j\) | 3 | 2 | 0 | 0 | 0 | \(X_B / x_2\) | |
| B | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | |
| \(s_1\) | 0 | 5 | 0 | 1 | 1 | -1 | 0 | |
| \(x_1\) | 3 | 5 | 1 | 0 | 0 | 1 | 0 | |
| \(s_3\) | 0 | 5 | 0 | 1 | 0 | 0 | 1 | |
| z=15 | \(Z_j\) | 3 | 0 | 0 | 3 | 0 | ||
| \(\Delta = Z_j - C_j\) | 0 | -2 | 0 | 3 | 0 |
| Iteration-3(1) | \(C_j\) | 3 | 2 | 0 | 0 | 0 | ||
| B | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | |
| \(x_2\) | 2 | 5 | 0 | 1 | 1 | -1 | 0 | |
| \(x_1\) | 3 | 5 | 1 | 0 | 0 | 1 | 0 | |
| \(s_3\) | 0 | 0 | 0 | 1 | -1 | 1 | 1 | |
| z=15 | \(Z_j\) | 3 | 2 | 2 | 1 | 0 | ||
| \(\Delta_j = Z_j - C_j\) | 0 | 0 | 2 | 1 | 0 |
| Iteration-3(2) | \(C_j\) | 3 | 2 | 0 | 0 | 0 | ||
| B | \(C_B\) | \(X_B\) | \(x_1\) | \(x_2\) | \(s_1\) | \(s_2\) | \(s_3\) | |
| \(s_1\) | 0 | 0 | _ | _ | _ | _ | _ | |
| \(x_1\) | 3 | 5 | _ | _ | _ | _ | _ | |
| \(x_2\) | 2 | 5 | _ | _ | _ | _ | _ | |
| z=15 | \(Z_j\) | _ | _ | _ | _ | _ | ||
| \(\Delta_j = Z_j - C_j\) | 0 | 0 | 0 | 3 | 2 |