Анализ оптимального плана симплекс-таблицы
Задание. Предприятие планирует выпуск двух видов продукции I и II, на производство которых расходуется три вида сырья А, В, и С. Потребность aij на каждую единицу j-го вида продукции i-го вида сырья, запас bj соответствующего вида сырья и прибыль cj от реализации единицы j-го вида продукции заданы таблицей.1. Для производства двух видов продукции I и II с планом x1 и x2 единиц составить целевую функцию прибыли Z и соответствующую систему ограничений по запасам сырья, предполагая, что требуется изготовить в сумме не менее n единиц обоих видов продукции.
2. В условиях задачи 1 составить оптимальный план (x1,x2) производства продукции, обеспечивающий максимальную прибыль Z. Определить остатки каждого вида сырья. (Задачу решить симплекс–методом)
3. Построить по полученной системе ограничений многоугольник допустимых решений и найти оптимальный план производства геометрическим путем. Определить соответствующую прибыль Z.
Решение находим с помощью калькулятора. Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.
Определим максимальное значение целевой функции F(X) = 3x1 + 2x2 при следующих условиях-ограничений.
x1 + 2x2<=6
x1 + x2<=5
2x1 + 2x2<=10
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла (<=) вводим базисную переменную x3. В 2-м неравенстве смысла (<=) вводим базисную переменную x4. В 3-м неравенстве смысла (<=) вводим базисную переменную x5.
1x1 + 2x2 + 1x3 + 0x4 + 0x5 = 6
1x1 + 1x2 + 0x3 + 1x4 + 0x5 = 5
2x1 + 2x2 + 0x3 + 0x4 + 1x5 = 10
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| A = |
|
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x3, x4, x5,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,6,5,10)
Базисное решение называется допустимым, если оно неотрицательно.
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 6 | 1 | 2 | 1 | 0 | 0 |
| x4 | 5 | 1 | 1 | 0 | 1 | 0 |
| x5 | 10 | 2 | 2 | 0 | 0 | 1 |
| F(X0) | 0 | -3 | -2 | 0 | 0 | 0 |
Переходим к основному алгоритму симплекс-метода.
Итерация №0.
1. Проверка критерия оптимальности.
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
2. Определение новой базисной переменной.
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.
3. Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (6 : 1 , 5 : 1 , 10 : 2 ) = 5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.
| Базис | B | x1 | x2 | x3 | x4 | x5 | min |
| x3 | 6 | 1 | 2 | 1 | 0 | 0 | 6 |
| x4 | 5 | 1 | 1 | 0 | 1 | 0 | 5 |
| x5 | 10 | 2 | 2 | 0 | 0 | 1 | 5 |
| F(X1) | 0 | -3 | -2 | 0 | 0 | 0 | 0 |
Поскольку в последнем столбце присутствует несколько минимальных элементов 5, то номер строки выбираем по правилу Креко.
Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=5, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.
4. Пересчет симплекс-таблицы.
Формируем следующую часть симплексной таблицы.
Вместо переменной x4 в план 1 войдет переменная x1 .
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=1
На месте разрешающего элемента в плане 1 получаем 1.
В остальных клетках столбца x1 плана 1 записываем нули.
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1 .
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ.
НЭ = СЭ - (А*В)/РЭ
СТЭ - элемент старого плана, РЭ - разрешающий элемент (1), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:
| B | x 1 | x 2 | x 3 | x 4 | x 5 |
| 6-(5 • 1):1 | 1-(1 • 1):1 | 2-(1 • 1):1 | 1-(0 • 1):1 | 0-(1 • 1):1 | 0-(0 • 1):1 |
| 5 : 1 | 1 : 1 | 1 : 1 | 0 : 1 | 1 : 1 | 0 : 1 |
| 10-(5 • 2):1 | 2-(1 • 2):1 | 2-(1 • 2):1 | 0-(0 • 2):1 | 0-(1 • 2):1 | 1-(0 • 2):1 |
| 0-(5 • -3):1 | -3-(1 • -3):1 | -2-(1 • -3):1 | 0-(0 • -3):1 | 0-(1 • -3):1 | 0-(0 • -3):1 |
Получаем новую симплекс-таблицу:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 1 | 0 | 1 | 1 | -1 | 0 |
| x1 | 5 | 1 | 1 | 0 | 1 | 0 |
| x5 | 0 | 0 | 0 | 0 | -2 | 1 |
| F(X1) | 15 | 0 | 1 | 0 | 3 | 0 |
1. Проверка критерия оптимальности.
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.
Окончательный вариант симплекс-таблицы:
| Базис | B | x1 | x2 | x3 | x4 | x5 |
| x3 | 1 | 0 | 1 | 1 | -1 | 0 |
| x1 | 5 | 1 | 1 | 0 | 1 | 0 |
| x5 | 0 | 0 | 0 | 0 | -2 | 1 |
| F(X2) | 15 | 0 | 1 | 0 | 3 | 0 |
Оптимальный план можно записать так:
x3 = 1
x1 = 5
x5 = 0
F(X) = 3•5 = 15
Анализ оптимального плана
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 1-го вида в количестве 1. Значение 0 в столбце x1 означает, что использование x1 - выгодно. Значение 1 > 0 в столбце x2 означает, что использование x2 - не выгодно. Значение 3 в столбце x4 означает, что теневая цена (двойственная оценка) равна 3.Пример. Фирме «Иерихонская сталь» предстоит решить, какое количество чистой стали, и какое количество металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты в расчете на 1т чистой стали равняются 3 у.е., а затраты в расчете на 1 т металлолома – 5у.е. (последнее число больше предыдущего, т.к. использование металлолома сопряжено с его предварительной очисткой). Заказ предусматривает поставку не менее 5 т литья; при этом заказчик готов купить большее количество литья, если фирма «Иерихонская сталь» поставит перед ним такие условия.
Предположим, что запасы чистой стали, ограничены и не превышают 4 т, а запасы металлолома не превышают 6 т. Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7:8. Производственно – технологические условия таковы, что на процессы плавки и литья не может быть отведено более 18 часов, при этом на 1 т стали уходит 3 часа, а на 1 т металлолома – 2 часа производственного времени.
Постройте линейную оптимизационную модель.
Решение.
x1 - чистая сталь, [т], x2 - металлолом, [т]
Ограничения по запасам:
1 ≤ 4
x2 ≤ 6
Ограничения по структуре:
x1 : x2 ≤ 7:8
Ограничения по ресурсам:
3x1 + 2x2 ≤ 18
Ограничения по поставкам:
x1 + x2 ≥ 5
Целевая функция:
3x1 + 5x2 = min
Таким образом, линейная оптимизационная модель имеет вид.
x1 ≤ 4
x2 ≤ 6
8x1 - 7x2 ≤ 0
3x1 + 2x2 ≤ 18
x1 + x2 ≥ 5
x1, x2 ≥ 0
Целевая функция:
3x1 + 5x2 = min