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

На этом плане значение целевой функции z^о = 0 (-5*0 +
+ 2*0 = 0). Отметим, что в системе (15) столбец коэффициентов при переменной z тоже единичный ( - она входит только в ограничение (4) с коэфициентом 1). Она тоже приравнивается к свободному члену – 0.

Является ли план Х^о оптимальным? Чтобы ответить на этот вопрос, попытаемся увеличить значение целевой функции z. Переменная z входит в ограничение (4). Если в ограничении (4) увеличивать z, то остальные слагаемые (5х₁ - 2х₃) необходимо уменьшить. Это можно сделать либо за счет уменьшения х₁ (при этой переменной стоит положительный коэффициент 5), либо увеличения х₃ (при этой переменной стоит отрицательный коэффициент -2). Однако уменьшить переменную х₁ нельзя, так как она небазисная и равна нулю (а отрицательные значения переменные задачи принимать не могут). Поэтому следует увеличить х₃. Эту переменную увеличить можно, при этом z возрастет. Следовательно, оптимальный план еще не найден.

Итак, в следующем опорном плане появится новая ненулевая переменная - х₃. Но так как базисных переменных должно быть в этой задаче не более трех, какая-то другая переменная при этом из базиса выйдет, т.е. уменьшится до нуля.

До какого значения можно увеличивать переменную х₃, и какую переменную следует вывести из базиса? Чтобы ответить на этот вопрос, следует проанализировать остальные ограничения задачи.

В ограничение (1) входит базисная переменная х₅. Если уменьшить ее до нуля, то, учитывая, что небазисные переменные х₁ = х₂ = 0, получим 2х₃ =
= 2 Û х₃ = 2/2 = 1. Следовательно, ограничение (1) позволяет увеличить х₃ до 1 (за счет уменьшения х₅).

Аналогично ограничение (2) позволяет увеличить х₃ до 5 (за счет уменьшения х₆).

В ограничение (3) переменная х₃ вообще не входит, следовательно, оно позволяет увеличивать значение этой переменной до бесконечности.

Таким образом, самым жестким ограничением является первое, и мы увеличим х₃ только до 1 (если попытаться увеличить эту переменную до большего значения, то придется уменьшить переменную х₅ до отрицательных значений, иначе ограничение (1) не будет выполняться).

Следовательно, в в новом опорном плане переменная х₃ станет базисной, а х₅ из базиса выйдет. Преобразуем систему методом Гаусса таким образом, чтобы перейти к новому опорному плану. В новой системе столбец коэффициентов при х₃ станет единичным, причем единица должна стоять именно в первом ограничении, а в остальных – нули (тогда при ненулевых компонентах опорного плана снова будут линейно независимые столбцы коэффициентов - единичные).

Столбец коэффициентов при х₃ будем называть разрешающим (ведущим, ключевым). Так же будем называть и первое ограничение, которое определило выбор переменной, выходящей из базиса. Коэффициент в этом ограничении в разрешающем столбце (он равен 2) будем называть разрешающим элементом.

Чтобы получить на месте разрешающего элемента единицу, надо обе части первого ограничения разделить на этот элемент, т.е. на 2. После этого ограничение примет вид (1`).

В ограничение (2) переменная х₃ входит с коэффициентом 1. На месте этого коэффициента необходимо получить ноль. Для этого вычтем из ограничения (2) ограничение (1`), в которое х<sub>3</sub> входит теперь именно с коэффициентом 1. Результат обозначим (2`).

Ограничение (3) можно оставить без изменений, так как коэффициент при х₃ в нем и так нулевой. В новой системе обозначим его (3`).

В ограничение (4) переменная х₃ входит с коэффициентом -2. Умножим обе части ограничения (1`) на -2. Теперь переменная х<sub>3</sub> входит в него не с коэффициентом 1, а с коэффициентом -2. Вычтем из уравнения (4) полученное уравнение, при этом коэффициент при х<sub>3</sub> станет нулевым. Результат обозначим (4`).

Преобразованная система примет вид:

1`) -2,5х₁ – 0,5х₂ + х₃        + 0,5х₅                  = 1

2`) 1,5х₁ + 0,5х₂         + х₄ - 0,5х₅ + х₆      = 4

3`) -3х₁                       + 5х₄                   + х₇   = 7

4`) z         – х₂                        + х₅              = 2

х_1-7 ³ 0

Этой системе можно поставить в соответствие новый опорный план, приравняв базисные переменные х₃, х₆ и х₇ к свободным членам, а остальные – к нулю: Х⁽¹⁾ = (0; 0; 1; 0; 0; 4; 7).