Методы построения начального опорного плана

Алгоритм построения начального опорного плана

Метод последовательного улучшения плана, который применяется для решения ЗЛП, предполагает знание некоторого исходного опорного плана. Однако, далеко не всегда такой начальный опорный план может быть указан без каких-либо вычислений. Это возможно лишь в случае, когда среди столбцов матрицы условий найдётся достаточное количество таких столбцов, из которых составится единичная матрица и эта матрица будет являться базисом искомого начального плана.

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

Итак, начальный опорный план задачи может быть найден с помощью следующей вспомогательной ЗЛП (L - задачи):

	(11.1)
	(11.2)
	(11.3)

Так как матрица условий ЗЛП (11.1)-(11.3) уже содержит единичную подматрицу которая может быть взята в качестве базиса опорного плана, то начальным опорным планом этой задачи будет являться вектор

,

у которого небазисные компоненты а базисные .

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

Пусть - оптимальный опорный план задачи, у которого все искусственные компоненты равны нулю. Тогда вектор является опорным планом исходной задачи. Действительно, все дополнительные переменные . Значит, компоненты вектора удовлетворяют ограничениям исходной задачи, т.е. вектор является некоторым планом исходной задачи. По построению план является также опорным.

Алгоритм искусственного базиса

Далеко не всегда имеет смысл разделять решение задачи линейного программирования на два этапа – вычисление начального опорного плана и определение оптимального плана. Вместо этого решается расширенная задача (М-задача). Она имеет другие опорные планы (один из них всегда легко указать), но те же решения (оптимальные планы), что и исходная задача.

Расширенная М-задача применительно к исходной задаче записывается следующим образом:

;	(10.4)
;	(10.5)
.	(10.6)

Здесь - достаточно большое число.

Начальный опорный план задачи (10.4) – (10.6) может быть назначен непосредственно, так как в матрице условий этой задачи уже сформирована единичная подматрица, которая и составит его базис . Поэтому вектор с компонентами , и будет являться начальным опорным планом задачи (10.4) – (10.6). Переменные называются искусственными переменными.

Таким образом, исходная задача линейного программирования с неизвестным заранее начальным опорным планом сводится к М-задаче, начальный опорный план которой может быть указан непосредственно. В процессе решения этой расширенной задачи можно либо вычислить оптимальный план исходной задачи, либо убедиться в её неразрешимости, если оказывается неразрешимой М-задача.