Рішення задач цілочисленного програмування
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
?астину: {xi}= xi - [xi]. Очевидно, (xi)>0.
Покажемо, що по i-і рядку симплексної таблиці (?, C) - задачі (у якій коштує неціла координата рішення) можна визначити додаткове лінійне обмеження, що володіє властивостями правильності.
Теорема. Нехай - припустиме рішення (ц, C) задачі, тоді співвідношення
,(17)
, - ціле,
визначають правильне відсікання.
Доказ.
Запишемо вираження (16) у вигляді:
Використовуючи для цього вираження формулу (17), одержимо:
або
На підставі припущень теореми про допустимість рішення
(ц, C) задачі xi ціле. Величини [xio], - цілі по визначенню, отже, zi теж ціле.
Отже, zi певне формулою (17), ціле. Доведемо що . Доказ будемо вести від противного. Нехай .-
Це значить, що . По визначенню дробової частини . За умовою теореми x припустиме рішення (ц, C) задачі, тому . Отже,
Тоді повинне виконуватися:
Отже, із припущення заперечності zi, відразу ж одержуємо тобто zi неціле. Оскільки раніше було показано, що zi, певне формулою (17), є цілим, те тим самим ми прийшли до протиріччя. Отже, припущення, що zi < 0, невірне. Теорема доведена.
Наслідок. Будь-яке оптимальне рішення x(, C) (, C) задачі, що не є припустимим рішенням (ц, C) задачі, не задовольняє умові правильного відсікання (17).
Доказ. Нехай х (, C) оптимальне рішення (, C) задачі, xi0 дробове.
Покажемо, що х (, C) не задовольняє умові відсікання. Оскільки план оптимальний, всі небазисні змінні xi, для jN дорівнюють нулю. Тому . З огляду на це, підставимо xio у формулу (17):
zi(x (, C))= {xi0}+0<0,
що суперечить умові незаперечності zi. Наслідок доведений.
Очевидно, що кількість додаткових обмежень буде наростати в міру рішення допоміжних (, C) задач, оптимальні плани яких будуть містити нецілі координати, тобто виникає проблема розмірності.
Р. Гомори запропонував прийом, що дозволяє обмежити розміри розглянутих симплексних таблиць допоміжних задач величиною (n+2) (k+1), де n кількість змінних (, C) задачі, k число небазисних змінних її. Цей прийом ґрунтується на тім, що нас цікавить додаткове обмеження лише як спосіб відсікання нецілочисленного оптимального рішення допоміжної задачі, отриманої на даному кроці, і переходу до наступної задачі.
Послідовність (, C) задач позначимо індексом k=0,1,…,відповідному номеру ітерації в послідовному наближенні до рішення вихідної (ц, C) задачі, і позначимо (k, C). При цьому (0, C) задача відповідає (, C) задачі (задачі без вимоги цілочисленності).
Змінну zi, що визначається додатковим лінійним обмеженням (7) і будується по деякої нецілочисленної координаті оптимального рішення (k, C) задачі (k =0, 1, 2,…)позначимо xn+k+l.
Щоб розмірність послідовності (k, C) задач не зростала, викреслимо із симплекс-таблиці змінну, по якій побудоване додаткове лінійне обмеження.
Після зроблених зауважень перейдемо безпосередньо до викладу обчислювальної схеми.
1. Вирішимо (k, C) задачу (спочатку k = 0) методом послідовного поліпшення плану.
Нехай у базис оптимального рішення ввійшли вектори As1,…,Asm... Параметри останньої симплексної таблиці позначимо через xij:
.
Якщо, всі базисні тридцятилітні оптимального рішення x(k, C) (k, C) задачі цілі, то x(k, C) = x(ц, C). Якщо деяка координата xio оптимального рішення x(k, C) неціла, то перейдемо до п. 2.
2. Якщо серед сукупності координат оптимального рішення x(k, C) є єдина неціла координата, то додаткове лінійне обмеження (17) будується по цій координаті. Якщо нецілих координат в x(k, C) більше однієї, то виберемо координату з найменшим номером. Нехай нею виявилася xi0. Складемо додаткове лінійне обмеження
(18)
(19)
3. Додамо умови (18, 19) до умов (k, C) задачі. Одержимо нову (k+1, C) задачу. Тому що оптимальне рішення x(k, C) (k, C) задачі визначало одну з вершин багатогранника умов, то воно може бути обране в якості первісного опорного рішення для знову отриманої задачі. А це означає, що останню симплексну таблицю (k, C) задачі можна взяти в якості вихідної для (k+1, C) задачі, доповнивши її умовою (18).
Отже, симплексна таблиця для (k+1, C) задачі виходить із останньої симплексної таблиці для (k, C) задачі шляхом облямівки (i+1) й рядком з елементами:
де небазисні змінні (k, C) задачі.
Одержимо нову задачу, змінними якої є . Умови цієї задачі дозволені відносно xsl,…,xsmзмінних і нова змінної xn+k+1, а лінійна форма виражена через небазисні змінні (k, C) задачі. Тому що ми займаємося максимізацією F(x) і рішення х* для (k, C) задачі оптимально, те всі i > 0. Тому процес переходу до нового рішення (k+1, C) задачі не може бути здійснений по методу уточнення плану. У той же час і тому вектор А0 симплексної таблиці не є опорним рішенням для (k+1, C) задачі, тому що рішенням називається вектор, всі координати якого ненегативні й задовольняють умові приналежності області k+l. Тому назвемо отриманий вектор псевдо рішенням задачі (k+1, C) і перейдемо до подальшого перетворення симплекса-таблиці.
Позначимо через k номер псевдо рішення (k, C) задачі; тоді напрямним рядком є i+k+ 1-я рядок, k =0, 1, 2,…... Тому на кожному етапі перетворення таблиці вектор Ai+k+i буде виводитися з таблиці. Можна довести, що через кінцеве число кроків або буде знайдене цілочисленне рішення, або буде виявлена її нерозвязність, а тим самим нерозвязність (ц,