Відмінності між версіями «Комбінаторні методи. Метод гілок та меж»
Матеріал з Вікі ЦДУ
(Створена сторінка: В основі комбінаторних методів є перебір можливих варіантів розв’язків поставленої зад...) |
|||
| Рядок 3: | Рядок 3: | ||
Нехай потрібно знайти <math>x_j</math> — цілочислову змінну, значення якої <math>x_j= x'_j</math> в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Та-ким проміжком є інтервал між найближчими до <math>x'_j</math> цілочисловими значеннями. Можна стверджувати, що на інтервалі <math> \left [ \left [ x'_j \right ] ; \left [ x'_j \right ] + 1 \right ] </math>цілих значень немає. | Нехай потрібно знайти <math>x_j</math> — цілочислову змінну, значення якої <math>x_j= x'_j</math> в оптимальному плані послабленої задачі є дробовим. Очевидно, що в деякому околі даної точки також не існує цілочислових значень, тому відповідний проміжок можна виключити з множини допустимих планів задачі в подальшому розгляді. Та-ким проміжком є інтервал між найближчими до <math>x'_j</math> цілочисловими значеннями. Можна стверджувати, що на інтервалі <math> \left [ \left [ x'_j \right ] ; \left [ x'_j \right ] + 1 \right ] </math>цілих значень немає. | ||
| − | Наприклад, якщо <math>x'_j = 2,7</math> дістаємо інтервал \left [ 2;3 \right ] , де, очевидно, немає <math>x_j</math> , яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі <math>x_j \le 2</math>, або <math>x_j \ge 3</math> | + | Наприклад, якщо <math>x'_j = 2,7</math> дістаємо інтервал \left [ 2;3 \right ] , де, очевидно, немає <math>x_j</math> , яке набуває цілого значення і оптимальний розв’язок буде знаходитися або в інтервалі <math>x_j \le 2</math>, або <math>x_j \ge 3</math> Виключення проміжку \left [ 2;3 \right ] з множини допустимих планів здійснюється введенням до системи обмежень початкової задачі додаткових нерів¬ностей. Тобто допустиме ціле значення <math>x_j</math> має задовольняти одну з нерівностей виду: |
| + | <math>x_j \le \left [ x'_j \right ]</math> або <math>x_j \ge \left [ x'_j \right ] +1</math> | ||
| + | |||
| + | Дописавши кожну з цих умов до задачі з послабленими обме-женнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, [[Постановка_цілочислової_задачі_ЛП._Геометрична_інтерпретація | початкову задачу цілочислового програмування]] поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими. | ||
| + | Це означає, що симплекс-методом розв’язуватимемо дві такі задачі: | ||
| + | |||
| + | перша задача: | ||
| + | <center><math> \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} }</math></center> | ||
| + | за умов: | ||
| + | <center><math>\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);</math></center> | ||
| + | |||
| + | |||
| + | <center><math> | ||
| + | x_{j} \ge 0 | ||
| + | \quad | ||
| + | \left( {j=\overline {1,n} } \right);</math></center> | ||
| + | |||
| + | |||
| + | <center> <math>\ \quad x_{j}</math> - цілі числа <math>\left( {j=\overline {1,n} } \right);</math></center> | ||
| + | |||
| + | <center> <math>x_j \le \left [ x'_j \right ] </math> </center> | ||
| + | |||
| + | друга задача: | ||
| + | <center><math> \max \,(\min )\,\,F=\sum\limits_{j=1}^n {c_{j} x_{j} }</math></center> | ||
| + | за умов: | ||
| + | <center><math>\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);</math></center> | ||
| + | |||
| + | |||
| + | <center><math> | ||
| + | x_{j} \ge 0 | ||
| + | \quad | ||
| + | \left( {j=\overline {1,n} } \right);</math></center> | ||
| + | |||
| + | |||
| + | <center> <math>\ \quad x_{j}</math> - цілі числа <math>\left( {j=\overline {1,n} } \right);</math></center> | ||
| + | |||
| + | <center> <math>x_j \ge \left [ x'_j \right ] </math> </center> | ||
Версія за 07:45, 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
Дописавши кожну з цих умов до задачі з послабленими обме-женнями, дістанемо дві, не пов’язані між собою, задачі. Тобто, початкову задачу цілочислового програмування поділимо на дві задачі з урахуванням умов цілочисловості змінних, значення яких в оптимальному плані послабленої задачі є дробовими.
Це означає, що симплекс-методом розв’язуватимемо дві такі задачі:
перша задача:
за умов:
- цілі числа Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);
друга задача:
за умов:
- цілі числа Неможливо розібрати вираз (невідома помилка): \left( {j=\overline {1,n} } \right);
