Симплексный метод решения задач линейного программирования

– количество продукта вида 1, через x2 – количество продукта вида 2, через x3 – количество продукта вида 3, через x4 – количество продукта вида 4.
Цена одного изделия каждого вида соответственно равна: 15, 12, 25 и 18. Необходимо максимизировать целевую функцию:
Fx=15x1+12x2+25x3+18x4→max
Введем следующие ограничения:
6x1+8x2+4x3+7x4≤4600
0,75x1+0,64x2+0,5x3+0,8x4≤510
8x1+12x2+10x3+14x4≤6180
Кроме технологических ограничений следует наложить ограничения на переменные:
x1≥0; x2≥0; x3≥0; x4≥0.
Тогда математическая модель задачи будет следующей:
Fx=15x1+12x2+25x3+18x4→max
6x1+8x2+4x3+7x4≤4600,0,75x1+0,64x2+0,5x3+0,8x4≤510,8x1+12x2+10x3+14x4≤6180, xi≥0;i=1,4.
Найдем оптимальный план симплексным методом.
Построим начальный опорный план задачи.
Для этого приведем задачу к каноническому виду, добавив к левым частям системы ограничений дополнительные переменные xj≥0 j=5,7. В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.
Получаем задачу в канонической форме записи:
Fx=15x1+12x2+25x3+18x4→max
6x1+8x2+4x3+7x4+x5=4600,0,75x1+0,64x2+0,5x3+0,8x4+x6=510,8x1+12x2+10x3+14x4+x7=6180, xi≥0;i=1,7.
Составляем первую симплекс-таблицу:
БП 15 12 25 18 0 0 0 Bi
x1
x2
x3
x4
x5
x6
x7
x5
6 8 4 7 1 0 0 4600
x6
0,75 0,64 0,5 0,8 0 1 0 510
x7
8 12 10 14 0 0 1 6180
F
-15 -12 -25 -18 0 0 0 0
Все элементы столбца свободных членов положительны, поэтому план X10=0;0;0;0;4600;510;6180 является опорным.
Но этот план не оптимален, так как в F-строке имеются отрицательные элементы . Чтобы получить новый опорный план, более близкий к оптимальному плану, выполним симплексные преобразования первой симплексной таблицы. Наибольший по модулю отрицательный коэффициент F-строки указывает, что в новый базис следует ввести переменную x3.
Чтобы определить переменную, выводимую из базиса, составим симплексные отношения и выберем наименьшее из них:
min46004;5100,5;618010=min1150;1020;618=618
Итак, из базиса исключаем переменную x7.
Получаем вторую симплексную таблицу:
БП 15 12 25 18 0 0 0 Bi
x1
x2
x3
x4
x5
x6
x7
x5
2,8 3,2 0 1,4 1 0 -0,4 2128
x6
0,35 0,04 0 0,1 0 1 -0,05 201
x3
0,8 1,2 1 1,4 0 0 0,1 618
F
5 18 0 17 0 0 2,5 15450
В виду отсутствия в F-строке отрицательных элементов, можно утверждать, что опорный план X*=0;0;618;0;2128;201 оптимальный.
Тогда F=15∙0+12∙0+25∙618+18∙0=15450.
Таким образом, необходимо выпускать только продукцию третьего вида в количестве 618 штук, тогда будет обеспечена максимальная прибыль для предприятия равная 15450 ден