Расчетный пример решения задачи с помощью симплекс-метода. Значение целевой функции

Страницы работы

Фрагмент текста работы

Аннотация лекции. Лекция посвящена симплекс-методу решения задачи линейного программирования. Рассмотрен расчетный пример решения задачи с помощью симплекс-метода.

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; 0; 0; 0; 2; 5; 7). 

                                 На этом плане значение целевой функции                 zо      =      0                                                          (-5*0                                                 + 

+ 2*0 = 0). Отметим, что в системе (15) столбец коэффициентов при переменной z тоже 0

 

0

единичный (0 - она входит только в ограничение (4) с коэффициентом

Похожие материалы

Информация о работе