Навігація
Головна
Перша теорема подвійностіТеорема Хекшера - ОлінаОсновні теореми і положення алгебри логіки
Друга теорема подвійності (теорема про доповнює нежорсткості)Теорема Хекшера - ОлінаОсновні теореми і положення алгебри логіки
Теорема про оцінки (третя теорема подвійності)Теорема Хекшера - ОлінаМетоди опуклого математичного програмування і умовні нелінійні оцінки
 
Головна arrow Економіка arrow Економіко-математичні методи і прикладні моделі
< Попередня   ЗМІСТ   Наступна >

Перша теорема подвійності

data-override-format="true" data-page-url = "http://stud.com.ua">

Для взаімодвойственних ЗЛП має місце один з взаємовиключних випадків.

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

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

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

4. Обидві з розглянутих завдань мають порожні допустимі множини.

Друга теорема подвійності (теорема про доповнює нежорсткості)

Нехай - допустиме рішення прямої задачі (3.1) - (3.3), а допустиме рішення двоїстої задачі (3.4) - (3.6). Для того щоб вони були оптимальними рішеннями відповідних взаімодвойственних завдань (3.1) - (3.3) і (3.4) - (3.6), необхідно і достатньо, щоб виконувалися наступні співвідношення:

Умови (3.7) і (3.8) дозволяють, знаючи оптимальне рішення однієї з взаімодвойственних завдань, знайти оптимальне рішення іншої задачі.

(3.7)

(3.8)

Розглянемо ще одну теорему, висновки якої будуть використані надалі.

Теорема про оцінки (третя теорема подвійності)

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

(3.9)

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

Розглянемо економічну інтерпретацію двоїстої задачі на наступному прикладі.

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

Рішення. Складемо економіко-математичну модель задачі оптимального використання ресурсів на максимум прибутку. В якості невідомих приймемо обсяг випуску продукції j-го виду.

Таблиця 3.1

Початкові дані

Вид

сировини

Запаси

сировини

Вид продукції

P 1

P 1

P 1

P 1

S 1

35

4

2

2

3

S 2

30

1

1

2

3

S 3

10

3

1

2

1

Прибуток

14

10

14

11

Модель задачі за критерієм "максимум прибутку":

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

data-override-format="true" data-page-url = "http://stud.com.ua">

1) купує організація намагається мінімізувати загальну вартість ресурсів;

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

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

За економічним змістом ціни невід'ємні:

Отримали симетричну пару взаімодвойственних завдань. У результаті рішення даної задачі симплексним методом отриманий оптимальний план. На рис. 3.1 приведений результат рішення задачі з використанням надбудови Пошук рішення Excel [18,19]. Жирним шрифтом виділено оптимальні значення і

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

Звіт по стійкості Microsoft Excel

Мал. 3.1. Звіт по стійкості Microsoft Excel

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

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

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

З другої теореми подвійності в даному випадку йдуть такі вимоги на оптимальну виробничу програму і оптимальний вектор оцінок:

(3.10)

(3.11)

Умови (3.10) можна інтерпретувати так: якщо оцінка у i одиниці ресурсу i -го виду позитивна, то при оптимальній виробничій програмі цей ресурс використовується повністю; якщо ж ресурс використовується не повністю, то його оцінка дорівнює нулю.

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

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

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

Один з ефективних засобів економіко-математичного аналізу - використання об'єктивно обумовлених оцінок оптимального плану. Такого роду аналіз базується на властивостях двоїстих оцінок. Вище ми встановили загальні математичні властивості двоїстих оцінок для завдань на оптимум будь-якої економічної природи. Однак економічна інтерпретація цих оцінок може бути зовсім різною для різних завдань.

Перейдемо до розгляду конкретних економічних властивостей оцінок y i оптимального плану. Спочатку перерахуємо ці властивості, а потім проілюструємо їх конкретними прикладами.

Властивість 1. Оцінки як міра дефіцитності ресурсів і продукції.

Властивість 2. Оцінки як міра впливу обмежень на функціонал.

Властивість 3. Оцінки як інструмент визначення ефективності окремих варіантів.

Властивість 4. Оцінки як інструмент балансування сумарних витрат і результатів.

Приклад 3.2 (завдання про плануванні випуску тканин). Нехай деяка фабрика випускає три види тканин, причому добове планове завдання становить не менше 90 м тканин першого виду, 70 м - другого і 60 м - третього. Добові ресурси наступні: 780 одиниць виробничого устаткування, 850 одиниць сировини і 790 одиниць електроенергії, витрата яких на один метр тканини представлений в табл. 3.2.

Таблиця 3.2

Норми витрати ресурсів

Ресурси

Тканини

I

II

III

Устаткування

2

3

4

Сировина

1

4

5

Електроенергія

3

4

2

Ціна за один метр тканини виду I дорівнює 80 грошовим одиницям, II - 70 грошовим одиницям, III - 60 грошовим одиницям.

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

Рішення. Складемо модель задачі. Введемо наступні позначення. Невідомими в задачі є обсяги випуску тканини кожного виду:

х 1 - кількість метрів тканини виду I;

х 2 - кількість метрів тканини виду II;

х 3 - кількість метрів тканини виду III.

З урахуванням наявних даних модель прийме вигляд:

У результаті рішення задачі симплексним методом отриманий наступний оптимальний план: максимум загальної вартості продукції ден. од. досягається при

х 1 = 112,5 м - оптимальний обсяг випуску тканини виду I; х 2 = 70 м - оптимальний обсяг випуску тканини виду II; х 3 = 86,25 м - оптимальний обсяг випуску тканини виду III. Рішення двоїстої задачі отримаємо з використанням теорем подвійності. Введемо позначення:

y 1 - двоїста оцінка ресурсу "обладнання";

y 2 - двоїста оцінка ресурсу "сировину";

y 3 - двоїста оцінка ресурсу "електроенергія";

y 4 - двоїста оцінка тканини виду I;

у 5 - двоїста оцінка тканини виду II;

y 6 - двоїста оцінка тканини виду III.

Модель двоїстої задачі має вигляд:

Зі співвідношень другий теореми подвійності випливають такі умови:

для кожного ресурсу:

для завдання щодо випуску продукції:

(3.12)

Для нашого прикладу в цих співвідношеннях т = 3 (кількість типів ресурсів).

Підставимо значення х 1 = 112,5, х 2 = 70 і х 3 = 86,25 в обмеження прямої задачі:

2 • 112,5 + 3-70 + 4-86,25 = 780,

112.5 + 4 - 70 + 5 • 86,25 = 823,75 <850,

3 - 112,5 + 4 - 70 + 2 - 86,25 = 790,

112,5> 90,

70 = 70,

86,25> 60.

Добові ресурси по обладнанню та електроенергії використані повністю. Сировина використовується не повністю, є залишок у розмірі 850 - 823,75 = 26,25 (кг). План випуску по тканинах виду I і III перевиконано.

З другої теореми подвійності випливає, що у 2, у 4 і у 6 дорівнюють нулю. Залишається знайти значення у 1, у 3 і у 5. Так як х 1, х 2 і х 3 - більше нуля, то всі три обмеження двоїстої задачі виконуються як рівності:

Враховуючи, що, маємо:

звідки

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

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

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

Обмежують цільову функцію дефіцитні ресурси, в даному прикладі - обладнання та електроенергія. Вони повністю використані в оптимальному плані. За умовою (3.10) оцінка таких ресурсів позитивна (). Розглянемо тепер поняття дефіцитності продукції. За умовою (3.12) нульову оцінку () отримує продукція, завдання щодо випуску якої в оптимальному плані перевиконуються. Очевидно, перевиконання плану доцільно але вигідною продукції (тканини I і III видів), тобто такий, виробництво якої сприяє досягненню максимуму критерію оптимальності. Розміри виробництва такою вигідною продукції визначаються не величиною завдання на випуск () (в оптимальному плані вони перекриті), а обмеженістю дефіцитних ресурсів. Цю продукцію випускають якомога більше, поки вистачить ресурсів. Випуск вигідною продукції лімітується не тільки фактом обмеженості дефіцитних ресурсів, але й тим, що частина дефіцитних ресурсів треба виділити на забезпечення випуску невигідною продукції відповідно до плановими завданнями. За умовою (3.12) негативну оцінку () отримує продукція, завдання, з випуску якої, чи не перевиконуються. Оскільки за умовою задачі () планові завдання повинні бути обов'язково виконані, то продукція ділиться на вигідну (види I і III тканини) і невигідну (вид II тканини).

Якщо в обмеження двоїстої задачі, що відноситься до виду II тканини,

підставити отримані значення двоїстих оцінок, то отримуємо

3-2,5 + 4-0 + 4-25-37,5 = 70,

107,5-37,5 = 70,

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

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

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

Вплив обмежень щодо випуску продукції на критерій оптимальності протилежно впливу обмежень по ресурсах. Якщо продукція невигідна (вид II тканини, у 5 = -37,5), то збільшення планових завдань по її випуску веде до зменшення випуску вигідною продукції і погіршує план. Навпаки, зменшення планових завдань за невигідною продукції дозволяє знизити її випуск, перекинути зекономлені ресурси па додатковий надплановий випуск вигідних видів продукції, що збільшує значення цільової функції. Зміна планових завдань за вигідною продукції не змінює значення цільової функції.

Перейдемо до аналізу моделі на чутливість.

Приклад 3.3. На підставі інформації, наведеної в табл. 3.3, скласти план виробництва, максимізує обсяг прибутку.

Таблиця 3.3

Ресурси

Витрати ресурсів на одиницю продукції

Наявність

ресурсів

А

А

Праця

2

4

2000

Сировина

4

1

1 400

Устаткування

2

1

800

Прибуток на одиницю продукції

40

60

Рішення. Економіко-математична модель задачі матиме вигляд:

У результаті рішення задачі симплексним методом було отримано наступний оптимальний план:

Відповідний звіт про стійкість рішення представлений на рис. 3.2.

Звіт про стійкість

Мал. 3.2. Звіт про стійкість

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

1. Збільшення обсягів якого виду ресурсів найбільш вигідно?

2. Наскільки можна збільшити запас сировини для поліпшення отриманого оптимального значення цільової функції?

3. Який діапазон зміни того чи іншого коефіцієнта цільової функції, при якому не відбувається зміни оптимального рішення?

4. Доцільність включення в план нових виробів.

Постараємося послідовно відповісти на всі поставлені питання.

 
Якщо Ви помітили помилку в тексті позначте слово та натисніть Shift + Enter
< Попередня   ЗМІСТ   Наступна >
data-override-format="true" data-page-url = "http://stud.com.ua">

Cхожі теми

Перша теорема подвійності
Теорема Хекшера - Оліна
Основні теореми і положення алгебри логіки
Друга теорема подвійності (теорема про доповнює нежорсткості)
Теорема Хекшера - Оліна
Основні теореми і положення алгебри логіки
Теорема про оцінки (третя теорема подвійності)
Теорема Хекшера - Оліна
Методи опуклого математичного програмування і умовні нелінійні оцінки
 
Дисципліни
Агропромисловість
Аудит та Бухоблік
Банківська справа
БЖД
Географія
Документознавство
Екологія
Економіка
Етика та Естетика
Журналістика
Інвестування
Інформатика
Історія
Культурологія
Література
Логіка
Логістика
Маркетинг
Медицина
Нерухомість
Менеджмент
Педагогіка
Політологія
Політекономія
Право
Психологія
Релігієзнавство
Риторика
Соціологія
Статистика
Техніка
Страхова справа
Товарознавство
Туризм
Філософія
Фінанси
Пошук