Симплексный метод
Общая идея симплекс-метода. Геометрическая иллюстрация
Симплекс–метод (метод последовательного улучшения плана) был предложен американцем Геогрем Данцигом в 1951 г.
Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум.
Пусть ЗЛП записана в каноническом виде:
Из теоремы 4 следует, что оптимальный план задачи (52)-(54), если он существует, совпадает по крайней мере с одним из опорных решений системы (53).
Первый этап: поиск начального опорного плана.
Второй этап: среди опорных планов отыскивается оптимальный.
С геометрической точки зрения перебор опорных планов х 0, х 1, х 2, … можно толковать как последовательный переход по рёбрам из одной вершины многогранника планов в соседнюю, в которой значение целевой функции не меньше, чем в предыдущей вершине (рис. 13).
Рисунок 13
Табличная запись условий задачи
В таблицу впишем систему ограничительных уравнений и целевую функцию в виде выражений, разрешенных относительно начального базиса Б 0={ х 1; …; xm } (табл. 1).
Таблица 1
Левый столбец занимают базисные переменные (БП) и целевая функция, а верхнюю строку – свободные переменные (СП).
Нижнюю строку, в которую вписаны коэффициенты целевой функции f, называют f-строкой или строкой целевой функции.
За столбцом базисных переменных следует столбец свободных членов.
Признак оптимальности опорного плана
В симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то опорный план является оптимальным.
Переход от одного опорного плана к другому,
Более близкому к оптимальному.
Симплексное преобразование
Признак: если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент (не считая свободного члена), которому соответствует столбец с хотя бы одним положительным элементом, то можно, преобразовав базис, перейти к другому опорному плану с большим значением целевой функции.
Переменная, подлежащая включению в базис определяется отрицательным элементом f -строки.
Если в f -строке несколько отрицательных элементов, в базис вводят переменную хm + j, соответствующую отрицательному элементу с наибольшей абсолютной величиной.
Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим.
Симплексное отношение:
для определения переменной, исключаемой из базиса, составляют отношение свободных членов к положительным элементам разрешающего столбца и находят среди них наименьшее, которое определяет строку (разрешающую), содержащую исключаемую переменную.
Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует положительность базисных компонент в новом опорном плане.
Равенства, являющиеся результатом симплексного преобразования предыдущих равенств, запишем в форме симплекс-таблицы (табл. 2)
Таблица 2
Правила расчета переменных при переходе к новому опорному плану, более близкому к оптимальному.
Предполагается, что разрешающий элемент уже выбран, и при табличной записи задачи разрешающий элемент оказывается на пересечении разрешающих столбца и строки (см. табл. 1):
1) разрешающий элемент заменяется обратной величиной;
2) остальные элементы разрешающей строки делятся на разрешающий элемент;
3) остальные элементы делятся на разрешающий элемент и меняют свои знаки;
4) прочие элементы вычисляются по правилу прямоугольника.
Элементы, входящие в эту формулу, расположены в вершинах воображаемого «прямоугольника»:
Диагональ прямоугольника, на которой расположены разрешающий bks преобразуемый bij элементы, назовём главной, а другую диагональ – побочной.
Преобразованный элемент b/ij равен разности произведений элементов главной и побочной диагоналей, деленной на разрешающий элемент.
Если в разрешающей строке некоторый элемент bkj = 0, то b/ij = bij, то элементы столбца, в котором расположен нулевой элемент разрешающей строки, остаются при симплексном преобразовании без изменения.
Аналогично: если в разрешающем столбце есть нулевой элемент (bis = 0), то соответствующая ему строка остаётся на данном шаге преобразований неизменной.
Признак неограниченности
целевой функции на множестве планов
Если в f-строке симплекс-таблицы, содержащей некоторый опорный план, есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то целевая функция неограниченна на множестве планов, т.е. f→∞.
Признак бесконечности множества оптимальных планов
Если в f-строке симплекс-таблицы, содержащей оптимальный план, есть хотя бы один нулевой элемент (не считая свободного члена), то ЗЛП имеет бесконечное множество оптимальных планов.
