По дисципліні «дослідження операцій» icon

По дисципліні «дослідження операцій»




НазваПо дисципліні «дослідження операцій»
Сторінка2/5
Дата26.06.2012
Розмір0.83 Mb.
ТипКонспект
1   2   3   4   5

^ МЕТОД ГІЛОК І ГРАНИЦЬ ДЛЯ розвязування ЦЗЛП

Уперше метод гілок і границь стосовно до ЗЦЛП був запропонований в 1960 р. у роботі Ленда й Дойга. Однак, запропонований підхід не зробив істотного впливу на розвиток методів розв’язування задач дискретного програмування.

Фактично друге народження методу гілок і границь пов'язане з роботою Літла, Муті, Суіні й Керела (1963 р.). Ця робота присвячена розв’язуванню задачі комівояжера. Друге народження методу пояснюється тим, що автори відзначили надзвичайну широту методу, вони показали важливість використання специфіки задачі при застосуванні цього методу.

У загальному випадку ЦЗЛП формулюється в такий спосіб: знайти оптимум функції:

; (2.1)

при обмеженнях

(2.2)

(2.3)

(2.4)



Алгоритм методу гілок і границь

1. На множині припустимих планів G0 знаходять оптимальне значення функції цілі (2.1), відкинувши умови цілочисельності (2.4). При цьому знаходять оцінку функції якості

.

Цю оцінку вважають верхньою оцінкою функції якості G0. Якщо план задовольняє умовам цілочисельності, то він вважається оптимальним для ЦЗЛП (2.1)–(2.4).

Якщо ж умови цілочисельності для задачі (2.1)-(2.4) не виконуються, то переходять до пункту два цього алгоритму.

2. Починають розвивати процес розгалуження. Для цього вибирають деяку нецілочисельну компоненту xj = xj0, 1  jn. При цьому множину G0 розбивають на дві непересічні підмножини .

Операцію реалізують у такий спосіб





Для наочності отриманого результату зображують дерево розв’язків.







G0






0 крок







1 крок



































3. На третьому етапі розв’язуються дві задачі лінійного програмування. Одна – на множині , а друга – на множині . При цьому одержують верхню оцінку функції якості на відповідних підмножинах. Якщо розв’язки на множинах і виявляться цілочисельними, то оптимальним для задачі (2.1)–(2.4) буде той план, що дає більшу верхню оцінку функції якості.

Якщо ж, допустимо, на множині одержують цілочисельний план, а на множині – нецілочисельний, причому , то надалі розвивається процедура розгалуження на множині .

4. Далі здійснюють процес розгалуження ОПР і паралельно формують дерево розв’язків. Процес розгалуження реалізують доти, поки не знайдуть той оптимальний план, що задовольняє постановці задачі. Після того, як дерево розв’язків буде сформовано остаточно, аналізують кожну його гілку і знаходять той вектор , що доставляє оптимум функції якості (2.1).


Особливості методу

1. Безпосередньо з алгоритму необхідно, щоб метод гілок і границь застосовувався як для задач повністю цілочисельного програмування, так і для задач частково цілочисельного програмування.

2. Для даного методу несуттєва проблема помилок округлення.

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




4. Нові обмеження виду , відіграють роль розсічень ОПР.

5. Коли вводять нові обмеження зазначеного типу, то немає необхідності розв’язувати ЗЛП заново, а можна скористатися попередньою ітерацією, уводячи нові обмеження. Розглянемо приклад.

Приклад. Вирішити ЦЗЛП методом гілок і границь.










Зобразимо ОПР задачі.




Визначимо координати точки А.

Для цього розв’язується система рівнянь, використовуються формули Крамера:

 = –9; 1 = –39; 2 = –24;



Таким чином, F(А) = F (13/3, 8/3) = 7.

Визначимо координати точки В.



Таким чином, F(В) = F (40/9, 23/9) = 7.

Процедура розгалуження здійснюється відповідно до співвідношень



Вихідна задача розпадається на дві:

Перший крок

1 задача 2 задача







Ця задача несумісна



Другий крок

Розгалуження здійснюємо по змінній х2.



1 задача 2 задача











Отриманий план не є цілочисельним


Третій крок

Розгалуження здійснюємо в першій задачі по змінній х1.






Четвертий крок

Розгалуження здійснюємо по змінній х1 задачі другого кроку.



1 задача 2 задача







Ця задача несумісна.

Дерево розв’язків




^ 3. ДРОБово - ЛІНІЙНЕ ПРОГРАМУВАННЯ (ДЛП)

Загальна постановка задач дробово-лінійного програмування (ЗДЛП)

Постановка ЗДЛП складається у визначенні оптимального значення функції:

(3.1)

при обмеженнях виду:

. (3.2)

Крім того, на змінні накладаються умови невід’ємності

. (3.3)

Очевидно, що в області невід’ємних значень змінних х.

Як і у випадку ЗЗЛП цільова функція (3.1) досягає свого оптимального значення в одній з вершин гіперопуклого багатогранного тіла. ОПР у цілому ЗДЛП визначається обмеженнями виду (3.2)-(3.3).

Очевидно, що якщо задача (3.1)–(3.3) має одну або дві змінні, то її можна розв’язувати в площині Х10Х2 графічно.


^ 3.1. ГРАФІЧНИЙ МЕТОД розвязування ЗДЛП

Постановка задачі

Необхідно знайти экстремум наступної функції (3.4), при обмеженнях виду:

(3.5)

і умовах невід’ємності, що накладають на змінні:

. (3.6)

Аналіз задачі (3.4)-(3.6)

1. Областю припустимих розв’язків задачі (3.4)–(3.6) служить або замкнуте опукле багатогранне тіло або розімкнуте опукле багатогранне тіло. Таке тіло визначається системою обмежень (3.5) і умовами невід’ємності (3.6), які накладаються на змінні х1, х2.

2. Функція (3.4) визначає в площині Х10Х2 сімейство прямих, що проходять через початок координат. Таке сімейство прямих описується рівняннями виду:

.

3. Обертаючи пряму (3.4) відносно початку координат, можна знайти ту вершину ОПР, в якій функція (3.4) досягає свого оптимального значення (якщо таке значення існує). Крім того, при обертанні такої прямої можна переконатися в нерозв'язності задачі (3.4)-(3.6).

Алгоритм розв’язування задачі (3.4)-(3.6)

1. У площині Х10Х2 будуємо область припустимих розв’язків задачі, що визначається співвідношеннями (3.5)–(3.6). Помітимо, що якщо така область замкнута, то задача (3.4)-(3.6) завжди має рішення.





2. У площині Х10Х2 будуємо пряму лінію з рівнянням .

3. Обертаючи пряму відносно початку координат, визначаємо крайню точку ОПР або переконуємося в нерозв'язності такої задачі.

У розглянутій задачі

4. Далі визначаємо координати точки оптимуму й підставляємо їх у вираз для функції мети.

Розглянемо приклад.

Приклад. Для виробництва двох видів виробів А й В підприємство використовує три типи технологічного встаткування. Кожен виріб повинен пройти обробку на кожному типі встаткування. Час обробки виробу на кожнім устаткуванні наведено в таблиці. Крім того, в таблиці зазначені витрати, пов'язані з виробництвом одного виробу кожного виду

Тип устаткування

Витрати в годинниках на обробку 1 виробу

А

В

I

2

8

II

1

1

III

12

3

Витрати на виробництво 1 вир.

2

3


Підприємство може використати встаткування першого й третього типів не більше 26 й 39 годин відповідно. При цьому встаткування другого типу доцільно використовувати не менше 4 годин. Потрібно визначити, скільки виробів кожного виду варто виготовляти даному підприємству, щоб собівартість кожного виробу була мінімальною.

Сформулюємо задачу математично. Позначимо через х1 і х2 кількість виробів видів А и В відповідно, який повинне виготовляти дане підприємство при мінімальних загальних витратах .

Тоді функція, відповідальна за собівартість одного виробу, визначається співвідношенням:

. (3.7)

Задача розв’язується в рамках наступних обмежень

(3.8)

(3.9)

Висновок:

1) математична постановка задачі складається у визначенні такого невід’ємного розв’язку системи обмежень (3.8), що доставляє мінімум функції (3.7);

2) беручи до уваги, що математична модель (3.7)–(3.9) містить у собі лише дві змінні, задача може бути вирішена графічно в площині Х10Х2.




В силу того, що область замкнута, вихідна ЗДЛП завжди буде мати розв’язок. Зобразимо в площині Х10Х2 рівняння прямої .

Виразимо із цього рівняння х2 :

.

Очевидно, що при збільшенні h кутовий коефіцієнт буде рости (отже, буде збільшуватися й відповідна похідна).

Стрілки на графіку вказують напрямок збільшення h, отже, максимум цільової функції буде досягнутий у точці А, а мінімум – у точці В.

Визначимо координати точки В із системи рівнянь:

. Одержимо .

Отже, оптимальним планом виробництва є план, при якому підприємство буде виготовляти три вироби виду А и один виріб виду В. При цьому собівартість одного виробу складе 2,25 грошових одиниць, тобто




^ Розв’язування задачі в середовищі Mathcad


I




Given










^ ДЕЯКІ ОСОБЛИВОСТІ Розвязування ЗДЛП

ГРАФІЧНИМ МЕТОДОМ

1. ОПР обмежена знизу й зверху







2. Багатогранник розв’язків необмежений, однак на ньому існують точки, у яких цільова функція досягає свого оптимуму






3. Багатогранник розв’язків необмежений, однак один з экстремумов існує






Задача має так званий асимптотичнтй максимум, тобто .

4. Багатогранник розв’язків необмежений, задача має асимптотичні оптимуми







1   2   3   4   5

Схожі:

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconКонтрольні домашні завдання по дисципліні «Дослідження операцій»

По дисципліні «дослідження операцій» iconI. Предмет І задачі дослідження операцій
Навчальний посібник являє собою конспект лекцій для студентів економічних фахів по однойменній дисципліні. У кожній главі розглядаються...
По дисципліні «дослідження операцій» iconПо дисципліні «дослідження операцій»
У ній найбільше чітко реалізуються основні ідеї вивчення математичних дисциплін на економічних спеціальностях|экономичном| – ідеї...
По дисципліні «дослідження операцій» iconТематичнийпла н по видах занять з курсу "Дослідження операцій"
Операція, основні поняття І якості. Прямі та зворотні задачі. Управління операцією, оцінка якості. Математичні моделі операцій. Допустимі...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconЗвіт до лабораторної роботи №5 «Дослідження залежності показників діяльності людини-оператора від структур алгоритмів діяльності та способів виконання операцій»
...
По дисципліні «дослідження операцій» iconПара 6/18/2013
Дослідження операцій в транспортних системах, корп. 4, ауд. 1-7А, Пристінський М. Г., Екзамен
По дисципліні «дослідження операцій» iconМетодичні вказівки щодо виконання контрольної роботи з навчальної дисципліни " дослідження операцій" для студентів заочної форми навчання
Методичні вказівки щодо виконання контрольної роботи з навчальної дисципліни „Дослідження операцій” для студентів заочної форми навчання...
По дисципліні «дослідження операцій» iconПитання з дисциплини «дослідження операцій»
Розподіл капіталовкладень між підприємствами; постановка задачі, функціональні рівняння
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи