Типи задач параметричного програмування

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

Якщо ведеться аналіз коефіцієнтів цільової функції, то , якщо – правих частин обмежень, то , де .

Розглянемо найпростіші задачі ПП:

перший тип

назвемо параметричною ЗЛП з параметром у цільовій функції;

другий тип

назвемо параметричною ЗЛП з параметром у правій частині обмежень.

Мета задачі першого типу – встановити межі зміни коефіцієнтів , де оптимальний розв’язок не змінюється.

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

Наведемо загальну схему параметричного дослідження.

Розв’язують ЗЛП симплекс-методом при . Потім за допомогою аналізу знайденого оптимального розв’язку встановлюють, для якого значення оптимальний розв’язок не змінюється. При цьому знаходять інтервал цього розв’язку.

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

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

Оптимальний розв’язок не буде змінюватися для першого типу задач доти (при ), поки

,

для другого типу задач доти, поки

.

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

Сукупність значень t_k (k = 1, 2, 3 ,…) визначає критичне значення параметра у разі переходу від одного оптимального розв’язку до іншого.