Тема. 2. Задача цілочисельного програмування.

(методичні вказівки № 1358, стор. 31-34)

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

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

Алгоритм методу Гоморі.

1. Розв’язуємо симплекс-методом ЗЛП без умови цілочисельності.

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

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

1) лінійне;

2) відсікає знайдений оптимальний нецілочисельний план;

3) не відсікає жодного цілочисельного плану.

Додаткове обмеження з вказаними особливостями називається правильним відсіканням. Розв’язуємо двоїстим симплекс-методом ЗЛП з додатковим обмеженням.

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

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Двоїста задача	\|	Побудова правильного відсікання.

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.