Симплексное преобразование

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

 

Общая идея симплекс-метода. Геометрическая иллюстрация

 

Симплекс–метод (метод последовательного улучшения плана) был предложен американцем Геогрем Данцигом в 1951 г.

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

 

Пусть ЗЛП записана в каноническом виде:

Из теоремы 4 следует, что оптимальный план задачи (52)-(54), если он существует, совпадает по крайней мере с одним из опорных решений системы (53).

Первый этап: поиск начального опорного плана.

Второй этап: среди опорных планов отыскивается оптимальный.

С геометрической точки зрения перебор опорных планов х ₀, х ₁, х ₂, … можно толковать как последовательный переход по рёбрам из одной вершины многогранника планов в соседнюю, в которой значение целевой функции не меньше, чем в предыдущей вершине (рис. 13).

Рисунок 13

Табличная запись условий задачи

 

В таблицу впишем систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относительно начального базиса Б ₀={ х ₁; …; x_m } (табл. 1).

 

Таблица 1

 

Левый столбец занимают базисные переменные (БП) и целевая функция, а верхнюю строку – свободные переменные (СП).

Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f-строкой или строкой целевой функции.

За столбцом базисных переменных следует столбец свободных членов.

 

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

 

В симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то опорный план является оптимальным.

 

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

Более близкому к оптимальному.

Симплексное преобразование

 

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

 

Переменная, подлежащая включению в базис определяется отрицательным элементом f -строки.

Если в f -строке несколько отрицательных элементов, в базис вводят переменную х_{m + j}, соответствующую отрицательному элементу с наибольшей абсолютной величиной.

Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим.

Симплексное отношение:

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

 

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

 

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

Таблица 2

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

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

1) разрешающий элемент заменяется обратной величиной;

2) остальные элементы разрешающей строки делятся на разрешающий элемент;

3) остальные элементы делятся на разрешающий элемент и меняют свои знаки;

4) прочие элементы вычисляются по правилу прямоугольника.

Элементы, входящие в эту формулу, расположены в вершинах воображаемого «прямоугольника»:

Диагональ прямоугольника, на которой расположены разрешающий b_ks преобразуемый b_ij элементы, назовём главной, а другую диагональ – побочной.

Преобразованный элемент b^/_ij равен разности произведений элементов главной и побочной диагоналей, деленной на разрешающий элемент.

 

Если в разрешающей строке некоторый элемент b_kj = 0, то b^/_ij = b_ij, то элементы столбца, в котором расположен нулевой элемент разрешающей строки, остаются при симплексном преобразовании без изменения.

Аналогично: если в разрешающем столбце есть нулевой элемент (b_is = 0), то соответствующая ему строка остаётся на данном шаге преобразований неизменной.

 

Признак неограниченности

целевой функции на множестве планов

 

Если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то целевая функция неограниченна на множестве планов, т.е. f→∞.

 

Признак бесконечности множества оптимальных планов

 

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