Реферат: Метод ветвей и границ (контрольная)
Как видно из рис. 2.7задача (I) имеет оптимальный план (3, 3/2, 0, 9/2, 3/2), а из рис.2.8 следует, что задача (II) неразрешима.
Поскольку среди компонент плана есть дробные числа, выберем переменную х2 и рассмотрим задачи (III) (IV). Задача (III) имеет оптимальный план(3, 1, 2, 3, 3) (рис. 2.9), а задача (IV) неразрешима (рис. 2.10).
Итак, Х*= (3, 1, 2, 3, 3) является оптимальным планом задачи (50)-(53). При этом плане .
Решение задачи, правые части которых содержат параметр.
Алгоритм решения задачи (60)-(62) подобен рассмотренному выше алгоритму решения задачи (57)-(59).
Полагая значение параметра t равным некоторому числу t0, находим решение полученной задачи линейного программирования (60)-(62). При данном значении параметра t0 либо определяем оптимальный план, либо устанавливаем неразрешимость задачи. В первом случае найденный план является оптимальным для любого, где
и числа qi и pi определены компонентами оптимального плана и зависят от t0:
Если при t = t0 задача (60)-(62) неразрешима, то, либо целевая функция задачи (60) не ограничена на множестве планов, либо система уравнений не имеет неотрицательных решений. В первом случае задача неразрешима для всех , а во втором случае определяем все значения параметра , для которых система уравнений (61) несовместна, и исключаем их из рассмотрения.
После определения промежутка, в котором задача (60)-(62) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра t, не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью действенного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (60)-(62).
Итак, процесс нахождения задачи (60)-(62) включает следующие основные этапы:
10. Считая значение параметра t равным некоторому числу , находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.
20. Находят значения параметра , для которых задача (60)-(62) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра t исключают из рассмотрения.
30. Выбирают значения параметра t из оставшейся части промежутка и устанавливают возможность определения нового оптимального плана находят его двойственным симплекс-методом.
40. Определяют множество значений параметра t, для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра .
2.66. Для каждого значения параметра найти максимальное значение функции
при условиях
Р е ш е н и е . Считая значение параметра t в системе уравнений (81) равным нулю, находим решение задачи (80)-(82) (табл. 2. 41).
Таблица 2.41
i |
Базис |
Сб |
Р0 |
3 | -2 | 5 | 0 | -4 |
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
||||
1 |
Р3 |
5 |
12+t |
1 | 1 | 1 | 0 | 0 |
2 |
Р4 |
0 |
8+4t |
2 | -1 | 0 | 1 | 0 |
3 |
Р5 |
-4 |
10-6t |
-2 | 2 | 0 | 0 | 1 |
4 |
20+29t |
10 | -1 | 0 | 0 | 0 | ||
1 |
Р3 |
5 |
7+4t |
2 | 0 | 1 | 0 | -½ |
2 |
Р4 |
0 |
13+t |
1 | 0 | 0 | 1 | ½ |
3 |
Р2 |
-2 |
5-3t |
-1 | 1 | 0 | 0 | ½ |
4 |
25+26t |
9 | 0 | 0 | 0 | ½ |
Как видно из табл. 2.41, при t =0 есть оптимальный план задачи. Однако является оптимальным планом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t0; 7+4t0;
13+t или при Таким образом, если то- оптимальный план задачи (80)-(82), при котором
Исследуем теперь, имеет ли задача оптимальные планы при . Если , то 5-3t<0 и следовательно, X=(0,5 – 3t, 7+4t, 13+t, 0) не является планом задачи. Поэтому при нужно перейти к новому плану, который был в то же время оптимальным. Это можно сделать в том случае, когда в строке вектора Р2 имеются отрицательные числа . В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Р1 и исключаем из него вектор Р2 (табл. 2.42).
Таблица 2.42
i |
Базис |
Сб |
Р0 |
3 | -2 | 5 | 0 | -4 |
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
||||
1 |
Р3 |
5 |
17+2t |
0 | 2 | 1 | 0 | ½ |
2 |
Р4 |
0 |
18-2t |
0 | 1 | 0 | 1 | 1 |
3 |
Р1 |
3 |
-5+3t |
1 | -1 | 0 | 0 | -½ |
4 |
70-t |
0 | 9 | 0 | 0 | 5 |
Как видно из табл. 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 есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р3 стоит отрицательное число -1/2), нужно исключить из базиса вектор Р3 и ввести в базис вектор Р5 (табл. 2.43).
Таблица 2.43
i |
Базис |
Сб |
Р0 |
3 | -2 | 5 | 0 | -4 |
Р1 |
Р2 |
Р3 |
Р4 |
Р5 |
||||
1 |
Р5 |
-4 | -14-8t | -4 | 0 | -2 | 0 | 1 |
2 |
Р4 |
0 | 20+5t | 3 | 0 | 1 | 1 | 0 |
3 |
Р2 |
-2 | 12+t | 1 | 1 | 1 | 0 | 0 |
4 | 32+30t | 11 | 11 | 1 | 0 | 0 |
Как видно из табл. 2.43, является оптимальным планом задачи для всех значений параметра t, при которых
Таким образом, если , то задача (80)-(82) имеет оптимальный план , при котором
Из табл. 2.43 так же видно, что при t<4 задача неразрешима, поскольку в строке вектора Р4 нет отрицательных элементов.
Итак, если , то задача не имеет оптимального плана; если оптимальный план, а если , то - оптимальный план, а если , то - оптимальный план, а если , то задача неразрешима.