Опишіть алгоритм методу гілок та меж.
- Симплексним методом розв’язують задачу (без вимог цілочисловості змінних).
Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей розв’язок є оптимальним планом задачі цілочислового програмування.
Якщо задача з послабленною умовою не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то і вся наша задача з вимогою цілочисельності також не має розв’язку.
- Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних
і визначають її цілу частину 
. - Записують два обмеження, що відтинають нецілочислові розв’язки:
,
.
- Кожну з одержаних нерівностей приєднують до обмежень початкової задачі. В результаті отримують дві нові цілочислові задачі лінійного програмування.
- У будь-якій послідовності розв’язують обидві задачі. У разі, коли отримано цілочисловий розв’язок хоча б однієї із задач, значення цільової функції цієї задачі зіставляють з початковим значенням. Якщо різниця не більша від заданого числа e, то процес розв’язування може бути закінчено. У разі, коли цілочисловий розв’язок одержано в обох задачах, то з розв’язком початкової зіставляється той, який дає краще значення цільової функції. Якщо ж в обох задачах одержано нецілочислові розв’язки, то для дальшого гілкування вибирають ту задачу, для якої здобуто краще значення цільової функції і здійснюють перехід до кроку 2.
Сформулюйте задачу динамічного програмування.
|
|
|
Динамічне програмування являє собою математичний апарат, що дає змогу здійснювати планування багатокрокових керованих процесів, а також процесів, які розвиваються у часі. Поставимо задачу динамічного програмування в загальному вигляді.
Нехай аналізується деякий керований процес, подання якого допускає декомпозицію на послідовні етапи (кроки), кількість яких n задана. Ефективність всього процесу Z може бути подана як сума ефективностей 
окремих кроків, тобто:
,
що має назву адитивного критерію (або як добуток ефективностей окремих кроків у вигляді: 
, що має назву мультиплікативного критерію).
З кожним етапом (кроком) задачі пов’язане прийняття певного рішення, так званого крокового управління 
що визначає як ефективність даного етапу, так і всього процесу в цілому.
Розв’язування задачі динамічного програмування полягає в знаходженні такого управління 
процесом у цілому, яке максимізує загальну ефективність: 
(max ).
Оптимальним розв’язком цієї задачі є управління 
що складається з сукупності оптимальних покрокових управлінь:
і уможливлює досягнення максимальної ефективності:
Дата добавления: 2018-02-18; просмотров: 1305; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!