3. Нахождение решения задачи линейного программирования

Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).

Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду.

Для применения симплекс-метода с естественным базисом ЗЛП должна содержать единичную подматрицу размером mm – в этом случае очевиден начальный опорный план.

Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные записать в таблицу:

Базис	Сб	Р0	с1	с2	...	сm	cm+1	...	cn
			Р1	Р2	...	Рm	Рm+1	...	Рn
Р1	с1	b1	1	0	...	0	a1m+1	...	a1n
Р2	с2	b2	0	1	...	0	a2m+1	...	a2n
...	...	...	...	...		...	...	...
Рm	сm	bm	0	0	...	1	amm+1	...	amn
		F0	0	0		0	Δm+1		Δn

В первом столбце таблицы "Базис" записывают базисные векторы данного опорного плана. Во втором столбце - коэффициенты целевой функции (с₁,с_2,…,с_m) при базисных переменных (напомним, что в базис входят только векторы, образующую единичную подматрицу). В третьем столбцеР₀- правая часть ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы второго столбца таблицы со столбцомР₀, и суммируя эти произведения, мы получаем значение целевой функции (F₀=с₁*b₁+с₂*b₂+…+с_m*b_m).

Первая строка симплексной таблицы содержит коэффициенты целевой функции нашей задачи и остается неизменной на протяжении всего решения (с₁,с_2,…,с_m).

В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи. При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи составляют единичную подматрицу. Последнюю оценочную строку рассчитывают по формуле .

После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы последней (оценочной) строки. Возможны три варианта:

1. Все оценки , значит на основании признака оптимальности получен оптимальный план.

2. для некоторогоj, и все соответствующие этому индексу величины, значит целевая функция не ограничена сверху на множестве планов.

3. для некоторых индексовj, и для каждого такогоjпо крайней мере одно из чисел, значит можно перейти к новому опорному плану, при котором значение целевой функции увеличится.

Переход от одного опорного плана к другому осуществляется исключением из исходного базиса какого-нибудь из векторов и введением в него нового вектора. В качестве вводимого в базис вектора берётся один из векторов, для которых . Пусть это будет векторР_k.

Для определения вектора, подлежащего исключению из базиса находят . Тогда выполняется условие неотрицательности значений опорного плана. Пусть этот минимум достигается приi=r. Тогда из базиса исключают векторР_r, а числоназываютразрешающимэлементом.

Элементы новой симплекс-таблицы получают методом Жордана-Гаусса по формулам:

дляi = r;

.

Значения нового опорного плана рассчитываются по формулам:

дляi = r;

.

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

Если единичной подматрицы не обнаруживается, то либо придется перебирать все подсистемы mуравнений сmнеизвестными в надежде обнаружить неотрицательные решения, либо прибегнуть кметоду искусственного базиса.

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

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