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

--PAGE_BREAK--.
Якщо, всі базисні тридцятилітні <img width=«21» height=«24» src=«ref-1_1542759569-98.coolpic» v:shapes="_x0000_i1088"> оптимального рішення x(Јk, C) (Јk, C) – задачі цілі, то x(Јk, C) = x(Јц, C). Якщо деяка координата xioоптимального рішення x(Јk, C)неціла, то перейдемо до п. 2.

2. Якщо серед сукупності координат оптимального рішення x(Јk, C)є єдина неціла координата, то додаткове лінійне обмеження (17) будується по цій координаті. Якщо нецілих координат в x(Јk, C)більше однієї, то виберемо координату з найменшим номером. Нехай нею виявилася xi0. Складемо додаткове лінійне обмеження
<img width=«195» height=«37» src=«ref-1_1542759667-511.coolpic» v:shapes="_x0000_i1089">        (18)

<img width=«140» height=«24» src=«ref-1_1542760178-254.coolpic» v:shapes="_x0000_i1090">                            (19)
3. Додамо умови (18, 19) до умов (Јk, C) – задачі. Одержимо нову (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачу. Тому що оптимальне рішення x(Јk, C)(Јk, C) – задачі визначало одну з вершин багатогранника умов, то воно може бути обране в якості первісного опорного рішення для знову отриманої задачі. А це означає, що останню симплексну таблицю (Јk, C) – задачі можна взяти в якості вихідної для (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачі, доповнивши її умовою (18).

Отже, симплексна таблиця для (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачі виходить із останньої симплексної таблиці для (Јk, C) – задачі шляхом облямівки (i+1) – й рядком з елементами:
<img width=«95» height=«24» src=«ref-1_1542760432-195.coolpic» v:shapes="_x0000_i1091">

<img width=«143» height=«25» src=«ref-1_1542760627-263.coolpic» v:shapes="_x0000_i1092"> 
де <img width=«23» height=«24» src=«ref-1_1542760890-111.coolpic» v:shapes="_x0000_i1093"> – небазисні змінні (Јk, C) задачі.
<img width=«108» height=«51» src=«ref-1_1542761001-335.coolpic» v:shapes="_x0000_i1094">


Одержимо нову задачу, змінними якої є <img width=«116» height=«24» src=«ref-1_1542761336-202.coolpic» v:shapes="_x0000_i1095">. Умови цієї задачі дозволені відносно xsl,…,xsmзмінних і нова змінної xn+k+1, а лінійна форма виражена через небазисні змінні (Јk, C) – задачі. Тому що ми займаємося максимізацією F(x) і рішення х* для (Јk, C) – задачі оптимально, те всі Di> 0. Тому процес переходу до нового рішення (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачі не може бути здійснений по методу уточнення плану. У той же час <img width=«92» height=«25» src=«ref-1_1542761538-192.coolpic» v:shapes="_x0000_i1096"> і тому вектор Асимплексної таблиці не є опорним рішенням для (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачі, тому що рішенням називається вектор, всі координати якого ненегативні й задовольняють умові приналежності області Јk+l. Тому назвемо отриманий вектор <img width=«128» height=«27» src=«ref-1_1542761730-250.coolpic» v:shapes="_x0000_i1097"> псевдо рішенням задачі (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C)і перейдемо до подальшого перетворення симплекса-таблиці.

Позначимо через k номер псевдо рішення (Јk, C) – задачі; тоді напрямним рядком є i+k+ 1-я рядок, k =0, 1, 2,…… Тому на кожному етапі перетворення таблиці вектор Ai+k+iбуде виводитися з таблиці. Можна довести, що через кінцеве число кроків або буде знайдене цілочисленне рішення, або буде виявлена її нерозв'язність, а тим самим нерозв'язність (Јц, C) – задачі.

Якщо рішення (Јk, C)– задачі завершується побудовою оптимального цілочисленного рішення x*, те m, перших його компонентів визначають рішення цілочисленної задачі; якщо серед координат х* є дробові, те один із дробових компонентів (раніше певним правилом) породжує додаткове обмеження й процес рішення повинен бути продовжений з новим рядком, що облямовує. Рядок, використовуваний раніше для облямівки, викреслюється й більше для побудови розширених задач не відновлюється.

Процедуру рішення (Јk, C) – задачі (k=0, 1,…)і аналізу отриманого рішення назвемо великою ітерацією. Номер великої ітерації збігається з номером розв'язуваної (Јk, C) – задачі.

Результатом великої ітерації є перехід до нового (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачі або закінчення рішення задачі.

Уведемо: 1) осередок i, у якій будемо запам'ятовувати номер рядка, на підставі якої будується чергове додаткове лінійне обмеження, 2) лічильник r, що відповідає номеру проведеної великої ітерації. Позначимо x*(Јr, C)оптимальне рішення (Јr, C) – задачі. Помітимо, що позначення (Јr, C) – задача, еквівалентне (Јr, C), уведено в блок-схемі для зручності запису.

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

Теорема. Нехай множина оптимальних планів задачі (Ј0, C)обмежено й виконуються наступні умови:

1) сi – цілі коефіцієнти цільової функції F(x) (i =1,2,…,n),рядок цільової функції в симплексній таблиці враховується при виборі рядка для побудови правильного відсікання;

2) справедливо одне із двох тверджень: або цільова функція <img width=«52» height=«24» src=«ref-1_1542761980-133.coolpic» v:shapes="_x0000_i1098"> обмежена знизу на Сo, або задача (Јц, C)має хоча б один план х'.

Тоді перший алгоритм Гомори вимагає кінцевого числа більших ітерацій.
4. Другий алгоритм Гомори
Другий алгоритм Р. Гомори призначається для рішення задач, у яких вимога цілочисленності накладена на деякі змінні (зокрема й на все). Ми його розглянемо стосовно до задач частково цілочисленного типу, розуміючи, що обчислювальна схема буде справедливої й для задач, повністю цілочисленних.

Нехай в області, певної умовами:
<img width=«152» height=«47» src=«ref-1_1542762113-458.coolpic» v:shapes="_x0000_i1099">                 (20)

<img width=«115» height=«25» src=«ref-1_1542762571-214.coolpic» v:shapes="_x0000_i1100">                        (21)


<img width=«19» height=«25» src=«ref-1_1542733606-97.coolpic» v:shapes="_x0000_i1101"> – цілі, <img width=«132» height=«23» src=«ref-1_1542762882-234.coolpic» v:shapes="_x0000_i1102">     (22)
потрібно максимізувати функцію
<img width=«96» height=«45» src=«ref-1_1542763116-370.coolpic» v:shapes="_x0000_i1103">                            (23)
Метод рішення задачі (20–23) ґрунтується на тій же ідеї, що й метод рішення повністю цілочисленних задач. А саме: будується область Јk, що при k = 0 визначається умовами (20–21); вирішується отримана при цьому задача лінійного програмування (20–21, 23). Якщо задача (20–21, 23) виявляється розв'язної, то отримане оптимальне рішення її аналізується на допустимість для вихідної задачі цілочисленного програмування (20–23). Якщо знайдене рішення виявляється целочисленным, то одночасно воно буде оптимальним для (20–23). Якщо оптимальне рішення (Јk, C)– задачі виявляється неприпустимим для вихідної задачі (20–23), те здійснюється побудова правильного відсікання й перехід до рішення нової задачі,

Другий алгоритм Р. Гомори формулюється у вигляді наступної теореми:

Теорема. Нехай х(Јk, C)– оптимальне рішення (Јk, C) – задачі, <img width=«29» height=«29» src=«ref-1_1542763486-150.coolpic» v:shapes="_x0000_i1104"> – елементи відповідної йому симплексної таблиці. Якщо <img width=«21» height=«25» src=«ref-1_1542763636-111.coolpic» v:shapes="_x0000_i1105"> – неціле <img width=«60» height=«23» src=«ref-1_1542763747-155.coolpic» v:shapes="_x0000_i1106">, то
<img width=«124» height=«39» src=«ref-1_1542763902-425.coolpic» v:shapes="_x0000_i1107">                                         (24)

<img width=«51» height=«21» src=«ref-1_1542764327-137.coolpic» v:shapes="_x0000_i1108"> – ціле,                                            (25)
де


<img width=«292» height=«187» src=«ref-1_1542764464-1953.coolpic» v:shapes="_x0000_i1109">                 (26)
визначає правильне відсікання. Блок-схема другого алгоритму Р. Гомори аналогічна блок-схемі першого алгоритму Р. Гомори й відрізняється лише правилом побудови коефіцієнтів правильного відсікання.

Правило побудови правильного відсікання

Нехай x(Јk, C)не задовольняє умові цілочисленності, <img width=«29» height=«29» src=«ref-1_1542763486-150.coolpic» v:shapes="_x0000_i1110"> – елементи симплексної таблиці, що відповідає отриманому оптимальному рішенню (Јk, C)– задачі. Виберемо i0=min {i| i Î
(1, 2,…,n),xi0k–неціле}
і будуємо правильне відсікання по формулах (24 – 26).

Умови кінцівки другого алгоритму Гомори:

1) Цільова функція F(x) задовольняє умові цілочисленності. Це враховується при виборі рядка k для побудови правильного відсікання.

2) Виконано принаймні одне із двох умов:

2') цільова функція обмежена знизу на багатогранній множині Ј= Ј0;

2») задача (Ј0ц, C)має принаймні один план.

За допомогою другого алгоритму Гомори можна (у випадку n1=n) вирішувати й повністю цілочисленну задачу лінійного програмування. Однак у цьому випадку немає підстав для порівняння ефективності другого й першого алгоритмів Гомори.
5. Алгоритм Дальтона й Ллевелина
Другий алгоритм Гомори має справа із частково цілочисленними задачами лінійного програмування. Дальтон і Ллевелин розглядають широкий клас задач — частково дискретні задачі лінійного програмування й стосовно до них модифікують другий алгоритм Гомори.

Нагадаємо, що рішенням задачі дискретного програмування будемо називати вектор, координати якого належать Јцобласті виду:
<img width=«160» height=«47» src=«ref-1_1542766567-473.coolpic» v:shapes="_x0000_i1111">                                  (27)

<img width=«111» height=«25» src=«ref-1_1542767040-212.coolpic» v:shapes="_x0000_i1112">                                            (28)

<img width=«296» height=«27» src=«ref-1_1542767252-543.coolpic» v:shapes="_x0000_i1113">       (29)
і максимізує значення функції
<img width=«104» height=«47» src=«ref-1_1542767795-389.coolpic» v:shapes="_x0000_i1114">                                             (30)
Будемо припускати, що <img width=«24» height=«25» src=«ref-1_1542768184-134.coolpic» v:shapes="_x0000_i1115">, тобто <img width=«239» height=«27» src=«ref-1_1542768318-454.coolpic» v:shapes="_x0000_i1116"> і є наперед заданими числами.

Теорема. Нехай x(Јk, C) – оптимальне рішення задачі (27–28, 30), <img width=«29» height=«29» src=«ref-1_1542763486-150.coolpic» v:shapes="_x0000_i1117"> – елементи симплексної таблиці, що відповідає йому.

Якщо x(Јk, C) є неприпустимим рішенням задачі (27–30) і <img width=«107» height=«27» src=«ref-1_1542768922-239.coolpic» v:shapes="_x0000_i1118">, тоді, використовуючи i-ю рядок симплексної таблиці, можна побудувати відсікання, що володіє властивістю правильності по формулах:
<img width=«124» height=«39» src=«ref-1_1542763902-425.coolpic» v:shapes="_x0000_i1119">                                (31)

<img width=«43» height=«24» src=«ref-1_1542753613-131.coolpic» v:shapes="_x0000_i1120">                                                (32)
де

<img width=«92» height=«27» src=«ref-1_1542769717-216.coolpic» v:shapes="_x0000_i1121">

<img width=«200» height=«83» src=«ref-1_1542769933-745.coolpic» v:shapes="_x0000_i1122">                (33)
Доказ. Перевіримо спочатку умову відсікання. Нехай в оптимальному рішенні x(Јk, C)координата <img width=«21» height=«25» src=«ref-1_1542763636-111.coolpic» v:shapes="_x0000_i1123"> не задовольняє умові (29). Покажемо, що в цьому випадку вектор х(Јk, C)не задовольняє умовам (31, 32). Оскільки Nk– множина індексів небазисних змінних xi,які в оптимальному рішенні дорівнюють нулю, то рівність (31) приймає вид <img width=«87» height=«25» src=«ref-1_1542770789-191.coolpic» v:shapes="_x0000_i1124"> і буде негативним відповідно до умови теореми. Отже, <img width=«43» height=«24» src=«ref-1_1542756491-130.coolpic» v:shapes="_x0000_i1125">, тобто умова відсікання не виконується.

Перевіримо умову правильності. Для цього покажемо, що будь-яке припустиме рішення задачі (27-30) задовольняє умовам (31, 32).

Запишемо розкладання для координати припустимого рішення задачі (27-30) по небазисним змінним
<img width=«267» height=«39» src=«ref-1_1542771110-730.coolpic» v:shapes="_x0000_i1126">            (34)
і розглянемо два випадки: a) <img width=«65» height=«25» src=«ref-1_1542771840-164.coolpic» v:shapes="_x0000_i1127">; б) <img width=«52» height=«24» src=«ref-1_1542772004-148.coolpic» v:shapes="_x0000_i1128">.Уведемо позначення:
<img width=«175» height=«56» src=«ref-1_1542772152-597.coolpic» v:shapes="_x0000_i1129">
і представимо (34) у вигляді
<img width=«334» height=«39» src=«ref-1_1542772749-854.coolpic» v:shapes="_x0000_i1130">


де
<img width=«228» height=«39» src=«ref-1_1542773603-683.coolpic» v:shapes="_x0000_i1131">
Очевидно, <img width=«100» height=«25» src=«ref-1_1542774286-222.coolpic» v:shapes="_x0000_i1132"> тому що <img width=«45» height=«25» src=«ref-1_1542774508-139.coolpic» v:shapes="_x0000_i1133">.

Розглянемо випадок а): <img width=«65» height=«25» src=«ref-1_1542771840-164.coolpic» v:shapes="_x0000_i1134">, або що однаково, <img width=«136» height=«27» src=«ref-1_1542774811-282.coolpic» v:shapes="_x0000_i1135">.

Звідси <img width=«140» height=«27» src=«ref-1_1542775093-282.coolpic» v:shapes="_x0000_i1136">Але <img width=«52» height=«25» src=«ref-1_1542775375-150.coolpic» v:shapes="_x0000_i1137"><img width=«12» height=«23» src=«ref-1_1542734734-73.coolpic» v:shapes="_x0000_i1138">тому
<img width=«104» height=«27» src=«ref-1_1542775598-232.coolpic» v:shapes="_x0000_i1139">                                                      (35)
Помножимо обидві частини (35) на ненегативну величину <img width=«73» height=«49» src=«ref-1_1542775830-275.coolpic» v:shapes="_x0000_i1140"> й складемо з ненегативною величиною <img width=«33» height=«25» src=«ref-1_1542776105-116.coolpic» v:shapes="_x0000_i1141">:
<img width=«207» height=«49» src=«ref-1_1542776221-504.coolpic» v:shapes="_x0000_i1142">                                  (36)
Розглянемо випадок б): <img width=«52» height=«24» src=«ref-1_1542772004-148.coolpic» v:shapes="_x0000_i1143"> або, що однаково, <img width=«128» height=«25» src=«ref-1_1542776873-262.coolpic» v:shapes="_x0000_i1144"> Тому що по визначенню <img width=«60» height=«25» src=«ref-1_1542777135-156.coolpic» v:shapes="_x0000_i1145">, то <img width=«116» height=«25» src=«ref-1_1542777291-232.coolpic» v:shapes="_x0000_i1146"> Помножимо обидві частини нерівності <img width=«60» height=«25» src=«ref-1_1542777135-156.coolpic» v:shapes="_x0000_i1147"> на ненегативну величину <img width=«73» height=«49» src=«ref-1_1542775830-275.coolpic» v:shapes="_x0000_i1148"> й на -1, одержимо <img width=«119» height=«49» src=«ref-1_1542777954-371.coolpic» v:shapes="_x0000_i1149">. Додаючи до отриманого вираження нерівність <img width=«103» height=«25» src=«ref-1_1542778325-218.coolpic» v:shapes="_x0000_i1150">, одержимо
<img width=«207» height=«49» src=«ref-1_1542776221-504.coolpic» v:shapes="_x0000_i1151">                                  (37)


Таким чином, в а) і в б) випадках прийшли до тому самому нерівності (36) і (37). Користуючись раніше уведеними позначеннями, їх можна записати
<img width=«308» height=«49» src=«ref-1_1542779047-917.coolpic» v:shapes="_x0000_i1152">    (38)
Формула (38) визначає правильні відсікання. Порівнюючи її з вираженням (31–32), доходимо висновку, що коефіцієнти <img width=«20» height=«27» src=«ref-1_1542779964-110.coolpic» v:shapes="_x0000_i1153">визначаються в такий спосіб:
<img width=«204» height=«80» src=«ref-1_1542780074-745.coolpic» v:shapes="_x0000_i1154">
Теорема доведена.

Алгоритм Дальтона — Ллевелина може бути описаний у такий спосіб.

1. Вирішується (Јk, C) – задача (27–30) (спочатку k = 0). Нехай x(Јk, C), k = 0, 1, 2,…оптимальне рішення (Јk, C)– задачі, <img width=«29» height=«29» src=«ref-1_1542763486-150.coolpic» v:shapes="_x0000_i1155"> – симплексна таблиця.

2. Перевіряється умова допустимості по всіх координатах оптимального вектора рішення х(Јk, C)(Јk, C)– задачі. Якщо умова допустимості виконується, то отримане рішення є оптимальним рішенням вихідної задачі (27-30). Якщо умова допустимості не виконується хоча б по одній координаті, здійснюється перехід до 3.

3. Нехай <img width=«83» height=«25» src=«ref-1_1542780969-194.coolpic» v:shapes="_x0000_i1156"> не задовольняє умові допустимості. Тоді вибирається


i0
= min {i| 1<i<n1, хj0k – не задовольняє (29)}.



4. Для обраного номера i=iбудується правильне відсікання, тобто вводиться додаткова змінна
<img width=«256» height=«39» src=«ref-1_1542781163-631.coolpic» v:shapes="_x0000_i1157">
де <img width=«20» height=«27» src=«ref-1_1542781794-111.coolpic» v:shapes="_x0000_i1158">визначається формулою (33),

5. Додаємо лінійне обмеження, що визначає правильне відсікання, до умов (Јk, C) – задачі й одержуємо нову (Јk+<metricconverter productid=«1, C» w:st=«on»>1, C) – задачу. Думаючи k = k + 1, переходимо до п. 1.

Приведемо без доказу теорему про кінцівку алгоритму.

Теорема. Якщо: коефіцієнти цільової функції дискретні; F(x) обмежена знизу на багатогранній множині Ј; задача (Ј, C)має принаймні одне рішення; вибір рядка для побудови правильного відсікання виробляється за правилом мінімального номера й (Јk, C)– задачі вирішуються методом послідовного уточнення оцінок, то алгоритм Дальтона й Ллевелина сходиться.
6. Алгоритм Данцига
Спосіб побудови правильних площин, що відтинають, запропонованим Данцигом значно простіше, ніж всі викладені вище способи. Але, як показали Гомори й Гофман, кінцівка алгоритму Данцига гарантується лише для дуже вузького класу задач. На прикладі алгоритму Данцига видно, наскільки тонким є питання про побудову правильних відсікань і як обережно варто підходити до різним спрощеним алгоритмам.

Розглядається повністю цілочисленна задача лінійного програмування:

Максимізувати
<img width=«104» height=«47» src=«ref-1_1542767795-389.coolpic» v:shapes="_x0000_i1159">                          (39)

при умовах
<img width=«152» height=«47» src=«ref-1_1542762113-458.coolpic» v:shapes="_x0000_i1160">                 (40)

<img width=«115» height=«25» src=«ref-1_1542762571-214.coolpic» v:shapes="_x0000_i1161">                        (41)

<img width=«19» height=«25» src=«ref-1_1542733606-97.coolpic» v:shapes="_x0000_i1162"> – цілі, <img width=«132» height=«23» src=«ref-1_1542762882-234.coolpic» v:shapes="_x0000_i1163">     (42)
Ранг матриці <img width=«96» height=«32» src=«ref-1_1542783297-258.coolpic» v:shapes="_x0000_i1164"> вважаємо рівним m.

Теорема. Нехай x(Јr, C)=xr є оптимальним опорним планом задачі (Јr, C)і xr не задовольняє умові цілочисленності, Nr – множина індексів, що нумерують небазисні змінні, відповідні xr.

Тоді нерівність
<img width=«64» height=«39» src=«ref-1_1542783555-309.coolpic» v:shapes="_x0000_i1165">                                  (43)
є правильним відсіканням.

Правильне відсікання, що відтинає нецілочисленний оптимум x(Јr, C)задачі (Јr, C    продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по информатике