Очередное критическое значение tM определяется как наибольшее t, t > tt, при котором выполняются все условия оптимальности.

Отметим, что приведенное неравенство не требует, чтобы вектор С(0 был линейной функцией от t; допустима функциональная зависимость любого вида - как линейная, так и нелинейная. Трудность использования нелинейных функций заключается лишь в том, что численное решение системы неравенств может быть очень трудоемким. (В упражнении 7.6.1.5 рассмотрен случай нелинейной функции.)

Пример 7.6.1

Рассмотрим задачу ЛП.

Максимизировать г = (3 - 60 х, + (2 - 2t) х2 + (5 + 50 х. при ограничениях

х, + 2х2 + х3< 40, Зхх + 2х3<60, х1 + 4х2 < 30,

Здесь С(0 = (3 - 6t, 2 - 2t, 5 + 50, t > 0. Введем дополнительные (остаточные) переменные х4, х5 и х6.

Оптимальное решение при t0 = 0.

Хйо - (х2, х3, х/ = (5, 30, 10f СВо(/) =(2-2t, Ъ + Ы, 0),

i -10

в- =

Условия оптимальности для текущих небазисных векторов Р Р4 и Р5 имеют вид {<: (/)В-Ру - с )}.= о = (4 + Ш, 1 - t, 2 + 3t) > 0.

Таким образом, решение остается оптимальным до тех пор, пока выполняются неравенства

4 + 14t>0,

1 -t>0,

2 + 3t> 0.

Первое и третье неравенства выполняются при всех положительных t (напомним, что t > 0), второе - справедливо при t < 1. Отсюда имеем, что £, = 1, т.е. решение остается оптимальным (и допустимым) для всех t из интервала 0 < t < 1.

При t = 1 разность z4(f) - ct(t) = 1 -1 равна нулю и становится отрицательной при t > 1. Поэтому при f > 1 вектор Р4 должен войти в базис, тогда вектор Р2 будет исключен из базиса (см. симплекс-таблицу с оптимальным решением при t = 0). Итак, при t = 1 (вследствие включения в базис вектора Р4) получаем новое решение Х .

Оптимальное решение при f, = 1. Имеем новый базис и новую обратную матрицу.

Отсюда получаем

Х = (xt, х3, хв)т = В-Ь = (10, 30, 30)т, Ся(0 =(0, 5 + 5i, 0).

Для небазисных векторов Р Р2 и Р5 условия оптимальности можно записать следующим образом.

{C,(0Br-P,-ciW}=(.-2 + 2i.)20

В соответствии с этими условиями базисное решение Хв остается оптимальным для

всех t > 1. Это означает, что t2 = °° и вычислительный процесс параметрического анализа закончен. Отметим, что условие оптимальности -2 + 2t > 0 автоматически запомнило , что решение Х оптимально в интервале, который начинается со значения £, = 1. Такое запоминание всегда имеет место при параметрическом анализе.

Оптимальные решения для всей области изменения параметра t представлены в следующей таблице. Значения целевой функции получены путем подстановки значений переменных в выражение целевой функции.

УПРАЖНЕНИЯ 7.6.1

1. Пусть в примере 7.6.1 параметр t может принимать как положительные, так и отрицательные значения. Определите интервал изменения значений параметра t, при которых решение Х% остается оптимальным.

2. Проведите параметрический анализ задачи ЛП из примера 7.6.1, если целевая функция задана следующими выражениями.

a) Максимизировать z = (3 + 3i) xt + 2х2 + (5 - 6t) х3.

b) Максимизировать z = (3 - 2t) xx + (2 +1) x2 + (5 + 2t) x3.

c) Максимизировать z = (3 +1) дг1 + (2 + 2t) x2 + (5 - t) x3.

3. Проведите параметрический анализ оптимального решения следующей задачи ЛП, здесь t > 0.

Минимизировать z = (4 - t) xl + (1 - 3t) x2 + (2 - 2t) x3 при ограничениях

3jc, +Je2+ 2x3 = 3, 4xt + 3x3 + 2x3 > 6, jc, + 2x2 + bx3 < 4,

X j j ОС - 0

4. При выполнении параметрического анализа в этом разделе предполагалось, что оптимальное решение задачи ЛП при t = 0 получено обычным симплекс-методом. Однако в некоторых ситуациях предпочтительнее получить оптимальное решение двойственным симплекс-методом (раздел 4.4). Разработайте схему проведения параметрического анализа для такого случая и выполните анализ задачи ЛП из примера 4.4.1, предполагая, что целевая функция задана следующим выражением.

Минимизировать z = (3 + t) xl + (2 + 4t) x2

5. Пусть в примере 7.6.1 целевая функция нелинейная по t (t > 0) и задается следующим выражением.

Максимизировать z = (3 + 2t2) jc, + (2 - 2t2) x2 + (5 - t) x3.

Найдите первое критическое значение tv

7.6.2. Параметрическое изменение правых частей ограничений

Параметрическое изменение вектора правых частей ограничений Ь(£) влияет только на свойство допустимости решения. В этом случае критические значения параметра t определяются на основе условия

Х = ВЬ(0>0.

Пример 7.6.2

Рассмотрим задачу ЛП.

Максимизировать z = Зх1 + 2х2 + Ъх3

при ограничениях

х, + 2х2 + x3<40~t, 3x1 + 2x3<60 + 2t, xl + 4х2 < 30 - It,

Предполагается, что t > 0.

Оптимальное решение этой задачи при t = 10 = 0 приведено в примере 7.6.1. Имеем

ХВ(] = (* х3, х/ = (5, 30, 10)т,

1 о

1 1.