Перший алгоритм Гомори рішення повністю цілочислових задач
13.3.1 Перший алгоритм Гомори рішення повністю цілочислових задач
Розглянемо повністю целочисленную завдання лінійного програмування (13.4) - (13.7), в якій n1 = n.
Нехай - оптимальний опорний план завдання на цілочисельність. Якщо вони всі цілі, то. Якщо хоча б одна координата, припустимо. буде нецілої, поступимо таким чином.
Позначимо через N сукупність небазисних змінних і на підставі останньої симплексного таблиці висловимо цільову функцію і всі змінні через небазисних змінні.
Так як - неціла величина, позначимо найближче ціле число, яке не перевищує. через [] (ціла частина) і визначимо дробову частину числа (<>):<>= -.
Теорема13.5. Нехай - допустиме рішення задачі. тоді співвідношення
визначають правильне відсікання.
Доведення. Запишемо вираз (13.10) у вигляді
Використовуючи вираз (13.11), отримаємо
На підставі припущення теореми про допустимість рішення задачі - цілі. Величини цілі по визначенню. Отже, теж ціле.
Доведемо, що. Припустимо, що . Це означає що
За визначенням дробової частини. За умовою теореми x - припустиме рішення задачі. тому. Отже,. . Звідси. або, що те ж саме,. Отже, - нецілим, а це суперечить щойно доведеним. Отже, припущення невірне. Теорема доведена.
Слідство. Будь-яке оптимальне рішення X (D. F) завдання (D. F), які не є допустимим рішенням задачі не задовольняє умові правильного відсікання (13.11).
Доведення. Нехай X (D. F) - оптимальне рішення задачі (D. F), -дробное. Покажемо, що не задовольняє умові відсікання. З оптимальності плану слід, що. Тому. З огляду на це, підставимо в вираз (13.11):
що суперечить умові.
Важливою проблемою методу відсікання є наростання кількості додаткових обмежень у міру рішення допоміжних завдань, оптимальні плани яких будуть містити нецілі координати, тобто виникає проблема розмірності. Гомори запропонував прийом, що обмежує розміри розглянутих розширених симплексних таблиць числом (n +2) (k +1), де n - кількість змінних завдань. k - число її небазисних змінних. Цей прийом заснований на тому, що додаткові обмеження (правильні відсікання) цікавлять нас лише як спосіб відсікання нецілочисельне оптимального рішення і переходу від завдання до завдання. Зауважимо, що змінна виводиться з базису відразу ж після введення обмеження:
Ідею Гомори проілюструємо на конкретному прикладі.
Приклад. Вирішити повністю целочисленную завдання лінійного програмування:
Відкидаючи умова целочисленности, вирішуємо задачу симплексним методом.
Після II ітерації отримуємо в останній симплексній таблиці оптимальне рішення. Це рішення не целочисленное. Тому переходимо до побудови завдання. З нецілочисельне значенням два рядки - перша і друга. Номер k вибираємо з умови
У нашому випадку . Тоді для освіти перетину вибирається перший рядок, тобто k = 1. Випишіть перший перетин Гоморі:
Так як = 1/2, = 7/22, = 1/22, отримуємо
Перенісши члени зі змінними в праву частину і ввівши неотрицательную балансову змінну. отримаємо переріз у формі 3-го додаткового рівняння. (13.12)
Приєднавши його до попередніх двох, прийдемо до задачі. Її рішення можна починати з остаточної симплексной таблиці для. додавши рівняння (13.12).
У рівнянні (13.12) змінна може бути базисної, проте коефіцієнт при ній дорівнює -1, тому в вихідної для завдання таблиці базисне рішення не є опорним. Значить, необхідно отримати вихідне опорне рішення.
Виділимо третю додаткову рядок і для стовпців, що мають в ній позитивні елементи (в нашому випадку для 3-го і 4-го), обчислимо відносини. Якщо знайдеться стовпець, для якого min <> відповідає виділеному рядку, то дані стовпець і рядок вибираємо в якості дозволяють, після чого змінна відразу ж виводиться з базису і нове рішення стає опорним. Якщо такого стовпця немає, то в якості дозволяють вибираються стовпець з найменшим елементом в виділеному рядку і рядок по min <>. Після цього починається процес перетворення симплексной таблиці.
В даному випадку min <> відповідає виділеному рядку 3-го стовпця. Тому, вибравши за які дозволяють 3-ю рядок і 3-й стовпець, відразу отримаємо опорне рішення, яке одночасно і оптимально:. Так як воно знову не целочисленное, то перейдемо до побудови завдання.
Відповідні перетин наступне:
Бо ж маємо нове, 4-е рівняння
Ввівши неотрицательную балансову змінну. отримаємо перетин 4-го додаткового рівняння для завдання.
Після виконання I ітерації маємо опорне рішення яке одночасно і оптимальне і целочисленное. Таким чином, . .
Дамо геометричну інтерпретацію рішення задачі. На рис. 13.2 побудована область допустимих рішень задачі і показано визначення її оптимального рішення. При вирішенні задачі введено першу перетин Гоморі. Виключивши з нього змінні і за допомогою вихідних рівнянь, отримаємо. Цьому нерівності відповідає гранична пряма. відсікає з області знайдене нецелочисленное рішення. але зберігає всі цілочисельні рішення.
Для нової області знаходимо оптимальне рішення задачі; при переході до задачі будується друга розтин. яке після виключення базисних змінних і набуде вигляду. У новій області оптимальне рішення виявляється потрібним цілочисельним.
При певних умовах вдається довести теорему про кінцівку першого алгоритму Гомори, яку ми наведемо без доведення.
Теорема13.6.Пусть безліч оптимальних планів задачі обмежена і виконуються наступні умови:
1) гарантована цілочисельність цільової функції (наприклад, все - цілі) і рядок цільової функції враховується при виборі рядка для побудови правильного відсікання:
2) справедливо принаймні одне з двох тверджень: або цільова функціяогранічена знизу на. або завдання має хоча б один план.
Тоді перший алгоритм Гомори вимагає лише кінцевого числа великих ітерацій.