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

Конечная вершина определяет вариант (последовательность)  = 3, 1, 5, 2, 4 с наилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.

Непосредственной проверкой убеждаемся, что время обработки всей последовательности деталей для этого варианта совпадает со значением оценки-прогноза и является минимальным:

.

Список литературы

1.  Акулич И.Л. Математическое программирование в примерах и задачах. М., Высшая школа, 1993.

2.  Гончаренко В.М. «Математические методы и модели операций. Руководство к решению задач». М., Финансовая Академия, 2006.

3.  Зайченко Ю.П. Исследование операций. Киев, Высшая школа, 1975.

4.  Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М., Высшая школа, 1980.

5.  Шкурба В.В. Задача трех станков. М., Наука, 1976.

Приложение 1

Решение задачи

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

симплекс-методом:

z*=13,5,Х1*=(3;0,5;0;1;0;2,5).

Приложение 2

Решение задачи 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] Естественно, без введения и вычисления переменных искусственного базиса.

[3] «о трех станкак».