• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Метод Гоморі

Нехай маємо задачу цілочислового програмування (6.1)— (6.4). Для її розв'язування можна скористатися ітеративним методом Гоморі. Суть його полягає ось у чому:

1. Знаходять розв'язок послабленої, тобто задачі без вимог цілочисловості змінних — (6.1)—(6.3).

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

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

де символ {} позначає дробову частину числа.

Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що не перевищує даного. Цілу частину числа позначають символом []. Наприклад,

[1,3] = 1; [-1,3] = -2; {1,3} = 1,3 - 1 = 0,3; {-1,3} = -1,3 - (-2) =2 - 1,3 = 0,7.

3. Додаткове обмеження після зведення його до канонічного вигляду і введення базисного елемента приєднується до останньої симплексної таблиці, яка містить умовно-оптимальний план. Здобуту розширену задачу розв'язують, а далі перевіряють її розв'язок на цілочисловість. Якщо він не цілочисловий, то процедуру повторюють, повертаючись до п. 2. Так діють доти, доки не буде знайдено цілочислового розв'язку або доведено, що задача не має допустимих розв'язків у множині цілих чисел.

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

Задача 6.1.Сільськогосподарське підприємство задумало створити сушильний цех на виробничій площі 190м², маючи для цього 100 тис.грн. і можливість придбати устаткування двох типів А і В. Техніко-економічну інформацію про ці два види устаткування подано в таблиці:

Розв'язування. Нехай і — кількість комплектів устатку вання відповідно типу А і В.

Запишемо економіко-математичну модель:

і - цілі.

Розв'язуємо задачу, нехтуючи умовою цілочисловості. Остання симплексна таблиця набере вигляду:

		План

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

Оскільки то додаткове обмеження набирає вигляду

Зведемо його до канонічної форми та введемо штучну змінну:

Приєднавши здобуте обмеження до останньої симплексної таблиці з умовно-оптимальним планом, дістанемо:

		План						-М
	-М						-1
М			М	М	М

Розв'язуючи наведену задачу, остаточно знаходимо цілочисловий оптимальний план:

.

6.4. Метод «віток і меж»

Ефективнішим за метод Гоморі розв'язування задач цілочислового програмування є метод «віток і меж». Спочатку, як і в разі методу Гоморі, розв'язується послаблена (відкиданням умови цілочисловості) задача.

З цією метою застосовується симплексний метод.

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

Наприклад, якщо , дістаємо інтервал (2,3), де, очевидно, немає яке набуває цілого значення.

Значенню відповідає інтервал (-3; -2), де також не існує цілого значення. Отже, допустиме ціле значення має задовольняти одну з нерівностей

або .

Приписавши кожну з цих умов до задачі з послабленими обмеженнями, дістанемо дві не пов'язані між собою задачі. Тобто початкову задачу цілочислового програмування (6.1)—(6.4) розіб'ємо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв'язуватимемо дві такі задачі:

(6.5)

за умов

	(6.6)
	(6.7)
	(6.8)
	(6.9)
	(6.10)

за умов

	(6.11)
	(6.12)
	(6.13)
	(6.14)

де —компонент розв'язку задачі (6.1)—(6.4).

Далі симплекс-методом розв'язуємо послаблені задачі (6.6)— (6.9) і (6.10)—(6.14), тобто з відкиданням обмежень (6.8) і (6.13). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв'язками задачі (6.1)—(6.4). Інакше пошук розв'язку задачі триває. Для подальшого розгалуження беремо задачу з найбільшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки — з найменшим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв'язку. Здобутий план — оптимальний.

Розв'язування цілочислових задач методом «віток і меж» можна значно прискорити, приєднавши обмеження виду (6.9) і (6.14) до останньої симплекс-таблиці не початкової (6.1)—(6.4), а відповідних задач.

Розв'яжемо методом «віток і меж» задачу 6.1.

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

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

1. D) методу мозкового штурму.
2. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
3. I Метод Шеннона-Фано
4. I. Метод рiвних вiдрiзкiв.
5. VII. Нахождение общего решения методом характеристик
6. А. науковий факт, b. гіпотеза, с. метод
7. Автоматизація водорозподілу на відкритих зрошувальних системах. Методи керування водорозподілом. Вимірювання рівня води. Вимірювання витрати.
8. Агрегативна стійкість, коагуляція суспензій. Методи отримання.
9. АгротехнІЧНИЙ метод
10. Адаптовані й специфічні методи дослідження у журналістикознавстві
11. Адміністративні (прямі) методи регулювання.
12. Адміністративні методи - це сукупність прийомів, впливів, заснованих на використанні об'єктивних організаційних відносин між людьми та загальноорганізаційних принципів управління.

Переглядів: 1995