Симплексный метод решения задачи линейного программирования

Пусть имеется ЗЛП, записанная в стандартной форме:

max , (1)

(2)

Обозначим через ивекторы-столбцы:

, и через- вектор-строку.

Тогда условия (1) и (2) можно записать в виде

max ,или max ,

Прежде чем приступить к обоснованию симплексного метода, множество всех векторов , удовлетворяющих условию , обозначим через и введем несколько определений:

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

Определение 2. Допустимая точка называется базисной или опорной (опорным планом), если она соответствует крайней точке многогранника решений;

Определение 3. Допустимая точка называется вырожденной, если менее чем значенийотличны от нуля (- число ограничений в задаче);

Определение 4. Если X – крайняя точка многогранника К, то не более её координатотличны от нуля, и векторы, коэффициентыпри которых отличны от нуля, линейно независимы.

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

- невырожденный опорный план задачи.

Согласно определению 4, векторы линейно независимы и образуют базис-мерного пространства. Функция целив точкепринимает значение

и равенство объединяется в равенство (3)

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

(4)

Так как , то получим.

Таким образом, если выбрать точку с координатами

то она будет удовлетворять условию и, если при этом все координаты точкибудут неотрицательны, т.е.(5) , тобудет допустимой точкой задачи. Условие (5) выполняется, если выбрать, (6)

где берётся min только положительных отношенийи. В случае, когда все, величинуможно выбрать как угодно большой. Это свидетельствует о неограниченности многогранника решений. Пусть выбрано, удовлетворяющее условию (6); тогда имеем в предположении, что:. Координаты второй точки будут:

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

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

Точке соответствует значение функции цели, равное

Преобразовав это выражение для , получим, где. Очевидно, если.

Решение задачи 1 симплексным методом

max Стандартная формаmax

Ба- зис	сz	bi							θ	Замечания
Результи- рующая строка		zопт
Результи- рующая строка		zопт
Результи- рующая строка		zопт

Презентация решения задачи 1 симплексным методом