Графический метод решения ЗЛП

4. Перемещая гиперплоскость линейной формы (линию уровня) из начального положения (3') по направлению вектора С находим крайнее положение, определяющее опорную гиперплоскость. Поскольку полученная нами гиперплоскость пересекается с множеством М по ребру АВ, то наша задача имеет бесконечное множество решений. А именно, все точки отрезка АВ являются оптимальными планами задачи, на которых достигается максимальное значение линейной формы .

Метод последовательного улучшения плана

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

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

Переход от одного опорного плана к другому опорному плану

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

, (10.1)

где - матрица условий размером

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

. (10.2)

Так как вектора составляющие базис - линейно независимы, то существуют не все равные нулю, такие что

Разложим вектор по базису .

(10.3)

Умножим обе части последнего соотношения на некоторую величину , и результат вычтем из (10.2)

. (10.4)

Отсюда следует, что точка

удовлетворяет ограничениям типа равенств задачи (10.1). Чтобы эта точка являлась планом задачи необходимо выполнение условий неотрицательности её координат

(10.5)

При этом,

· если все , то (10.5) выполняется при любом

· если же существует , то (10.5) будет выполняться не при любом значении .

Решая неравенства относительно , получим

.

Ясно что, таких чисел может быть больше одного. Выберем наименьшее из них и обозначим его , т.е.

.

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

Пусть для определенности

Тогда первая координата обратиться в ноль

,

т.е. имеет ровно положительных координат.

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

Допустим противное, т.е., что вектора - линейно зависимы. Тогда существует

. (10.6)

С другой стороны, мы уже знаем, что

(10.7)

Подставим выражение (10.7) в предыдущее равенство (10.6)

(10.8)

Так как система - линейно независима равенство (10.8) возможно только в случае, когда все коэффициенты линейной комбинации равны нулю

Учитывая, что , то из последних соотношений получаем , , что противоречит предположению о линейной зависимости, а значит, - опорный план ЗЛП (10.1).

Базис этого опорного плана получился, очевидно, из базиса исходного опорного плана путем введения в него вектора и удаления вектора . Таким образом, мы перешли от одного опорного плана к другому опорному плану . Этот переход был выполнен с помощью процедуры однократного замещения, т.е. из старого базиса был выведен вектор-столбец и введен .

Рис 10.3.

Ребро, соединяющее соседние угловые точки и . определяется угловой точкой и вводимым в базис вектором . Если бы вместо ввели бы другой вектор, то получили бы другое ребро, а, следовательно, и другую угловую точку (рис 10.3).

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

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

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

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

Признак оптимальности опорного плана

Пусть дана задача:

(10.9)

(10.10)

(10.11)

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

, (10.12)

Умножим равенство слева на и получим

(10.13)

Условие (10.10) можно записать

,

т.е.

Умножая последнее равенство слева на получим

(10.14)

Разложим вектор по базису и полученное выражение умножим слева на

Перепишем (10.14) с учетом (10.13)

.

(10.15)

Подсчитаем значение линейной формы в точке :

или

,

где

(10.16)

- оценки векторов относительно базиса .

Теорема 10.1. (необходимое условие оптимальности опорного плана). Для того, чтобы опорный план ЗЛП был оптимальным необходимо, чтобы оценки всех векторов условий относительно базиса этого опорного плана были неотрицательны ( ).

Д о к а з а т е л ь с т в о. Пусть - оптимальный опорный план с базисом . Выберем вектор , тогда

,

т.е. . Оценка вектора относительно базиса

Таким образом, оценка базисного вектора относительно того же базиса равна нулю.

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

Вычислим значение линейной формы в точке :

С учетом того, что и

,

чего быть не может.

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

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

Первый способ состоит в вычислении коэффициентов разложения векторов по базису рассматриваемого опорного плана по формулам

и, затем, в вычислении оценок

Второй способ состоит в вычислении вектора-строки

и последующем вычислении оценок , .

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