Двоїстість в оптимізаційних задачах

 

 

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

ЛЬВІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

ІМЕНІ ІВАНА ФРАНКА

Кафедра економічної кібернетики

 

 

 

 

 

 

КУРСОВА РОБОТА

 

з дисципліни “Дослідження операцій”

на тему:

“ Двоїстість в оптимізаційних задачах”

 

 

 

 

Студентки   3 курсу групи Екк-31

напряму підготовки

6.030502 “Економічна кібернетика”

Моргун К.А.

Керівник:

доцент кафедри економічної кібернетики,

к.е.н.  доц. Артим-Дрогомирецька З.Б.

Національна шкала ________________   

Кількість балів: _________Оцінка:  ECTS

                

Члени комісії             

                                    _____________               ___________________________

                                                                  (підпис)                                                  (прізвище та ініціали)

                                      

                                      _____________               ___________________________                               

                                               (підпис)                                                    (прізвище та ініціали)

 

                                      _____________               ___________________________           

                                               (підпис)                                                  (прізвище та ініціали)

 

 

 

 

 

 

м. Львів – 2013 р.

 

РЕФЕРАТ

Курсова робота: загальний обсяг роботи – 36 сторінок, 5 рисунків, 2 таблиці, 15 джерел літератури.

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

Предметом дослідження є аналіз теорії двоїстості та її застосування в аналізі економічних задач.

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

У роботі використано наступні методи дослідження: методи економічного та математичного аналізу, економіко-математичного моделювання, системного аналізу.

Значимість даної роботи полягає в детальному вивченні властивостей двоїстих задач і  їх застосування для розв’язування задач лінійного та нелінійного програмування

 

ПРЯМА ЗАДАЧА, ДВОЇСТА ЗАДАЧА, ТЕОРЕМИ ДВОЇСТОСТІ, ДВОЇСТІ ОЦІНКИ,  ЕКОНОМІЧНА ІНТЕРПРЕТАЦІЯ.

 

 

 

ЗМІСТ

Вступ………………………………………………………………………………4

1. Теорія двоїстості для задач лінійного програмування…………………...5

1.1 Економічна інтерпретація прямої та двоїстої задач лінійного програмування……………………………………………………………...5

1.2 Правила побудови двоїстих задач…………………………………….7

1.3 Основні теореми двоїстості та їх економічний зміст………………...9

2. Теорія двоїстості для задач нелінійного програмування………………13

3. Розв’язок, аналіз та інтерпретація двоїстих задач………………………16

3.1 Двоїстий симплекс метод………………………………………….....16

3.2 Двоїстість  і аналіз чутливості………………………………………..19

3.3 Економічна  інтерпретація обмежень двоїстої  задачі……………….20

3.4 Аналіз  стійкості двоїстих оцінок…………………………………….21

3.5 Приклад розв’язування двоїстої задачі графічним методом……….22

4. Практична реалізація задачі оптимального розподілу ресурсів із застосуванням теорії двоїстості………………………………………………25

4.1 Економіко-математична постановка задачі оптимального розподілу ресурсів…………………………………………………………………….25

4.2 Програмна реалізація розв’язку задачі оптимального розподілу ресурсів в середовищі MS Excel…............................................................30

Висновки………………………………………………………………………...34

Список використаних джерел………………………………………………...35

ВСТУП

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

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

Предметом дослідження є аналіз теорії двоїстості та її застосування в аналізі економічних задач.

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

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

 

РОЗДІЛ 1

ТЕОРІЯ ДВОЇСТОСТІ ДЛЯ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1 Економічна інтерпретація прямої та двоїстої задач лінійного програмування

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

Економічну інтерпретацію кожної з таких задач розглянемо на прикладі виробничої задачі. Пряма задача:

 

 ,                                     (1.1)

                                   (1.2)

                                                  (1.3)

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

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

На виготовлення j-го виду продукції витрачається згідно з моделлю (1.1) - (1.3) m видів ресурсів у кількості відповідно . Оскільки ціна одиниці і-го виду ресурсу дорівнює , то загальна вартість ресурсів, що витрачаються на виробництво одиниці -го виду продукції, обчислюється у такий спосіб: .

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

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

.

Отже, в результаті маємо двоїсту задачу:

                                          

,                            (1.4)

                                            (1.5)

                                            

.                                                       (1.6)

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

Справжній зміст величини - умовні ціни, що виражають рівень «цінності» відповідного ресурсу для даного виробництва, або об’єктивно обумовлена оцінка відповідного ресурсу.

Задача (1.4) - (1.6) є двоїстою або спряженою до задачі (1.1) - (1.3), яку називають прямою (основною, початковою). Поняття двоїстої є взаємним. По суті мова йде про одну і ту ж задачу, але з різних поглядів. Дійсно, не важко переконатися, що двоїста задача до (1.4) - (1.6) збігається з початковою. Тому кожну з них можна вважати прямою, а іншу – двоїстою. Симетричність двох таких задач очевидна. Як у прямій, так і у двоїстій задачі використовують один набір початкових даних: , , . Крім того, вектор обмежень початкової задачі стає вектором коефіцієнтів цільової функції двоїстої задачі і навпаки, а рядки матриці А (матриці коефіцієнтів при змінних з обмежень прямої задачі) стають стовпцями матриці коефіцієнтів при змінних в обмеженнях двоїстої задачі. Кожному обмеженню початкової задачі відповідає змінна двоїстої і навпаки.

Початкова постановка задачі та математична модель може мати вигляд як (1.1) - (1.3), так і (1.4) - (1.6). Отже, як правило, кажуть про пару спряжених задач лінійного програмування[3,4,8,14].

1.2 Правило побудови двоїстої задачі

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

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

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення, то цільова функція двоїстої задачі – на визначення найменшого значення, і навпаки.
4. Коефіцієнтами при змінних цільової функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця , що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків – рядками.

Виділяють два основних види задач лінійного програмування: симетричні та несиметричні.

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

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

Різні можливі форми прямих задач лінійного програмування та відповідні їм варіанти моделей двоїстих задач:

Пряма задача	Двоїста задача
Симетричні

Несиметричні

 

 

 

 

 

 

 

 

 

 

1.3 Основні теореми двоїстості та їх економічний зміст

Зв’язок між оптимальними розв’язками прямої та двоїстої задач встановлюють леми та теореми двоїстості. Розглянемо задачі (1.1) - (1.3) та (1.4)-(1.6) з економічною інтерпретацією.

Лема 1.3.1 (основна нерівність теорії двоїстості). Якщо та - допустимі розв’язки відповідно прямої та двоїстої задач, то виконується нерівність

 або  .

Лема 1.3.2 (достатня умова оптимальності). Якщо та - допустимі розв’язки відповідно прямої та двоїстої задач, для яких виконується рівність , то - оптимальні розв’язки відповідних задач[10].

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

Якщо цільова функція однієї із задач необмежена, то спряжена задача також не має розв’язку. Слід зауважити, що коли одна із задач не має допустимого розв’язку, то двоїста до неї задача також може не мати допустимого розв’язку, тобто зворотне твердження щодо другої частини теореми в загальному випадку не виконується[12].

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