Відмінності між версіями «Комбінаторні методи. Метод гілок та меж»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(Алгоритм методу гілок та меж:)
Рядок 94: Рядок 94:
  
 
Якщо задача (1)—(3) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача (1)—(4) також не має розв’язку.
 
Якщо задача (1)—(3) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача (1)—(4) також не має розв’язку.
2. Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних <math>x_i</math> і визначають її цілу частину <math> \left [ x'_i \right ]</math>3. 3. Записують два обмеження, що відтинають нецілочисло-ві розв’язки:
+
 
 +
2. Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних <math>x_i</math> і визначають її цілу частину <math> \left [ x'_i \right ]</math>
 +
3. Записують два обмеження, що відтинають нецілочисло-ві розв’язки:
 
<center><math>x_i \le  \left [ x'_i \right ] </math> </center>
 
<center><math>x_i \le  \left [ x'_i \right ] </math> </center>
 
<center><math>x_i \ge  \left [ x'_i \right ] +1</math> </center>
 
<center><math>x_i \ge  \left [ x'_i \right ] +1</math> </center>

Версія за 08:10, 14 травня 2012

Комбінаторні методи

В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої задачі. Для розв’язування задач цілочис-лового програмування ефективнішим за метод Гоморі є метод гілок і меж. Спочатку, як і в разі методу Гоморі, симплексним методом розв’язується послаблена (без умов цілочисловості) за-дача. Потім вводиться правило перебору.

Нехай потрібно знайти Неможливо розібрати вираз (невідома помилка): x_j

— цілочислову змінну, значення якої Неможливо розібрати вираз (невідома помилка): x_j= x'_j
в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Та-ким проміжком є інтервал між найближчими до Неможливо розібрати вираз (невідома помилка): x'_j
цілочисловими значеннями. Можна стверджувати, що на інтервалі Неможливо розібрати вираз (невідома помилка):  \left [ \left [ x'_j \right ] ; \left [ x'_j \right ] + 1 \right ] 

цілих значень немає.

Наприклад, якщо Неможливо розібрати вираз (невідома помилка): x'_j = 2,7

дістаємо інтервал \left [ 2;3 \right ] , де, очевидно, немає Неможливо розібрати вираз (невідома помилка): x_j
, яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі Неможливо розібрати вираз (невідома помилка): x_j \le 2

, або Неможливо розібрати вираз (невідома помилка): x_j \ge 3

Виключення проміжку \left [ 2;3 \right ] з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерів¬ностей. Тобто допустиме ціле значення Неможливо розібрати вираз (невідома помилка): x_j
має задовольняти одну з нерівностей виду:

Неможливо розібрати вираз (невідома помилка): x_j \le \left [ x'_j \right ]

або Неможливо розібрати вираз (невідома помилка): x_j \ge \left [ x'_j \right ] +1


Дописавши кожну з цих умов до задачі з послабленими обме-женнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, початкову задачу цілочислового програмування поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:

перша задача:

Неможливо розібрати вираз (невідома помилка): \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} } (1)

за умов:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {a_{ij} x_{j} } \left\{ {\begin{array}{l} \le \\ = \\ \ge \\ \end{array}} \right\}b_{i} \quad \left( {i=\overline {1,m} } \right); (2)


Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0 \quad \left( {j=\overline {1,n} } \right); (3)


Неможливо розібрати вираз (невідома помилка): \ \quad x_{j}
- цілі числа  Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);
(4)
Неможливо розібрати вираз (невідома помилка): x_j \le \left [ x'_j \right ] (5)

друга задача:

Неможливо розібрати вираз (невідома помилка): \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} } (6)

за умов:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {a_{ij} x_{j} } \left\{ {\begin{array}{l} \le \\ = \\ \ge \\ \end{array}} \right\}b_{i} \quad \left( {i=\overline {1,m} } \right); (7)


Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0 \quad \left( {j=\overline {1,n} } \right); (8)


Неможливо розібрати вираз (невідома помилка): \ \quad x_{j}
- цілі числа  Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);
(9)
Неможливо розібрати вираз (невідома помилка): x_j \ge \left [ x'_j \right ] (10)

де Неможливо розібрати вираз (невідома помилка): x'_j

 — дробова компонента розв’язку початкової задачі цілочислового програмування. Наведені задачі (1)—(5) і (6)—(10) спочатку посла-б¬люємо, тобто розв’язуємо з відкиданням обмежень (4) і (9). Якщо знайдені оптимальні плани задовольняють умови цілочисловості, то ці плани є розв’язками початкової задачі цілочислового програмування. Інакше пошук розв’язку задачі триває. Для дальшого розгалуження вибираємо розв’язок задачі з більшим значенням цільової функції, якщо йдеться про максимізацію, і навпаки — з меншим значенням цільової функції в разі її мінімізації. Подальше розгалуження виконується доти, доки не буде встановлено неможливість поліпшення розв’язку. Здобутий останній план — оптимальний.

Розв’язування цілочислових задач методом гілок і меж можна значно прискорити. Очевидно, що кожна наступна задача, яку отримують в процесі розв’язування відрізняється від попере-дньої лише одним обмеженням. Досить буде почергово приєд-нати нові обмеження виду (5) і (10) до останньої симплекс-таблиці попередньої задачі та вилучити (в разі необхідності) не-потрібні «старі» обмеження.

Геометрично введення додаткових лінійних обмежень виду (5) та (10) в систему обмежень початкової задачі означає проведення гіперплощин (прямих), що розтинають багатогранник (багатокутник) допустимих планів відповідної задачі лінійно-го програмування у такий спосіб, що уможливлюється включення в план найближчої цілої точки цього багатокутника.

Clip image002.gif
Допустимо, що А — точка максимуму, тоді за методом гілок та меж багатокутник допустимих планів задачі ABCOD поділяється на дві частини прямими Неможливо розібрати вираз (невідома помилка): x'_1 = \left [ x'_1 \right ]
та Неможливо розібрати вираз (невідома помилка): x'_1 = \left [ x'_1 \right ]+1

, що виключає з розгляду точку А, координата якої Неможливо розібрати вираз (невідома помилка): x'_1

є не цілим числом.
Combmet.png


Алгоритм методу гілок та меж:

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

Неможливо розібрати вираз (невідома помилка): \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} } (1)

за умов:

Неможливо розібрати вираз (невідома помилка): \sum\limits_{j=1}^n {a_{ij} x_{j} } \left\{ {\begin{array}{l} \le \\ = \\ \ge \\ \end{array}} \right\}b_{i} \quad \left( {i=\overline {1,m} } \right); (2)


Неможливо розібрати вираз (невідома помилка): x_{j} \ge 0 \quad \left( {j=\overline {1,n} } \right); (3)


Неможливо розібрати вираз (невідома помилка): \ \quad x_{j}
- цілі числа  Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);
(4)

1. Симплексним методом розв’язують задачу (1)—(3) (без вимог цілочисловості змінних).

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей розв’язок є оптимальним планом задачі цілочислового програмування (1)—(4).

Якщо задача (1)—(3) не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача (1)—(4) також не має розв’язку.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирають одну з нецілочислових змінних Неможливо розібрати вираз (невідома помилка): x_i

і визначають її цілу частину Неможливо розібрати вираз (невідома помилка):  \left [ x'_i \right ]

3. Записують два обмеження, що відтинають нецілочисло-ві розв’язки:

Неможливо розібрати вираз (невідома помилка): x_i \le \left [ x'_i \right ]
Неможливо розібрати вираз (невідома помилка): x_i \ge \left [ x'_i \right ] +1

4. Кожну з одержаних нерівностей приєднують до обме-жень початкової задачі. В результаті отримують дві нові ціло-числові задачі лінійного програмування. 5. У будь-якій послідовності розв’язують обидві задачі. У разі, коли отримано цілочисловий розв’язок хоча б однієї із задач, значення цільової функції цієї задачі зіставляють з почат¬ковим значенням. Якщо різниця не більша від заданого числа \epsilon, то процес розв’язування може бути закінчено. У разі, коли цілочисловий розв’язок одержано в обох задачах, то з роз¬в’язком початкової зіставляється той, який дає краще значення цільової функції. Якщо ж в обох задачах одержано нецілочислові розв’язки, то для дальшого гілкування вибирають ту задачу, для якої здо-буто краще значення цільової функції і здійснюють перехід до кроку 2.