Фінансової академії при Уряді РФ
КАФЕДРА МТЕМАТІКІ
Курсова робота тема:
Застосування методу гілок і меж для задач календарного планування
Студент групи МЕК 1-1 Клейменов І.Д.
Науковий керівник Солодовников А.С.
МОСКВА, 2001р.
План < p> 1.Постановка завдання цілочисельного програмування 3
2. Поняття про метод гілок і меж 4
3.Прімененіе методу гілок і меж для задач календарного планування
13
Летература 20
1 . Постановка завдання цілочисельного програмування
За змістом значної частини економічних завдань, що відносяться до завданьлінійного програмування, компоненти рішення повинні виражатися в цілихчислах, тобто бути цілочисельними. До них належать, наприклад, завдання, вяких змінні означають кількість одиниць неподільної продукції, числоверстатів при завантаженні устаткування, число судів при розподіли полініях, кількість турбін в енергосистемі, число обчислювальних машин укеруючому комплексі та багато інших.
Задача лінійного цілочисельного програмування формується наступнимчином: знайти таке рішення (план) X = (x1, x2 ,..., xn), при якомулінійна функція
(1) приймає максимальне або мінімальне значення приобмеження
= 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 не задовольняє умовіцілочисельності змінних, тим самим вважаємо, що серед його компонент єдробові числа. Нехай, наприклад, мінлива прийняла в плані X0 дробовезначення. Тоді в оптимальному цілочисельне плані її значення буде поПринаймні або менше або рівне найближчого меншого цілого числа,або більше або дорівнює найближчого більшого цілого числа + 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 + 2x2 (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 = 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 = < br>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 Завдання 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 * --дробове, з області рішень виключаємо смугу 3max
при обмеженнях:
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 Отже, список завдань вичерпаний і оптимальним целочисленным рішенням вихідної задачі буде X * = Х4 * = (4; 0; 2; 2 ; 0; 0), а оптимум лінійної функції
Zmax = 12
Зауваження 1. Неважко бачити, що кожна наступна задача, що складається впроцесі застосування методу гілок і меж, відрізняється від попередньої лишеодним нерівністю - обмеженням. Тому при вирішенні кожної наступноїзавдання немає сенсу вирішувати її симплексним методом з самого початку (з I кроку).
А доцільніше почати вирішення з останнього кроку (ітерації) попередньоїзавдання, із системи обмежень якої виключити "старі" (одне або два)рівняння - обмеження та ввести в цю систему "нові" рівняння --обмеження. 3.Прімененіе методу гілок і меж для задач календарного планування
Метод гілок і меж є універсальним методом рішення комбінаторних задач дискретного програмування. Складність практичного застосування методу полягає в труднощах знаходження способу розгалуження множини на підмножини і обчислення відповідних оцінок, які залежать від специфіки конкретного завдання.
Розглянемо застосування різновиди методу гілок і меж-методу
«послідовного конструювання та аналізу варіантів »для вирішення задачі календарного планування трьох верстатів.
задані п деталей di (i = 1, 2, ..., n), послідовно обробляються на трьох верстатах R1, R2, R3, причому технологічні маршрути всіх деталей однакові. Позначимо ai, bi, ci - тривалість обробки деталей di на першому, другому і третьому верстатах відповідно.
Визначити таку черговість запуску деталей в обробку, при якій мінімізується сумарний час завершення всіх робіт Tц. < p> Можна показати, що в задачі трьох верстатів черговість виконання першого, другого і третього операцій в оптимальному рішенні може бути однаковою (для чотирьох верстатів це властивість вже не виконується). Тому досить визначити черговість запуску тільки на одному верстаті
(наприклад, третьому).
Позначимо (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 )+,
У ((k +1) = max [A ((k +1 ); У ((k)] +,
З ((k +1) = max [В ((k +1); З ((k)] +
Для завдання трьох верстатів можна використовувати наступне правило домінування.
Якщо (- деяка початкова послідовність, а - під послідовність утворена з (перестановкою деяких символів, то варіант (домінує над, коли виконуються наступні нерівності:
А ( () (А (), В (() (В (), С (() (С
(),
причому хоча б одне з них виконується як суворе нерівність.
Спосіб конструювання варіантів після-
послідовно (і обчислення оцінок ((() для кожного з них полягає в наступному.
Нехай є початкова подпоследовательность (. Тоді обчислюються величини: < p> (C (() = С (() +, (1)
(B (() = У (() + + min cj, (2)
( A (() = A (() + + (3) де J (() - безліч символів, що утворюють послідовність (.
За оцінку критерію З (() для варіанта (можна прийняти величину
((() = max ((A ((), (B ((), (C (()}. (4)
Тоді хід розв'язання задачі трьох верстатів можна представити наступною схемою формальної.
Нульовий крок. Завдання безлічі G (0), утворюється усіма можливими послідовностями ((= 0).
Обчислення оцінки для безлічі G0: де ((0) = max ((A (0), (B (0), бC (0 )},
;;.
Перший шаг.Образованіе множин G1 (1) U G1 (2) U. .. ... G1 (n) .
Підмножина Gk визначається всіма послідовностями з початком ik (k - 1, ..., n).
Обчислення оцінок. Оцінку для послідовності (k визначають зі співвідношення (4), тобто
(((k) = max ((A ((k), (B ((k), (C ((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 )). < p> Безліч Gs (k) розбиваємо на (п - k) підмножин, кожне з яких утворюється додаванням до послідовності (s (k) деякого елемента ik 1 такого, що ik 1.
Оцінка визначається в Відповідно до співвідношеннями (1) - (4).
У результаті будуємо дерево варіантів такого вигляду: вершина Про відповідає (= 0, вершини першого рівня G1 (1), G2 (1 )..., Gn (1) відповідають послідовностей довжиною 1, тобто (1 (1) = 1, (2 (1) =
2 ,..., (n (1) = п і т. д. Кожна кінцева вершина відповідає послідовності максимальної довжини п.
Ознака оптимальності. Якщо (v (n) відповідає кінцевій вершині дерева, причому оцінка найменша з оцінок всіх вершин, то (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) + + = 0 + 14 + 3 = 17;
(B ((= 0) = В (0) + + min cj = 0 + 15 + 2 = 17;
(C ((= 0) = С (0) + = 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 + + = 14 + 3 = 17;
(B (1) ((= 0) = В1 + + = 5 + 12 + 2 = 19;
(C (1) = С1 + = 9 + 10 = 19.
Звідки? (1) = max (17, 19, 19) = 19.
Аналогічно визначаємо? (2),? (3),? (4),? (5).
Другий крок. Серед безлічі подпоследовательностей довжиною 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. Якщо для деякої такої вершини величина оцінки? (() не перевищує величини оцінок для всіх інших вершин, то ця оцінка визначає шуканий оптимальний варіант. Інакше розбиваємо більш перспективний варіант з найкращою оцінкою.
Кінцева вершина визначає варіант (послідовність) = 3,
1, 5, 2, 4 з найкращою оцінкою? = 20. Тому цей варіант є оптимальним.
Безпосередньою перевіркою переконуємося, що час обробки всієї послідовності деталей для цього варіанту таке саме, як оцінки-прогнозу і є мінімальним:
Летература
1) Зайченко Ю. П., « Дослідження операцій », Київ« Вища школа »1975р.
2) Акулич І.Л.,« Математичне програмування в прикладах і завданнях »,
Москва« У исшая школа »1993р.
3) Кузнєцов Ю. М., Кузубов В.І., Волощенко А.Б. «Математичне програмування», Москва «У исшая школа» 1980р.
-----------------------
† † † † † † † † † †??
