Оптимальное планирование. Постановка задачи: предприятие располагает ресурсами сырья, рабочей силы и оборудованием, необходимым для производства любого из 3-х видов производимых товаров. Затраты ресурсов, прибыль, получаемая от реализации единицы товара, а так же запасы ресурсов указаны в таблице:
Вид ресурса Затраты ресурса на единицу товара Запас ресурса
Сырьё, кг
3 5 2 260
Рабочая сила, ч. 22 14 18 400
Оборудование, станко-час. 10 14 8 128
Прибыль, руб. 30 25 56
Решение:
решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 30×1+25×2+56×3 при следующих условиях-ограничений.
3×1+5×2+2×3≤260
22×1+14×2+18×3≤400
10×1+14×2+8×3≤128
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.
3×1+5×2+2×3+x4 = 260
22×1+14×2+18×3+x5 = 400
10×1+14×2+8×3+x6 = 128
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
EQ A = b(a al co6 hs3 (3;5;2;1;0;0;22;14;18;0;1;0;10;14;8;0;0;1))
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6
Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,0,260,400,128)
Базисное решение называется допустимым, если оно неотрицательно.
Базис
B x1 x2 x3 x4 x5 x6
x4 260 3 5 2 1 0 0
x5 400 22 14 18 0 1 0
x6 128 10 14 8 0 0 1
F(X0) 0 -30 -25 -56 0 0 0
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai3
и из них выберем наименьшее:
min (260 : 2 , 400 : 18 , 128 : 8 ) = 16
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (8) и находится на пересечении ведущего столбца и ведущей строки.
Базис
B x1 x2 x3 x4 x5 x6 min
x4 260 3 5 2 1 0 0 130
x5 400 22 14 18 0 1 0 22.222
x6 128 10 14 8 0 0 1 16
F(X1) 0 -30 -25 -56 0 0 0
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x3.
Строка, соответствующая переменной x3 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=8. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули.
Таким образом, в новом плане 1 заполнены строка x3 и столбец x3. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ – (А*В)/РЭ
СТЭ – элемент старого плана, РЭ – разрешающий элемент (8), А и В – элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
B x1 x2 x3 x4 x5 x6
260-(128 • 2):8 3-(10 • 2):8 5-(14 • 2):8 2-(8 • 2):8 1-(0 • 2):8 0-(0 • 2):8 0-(1 • 2):8
400-(128 • 18):8 22-(10 • 18):8 14-(14 • 18):8 18-(8 • 18):8 0-(0 • 18):8 1-(0 • 18):8 0-(1 • 18):8
128 : 8 10 : 8 14 : 8 8 : 8 0 : 8 0 : 8 1 : 8
0-(128 • -56):8 -30-(10 • -56):8 -25-(14 • -56):8 -56-(8 • -56):8 0-(0 • -56):8 0-(0 • -56):8 0-(1 • -56):8
Получаем новую симплекс-таблицу:
Базис
B x1 x2 x3 x4 x5 x6
x4 228 0.5 1.5 0 1 0 -0.25
x5 112 -0.5 -17.5 0 0 1 -2.25
x3 16 1.25 1.75 1 0 0 0.125
F(X1) 896 40 73 0 0 0 7
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
Базис
B x1 x2 x3 x4 x5 x6
x4 228 0.5 1.5 0 1 0 -0.25
x5 112 -0.5 -17.5 0 0 1 -2.25
x3 16 1.25 1.75 1 0 0 0.125
F(X2) 896 40 73 0 0 0 7
Оптимальный план можно записать так:
x1 = 0, x2 = 0, x3 = 16
F(X) = 30*0 + 25*0 + 56*16 = 896
