программном обеспечении для решения задач линейного программирования на компьютере. Для задач небольшой размерности он может использоваться и вручную.
Симплексный метод состоит из трех основных элементов:
1)определения какого-либо первоначального допустимого базисного решения задачи;
2)правила перехода к лучшему решению;
3)проверки оптимальности допустимого решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
3.3. Вычислительная схема симплексного метода
Рассмотрение алгоритма симплексного метода начнем с анализа следующего примера [44].
Решить симплексным методом задачу:
F = 2xi+при ограни-
чениях:
В качестве основных переменных на первом шаге симплекс-метода следует выбрать (если зто возможно) такие m переменных, каждая из которых входит только в одно из т уравнений системы ограничений.
Xi +3X2 <18; 2xi +Х2 <16; Х2 <5 ; 3xj<21; xi>0;
(3.1)
Х2>0.
Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. Учитьшая, что все неравенства имеют знак «<», дополнительные переменные входят со знаком плюс. Исходная система ограничений после указанных преобразований примет следующий вид:
Xi +3x2 +Хз =18 2xj +Х2 +Х4 =16 Х2 + Х5 = 5 ЗХ1+Х6 =21
(3.2)
Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (небазисные).
Легко видеть, что определитель Хз, Х4, Хз, Хб имеет следующий вид:
при дополнительных переменных
1000 0100 0010 0001
и, следовательно, отличен от нуля. Исходя из этого переменные Х3, Х4, Х5, х можно взять в качестве основных на первом шаге решения
задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель и проверять равно ли его значение нулю. Можно воспользоваться следующим правилом.
В качестве основных переменных на первом шаге следует выбрать (если это возможно) такие т переменных, каждая из которых входит только в одно из т уравнений системы офаничений. При этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. В рассматриваемой си-туащш дополнительные переменные удовлетворяют этому правилу.
Шаг 1. Основные переменные Хз,Х4,Х5,Хб. Неосновные переменные х,, Х2.
Выразим основные переменные через неосновные:
Хз = 18 - х, - 3x2 Х4 =16-2х, -Х2 Х5 = 5 - Х2 Хб =21-3xi.
(3.3)
Положим неосновные переменные равными нулю, то есть X, = О, Х2 = О, получим базисное решение Xj = (0; 0; 18; 16; 5; 21), которое является допустимым. Учитывая, что целевая функция, выраженная через неосновные переменные, имеет вид
F = 2xi +3x2,
легко понять, что ее значение при х, = О, Х2 = О равно нулю и может быть увеличено за счет увеличения любой из неосновных переменных XpXj.
Это можно сделать, если перейти к такому новому допустимому базисному решению, в котором эта переменная будет основной, т.е. будет принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многогранника, где значение целевой функции лучше (по крайней мере, не хуже). В данном примере, учитьшая.
что в целевой функции коэффициенты при Xi и при 2 положительны, в основные переменные можно переводить и х, и х Для определенности в основные переменные переведем ту переменную, коэффициент которой в целевой функции больше. В данном случае такой переменной является х.
При решении задачи определения минимума целевой функции можно использовать один из следующих путей:
1.Если необходимо отыскать минимум функции F, то решается задача максимизации функции - F и зто решение принимается за решение исходной задачи.
2. На каждом шаге симплекс-метода уменьшать целевую функцию за счет той неосновной переменной, которая входит в выражение линейной функции с отрицательным коэффициентом.
Поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными и, следовательно, необходимо выполнение следующих неравенств (при этом xj = О как неосновная переменная)
Хз =18-3x2 >О Х4 =16-Х2 >0 Х5 =5-Х2 >0 х,=21
Х2 <18/3 Х2<16 Х2 <5
Каждое уравнение системы (3.3), кроме последнего, определяет оценочное отношение - границу роста переменной Х2, сохраняющую неотрицательность соответствующей переменной.
Эта граница определяется абсолютной величиной отношения числа, стоящего в правой части неравенства (3.1), к коэффициенту, стоящему при Х2 в соответствующем неравенстве. Уравнение х = 21 не офаничивает рост переменной, так как данная переменная Х2 в него не входит. В этом случае условимся обозначать фаницу символом оо. Такой же знак будем использовать, когда свободный член и коэффрщиент при переменной в уравнении имеют одинаковые знаки, так как в этом случае нет офаничений на рост переменной.
На рост переменной не накладывается офаничений и в том случае, когда правая часть соответствующего неравенства равна нулю, а перево-