Метод Гоморі. Приклад розв'язку задачі цілочисельного програмування методом Гоморі

Розглянемо приклад знаходження розв'язку задачі цілочисельного програмування використовуючи метод Гоморі. Отже, для виготовлення товару A і В підприємство використовує два види сировини. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A та B, а також загальна кількість сировини наведені в наступній таблиці:

Таблиця даних задачі лінійного програмування

Таблиця даних задачі цілочисельного програмування

Необхідно скласти такий план випуску даної продукції, щоб прибуток від її реалізації був максимальним.

Нехай Метод Гоморі приклад та Метод Гоморі приклад — кількість комплектів товару типу А та В відповідно. Тоді економіко-математична модель даної задачі запишеться у наступному вигляді:

Метод Гоморі приклад

де Метод Гоморі приклад та Метод Гоморі приклад — цілі числаю. На першому кроці, розв'яжемо дану задачу нехтуючи умовою цілочисельності. Для цього скористаємось симплекс методом, остання таблиця якого для даної задачі набуде наступного вигляду:

Метод Гоморі приклад

Розв'язок задачі лінійного програмування без урахування умови цілочисельності

З отриманого умовно-оптимального плану бачимо, що значення другої змінної є дробовим числом, що не задовільняє початковій умові задачі. Тому, для другого рядка даної симплекс таблиці будуємо додаткове обмеження наступного виду: Метод Гоморі приклад. Далі зведемо дану нерівність до канонічної форми та з допомогою додаткової змінної перетворимо її у рівність. В результаті отримаємо: Метод Гоморі приклад.

Приєднавши отримане обмеження до останньої симплекс таблиці з умовно-оптимальним планом, отримаємо:

Симплекс таблиця з приєднаним додатковим обмеженням

Симплекс таблиця з приєднаним додатковим обмеженням

Після цього, згідно алгоритму методу Гоморі, даний псевдоплан розв'яжемо з допомогою двоїстого симплекс методу в результаті чого отримаємо цілочисельний оптимальний план.

Оптимальний план задачі лінійного програмування

Оптимальний план задачі лінійного програмування

Отже, прибуток буде максимальним, якщо реалізувати дві одиниці продукції типу А і становитиме 10 умовних одиниць.

Зауваження: яким чином звести додаткове обмеження до канонічної форми та як його перетворити у рівність можна знайти перейшовши за посиланням Розв'язок задачі цілочисельного програмування методом Гоморі.

Матеріал був корисним, поділись в соціальних мережах:

Якщо тобі сподобалась дана тема, залиш свій коментар