Аннотация лекции. Лекция посвящена симплекс-методу решения задачи линейного программирования. Рассмотрен расчетный пример решения задачи с помощью симплекс-метода.
3.2.1 Пример решения задачи линейного программирования симплекс-методом
Решим следующую
задачу: max -5х1 + 2х3 -5х1 - х2
+ 2х3 ≤
2
-х1 + х3 + х4 ≤ 5 -3х1 + 5х4 ≤ 7 х1-4 ≥ 0
Приведем ее к канонической форме.
max -5х1 + 2х3
-5х1
- х2 + 2х3 + х5 =
2
-х1 + х3 + х4 + х6 = 5
-3х1 + 5х4 + х7 = 7
х1-7 ≥ 0
Теперь пример имеет вид задачи (14) с той разницей, что единичные вектора стоят не при первых трех, а при последних трех переменных - х5, х6 и х7; но изменять обозначения не имеет смысла.
Для удобства дальнейших рассуждений ограничения пронумеруем. При этом обозначим значение целевой функции (-5х1 + 2х3) = z и припишем к системе новое (четвертое) ограничение, после чего задача примет следующий вид: max z
1)
-5х1
- х2 + 2х3 + х5 =
2
2) -х1 + х3 + х4 + х6 = 5 (15)
3) -3х1 + 5х4 + х7 = 7
4) z + 5х1 - 2х3 = 0
х1-7 ≥ 0
Решений такой системы бесконечно много.
При последних трех переменных (дополнительных) стоят единичные столбцы: А5
1 0 0
0 1 0
= 0 , А6 = 0 и А7 = 1 . Поэтому удобно взять переменные х5, х6 и х7 в качестве ба-
зисных. Приравняем их к свободным членам, а остальные – к нулю. Таким образом мы получим исходный опорный план - одно из решений этой системы - Хо =
= (0; 0; 0; 0; 2; 5; 7).
На этом плане значение целевой функции zо = 0 (-5*0 +
+ 2*0 = 0). Отметим, что в системе (15) столбец коэффициентов при переменной z тоже 0
0
единичный (0 - она входит только в ограничение (4) с коэффициентом
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.