Для решения ЗЛП в аналитической форме применяют один из методов решения – симплекс метод (метод последовательного улучшения решения), который предполагает: 1) умение находить начальный опорный план; 2)наличие признака оптимальности плана; 3) умение переходить к не худшему опорному плану.
Для построение начального опорного плана исходные данные задачи должны быть представлены в канонической форме. Пусть ЗЛП представлена системой ограничений в каноническом виде:
, bi ≥ 0 (i = 1, m).
Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при не отрицательности правой части (вi ≥ 0) левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения – равенства – с коэффициентом, равным нулю.
Если каждое ограничение-равенство ЗЛП в каноническом виде содержит переменную, входящую в левую часть с коэффициентом, равным единице, а во все остальные с коэффициентом, равным нулю (при не отрицательности правых частей), то говорят, что система ограничений представлена в предпочтительном виде. В этом случае легко найти ее опорное решение (базисное с не отрицательными координатами): все свободные переменные нужно приравнять нулю, тогда базисные переменные (БП) будут равны свободным членам. Если полученный план будет иметь не более m отличных от нуля координат, то он будет опорным.
Приравнивание предпочтительных переменных к правым частям дает базисное решение, т.е. крайнюю точку многоугольника. Поэтому предпочтительные – базисные. Переменные, приравниваемые нулю, -свободные.
Пусть система ограничений имеет вид
, bi ≥ 0 (i = 1, m).
Приведем систему к каноническому виду
, bi ≥ 0 (i = 1, m),
которая имеет предпочтительный вид.
Следовательно, начальный опорный план примет вид: Х0 = (0;0;……0; b1;b2; …….bm). В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.
Пусть система ограничений имеет вид
, bi ≥ 0 (i = 1,… m).
Приведем систему к каноническому виду
, bi ≥ 0 (i = 1,.. m),
которая не имеет предпочтительный вид, так как дополнительные переменные xn+i входят в левую часть (при bi ≥ 0) с коэффициентом -1. Поэтому, базисный план Х0 = (0;0;...0; -b1; -b2;… -bm) является недопустимым. В практических задачах всегда имеются условия ограничений, которые в каноническом виде преобразуются из соотношений (х.х7), поэтому можно перейти к улучшенному решению.
Приведем последовательность шагов при решении задачи оптимизации: шаг первый: Приводим задачу к канонической форме
Z = c0 – ( ) → min;
-БП; - свободные переменные.
шаг второй: Находим начальный опорный план, приравняв , тогда Z = c0 , .
шаг третий: Проверяем, оптимально ли найденное решение. Если решение оптимально, то вычисления окончены, в противном случае необходим переход к следующему опорному плану.
Выполнение этого шаг требует анализа коэффициентов в функции цели при свободных переменных и проверки не отрицательности значений БП. Если значения БП удовлетворяют условию не отрицательности, то решение одно из допустимых (т.е. это одна из вершин ОДР). На оптимальность решения будут указывать отрицательные значения коэффициентов в целевой функции. В случае наличия положительных коэффициентов решение может быть улучшено.
шаг четвертый: Переход к новой вершине ОДР, в которой значение целевой функции меньше начального. Наибольшее из положительных коэффициентов будет указывать на ту свободную переменную , которая может изменяться от нуля до значений, не нарушающих условия ограничений.
Приравнивают БП к нулю для всех ограничений на данном шаге. Находят отношения для j – oй свободной переменной при условии равенства нулю других свободных переменных ( ). Наименьшее из положительных укажет ту БП, которая станет свободной, т.е. укажет уравнение ограничений, из которого определится новая БП, выраженная через новые свободные переменные. Все остальные БП и функцию цели нужно пересчитать через новые свободные переменные. Т. о. будет получен очередной опорный план. Далее повторение шагов 3 и 4. Выполнение шагов один – четыре предполагает последовательные преобразования условий ограничений и функции цели. Поэтому, в дальнейшем будем говорить о решениях, полученных методом симплекс – преобразований.
Все преобразования симплекс – метода можно выполнить в табличной форме. Табличная форма симплекс – метода предполагает представление исходной задачи в канонической форме (см. выше). Для внесения исходных данных в таблицу запишем условие задачи следующим образом:
Z = c0 – ( ) → min;
) -БП;
- свободные переменные.
Коэффициенты при свободных переменных в уравнениях БП и функции цели внесем в таблицу, причем разместим их в верхние части клеток со знаками, указанными в скобках соответствующих уравнений.
Таблица 5.1
БП
Свободный член
Свободные переменные
…
…
…
…
…
…
…
…
…
…
…
…
Столбец «свободные члены» определяет первое начальное решение при равенстве нулю свободных переменных:
Z1( )=c0 .
Далее выполняем шаги 3 и 4 симплекс - преобразований. Наибольший коэффициент при свободных переменных в функции цели определяет разрешающий столбец (пусть это будет хj). Находим наименьшее положительное отношение , которое определяет разрешающую строку. Элемент, стоящий на
пересечении разрешающего столбца и разрешающей строки, называют генеральным (обведем его кружком). Разрешающая строка показывает: какая базисная переменная поменяется со свободной переменной хi « xj .
Дляпересчетакоэффициентов базисных переменных и функции цели через новые свободные переменные выполним следующее:
1) находим l = 1/аij; аij - генеральный элемент;
2) все коэффициенты разрешающей строки умножим на l (кроме генерального), а коэффициенты разрешающего столбца - на "-l" изапишем в нижней части клеток;
3) выделим старые значения коэффициентов разрешающей строки (┘) и новые значения коэффициентов разрешающего столбца (l);
4) числа, вводимые в нижнюю часть клетки на пересечении строки l и столбца S находим перемножением старого значения коэффициентов разрешающей строки и нового значения коэффициентов разрешающего столбца.
После заполнения, всех клеток таблицы осуществляют ее преобразование в новую таблицу:
Таблица 5.2
Базисные переменные
Свободный член
Свободные переменные
…
…
…
…
…
…
…
…
…
…
…
…
Во все верхние отделения клеток разрешающей строки и разрешающего столбца заполняются значения из нижних отделений предыдущей таблицы; в остальные клетки помещают алгебраическую сумму значений данной клетки.
Анализируя полученную таблицу, видим, что решение «улучшено», т.е. Z1 > Z2 . Далее выполняем действия, аналогичные вышеописанным.
, bi ≥ 0 (i = 1, m). 
, bi ≥ 0 (i = 1, m).
, bi ≥ 0 (i = 1, m),
, bi ≥ 0 (i = 1,… m).
, bi ≥ 0 (i = 1,.. m),
) → min;
-БП; 
- свободные переменные.
, тогда Z = c0 , 
.
в целевой функции. В случае наличия положительных коэффициентов 
, которая может изменяться от нуля до значений, не нарушающих условия ограничений.
для j – oй свободной переменной при условии равенства нулю других свободных переменных ( 
). Наименьшее из положительных 
укажет ту БП, которая станет свободной, т.е. укажет уравнение ограничений, из которого определится новая БП, выраженная через новые свободные переменные. Все остальные БП и функцию цели нужно пересчитать через новые свободные переменные. Т. о. будет получен очередной опорный план. Далее повторение шагов 3 и 4. Выполнение шагов один – четыре предполагает последовательные преобразования условий ограничений и функции цели. Поэтому, в дальнейшем будем говорить о решениях, полученных методом симплекс – преобразований.
) → min;
) -БП;
- свободные переменные.
)=c0 
.
, которое определяет разрешающую строку. Элемент, стоящий на
