Первое и третье неравенства выполняются при всех положительных 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. Имеем новый базис и новую обратную матрицу.
| | | | | \ .1 о4 |
| | | | . ВГ = | о ; о |
| | | | | 0 0 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 представлены в следующей таблице. Значения целевой функции получены путем подстановки значений переменных в выражение целевой функции.
| | | | |
0< f< 1 | | | | 160 + 140г |
t> 1 | | | | 150 + 150f |
УПРАЖНЕНИЯ 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.
Чтобы найти первое критическое значение используем условие допустимости Хя = В„Ь(/) > 0, которое в данном случае примет вид
| | 5-t N | | |
| | 30 + f | > | |
\хь) | | ,10-3/, | | |
Эти неравенства выполняются при 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