Рішення задач цілочисленного програмування (стр. 2 из 5)

Доведемо, що 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) – задачі (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) у вигляді:

Використовуючи для цього вираження формулу (17), одержимо:

або

На підставі припущень теореми про допустимість рішення

(£^ц, C) – задачі x_i – ціле. Величини [x_io],

- цілі по визначенню, отже, z_i – теж ціле.

Отже, z_i певне формулою (17), ціле. Доведемо що

. Доказ будемо вести від противного. Нехай .-

Це значить, що

. По визначенню дробової частини . За умовою теореми x – припустиме рішення (£^ц, C) – задачі, тому . Отже,

Тоді повинне виконуватися:

Отже, із припущення заперечності z_i, відразу ж одержуємо

тобто z_i – неціле. Оскільки раніше було показано, що z_i, певне формулою (17), є цілим, те тим самим ми прийшли до протиріччя. Отже, припущення, що z_i < 0, невірне. Теорема доведена.

Наслідок. Будь-яке оптимальне рішення x(£, C) (£, C) – задачі, що не є припустимим рішенням (£^ц, C) – задачі, не задовольняє умові правильного відсікання (17).

Доказ. Нехай х (£, C) – оптимальне рішення (£, C) – задачі, x_i0 – дробове.

Покажемо, що х (£, C) не задовольняє умові відсікання. Оскільки план оптимальний, всі небазисні змінні x_i, для jÎN дорівнюють нулю. Тому

. З огляду на це, підставимо x_io у формулу (17):

z_i(x (£, C))= – {x_i0}+0<0,

що суперечить умові незаперечності z_i. Наслідок доведений.

Очевидно, що кількість додаткових обмежень буде наростати в міру рішення допоміжних (£, C) – задач, оптимальні плани яких будуть містити нецілі координати, тобто виникає проблема розмірності.

Р. Гомори запропонував прийом, що дозволяє обмежити розміри розглянутих симплексних таблиць допоміжних задач величиною (n+2) (k+1), де n – кількість змінних (£, C) – задачі, k – число небазисних змінних її. Цей прийом ґрунтується на тім, що нас цікавить додаткове обмеження лише як спосіб відсікання нецілочисленного оптимального рішення допоміжної задачі, отриманої на даному кроці, і переходу до наступної задачі.

Послідовність (£, C) – задач позначимо індексом k=0,1,…,відповідному номеру ітерації в послідовному наближенні до рішення вихідної (£^ц, C) – задачі, і позначимо (£_k, C). При цьому (£₀, C) – задача відповідає (£, C) – задачі (задачі без вимоги цілочисленності).

Змінну z_i, що визначається додатковим лінійним обмеженням (7) і будується по деякої нецілочисленної координаті оптимального рішення (£_k, C) – задачі (k =0, 1, 2,…)позначимо x_n+k+l.

Щоб розмірність послідовності (£_k, C) – задач не зростала, викреслимо із симплекс-таблиці змінну, по якій побудоване додаткове лінійне обмеження.

Після зроблених зауважень перейдемо безпосередньо до викладу обчислювальної схеми.

1. Вирішимо (£_k, C) – задачу (спочатку k = 0) методом послідовного поліпшення плану.

Нехай у базис оптимального рішення ввійшли вектори A_s1,…,A_sm... Параметри останньої симплексної таблиці позначимо через x_ij:

.