ання; б) комбінаторні методи; в) наближені методи. p> Метод Гоморі. Суть методу полягає в тому, що спочатку завдання вирішується без умови цілочисельності. Якщо отриманий план цілочисельний, задача вирішена. В іншому випадку до обмежень задачі додається нове обмеження, що володіє наступними властивостями:
Гј воно має бути лінійним;
Гј повинно відсікати знайдений оптимальний нецілочисельне план;
Гј не повинно відсікати жодного цілочисельного плану.
Додаткове обмеження, що володіє вказаними властивостями, називається правильним відсіканням.
Далі завдання вирішується з урахуванням нового обмеження. Після цього в разі потреби додається ще одне обмеження і т. д.
Метод гілок і меж - один з комбінаторних методів. Його суть полягає в упорядкованому переборі варіантів і розгляді лише тих з них, які виявляються за певними ознаками перспективними, і відкиданні безперспективних варіантів. Метод гілок і меж полягає в наступному: безліч припустимих рішень (планів) деяким способом розбивається на підмножини, кожне з яких цим же способом знову розбивається на підмножини. Процес продовжується до тих пір, поки не отримано оптимальне цілочисельне рішення вихідної задачі.
1. ПОСТАНОВКА ЗАВДАННЯ ОПЕРАЦІЙНОГО ДОСЛІДЖЕННЯ
При випуску двох видів хімічних добрив ("Флора" і "Росток") підприємство використовує три види сировини: азотну кислоту, аміак і калійну сіль. Витрата кожного виду сировини на випуск 1 т добрив, обсяг запасів сировини (на добу) і прибуток від продажу 1 т кожного виду добрив наведені в таблиці:
Види сировини
Запас (т)
Витрата сировини на 1 т добрив (т)
"Флора"
"Росток"
Азотна кислота
Аміак
Калійна сіль
900
1000
800
1
2,5
3
4
2
2
Прибуток (ден.ед.)
5
8
Визначити план виробництва добрив кожного виду, при якому прибуток підприємства буде максимальною.
2. ПОБУДОВА БАЗОВОЇ Аналітичні моделі
Для побудови математичної моделі даної задачі введемо змінні і з їх допомогою запишемо систему обмежень і цільову функцію. Припустимо:
X1-кількість виробленого добрива В«ФлораВ» (у тоннах);
Х2-кількість виробленого добрива В«РостокВ» (у тоннах);
Складемо обмеження, що враховують умову задачі.
Складемо обмеження на витрату азотної кислоти. На випуск однієї тонни добрива В«ФлораВ» витрачається 1 т азотної кислоти, значить,
витрата азотної кислоти на...
