Як розрахувати інтервали можливих змін цін на одиницю кожного виду продукції.

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

Задача лінійного програмування:

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

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

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

А. Перший випадок — коефіцієнт c_k відповідає базисній змінній оптимального плану.

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

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

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

,

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

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

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

.

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

;

.

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

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

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

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

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

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

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

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

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

8. Поясніть, що називається областю допустимих планів.

Вектор Х = (х 1, х 2, …, хп), координати якого задовольняють сис­темі обмежень називають допустимим розв’язком, або допустимим планом задачі. Сукупність допустимих розв’яз­ків (пла­нів) задачі утворює область допустимих розв’язків задачі. Опорним планом задачі лінійного програмування називається план, утворений координатами вершини многогранника планів задачі. Якщо задача лінійного програмування має розв’язок і серед її планів є опорні, то хоча б один із них буде оптимальним. Сукупність усіх розв’язків задачі лінійного програмування є многогранною опуклою множиною, яку називають многогранником розв’язків. Якщо задача лінійного програмування має оптимальний план, то екстремального значення цільова функція набуває в одній із вершин многогранника розв’язків. Якщо цільова функція набуває екстремального значення більш як в одній вершині цього многогранника, то вона досягає його і в будь-який точці, що є лінійною комбінацією таких вершин.