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, то исходная задача не имеет допустимых планов, т. е. ее условия не совместны.