Симплексный метод.

Дата добавления: 2015-09-15; просмотров: 860; Нарушение авторских прав

Опорные планы ЗЛП.

Пусть имеется ЗЛП в канонической форме

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

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

Рассмотрим случай .

Многоугольник планов (решение системы ограничений) есть область на плоскости.

Вершины многоугольника планов обладают следующим свойством: любую точку многоугольника планов можно представить как линейную комбинацию его вершин.

Теорема.Каждому опорному плану ЗЛП соответствует вершина многоугольника планов, и наоборот.

Из теоремы и указанного свойства следует, что для исследования множества планов ЗЛП достаточно изучить лишь опорные планы.

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

Симплексный метод.

Одним из универсальных методов решения ЗЛП является симплексный метод (метод последовательного улучшения плана).

<== предыдущая лекция	\|	следующая лекция ==>
	\|	Алгоритм симплекс-метода.