Материал: УП - Методы оптимальных решений

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

Доказано, что оптимальное решение задачи линейного программи­рования связано с угловыми точками многогранника решений, поэтому возникает мысль о следующем пути решения задачи линейного програм­мирования с любым числом переменных. Найти каким-нибудь способом все угловые точки многогранника планов (а их = , если каждый план определяется системой m-линейно независимых векторов, содержащихся в данной системе из n векторов Ā₁, Ā₂ ,..., Ā_n) и сравнить в них значения целевой функции. Но найти оптимальный план, перебирая все опорные планы задачи трудно, поэтому необходимо иметь схему, по­зволяющую переходить к не худшему опорному плану и иметь признак того, что лучших крайних точек, чем данная крайняя точка нет. В этом и состоит идея наиболее широко применяемого в настоящее время сим­плексного метода (метода последовательного улучшения плана).

Итак, симплексный метод предполагает: умение находить начальный опорный план, наличие признака оптимальности (неоптимальности) опорного плана, умение переходить к нехудшему опорному плану.

3.1. Построение начального опорного плана

1. Пусть задача линейного программирования представлена целевой функцией Z=c₁х₁ +с₂х₂ +...+с_nх_n = с_jх_j и системой ограничений, заданной в каноническом виде

Говорят, что ограничение задачи линейного программирования имеет предпочтительный вид, если в_i  0 и левая часть этого ограничения содержит переменную с коэффициентом 1, а в остальные ограничения – равенства она входит с коэффициентом равным 0.

Пример 7.

Первое и второе ограничения имеют предпочтительный вид, а третье – нет.

Если каждое ограничение – равенство задачи линейного программи­рования имеет предпочтительный вид, то и система ограничений пред­ставлена в предпочтительном виде. В этом случае легко найти ее опорное решение: все свободные переменные приравниваются к нулю, тогда ба­зисные переменные равны свободным членам.

Пример 8.

а) предпочтительными, т. е. базисными переменными являются х₂, х₃, х₄, а свободными – х₁ и х₅ х₁ = 0, х₅ = 0, а х₂ = 10, х₃ = 0, х₄ = 2. Тогда начальный опорный план =(0; 10; 80; 32; 0) – угловая точка (согласно теореме 1).

б) пусть система ограничений имеет вид в_i; в_i  0 (i = ) в задаче линейного программирования на max (задача об использовании сырья). Сведем задачу к каноническому виду, для этого добавим к левым частям неравенств дополнительные переменные х_{n + i}  0 (i = ), тогда получим систему равенств в_i; в_i  0 (i = ), которая будет иметь предпочтительный вид и, следовательно, начальный опорный план будет = (0,...0, в₁, в₂,…, в_m) (так как в этой системе все дополнительные переменные будут базисными, а в целевую функцию дополнительные переменные входят с коэффициентом равным 0), то Z = c₁x₁ + c₂x₂ + … c_nx_n + 0x_n+1 + …0x_n+m.

в) в задачах линейного программирования на min (задача о составлении ра­циона) система ограничений имеет вид в_i; в_i  0, (i = ). Если мы сведем эту задачу к каноническому виду, то надо из каждого неравенства (из левой части) вычесть дополнительные переменные х_n+i  0 (i = ). Получим систему в_i; в_i  0, (i = ), однако теперь система ограничений не имеет предпочтительного вида, так как дополнительные переменные х_{n + i} входят в левую часть с коэффициентами (– 1). В этом случае вводится так называемый искусственный базис: к левым частям ограничений равенств, не имеющих предпочтительного вида, добавляют искусственные переменные _i.

В целевую функцию переменные _i вводят с коэффициентом М в случае решения задачи на min и с коэффициентом (– M) для задачи на max, где М – большое положительное число. Полученная задача называ­ется М-задачей, которая соответствует исходной. Она всегда имеет пред­почтительный вид.

Пусть исходная задача линейного программирования имеет вид:

max(min) Z = ,

причем ни одно из ограничений не имеет предпочтительной переменной. Тогда М-задача запишется так:

max (min) = – (+) ,

в_i ,(i = ),

х_j  0, (j = ), _i  0 , (i = ).

Эта система ограничений имеет предпочтительный вид, ее начальный опорный план = (0,...0, в₁, в₂, …, в_m). Если некоторые из уравнений исходной системы ограничений имеют предпочтительный вид, то в них не следует вводить искусственные переменные. Итак, если в оптимальном плане = (х₁, x₂, .., x_n, ₁, ₂, .., _m) М-задачи все искусственные переменные _I = 0 (i = ), то план = (х₁, x₂, .., х_n) является оптимальным планом исходной задачи. Можно сказать, что если в результате применения симплексного метода к М-задаче получен оптимальный план, в котором все искусственные переменные _I = 0, то его первые n-компоненты дают оптимальный план исходной задачи. Если же в оптимальном плане М-задачи хотя бы одна из _i  0, то исходная задача не имеет допустимых планов, т. е. ее условия не совместны.

3.2. Симплексные таблицы. Признак оптимальности опорного плана

Итак, любую задачу линейного программирования можно предста­вить в предпочтительном виде: max(min) Z = ,

x_i + , B_i  0, (i = ),

х_j  0, (j = ).

Рассмотрим эту задачу для n = 4, m = 2 (и распространим ее для общего случая): Z = c₁x₁ + c₂x₂ + c₃x₃ + c₄x₄.

Выразим базисные переменные (БП) х₁, х₂ через свободные х₃ и х₄

x₁ = ,

x₂ = и подставим их в целевую функцию

Введем обозначения в общем виде:

,

где = (с₁; с₂; …; с_m) – вектор коэффициентов целевой функции при базисных переменных, = (B₁; B₂; ..; B_m) – вектор свободных членов; _{= – вектор коэффициентов при переменных хj}.

С учетом этих равенств целевая функция примет вид:

max(min)Z= где ; .

В общем случае задачу записывают в таблицу, которая называется симплексной (табл. 17).

Таблица 17

Последнюю строку называют индексной строкой, число – значение целевой функции для начального опорного плана , т. е. Δ_O = Z( ) = , числа – называются оценками свободных переменных.