Из всех неотрицательных решений системы (4.4) найти такое, которое максимизирует линейную функцию (4.3).

Дана линейная функция

(4.3)

и задана система неравенств (ограничений)

, (4.4)

причем .

Замечание.Подчеркнем что исключению подлежат лишь свободные переменные. Несвободные же переменные (которые, как указано выше, можно считать неотрицательными не исключают. Таким образом, если, как обычно, , то после п. Л4.1 приступают сразу к п. Л4.3.

 

Л4.3. Нахождение опорного решения

 

Если в таблице (4.2) все элементы столбца свободных членов неотрицательны (), то точка таблицы (с координатами ) является опорным решением, так как для нее , и, следовательно, все , и система (3.2) удовлетворяется.

Если же в таблице (4.2) хотя бы один свободный член отрицателен (например, - й, где ), то в точке таблицы и ,следовательно, она не является решением систем (4.4) и (3.2).

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

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

2) среди коэффициентов этой строки находим первый попавшийся отрицательный ( если такового не оказалось, то система ограничений ЛП-задачи противоречва). Пусть, например, , т.е. s-й столбец - разрешающий;

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

.

Тогда -ю строку берем в качестве разрешающей, так что - разрешающий элемент.

Примечание. Если часть свободных членов равна нулю, то говорят что имеет место вырождение. При этом МНО . Коэффициент следует брать в качестве разрешающего лишь при , в противном случае ищем новое МНО, не учитывая -ю строку.

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

Действительно, после МЖИ

Т.е. всегда при .

Если разрешающим оказался , то после шага МЖИ новый свободный член станет положительным.

Если же разрешающий элемент не попал в r-ю строку, то новый останется еще отрицательным, но уменьшится по модулю. В этом случае продолжаем работать с r-й строкой (делать МЖИ, выбирая разрешающий элемент по изложенному правилу), и либо станет неотрицательным, либо установим несовместность системы ограничений.

Повторяем п.п. 1-3, и после конечного (но заранее неизвестного) количества шагов МЖИ либо установим несовместность системы ограничений, либо получим таблицу с неотрицательным столбцом свободных членов. Точка этой таблицы и будет соответствовать опорному решению (при вырождении не исключена возможность так называемого зацикливания(См. Л7)).

Лекция 5. Симплекс-метод решения ОЗЛП (продолжение)

 

Л5.1. Обоснование правила выбора разрешающего элемента при поиске опорного решения

 

Пусть все свободные члены таблицы (4.2) отличны от нуля (нет вырождения).

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

Действительно,

,

в то время как для точек многогранника W обязательно .

Проинтерпретируем правило выбора в двумерном пространстве (см. Рис. 5.1), т.е. для последней таблицы базисными переменными являются и .

 

 

 

Рис. 5.1.

 

Так как , то двигаться к опорному решению следует в направлении к отделяющей прямой , например, вдоль . Обозначим через точку на оси с координатами

.

При движении к W модуль уклонения от отделяющей плоскости должен уменьшаться:

,

т.е.

.

Так как , то последнее неравенство означает, что

,

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

Если в r-й строке нет отрицательных коэффициентов, то движение к отделяющей плоскости невозможно ни по одной из осей и это является признаком несовместности (противоречивости) системы ограничений, т.е. многогранник W пустой. В этом случае , и неотрицательность несовместима с требованием неотрицательности .

Двигаться по оси следует до встречи с отделяющей плоскостью (не обязательно с ).

Каждый шаг МЖИ с разрешающим элементом, выбранным из s-го столбца, как раз и приводит к переносу точки таблицы в одну из точек пересечения плоскостей системы ограничений в направлении (на рисунке таких точек четыре).

Алгоритм симплекс-метода предлагает двигаться из точки таблицы по оси лишь до первой встречи с новой плоскостью (в нашем случае это плоскость ). Такой выбор исключает возможность «перепрыгивания» через W, обеспечивает монотонное но не обязательно оптимальное (по количеству МЖИ) приближения к W.

При движении из P0 в направлении можно встретить плоскости

,

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

Если МНО получилось при (что желательно), то в результате шага МЖИ перейдем к точке, которую отделяет от W меньшее, чем предыдущую, число плоскостей (количество отрицательных свободных членов в таблице уменьшится).

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

Если имеет место вырождение (часть свободных членов равна нулю), то через точку таблицы проходит больше чем плоскостей. Тогда МНО=0, и в результате шага МЖИ с разрешающим элементом точка таблицы останется на прежнем месте (т.к. ), но базисная плоскость заменится плоскостью , в результате чего появляются новые направления движения к W (о борьбе с возможным при этом зацикливанием см. Л7). Таким образом, после конечного количества шагов мы либо выйдем из вырожденной вершины, либо обнаружим противоречивость системы ограничений.

5.2. Поиск оптимального решения (решение задачи максимизации)

 

Пусть рассматривается задача максимизации линейной формы

при ограничениях

,

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

  ... ...
... ...
... . . . . . ...
... ...
... . . . . . ...
... ...
... ...

,

так что .

В зависимости от знаков коэффициентов Z-строки возможны два случая.

1. Все коэффициенты Z-строки неотрицательны.

Если , то задача линейного программирования решена, причем и достигается в точке . Действительно, в этой точке имеем , т.е. удовлетворяются ограничения (3.2), и так как в любой другой точке многогранника W все неотрицательны, то , т.е. - максимальное значение .

2. Среди коэффициентов Z-строки есть отрицательные.

Пусть . В этом случае нельзя утверждать, что значение функции в точке P0 с координатами является максимальным. Действительно, если в направлении от P0 взять точку Ps с координатами (), принадлежащую W (т.е. ), то в этой точке .

Чтобы осуществить переход от точки P0 к соседней вершине многогранника W с большим (не меньшим) значением , необходимо произвести шаг МЖИ с разрешающим элементом, выбранным по следующему правилу.

1) Находим столбец (первый попавшийся) с отрицательным коэффициентом Z-строки (если таковых не окажется, то задача уже решена). Пусть, например, т.е. s-й столбец - разрешающий;

2) для выбора разрешающей строки находим МНО, используя процедуру выполнения п. 3 правила выбора разрешающего элемента при поиске опорного решения (при поиске оптимального решения, в отличие от поиска опорного, МНО может не существовать, если в s-м столбце не оказалось положительных элементов — это означает неограниченность сверху функции цели). Пусть МНО достигается при , т.е.

.

Тогда -ю строку берем в качестве разрешающей, так что - разрешающий элемент.

Примечание. Если МНО , то коэффициент можно брать в качестве разрешающего лишь при , в противном случае ищем новое МНО, не учитывая -ю строку.

 

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

После шага МЖИ с разрешающим элементом коэффициент станет положительным (при этом возможно появление новых отрицательных коэффициентов в Z-строке).

Если все новые коэффициенты Z-строки неотрицательны то задача решена.

 

Л5.3. Обоснование правила выбора разрешающего элемента

 

Пусть среди коэффициентов Z-строки есть отрицательные и, следовательно, нет уверенности в том, что точка P0 с координатами дает максимум функции . Переход к соседней вершине означает движение из P0 по ребру многогранника вдоль некоторой оси , выбранной так, чтобы в точке с координатами () значение было больше, чем в P0. Т.е. . Отсюда и .

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

Пусть . Ясно, что по выбранному ребру можно двигаться лишь до соседней вершины многогранника ( чтобы не сойти с W !), т.е. до встречи с некоторой плоскостью , где . В точке встречи с этой плоскостью, если , получим , следовательно , и так как , то . Первой, очевидно, встретится плоскость для которой .

В случае вырождения, т.е. когда среди свободных членов встречаются равные нулю, искомая «соседняя» вершина может совпасть с исходной P0 ( движения не будет). Можно избежать таких «пустых» МЖИ, выбирая среди столбцов с отрицательными элементами Z-строки в качестве разрешающего тот столбец (если таковой существует), у которого против всех нулевых свободных членов нет положительных коэффициентов.

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

Лекция 6. Симплекс-метод решения ОЗЛП (продолжение)

 

Л6.1. Монотонность и конечность симплекс-метода

 

Чтобы убедиться в монотонности алгоритма симплекс-метода, достаточно показать, что значение функции Z (определяемое последним элементом Z-строки) не убывает при переходе от одного опорного решения к другому в процессе поиска оптимального решения.

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

.

Таким образом, если , то , т.е. имеет место строгая монотонность рассмотренного шага. Если же , то и имеет место вырождение (о борьбе с возможным при этом зацикливанием см. Л7).

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