24.Приклади застосування теорії двоїстості для знаходження оптимальних планів прямої та двоїстої оптимізаційних задач

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

max Z = – 5x1 + 2x2;

Розв’язання. Перш ніж записати двоїсту задачу, необхідно пряму задачу звести до стандартного вигляду. Оскільки цільова функція F максимізується і в системі обмежень є нерівності, то їх слід звести до виду « ». Тому перше обмеження задачі помножимо на (–1). Після цього знак нерівності зміниться на протилежний. Отримаємо:

max Z = – 5x1 + 2x2;

Тепер за відповідними правилами складемо двоїсту задачу:

min F = – y1 + 5y2;Оскільки записані задачі симетричні, то будь-яку з них можна розв’язати симплекс-методом. Наприклад, визначимо спочатку оптимальний план прямої задачі. Для цього застосуємо алгоритм симплекс-методу.1. max Z = – 5x1 + 2x2 + 0x3 + 0x4;

2. Векторна форма запису системи обмежень має вигляд:

,

де , , , , .У системі векторів для утворення початкового одиничного базису відсутній один вектор. Тому введемо штучну змінну в перше обмеження.3. Розширена задача лінійного програмування буде такою:max Z = – 5x1 + 2x2 + 0x3 + 0x4 – Мx5;

У цій задачі х4 та х5 — базисні змінні, а х1, х2, х3 — вільні. Нехай х1 = х2 = х3 = 0, тоді х4 = 5; х5 = 1.

Перший опорний план задачі:X0 = (0; 0; 0; 5; 1), Z0 = – M.

25.Аналіз лінійних оптимізаційних задач. Економічна інтерпретація пари двоїстих задач

Кожна задача лінійного програмування пов’язана з іншою, так званою двоїстою задачею. Економічну інтерпретацію кожної з пари таких задач розглянемо на прикладі виробничої задачі .Пряма задача: max F = c1x1 + c2x2 + … + cnxn (3.1)

за умов: (3.2) Необхідно визначити, яку кількість продукції кожного j-го виду необхідно виготовляти в процесі виробництва, щоб максимізувати загальну виручку від реалізації продукції підприємства. Причому відомі: наявні обсяги ресурсів — ; норми витрат і-го виду ресурсу на виробництво одиниці j-го виду продукції — , а також — ціни реалізації одиниці j-ої продукції.Розглянемо тепер цю саму задачу з іншого погляду. Допустимо, що за певних умов доцільно продавати деяку частину чи всі наявні ресурси. Необхідно визначити ціни ресурсів. Кожному ресурсу поставимо у відповідність його оцінку . Умовно вважатимемо, що — ціна одиниці і-го ресурсу. На виготовлення одиниці j-го виду продукції витрачається згідно з моделлю (3.1)—(3.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці j-го виду продукції, обчислюється у такий спосіб: .

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

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

(3.4)

за умов: (3.5)

Тобто необхідно визначити, які мінімальні ціни можна встановити для одиниці кожного і-го виду ресурсу , щоб продаж ресурсів був доцільнішим, ніж виробництво продукції. Зауважимо, що справжній зміст величин — умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва. Англійський термін «shadow prices» у літературі перекладають як «оцінка» або «тіньова, неявна ціна». Академік Л. В. Канторович назвав їх об’єктивно обумовленими оцінками відповідного ресурсу.

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

Розглянемо задачу лінійного програмування Допустимо, що коефіцієнт цільової функції при деякій k-ій змінній з початковим значенням змінився на величину . Отже, цільова функція набуде вигляду: , де С, Х — відповідно вектор компонент цільової функції та вектор змінних, ek — одиничний вектор-рядок, де одиниця відповідає k-ій компоненті.Дослідимо питання визначення границь можливих змін коефіцієнтів цільової функції, в межах яких структура оптимального плану залишається постійною.А. Перший випадок — коефіцієнт ck відповідає базисній змінній оптимального плану. За припущенням базисними змінними оптимального плану є перші m векторів останньої симплексної таблиці, отже, .Зміни коефіцієнтів цільової функції в процесі реалізації симплексного методу впливатимуть лише на значення оцінкового ряду ( ).Для оптимального плану задачі (3.36)—(3.38), як відомо з § 2.7.4, оцінки векторів розраховують так: .Якщо цільова функція має вигляд то оцінки векторів розраховуватимуться за формулою:

,

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

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

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

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

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

теми обмежень, що відповідає k-ій небазисній змінній. Нехай для деякого k виконується рівність: . Розрахуємо значення оцінки вектора , підставляючи в (3.54) нові значення : .Для того, щоб план нової задачі також був оптимальним, має виконуватися умова: .Отже, розв’язок залишається оптимальним у такому діапазоні змін : , якщо ; , якщо .Економічний зміст нерівностей (3.58), (3.59) полягає в тому, що вони дають змогу визначати межі можливих змін норм витрат ресурсів на виробництво одиниці продукції, в яких оптимальна структура виробництва продукції залишається незмінною. Розглянутий випадок стосується зміни коефіцієнтів аij для тих видів продукції, виробництво яких за оптимальним планом є недоцільним..