Задачи параметрического программирования

Так как определяющую роль на этом шаге решения играет величина M, превышающая все величины задачи, то не обращаем внимания на λ и, обнаружив невыполнение критерия оптимальности для X0, вводим в базис A4 вместо A7 (переходим к следующему опорному плану):

Полученный опорный план X1 = (0, 0, 0, 5, 0, 8) c L(X1, λ) = 5 будет оптимальным, если все значения Δkнеположительны, т. е.

Решаем систему двух линейных неравенств и обнаруживаем, что найденный план X1 оптимален при λ = 3.

Исследуем оставшиеся из заданного диапазона значения λ.

Пусть λ > 3. Тогда Δ2 > 0 и вектор A2 подлежит вводу в базис, но в силу неположительности его компонент приходим к выводу, что при λ > 3 линейная форма задачи не ограничена снизу.

Пусть λ < 3. Тогда Δ1 > 0 и в базис вводится вектор A1:

Полученный опорный план является оптимальным, если все значения Δk неположительны, т. е.

Решая эту систему линейных неравенств, обнаруживаем, что найденный план X=(8/5, 0, 0, 1/5) c L(X, λ) = (8λ + 1)/5 оптимален при -2 ≤ λ ≤ 3.

Пусть λ < -2. Тогда Δ5 > 0 и вектор A5 подлежит вводу в базис; в силу неположительности его компонент приходим к выводу, что при λ < -2 линейная форма задачи не ограничена снизу.

Таким образом, мы получили решение задачи:

Пример 2.Рассмотрим задачу минимизации

L(X, λ) = (2 - λ)X1 - 3λX2 + (λ - 3)X3

при условиях

X1 + X2 + X3 ≤ 5;

3X1 - X2 - 2X3 ≤ 6;

X1 + 2X2 + 2X3 ≤ 8;

Xk ≥ 0,   k = 1 ... 3;    -∞ < λ < ∞.

Решение.

Находим начальный опорный план задачи X0 = (0, 0, 0, 5, 6, 8) c L(X0, ) = 0, который был бы оптимален при выполнении условий:

Δ1 = λ - 2 ≤ 0,     Δ2 = 3λ - 2 ≤ 0,     Δ3 = 3 - λ ≤ 0.

Однако попытка решения этой системы трех линейных неравенств обнару-живает её противоречивость (λ ≤ 2, λ ≤ 0, λ ≥ 3).

Пусть λ < 3. Тогда Δ3 > 0 и выводим в базис A3:

Полученный опорный план оптимален, если

Δ1 = (3λ - 7)/2 ≤ 0,     Δ2 = 4λ - 3 ≤ 0,     Δ6 = (λ - 3)/2 ≤ 0.

Решение этой системы неравенств обнаруживает, что план X=(0,0,4) c L(X, λ) = 4(&lambda - 3) оптимален при λ ≤ 3/4.

Пусть λ > 3/4. Тогда Δ2 > 0 и вводим в базис A2:

Полученный план оптимален, если:

Δ1 = - (λ + 4)/2 ≤ 0,     Δ3 = - 4λ + 3 ≤ 0,     Δ6 = 3λ / 2 ≤ 0.

Решение системы трех неравенств обнаруживает, что план X = (0, 4, 0) c L(X, λ)= -12λ оптимален при всех λ ≥ 3/4.

Таким образом, рассмотрен весь диапазон значений λ. Задача решена:

Пример 3. Рассмотрим задачу максимизации

L(X, λ) = X1 - X2 - 2X3

при условиях

X1 + X2 + X3 ≤ 3 + λ;

2X1 - X2 + X3 ≤ 5 - λ;

Xk ≥ 0,   k = 1 ... 3;    -∞ < λ < ∞.

Решение. Чтобы решить эту задачу, достаточно решить двойственную к ней задачу, имеющую вид:

минимизировать

L(Y, λ) = (3 + λ)Y1 + (5 - λ)Y2

при условиях

Y1  +  2Y2  ≥  1;

Y1  -  Y2  ≥  -1;

Y1  +  Y2  ≥  -2;

Y1,  Y2  ≥  0;

-∞  <  λ  <  ∞.

Приводим двойственную задачу к канонической форме (умножив предварительно второе и третье неравенства на -1) и начинаем обычное решение обычным симплексным методом. Заметьте, что указанное умножение тождественно смене знака у переменных x2 и x3 исходной задачи.

 

Найденный план Y = (1, 0) оптимален, если Δ2 = (1+3λ) ≤ 0 и Δ3 = - (3 + λ) ≤ 0, т.е. при -3 ≤ λ ≤ -1/3    Yopt = (1, 0). В строке Zk (в позициях 6, 4, и 5 в соответствии с начальным базисом) находим решение прямой задачи: Xopt = (3 + λ, -0, -0), L(Xopt) = 3 + λ.

Пусть λ < -3. Попытка ввода в базис вектора A3 обнаруживает, что в этом случае линейная форма решаемой (двойственной) задачи не ограничена снизу и, следовательно, ограничения исходной задачи противоречивы.

В случае λ > -1/3 имеем:

Решаем систему неравенств Δ1 = -(3λ + 1)/2 ≤ 0, Δ3 = -(5 - λ)/2 ≤ 0. Обнаруживаем, что при -1/3 ≤ λ ≤ 5     Yopt = (0, 1/2), Xopt = ((5 - λ)/2, -0, -0), L(Xopt) = (5 - λ)/2.

Продолжаем решение задачи при λ > 5 . Получаем:

Видим, что при λ ≥ 5     Yopt = (0, 1), Xopt = (0, -5 + λ, -0), L(Xopt) = 5 - λ.

Задача решена:

Увы, в случае зависимости от параметра компонент матрицы ограничений столь простого универсальногоподхода к решению не существует. Нет простых решений и в случае зависимости характеристик задачи от нескольких параметров.

 

 

 

 

 

Заключение

Литература.

При написании курсовой использовалась следующая справочная литература: Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование, Ашманов С.А. Линейное программирование. Некоторые примеры были взяты из книг Копылов В.И. Лекции и практические занятия по математическому программированию, Акулич И.Л. Математическое программирование в примерах и задачах.