Симплекс-метод решения задач линейного программирования
Симплексный метод – это аналитический метод решения ЗЛП, реализующий алгоритм графического метода аналитически, без построения чертежа.
Таким образом, суть симплексного метода состоит в направленном переборе допустимых решений, при котором значение целевой функции на каждом шаге лучше, чем на предыдущем. Процесс повторяется до тех пор, пока не будет получено оптимальное по значению целевой функции решение.
Симплекс метод может использоваться для решения ЗЛП с любым количеством неизвестных.
Техническая реализация симплексного метода связана с решением систем линейных уравнений, для чего используют метод Гаусса, разработаны табличные формы и правила преобразования симплексных таблиц.
Симплекс-метод с естественным базисом применяется, если ЗЛП задана в канонической форме записи, и матрица в КЗЛП содержит единичную подматрицу размером m´m . Для определённости положим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный план выбирается следующим образом:
Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому плану проводится с помощью преобразования Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и т.д.
Математический признак оптимальности состоит из следующих двух теорем:
1. Если для всех векторов A 1 , A 2 , … , A n
выполняется условие , где 
, то полученный опорный план является оптимальным. В сумме для определения Z j
участвуют m
слагаемых, то есть в ней участвуют не все коэффициенты целевой функции c j
, а лишь с номерами соответствующими номерам текущих базисных векторов A i
, количество которых равно m
.
2. Если для некоторого вектора, не входящего в базис, выполняется условие 
, то следует искать новый опорный план, для которого значение ЦФ больше, чем для текущего. При этом возможны два случая:
а) если все компоненты вектора A k , подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);
б) если имеется хотя бы одна положительная компонента у вектора A k , подлежащего ввода в базис, то можно получить новый опорный план.
На основании признака оптимальности в базис вводится вектор A k , давший минимальную отрицательную величину симплекс-разности:
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор A r , который даёт минимальное положительное оценочное отношение
Строка A r , в которой находился старый базисный вектор, называется направляющей, столбец A k и элемент a rk - направляющими.
Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:
а элементы любой другой i -й строки - по формулам:
Значения нового опорного плана рассчитываются по аналогичным формулам:
,
Процесс продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди разностей Δ j , j=1, 2, … , n оптимального плана нулевыми являются только разности, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что оптимальный план не единственный.
Пример. Решить ЗЛП по модели:
найти 
,
при ограничениях 
Эта ЗЛП сводится к каноническому виду путём введения дополнительных переменных x 3 и x 4 :
КЗЛП имеет необходимое количество (два) нулевых столбцов при x 3 и x 4 , то есть обладает очевидным начальным опорным планом (0,0,300,150).
Решение осуществляется симплекс-методом с естественным базисом с оформлением расчётов в симплекс-таблицах:
| Номер симплекс-таблицы | Базис | с j | с j | Q | ||||
| B | A 1 | A 2 | A 3 | A 4 | ||||
| ← A 3 | ||||||||
| A 4 | ||||||||
| Δ | - | -2 | -3 | - | ||||
| I | → A 2 | 1/3 | 1/3 | |||||
| ← A 4 | 2/3 | -1/3 | ||||||
| Δ | - | -1 | - | |||||
| II | A 2 | 1/2 | -1/2 | - | ||||
| → A 1 | -1/2 | 3/2 | - | |||||
| Δ | - | 1/2 | 3/2 | - |
Остановимся подробнее на заполнении симплекс-таблиц и, соответственно, получении решения КЗЛП.
В верхнюю строку общей таблицы внесены коэффициенты c j , j=1, 2, 3, 4 при переменных в ЦФ. В первые две строки нулевой симплекс-таблицы внесены вектор-столбцы B, A 1 , A 2 , A 3 , A 4 , соответствующие векторной форме записи КЗЛП. Поскольку исходным базисом является пара векторов A 3 , A 4 , они внесены в колонку под названием “Базис” нулевой симплекс-таблицы. При этом, A 3 внесён в первую строку, что определяется единицей, являющейся первым элементов этого вектора, а вектор A 4 - во вторую строку, у этого вектора единица находится во второй строке. В столбец под названием “ c i ” внесены коэффициенты целевой функции, соответствующие базисным векторам A 3 , A 4 , то есть c 3 , c 4 . Они оба равны нулю. Далее вычисляются значения разностей Δ для векторов B, A 1 , A 2 , A 3 , A 4 и заносятся в третью строку нулевой таблицы. Для вектора A 1 :
для вектора :
Аналогично , .
Для вектора B вычисление разности несколько упрощается, поскольку ему нет соответствующего коэффициента c j , j=1, 2, 3, 4 в ЦФ:
Не для всех векторов A 1 , A 2 , A 3 , A 4 полученные разности являются неотрицательными, поэтому выбранный нами опорный план не является оптимальным. Нам необходимо искать новый опорный план, а для этого нужно заменить один из входящих в базис векторов A 3 , A 4 .
Для определения вектора, который мы должны ввести, ищем вектор, для которого значение разности получилось минимальным. Таким является вектор, A 2 , ему соответствует минимальное значение разности: -3. То есть индекс k из формулы (8.4) равен 2. Для определения вектора, который мы должны будем вывести из базиса, вычисляем значения Q для каждой строки по формуле (8.5) и вносим их в последнюю колонку. В данном случае в каждой строке мы должны величину элемента вектора B разделить на величину элемента вектора A 2 . В первой строке получим 300/3=100, во второй: 150/1=150. Меньше получилось отношение в первой строке, ей соответствовал базисный вектор A 3 , следовательно, индекс r в формуле (8.5) равен 1, a rk =3 (выделен в таблице рамкой), а выводить из базиса мы будем вектор A 3 (обозначено в таблице стрелкой).
Поскольку среди элементов вектора A 2 , который должен быть введён в базис, имеются положительные, то можно получить новый опорный план и решение следует продолжить.
После этого заполняется вторая симплекс-таблица. Для перерасчёта элементов векторов B, A 1 , A 2 , A 3 , A 4 используются формулы (8.6)-(8.8). Они несколько отличаются для определения элементов направляющей строки (в нашем случае первая) и для определения элементов прочих строк. Распишем вычисления нескольких элементов:
Другие элементы первой симплекс-таблицы вычисляются аналогично тому, как мы это делали для нулевой таблицы. Поскольку не все разности в первой симплекс-таблице неотрицательны, возникает необходимость продолжить расчёты.
Как мы видим, в результате расчётов во второй симплекс-таблице с базисными векторами A 2 , A 1 все разности получились неотрицательные, что означает достижение оптимального плана (75; 75; 0; 0). Симплекс-разность для вектора В равна искомому максимальному значению ЦФ - 375.
Теорема (о конечности симплекс-алгоритма). Если существует оптимальное решение ЗЛП, то существует и базисное оптимальное решение. Последнее всегда может быть получено с помощью симплекс-метода, причём начинать можно с любого исходного базиса.
Симплексный метод. Алгоритм. Признак оптимальности опорного плана.
Из геометрической интерпретации ЗЛП видно, максимум или минимум функции достигается в угловой точке выпуклого многогранника – ОДР – системы ограничений. Поэтому в основу симплекс-метода положена идея рассмотрения и испытания на оптимальность только угловых точек – вершин многогранника, а не всего бесконечного множества его точек.
Рис. Геометрическая интерпретация идеи симплекс-метода
в случае двух (рис а) и трех (рис б) переменных.
Симплекс – это выпуклый многоугольник в n – мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на 2 полупространства).
Симплексный метод - это вычислительная процедура, основанная на принципе последовательного улучшения решения. При этом переходим от одной базисной точки к другой. Значение целевой функции всегда улучшается.
Базисное решение – это одно из допустимых решений, находящихся в ОДР.
Переменные, относительно которых разрешена система линейных уравнений, называются базисными . Тогда все остальные переменные называются свободными .
Доказано, что если оптимальное решение существует, то оно будет найдено за конечное число шагов, кроме случаев зацикливания.
Алгоритм симплексного метода:
1. Построить математическую модель задачи.
- Преобразовать полученную математическую модель в каноническую форму, у которой: правые части условий неотрицательны; условия являются равенствами (при необходимости ввести искусственные переменные).
- Построить симплекс таблицу и найти начальный опорный план решения задачи. Множество переменных, которые являются базисными , принимаются за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные переменные равны нулю.
- Проверка базисного решения на оптимальность осуществляется с помощью специальных оценок коэффициентов целевой функции (смотреть последнюю строку таблицы). Если задача решается на max, то все оценки должны быть неотрицательными, если на min, то все оценки должны быть неположительные.
- Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличит целевую функцию. При решении задач на max в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по max положительному значению оценки коэффициентов целевой функции. Столбец таблицы, который содержит эту оценку, называется генеральным столбцом. Если хотя бы один элемент столбца положительный, то отыскивается генеральная строка (в противном случае задача не имеет оптимального решения). Если в этом столбце есть нули, то нужно брать другой столбец. Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший, соответствующая строка называется генеральной. Она соответствует ресурсу, который ограничивает производство на данном шаге. Элемент симплекс таблицы, находящийся на пересечении генеральной строки и столбца, называется генеральный элемент. Все элементы генеральной строки, включая свободный член, делятся на генеральный элемент. В результате генеральный элемент становится равным 1. Далее необходимо чтобы все другие элементы генерального столбца стали равными 0. генеральный столбец должен стать единичным. Все строки кроме генеральной преобразуют следующим образом: полученные элементы новой строки умножим на соответствующие элементы генерального столбца, и полученное произведение вычитаем из элементов старой строки. Значение новых базисных переменных получим в соответствующих ячейках столбца свободных членов (правило прямоугольников).
- Полученное базисное решение проверяется на оптимальность (шаг №4). Если оно оптимально, то вычисления прекращаются, в противном случае находится новое базисное решение (шаг №5).
Признак оптимальности опорного плана
Если решаем задачу на max то все оценки должны быть неотрицательными.
Если решаем задачу на min то все оценки должны быть неположительными.
В случае, если опорный план не оптимален нужно перейти к более лучшему опорному плану. Для этого выбираем самую худшую оценку. Она будет соответствовать разрешающему столбцу. После этого надо найти разрешающую строку.
Θ (столбец симплекс-отношений) не рисуется для строчек с отрицательными и нулевыми значениями. Из всех θ выбираем наименьшее, так делается всегда неважно на min или на max исходная задача.
Разрешающая строка всегда показывает, какой элемент надо вывести из базиса, а разрешающий столбец – какой элемент надо ввести в базис.
Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).
Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден – (b 1 , b 2 ,…, b m ,0,…,0).
Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.
Математический признак оптимальности состоит из следующих двух теорем:
1. Если для всех векторов А 1 , А 2 ,…, А n выполняется условие
где ,
то полученный опорный план является оптимальным.
2. Если для некоторого вектора, не входящего в базис, выполняется условие
, то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:
- если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);
- если имеется хотя бы одна положительная компонента у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
На основании признака оптимальности в базис вводится вектор А к, давший минимальную отрицательную величину симплекс разности:
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор А r , который дает минимальное положительное оценочное отношение
Строка А r называется направляющей, столбец А к и элемент a r к – направляющими.
Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:
а элементы i-й строки – по формулам:
Значения нового опорного плана рассчитываются по формулам:
для i = r ;
Процесс решения продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди симплекс-разностей (оценок) оптимального плана нулевые только оценки, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему, то в общем случае это означает, что оптимальный план не единственный.
Примечание.
Для использования приведенной процедуры к минимизации линейной функции f (x 1 ,x 2 ,…, x n) следует искать максимум - f (x 1 ,x 2 ,…, x n), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же.
Пример.
Получить решение по модели:
Эта задача (модель) линейного программирования, приведем ее к каноническому виду путем введения дополнительных переменных x 3 и x4:
КЗЛП имеет необходимое число единичных столбцов, т.е. обладает очевидным начальным опорным планом (0,0,300,150). Решение осуществляется симплекс-методом с естественным базисом с оформлением расчетов в симплекс-таблицах:
Номер | В | 2 | 3 | 0 | 0 | |||
симплекс- | Базис | план | Q |
|||||
таблицы | ||||||||
А3 | 0 | 300 | 1 | 3 | 1 | 0 | 100 |
|
| 0 | А4 | 0 | 150 | 1 | 1 | 0 | 1 | 150 |
f(x) | 0 | -2 | -3 | 0 | 0 | |||
А2 | 3 | 100 | 1/3 | 1 | 1/3 | 0 | 300 |
|
| I | А4 | 0 | 50 | 2/3 | j. Оптимальные значения переменных равны: x1*=75, x2* =75 (основные переменные), x3* =0, x4* =0 (дополнительные переменные). Максимальное значение целевой функции равно 375.
Каноническая задача линейного программирования в векторной форме имеет вид:
Положительным координатам допустимых решений ставятся в соответствие векторы условий. Эти системы векторов зависимы, так как число входящих в них векторов больше размерности векторов.
Базисным решением системы называется частное , в котором неосновные переменные имеют нулевые значения. Любая система уравнений имеет конечное число базисных решений, равное , где - число неизвестных, - ранг системы векторов условий. Базисные , координаты которых удовлетворяют условию неотрицательности, являются опорными.
Опорным решением
задачи линейного программирования называется такое допустимое , для которого векторы условий, соответствующие положительным координатам 
, линейно независимы.
Число отличных от нуля координат опорного не может превосходить ранга Системы векторов условий (т. е. числа линейно независимых уравнений системы ограничений).
Если число отличных от нуля координат опорного решения равно , то такое решение называется Невырожденным , в противном случае, если число отличных от нуля координат опорного решения меньше , такое решение называется Вырожденным .
Базисом опорного решения называется базис системы векторов условий задачи, в состав которой входят векторы, соответствующие отличным от нуля координатам опорного решения.
Теорема . Любое опорное решение является угловой точкой области допустимых решений .
Теорема . Любая угловая точка области допустимых решений является опорным решением .
Пример.
Графический метод решения задачи линейной оптимизации рассмотрим на примере задачи производственного планирования при
= 2.
Предприятие изготавливает изделия двух видов А и В. Для производства изделий оно располагает сырьевыми ресурсами трех видов С, D и Е в объемах 600, 480 и 240 единиц соответственно. Нормы расхода ресурсов на единицу продукции каждого вида известны и представлены в табл. 14.1
Решение :
Прибыль от реализации изделия А составляет 40 млн. руб., а изделия В - 50 млн. руб. Требуется найти объемы производства изделий А и В, обеспечивающие максимальную прибыль.
Построим математическую модель задачи, для чего обозначим и - объемы производства изделий А и В соответственно.
Тогда прибыль предприятия от реализации изделий А и изделий В составит:
Ограничения по ресурсам будут иметь вид:
Естественно, объемы производства должны быть неотрицательными 
.
Решение сформулированной задачи найдем, используя геометрическую интерпретацию. Определим сначала многоугольник решений, для чего систему ограничений неравенств запишем в виде уравнений и пронумеруем их:
Каждое из записанных уравнений представляет собой прямую на плоскости, причем 4-я и 5-я прямые являются координатными осями.
Чтобы построить первую прямую, найдем точки ее пересечения с осями координат: при 
, а при 
. Далее нас интересует, по какую сторону от прямой будет находиться полуплоскость, соответствующая первому неравенству. Чтобы определить искомую полуплоскость, возьмем точку и, подставив ее координаты в неравенство, видим, что оно удовлетворяется. Так как точка лежит левее первой прямой, то и полуплоскость будет находиться левее прямой 
. На рис. 14.1 расположение полуплоскости относительно первой прямой отмечено стрелками.
Аналогично построены 2-я и 3-я прямые и найдены полуплоскости, соответствующие 2-му и 3-му неравенству. Точки, удовлетворяющие ограничениям 
, находятся в первом квадранте.
Множество точек, удовлетворяющих всем ограничениям одновременно, является ОДР системы ограничений. Такой областью на графике (рис. 14.1) является многоугольник .
Любая точка многоугольника решений удовлетворяет системе ограничений задачи и, следовательно, является ее решением. Это говорит о том, что эта задача линейной оптимизации имеет множество допустимых решений, т. е. многовариантна. Нам же необходимо найти решение, обеспечивающее максимальную прибыль.
Чтобы найти эту точку, приравняем функцию к нулю и построим соответствующую ей прямую. Вектор-градиент прямой функции 
имеет координаты 
.
 |
Рис. 14.1
Изобразим вектор на графике и построим прямую функции перпендикулярно вектору на рис. 14.1. Перемещая прямую функции параллельно самой себе в направлении вектора, видим, что последней точкой многоугольника решений, которую пересечет прямая функции, является угловая точка В. Следовательно, в точке В функция достигает максимального значения. Координаты точки В находим, решая систему уравнений, прямые которых пересекаются в данной точке.
Решив эту систему, получаем, что .
Следовательно, если предприятие изготовит изделия в найденных объемах, то получит максимальную прибыль, равную:
(млн. руб.).
Алгоритм решения задачи линейного программирования графическим методом таков:
1. Строится область допустимых решений;
2. Строится вектор нормали к линии уровня с точкой приложении в начале координат;
3. Перпендикулярно вектору нормали проводится одна из линий уровня, проходящая через начало координат;
4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будут находиться максимум или минимум функции.
В зависимости от вида области допустимых решений и целевой функции задача может иметь единственное решение, бесконечное множество решений или не иметь ни одного оптимального решения.
На рис. 14.3 показан случай, когда прямая функции параллельна отрезку АВ, принадлежащему ОДР. Максимум функции достигается в точке А и в точке В, а, следовательно, и в любой точке отрезка АВ, т. к. эти точки могут быть выражены в виде линейной комбинации угловых точек А и В.
|
Основные понятия симплексного метода решения задачи линейного программирования.
Среди универсальных методов решения линейного программирования наиболее распространен симплексный метод (или симплекс-метод), разработанный американским ученым Дж. Данцигом. Суть этого метода заключается в том, что вначале получают допустимый вариант, удовлетворяющий всем ограничениям, но необязательно оптимальный (так называемое начальное опорное решение); оптимальность достигается последовательным улучшением исходного варианта за определенное число этапов (итераций). Нахождение начального опорного решения и переход к следующему опорному решению проводятся на основе применения рассмотренного выше метода Жордана-Гаусса для системы линейных уравнений в канонической форме, в которой должна быть предварительно записана исходная задача линейного программирования; направление перехода от одного опорного решения к другому выбирается при этом на основе критерия оптимальности (целевой функции) исходной задачи.
Симплекс-метод основан на следующих свойствах задачи линейного программирования:
· Не существует локального экстремума, отличного от глобального. Другими словами, если экстремум есть, то он единственный.
· Множество всех планов задачи линейного программирования выпукло.
· Целевая функция ЗЛП достигает своего максимального (минимального) значения в угловой точке многогранника решений (в его вершине). Если целевая функция принимает свое оптимальное значение более чем в одной угловой точке, то она достигает того же значения в любой точке, являющейся выпуклой линейной комбинацией этих точек.
· Каждой угловой точке многогранника решений отвечает опорный план ЗЛП.
Рассмотрим две разновидности симплексного метода: симплекс-метод с естественным базисом и симплекс-метод с искусственным базисом (или М-метод).
Симплекс-метод с естественным базисом
Для применения этого метода задача линейного программирования должна быть сформулирована в канонической форме, причем матрица системы уравнений должна содержать единичную подматрицу размерностью . В этом случае очевиден начальный опорный план (неотрицательное базисное решение).
Для определенности предположим, что первые Т
Векторов матрицы системы составляют единичную матрицу. Тогда очевиден первоначальный опорный план: 
.
Проверка на оптимальность опорного плана проходит с помощью критерия оптимальности, переход к другому опорному плану — с помощью преобразований Жордана-Гаусса и с использованием критерия оптимальности.
Полученный опорный план снова проверяется на оптимальность и т. д. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получаются оптимальный опорный план и соответствующее ему оптимальное значение целевой функции.
Признак оптимальности заключается в следующих двух теоремах.
Теорема 1. Если для некоторого вектора, не входящего в базис, выполняется условие:
, где 
,
То можно получить новый опорный план, для которого значение целевой функции будет больше исходного; при этом могут быть два случая:
1. Если все координаты вектора, подлежащего вводу в базис, неположительны, то задача линейного программирования не имеет решения;
2. Если имеется хотя бы одна положительная координата у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
Теорема 2.
Если для всех векторов выполняется условие 
, то полученный план является оптимальным.
На основании признака оптимальности в базис вводится вектор , давший минимальную отрицательную величину симплекс-разности: .
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Г, Который дает минимальное положительное отношение:
; , .
Строка
Называется Направляющей
,
Столбец
и элемент
— Направляющими
(последний называют также Разрешающим
Элементом).
Элементы вводимой строки, соответствующей направляющей строке, в новой симплекс-таблице вычисляются по формулам:
А элементы любой другой -й Строки пересчитываются по формулам:
,,
Значения базисных переменных нового опорного плана (показатели графы «план») рассчитываются по формулам:
Для ; 
, для .
Если наименьшее значение достигается для нескольких базисных векторов, то чтобы исключить возможность зацикливания (повторения базиса), можно применить следующий способ.
Вычисляются частные, полученные от деления всех элементов строк, давших одинаковое минимальное значение на свои направляющие элементы. Полученные частные сопоставляются по столбцам слева направо, при этом учитываются и нулевые, и отрицательные значения. В процессе просмотра отбрасываются строки, в которых имеются большие отношения, и из базиса выводится вектор, соответствующий строке, в которой раньше обнаружится меньшее частное.
Для использования приведенной выше процедуры симплекс-метода к минимизации линейной формы следует искать максимум функции 
, затем полученный максимум взять с противоположным знаком. Это и будет искомый минимум исходной задачи линейного программирования.
Симплексный метод с искусственным базисом (М-метод)
Симплексный метод с искусственным базисом применяется в тех случаях, когда затруднительно найти первоначальный опорный план исходной задачи линейного программирования, записанной в канонической форме.
М -метод заключается в применении правил симплекс-метода к так называемой М-задаче . Она получается из исходной добавлением к левой части системы уравнений в канонической форме исходной задачи линейного программирования таких искусственных единичных векторов с соответствующими неотрицательными искусственными переменными, чтобы вновь полученная матрица содержала систему единичных линейно-независимых векторов. В линейную форму исходной задачи добавляется в случае её максимизации слагаемое, представляющее собой произведение числа (-М ) на сумму искусственных переменных, где М - достаточно большое положительное число.
В полученной задаче первоначальный опорный план очевиден. При применении к этой задаче симплекс-метода оценки теперь будут зависеть от числа М . Для сравнения оценок нужно помнить, что М - достаточно большое положительное число, поэтому из базиса будут выводиться в первую очередь искусственные переменные.
В процессе решения М- Задачи следует вычеркивать в симплекс-таблице искусственные векторы по мере их выхода из базиса. Если все искусственные векторы вышли из базиса, то получаем исходную задачу. Если оптимальное решение М- Задачи содержит искусственные векторы или М- Задача неразрешима, то исходная задача также неразрешима.
Путем преобразований число вводимых переменных, составляющих искусственный базис, может быть уменьшено до одной.
Табличный вид ЗЛП. Симплекс - таблицы.
СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП
3.1. Общая характеристика и основные этапы симплекс – метода
Основоположниками симплекс-метода являются советский математик Л.В. Канторович и американский математик Дж. Данциг.
Симплекс-методом можно решить любую ЗЛП или обнаружить ее неразрешимость. Многие специальные классы ЗЛП можно решить другими, более эффективными для этих классов методами. Однако преимущество симплекс-метода - его универсальность. Почти для всех ЭВМ разработаны стандартные программы для решения ЗЛП симплекс - методом.
Опишем общую идею симплекс-метода.
Считаем, что ЗЛП записана в каноническом виде и целевую функцию нужно минимизировать. Как мы уже знаем, оптимальный план следует искать среди опорных планов ЗЛП. Симплекс-метод не перебирает все опорные планы (что было бы часто невозможно из-за их огромного количества), а, начиная с некоторого исходного опорного плана, он последовательно переходит к другим опорным планам с уменьшением целевой функции. Симплекс-метод прекращает свою работу тогда, когда либо будет найден оптимальный опорный план, либо установлена неразрешимость задачи.
При решении ЗЛП симплекс-методом можно выделить следующие этапы:
1) приведение ЗЛП к каноническому виду;
2) приведение системы линейных уравнений к жордановой форме с неотрицательными правыми частями с одновременной проверкой на неразрешимость ЗЛП из-за противоречивости системы линейных ограничений;
3) исследование опорного плана на оптимальность;
4) исследование ЗЛП на неразрешимость из-за неограниченности снизу на ОДР целевой функции;
5) переход к новому, "лучшему" опорному плану.
Для сокращения и упорядочения записей при решении ЗЛП симплекс-методом используются так называемые симплекс-таблицы. Чтобы воспользоваться симплекс-таблицей, ЗЛП нужно привести к табличному виду. Делается это так.
Пусть ЗЛП записана в каноническом виде (2.3-2.5). Для приведения ЗЛП к табличному виду систему (2.4) следует сначала привести к жордановой форме с неотрицательными правыми частями. Предположим, что эта жорданова форма имеет вид (2.6). Выразим из (2.6) базисные переменные через свободные:
Подставив в целевую функцию (2.3) вместо базисных переменных их выражения через свободные переменные по формулам (3.1), исключим тем самым из целевой функции базисные переменные. Целевая функция примет вид:
В табличном виде целевая функция записывается так:
где 
.
Отметим следующие особенности табличного вида ЗЛП:
а) система линейных уравнений приведена к жордановой форме с неотрицательными правыми частями;
б) из целевой функции исключены базисные переменные и она записана в форме (3.3).
Перейдем теперь к описанию симплекс-таблицы. Пусть ЗЛП записана в табличном виде:
(3.4)
Тогда заполненная симплекс-таблица выглядит так.
Таблица 3.1.
| Базис | Переменные | Свободные члены | |||||||
| ... | x k | ... | |||||||
| ... | ... | ||||||||
| ... | ... | ||||||||
| . . . | . . | . . | ... | . . | . . | . . | ... | . . | . . . |
| ... | ... | ||||||||
| f | ... | .... |
Опорный план ЗПЛ: ..., называется опорным планом, соответствующим этой симплекс-таблице. Как видно из формулы (3.2), значение целевой функции при этом опорном плане равно γ 0 .
Рассмотрим пример. Привести к табличному виду следующую ЗЛП и заполнить симплекс-таблицу:
Вначале ЗЛП следует привести к каноническому виду. Для этого функцию f нужно заменить на - f:
Система уравнений должна быть записана в жордановой форме с неотрицательными правыми частями. Общий прием, с помощью которого это достигается, будет рассмотрен позднее (параграф 3.7). В нашем примере такая жорданова форма уже есть с базисными переменными и . Исключим базисные переменные из целевой функции - f. Для этого выразим их через свободные и подставим эти выражения в целевую функцию.
Табличный вид ЗЛП таков:
Заполним симплекс-таблицу (для сокращения записей первый столбец озаглавлен "Б", последний столбец - "Q").
Таблица 3.2.
| Б | Q | ||||
| -5 | |||||
| -7 | -2 | ||||
| -f | -4 | -20 |
Опорный план, соответствующий этой симплекс-таблице, имеет вид:
Значение функции - f при этом опорном плане равно - 20.
Пусть имеется заполненная симплекс-таблица. Сформулируем условие оптимальности опорного плана.
Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны , то опорный план, соответствующий этой таблице, оптимален.
Для простоты обоснуем справедливость этого утверждения на примере. Пусть заполненная симплекс-таблица имеет вид:
Таблица 3.3.
| Б | Q | |||||
| -1 | ||||||
| -1 | ||||||
| f | -5 | -3 | -1 |
Значение целевой функции при опорном плане, соответствующем симплекс-таблице, равно 6. Выпишем целевую функцию в табличном виде:
, откуда . Так как при любом допустимом решении ЗЛП переменные принимают только неотрицательные значения, то из последней записи целевой функции видно, что ее значение в любой точке ОДР не меньше 6. Следовательно, минимальное значение целевой функции на ОДР равно 6 и оно достигается при опорном плане, соответствующем симплекс-таблице, .
3.4. Условие неразрешимости ЗЛП из-за неограниченности снизу на ОДР целевой функции.
Если для ЗЛП заполнена симплекс-таблица, то ОДР задачи непуста, так опорный план, соответствующий симплекс-таблице, принадлежит ОДР. Однако ЗЛП может быть неразрешимой из-за неограниченности снизу на ОДР целевой функции.
Условие неразрешимости формулируется так.
Если симплекс-таблица содержит хотя бы один столбец, отличный от самого правого, у которого в нижней строке стоит положительное число, а во всех остальных строках столбца - неположительные числа, то ЗЛП неразрешима из-за неограниченности снизу на ОДР целевой функции.
Для обоснования снова воспользуемся примером.
Таблица 3.4.
| Б | Q | |||||
| -2 | ||||||
| -3 | -1 | |||||
| f | -1 |
Столбец в нижней строке содержит положительное число, а в остальных строках - неположительные числа. Докажем неразрешимость ЗЛП.
Выпишем жорданову форму, соответствующую симплекс-таблице, и перенесем члены, содержащие , в правую часть. Получим
Пусть а - произвольное положительное число. Очевидно, ЗЛП имеет следующее допустимое решение:. Вычислим значение целевой функции при этом допустимом решении. Из таблицы 3.4 имеем:
. При указанном допустимом решении f = 4 - 2а. Отсюда видим, что значение целевой функции может стать как угодно малым при достаточно большом значении а. Иначе говоря, целевая функция не ограничена снизу на ОДР. Следовательно, ЗЛП неразрешима.
3.5. Переход к новому опорному плану.
Предположим, что условия оптимальности и неразрешимости не выполняются. Тогда симплекс-метод переходит к новому опорному плану. Этот переход совершается за счет выведения из базиса одной из базисных переменных и введения в базис одной из свободных переменных. При этом должны выполняться следующие два условия:
1) новый базис должен быть по-прежнему допустимым, т.е. правые части соответствующей жордановой формы должны быть по-прежнему неотрицательными;
2) при новом опорном плане значение целевой функции не должно превышать ее значения при прежнем опорном плане.
Столбец симплекс-таблицы, в котором стоит переменная, вводимая в базис, называется генеральным столбцом . Строка, в которой стоит переменная, выводимая из базиса, называется генеральной строкой . Элемент, стоящий на пересечении генеральной строки и генерального столбца, называется генеральным элементом .
Правило выбора генерального элемента.
В качестве генерального столбца выбирается любой столбец симплекс-таблицы, отличный от самого правого, у которого в нижней строке стоит положительное число. Затем рассматриваются только те строки симплекс-таблицы, отличные от самой нижней, у которых на пересечении с генеральным столбцом стоят положительные числа. Для каждой из таких строк вычисляется отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, выбирается в качестве генеральной. Элемент, стоящий на пересечении генеральной строки и генерального столбца, и будет генеральным элементом.
Проиллюстрируем это правило на примере.
Таблица 3.5.
| Б | Q | |||||
| 2 | -1 | |||||
| -2 | ||||||
| F |
В качестве генерального столбца можно выбрать либо столбец , либо столбец . Выберем (чаще всего выбирают тот столбец, у которого внизу большее положительное число). Теперь приступим к выбору генеральной строки. Для этого рассмотрим две строки - и . Составляем отношения 4:2 и 8:3. Меньшее значение имеет отношение 4:2, поэтому первую строку выбираем в качестве генеральной. Следовательно, генеральный элемент равен 2 - он стоит на пересечении столбца и строки .
После выбора генерального элемента нужно перейти к новому опорному плану, при котором переменная становится базисной, а переменная х 1 - свободной. Коэффициент при в новой жордановой форме должен быть равен 1. Поэтому первая строка таблицы 3.5 делится на 2. Умножив затем полученную первую строку на (-3) и прибавив ко второй строке, исключим из второго уравнения. Аналогично, с помощью жордановой процедуры исключаем из третьего уравнения и из целевой функции (последнее требует табличный вид ЗЛП).
В результате получим следующую таблицу.
Таблица 3.6
| Б | Q | |||||
| f | -2 |
Обратим внимание, что в столбце Q в первых трех строках стоят неотрицательные числа, т.е. новый базис по-прежнему является допустимым. Это не случайный факт: так будет всегда при точном соблюдении правила выбора генеральной строки. Далее, значение целевой функции при новом опорном плане равно -2, при старом оно было равно 12. "Улучшение" опорного плана гарантирует правило выбора генерального столбца. Хотя эти факты мы строго не доказываем, следует иметь в виду, что они всегда имеют место.
Посмотрев на таблицу З.6 , мы видим, что не выполняются ни условие оптимальности опорного плана, ни условие неразрешимости ЗЛП. Значит, надо снова выбирать генеральный элемент и переходить к новой симплекс-таблице. Читатель сможет проделать это самостоятельно.
3.6. Табличный симплекс-алгоритм.
Пусть имеется заполненная симплекс-таблица. Подводя итоги изложенному, получим следующий алгоритм решения ЗЛП симплекс-методом.
1. Если в нижней строке симплекс-таблицы все числа, кроме, быть может, самого правого, неположительны, то опорный план, соответствующий симплекс-таблице, оптимален, и алгоритм останавливается. В противном случае - переход пункту 2.
2. Если симплекс-таблица содержит столбец, отличный от самого правого, у которого в нижней строке стоит положительное число, а во всех остальных строках - неположительные числа, то ЗЛП неразрешима из-за неограниченности снизу на ОДР целевой функции, и алгоритм останавливается. В противном случае - переход к пункту 3.
3. Выбираем любой столбец, отличный от самого правого, у которого в нижней строке стоит положительное число - назовем его генеральным. Затем рассматриваем строки симплекс-таблицы, отличные от самой нижней, у которых в генеральном столбце стоят положительные числа. Для каждой из таких строк вычисляем отношение свободного члена к элементу, стоящему в генеральном столбце. Строка, для которой это отношение минимально, является генеральной строкой. Элемент, стоящий на пересечении генерального столбца и генеральной строки, будет генеральным элементом. Переход к пункту 4.
4. Составляем новую симплекс-таблицу, в которой:
1) из базиса выведена переменная, стоящая в генеральной строке; в базис введена переменная, стоящая в генеральном столбце;
2) генеральная строка поделена на генеральный элемент;
3) с помощью жордановой процедуры все числа генерального столбца, за исключением 1, стоящей в генеральной строке, делаются равными нулю. Переход к пункту 1.
Пример I. Решить симплекс-методом
Задача записана в каноническом виде, нужно привести ее к табличному виду. Система уравнений записана в жордановой форме с неотрицательными правыми частями (базисные переменные и ). Необходимо привести к табличному виду целевую функцию. Для этого выразим базисные переменные через свободные
x 3 =10 - 2x 1 - x 2
x 4 = 8 - x 1 - 2x 2
и подставим в целевую функцию
Для получения табличного вида функцию запишем так:
Теперь имеем табличный вид ЗЛП:
Заполним первую симплекс-таблицу
Таблица 3.7
| Б | Q | ||||
| F |
В таблице 3.7 условия оптимальности и неразрешимости не выполняются. Выберем в качестве генерального столбец , у которого в нижней строке стоит положительное число. Затем, сравнивая отношения 10:3 и 8:1, выберем первую строку в качестве генеральной. В таблице генеральный элемент 2 .
Действуя в соответствии с пунктом 4 табличного симплекс-алгоритма, перейдем к таблице 3.8.
Таблица 3.8
| Б | Q | ||||
| F | -5 | -22 |
Условия оптимальности и неразрешимости не выполняются. Выбираем в таблице 3.8 генеральный элемент и переходим к следующей таблице
Таблица 3.9
| Б | Q | ||||
| F | -24 |
Таблица 3.9 удовлетворяет условию оптимальности.
Ответ: оптимальный план
Минимальное значение целевой функции f min = - 24.
Пример 2 . Решить симплекс-методом:
Прежде всего, ЗЛП нужно привести к каноническому виду
Теперь приводим ЗЛП к табличному виду. Видим, что система уравнений записана в жордановой форме с неотрицательными правыми частями (и z- базисные переменные). Однако в целевую функцию входит базисная переменная. Имеем:
Следовательно, табличный вид ЗЛП таков:
Заполняем симплекс-таблицу (таблица 3.10).
Таблица 3.10
| Б | z | Q | |||
| -1 | |||||
| z | -2 | ||||
| g | -1 |
После выбора генерального элемента переходим к таблице 3.11
