Навигация
Теоретичні основи методів відсікання
32739
знаков
0
таблиц
2
изображения
2. Теоретичні основи методів відсікання
Запишемо загальну задачу цілочисленного програмування: в області, певної умовами
(11)
(12)
- цілі, 
(13)
максимізувати функцію
(14)
Назвемо для кратності задачу (11–14) (£ц, C) – задачею. Відповідну їй задачу без вимоги цілочисленності змінних, тобто задачу (11, 12, 14) назвемо (£, C) – задачею. Порушимо питання: чи не можна рішення (£ц, C) – задачі одержати шляхом рішення якоїсь спеціальним образом побудованої задачі без вимоги цілочисленності змінних і такий, що оптимальні рішення вихідної (£ц, C) – задачі й задачі без вимог цілочисленності змінних будуть збігатися. Іншими словами: чи не можна добре вивчений апарат рішення задач лінійного програмування пристосувати до рішення цілочисленних задач. Принципова відповідь на це питання дає наступна теорема.
Теорема. Нехай £ – багатогранник, £ц – множина його цілих крапок, R – опукла, лінійна оболонка множини £ц, тоді:
1) R=Rц – цілочисленний багатогранник;
2) Rц = £ц;
3) R* – множина опорних рішень задачі (£ц, C) утримується в багатограннику Rц.
Доказ. Доведемо, що R – цілочисленний багатогранник. За умовою теореми £ – багатогранник, тому множина його цілих крапок (воно позначено через £ц) звичайно. Оскільки R - опукла лінійна оболонка цієї кінцевої множини крапок, R - теж багатогранник.
По самому визначенню опуклої лінійної оболонки, вона містить всі опорні плани множини, на яке вона натягнута, тобто багатогранник R містить всі целочисленные крапки £ц. Тому R – цілочисленний багатогранник. Позначимо його через Rц. Перша частина теореми доведена.
Доведемо, що Rц збігається з £ц. Тому що R – опукла оболонка крапок множини £ц, те £ц ÍRц.
Покажемо, що справедливо також і протилежна нерівність-включення, т.е. RцÍ£ц. Для цього виберемо деякий довільний елемент х°ÎRц. Оскільки Rц містить всі опорні рішення задачі (£ц, C), те х° задовольняє умовам задачі (£ц, C), тобто х°Î£ц. Але оскільки довільний елемент із Rцналежить £ц, те очевидно, що справедливо RцÍ£ц. Зіставляючи протилежні включення RцÍ£ц і £цÍRц доходимо висновку: що £ц=Rц. Друга частина теореми також доведена.
Доказ 3-го пункти теореми є зовсім очевидним. Тому що R* – множина опорних рішень задачі (£ц, C), те R*Í£ц але £ц=Rц, тому R*ÍRц
Теорема доведена.
Наслідком із цієї теореми є той висновок, що оптимальне рішення задачі, областю визначення якої є опукла оболонка, натягнута на область пошуку цілочисленного рішення, збігається з оптимальним рішенням вихідної цілочисленної задачі.
Доведена теорема й наслідок з її показують принципову можливість заміни рішення задачі типу (£ц, C) деякою процедурою побудови й рішення допоміжної задачі типу (£, C), однак не дають алгоритму рішень. До того ж побудова опуклої оболонки множини £ц реальних задач – надзвичайно складна, а часом практично нерозв'язна задача,
В 1954 р. Дж. Данциг висловив ідею про те, що побудова опуклої оболонки цілочисленної області для задачі (£ц, C) можна здійснювати поетапно й вирішувати одержувані при цьому задачі. Однак при цьому виникли питання як будувати обмеження нової задачі і як забезпечити кінцівка процесу.
Відповідь на ці питання був уперше отриманий Р. Гомори, що запропонував алгоритми рішення цілочисленних і. частково цілочисленних задач.
Алгоритм Р. Гомори складається з наступних процедур:
Вирішується (£, C) – задача, що відповідає вихідної (£ц, C) – задачі.
Отримане оптимальне рішення (£, C) – задачі, якщо воно існує, перевіряється на целочисленність. Якщо умова цілочисленності виконується по всім змінним, то оптимальне рішення (£, C) – задачі є оптимальне рішення (£ц, C) – задачі. Якщо умова цілочисленності не виконується хоча б по одній координаті, то переходять до третього етапу. Якщо (£, C) – задача, виявляється нерозв'язної, те (£ц, C) – задача теж рішення не має.
Будується додаткове обмеження, що володіє тим властивістю, що з його допомогою відтинається частина області, у якій утримується оптимальне рішення (£, C) – задачі й не втримується жодного припустимого рішення (£ц, C) – задачі. Процес побудови додаткових обмежень і рішення одержуваних при цьому (£, C) – задач триває доти, поки не одержимо цілочисленного рішення або не переконаємося в нерозв'язності задачі.
При цьому властивості, який повинне володіти кожне з додаткових обмежень при переході від однієї задачі до іншої наступні:
додаткове обмеження повинне бути лінійним, щоб залишатися в області застосовності апарата лінійного програмування;
додаткове обмеження повинне відтинати частина області, у якій не втримується припустимих рішень цілочисленної (£ц, C) – задачі, але є знайдене оптимальне рішення нецілочисленної (£, C) – задачі, тобто обмеження повинне мати властивість правильності, що не дозволяє втратити оптимальне рішення вихідної (£ц, C) – задачі.
Нехай х (£, C) – оптимальне рішення (£, C) – задачі, що є неприпустимим рішенням для (£ц, C) – задачі. Нерівність
(15)
визначає правильне відсікання, якщо задовольняє
а) умові відсікання: x(?, C) задовольняє нерівності (15)
б) умові правильності: будь-яке припустиме рішення задачі (£ц, C), задовольняє нерівності (15).
Методи, засновані на використанні процедури побудови правильних відсікань, одержали назву методів відсікання.
Похожие работы
4 9 0 1 0 3 Р5 0 8 4 -2 0 0 1 4 F 0 -5 -6 0 0 0 Таблиця № 1 – Вихідна симплекс-таблиця Знаходження оптимального розвязку ЗЛП за допмогою с-м включає слідуючі етапи: 1. За вихідною с-т знаходять опорне рішення Кожній с-т відповідає своє опорне рішення. Воно може бути представлене у вигляди вектора Х Розмірніст вектора дорівнює кількості змі ...
... . Механізм переривань забезпечує ефективна взаємодія пристроїв уведення-висновку з мікропроцесором. Переривання цікавлять нас тому, що обробка переривань - це прерогатива програмування на мові асемблера. У високорівневих мовах відсутні засоби роботи з перериваннями на машинному рівні. Переривання звичайно викликаються зовнішніми пристроями. Переривання сигналізує мікропроцесору, щоб він призупинив ...
... рішень, зв’язаних із регулюванням витрат і з питань інвестиційної діяльності підприємства. Отже, управлінський облік це формування інформації для управління витратами з метою підвищення ефективності функціонування підприємства. Причому, відповідно до Закону «Про бухгалтерський облік і фінансову звітність в Україні», підприємства вправі самостійно обирати систему і форми ведення управлінського ...
... ‚ є гіпотезою про закон розподілу. Гіпотеза про те‚ що середні розміри деталей‚ які виготовляються на однотипних‚ паралельно працюючих станках‚ приблизно однакові‚ є гіпотезою про параметри розподілу. Зроблений на основі статистичних даних висновок про те‚ що між кількома генеральними сукупностями або між емпіричним і теоретичним розподілом істотних відмінностей немає‚ називають нульовою ( ...
0 комментариев