Применение методу гілок і національних кордонів для завдань календарного планирования

ФІНАНСОВА АКАДЕМІЯ ПРИ УРЯДІ РФ.

КАФЕДРА МТЕМАТИКИ.

КУРСОВА РОБОТА тема:

Застосування методу гілок і національних кордонів для завдань календарного планирования.

Студент групи МЕК 1−1 Клеймёнов И.Д.

Науковий керівник Солодовников А.С.

МОСКВА, 2001 г.

План.

1.Постановка завдання целочисленного програмування 3.

2. Поняття методі гілок і національних кордонів 4.

3.Применение методу гілок і національних кордонів для завдань календарного планирования.

Летература 20.

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

За змістом значній своїй частині економічних завдань, ставляться до завдань лінійного програмування, компоненти рішення мають виражатися у цілих числах, тобто. бути целочисленными. До них належать, наприклад, завдання, в яких перемінні означають кількість одиниць неподільної продукції, число верстатів за мінімального завантаження устаткування, число судів при розподілах по лініях, число турбін в енергосистемі, число обчислювальних машин управляючому комплексі та багатьох інших. Завдання лінійного целочисленного програмування формується наступним чином: знайти таке рішення (план) X = (x1,x2,…, xn), у якому лінійна функция.

[pic] (1) приймає максимальне чи мінімальне значення при ограничениях.

[pic]=bi, i=1, 2…, m. (2) хj (0, j=1, 2,…, п. (3) xj — цілі числа (4).

2. Поняття методі гілок і границ.

Метод гілок і національних кордонів — одне із комбінаторних методів. Суть його залежить від упорядкованому переборі варіантів і розгляді тільки тих із них, які знаходяться за ознаками перспективними, і відкиданні безперспективних варіантів. Метод гілок і національних кордонів ось у чому: безліч допустимих рішень (планів) деяким способом розбивається на підмножини, кожна з яких цим самим способом знову розбивається на підмножини. Процес триває до того часу, доки отримано оптимальне целочисленное рішення вихідної завдання. Алгоритм рішення: Спочатку знаходимо симплексным методом чи методом штучного базису оптимальний план завдання не враховуючи целочисленности змінних. Нехай таким є план X0. Якщо серед компонент цього плану немає дробових чисел, то цим знайдено дані вирішення цього завдання і Fmax = F (Xo). Якщо серед компонент плану X0 є дробные числа, то X0 не задовольняє умові целочисленности і потрібно здійснити упорядкований перехід до нових планам, поки що не знайдено вирішення завдання. Покажемо, як це можна зробити, попередньо зазначаючи, що F (X0) (F (X) будь-кого наступного плану X. Припускаючи, що знайдений оптимальний план X0 не задовольняє умові целочисленности змінних, цим вважаємо, що його компонент є дробные числа. Нехай, наприклад, змінна [pic] прийняла у плані X0 дробове значення. Тоді, у оптимальному целочисленном плані його значення буде по крайнього заходу або менше, або одно найближчому меншому цілому числу[pic], або більше або одно найближчому більшого цілому числу [pic] + 1. Визначаючи ці числа, знаходимо симплексным методом рішення двох завдань лінійного программирования:

Знайдемо вирішення завдань лінійного програмування (I) і (II). Вочевидь, тут може бути одне із наступних чотирьох випадків: 1. Одне із завдань нерозв’язна, іншу має целочисленный оптимальний план. Тоді це план і значення цільової функції у ньому й прокурори дають рішення вихідної завдання. 2. Одне із завдань нерозв’язна, іншу має оптимальний план, серед компонент якого є дробные числа. Тоді розглядаємо другу завдання й у її оптимальному плані вибираємо жодну з компонент, значення одно дробному числу, й будуємо два завдання, аналогічні завданням (I) і (II). 3. Обидва завдання можна розв’язати. Одне із завдань має оптимальний целочисленный план, а оптимальному плані інший завдання є дробные числа. Тоді обчислюємо значення цільової функції цих плани та порівнюємо їх між собою. Коли целочисленном оптимальному плані значення цільової функції більше або одно її значенням на плані, серед компонент якого є дробные числа, то даний целочисленный план є оптимальним для вихідної завдання й він разом із значенням цільової функції у ньому дає дані рішення. Якщо ж значення цільової функції понад плані, серед компонент якого є дробные числа, слід взяти одна з таких чисел й у завдання, план якої розглядається, необхідно побудувати два завдання, аналогічні (I) і (II). 4. Обидва завдання можна розв’язати, серед оптимальних планів обох завдань є дробные числа. Тоді обчислюємо значення цільової функції на даних оптимальних плани та розглядаємо ту із завдань, на яку значення цільової функції найбільший. У оптимальному плані це завдання вибираємо жодну з компонент, значення є дробовим числом, і будуємо два завдання, аналогічні (I) і (II). Отже, описане вище итерационный процес то, можливо подано у вигляді деякого дерева, у якому вихідна вершина відповідає оптимальному плану Х0 завдання (1)-(3), а кожна сполучена із нею гілкою вершина відповідає оптимальним планам завдань (I) і (II). Кожна з цих вершин має розгалуження. У цьому кожному кроці вибирається та вершина, на яку значення функції найбільший. Коли деякому кроці отримають план, має целочисленные компоненти, і значення функції у ньому виявиться більше або одно, ніж значення функції за іншими можливих для розгалуження вершинах, то даний план є оптимальним планом вихідної завдання целочисленного програмування і значення цільової функції у ньому є межею. Отже, процес знаходження рішення завдання целочисленного програмування (1) — (4) методом гілок і національних кордонів входять такі основні етапи: 1°. Знаходять вирішення завдання лінійного програмування (1)-(3). 2°. Становлять додаткових обмежень до котроїсь із пере-менных, значення в оптимальному плані завдання (1)-(3) є дробовим числом. 3°. Знаходять вирішення завдань (I) і (II), які виходять з завдання (1)-(3) внаслідок приєднання додаткових обмежень. 4°. У разі потреби становлять додаткових обмежень для перемінної, значення є дробовим, формулюють завдання, аналогічні завданням (I) і (II), і знаходять їхнє рішення. Итерационный процес продовжують до того часу, поки що не знайдено вершина, відповідна целочисленному плану завдання (1)-(3) і такі, що значення функції у цій вершині більше або одно значенням функції за іншими можливих для розгалуження вершинах. Описаний вище метод гілок і національних кордонів має як просту логічний схему розрахунків, ніж метод Гомори. Тож у вона найчастіше перебування вирішення конкретних завдань целочисленного програмування з допомогою ЕОМ застосовується саме такий метод.

Проілюструємо метод гілок і національних кордонів на примере.

Вирішити задачу.

Z = Зх1 + х2 — max.

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

4xl + Зх2 < 18, x1 + 2×2 (6,.

0 (x1 (5,.

0 (x2 (4, х1, x2 — цілі числа. Рішення. За нижню межу лінійної функції приймемо, наприклад, його значення у точці (0,0), тобто. Z0 = Z (0; 0) = 0. I етап. Вирішуючи завдання симплексным методом, одержимо Zmax = 13 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); оскільки перша компонента х1* подрібнена, те з області рішення виключається смуга, що містить дробове оптимальне значення х1*, тобто. 4 < х1 < 5. Тому завдання 1 розбивається на два завдання 2 і 3:

Завдання 2.

Z=3×1+x2>max.

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

4xl + Зх2 < 18×1 + 2×2 (6.

0 (x1 (4.

0 (x2 (4×1, x2 — цілі числа.

Завдання 3.

Z=3×1+x2>max.

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

4xl + Зх2 < 18×1 + 2×2 (6.

5 (x1 (5.

0 (x2 (4×1, x2 — цілі числа.

Список завдань: 2 і трьох. Нижню межу лінійної функції не змінилася: Z0= 0. II етап. Вирішуємо (за вибором) одне з завдань списку, наприклад завдання 3 симплексным методом.

Одержимо, що умови завдання 3 противоречивы.

III етап. Вирішуємо завдання 2 симплексным методом. Одержимо Zmax = 14/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хоча Z (X3*) = 14/3 > Z0 = 0, як і зберігається Z0 = 0, бо план нецелочисленный. Оскільки х2* — дробове число, в галузі рішень виключаємо смугу 0 < x2 < 1 і завдання 2 розбиваємо на два завдання 4 і 5.

Завдання 4.

Z=3×1+x2>max.

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

4xl + Зх2 < 18×1 + 2×2 (6.

0 (x1 (4.

0 (x2 (0×1, x2 — цілі числа. Завдання 5.

Z=3×1+x2>max.

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

4xl + Зх2 < 18×1 + 2×2 (6.

0 (x1 (4.

1 (x2 (4×1, x2 — цілі числа.

Список завдань: 4 і п’яти. Значення 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* — дробове, в галузі рішень виключаємо смугу 3max.

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

4xl + Зх2 < 18×1 + 2×2 (6.

4 (x1 (4.

1 (x2 (4×1, x2 — цілі числа. Список завдань: 6 і аналогічних сім. Значення 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. Неважко бачити, кожна наступна завдання, составляемая в ході застосування методу гілок і національних кордонів, відрізняється від попередньої лише одним нерівністю — обмеженням. Тому, за рішенні кожної наступної завдання немає сенсу вирішувати її симплексным методом від початку (з I кроку). А доцільніше розпочати рішення з останнього кроку (ітерації) попередньої завдання, із системи обмежень якої виключити «старі «(одне або двоє) рівняння — обмеження і введення у цю систему «нові «рівняння — ограничения.

3.Применение методу гілок і національних кордонів для завдань календарного планирования.

Метод гілок і національних кордонів універсальний методом рішення комбінаторних завдань дискретного програмування. Складність практичного застосування методу залежить від труднощі перебування способу розгалуження безлічі на підмножини і обчислення відповідних оцінок, які залежить від специфіки конкретної задачи.

Розглянемо застосування різновиду методу гілок і національних кордонів— методу «послідовного конструювання та якісного аналізу варіантів» на вирішення завдання календарного планування трьох станков.

Задано п деталей di (і = 1, 2, …, n), послідовно оброблюваних на трьох верстатах R1, R2, R3, причому технологічні маршрути всіх деталей однакові. Означимо ai, bi, ci — тривалість обробки деталей di першою, другому й третьому верстатах соответственно.

Визначити таку черговість запуску деталей в обробку, коли він мінімізується сумарне час всіх робіт Tц.

Можна показати, що у завданню трьох верстатів черговість виконання перших, других і третіх операцій на оптимальному рішенні то, можливо однаковою (для чотирьох верстатів це властивість не виконується). Тому досить визначити черговість запуску одному верстаті (наприклад, третьем).

Означимо (k = (i1, i2, …, ik) — деяку послідовність черговості запуску довжиною k (1 (k (п) і A ((k), У ((k), З ((k) — час закінчення обробки послідовності деталей (k першою, другому й третьому верстатах соответственно.

Необхідно відшукати таку послідовність (опт, что.

С ((опт) = min З (().

(.

Покажемо, як і рекуррентно вираховуватимуть A ((k), У ((k), З ((k). Нехай (k+1 = ((k, ik+i), т. е. послідовність деталей (k+1 отримана з деталей (k з додаванням ще з однією деталі ik+1. Тогда.

A ((k+1) = A ((k)+[pic],.

У ((k+1) = max [A ((k+1); У ((k)] + [pic],.

З ((k+1) = max [У ((k+1); З ((k)] +[pic] Для завдання трьох верстатів можна використовувати таке правило домінування .

Якщо (— деяка початкова послідовність, а [pic] — під послідовність освічена з (перестановкою деяких символів, то варіант (домінує над [pic], коли виконуються такі неравенства:

А (() (А ([pic]), У (() (У ([pic]), З (() (С.

([pic]),.

причому хоча одне їх виконується, як суворе нерівність. Спосіб конструювання варіантів после;

довательностей (і обчислення оцінок ((() кожного з них ось у чому. Нехай є початкова подпоследовательность (. Тоді обчислюються величины:

(З (() = З (() +[pic], (1).

(B (() = У (() +[pic] + min cj, (2).

(A (() = A (() +[pic] + [pic] (3) де J (() — безліч символів, їхнім виокремленням послідовність (.

За оцінку критерію З (() для варіанта (можна взяти величину.

((() = max {(A ((), (B ((), (З (()}. (4) Тоді хід виконання завдання трьох верстатів можна наступній формальної схемой.

Нульовий крок. Завдання безлічі G (0), утворюється всілякими послідовностями ((= 0). Обчислення оцінки для безлічі G0: де ((0) = max {(A (0), (B (0), бC (0)},.

[pic]; [pic]; [pic].

Перший шаг. Образование множин G1(1) U G1(2) U… …G1(n).

Підмножина Gk визначається усіма послідовностями з початком ik (k — 1, …, n).

Обчислення оцінок. Оцінку для послідовності (k визначають з співвідношення (4), т. е.

(((k) = max {(A ((k), (B ((k), (З ((k)}; k = 1, n.

Вибір варіанти продовження. З усіх подпоследовательностей, побудованих попередньому кроці, вибирають найбільш перспективну послідовність (k з найменшої оцінкою, т. е.

(((k (1))=min (((j (1)).

Галуження. Вибравши найперспективніший варіант послідовності (k (1), розвивають його побудовою всіх можливих подпоследовательностей довжиною 2 з початком (k (1) виду (k+1(2)= ((k (1), j), де j не входить у (k.

Обчислення оцінок роблять у відповідність до співвідношеннями (1), (2), (3). k — ш, а р. Припустимо, що вони проведено k кроків, у результаті побудовано варіанти (1(k), (2(k) ,…,(vk (k), саме подпоследовательности довжиною k.

Вибираємо найперспективніший варіант (S (k) такий, что.

(((s (k))=min (((j (k)).

Безліч Gs (k) розбиваємо на (п — k) підмножин, кожна з яких утворюється додаванням до послідовності (s (k) деякого елемента ik+1 такого, що ik+1[pic].

Оцінка [pic] визначається відповідність до співвідношеннями (1) — (4).

Через війну будуємо дерево варіантів наступного виду: вершина Про відповідає (= 0, вершини першого рівня G1(1), G2(1)…, Gn (1) відповідають послідовностям довжиною 1, т. е. (1(1) = 1, (2(1) = 2,…, (n (1) = п тощо. буд. Кожна кінцева вершина відповідає послідовності максимальної довжини п.

Ознака оптимальності. Якщо (v (n) відповідає кінцевої вершині дерева, причому оцінка [pic] найменша з оцінок всіх вершин, то (v (n) — шуканий варіант, інакше переходимо продовження варіанта з найменшої оценкой.

Приклад 6. Розглянемо завдання. трьох верстатів, умови якій наведено в табл. 1:

Таблиця 1 |Тривалість |Деталь | |операцій | | | |1 |2 |3 |4 |5 | |ai |2 |5 |1 |3 |3 | |bi |3 |2 |1 |4 |5 | |ci |4 |4 |2 |2 |2 |.

Нульовий крок. (= 0.

(A ((= 0) = A (0) + [pic] + [pic] = 0 + 14 + 3 = 17;

(B ((= 0) = В (0) + [pic] + min cj = 0 + 15 + 2 = 17;

(З ((= 0) = С (0) + [pic]=14 .

Тогда.

? ((= 0) = max {17, 17,14} = 17.

Перший крок. Констатуємо всіх можливих послідовності довжиною 1.

(1(1) = 1; (2(1) = 2; (3(1) = 3; (4(1) = 4; (5(1) = 5.

Находим.

(A (1) = A1 + [pic] + [pic] = 14 + 3 = 17;

(B (1)((= 0) = В1 + [pic] + [pic] = 5 + 12 + 2 = 19;

(C (1) = С1 + [pic]= 9 + 10 = 19 .

Звідки? (1) = max {17, 19, 19} = 19.

Аналогічно визначаємо? (2),? (3),? (4),? (5).

[pic].

Другий крок. Серед сили-силенної подпоследовательностей довжиною 1, (1(1) = 1, (2(1) = 2,…, (5(1) = 5 вибираємо найбільш перспективну (= 1, на яку величина оценки-прогноза? (() виявляється найменшої. Далі розвиваємо її, конструюючи можливі варіанти довжиною 2, т. е. (1.2), (1.3), (1.4), (1.5).

До кожного з цих варіантів знову визначаємо оцінки за формулам (1) — (4).

Процес обчислень продовжуємо аналогично.

Процес побудови дерева варіантів наведено на рис. 1.

Кожній кінцевої вершині дерева варіантів відповідатиме повна послідовність (= i1, i2,.in. Якщо деякою такий вершини величина оцінки? (() не перевершує величини оцінок ж для решти вершин, ця оцінка визначає шуканий оптимальний варіант. Інакше розбиваємо перспективніший варіант, із найкращою оценкой.

Кінцева вершина визначає варіант (послідовність) [pic] = 3, 1, 5, 2, 4 з найкращого оцінкою? = 20. Тому цей варіант оптимальным.

Безпосередньою перевіркою переконуємося, що час обробки всієї послідовності деталей при цьому варіанта збігається з значенням оценки-прогноза і є минимальным:

[pic].

Летература.

1)Зайченко Ю. П., «Дослідження операцій», Київ «Вищу школу» 1975 г.

2)Акулич И.Л., «Математичне програмування в прикладах і задачах»,.

Москва «У ысшая школа» 1993 г.

3)Кузнецов Ю.Н., Кузубов В.І., Волощенко Г. Б. «Математичне програмування», Москва «У ысшая школа» 1980 г. ———————————;

††††††††††??

[pic].