|
|
Главная \ Методичні вказівки \ Методические указания и информация \ Двоїстість у лінійному програмуванні.
Двоїстість у лінійному програмуванні.Дата публикации: 11.03.2019 08:58
Тема 3. Двоїстість у лінійному програмуванні. Мета: Навчитися будувати, інтерпретувати та розв’язувати двоїсті задачі ЛП (в т.ч. й засобами MS Excel). План. 1. Побудова задачі, двоїстої до даної. 2. Визначення економічного змісту основних і додаткових змінних двоїстої задачі. 3. Аналіз задачі на чутливість за допомогою звітів, що генеруються Microsoft Excel.
1. Побудова задачі, двоїстої до даної. Згадаємо задачу про відгодівлю фермером тварин. Припустимо, що деяке господарство вирішило викупити корми (ресурси). Фермеру необхідно встановити оптимальні ціни на ці корми. Позначимо через Взагалі кажучи, поняття ціни корму в даному випадку не співпадає зі звичним для нас економічним поняттям ціни. В теорії двоїстості змінні Очевидно, що господарство, яке закуповує корми, зацікавлено в тому, щоб витрати на них були мінімальними. Отже, цільова функція буде мати вигляд З іншого боку, фермер при продажу кормів прагне отримати не менше грошей, ніж він би отримав, якщо б використовував ці корми на годівлю тварин. Тобто система обмежень матиме вигляд:
Отже, ми отримали нову модель задачі лінійного програмування, яка називається двоїстою до вихідної:
2. Визначення економічного змісту основних і додаткових змінних двоїстої задачі. Визначимо економічний зміст основних та додаткових змінних двоїстої задачі. Як зазначалося раніше, основні змінні прямої задачі показують ціну (оцінку) корму (сировини) певного виду. Отже, змінні, Розтлумачимо економічний зміст двоїстої оцінки Аналогічно збільшення сировини третього виду на одиницю дозволить знайти новий оптимальний план виробництва. Що показують додаткові змінні двоїстої задачі? Розглянемо першу нерівність двоїстої задачі:
Ліва частина нерівності показує витрати на годівлю 1 норки (витрати на виробництво одиниці продукції певного виду). 16 – ціна від реалізації 1 норки (ціна одиниці продукції). Введемо додаткову змінну Аналізуючи отриманий розв'язок, робимо висновки, що, так як
3. Аналіз задачі на чутливість за допомогою звітів, що генеруються Microsoft Excel. Для аналізу чутливості в середовищі електронних таблиць формуються наступні звіти (рис. 1): Звіт по результатам, звіт по сталості, звіт по границям.
Рис. 1. Результати пошуку розв’язку Розглянемо звіт за результатами, що відповідає Типу отчета: Результаты (рис. 2).
Рис. 2 Звіт за результатами Звіт за результатами містить інформацію про три компоненти задачі оптимізації: цільової функції (Целевая ячейка), розв’язку (Изменяемые ячейки), і обмежень (Ограничения). 1 – початкове значення цільової функції при початковому опорному плані (Исходное значение (3)); 2 – максимальне або мінімальне значення (залежно від завдання) цільової функції. У нашому випадку — 285 грош. од.; 3 – початковий опорний план; 4 – оптимальний план (розв’язок) задачі. У даному випадку, щоб одержати максимальний прибуток у розмірі 285 грош. од., потрібно виготовляти 35 одиниць товару С и 45 одиниць товару Д (зрозуміло, що товар повинен бути в цілих одиницях, але якщо задати такий параметр, то звіти, які потрібні для аналізу й покращення отриманих результатів не генеруються); 5 – показує кількість використаних ресурсів на виробництво при оптимальному плані; 6 – формули обмежень; 7 – показує вплив обмежень на кінцевий результат. Якщо статус «связанное», тоді дане обмеження впливає на отриманий оптимальний план, якщо «не связан.» — не впливає. У даному прикладі ресурс 2 має статус «не связан.» — це означає, що цей ресурс не обмежує можливості у виробництві, що не можна сказати про ресурс 1 та 3, які використано повністю; 8 – різниця між наявною кількістю ресурсів і тією, що використана при отриманні оптимального плану. Для нашого прикладу бачимо, що ресурс 2 є ще в наявності на складі (30 ум. од.). Розглянемо звіт по стійкості, що відповідає Типу отчета: Устойчивость (рис. 3).
Рис. 3 Звіт по стійкості Звіт по стійкості (більше точним був би переклад з оригіналу sensitivity — чутливість) визначає чутливість структури отриманого плану до змін початкових даних і, відповідно, подальші дії менеджера з метою покращення результатів. Такий звіт не створюється для моделей, в яких значення змінних обмежено множиною цілих чисел (задачі цілочислового лінійного програмування). 1 – оптимальний план (розв’язок) задачі. У даному випадку, щоб одержати максимальний прибуток у розмірі 285 грош. од., необхідно виготовляти 35 одиниць товару С та 45 одиниць товару Д; 2 – нормована вартість, яка стосується невідомих плану. Це невдалий переклад з оригіналу reduced cost, яку можна було перевести, як «ціна, що зменшує (цільову функцію)». Цей показник вказує на те, як зміниться оптимальне значення цільової функції при випуску продукції, якої немає в оптимальному плані. Так як нормована вартість товару А дорівнює – 5, то примусовий випуск 2 одиниць товару А (якого немає в оптимальному плані) привів би до зменшення Прибутку на 2·5=10 і становив би 285–10 = 275 грош. од. Так само, нормована вартість товару В дорівнює -2,5, то якщо б ми примусово випустили 2 одиниці товару В, то Прибуток зменшився б на 2·(-2,5) = 5 і становив би 285 – 5 = 280 грош. од. 3 – коефіцієнти цільової функції; 4, 5 – границі змін значень коефіцієнтів цільової функції за умови, що оптимальна кількість продукції (план) не зміниться. Наприклад, якщо цільовий коефіцієнт товару Д (КД) дорівнює 4 (ціна за 1 одиницю товару), то змінюючи його в рамках (Допустимое Увеличение, Допустимое Уменьшение)
то план не зміниться, але значення прибутку може зменшитись або збільшитись. Це можна перевірити, якщо запустити Поиск решений, після внесень у таблицю змін даного коефіцієнта. 6 – кількість використаних ресурсів; 7 – тіньова ціна стосується обмежень, тобто, певне значення вказує на «цінність» обмеженого ресурсу в порівнянні з іншими ресурсами. Цей показник указує на те, як зміниться оптимальне значення цільової функції (Прибуток) при зміні запасів ресурсів на 1 одиницю. Наприклад, якщо збільшити запас ресурсу 3 на 10 одиниць, то прибуток збільшиться на 10·2=20 і буде становити 285+20=305 грош. од. 8 – запаси ресурсів; 9, 10 – задають діапазон для 8, у якому діє тіньова ціна (7) (аналогічно (4) та (5) для цільової функції). Наприклад, діапазон ресурсу 1: 160 < ресурс 1 < 280. Якщо ресурс 1 збільшити на 10 одиниць, то прибуток збільшиться на 5 і буде становити 290. Якщо цей ресурс збільшити на 40 одиниць, то про прибуток нічого сказати не можна, оскільки ми вийшли за зазначені межі. Розглянемо звіт по границям, що відповідає Типу отчета: Пределы (рис. 4).
Рис. 4 Звіт по границям Звіт по границям складається із двох частин, що стосуються значень цільової функції (Целевое) і плану (Изменяемое). 1 – значення цільової функції (Прибуток); 2 – оптимальний план задачі; 3 – найменше значення, що може прийняти невідоме (у даному випадку кількість товару А, В, С та Д має Нижню границю 0, оскільки в Параметрах Поиск решений зазначили невід’ємність значень); 4 – це значення, що буде знаходитись в цільовій клітинці (Прибуток), якщо невідоме дорівнюватиме Нижний предел; 5 – це найбільше значення, що можуть прийняти невідомі, щоб одержати максимальне значення цільової функції; 6 – це значення, що буде знаходитись в цільовій клітинці (Прибуток), якщо невідомі дорівнюватимуть Верхний предел. Відповідь: Аналізуючи результати, що отримані після проведення аналізу чутливості, можна зауважити, що інформації, яку отримано аналітично та інформації звітів Microsoft Excel, значно більше в останньому випадку. Так як при аналітичному аналізі, щоб отримати повний аналіз чутливості, необхідно зробити більш складні розрахунки. Випуск продукції А та В не передбачається, а С і Д у кількості відповідно 35 та 45 од. За такого оптимального плану виробництва продукції та використання ресурсів підприємство отримує найбільшу виручку у розмірі 285 ум. од. Другий ресурс використовується у процесі виробництва продукції не повністю, а перший та третій ресурси – повністю. Таким чином, виготовлення продукції А та В нерентабельне, а С та Д – рентабельне, при цьому ресурси 1 та 3 дефіцитні, а ресурс 2 – недефіцитний. Примусовий випуск 1 одиниці товару А привів би до зменшення Прибуток на 5 грош. од. і становив би 285–5 = 280 грош. од. Примусовий випуск 1 одиниці товару В зменшить Прибуток на 2,5 грош. од. і становив би 285–2,5 = 282,5 грош. од. Границі змін значень коефіцієнтів цільової функції за умови, що оптимальна кількість продукції (план) не зміниться:
при цьому план не зміниться, але значення прибутку може зменшитись або збільшитись. Діапазон ресурсу 1: 160<ресурс 1<280, якщо ресурс 1 збільшити на 10 одиниць, то прибуток збільшиться на 5 і буде становити 290. Діапазон ресурсу 2: 250<ресурс 2<+∞. Збільшення одиниць ресурсу 2 не змінить прибуток. Діапазон ресурсу 3: 62,5<ресурс 1<125, якщо ресурс 3 збільшити на 10 одиниць, то прибуток збільшиться на 20 і буде становити 305. Останні зауваження щодо зв’язку прямої та двоїстої задачі. Зауваження 1. Оскільки систему нерівностей за допомогою штучних змінних можна звести до системи рівнянь, то будь яку пару симетричних задач можна представити у вигляді пари несиметричних. Зауваження 2. Якщо в обмеженнях є нерівності й рівності, то в прямій задачі рівності можна залишити , а у двоїстій задачі в обмеженнях може бути будь-який знак там де була рівність. Зауваження 3. Можна використати змінну в якості базисної, якщо вона присутня тільки в одному обмеженні й з коефіцієнтом = 1, тобто
х3 – може бути базисною змінною, а х4 - ні.
Методичне забезпечення
Рекомендована література Базова
Інформаційні ресурси (в т.ч. електронна бібліотека СНАУ)
|
- ціну корму першого виду, 
- ціну корму другого виду, 
- ціну корму третього виду.
є так званими двоїстими оцінками ресурсів. Вони показують розмір прибутку, який може принести одиниця певного ресурсу.
.
.
.
, 
та 
показують двоїсті оцінки корму (сировини) відповідно І, ІІ, та ІІІ-го виду. Двоїсті оцінки сировини другого та третього видів додатні, це означає, що дані види сировини повністю використовуються у виробництві. Двоїста оцінка сировини першого виду дорівнює нулю. Це вказує на те, що сировина першого виду використовується не повністю. Отже, двоїсті оцінки визначають дефіцитність сировини. Більш того, величина двоїстої оцінки показує, на скільки збільшиться прибуток підприємства при збільшенні сировини відповідного виду на одиницю.
. Якщо збільшити кількість корму ІІ виду на одиницю, тобто якщо його кількість складатиме 241, то загальний прибуток збільшиться на 38/11 і складатиме 984+38/11=987 5/11 гр. од.. При цьому числа, що знаходяться у відповідному до змінної 
, кількість продукції 1-го виду збільшиться на 7/22 і складатиме 
, кількість продукції другого виду зменшиться на 3/11 і складатиме 
.
.
. 
показує, на скільки витрати на виробництво одиниці продукції більші за ціну цієї продукції. Виходячи з визначеного економічного змісту можна зробити ще один висновок про ті види продукції, які вигідно виробляти: якщо додаткова змінна двоїстої задачі додатна, то це означає, що продукцію відповідного виду випускати економічно невигідно, так як ціна сировини, що витрачається на виробництво одиниці продукції, більша за ціну цієї продукції.
, то вартість сировини на виробництво цих видів продукції не перевищує ціну одиниці продукції, а значить випускати продукцію даних видів економічно вигідно.
