методи відсікання
Сутність методів відсікання полягає в тому, що спочатку завдання вирішується без умови целочисленности. Якщо отриманий план цілочисельний, задача вирішена. В іншому випадку до обмежень задачі додається нове обмеження, що володіє наступними властивостями:
· Воно повинно бути лінійним;
· Має відсікати знайдений оптимальний нецілочисельне план;
· Не повинно відсікати жодного цілочисельного плану.
Додаткове обмеження, що володіє вказаними властивостями, називається правильним відсіканням.
Далі завдання вирішується з урахуванням нового обмеження. Після цього в разі потреби додається ще одне обмеження і т.д.
Геометрично додавання кожного лінійного обмеження відповідає проведенню прямої (гиперплоскости), яка відсікає від багатокутника (багатогранника) рішень деяку його частину разом з нецілі координатами, але не зачіпає жодної з цілих точок цього багатогранника. В результаті новий багатогранник рішень містить всі цілі точки, які полягали в первісному многограннике рішень і відповідно отримане при цьому многограннике оптимальне рішення буде цілочисельним (рис. 6.24).
Один з алгоритмів розв'язання задачі лінійного цілочисельного програмування (6.59) ... (6.62), запропонований Гоморі, заснований на симплексному методі і використовує досить простий спосіб побудови правильного відсікання.
Мал. 6.18. Графічна ілюстрація цілочисельного рішення
Нехай задача лінійного програмування (6.52) ... (6.55) має кінцевий оптимум і на останньому етапі її рішення симплексним методом отримані наступні рівняння, що виражають основні змінні через неосновні змінні оптимального рішення
так, що оптимальним рішенням задачі (6.52) ... (6.55) є. в якому, наприклад # 946; i - неціла компонента. В цьому випадку можна довести, що нерівність
сформоване за i -му рівняння системи (6.56), має всі властивості правильного відсікання.
У нерівності (6.57) є присутнім символ. що означає дробову частину числа. Число а називається конгруентним числу в (позначається) тоді і тільки тоді, коли різниця а - в - ціле число.
Цілою частиною числа а називається найбільше ціле число. що не перевершує а. Дрібна частина числа визначається як різниця між цим числом і його цілою частиною, тобто . Наприклад, для = 2,; для = -3 і.
Для вирішення задачі цілочислового лінійного програмування (6.52) ... (6.55) методом Гоморі використовується наступний алгоритм:
1. симплексним методом вирішити задачу (6.52) ... (6.55) без урахування умови целочисленности. Якщо всі компоненти оптимального плану цілі, то він є оптимальним і для задачі цілочислового програмування (6.52) ... (6.55). Якщо перше завдання (6.52) ... (6.54) нерозв'язна (тобто не має кінцевого оптимуму або умови її суперечливі), то друге завдання (6.52) ... (6.55) також нерозв'язна.
2. Якщо серед компонент оптимального рішення є нецілі, то вибрати компоненту з найбільшою цілою частиною і за відповідним рівнянням системи (6.56) сформувати правильне відсікання (6.57).
3. Нерівність (6.57) введенням додаткової неотрицательной цілочисельний змінної перетворити в рівносильне рівняння
і включити його в систему обмежень (6.53).
4. Отриману розширену задачу вирішити симплексним методом. Якщо знайдений оптимальний план буде цілочисельним, то задача цілочисельного програмування (6.52) ... (6.55) вирішена. В іншому випадку повернутися до п. 2 алгоритму.
Якщо завдання можна вирішити в цілих числах, то після кінцевого числа кроків (ітерацій) оптимальний цілочисельний план буде знайдений.
Якщо в процесі вирішення з'явиться рівняння (виражає основну змінну через неосновні) з нецілим вільним членом і цілими іншими коефіцієнтами, то відповідне рівняння не має рішення в цілих числах. В цьому випадку і дана задача не має цілочисельного оптимального рішення.
Недоліком методу Гоморі є вимога целочисленности для всіх змінних - як основних (виражають, наприклад, в задачі про використання ресурсів одиниці продукції), так і додаткових змінних (виражають величину невикористаних ресурсів, які можуть бути і дробовими).
Відзначимо, що перехід до канонічного виду в повністю целочисленной задачі лінійного програмування, що містить обмеження - нерівності
не приводить, взагалі кажучи, до повністю целочисленной задачі в канонічному вигляді, так як в перетворених обмеженнях (6.59)
допоміжні змінні xn + i не підпорядковані вимогу целочисленности.
Однак якщо всі коефіцієнти aij. bi в (6.59) - цілі числа, то умова целочисленности можна поширити і на xn + i. як це зроблено при вирішенні прикладу 6.10.
Повністю целочисленную завдання в канонічному вигляді можна отримати також, якщо в (6.59) aij. bi - раціональні числа. Для цього слід помножити (6.59) на спільне кратне знаменників коефіцієнтів - aij. bi (тобто перейти до цілих коефіцієнтам в (6.59)) і лише після цього ввести допоміжні змінні.
Приклад 6.20. Вирішити завдання повністю цілочисельного програмування
Рішення. Наведемо завдання до канонічного виду, ввівши додаткові невід'ємні змінні. Отримаємо систему обмежень:
Вирішуємо задачу симплексним методом. Для наочності рішення ілюструємо графічно (рис. 6.19).
Мал. 6.19. Графічна ілюстрація рішення задачі
На рис. 6.19 0KLM - область допустимих рішень задачі обмежена прямими (1), (2), (3) і осями координат; L (2/3; 8) - точка оптимального, але нецілочисельне рішення задачі; (4) - пряма, що відсікає це нецелочисленное рішення; 0KNM - область допустимих рішень розширеної задачі (6.64 ') N (2; 7) - точка оптимального цілочисельного рішення.
I крок. Основні змінні; неосновні змінні.
Базисне рішення Х3 оптимально для задачі. так як в вираженні лінійної функції відсутні неосновні змінні з позитивними коефіцієнтами.
Однак рішення Х3 не задовольняє умові целочисленности (6.55 '). По першому рівнянню зі змінною х1. отримала нецелочисленное значення в оптимальному рішенні (2/3), складаємо додаткове обмеження (6.57):
Звертаємо увагу на те, що згідно з (6.56) і (6.57) беремо дробову частину вільного члена з тим же знаком, який він має в рівнянні, а дробові частини коефіцієнтів при неосновних змінних х4 і х5 - з протилежними знаками.
Так як дробові частини
то остання нерівність запишемо у вигляді
Ввівши додаткову целочисленную змінну х6 ≥ 0, одержимо рівносильне нерівності (6.57 ') рівняння
Рівняння (6.58) необхідно включити в систему обмежень (6.56 ') вихідної канонічної задачі, після чого повторити процес вирішення завдання симплексним методом стосовно розширеної задачі. При цьому для скорочення числа кроків (ітерацій) рекомендується вводити додаткове рівняння (6.58 ') в систему, отриману на останньому кроці рішення задачі (без умови целочисленности).
IV крок. Основні змінні; неосновні змінні.
Так як в вираженні лінійної функції немає основних змінних з позитивними коефіцієнтами, то Х5 - оптимальне рішення.
Отже, fmax = 25 при оптимальному целочисленном вирішенні Шоста компонента змістовного сенсу не має.
Для геометричної інтерпретації на площині 0х1х2 (див. Рис. 6.19) відсікання (6.57 ') необхідно входять до нього змінні х4 і х5 висловити через змінні х1 і х2. Отримаємо (див. 2-е і 3-е рівняння системи обмежень (6.56 '):
(Див. Відсікання прямий (4) на рис. 6.19).