Чтобы найти первое критическое значение используем условие допустимости Хя = В Ь(/) > 0, которое в данном случае примет вид

Эти неравенства выполняются при t < 10/3. Таким образом, = 10/3, и базис В0 остается допустимым при изменении параметра t в интервале 0 < t < 10/3. Отметим, что здесь значения базисных переменных хг, х3 и хв изменяются при изменении параметра t.

Значение базисной переменной х6 (= 10 - 3t) равно нулю при t = tх = 10/3 и становится отрицательным для t > 10/3. Следовательно, при t = 10/3 необходимо определить новый базис В,. Для этого применим модифицированный симплекс-метод (см. упражнение 7.2.2.5). Исключаемой из базиса будет переменная х6.

Новый базис при t = 10/3.

Имея переменную хе в качестве исключаемой из базиса, определяем вводимую в базис. Поскольку

х = (Х2> хз> *в) и ся С) = (2> 5> °)>

к-и,={в0-ру-сл14а-(4,1,2).

Далее вычисляем

{(ВРД. };=М], = (строка в В 1, ассоциированная с х6) (Р Р4, Р5) =

= (3-я строка в В0) (Р Р4, Р5) -= (-2, 1, 1)(Р Р4,Р6) = = (2,-2, 1).

Отсюда следует, что

e = min< -

соответствует переменной xt. Следовательно, в базис вводится вектор Р4. Вычисляем новый базис и обратную матрицу В~.

ХВ; (2 XV 4

2 1 \\

В,=(Р2,Р3,Р4) =

0 2 0 4 0 0

0 0

Следующее критическое значение t2 определяем из условия Хв = В, Ь(г) >0. Отсюда получаем следующее.

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 приведены в следующей таблице.

УПРАЖНЕНИЯ 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) разработал алгоритм с полиномиальным временем выполнения, который пробегает по внутренним точкам пространства решений. Этот алгоритм особенно эффективен при решении очень больших задач ЛП.

Мы сначала рассмотрим основную идею метода Кармаркара, а затем остановимся на вычислительной реализации алгоритма.