Следующее критическое значение t2 определяем из условия Хв = В, Ь(г) >0. Отсюда получаем следующее.
| ( 30-7/ | | |
| | | |
ХУ = | 30+/ | > | |
\X4j | -10 + 3/ | | |
i 2 ;
Это условие показывает, что В, остается допустимым базисом для 10/3 < t < 30/7.
При t = t2 = 30/7 новый базис можно получить с помощью модифицированного двойственного симплекс-метода, при этом исключаемой из базиса будет переменная х2.
Новый базис при t2 = 30/7.
Определив исключаемую переменную х2, находим вводимую переменную следующим образом. Поскольку
ХЯ = (х2, х3, х/ и СЯ (/) = (2, 5, 0),
Далее вычисляем
{(В[Р.)Д, }>=,.5.б = (строка в В;, ассоциированная с х2) (Р,, Р5, Р6) = = (1-я строка в В) (Plf Р5, Р6) =
-(o.0.i)(PlfP„ Р.)-
Поскольку все элементы неотрицательны, задача не имеет допустимых решений при £>30/7. Таким образом, параметрический анализ заканчивается в точке f = *2 = 30/7.
Оптимальные решения при различных значениях параметра t приведены в следующей таблице.
| xi хг | | |
0< f S 10/3 | 0 5-f | 30 + f | 160+ 3f |
10/3 S f<30/7 | 0 (30 - 7()/4 | 30+ f | 165 + (3/2)f |
t > 30/7 | Допустимых решений нет | | |
УПРАЖНЕНИЯ 7.6.2
1. Для задачи из примера 7.6.2 найдите первое критическое значение £, и определите векторы, составляющие матрицу В,, для следующих случаев.
a) Ь(*) = (40 + 2t, 60 - 3t, 30 + 6tf.
b) b(r) = (40 - t, 60 + 2t, 30 - 5t)T.
2. Проведите параметрический анализ оптимального решения следующей задачи ЛП, предполагая, что t > 0.
Минимизировать г = 4Xj 4- х2 + 2х3
при ограничениях
Зхх + х2 + 2хг = 3 + 3t, 4х, + Зх, + 2х3 > 6 + 2f, х, + 2х2 + 5х3 < 4 - г,
*2* 3~ *
3. При выполнении параметрического анализа в этом разделе предполагалось, что оптимальное решение задачи ЛП при £ = 0 получено обычным симплекс-методом. Однако в некоторых ситуациях предпочтительнее получать оптимальное решение двойственным симплекс-методом (раздел 4.4). Разработайте схему проведения параметрического анализа для такого случая и выполните анализ задачи ЛП из примера 4.4.1, предполагая, что вектор правых частей ограничений задачи задан следующим выражением (считаем, что t > 0).
b(f) = (3 + 2r, б-t, 3-4г)т
4. Решите задачу из упражнения 2, предполагая, что вектор правых частей ограничений задан следующим выражением.
Ь(0 = (3 + 3t\ 6 + 2t\ 4 - t2f
Затем решите эту же задачу при условии, что параметр t может принимать как положительные, так и отрицательные значения.
7.7. МЕТОД КАРМАРКАРА
В симплекс-методе оптимальное решение находится путем продвижения вдоль граней пространства решений от одной угловой (крайней) точки к другой. Хотя на практике симплекс-метод применяется для решения очень больших задач, теоретически количество итераций, необходимых для достижения оптимального решения, может расти по экспоненциальному закону. Можно построить задачу ЛП с л переменными, при решении которой необходимо перебрать все 2" крайних точек, пока не будет достигнуто оптимальное решение.
В 1984 году Н. Кармаркар (N. Karmarkar) разработал алгоритм с полиномиальным временем выполнения, который "пробегает" по внутренним точкам пространства решений. Этот алгоритм особенно эффективен при решении очень больших задач ЛП.
Мы сначала рассмотрим основную идею метода Кармаркара, а затем остановимся на вычислительной реализации алгоритма.
7.7.1. Основная идея метода Кармаркара
Рассмотрим очень простой пример.
Максимизировать г = хх при выполнении ограничения
0<x,<2.
Вводим дополнительную (остаточную) переменную х2. Задача в стандартной форме будет записана следующим образом.
Максимизировать г = х1
при ограничениях
ос j ~\~ ос 2) хх, х2 > 0.
Эта задача представлена на рис. 7.6. Ее пространство решений совпадает с отрезком прямой АВ. Направление возрастания целевой функции z совпадает с положительным направлением оси хх.
Рис. 7.6. Иллюстрация основной идеи метода Кармаркара
Начнем поиск оптимального решения с произвольной внутренней (не крайней) точки С пространства допустимых решений (отрезок АВ). Градиент целевой функции г = х, в точке С показывает направление скорейшего возрастания функции г. Если мы зафиксируем какую-нибудь точку вдоль градиента и опустим из нее перпендикуляр на пространство допустимых решений, то получим новую точку D с лучшим значением целевой функции. Такое улучшение значения целевой функции получено вследствие движения по направлению проекции CD градиента. Если мы повторим описанную процедуру для точки D, получим новую точку Е, которая будет еще ближе к точке оптимума В. Таким образом, если мы будем двигаться (но осторожно) в направлении проекции градиента, то, вероятно, рано или поздно