Размещено на http://www.allbest.ru/

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

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

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

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

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

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

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

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

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

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

Моргун К.А.

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

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

м. Львів 2013 р.

РЕФЕРАТ

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

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

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

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

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

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

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



ЗМІСТ

ВСТУП

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

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

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

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

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

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

3.1 Двоїстий симплексний метод

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

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

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

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

РОЗДІЛ 4. ПРАКТИЧНА РЕАЛІЗАЦІЯ ЗАДАЧІ ОПТИМАЛЬНОГО РОЗПОДІЛУ РЕСУРСІВ ІЗ ЗАСТОСУВАННЯМ ТЕОРІЇ ДВОЇСТОСТІ

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

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

ВИСНОВКИ

СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ



ВСТУП

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

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

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

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

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



РОЗДІЛ 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].

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани та відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:

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

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

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

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

Існування двоїстих змінних уможливлює зіставлення витрат на виробництво і цін на продукцію, на підставі чого обґрунтовується висновок про доцільність чи недоцільність виробництва кожного виду продукції. Крім цього, значення двоїстої оцінки характеризує зміну значення цільової функції, що зумовлена малими змінами вільного члена відповідного обмеження. Дане твердження формулюється у вигляді такої теореми[14].

Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі дорівнюють значенням частинних похідних від цільової функції за відповідними аргументами або

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

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

.

Кожну з двох спряжених задач можна розв'язати окремо, проте встановлені теоремами двоїстості залежності між оптимальними планами прямої та двоїстої задач уможливлюють знаходження розв'язку двоїстої задачі за наявності оптимального плану, і навпаки[14].



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

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

, (2.1)

при обмеженнях:

. (2.2)

Ввівши функцію Лагранджа , можна записати цю задачу в еквівалентному вигляді:

, (2.3)

при обмеженнях:

. (2.4)

За аналогією з лінійним програмуванням назвемо таку задачу:

(2.5)

при обмеженнях:



(2.6)

двоїстою до задачі (2.3) - (2.4).

Має місце теорема, аналогічна теоремі двоїстості ЛП, вперше доведена П.Вульфом.

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

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

, (2.7)

(2.8)

де С - симетрична, від'ємно визначена матриця. Перетворимо (2.7) - (2.8) в еквівалентну задачу мінімізації і побудуємо функцію Лагранджа:

(2.9)

Вихідну задачу можна записати у такому вигляді:

(2.10)



(2.11)

Неважко показати, що задача (2.10) - (2.11) еквівалентна задачі (2.7) - (2.8).

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

(2.12)

при обмеженнях:

. (2.13)

Підставляючи вираз для із (2.9) в (2.12) і (2.13), отримаємо таку форму запису двоїстої задачі:

, (2.14)

, . (2.15)

Оптимальні розв'язки та зв'язані між собою співвідношеннями:

(2.16)

(2.17)

Використовуючи вираз (2.9) і підставляючи його в (2.16) та (2.17), знаходимо відповідно:

(2.18)

(2.19)

Покажемо, що задачі (2.7) - (2.8) і (2.14) - (2.15) справді є двоїстими і виконується твердження теореми про те, що

. (2.20)

Оскільки звя'зані між собою співвідношеннями (2.18) та (2.19), то маємо

,

або

Таким чином, встановлено справедливість відношення (2.20) і теореми (2.1) [11].



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

3.1 Двоїстий симплексний метод

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

Перехід до двоїстої задачі не обов'язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках - двоїсту. Оцінками плану прямої задачі є рядок , (j=), а оцінками плану двоїстої - стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв'язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв'язок двоїстої задачі. Однак двоїсту задачу можна також розв'язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв'язок початкової задачі. Такий спосіб розв'язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов'язані між собою.

Нехай необхідно розв'язати задачу лінійного програмування:

min F = CX, (3.1)

AX = B, (3.2)

X ? 0. (3.3)

Тоді двоїстою до неї буде така задача:



max Z = BY, (3.4)

YA ? C. (3.5)

За алгоритмом двоїстого симплексного методу як перший опорний план вибирається деякий допустимий розв'язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків.

Допустимо, що початковий базис складається з m векторівD=() , причому хоча б одна з компонент вектораX=B=() від'ємна. Нехай справджується критерій оптимальності плану, тобто всі оцінки векторів , (j=). На підставі першої теореми двоїстості план двоїстої задачі відшукуємо у вигляді: Y=. Цей план не є оптимальним для прямої задачі, оскільки він не задовольняє умову невід'ємності змінних і не є оптимальним для двоїстої задачі, бо всі оцінки векторів оптимального плану двоїстої задачі мають бути невід'ємними.

Отже, вектор, що відповідає компоненті >0, потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від'ємній оцінці, включити до базису двоїстої.

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

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

Розглянемо такий алгоритм двоїстого симплексного методу:

1. Необхідно звести всі обмеження задачі до виду «? », ввести додаткові невід'ємні змінні, визначити початковий базис та перший опорний план X=(). програмування економічний математичний двоїстий

2. Якщо всі оцінки векторів ? 0 і компоненти вектора-стовпчика «План» () ? 0 для всіх i=, то задача розв'язана. Інакше необхідно вибрати найбільшу за модулем компоненту <0 і відповідну змінну виключити з базису.

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

,

(<0),

що дає змогу вибрати вектор, який буде включено в базис.

4. Виконавши крок методу повних виключень Жордана-Гаусса, переходять до наступної симплексної таблиці (переходять до пункту 2).

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

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

Крім того, двоїстий симплексний метод буває вигіднішим для розв'язування задач, що випливають з уже розв'язаних, наприклад, якщо введенням кількох нових обмежень уточнюють задачу або ж пристосовують її до змінених реальних умов[2,7,15].

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

За таких умов:

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

1. Всі обмеження записані у вигляді рівності (з невід'ємною правою частиною).

2. Всі змінні невід'ємні.

3. Оптимізація визначається як максимізація або мінімізація цільової функції.

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

1. Кожному з m обмежень прямої задачі відповідає змінна двоїстої задачі.

2. Кожна з n змінних прямої задачі відповідає обмеження двоїстої завдання.

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

4. Коефіцієнти цільової функції двоїстої задачі рівні правим частинам обмеження прямої задачі[9].



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

Для розв'язання прямої задачі справедливою є рівність:

Коефіцієнт при в z + рядку рівний:

=.

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

Коефіцієнт - дохід на одиницю «виходу» j-го виду виробничо діяльності. Далі, оскільки представляє дохід, сума , яка входить в рівність з протилежним знаком, повинна відповідати витратам.

В той же час коефіцієнт дорівнює кількості ресурсу i-го виду, використаного на підтримку j-го виду діяльності;

А мінлива представляє осудні витрати (осудну вартість) одиниці ресурсу i. Таким чином, величина відповідає сумарній вартості всіх ресурсів, необхідних для виробництва j-го виду діяльності.

Умова оптимальності симплекс-методу в задачі максимізації говорить про те, що j-й вид діяльності (змінна ), не наданих у поточному базисному розв'язку, можна ввести в базис для збільшення доходу тільки тоді, коли коефіцієнт при в z рядку буде невід'ємним. У рамках пропонованої економічної інтерпретації це означає, що j-й вид діяльності повинен бути представлений у базисному розв'язку, якщо виконується наступна нерівність:

Вартість всіх ресурсів, використаних для виробництва одиниці продукції j-го виду діяльності < Доходу від реалізації одиниці продукції j-го виду діяльності

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

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

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

L max (b₁, b₂, …, b_m).

Теорема. В оптимальному плані двоїстої задачі значення змінної u_i чисельно дорівнює частинній похідній функції L max (b₁, b₂, …, b_m) за відповідним аргументом b_i:

.

Це означає, що зміна значень величини b_i приведе до збільшення або зменшення L max (b₁, b₂, …, b_m) при незмінної |u_i| у відповідному оптимальному плані двоїстої задачі.

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

План двоїстої задачі не змінюється для всіх значень b_i + b_i, при яких стовпець вектора Р₀ останньої симплекс-таблиці не містить від'ємних чисел, тобто коли серед компонентів вектора немає від'ємних.

b1 + b1
b2 + b2
…………
bm + bm

В^-1 - матриця, зворотна матриці В, укладеної з компонентів векторів базису, який визначає оптимальний план задачі[13].

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

За описаними в попередньому параграфі правилами побудуємо двоїсту задачу:



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

Двоїста задача має дві змінні, а отже, її можна розв'язати графічно (зображено на рис. 3.1).

Рис. 3.1. Графічний розв'язок двоїстої задачі

Найбільшого значення цільова функція двоїстої задачі F досягає в точці В багатокутника ABCD. Її координати визначимо розв'язанням системи рівнянь:

Отже,

Оптимальний план прямої задачі визначимо за допомогою співвідношень другої теореми двоїстості.

Підставимо у систему обмежень двоїстої задачі і з'ясуємо, як виконуються обмеження цієї задачі:

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

Тепер проаналізуємо оптимальний план двоїстої задачі. Оскільки друга компонента плану додатна, то друге обмеження прямої задачі для виконуватиметься як строге рівняння (друга частина другої теореми двоїстості).

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

тобто

Умова виконується, і тому є оптимальними планами відповідно прямої та двоїстої задачі[6].



РОЗДІЛ 4. ПРАКТИЧНА РЕАЛІЗАЦІЯ ЗАДАЧІ ОПТИМАЛЬНОГО РОЗПОДІЛУ РЕСУРСІВ ІЗ ЗАСТОСУВАННЯМ ТЕОРІЇ ДВОЇСТОСТІ

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

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

Для виготовлення трьох видів пива: «Львівське», «Оболонь» та «Балтика» використовують три різні види сировини: дріжджі, хміль та солод. Кожен з видів сировини може бути використаний в кількості, не більшій ніж 180, 210 та 244 кг відповідно. Норми витрат кожного з видів сировини на одиницю продукції даного виду та ціна одиниці продукції кожного з видів наведені в таблиці 4.1.

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

Таблиця 4.1

Норми затрат сировини на одиницю продукції

Вид сировини	«Львівське»	«Оболонь»	«Балтика»
Дріжджі	4	2	1
Хміль	3	1	3
Солод	1	2	5
Ціна одиниці продукції(грн)	10	14	12

Нехай виготовляють х₁ виробів «Львівське», х₂ виробів «Оболонь» та х₃ виробів «Балтика». Для визначення оптимального плану виробництва потрібно розв'язати задачу на максимізацію цільової функції

F=10 х₁+14 х₂+12 х₃,

при таких умовах:

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

За умовою задачі, повинні задовольняти наступну систему нерівностей:

Отримали симетричну пару двоїстих задач. Розв'язання прямої задачі дає оптимальний план виготовлення виробів «Львівське», «Оболонь» та «Балтика», а розв'язання двоїстої - оптимальну систему оцінок сировини, яка використовується для виготовлення цих виробів. Щоб розв'язати ці задачі, необхідно спочатку знайти розв'язок однієї з них. Розв'яжемо пряму задачу (її система обмежень містить лише нерівності виду «»). Її розв'язання наведено в таблиці 4.2.



Таблиця 4.2

Остання симплексна таблиця із оптимальним планом

і	Базис	Сб	Х0	10	14	12	0	0	0
				х1	х2	х3	х4	х5	х6
1	х2	14	82		1	0		0
2	х5	0	80		0	0		1
3	х3	12	16		0	1		0
	1340		0	0		0

З даної таблиці видно, що оптимальним планом виготовлення виробів є такий план, при якому виготовляються 82 виробів «Оболонь» та 16 виробів «Балтика». В цьому випадку залишається невикористаним 80 кг хмелю, а загальна вартість виробів дорівнює 1340 грн. З таблиці 4.2 також видно, що оптимальний розв'язок двоїстої задачі має вигляд: Змінні та є умовними двоїстими оцінками сировини, дріжджів та солоду відповідно. Ці оцінки відмінні від нуля, а сировина дріжджі і солод повністю використовується при оптимальному плані виготовлення продукції. Двоїста оцінка одиниці хмелю дорівнює нулю. Цей вид сировини не повністю використовується при оптимальному плані виробництва продукції.

Таким чином, додатну двоїсту оцінку мають лише ті види сировини, які повністю використовуються при оптимальному плані виробництва продукції. Тому двоїсті оцінки визначають дефіцитність сировини що використовує підприємство. Більш того, величина даної двоїстої оцінки показує, на скільки зростає максимальне значення цільової функції прямої задачі при збільшенні кількості сировини відповідного виду на 1 кг. Так, збільшення кількості дріжджів на 1 кг призведе до появи можливості знайти новий оптимальний план виготовлення виробів, при якому загальна вартість виготовленої продукції зросте на 5,75 грн і становитиме 1340+5,75=1345,75 грн. При цьому числа, що стоять в стовпці вектора х₄ наведено в (табл. 4.2), показують, що таке збільшення загальної вартості виготовленої продукції може бути досягнуто за рахунок збільшення випуску пива «Оболонь» на од. та скорочення випуску пива «Балтика» на од. Внаслідок цього використання хмелю зменшиться на кг. Аналогічно, збільшення на 1 кг солоду дозволить знайти новий оптимальний план виготовлення виробів, при якому загальна вартість виготовленої продукції зросте на 1,25 грн і становитиме 1340+1,25=1341,25 грн. Це буде досягнуто внаслідок збільшення випуску пива «Балтика» на од. та зменшенні виготовлення пива «Оболонь» на од., причому об'єм хмелю зросте на кг.

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

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

Перше обмеження двоїстої задачі виконується як строга нерівність. Це означає, що двоїста оцінка сировини, що йде на виготовлення одного виробу «Львівське», вища ціни цього виробу, отже, випускати ці вироби невигідно. Його виготовлення й непередбачено оптимальним планом прямої задачі. Друге й третє обмеження двоїстої задачі виконуються як строгі рівності. Це означає, що двоїста оцінка сировини, що використовується для виготовлення пива «Оболонь» та «Балтика» відповідно, дорівнюють їх цінам. Тому випускати ці два види продукції по двоїстим оцінкам економічно вигідно. Їх виготовлення й передбачено оптимальним планом прямої задачі.

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

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

Розв'язок поставленої вище задачі можливо здійснити за допомогою програмного пакету MS EXCEL:Умови задачі оптимального розподілу ресурсів зображено на рис. 4.1.



Рис. 4.1. Умова задачі оптимального розподілу ресурсів

Згідно з умовою змінні значення позначені наступним чином:

B1: D1 - вид продукції;

A2: A4 - вид ресурсу;

B2: D4 - витрати ресурсів на одиницю продукції;

B6: D6 - ціни на продукцію;

B8: D8 - змінні;

F2: F4 - запас ресурсів;

G6 - значення цільової функції.

Для того, щоб записати двоїсту задачу до даної потрібно перезаписати умову, як зображено на рис. 4.2.



Рис. 4.2. Умова двоїстої задачі

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

1. Цільова комірка - G4;

2. Включити кнопку «мінімальне значення»;

3. Вказати змінювані клітинки (розташування змінних) - $B$2:$D$2;

4. Записати обмеження.

Обмеження можна записати в цьому ж вікні, але краще вибрати кнопку «додати» і у вікні «додати» записати їх послідовно. Одне обмеження на невід'ємність зміних:

$B$2:$D$2>=0,

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

$G$6>=$F$6,

$G$7>=$F$7,

$G$8>=$F$8.

Приклад запису параметрів «пошуку рішень» зображений на рис. 4.3.

Рис.4.3. Параметри «пошуку рішень»

Тепер електронна модель сформована і можна розв'язувати задачу. Для цього потрібно повернутися до вікна «пошук рішення» і натиснути «виконати». Якщо електронна модель сформована правильно, то буде отримано повідомлення, що завдання виконане. Результат розв'язку знаходиться на аркуші EXCEL (див. рис. 4.4.).



Рис. 4.4. Результати розв'язку задачі

Порівнявши результати обох методів розв'язування задачі було отримано спільний розв'язок.



ВИСНОВКИ

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

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

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

Результатом роботи над курсовим проектом є програма розв'язку задачі лінійного програмування за допомогою двоїстого симплекс-методу. А також її реалізація в програмі MS Excel.

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



СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ

1. Акулич М.Л. Математическое програмирование в примерах и задачах: Учеб. пос. для студ. эконом. спец. / И.А. Акулич - М. : Высшая школа, 1986. - 319 с.

2. Вітлінський В.В. Математичне програмування - Навчально- методичний посібник для самост. вивч. дисц. / В.В. Вітлінський, С.І. Наконечний, Т.О. Терещенко -вид. 2-ге без змін - Київ: КНЕУ, 2006. - 248 с.

3. Дацко М.В. Дослідження операцій. Навч. пос. / М.В. Дацко, М.М. Карбовник - Львів : “ПАЇС”, 2009. - 288 с.

4. Дегтярев В.И. Исследование операций: Уч. для вузов по спец АСУ / В.И. Дегтярев - М. : Высшая школа, 1986. - 320 с.

5. Зайченко Ю.П. Дослідження операцій / Ю.П. Зайченко - Київ : ЗАТ “Віпол”, 2000. - 688 с.

6. Калихман И.Л. Сборник задач по математическому програмированию / И.Л. Калихман - М. : Высшая школа, 1986. - 270 с.

7. Карагодова О.О. Дослідження операцій: Навч. пос. / О.О. Карагодова, В.Р. Кігель, В.Д. Рожок - К. : ЦУЛ, 2007. - 256 с.

8. Кутковецький В.Я. Дослідження операцій: Навчальний посібник / В.Я. Кутковецький - Київ : Вид-во ТОВ “Видавничий дім “Професіонал”, 2004. - 350с.

9. Машина Н.І. Математичні методи в економіці: Навч. пос. / Н.І. Машина- К. : Центр навч. л-ри, 2003. - 148с.

10. Наконечний С.І. Математичне програмування: Навч. посіб. / С.І. Наконечний, С.С. Савіна - К. : КНЕУ, 2003. - 452с.

11. Новиков В.Р. Экономико-математические методы: Навч. пос. / В.Р. Новиков - М. : Дело, 2000. - 177 c.

12. Охріменко М.Г. Дослідження операцій: Навч. пос. / М.Г. Охріменко, І.Ю. Дзюбан - К. : Центр навч. л-ри, 2006. - 184 с.

13. Ульянченко О.В. Дослідження операцій в економіці. Підручник для студ. вузів / О.В. Ульянченко - Харків : Гриф, 2002. - 580 с.

14. Федоренко І.К. Дослідження операцій в економіці: Підручник / І.К. Федоренко, О.І. Черняк - К. : Знання, 2007. - 558 с.

15. Шикин Е.В., Математические методы и модели в управлении: Учебное пособие / Е.В. Шикин, Л.Г. Чхартишвили - М. : Дело, 2001. - 440с.

Размещено на Allbest.ru

...