03 - Лекция

Симплекс-метод

Словесный алгоритм

Систему ограничений ЗЛП приводим к канонической форме и целевую функцию ЗЛП к симплексной форме (вводим столько новый неизвестных, сколько ограничений).
Составим симплекс-таблицу из коэффициентов системы и целевой функции в симплексной форме. (Заносим прежде всего базис)
Проверяем матрицы на выполнение критерия оптимальности; если он выполняется, то решение закончено.
При невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности; в случае выполнения последнего решение закончено - нет оптимального плана.
В случае невыполнения обоих критериев, находим разрешающий элемент для перехода к следующей матрице, для чего:
1. выбираем разрешающий столбец по наименьшему из отрицательных элементов целевой строки;
2. выбираем разрешающую строку про критерию выбора разрешающего элемента; на их пересечении находится разрешающий элемент.
С помощью разрешающего элемента и симплекс-преобразования переходим к следующей матрице.
1. Выводится базис ключевой строки, уступая место переменной из ключевого столбца со своими коэффициентами
2. Выполняется строка разрешающая путем деления соответственных элементов ...
3. Если в главной строке есть хотя бы один нулевой элемент, то этот элемент просто переносится
4. Если в главном столбце находится ноль, то эту строчку можно просто переносить
5. Остальные элементы считаются по формуле прямоугольника [фото]
Вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3)

Шаблон матрицы

[\begin{matrix} X_{б} & C_{б} & B & X_{1} & X_{2} & X_{3} & X_{4} & Q_{1} \\ X_{3} \\ X_{4} \\ Δ K \end{matrix}]

Пример

$f = 2 x_{1} + 3 x_{2} \to m a x$
$x_{1} + 3 x_{2} \leq 300$ - сколько ресурсов истратили
$x_{1} + x_{3} \leq 150$
$x_{12} \geq 0$

В каноническом виде:
$f = 2 x_{1} + 3 x_{2} + 0 x_{3} + 0 x_{4} \to m a x$
$x_{1} + 3 x_{2} + x_{3} = 300$
$x_{1} + x_{2} + x_{4} = 150$
$x_{1234} \geq 0$

$\overset{―}{X_{1}} = 0$
$\overset{―}{X_{2}} = 0$
$\overset{―}{x_{1}} = (0, 0, 300, 150)$ - опорное решение
$Б_{1} (x_{3}, x_{4})$ - базисное решение

[\begin{matrix} 2 & 3 & 0 & 0 \\ X_{б} & C_{б} & B & X_{1} & X_{2} & X_{3} & X_{4} & Q_{1} \\ X_{3} & 0 & 300 & 1 & [3] & 1 & 0 & 100 \\ X_{4} & 0 & 150 & 1 & 1 & 0 & 1 & 150 \\ Δ K & 0 & - 2 & - 3 & 0 & 0 \end{matrix}]

$0 \cdot 300 + 0 \cdot 150 = 0$
$Δ = \sum C_{1} a_{i j} - C_{j}$
$Δ_{1} = (0 \cdot 1 + 0 \cdot 1) - 2 = - 2$
$Q_{i j} = \frac{A_{b}}{A_{i j}}$

[\begin{matrix} 2 & 3 & 0 & 0 \\ X_{б} & C_{б} & B & X_{1} & X_{2} & X_{3} & X_{4} & Q_{2} \\ X_{2} & 3 & 100 & \frac{1}{3} & 1 & \frac{1}{3} & 0 & 300 \\ X_{4} & 0 & 150 & [\frac{2}{3}] & 0 & - \frac{1}{3} & 1 & 75 \\ Δ K & 300 & - 1 & 0 & 1 & 0 \end{matrix}]

$= 1 - \frac{1 \cdot 1}{3} = \frac{2}{3}$

[\begin{matrix} 2 & 3 & 0 & 0 \\ X_{б} & C_{б} & B & X_{1} & X_{2} & X_{3} & X_{4} & Q_{3} \\ X_{2} & 3 & 75 & 0 & 1 & \frac{1}{2} & - \frac{1}{2} \\ X_{1} & 2 & 75 & 1 & 0 & - \frac{1}{2} & \frac{3}{2} \\ Δ K & 375 & 0 & 0 & \frac{1}{2} & \frac{3}{2} \end{matrix}]

Решения является оптимальным, так как отсутствуют отрицательные оценки
$X_{1} = 75$
$X_{2} = 75$
$f = 375$