Методичні вказівки

Задача про завантаження - це задача про раціональне завантаження судна (літака, автомашини і т.п.), що має обмеження по обсязі вантажопідйомності. Кожен поміщений на судно вантаж приносить визначений прибуток. Завдання полягає у визначенні завантаження судна такими вантажами, що приносять найбільший сумарний прибуток.

Рекурентне рівняння процедури зворотного прогону виводиться для загальної задачі завантаження судна вантажопідйомністю W предметів (вантажів) n найменувань. Нехай m_i - кількість предметів i-го найменування, що підлягають завантаженню, r_i - прибуток, що приносить один завантажений предмет i-го найменування, w_i - вага одного предмета i-го найменування. Загальна задача має вид наступної цілочисельної задачі лінійного програмування.

М аксимізувати

за умови, що

та цілі

Три елементи моделі динамічного програмування визначаються в такий спосіб.

1. Етап i ставиться у відповідність предмету i-го найменування, i = 1,2,п.

2. В аріанти рішення на етапі i описуються кількістю m_i- предметів i-го найменування, що підлягають завантаженню. Відповіднbq прибуток дорівнює r_im_i. Значення m_i належить інтервалу від 0 до - ціла частина числа

3. Стан х1 на етапі і виражає сумарну вагу предметів, рішення про навантаження яких прийняті на етапах і, і+1, n. Це визначення відображають той факт, що обмеження ваги є єдиним, котре зв'язує п етапів разом.

Припустимо f_i(х_i) - максимальний сумарний прибуток від етапів і, і+1, n при заданому стані x_i. Простіше всього рекурентне рівняння визначається за допомогою наступної процедури.

Крок 1. Виражають f_i(х_i) як функцію / f_i+1(х_i+1) у виді процедури

.

де

К рок 2. Виразимо х_i+1 як функцію х_i для гарантії того, що ліва частина останнього рівняння є функцією лише х_i. По визначенню х_i- х_i+1 являє собою вага, завантажена на етапі і, тобто або . Отже, рекурентне рівняння:

Задача про завантаження є типовим представником задачі розподілу ресурсів, у якій обмежений ресурс розподіляється між кінцевим числом видів (економічної) діяльності. При цьому метою є максимізація відповідної функції прибутку. У таких моделях визначення стану на кожному етапі буде аналогічно приведеному для задачі про завантаження: станом на етапі і є сумарна кількість ресурсу, що розподіляється на етапах і, і+1,n.

Контрольні питання:

1. Особливість моделі рюкзака?

2. Методи вирішення задач рюкзачного типу? 3. Наведить приклади можливого використання у реальному житті.

Література [1,5]

Практична робота 21. Комбінаторне програмування

Мета: навчитись використовувати метод гілок та границь

Задача

Дані пр..роботи №6 (симплекс-метод)

Завдання

Знайти оптимальне значення цільової функції та значення параметрів оптимізаціїї за умовою їх цілочисельності.

Методичні вказівки

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

Розглянемо один із комбінаторних методів. Для розв’язування задач цілочислового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв’язується послаблена (без умов цілочисловості) задача. Потім вводиться правило перебору.

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

 цілих значень немає.

Тобто допустиме ціле значення x_j має задовольняти одну з нерівностей виду:

 або  .

Дописавши кожну з цих умов до задачі з послабленими обмеженнями, отримують дві, не пов’язані між собою, задачі. Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:

перша задача: 

за умов:

— цілі числа,  ;

, (6.18)

друга задача

за умов:

, 

 

— цілі числа 

д е   — дробова компонента розв’язку задачі.

Наведені задачі спочатку послаблюють, тобто розв’язують з відкиданням обмежень Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками основної задачі. Інакше пошук розв’язку задачі триває. Для подальшого розгалуження вибирають розв’язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки — з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв’язку. Здобутий останній план — оптимальний.

Розв’язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв’язування відрізняється від попередньої лише одним обмеженням. Тому за послідовного розв’язування задач немає сенсу розв’язувати їх симплексним методом спочатку. Досить буде почергово приєднати нові обмеження виду до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) непотрібні «старі» обмеження.

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

Припустимо, що А — точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими   та  +1, що виключає з розгляду точку А, координата якої   є не цілим числом.

Алгоритм методу гілок та меж:

• Симплексним методом розв’язують основну задачу (без вимог цілочисловості змінних).

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

Якщо задача не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача також не має розв’язку.

• Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних   і визначають її цілу частину  .

• Записують два обмеження, що відтинають нецілочислові розв’язки:

,

.

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

• У будь-якій послідовності розв’язують обидві задачі. У разі, коли отримано цілочисловий розв’язок хоча б однієї із задач, значення цільової функції цієї задачі зіставляють з початковим значенням. Якщо різниця не більша від заданого числа e, то процес розв’язування може бути закінчено. У разі, коли цілочисловий розв’язок одержано в обох задачах, то з розв’язком початкової зіставляється той, який дає краще значення цільової функції. Якщо ж в обох задачах одержано нецілочислові розв’язки, то для дальшого гілкування вибирають ту задачу, для якої здобуто краще значення цільової функції і здійснюють перехід до кроку 2.