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

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

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

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

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

	(11.1)
	(11.2)
	(11.3)

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

,

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

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

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

Дата добавления: 2014-01-06