Побудова правильного відсікання.

Введемо такі позначення:

– ціла частина числа , найбільше ціле число, яке не перевершує . Наприклад, , , .

– дробова частина числа , , .

Наприклад, , , .

Відсікання Гоморі обирають наступним чином: серед нецілочисельних розв’язків системи обирають компоненту з максимальною дробовою частиною та з відповідного рівняння формують правильне відсікання

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

Приклад 10.


	1/3	5/3	17/3

–2	2/3	34/3	34/3

Розв’язок знайдений, але він не є цілочисельним. Максимальна дробова частина , будуємо додаткове відсікання за першою строкою.

обчислюємо дробові частини

Заносимо додаткове обмеження в таблицю і розв’язуємо двоїстим симплекс-методом.


1/3	5/3	17/3	1/3

–1	–2	–2	–1
2/3	34/3	34/3

Розв’язок є оптимальним і цілочисельним.

Відповідь: .

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

<== попередня сторінка	\|	наступна сторінка ==>
Тема. 2. Задача цілочисельного програмування.	\|	Тема 3. Транспортна задача.

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

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