Определение исходного базиса

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

1. Система записана неравенством вида (меньше или равно).

1. Ограничения задачи линейного программирования выражены линейными уравнениями

(7.60)

(7.61)

3. Ограничения задачи выражены неравенством вида (больше или равно). При ограничениях, записанных по первой форме, в уравнения вводятся свободные переменные (по одной свободной переменной в каждом соотношении), которые и включаются в исходный базис.

Если ограничения записаны в виде равенств (вторая форма огра­ничений), то возможны следующие приемы.

1. Если некоторая переменная входит только j-е уравнение (со­отношение), причем с коэффициентом, равным единице, то ее можно включить в исходный базис.

2. Ограничения, выраженные в виде равенств, записываются в сле­дующем виде:

(7.62)

где у_i - искусственная переменная, ввод которой делается с це­лью построения исходною базиса.

264

265

Чтобы окончательное решение имело смысл, каждая искусствен­ная переменная у_i на заключительной симплекс-итерации должна обращаться в нуль. Если на последней симплекс-итерации по край­ней мере одна из переменных у_i войдет в базис с положительным значением, то это означает несовместимость условий задачи, т. е. зада­ча не имеет допустимых решений.

3. Если ограничения задачи выражены неравенством , то в левую часть неравенств вводятся неотрицательные переменные с коэффи­циентом (-1). В полученных уравнениях дополнительные перемен­ные не могут быть приняты за базисные, так как они входят в уравнения с отрицательным коэффициентом. Для нахождения допустимого ис­ходного базиса в этом случае может быть задан конкретный набор переменных, предназначенный для формирования исходного базиса.

При некоторых итерациях вычислительные процедуры, предпи­санные правилами 1 и 2, в части, касающейся перехода от одного базиса к другому, могут оказаться неоднозначно определенными. На­пример, когда в результате оценки коэффициентов в строке 0 две или более двух переменных являются по правилу 1 в равной степени «пер­спективными» с точки зрения улучшения пробного решения, выбор одной из этих переменных осуществляется произвольным способом.

Е сли, согласно правилу 2, две или более двух переменных проме­жуточного базиса должны одновременно принять нулевые значения в силу включения в очередной базис новой переменной, из старого базиса подлежит исключению только одна из них. Другие переменные из упомянутых переменных остаются в базисе, принимая при этом нулевые значения. Базис, полученный в результате такой замены. называется вырожденным.

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