Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

3.5.2. Аналіз діапазону зміни коефіцієнтів цільової функції

Розглянемо задачу лінійного програмування (3.36)—(3.38). Допустимо, що коефіцієнт цільової функції при деякій k-ій змінній з початковим значенням змінився на величину . Отже, цільова функція (3.36) набуде вигляду:

, (3.49)

де С, Х — відповідно вектор компонент цільової функції та вектор змінних, ek — одиничний вектор-рядок, де одиниця відповідає k-ій компоненті.

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

А. Перший випадок — коефіцієнт ck відповідає базисній змінній оптимального плану. За припущенням базисними змінними оптимального плану є перші m векторів останньої симплексної таблиці, отже, .

Зміни коефіцієнтів цільової функції в процесі реалізації симплексного методу впливатимуть лише на значення оцінкового ряду ().

Для оптимального плану задачі (3.36)—(3.38), як відомо з § 2.7.4, оцінки векторів розраховують так:

.

Якщо цільова функція має вигляд (3.49), то оцінки векторів розраховуватимуться за формулою:

,

де аkj — елементи вектора-рядка, який є результатом множення ek на Х.

Остання симплексна таблиця набуває вигляду:

Таблиця 3.4

Для того, щоб план задачі з цільовою функцією (3.49) та системою обмежень (3.37), (3.38) також був оптимальним, має виконуватися умова:

(3.50)

Отже, у разі зміни коефіцієнтів цільової функції, що відповідають базисним змінним, діапазон стійкості оптимального плану визначається з (3.50):

. (3.51)

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

;

.

Якщо не існує жодного для , то , а якщо не існує ні одного для , то .

Отже, за змін сk, що відповідає базисній змінній, в інтервалі , якщо , структура оптимального плану задачі (3.36)—(3.38) залишиться тією самою.

В. Другий випадок — змінюється коефіцієнт цільової функції при небазисній змінній.

Зміна коефіцієнта цільової функції небазисної змінної впливає на оцінку лише цієї змінної. Допустимо, що це коефіцієнт і за припущенням у даній задачі . Нехай цей коефіцієнт зміниться на величину . Тоді для задачі з цільовою функцією (3.49) в останній симплексній таблиці зміниться лише одна оцінка, що відповідає небазисній змінній :

,

де — оцінка вектора при змінній задачі (3.36)—(3.38). Дана оцінка має бути невід’ємною, отже:

.

Для небазисної змінної діапазон стійкості оптимального плану визначається нерівністю:

. (3.52)

Тобто для коефіцієнтів цільової функції при небазисних змінних існує лише верхня межа зміни діапазону .

С. Якщо коефіцієнти при змінних цільової функції (3.36) задачі лінійного програмування водночас змінюються для кількох чи всіх значень , то визначення границь можливих змін величин здійснюється аналогічно випадку (А).

Для того, щоб план задачі з цільовою функцією, в якій одночасно змінюються кілька чи всі значення , та системою обмежень (3.37), (3.38) також був оптимальним, має виконуватися умова, аналогічна (3.50):

(3.53)

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

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