Метод Гоморі онлайн
Метод Гоморі використовують для знаходження цілочисельного рішення в задачах лінійного програмування.
Нехай знайдено рішення задачі ЛП:. Рішення Li буде цілим числом, якщо тобто . i> - дрібна частина нецілочисельне оптимального рішення xi. i> - дрібна частина не базисних змінних. Дане співвідношення визначає правильне відсікання Гомори (див. Малюнок).
Інструкція. Виберіть кількість змінних і кількість рядків (кількість обмежень), натисніть Далі. Отримане рішення зберігається в файлі Word (див. Приклад рішення методом Гоморі). Додатково створюється шаблон рішення в форматі Excel. При цьому обмеження типу xi ≥ 0 не зважайте.
Види алгоритму Гомори
- Перший алгоритм Гомори рішення повністю цілочислових задач.
- Другий алгоритм Гомори для частково цілочисельних задач лінійного програмування.
- Вирішується задача лінійного програмування без урахування целочисленности.
- Серед дрібних чисел вибирається елемент з найбільшою дробовою частиною і складається додаткове обмеження.
- Нерівність перетворюється в рівняння шляхом введення додаткової неотрицательной змінної.
- Отримана задача вирішується двоїстим симплекс-методом.
Геометрична інтерпретація відсікання Гомори
Приклад. Науково-виробниче об'єднання «Стріла» займається виготовленням комплектуючих виробів для підприємств ВПК. При виготовленні виробів типу А і типу В використовуються сталь і кольорові метали. Технологічний процес також включає обробку виробів на токарних і фрезерних верстатах. За технологічним нормам на виробництво одного виробу типу А і одного виробу типу В потрібна певна кількість сировини і деякий обсяг станко-годин для обробки на верстатах в цеху. Технологічні дані виробничого процесу наведені в таблиці.
Протягом місяця цеху НВО «Стріла» своєму розпорядженні обмежені ресурсами по сировині і за часом роботи в виробничих цехах (див. Таблицю). Прибуток від реалізації одного виробу типу А становить 100 руб. а від одиниці виробу типу В - 250 руб.
Робота в цеху, станко-годину
Прибуток від реалізації, руб.