Метод ветвей и границ (контрольная)

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: бесплатные рефераты на тему, шпоры по педагогике
| Добавил(а) на сайт: Denisov.

Как видно из рис. 2.7задача (I) имеет оптимальный план [pic](3, 3/2,
0, 9/2, 3/2), а из рис.2.8 следует, что задача (II) неразрешима.

Поскольку среди компонент плана [pic]есть дробные числа, выберем переменную х2 и рассмотрим задачи (III) (IV). Задача (III) имеет оптимальный план[pic](3, 1, 2, 3, 3) (рис. 2.9), а задача (IV) неразрешима
(рис. 2.10).

Итак, Х*= (3, 1, 2, 3, 3) является оптимальным планом задачи (50)-(53).
При этом плане [pic].

Решение задачи, правые части которых содержат параметр.

Алгоритм решения задачи (60)-(62) подобен рассмотренному выше алгоритму решения задачи (57)-(59).

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

[pic] и числа qi и pi определены компонентами оптимального плана и зависят от t0:

[pic]

Если при t = t0 задача (60)-(62) неразрешима, то, либо целевая функция задачи (60) не ограничена на множестве планов, либо система уравнений не имеет неотрицательных решений. В первом случае задача неразрешима для всех [pic], а во втором случае определяем все значения параметра [pic], для которых система уравнений (61) несовместна, и исключаем их из рассмотрения.

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

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

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

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

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

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

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

[pic] при условиях

[pic]
Р е ш е н и е . Считая значение параметра 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, [pic]при t =0 есть оптимальный план задачи.
Однако [pic] является оптимальным планом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t[pic]0; 7+4t[pic]0;
13+t[pic] или при [pic] Таким образом, если [pic] то[pic]- оптимальный план задачи (80)-(82), при котором [pic]

Исследуем теперь, имеет ли задача оптимальные планы при [pic][pic].
Если [pic], то 5-3t17/2, то [pic]не является планом задачи, так как третья компонента 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, [pic] является оптимальным планом задачи для всех значений параметра t, при которых [pic]

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

Из табл. 2.43 так же видно, что при t