• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Для знаходження оптимальних планів задач цілочислового програмування застосовують такі групи методів:

1) точні методи:

· методи відтинання;

· комбінаторні методи;

2) наближені методи.

Основою методів відтинання є ідея поступового «звуження» області допустимих розв’язків розглядуваної задачі. Пошук цілочислового оптимуму починається з розв’язування задачі з так званими послабленими обмеженнями, тобто без урахування вимог цілочисловості змінних. Далі введенням у модель спеціальних додаткових обмежень, що враховують цілочисловість змінних, багатогранник допустимих розв’язків послабленої задачі поступово зменшують доти, доки змінні оптимального розв’язку не набудуть цілочислових значень.

До цієї групи належать:

а) методи розв’язування повністю цілочислових задач (дробовий алгоритм Гоморі);

б) методи розв’язування частково цілочислових задач (другий алгоритм Гоморі, або змішаний алгоритм цілочислового програмування).

Комбінаторні методи цілочислової оптимізації базуються на ідеї перебору всіх допустимих цілочислових розв’язків, однак, згідно з їх процедурою здійснюється цілеспрямований перебір лише досить невеликої частини розв’язків.

Найпоширенішим у цій групі методів є метод гілок і меж.

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

Для розв’язування задач із бульовими змінними застосовують комбінаторні методи, причому, оскільки змінні є бульовими, то методи пошуку оптимуму значно спрощуються.

Досить поширеними є також наближені методи розв’язування цілочислових задач лінійного програмування. Оскільки для практичних задач великої розмірності за допомогою точних методів не завжди можна знайти строго оптимальний розв’язок за прий­нятний час або для розв’язування задачі використовуються наближено визначені, неточні початкові дані, то часто в реальних задачах досить обмежитися наближеним розв’язком, пошук якого є спрощеним.

Значна частина наближених алгоритмів базується на використанні обчислювальних схем відомих точних методів, таких, наприклад, як метод гілок і меж.

До наближених методів належать: метод локальної оптимізації (метод вектора спаду); модифікації точних методів; методи випадкового пошуку та ін.

Головними показниками для зіставлення ефективності застосування конкретних наближених алгоритмів на практиці є такі: абсолютна та відносна похибки отриманих наближених розв’язків.

, ,

де F – цільова функція (в даному разі для визначеності допускаємо вимогу відшукання максимального її значення); Х₁ –наближений розв’язок, знайдений деяким наближеним методом; Х^* – оптимальний план задачі.

Читайте також:

1. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
2. I. Загальна характеристика політичної та правової думки античної Греції.
3. II. ВИРОБНИЧА ХАРАКТЕРИСТИКА ПРОФЕСІЇ
4. II. Морфофункціональна характеристика відділів головного мозку
5. Ni - загальна кількість періодів, протягом яких діє процентна ставка ri.
6. Аварії на хімічно-небезпечних об’єктах та характеристика зон хімічного зараження.
7. Автобіографія. Резюме. Характеристика. Рекомендаційний лист
8. Автокореляційна характеристика системи
9. Алгоритм розв’язання задачі
10. Алгоритм розв’язання розподільної задачі
11. Алгоритм розв’язування задачі
12. Алгоритм розв’язування задачі

Переглядів: 1215