Метод Гоморі розв'язування задачі лінійного програмування
Рішення задачі ЛП методом Гоморі
Спасибі, що Новомосковскете і діліться з іншими
Завдання, які ми вирішували раніше завжди давали цілочисельний відповідь. Це відбувалося тому, що вихідні дані були підібрані спеціальним чином. Але так буває не завжди.
Набагато частіше у відповіді виходять дробові величини - наприклад, потрібно зробити 2,5 одиниці виробу A і 3,44 одиниці виробу B. Чи припустимо таке рішення? Тут все залежить від умов завдання. Якщо ми виробляємо, наприклад, борошно і цукор в кілограмах - таке рішення цілком допустимо. 2,5 одиниці виробу A - це 2 кілограми 500 грам борошна, а 3,44 одиниці виробу B це 3 кілограми 440 грам цукру. Однак уявіть, що виріб A - це комп'ютери, а виріб B - це MP3-плеєри. Як можна зробити 3,44 одиниці MP3-плеєра? Очевидно, що ніяк. У таких випадках кажуть, що необхідно вирішити задачу цілочисельного лінійного програмування, маючи на увазі, що у відповіді обов'язково повинні вийти цілі числа.
Для вирішення цілочислових задач був розроблений спеціальний метод під назвою Метод Гоморі. Насправді, метод Гоморі це всього лише "надбудова" над звичайним симплекс-методом, який ми вивчили в попередніх розділах. Ідея методу Гоморі полягає в тому, що можна вирішити задачу звичайним симплекс-методом, отримавши (можливо) нецелочисленное рішення, а потім для кожної нецілочисельне змінної додати "поправочний" обмеження, яке по-перше, зробить цю змінну целочисленной, а по-друге, мінімальним чином вплине на значення цільової функції.
Отже, зрозуміло, що нам необхідно спочатку просто вирішити задачу симплекс-методом, а потім для кожної нецілочисельне змінної в рішенні трохи "підправити" її значення. Тобто, схема методу Гоморі приблизно наступна:
- Вирішити вихідну виробничу задачу звичайним симплекс-методом;
- Переконатися, що відповідь вийшла нецілочисельне. Якщо він цілочисельний, то задача вирішена;
- Помножити значення в останньому рядку (рядок F) на -1;
- Поки у відповіді залишилися нецілочисельне змінні, робити наступне:
- Серед нецілочисельне значень в отриманому рішенні вибрати змінну, для якої необхідно скласти додаткове обмеження (як це зробити буде пояснено в наведеному нижче прикладі);
- До вихідної задачі додати спеціальним чином складене обмеження для обраної змінної (знову ж таки, в прикладі буде показано, як саме це зробити). Це призведе до появи ще однієї допоміжної змінної;
- До отриманої задачі застосувати один етап симплекс-методу, причому прибрати інформацію, що з'явилася допоміжну змінну, і додати якусь із вихідних (яку саме також буде пояснено в прикладі).
- Попередній крок (крок 4) необхідно виконувати, поки все рішення не стане цілочисельним. Метод Гоморі гарантує, що на будь-якому етапі це точно відбудеться.
Вирішимо методом Гоморі ту ж саму виробничу задачу, яку вирішували раніше Симплекс-методом, але змінимо в ній одне число - щоб рішення з використанням Симплекс-методу вийшло нецілочисельне:
Тепер другий рядок у нас висловлює базисну змінну $ x_A $, так як дійсно, в стовпці $ x_A $ одне значення дорівнює 1, а решта - 0. Ітерація виконана.
ітерація 3
Перш ніж виконувати чергову ітерацію, необхідно перевірити, оптимально чи наше рішення? В останньому рядку немає негативних елементів, отже, наше рішення оптимально. Якщо записати значення цікавлять нас змінних $ x_A, x_B, x_C $, то отримаємо, що $ x_A = \ frac; x_B = 0; x_C = \ frac $. Значення вийшли нецілі. Отже, необхідно застосувати метод Гоморі. За методом Гоморі нам необхідно додати ще одне обмеження нашого завдання. Спершу необхідно визначити, для якої нецілої змінної ми будемо складати додаткове обмеження. У нас дві нецілих змінних - $ x_C $ і $ x_A $. Щоб визначити, для якої саме, необхідно знайти дробові частини чисел, що стоять у відповідних рядках, стовпці B.
- Число, що стоїть в рядку $ x_C $, стовпці B дорівнює $ \ frac $. Можна записати його як $ 9 \ frac $. Його дрібна частина дорівнює $ \ frac $
- Число, що стоїть в рядку $ x_A $, стовпці B дорівнює $ \ frac $. Можна записати його як $ 6 \ frac $. Його дрібна частина дорівнює $ \ frac $
Серед даних дрібних частин потрібно знайти найбільшу, і саме для цієї змінної ми будемо складати додаткове обмеження. Однак у нас дробові частини вийшли рівними, тому просто беремо першу - $ x_C $. Складаємо для змінної $ x_C $ обмеження. Воно буде мати вигляд:
Для будь-якої іншої змінної буде точно така ж формула, тільки в ній індекси у коефіцієнтів $ q $ будуть не $ C $, а якісь інші
Розберемося що тут що. Очевидно, що $ x_A, x_B, x_C, x_1, x_2, x_3 $ - змінні нашої задачі. Для знаходження коефіцієнтів $ q $ будемо використовувати числа першого рядка, так як саме там містяться дані по нашій змінної $ x_C $. Значення $ q_C $ це просто дрібна частина числа в рядку $ x_C $ і стовпці вільних членів B. Значення цієї клітини дорівнює $ \ frac = 9 \ frac $. Очевидно, що ціла частина тут 9, а дробова $ \ frac $. Отже, $ q_C = \ frac $.
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_A $. Там знаходиться число 0, і очевидно, що його дрібна частина також дорівнює 0. $ q_ = 0 $
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_B $. Там знаходиться число $ \ frac $, і очевидно, що його дрібна частина також дорівнює $ \ frac $. $ Q _ = \ frac $
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_C $. Там знаходиться число 1, і очевидно, що його дрібна частина дорівнює 0. $ q_ = 0 $
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_1 $. Там знаходиться число $ \ frac $, і очевидно, що його дрібна частина також дорівнює $ \ frac $. $ Q _ = \ frac $
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_2 $. Там знаходиться число $ - \ frac $. Для негативних чисел дрібна частина визначається трохи не так, як для позитивних, і дорівнює різниці нашого числа і наступного цілого негативного числа, меншого, ніж нашого. Для числа $ - \ frac $ наступне менше ціле негативне число це $ -1 $, і, отже, $ q _ = - \ frac - (- 1) = \ frac $
- Значення коефіцієнта $ q_ $ це дрібна частина числа, що знаходиться в рядку $ x_C $, стовпці $ x_3 $. Там знаходиться число 0, і очевидно, що його дрібна частина також дорівнює 0. $ q_ = 0 $
Підставивши знайдені коефіцієнти, отримаємо ще одне обмеження:
Однак це обмеження у вигляді нерівності, а у нас все обмеження у вигляді рівності. Тому перетворимо дане обмеження в рівність, додавши ще одну невід'ємну змінну $ x_4 $:
Занесемо це обмеження ще одним рядком в симплекс-таблицю, крім того, не забудемо, що з'явився новий стовпець $ x_4 $, а також змінимо знак останнього рядка - так завжди робиться при початку роботи за методом Гоморі:
Перевіряємо, чи отримали ми целочисленное рішення. Так, отримали. Ми отримали рішення $ x_A = 6, x_B = 1, x_C = 9 $, причому значення цільової функції (права нижня клітка таблиці з протилежним знаком) одно 83, що, до речі, збігається зі значенням цільової функції в вихідної (нецілочисельне) завдання. Тому, можна сказати, що перехід до целочисленности не змінює значення доходу фірми. Так, проте це не завжди так, і найчастіше дохід фірми при переході до целочисленности трохи падає.
Так як ми отримали цілочисельне рішення, то задача вирішена. Якби якісь із змінних знову були б нецілочисельне, процес потрібно було б повторити - знайти одну з нецілочисельне змінних, скласти для неї додаткове обмеження, отримавши ще одну допоміжну змінну, а потім зробити крок симплекс-методу, приберіть її з базису. Після якогось кроку ми б точно отримали цілочисельне рішення (як і в цьому випадку).
Ми навчилися вирішувати виробничу задачу. і вміємо видавати такий результат, який забезпечує максимальний прибуток. Однак при цьому ми зовсім не враховуємо залишки на складах. Тобто, ми звичайно гарантуємо, що використовуємо не більше ресурсів, ніж є, однак цілком можливо, що на складах залишаться надлишки. Що зазвичай роблять підприємства, якщо у них на складах утворюються надлишки ресурсів? Насправді, можна багато чого зробити:
- Можна їх продати, і тим самим підвищити прибуток (цільову функцію);
- Можна поміняти одні ресурси на інші (якщо таке можливо), і, може бути, тоді прибуток збільшиться;
- Можна обдумати випуск нового товару, який споживає якраз той ресурс, якого у нас надлишок. Може бути, тоді наша прибуток збільшиться.
Звичайне рішення виробничого завдання не дає відповідей на питання подібного роду. Однак існують методи, що дозволяють отримати такі відповіді. Один з цих методів - рішення "двоїстої" завдання. Його ми розглянемо в наступному розділі.
Корисне по темі
МатБюро працює на ринку рішення математичних задач вже 11 років. Всі ці роки ми підтримуємо прекрасну репутацію і найкращі умови «ціна-якість».
Ми пропонуємо:
Грамотне і докладний рішення за розумну вартість.
Ви також можете:
- Кількість Більше 30000
виконаних
замовлень - Ціни Розумні і
обгрунтовані
ціни - Досвід Допомагаємо студентам
в рішенні задач
вже 11 років - Кредо Якість,
відповідальність
і повагу - І ще Ми раді
виконати
Ваше замовлення