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

Министерство образования Р.Ф.

Тюменский государственный нефтегазовый университет

Институт нефти и газа

                                                                                         Кафедра менеджмента

                                                                                         В отраслях ТЭК

Контрольная работа по

Дисциплине «Экономическая математика, методы и модели»

Вариант №4

                                                                                 Выполнил: студент гр.

                                                                                  МОс2 Ваганова А.Р.

                                                                                 Проверил: Захаров А.В

Тюмень 2002 г.

Метод ветвей и границ. Рассмотримзадачу, состоящую в определении максимального значения функции

/>

при условиях

/>

            Как и при решении сформулированнойзадачи методом Гомори, первоначально находим симплексным методом искусственногобазиса оптимальный план задачи без учета целочисленности переменных. Пусть имявляется план X0. Если среди компонент этого плана нет дробныхчисел, то тем самым найдено искомое решение задачи и />.

            Если же компонентплана Х0 имеются дробные числа, то Х0не удовлетворяетусловию целочисленности и необходимо осуществить упорядоченный переход к новымпланам, пока не будет найдено решение задачи. Покажем, как это можно сделать,предварительно отметив, что /> длявсякого последующего плана Х.

            Предполагая, чтонайденный оптимальный план Х0не удовлетворяет условиюцелочисленности переменных, тем самым считаем, что среди его компонент естьдробные числа. Пусть например переменная /> принялав плане Х0дробное значение. Тогда в оптимальном целочисленном планееё значение будет по крайней мере либо больше, либо меньше или равно ближайшемуменьшему целому числу />, либо больше илиравно ближайшему большему целому  числу />.Определяя эти числа, находим симплексным методом решение двух задач линейногопрограммирования:

/>
            Найдем рассмотренными выше методами решение задач линейногопрограммирования (I) и (II).Очевидно, здесь возможен один из следующих 4:

1.   Одна из задач неразрешима, а другая имеет целочисленный оптимальныйплан. Тогда этот план и значение целевой функции на нём и дают решение исходнойзадачи.

2.   Одна из задач неразрешима, а другая имеет оптимальный план, средикомпонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ееоптимальном плане выбираем одну из компонент, значение которой равно дробномучислу, и строим две задачи, аналогичные задачам  (I) и (II).

3.   Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленныйплан, а в оптимальном плане второй задачи есть дробные числа. Тогда вычисляемзначение целевой функции на этих планах и сравниваем их между собой. Если нацелочисленном оптимальном плане значение целевой функции больше, или равно еезначению на плане, среди компонент которого есть дробные числа, то данныйцелочисленный план является оптимальным для исходной задачи и он вместе созначением целевой функции на нем дает искомое  решение.

Если же значение целевой функции больше на плане, среди компоненткоторого есть дробные числа, то следует взять одно из таких чисел и для задачи,план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II).

4.   Обе задачи разрешимы, и среди оптимальных планов обеих задач естьдробные числа. Тогда выделяем значение целевой функции на данных оптимальныхпланах и рассматриваем ту из задач, для которой значение целевой функцииявляется наибольшим. В оптимальном плане этой задачи выбираем одну изкомпонент, значение которой является дробным числом, и строим две задачи,аналогичные (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 Методомветвей и границ найти решение задачи, состоящей в определении максимального значения функции

/>

при условиях/>

/>

xj – целые (j=/>)

Р е ш е н и е. Находим решениесформулированной задачи симплексным методом без учета условия целочисленностипеременных. В результате устанавливаем, что такая задача имеет оптимальный планХ0= (18/5, 3/5, 0, 0, 24/5).  При этом плане F= (X0)=39/5.

Так как в плане Х0значения трех переменных являются дробными числами, то Х0 не удовлетворяетусловию целочисленности, и следовательно, не является оптимальным планомисходной задачи.

Возьмем  какую-нибудь переменную,значение которой является дробным числом, например х1. Тогда этапеременная<sub/>в оптимальном плане исходной задачи будет принимать значение,либо меньшее или равное трём:/>, либобольше или равно четырём: />.

Рассмотрим две задачи линейногопрограммирования:

(I)/>                    (II)/>

Задача (I)имеет оптимальный план /> накотором значение целевой функции />. Задача(II) неразрешима.

Исследуем задачу (I). Так как среди компонент оптимального плана этой задачиесть дробные числа, то для одной из переменных, например x2, вводимдополнительные ограничения:

/>

Рассмотрим теперь следующие двезадачи:

/>(III)/>

(IV) />

Задача (IV) неразрешима, а задача (III) имеетоптимальный план />(3, 1, 3, 3, 3),на котором значение целевой функции задачи />

Таким образомисходная задача целочисленного программирования имеет оптимальный план Х*=(3, 1, 2, 3, 3). При этом плане целевая функция принимает максимальное значение/>.

Схемуреализованного выше вычислительного процесса можно представить в виде дерева,ветвями которого являются соответствующие ограничения на переменные, авершинами – решения соответствующих задач линейного программирования (рис 2.5).

Дадимгеометрическую интерпретацию решения задачи (50)-(53). На рис. 2.6 показана областьдопустимых решений задачи (50)-(52).

Из него видно,что данная задача имеет оптимальный план/>(18/5,3/5, 0, 0, 24/5). В то же время /> неявляется планом задачи (50)-(53), поскольку три переменные имеют дробныезначения. Возьмем переменную х1 и рассмотрим задачи (I)<sub/>и (II).

Как видно изрис.  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<sub/>и<sub/>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 -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,  />при 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имеютсяотрицательные числа />. В данном случаеэто условие выполняется. Поэтому переходим к новому опорному плану, для чеговведем в базис вектор Р1и исключаем из него вектор Р2(табл. 2.42).

            Таблица2.42/>

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, />-оптимальный план задачи длявсех 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 -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, /> является оптимальным планомзадачи для всех значений параметра t, прикоторых />

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

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

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