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

Решим следующую задачу:

max-5х₁+ 2х₃

-5х₁- х₂+ 2х₃2

-х₁+ х₃+ х₄ 5

-3х₁+ 5х₄7

х_1-40

Приведем ее к канонической форме.

max-5х₁+ 2х₃

-5х₁- х₂+ 2х₃+ х₅ = 2

-х₁+ х₃+ х₄ + х₆= 5

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

х_1-70

Теперь пример имеет вид задачи (14) с той разницей, что единичные вектора стоят не при первых трех, а при последних трех переменных - х₅, х₆и х₇; но изменять обозначения не имеет смысла.

Для удобства дальнейших рассуждений ограничения пронумеруем. При этом обозначим значение целевой функции (-5х₁+ 2х₃) =zи припишем к системе новое (четвертое) ограничение, после чего задача примет следующий вид:

maxz

1) -5х₁- х₂+ 2х₃+ х₅ = 2

2

(15)

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

4) z+ 5х₁- 2х₃ = 0

х_1-70

Решений такой системы бесконечно много.

При последних трех переменных (дополнительных) стоят единичные столбцы: А₅=, А₆=и А₇=. Поэтому удобно взять переменные х₅, х₆и х₇в качестве базисных. Приравняем их к свободным членам, а остальные – к нулю. Таким образом мы получим исходный опорный план - одно из решений этой системы - Х^о= = (0; 0; 0; 0; 2; 5; 7).

На этом плане значение целевой функции 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

(16)

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

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

х_1-70

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

Значение целевой функции увеличилось: z⁽¹⁾= 2. Это число является свободным членом ограничения (4`). В самом деле, так как небазисные переменные х<sub>2</sub>= х<sub>5</sub>=0, то из (4`)z= 2 (z- 0 + 0 = 2). Подстановкой плана в целевую функцию можно получить тот же результат (-5*0 + 2*1 = 2).

Из ограничения (4`) видно, что план Х⁽¹⁾тоже не является оптимальным. Значениеzможно еще увеличить за счет увеличения х₂.

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

В ограничение (1`) х₂входит с отрицательным коэффициентом -0,5. Следовательно, при увеличении х₂значение базисной переменной х₃, входящей в это ограничение, тоже будет увеличиваться (и это увеличение может происходить до бесконечности).

В ограничение (2`) входит базисная переменная х<sub>6</sub>. Если уменьшить ее до нуля, то, учитывая, что небазисные переменные х<sub>1</sub>= х<sub>4</sub>= х<sub>5</sub>= 0, получим 0,5х<sub>2</sub>= 4х<sub>2</sub>= 4/0,5 = 8. Следовательно, ограничение (2`) позволяет увеличить х₂до 8 (за счет уменьшения х₆).

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

Таким образом, самым жестким ограничением является второе, и мы увеличим х₂до 8.

Следовательно, в новом опорном плане переменная х₂станет базисной, а х₆из базиса выйдет. Снова преобразуем систему методом Гаусса таким образом, чтобы столбец коэффициентов при х₂стал единичным, причем единица должна стоять во втором ограничении (разрешающим столбцом будет столбец коэффициентов при х₂, а разрешающим ограничением – второе; разрешающий элемент равен 0,5).

Для этого обе части ограничения (2`) разделим на 0,5 (результат обозначим (2``)).

Из ограничения (1`) вычтем уравнение (2``), умноженное на (-0,5) (поскольку в ограничении (1`) в разрешающем столбце стоит именно (-0,5), а надо получить 0). Результат обозначим (1``).

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

Из ограничения (4`) вычтем уравнение (2``), умноженное на (-1) (поскольку в ограничении (4`) в разрешающем столбце стоит именно (-1), а надо получить 0). Результат обозначим (4``).

1``) -х₁+ х₃+ х₄+ х₆ = 5

2

(17)

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

4``) z+ 3х₁+ 2х₄ + 2х₆= 10

х_1-70

Этой системе можно поставить в соответствие новый опорный план Х⁽²⁾= (0; 8; 5; 0; 0; 0; 7). Значение целевой функции увеличилось:z⁽²⁾= 10.

Из ограничения (4`) видно, что значение целевой функции увеличить больше нельзя. Для этого пришлось бы уменьшить значения переменных х₁, х₄или х₆, а они и так равны нулю. Следовательно, Х⁽²⁾– оптимальный план, а 10 – оптимум задачи.