дет с планом х. При этом, естественно, значения целевой функции не улучшатся, т.е.
Zcx, = Лс,х, ,
В этой ситуации можно продолжить вычисления с вектором х\ надеясь, что в ходе очередной итерации возможно увеличить значение целевой функции, но в этом случае возникает возможность «зацикливания», т.е. перебора одного и того же набора планов х, х\..., х, и на очередной итерации происходит возврат к плану х.
Чтобы избежать проблемы зацикливания, рассмотрим следующую процедуру. Введем понятие лексикографической упорядоченности в пространстве R"\ Пусть а = (aQ aj а„) е R"\
Будем говорить, что вектор а лексикографически больше нулевого вектора О е ]\(а у 0), если аФОя первая ненулевая координата вектора а положительна, т.е. а > О, где = min у 9о.
Если а = {а а а.то будем говорить, что вектор а лексикографически больше а (а >- а), если а - а >- 0. Иными словами а у
а, если а а и а> а, где q = min j aj . Отметим два важных свойства отношения « >-»:
1)для любых двух векторов а, аеВ" имеет место одна из трех возможностей: а = а; а у а; а у а;
2)отношение « >-» транзитивно, т.е. если а у а и а у а", то а > а".
Далее для того, чтобы сделать невозможной ситуацию зацикливания, надо после выбора вектора а который вводится в базис, более тщательно выбирать тот вектор, который будет выведен из базиса.
С этой целью усилим требования на рассматриваемые в симплекс-методе опорные планы (базисные решения).
Будем говорить, что опорный план х строго допустим, если все строки а,, / е а (кроме строки ао) симплекс-таблицы, соответствующей плану х лексикографически больше нуля: а, > 0,1 е ст. Из этого определения следует, что если базисное решение не вырождено, то оно строго допустимо в каждом векторе а,, /еа, первая координата а/о = х/ положительна.
Правило L. Если вектор ct решено ввести в базис (т.е. А < 0), то следует рассмотреть А:-й столбец ct симплекс-таблицы и все строки aj, для которых а;Р>0. Индекс S выбирается так, чтобы
-а < -а,, S, / G а sk> О, o.,k> О
и вектор выводится из базиса.
Правило L жестко определяет выбор индекса S, указывающего, какой вектор следует выводить из базиса. Иными словами, среди векторов а/ / aik имеется ровно один минимальный в смысле отношения « >-».
Действительно, все векторы а,; / в <т линейно независимы, так как ранг матрицы U равен рангу матрицы А, т.е. числу строк т.
Если предположить, что имеется два лексикографически упорядоченных вектора / ask и а, / а,:, то это означает, что / ask - ct, / atk, что противоречит линейной независимости векторов и а/
Теорема 3.1. Если действовать по Правилу L, то новый опорный план строго допустим (т.е. а- > О, iea и «о о).
Доказательство, Так как ask>0,(Xs >- О то = а/ ask >- 0. Если индекс / таков, что aik< О, то очевидно Os a/jt/ ask О и У а; > 0. Если же aik> О, то согласно правилу L а, / a;jfe Os / аь откуда I aik >- О, т.е. cci > 0. При этом ccq = ао- Akas/ask> olq, так как Ак/ask< О, то а, >- 0. Теорема доказана.
Теорема 3.1 утверждает, что если начать вычисления со строго допустимого опорного плана, то на каждой итерации мы будем получать вновь строго допустимый опорный план и при этом исключается возможность зацикливания.
Действительно, пусть в процессе итеративного применения симплекс-метода возникает последовательность строго допустимых планов хх\...,х, ... Тогда по теоремеЗ.1 а\ -< а\ -< -< ао ... Поскольку отношение «>» транзитивно, то ао oto, а это означает, что ixvi ни при каком q зацикливание невозможно.
3.5. Нахождение начального допустимого базисного решения
В рассмотренных численных примерах решения задач линейного программирования симплексным методом использовалась итерацион-
ная процедура перехода от первоначально допустимого базисного решения к следующему и так далее до достижения оптимального решения. При этом получение первого допустимого решения задачи не всегда является задачей тривиальной. Рассмотрим один из возможных алгоритмов нахождения допустимого базисного решения [6]. Пусть необходимо решить симплексным методом задачу минимизации линейной целевой функции вида
F = x\ + 2x2 min
при ограничениях
Xl-Х2 <-l;xi-Х2 >-3;xi <3;xi >0; Х2>0.
Для решения этой задачи вводятся дополнительные неотрицательные переменные хз Х4 Х5 с соответствующими знаками:
X, -Х2 +Х3 =-1 Xj - Х2 - Х4 = -3
X, +Х5 =3.
в соответствии с правилами, сформулированными при рассмотрении предьщущих примеров на шаге 1, в качестве основных возьмем дополнительные переменные.
Шаг 1. Основные переменные х, х, х Неосновные переменные х, х
Выражаем основные переменные через неосновные:
Хз =-l-Xi +Х2
Х4 = 3 + Xl - Х2
X5=3-Xi.
Начальный опорный план задачи линейного программирования может бьпь определен путем решения вспомогательной задачи линейного программирования, начальный опорный план которой легко определяется.
Тогда первое базисное решение =
= (0; 0; -1; 3; 3) является недопустимым.
В последней системе выберем то уравнение, которое содержит отрицательный свободный член, т.е. первое. Если окажется, что таких уравнений несколько, то выбираем произвольное. Поскольку переменная х
принимает отрицательное значение при первом базисном решении, то ее необходимо увеличить. Это можно сделать за счет увеличения любой из неосновных переменных, входящих в первое уравнение с положительным коэффициентом, в данном случае 72