4.5. Основные понятия ЛП. Свойства задач ЛП (стр. 4 )

Следующая итерация начинается с проверок на оптимальность и разрешимость задачи, выбора направляющего элемента и заканчивается заполнением симплекс-таблицы 2.

Таблица 2	0	7	5	0	0	0	0	q
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A3	8/3	0	0	1	-3	0	4/3	2
2	5	A2	5/3	0	1	0	1	0	-2/3	--
3	0	A5	7	0	0	0	-3	1	2	7/2
4	7	A1	17/3	1	0	0	0	0	1/3	17
5	Δj	48	0	0	0	5	0	-1
6	zj	48	7	5	0	5	0	-1

Так как оптимальное решение не достигнуто, проводим 3-ю итерацию, результаты которой представлены в табл. 3.

В этой таблице нет отрицательных оценок, что свидетельствует о достижении оптимального решения. Максимальная прибыль составляет L*=50 при значениях переменных х*1 =5, х*2 =3, х*3 =х*4 =0, х*5 =3, х*6 =2, что полностью совпадает с результатами графического решения в разд. 4.6.

Таблица 3	0	7	5	0	0	0	0
i	Csi	Баз.	A0	A1	A2	A3	A4	A5	A6
1	0	A6	2	0	0	3/4	-9/4	0	1
2	5	A2	3	0	1	1/2	-1/2	0	0
3	0	A5	3	0	0	-3/2	3/2	1	0
4	7	A1	5	1	0	-1/4	3/4	0	0
5	Δj	50	0	0	3/4	11/4	0	0
6	zj	50	7	5	3/4	11/4	0	0

Пример 4.3. Рассмотрим задачу с разными видами ограничений и покажем только отличие от предыдущего примера.

Исходная модель L= 4x1 - x2→max, 1) 3x1+2x2 £ 10, 2) 2x1+x2³ 8, 3) x1 - 3x2 =12, 4) x1³0, 5) x2³0.

Каноническая модель L= 4x1 - x2→max, 3x1+2x2+x3 = 10, 2x1+x2 - x4 = 8, x1 - 3x2 = 12, "xj³0.

Для построения начального базисного решения по 4-му варианту введем искусственные переменные x5 и x6. Тогда модель примет вид

L= 4x1 - x2→max,

3x1+2x2+x3 = 10,

2x1+x2 - x4+x5 = 8,

x1 - 3x2+x6 = 12,

"xj³0.

Из нее получаем искусственное (недопустимое) базисное решение: x3 =10, x5 = 8, x6 = 12 (остальные переменные равны нулю). Соответственно базис состоит из одноименных векторов условий.

Далее можно выбрать один из способов решения:

1.  решение в один этап;

2.  решение в два этапа.

В первом случае критерий модифицируется введением искусственных переменных с большим весом: L’= 4x1 - x2 - M(x5+x6). Вместо символа большого числа M можно взять конкретное значение, например положить M= 100, что много больше С1 = 4. Дальше решение проводится согласно описанному алгоритму.

При использовании второго варианта на первом этапе решается задача минимизации искусственного критерия: Lи= x5 + x6→min. Если оптимальное значение этого критерия окажется отличным от нуля, исходная задача неразрешима из-за противоречивости условий. Нулевое значение будет свидетельствовать о достижении допустимого базисного решения, которое принимается за начальное для второго этапа. На нем решается задача по исходному критерию L. При этом в последней таблице первого этапа относительные оценки по критерию Lи заменяются оценками по критерию L. Они вычисляются так же, как в начальной таблице.

4.9.8. Учет двусторонних ограничений

В общем случае на переменные могут накладываться двусторонние ограничения aj£ xj£bj. Каждое такое ограничение порождает 2 равенства в канонической модели и, следовательно, увеличивает размер симплекс-таблицы на 2 строки. Если сместить начало отсчета на aj, ограничение примет вид 0£ xj£ dj, где dj=bj - aj, и таблица будет увеличиваться только на 1 строку. Однако, если такие ограничения накладываются на многие переменные, увеличение размеров симплекс-таблицы будет значительным.

Идея метода с двусторонними ограничениями состоит в учете ограничения сверху аналогично условию xj³ 0. Как было показано в разд. 4.9.2, выполнение этого условия обеспечивается выбором направляющей строки, т. е. значения вводимой переменной, равного q0. Чтобы переменные в новом базисном решении помимо неотрицательности были не больше dj, усложним выбор значения вводимой переменной. Предельное значение q по условию неотрицательности, вычисляемое по формуле (4.9), обозначим , а предельное значение по ограничению сверху ­– . Из формулы (4.11) следует, что верхнего значения могут достигать только переменные с отрицательными коэффициентами air. Приравнивая эти переменные значениям dj, получаем формулу для вычисления :

(4.24)

Новое базисное решение будет определяться по формуле (4.13), в которой q0 берется из соотношения

q0=min(). (4.25)

Соответственно и направляющая строка выбирается по q0. В симплекс-таблице вместо одного столбца для q удобнее иметь два: для q’ и q’’. Кроме того, добавляется одна строка (сверху), в которой записываются значения небазисных переменных: выводимая из базисного решения переменная xk равна нулю, если в (4.25) <, и равна dk в противном случае.

Изменяется также признак оптимальности базисного решения. Условие Δj³0 остается в силе только для нулевых небазисных переменных. К нему добавляется условие для небазисных переменных на верхнем уровне: Δj£0. Поэтому в случае неоптимальности текущего решения направляющий столбец выбирается по max| Δj| из отрицательных для xk=0 и положительных для xk=dk. Симплекс-преобразование (пересчет таблицы) не изменяется.

4.10. Модифицированный алгоритм

Этот алгоритм отличается от рассмотренного в разд. 4.9.6 тем, что основан на обратной матрице базиса. Для простоты расссмотрим случай с односторонними ограничениями на переменные. Тогда небазисные переменные равны нулю, а система условий задачи принимает вид

AbXb=B, (4.26)

где Ab – базисная матрица mxm, Xb – вектор базисных переменных. Так как определитель базисной матрицы не равен нулю, существует обратная матрица . Из (4.26) следует, что базисные переменные можно вычислять по формуле

(4.27)

Теперь покажем, что относительные оценки также можно определять по обратной матрице. Для этого выполним ряд преобразований:

(4.28)

Вектор найдем из разложения вектора условий Aj по базису

(4.29)

Подставляя (4.29) в (4.28), получаем

Произведение не зависит от индекса j, поэтому окончательно будем иметь

, (4.30)

где

(4.31)

Таким образом, для решения задачи модифицированным симплекс-методом достаточно вести не всю таблицу, а только обратную матрицу. При единичном начальном базисе обратную матрицу вычислять не надо – она также единичная. Имея обратную матрицу текущего решения, вычисляем сначала вектор по формуле (4.31), а затем оценки небазисных переменных по формуле (4.30). Если признак оптимальности не выполняется, находим минимальную оценку Коэффицинты разложения air вектора Аr по текущему базису находятся по формуле (4.29):

где Ar – вектор условий вводимой переменной xr, который берется из канонической модели. Столбец ar добавляем к обратной матрице в качестве направляющего. Далее действуем, как в стандартном методе, то есть для положительных air вычисляем q, находим направляющую строку и направляющий элемент. Затем получаем новую обратную матрицу путем симплекс-преобразования теущей обратной матрицы. После выполнения признака оптимальности решение находится по формуле (4.27).

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

Новую обратную матрицу можно находить не только симплекс преобразованием старой, но и по формуле

,

где Ek – почти единичная матрица (только k-й столбец отличается от единичного). Если эту формулу применять на всех итерациях, то для l-й обратной матрицы получим

.

Такое представление обратной матрицы называют мультипликативным. По сравнению с обычным симплекс-преобразованием оно уменьшает объем вычислений на каждой итерации и тем сильнее, чем меньше плотность матрицы условий.