work metod (Метод ветвей и границ (контрольная)), страница 2

После определения промежутка, в котором задача (60)-(62) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра t, не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью действенного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (60)-(62).

Итак, процесс нахождения задачи (60)-(62) включает следующие основные этапы:

1⁰. Считая значение параметра t равным некоторому числу , находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.

2⁰. Находят значения параметра , для которых задача (60)-(62) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра t исключают из рассмотрения.

3⁰. Выбирают значения параметра t из оставшейся части промежутка и устанавливают возможность определения нового оптимального плана находят его двойственным симплекс-методом.

4⁰. Определяют множество значений параметра t, для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра .

2.66. Для каждого значения параметра найти максимальное значение функции

при условиях

Р е ш е н и е . Считая значение параметра t в системе уравнений (81) равным нулю, находим решение задачи (80)-(82) (табл. 2. 41).

Таблица 2.41

Как видно из табл. 2.41, при t =0 есть оптимальный план задачи. Однако является оптимальным планом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t 0; 7+4t 0;

13+t или при Таким образом, если то - оптимальный план задачи (80)-(82), при котором

Исследуем теперь, имеет ли задача оптимальные планы при . Если , то 5-3t<0 и следовательно, X=(0,5 – 3t, 7+4t, 13+t, 0) не является планом задачи. Поэтому при нужно перейти к новому плану, который был в то же время оптимальным. Это можно сделать в том случае, когда в строке вектора Р₂ имеются отрицательные числа . В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Р₁ и исключаем из него вектор Р₂ (табл. 2.42).

Таблица 2.42

Как видно из табл. 2.42, -оптимальный план задачи для всех t, при которых Следовательно, если является оптимальным планом исходной задачи, причем .

Если t>17/2, то не является планом задачи, так как третья компонента 17 – 2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2.42 нет отрицательных при t>17/2 исходная задача неразрешима.

Исследуем теперь разрешимость задачи при t< -7/4. В этом случае Х= (0,5 -3t, 7+4t, 13+t, 0) (см. табл.2.41) не является планом задачи, так как третья компонента 7+4t есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р₃ стоит отрицательное число -1/2), нужно исключить из базиса вектор Р₃ и ввести в базис вектор Р₅ (табл. 2.43).

Таблица 2.43

Как видно из табл. 2.43, является оптимальным планом задачи для всех значений параметра t, при которых

Таким образом, если , то задача (80)-(82) имеет оптимальный план , при котором

Из табл. 2.43 так же видно, что при t<4 задача неразрешима, поскольку в строке вектора Р₄ нет отрицательных элементов.

Итак, если , то задача не имеет оптимального плана; если оптимальный план, а если , то - оптимальный план, а если , то - оптимальный план, а если , то задача неразрешима.