Xreferat.com » Рефераты по экономико-математическому моделированию » Применение метода ветвей и границ для задач календарного планирования

Применение метода ветвей и границ для задач календарного планирования

границ для задач календарного планирования" width="114" height="103" align="LEFT" />

Решение задачи z = 4х1 + х2 +1 ® max при ограничениях:


с помощью табличного процессора Microsoft Excel.


Применение метода ветвей и границ для задач календарного планирования


Приложение 3


В качестве примера применения метода ветвей и границ приведем поиск оптимального значения функции Z = Зх1 + х2 ® max при ограничениях:

Применение метода ветвей и границ для задач календарного планирования

4xl + Зх2 < 18,

x1 + 2x2 Ј 6,

0 Ј x1 Ј 5,

0 Ј x2 Ј 4,


х1, x2 — целые числа.


Решение


За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0 = Z (0; 0) = 0.

I этап. Решая задачу симплекс-методом, получим Zmax = 13,5 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента х1* дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение х1*, т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3.


Задача 2


Z=3x1+x2→max


при ограничениях:

Применение метода ветвей и границ для задач календарного планирования

4xl + Зх2 < 18

x1 + 2x2 Ј 6

0 Ј x1 Ј 4

0 Ј x2 Ј 4


х1, x2 — целые числа.


Задача 3


Z=3x1+x2→max


при ограничениях:

Применение метода ветвей и границ для задач календарного планирования

4xl + Зх2 < 18

x1 + 2x2 Ј 6

5 Ј x1 Ј 5

0 Ј x2 Ј 4


х1, x2 — целые числа.


Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0= 0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплекс-методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплекс-методом. Получим Zmax = 12 2/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 12 2/3 > Z0 = 0, по-прежнему сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2* — дробное число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем на две задачи 4 и 5.


Задача 4


Z=3x1+x2→max


при ограничениях:


Применение метода ветвей и границ для задач календарного планирования4xl + Зх2 < 18

x1 + 2x2 Ј 6

0 Ј x1 Ј 4

0 Ј x2 Ј 0


х1, x2 — целые числа.


Задача 5


Z=3x1+x2→max


при ограничениях:


Применение метода ветвей и границ для задач календарного планирования4xl + Зх2 < 18

x1 + 2x2 Ј 6

0 Ј x1 Ј 4

1 Ј x2 Ј 4


х1, x2 — целые числа.


Список задач: 4 и 5. Значение Z0 = 0.

IV этап. Решаем задачу 4 симплекс-методом.

Получим Zmax = 12 при X4* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0 = Z(X4*) = 12, ибо план Х4* целочисленный.

V этап. Решаем задачу 5 симплекс-методом.

Получим Zmax = 12,25 при X5* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не меняется, т.е. Z0 = 12, ибо план X5* нецелочисленный. Так как х1* — дробное, из области решений исключаем полосу 3<x1<4, и задача 5 разбивается на две задачи: 6 и 7.


Задача 6


Z=3x1+x2→max


при ограничениях:

Применение метода ветвей и границ для задач календарного планирования

4xl + Зх2 < 18

x1 + 2x2 Ј 6

0 Ј x1 Ј 3

1 Ј x2 Ј 4


х1, x2 — целые числа.


Задача 7


Z=3x1+x2→max


при ограничениях:

Применение метода ветвей и границ для задач календарного планирования

4xl + Зх2 < 18

x1 + 2x2 Ј 6

4 Ј x1 Ј 4

1 Ј x2 Ј 4


х1, x2 — целые числа.


Список задач: 6 и 7. Значение Z0 = 12.

VI этап. Решаем одну из задач списка, например задачу 7, симплекс-методом. Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплекс-методом. Получим Zmax = 10,5 ,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как, Z(X6*) = 10,5 < Z0 = 12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет X* = Х4* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax = 12.

Размещено на

1 «Оптимальным» будем называть план, оптимальный на данный момент решения.

2 Естественно, без введения и вычисления переменных искусственного базиса.

1 «о трех станкак».

30


Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: