ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Застосування методу гілок і меж для задач календарного планування
         

     

    Кибернетика

    Фінансової академії при Уряді РФ

    КАФЕДРА МТЕМАТІКІ

    Курсова робота тема:

    Застосування методу гілок і меж для задач календарного планування

    Студент групи МЕК 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р.
    -----------------------

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

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати !