Перший алгоритм Гоморі

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

1. Розв’язування задачі симплекс-методом, не враховуючи вимоги цілочисловості.

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

3. Складання додаткового обмеження-умови:

– знаходиться дрібова частина вільного члена для всіх рядків

,

де – ціла частина числа , але менша від самого числа , тобто , наприклад,

– вибирається такий -й рядок, для якого

– знаходяться дрібові частини коефіцієнтів як

– складається додаткове обмеження згідно з формулою

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

4. Доповнення початкової математичної моделі задачі додатковим обмеженням, перетворення її до простого виду (якщо це можливо) та перехід до п.1 алгоритму для розв’язування побудованої моделі симплекс-методом.

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

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

Це цілком очевидно, якщо додаткове обмеження звести до нерівності типу „ ”, а потім до строгого рівняння за допомогою додаткової змінної .

Побудовану таким чином симплекс-таблицю продовжують розв’язувати двоїстим методом, причому у першу чергу з базису виводиться змінна , тому що для цього рядку .

Знаходження розв’язку цілочислової задачі першим алгоритмом Гоморі показано блок-схемою на рис.7.3.

 

Приклад

Знайти цілочисловий розв’язок наступної математичної моделі:

та -цілочислові.

		Оптимальний варіант

 

так

 

ні

 

 

Знаходження по i 0-му рядку

так

 

 

ні

 

 

Рис.7.3

 

Стандартна форма моделі

 

та -цілочислові.

Розв’язування задачі симплекс-методом і знаходження оптимального нецілочислового розв’язку у такій симплекс-таблиці:

 

			-2
		3/2			1/2	-1/2
-2		7/2			1/2	1/2
			-1/2	-3/2

 

Обчислювання дрібових частин величин :

Ці частини у нашому випадку однакові, тому можна зробити вибір будь-якого з цих рядків, наприклад, перший, та скласти додаткове обмеження:

 

Тоді

.

Це обмеження перетворюється на рівняння так, щоб змінна була базисною:

та

.

Цим рівнянням доповнюється симплекс-таблиця оптимального неціло-числового розв’язку:

			-2
		3/2			1/2	-1/2
-2		7/2			1/2	1/2
		-1/2			-1/2	3/2
			-1/2	-3/2

 

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

			-2
-2
						-3	-2
				-3	-1

Наслідок розв’язку задачі:

 

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

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

IV. Циклдік оператор алгоритмдерін программалау
V. Алгоритм эффективной консультации и последующих приемов
V.ПРИКЛАДИ ЗАСТОСУВАННЯ АЛГОРИТМУ ЕВКЛІДА ДО РОЗВ’ЯЗУВАНЯ ДІОФАНТОВИХ РІВНЯНЬ.
VI. Алгоритм решения задач
X. Алгоритмы мотивации пациента к приобретению стоматологических услуг.
А) Зразок індивідуального програмованого завдання: (алгоритм вироблення навичок та вмінь)
А) орёл ; б) алгоритм ; ) л
Алгебраические алгоритмы реконструкции
Алгоритм (закон) регулирования
Алгоритм Бойера-Мура

Воспользуйтесь поиском по сайту: