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

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

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

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

перший тип

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

другий тип

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

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

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

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

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

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

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

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

,

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

.

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

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

4.3. Геометрична інтерпретація

При використанні графічного методу розв’язок ЗЛП міститься в одній з вершин многогранника ОДР (рис. 4.1).

Якщо змінити нахил прямої цільової

А функції, то ця пряма може збігатися зі сторо-

ною АВ чи ВС, не змінюючи значення .

D В Нахил прямої досягається за допомо-

С гою коефіцієнтів , задаючи різні значення

параметра :

Рис. 4.1 .

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

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

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

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