Курсовая работа: Рішення задач цілочисленного програмування

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

Доведена теорема й наслідок з її показують принципову можливість заміни рішення задачі типу (£^ц , 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) – задачі (11–14). Нехай x(£, C) – її оптимальне рішення. Проаналізуємо координати x(£, C) на цілочисленність. Якщо всі координати вектора x(£, C) цілі, то x(£, C) = x(£^ц , C). Якщо хоча б одна координата, нехай x_i , буде нецілої, надійдемо в такий спосіб.

Позначимо через N сукупність небазисних змінних і на підставі останньої симплексної таблиці запишемо розкладання x_i по небазисним змінним x_i , jÎN

(16)

Тому що x_i – неціла величина, позначимо найближче ціле число, що не перевершує x_i , через [x_i ] і визначимо дробову частину: {x_i }= x_i - [x_i ]. Очевидно, (x_i )>0.

Покажемо, що по i-і рядку симплексної таблиці (?, C) - задачі (у якій коштує неціла координата рішення) можна визначити додаткове лінійне обмеження, що володіє властивостями правильності.

Теорема. Нехай - припустиме рішення (£^ц , C) – задачі, тоді співвідношення

, (17)

, - ціле,

визначають правильне відсікання.

Доказ.

Запишемо вираження (16) у вигляді: