Рішення задач цілочисленного програмування
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?ленності змінних і такий, що оптимальні рішення вихідної (ц, 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).
Методи, засновані на використанні процедури побудови правильних відсікань, одержали назву методів відсікання.
3. Перший алгоритм Гомори
Випливаючи загальній схемі методів відсікання, вирішимо (, C) задачу (11, 12, 14), що відповідає (ц, C) задачі (1114). Нехай x(, C) її оптимальне рішення. Проаналізуємо координати x(, C) на цілочисленність. Якщо всі координати вектора x(, C) цілі, то x(, C) = x(ц, C). Якщо хоча б одна координата, нехай xi, буде нецілої, надійдемо в такий спосіб.
Позначимо через N сукупність небазисних змінних і на підставі останньої симплексної таблиці запишемо розкладання xi по небазисним змінним xi, jN
(16)
Тому що xi неціла величина, позначимо найближче ціле число, що не перевершує xi, через [xi] і визначимо дробову ?/p>