04 - Лекция

Симплекс метод на практике

Для изготовления изделий A, B, C используется 3 вида сырья в количестве 360, 192, 180 соответственно. Задана ценность изделий: 9, 10, 16 соответственно. Нормы расходы первого сырья на 3 вида продукции составляет 18, 15, 12. Второго сырья: 6, 4, 8. Третьего: 5, 3, 3. Изделие может производиться в любых соотношениях. Найти план выпуска дающий максимальную прибыль.

Необходимо написать модель
$F = 9 x_{1} + 10 x_{2} + 16 x_{3} \to m a x$
$18 x_{1} + 15 x_{2} + 12 x_{3} \leq 360$
$6 x_{1} + 4 x_{2} + 8 x_{3} \leq 192$
$5 x_{1} + 3 x_{2} + 3 x_{3} \leq 180$
$x_{1, 2, 3} \geq 0$
Перейти к каноническому виду
$F = 9 x_{1} + 10 x_{2} + 16 x_{3} + 0 x 4 + 0 x_{5} + 0 x 6 \to m a x$
$18 x_{1} + 15 x_{2} + 12 x_{3} + x_{4} = 360$
$6 x_{1} + 4 x_{2} + 8 x_{3} + x_{5} = 192$
$5 x_{1} + 3 x_{2} + 3 x_{3} + x_{6} = 180$
$\overset{―}{x_{1}}, \overset{―}{x_{2}}, \overset{―}{x_{3}} = 0$
$X_{(1)} = (0, 0, 0, 360, 192, 180)$
$Б_{1} = (x_{4}, x_{5}, x_{6})$
Строим симплекс таблицу

[\begin{matrix} 9 & 10 & 16 & 0 & 0 & 0 \\ X_{б} & C_{б} & B_{б} & X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & X_{6} & Q \\ X_{4} & 0 & 360 & 18 & 15 & 12 & 1 & 0 & 0 \\ X_{5} & 0 & 192 & 6 & 4 & 8 & 0 & 1 & 0 \\ X_{6} & 0 & 180 & 5 & 3 & 3 & 0 & 0 & 1 \\ Δ K \end{matrix}]

Даем оценку плану

[\begin{matrix} 9 & 10 & 16 & 0 & 0 & 0 \\ X_{б} & C_{б} & B_{б} & X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & X_{6} & Q \\ X_{4} & 0 & 360 & 18 & 15 & 12 & 1 & 0 & 0 & 30 \\ X_{5} & 0 & 192 & 6 & 4 & 8 & 0 & 1 & 0 & 24 \\ X_{6} & 0 & 180 & 5 & 3 & 3 & 0 & 0 & 1 & 60 \\ Δ K & 0 & - 9 & - 10 & - 16 & 0 & 0 & 0 \end{matrix}]

Берем разрешающий столбец по минимальному отрицательному элементу в строке $Δ K$

$Δ = \sum C_{i} a_{i j} - C_{j}$
$Δ_{1} = (0 \cdot 18) + (0 \cdot 6) + (0 \cdot 5) - 9 = - 9$
$Δ_{2} = (0 \cdot 15) + (0 \cdot 4) + (0 \cdot 3) - 10 = - 10$
$Δ_{3} = (0 \cdot 121) + (0 \cdot 8) + (0 \cdot 3) - 16 = - 16$
$Δ_{4, 5, 6} = (0 \cdot 1) + (0 \cdot 0) + (0 \cdot 0) - 0 = 0$
$Q_{13} = \frac{360}{12} = 30$
$Q_{23} = \frac{192}{8} = 24$
$Q_{33} = \frac{180}{3} = 60$

План не оптимален так как содержатся отрицательные элементы в строке $Δ K$
Ищем разрешающий элемент
Разрешающий элемент находится на пересечении разрешающего столбца и строки с минимальным элементом $Q$

Новая итерация
Меняем базис столбец. $X_{3}$ стал главным

[\begin{matrix} 9 & 10 & 16 & 0 & 0 & 0 \\ X_{б} & C_{б} & B_{б} & X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & X_{6} & Q \\ X_{4} & 0 & 72 & 9 & 9 & 0 & 1 & - \frac{3}{2} & 0 \\ X_{3} & 16 & 24 & \frac{3}{4} & \frac{1}{2} & 1 & 0 & \frac{1}{8} & 0 \\ X_{6} & 0 & 108 & \frac{11}{4} & \frac{3}{2} & 0 & 0 & - \frac{3}{8} & 1 \\ Δ K \end{matrix}]

$\frac{15 \cdot 8 - 4 \cdot 12}{8} = 9$
$18 - \frac{6 \cdot 12}{8} = 9$
$\frac{360 \cdot 8 - 192 \cdot 12}{8} = 72$
$\frac{3 \cdot 8 - 3 \cdot 4}{8} = \frac{11}{4}$
$180 - \frac{192 \cdot 3}{8} = 108$

Оцениваем план

[\begin{matrix} 9 & 10 & 16 & 0 & 0 & 0 \\ X_{б} & C_{б} & B_{б} & X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & X_{6} & Q \\ X_{4} & 0 & 72 & 9 & 9 & 0 & 1 & - \frac{3}{2} & 0 & 8 \\ X_{3} & 16 & 24 & \frac{3}{4} & \frac{1}{2} & 1 & 0 & \frac{1}{8} & 0 & 48 \\ X_{6} & 0 & 108 & \frac{11}{4} & \frac{3}{2} & 0 & 0 & - \frac{3}{8} & 1 & 72 \\ Δ K & 0 & 3 & - 2 & 0 & 0 & 2 & 0 \end{matrix}]

План не оптимален, так как присутствует отрицательный элемент в строке $Δ K$
Разрешающий элемент 9 в столбце $X_{2}$

[\begin{matrix} 9 & 10 & 16 & 0 & 0 & 0 \\ X_{б} & C_{б} & B_{б} & X_{1} & X_{2} & X_{3} & X_{4} & X_{5} & X_{6} & Q \\ X_{2} & 10 & 8 & 1 & 1 & 0 & \frac{1}{9} & - \frac{1}{6} & 0 & \frac{8}{9} \\ X_{3} & 16 & 20 & \frac{1}{4} & 0 & 1 & - \frac{1}{12} & - \frac{5}{24} & 0 & 0 \\ X_{6} & 0 & 96 & \frac{5}{4} & 0 & 0 \\ Δ K & 400 & 5 & 20 & 0 & \frac{4}{18} & \frac{5}{3} & 6 \end{matrix}]

Оптимальный план
$\overset{―}{X} = (0, 8, 20, 0, 0, 96)$

Пара кончилась