Анализ оптимального плана симплекс-таблицы

Задание. Предприятие планирует выпуск двух видов продукции 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 =
12100
11010
22001

Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
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.

Скачать решение:xml

Пример. Фирме «Иерихонская сталь» предстоит решить, какое количество чистой стали, и какое количество металлолома следует использовать для приготовления (из соответствующего сплава) литья для одного из своих заказчиков. Пусть производственные затраты в расчете на 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

Перейти к онлайн решению своей задачи

загрузка...