|
4.2.1. Представление пространства решений стандартной задачи ЛП.
Модель:
максимизировать целевую функцию
при ограничениях
На – пространство решений. Каждую точку можно определить с помощью
Для идентификации нужной точки воспользуемся тем, что при ограничения модели эквивалентны равенствам, которые представляются соответствующими рёбрами пространства решений.
Анализируя , заметим, что
можно упорядочить, исходя из того, какое значение (нулевое или ненулевое) имеет данная переменная в экстремальной точке.
переменные
точка
нулевые
ненулевые
A
B
C
D
E
F
Из таблицы выделим закономерности:
1. Стандартная модель содержит четыре уравнения и шесть неизвестных, поэтому в каждой из экстремальных точек (6–4) переменные должны иметь нулевые значения.
2. Смежные экстремальные точки отличаются только одной переменной в каждой группе (нулевых и ненулевых переменных).
Если линейная модель стандартной формы содержит уравнений и неизвестных, то все допустимые экстремальные точки определяются как все однозначные неотрицательные решения системы уравнений, в которых m-n переменных равны нулю. Однозначные решения такой системы – базисные решения. Если они удовлетворяют требованию неотрицательности правых частей, то это – допустимое базисное решение. Переменные, равные нулю – небазисные, остальные – базисные. Каждую следующую экстремальную точку можно определить определить путём замены одной из текущих небазисных переменных текущей базисной переменной. В нашем примере при переходе из т. A в т. B необходимо увеличивать небазисную переменную от исходного нулевого значения до значения, соответствующего т. B. В т. B s2 обращается в нуль (становится небазисной). Т.о., происходит взаимообмен xE и s2 между небазисными и базисными переменными.
Включаемая переменная – небазисная в данный момент переменная, которая будет включена в множество базисных переменных на следующей итерации. Исключаемая переменная – базисная в данный момент переменная, которая на следующей итерации подлежит исключению из множества базисных переменных.
4.2.2 Вычислительные процедуры симплекс-метода
Симплекс-алгоритм:
Шаг 0: Используя линейную модель стандартной формы, определяют НДБР путём приравнивания к нулю n-m (небазисных) переменных.
Шаг 1: Из числа текущих небазисных переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если её нет -- текущее базисное решение оптимально, иначе переход к Шагу 2.
Шаг 2: Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна стать небазисной при введении в состав базиса новой переменной.
Шаг 3: Находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных. Переход к Шагу 1.
Если xE=xI=0, то
(соответствует точке A Ha ) – начальное допустимое решение.
Решение
-3
-2
2
6
2
8
-1
2
Если в задаче максимизации все небазисные переменные в -уравнении имеют неотрицательные коэффициенты, полученное пробное решение является оптимальным. Иначе в качестве новой базисной переменной следует выбрать ту, которая имеет наибольший по абсолютной величине отрицательный коэффициент. Применяя это условие к исходной таблице – переменная, включаемая в базис.
Процедура выбора подключаемой переменной предполагает проверку условия допустимости, требующего, чтобы в качестве исключаемой переменной выбиралась та (из текущего базиса), которая первой обращается в нуль при увеличении включаемой переменной вплоть до значения, соответствующего смежной экстремальной точке.
Отношение, идентифицирующее исключаемую переменную, можно определить из симплекс-таблице. Для этого в столбце вводимой переменной вычёркиваются отрицательные и нулевые элементы ограничений. Затем вычисляются отношения постоянных из правых частей ограничений к оставшимся элементам столбца. Исключаемая переменная – та, для которой это отношение минимально.
Решение
При использовании материалов активная ссылка на источник обязательна.