Реферат: Метод ветвей и границ (контрольная)
Министерство образования Р.Ф.
Тюменский государственный нефтегазовый университет
Институт нефти и газа
Кафедра менеджмента
Вотраслях ТЭК
Контрольная работа по
Дисциплине «Экономическая математика, методы и модели»
Вариант №4
Выполнил: студент гр.
МОс2 Ваганова А.Р.
Проверил: Захаров А.В
Тюмень 2002 г.
<span Times New Roman",«serif»;mso-fareast-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">Метод ветвей и границ. Рассмотрим задачу, состоящую в определениимаксимального значения функции
<img src="/cache/referats/13948/image002.gif" v:shapes="_x0000_i1025">
при условиях
<img src="/cache/referats/13948/image004.gif" v:shapes="_x0000_i1026">
Каки при решении сформулированной задачи методом Гомори, первоначально находимсимплексным методом искусственного базиса оптимальный план задачи без учетацелочисленности переменных. Пусть им является план X0. Если средикомпонент этого плана нет дробных чисел, то тем самым найдено искомое решениезадачи и <img src="/cache/referats/13948/image006.gif" v:shapes="_x0000_i1027">
Еслиже компонент плана Х0 имеются дробные числа, то Х0неудовлетворяет условию целочисленности и необходимо осуществить упорядоченныйпереход к новым планам, пока не будет найдено решение задачи. Покажем, как этоможно сделать, предварительно отметив, что <img src="/cache/referats/13948/image008.gif" v:shapes="_x0000_i1028"> для всякогопоследующего плана Х.
Предполагая,что найденный оптимальный план Х0не удовлетворяет условиюцелочисленности переменных, тем самым считаем, что среди его компонент естьдробные числа. Пусть например переменная <img src="/cache/referats/13948/image010.gif" v:shapes="_x0000_i1029"> приняла в плане Х0дробное значение. Тогда в оптимальном целочисленном плане её значение будет покрайней мере либо больше, либо меньше или равно ближайшему меньшему целомучислу <img src="/cache/referats/13948/image012.gif" v:shapes="_x0000_i1030"> числу <img src="/cache/referats/13948/image014.gif" v:shapes="_x0000_i1031">
<img src="/cache/referats/13948/image016.gif" v:shapes="_x0000_i1032">
Найдем рассмотренными вышеметодами решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих 4:
1.<span Times New Roman"">
2.<span Times New Roman"">
(I) и (II).3.<span Times New Roman"">
решение.Если же значение целевой функции больше на плане, среди компоненткоторого есть дробные числа, то следует взять одно из таких чисел и для задачи,план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).
4.<span Times New Roman"">
I) и (II).Таким образом,описанный выше интеграционный процесс может быть представлен в виде некоторогодерева, на котором исходная вершина отвечает оптимальному плану Х0 задачи (32)-(34), а каждая соединенная с нейветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, длякоторой значение является наибольшим. Если на некотором шаге будет полученплан, имеющий целочисленные компоненты, и значение функции на нем окажетсябольше или равно, чем значение функции в других возможных для ветвлениявершинах, то данный план является оптимальным планом исходной задачицелочисленного программирования и значение целевой функции на нем являетсямаксимальным.
Итак, процесс нахождения решения задачицелочисленного программирования (32)-(35) методом ветвей и границ включаетследующие этапы:
10 Находят решение задачи линейногопрограммирования (32)-(34)
20 Составляютдополнительные ограничения для одной из переменных, значение которой воптимальном плане задачи (32)-(34) является дробным числом.
30 Находятрешения задач (I) и (II), которые получаются иззадачи (32)-(34) в результате присоединения дополнительных ограничений.
40 Вслучае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи,аналогичные задачам (I) и (II), и находят их решение. Интеграционный процесспродолжают до тех пор, пока не будет найдена вершина, соответствующаяцелочисленному плану задачи (32)-(34) и такая, что значение в этой вершинебольше или равно значению функции в других возможных для ветвления вершинах.
Описанный вышеметод ветвей и границ имеет более простую логическую схему расчетов, чемрассмотренный выше метод Гомори. Поэтому в большинстве случаев для нахождениярешения конкретных задач целочисленного программирования с использованием ЭВМприменяется именно этот метод. В частности в рассмотренном выше ППП «Линейноепрограммирование в АСУ» для отыскания целочисленного решения конкретных задачиспользуется метод ветвления и границ.
2.51 Методом ветвей и границ найтирешение задачи, состоящей в определении максимального значения функции
<img src="/cache/referats/13948/image018.gif" v:shapes="_x0000_i1033">
при условиях<img src="/cache/referats/13948/image020.gif" v:shapes="_x0000_i1034">
<img src="/cache/referats/13948/image022.gif" v:shapes="_x0000_i1035">
xj – целые (j=<img src="/cache/referats/13948/image024.gif" v:shapes="_x0000_i1036">
Р е ш е н и е. Находим решениесформулированной задачи симплексным методом без учета условия целочисленностипеременных. В результате устанавливаем, что такая задача имеет оптимальный планХ0= (18/5, 3/5, 0, 0, 24/5). При этом плане F= (X0)=39/5.
Так как в плане Х0значения трех переменных являются дробными числами, то Х0 не удовлетворяетусловию целочисленности, и следовательно, не является оптимальным планомисходной задачи.
Возьмем какую-нибудь переменную, значение которойявляется дробным числом, например х1. Тогда эта переменнаявоптимальном плане исходной задачи будет принимать значение, либо меньшее илиравное трём:<img src="/cache/referats/13948/image026.gif" v:shapes="_x0000_i1037"><img src="/cache/referats/13948/image028.gif" v:shapes="_x0000_i1038">
Рассмотрим две задачи линейногопрограммирования:
(I)<img src="/cache/referats/13948/image030.gif" v:shapes="_x0000_i1039"> (II)<img src="/cache/referats/13948/image032.gif" v:shapes="_x0000_i1040">
Задача (I) имеет оптимальный план <img src="/cache/referats/13948/image034.gif" v:shapes="_x0000_i1041"> на котором значениецелевой функции <img src="/cache/referats/13948/image036.gif" v:shapes="_x0000_i1042">II)неразрешима.
Исследуем задачу (I). Так как среди компонентоптимального плана этой задачи есть дробные числа, то для одной из переменных,например x2, вводим дополнительные ограничения:
<img src="/cache/referats/13948/image038.gif" v:shapes="_x0000_i1043">
Рассмотрим теперь следующие двезадачи:
<img src="/cache/referats/13948/image020.gif" v:shapes="_x0000_i1044">III)<img src="/cache/referats/13948/image040.gif" v:shapes="_x0000_i1045">
(IV)<img src="/cache/referats/13948/image042.gif" v:shapes="_x0000_i1046">
Задача (IV) неразрешима, а задача (III) имеет оптимальный план <img src="/cache/referats/13948/image044.gif" v:shapes="_x0000_i1047"><img src="/cache/referats/13948/image046.gif" v:shapes="_x0000_i1048">
Таким образомисходная задача целочисленного программирования имеет оптимальный план Х*=(3, 1, 2, 3, 3). При этом плане целевая функция принимает максимальное значение<img src="/cache/referats/13948/image048.gif" v:shapes="_x0000_i1049">.
Схемуреализованного выше вычислительного процесса можно представить в виде дерева,ветвями которого являются соответствующие ограничения на переменные, авершинами – решения соответствующих задач линейного программирования (рис 2.5).
Дадимгеометрическую интерпретацию решения задачи (50)-(53). На рис. 2.6 показана областьдопустимых решений задачи (50)-(52).
Из него видно,что данная задача имеет оптимальный план<img src="/cache/referats/13948/image050.gif" v:shapes="_x0000_i1050"><img src="/cache/referats/13948/image052.gif" v:shapes="_x0000_i1051"> не является планомзадачи (50)-(53), поскольку три переменные имеют дробные значения. Возьмемпеременную х1 и рассмотрим задачи (I)и (II).
Как видно изрис. 2.7задача (I) имеет оптимальный план <img src="/cache/referats/13948/image054.gif" v:shapes="_x0000_i1052">II) неразрешима.
Посколькусреди компонент плана <img src="/cache/referats/13948/image056.gif" v:shapes="_x0000_i1053">2 ирассмотрим задачи (III) (IV).Задача (III) имеетоптимальный план<img src="/cache/referats/13948/image058.gif" v:shapes="_x0000_i1054">IV) неразрешима (рис. 2.10).
Итак, Х*=(3, 1, 2, 3, 3) является оптимальным планом задачи (50)-(53). При этом плане <img src="/cache/referats/13948/image048.gif" v:shapes="_x0000_i1055">
Решениезадачи, правые части которых содержат параметр.
Алгоритмрешения задачи (60)-(62) подобен рассмотренному выше алгоритму решения задачи(57)-(59).
Полагаязначение параметра t равным некоторому числу t0, находим решениеполученной задачи линейного программирования (60)-(62). При данном значениипараметра t0 либо определяем оптимальный план, либо устанавливаем неразрешимостьзадачи. В первом случае найденный план является оптимальным для любого, где
<img src="/cache/referats/13948/image061.gif" v:shapes="_x0000_i1056">
и числа qiиpiопределены компонентами оптимального плана и зависят от t0:
<img src="/cache/referats/13948/image063.gif" v:shapes="_x0000_i1057">
Если при t= t0задача (60)-(62) неразрешима, то, либо целевая функция задачи (60) неограничена на множестве планов, либо система уравнений не имеет неотрицательныхрешений. В первом случае задача неразрешима для всех <img src="/cache/referats/13948/image065.gif" v:shapes="_x0000_i1058"><img src="/cache/referats/13948/image065.gif" v:shapes="_x0000_i1059">
Послеопределения промежутка, в котором задача (60)-(62) имеет один и тот жеоптимальный план или неразрешима, выбираем новое значение параметра t, непринадлежащее найденному промежутку, и находим решение полученной задачилинейного программирования. При этом решение новой задачи ищем с помощьюдейственного симплекс-метода. Продолжая итерационный процесс, после конечногочисла шагов получаем решение задачи (60)-(62).
Итак,процесс нахождения задачи (60)-(62) включает следующие основные этапы:
10.Считая значение параметра t равным некоторому числу <img src="/cache/referats/13948/image067.gif" v:shapes="_x0000_i1060">
20.Находят значения параметра <img src="/cache/referats/13948/image065.gif" v:shapes="_x0000_i1061">
30.Выбирают значения параметра t из оставшейся части промежутка <img src="/cache/referats/13948/image069.gif" v:shapes="_x0000_i1062"> и устанавливаютвозможность определения нового оптимального плана находят его двойственнымсимплекс-методом.
40.Определяют множество значений параметра t, для которых задача имеет один и тотже новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра <img src="/cache/referats/13948/image065.gif" v:shapes="_x0000_i1063">
2.66. Для каждого значения параметра <img src="/cache/referats/13948/image071.gif" v:shapes="_x0000_i1064">
<img src="/cache/referats/13948/image073.gif" v:shapes="_x0000_i1065">
при условиях
<img src="/cache/referats/13948/image075.gif" v:shapes="_x0000_i1066">
Р е ш е н и е. Считая значениепараметра t в системе уравнений (81) равным нулю, находим решение задачи(80)-(82) (табл. 2. 41).
Таблица 2.41
i
Базис
Сб
Р0
3
-2
5
-4
Р1
Р2
Р3
Р4
Р5
1
Р3
5
12+t
1
1
1
2
Р4
8+4t
2
-1
1
3
Р5
-4
10-6t
-2
2
1
4
20+29t
10
-1
1
Р3
5
7+4t
2
1
-½
2
Р4
13+t
1
1
½
3
Р2
-2
5-3t
-1
1
½
4
25+26t
9
½
Как видно из табл. 2.41, <img src="/cache/referats/13948/image077.gif" v:shapes="_x0000_i1067">t=0 естьоптимальный план задачи. Однако <img src="/cache/referats/13948/image079.gif" v:shapes="_x0000_i1068"> является оптимальнымпланом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при5-3t<img src="/cache/referats/13948/image081.gif" v:shapes="_x0000_i1069">t<img src="/cache/referats/13948/image081.gif" v:shapes="_x0000_i1070">0;
13+t<img src="/cache/referats/13948/image083.gif" v:shapes="_x0000_i1071"> или при <img src="/cache/referats/13948/image085.gif" v:shapes="_x0000_i1072"> Таким образом,если <img src="/cache/referats/13948/image087.gif" v:shapes="_x0000_i1073"> то<img src="/cache/referats/13948/image089.gif" v:shapes="_x0000_i1074"><img src="/cache/referats/13948/image091.gif" v:shapes="_x0000_i1075">
Исследуемтеперь, имеет ли задача оптимальные планы при <img src="/cache/referats/13948/image020.gif" v:shapes="_x0000_i1076"><img src="/cache/referats/13948/image093.gif" v:shapes="_x0000_i1077"><img src="/cache/referats/13948/image093.gif" v:shapes="_x0000_i1078">5-3t<0 иследовательно, X=(0,5 – 3t, 7+4t, 13+t, 0) не является планом задачи. Поэтому при <img src="/cache/referats/13948/image093.gif" v:shapes="_x0000_i1079"> нужно перейти к новомуплану, который был в то же время оптимальным. Это можно сделать в том случае, когда в строке вектора Р2 имеются отрицательныечисла <img src="/cache/referats/13948/image095.gif" v:shapes="_x0000_i1080">Р1 и исключаем из него вектор Р2 (табл. 2.42).
Таблица 2.42<img src="/cache/referats/13948/image020.gif" v:shapes="_x0000_i1081">
i
Базис
Сб
Р0
3
-2
5
-4
Р1
Р2
Р3
Р4
Р5
1
Р3
5
17+2t
2
1
½
2
Р4
18-2t
1
1
1
3
Р1
3
-5+3t
1
-1
-½
4
70-t
9
5
Как видно изтабл. 2.42, <img src="/cache/referats/13948/image097.gif" v:shapes="_x0000_i1082">t, прикоторых <img src="/cache/referats/13948/image099.gif" v:shapes="_x0000_i1083"> Следовательно, если <img src="/cache/referats/13948/image101.gif" v:shapes="_x0000_i1084"><img src="/cache/referats/13948/image103.gif" v:shapes="_x0000_i1085">
Если t>17/2, то <img src="/cache/referats/13948/image105.gif" v:shapes="_x0000_i1086">t есть отрицательное число. Посколькусреди элементов 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
-4
Р1
Р2
Р3
Р4
Р5
1
Р5
-4
-14-8t
-4
-2
1
2
Р4
20+5t
3
1
1
3
Р2
-2
12+t
1
1
1
4
32+30t
11
11
1
Как видно из табл. 2.43, <img src="/cache/referats/13948/image107.gif" v:shapes="_x0000_i1087"> является оптимальнымпланом задачи для всех значений параметра t, при которых <img src="/cache/referats/13948/image109.gif" v:shapes="_x0000_i1088">
Таким образом, если <img src="/cache/referats/13948/image111.gif" v:shapes="_x0000_i1089"> <img src="/cache/referats/13948/image107.gif" v:shapes="_x0000_i1090"> <img src="/cache/referats/13948/image114.gif" v:shapes="_x0000_i1091">
Из табл. 2.43 так же видно, чтопри t<4 задача неразрешима,поскольку в строке вектора Р4нет отрицательных элементов.
Итак, если <img src="/cache/referats/13948/image116.gif" v:shapes="_x0000_i1092"><img src="/cache/referats/13948/image118.gif" v:shapes="_x0000_i1093"><img src="/cache/referats/13948/image120.gif" v:shapes="_x0000_i1094"> если <img src="/cache/referats/13948/image122.gif" v:shapes="_x0000_i1095"><img src="/cache/referats/13948/image124.gif" v:shapes="_x0000_i1096"><img src="/cache/referats/13948/image126.gif" v:shapes="_x0000_i1097"><img src="/cache/referats/13948/image128.gif" v:shapes="_x0000_i1098"><img src="/cache/referats/13948/image130.gif" v:shapes="_x0000_i1099"><img src="/cache/referats/13948/image132.gif" v:shapes="_x0000_i1100"> если <img src="/cache/referats/13948/image134.gif" v:shapes="_x0000_i1101">