Автор работы: Пользователь скрыл имя, 19 Марта 2014 в 13: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
Список використаних джерел………………………………
Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани та відповідних спряжених задач були оптимальними, необхідно і достатньо, щоб виконувалися умови доповнюючої нежорсткості:
Економічний зміст другої теореми двоїстості стосовно оптимального плану прямої задачі. Якщо для виготовлення всієї продукції в обсязі, що визначається оптимальним планом , витрати одного і-го ресурсу строго менші, ніж його загальний обсяг , то відповідна оцінка такого ресурсу (компонента оптимального плану двоїстої задачі) буде дорівнювати нулю, тобто такий ресурс за даних умов для виробництва не є «цінним».
Якщо ж витрати ресурсу дорівнюють його наявному обсягові , тобто його використано повністю, то він є « цінним» для виробництва, і його оцінка буде строго більшою від нуля.
Економічне тлумачення другої теореми двоїстості щодо оптимального плану двоїстої задачі: у разі, коли деяке - те обмеження виконується як нерівність, тобто всі витрати на виробництво одиниці - го виду продукції перевищують її ціну , виробництво такого виду продукції є недоцільним, і в оптимальному плані прямої задачі обсяг такої продукції дорівнює нулю.
Якщо витрати на виробництво -го виду продукції дорівнюють ціні одиниці продукції , то її необхідно виготовляти в обсязі, який визначає оптимальний план прямої задачі
Існування двоїстих змінних уможливлює зіставлення витрат на виробництво і цін на продукцію, на підставі чого обґрунтовується висновок про доцільність чи недоцільність виробництва кожного виду продукції. Крім цього, значення двоїстої оцінки характеризує зміну значення цільової функції, що зумовлена малими змінами вільного члена відповідного обмеження. Дане твердження формулюється у вигляді такої теореми[14].
Теорема (третя теорема двоїстості). Компоненти оптимального плану двоїстої задачі дорівнюють значенням частинних похідних від цільової функції за відповідними аргументами або
Економічний зміст третьої теореми двоїстості. Двоїсті оцінки є унікальним інструментом, який дає змогу зіставляти непорівнянні речі Очевидно, що неможливим є просте зіставлення величин, які мають різні одиниці вимірювання. Якщо взяти як приклад виробничу задачу, то цікавим є питання: як змінюватиметься значення цільової функції (може вимірюватися в грошових одиницях) за зміни обсягів різних ресурсів (можуть вимірюватися в тоннах, люд./год, га тощо).
Використовуючи третю теорему двоїстості, можна легко визначити вплив на зміну значення цільової функції збільшення чи зменшення обсягів окремих ресурсів: числові значення двоїстих оцінок показують, на яку величину змінюється цільова функція за зміни обсягу відповідного даній оцінці ресурсу:
Кожну з двох спряжених задач можна розв’язати окремо, проте встановлені теоремами двоїстості залежності між оптимальними планами прямої та двоїстої задач уможливлюють знаходження розв’язку двоїстої задачі за наявності оптимального плану, і навпаки[14].
РОЗДІЛ 2
ТЕОРІЯ ДВОЇСТОСТІ ДЛЯ ЗАДАЧ НЕЛІНІЙНОГО ПРОГРАМУВАННЯ
Теорія двоїстості в задачах нелінійного програмування виглядає наступним чином:
при обмеженнях:
Ввівши функцію Лагранджа , можна записати цю задачу в еквівалентному вигляді:
при обмеженнях:
За аналогією з лінійним програмуванням назвемо таку задачу:
при обмеженнях:
двоїстою до задачі (2.3) - (2.4).
Має місце
теорема, аналогічна теоремі двоїстості
ЛП, вперше доведена П.Вульфом.
Теорема 2.1. Нехай функції
,
,
, опуклі та диференційовані в
і виконуються умови регулярності.
Якщо пряма задача (2.1) - (2.2) має розв’язок
, то в двоїстій задачі (2.6) існує такий
вектор
, який є її оптимальним розв’язком
і при цьому екстремуми пари двоїстих
задач рівні між собою.
Для ілюстрації цієї теореми розглянемо задачу квадратичного програмування:
де С – симетрична, від’ємно визначена матриця. Перетворимо (2.7) - (2.8) в еквівалентну задачу мінімізації і побудуємо функцію Лагранджа:
Вихідну задачу можна записати у такому вигляді:
Неважко показати, що задача (2.10) - (2.11) еквівалентна задачі (2.7) - (2.8).
За аналогією з лінійним програмуванням запишемо двоїсту задачу для задачі квадратичного програмування:
при обмеженнях:
Підставляючи вираз для із (2.9) в (2.12) і (2.13), отримаємо таку форму запису двоїстої задачі:
Оптимальні розв’язки та зв’язані між собою співвідношеннями:
Використовуючи вираз (2.9) і підставляючи його в (2.16) та (2.17), знаходимо відповідно:
Покажемо, що задачі (2.7) - (2.8) і (2.14) - (2.15) справді є двоїстими і виконується твердження теореми про те, що
Оскільки звя’зані між собою співвідношеннями (2.18) та (2.19), то маємо
або
Таким чином, встановлено справедливість відношення (2.20) і теореми (2.1) [11].
ЕКОНОМІЧНА ІНТЕРПРЕТАЦІЯ ДВОЇСТИХ ОЦІНОК І ЇХ ЗАСТОСУВАННЯ ДЛЯ ЕКОНОМІЧНИХ ЗАДАЧ
Кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Теоремами двоїстості встановлено зв’язок між розв’язками прямої та двоїстої задач. Для знаходження розв’язку однієї зі спряжених задач можна перейти до двоїстої і, використовуючи її оптимальний план, визначити оптимальний план початкової.
Перехід до двоїстої задачі не обов’язковий. Легко помітити, що звичайна симплексна таблиця в стовпчиках містить початкову задачу, а в рядках - двоїсту. Оцінками плану прямої задачі є рядок , (j= ), а оцінками плану двоїстої - стовпчик «План» з компонентами вектора вільних членів системи обмежень В. Отже, розв’язуючи пряму задачу, симплексний метод дає змогу одночасно знаходити і розв’язок двоїстої задачі. Однак двоїсту задачу можна також розв’язати за таблицею, в якій записана пряма, а відшукавши оптимальний план двоїстої задачі, разом з тим отримати розв’язок початкової задачі. Такий спосіб розв’язання задачі лінійного програмування має назву двоїстого симплексного методу. Прямий та двоїстий симплексні методи пов’язані між собою.
Нехай необхідно розв’язати задачу лінійного програмування:
Тоді двоїстою до неї буде така задача:
За алгоритмом двоїстого симплексного методу як перший опорний план вибирається деякий допустимий розв’язок двоїстої задачі (іноді в літературі його називають «псевдопланом») і зберігається його допустимість для двоїстої задачі упродовж всіх кроків.
Допустимо,
що початковий базис складається з m векторів D=(
) , причому
хоча б одна з компонент вектора
Отже, вектор, що відповідає компоненті >0, потрібно виключити з базису початкової задачі, а вектор двоїстої задачі, що відповідає від’ємній оцінці, включити до базису двоїстої.
У прямому симплекс-методі спочатку виявляють змінну, яку слід ввести у базис, а в двоїстому симплекс-методі навпаки - спочатку визначають змінну, яку виключають з базису, а потім змінну, яку вводять у базис.
У літературі зустрічаються різні варіанти двоїстого симплексного методу, які не мають принципових відмінностей.
Розглянемо такий алгоритм двоїстого симплексного методу:
1. Необхідно звести всі обмеження задачі до виду «≤ », ввести додаткові невід’ємні змінні, визначити початковий базис та перший опорний план X=( ).
2. Якщо всі оцінки векторів ≤ 0 і компоненти вектора-стовпчика «План» ( ) ≥ 0 для всіх i= , то задача розв’язана. Інакше необхідно вибрати найбільшу за модулем компоненту <0 і відповідну змінну виключити з базису.
3. Якщо в першому рядку, що відповідає змінній , не міститься жодного , то цільова функція двоїстої задачі необмежена на багатограннику розв’язків, а початкова задача розв’язку не має. Інакше існують деякі і тоді для відповідних стовпчиків визначають аналогічно прямому симплекс-методу оцінки :
(
що дає змогу вибрати вектор, який буде включено в базис.
4. Виконавши крок методу повних виключень Жордана-Гаусса, переходять до наступної симплексної таблиці (переходять до пункту 2).
Зазначимо, що для задачі знаходження максимального значення цільової функції за наведеним алгоритмом необхідно перейти до цільової функції , або дещо змінити сам алгоритм.
Зауважимо, що здебільшого двоїстий симплексний метод за кількістю ітерацій не кращий, ніж звичайний. Однак, в окремих задачах він дає змогу спростити розрахунки. Завдяки двоїстому симплекс-методу розв’язування задачі простіше, зменшена кількість ітерацій.
Крім того, двоїстий симплексний метод буває вигіднішим для розв’язування задач, що випливають з уже розв’язаних, наприклад, якщо введенням кількох нових обмежень уточнюють задачу або ж пристосовують її до змінених реальних умов[2,7,15].
3.2 Двоїстість і аналіз чутливості
За таких умов:
До складу n змінних входять також додаткові змінні. Стандартна форма задачі лінійного програмування передбачає виконання таких умов:
1. Всі обмеження записані у вигляді рівності (з невід’ємною правою частиною).
2. Всі змінні невід’ємні.
3. Оптимізація визначається як максимізація або мінімізація цільової функції.
Змінні і обмеження двоїстої завдання формуються шляхом симетричних структурних перетворень прямої задачі за такими правилами:
1. Кожному з m обмежень прямої задачі відповідає змінна двоїстої задачі.
2. Кожна з n змінних прямої задачі відповідає обмеження двоїстої завдання.
3. Коефіцієнти при будь-якій змінної в обмеженнях прямої задачі, відповідної цієї змінної, а права частина формованого обмеження дорівнює коефіцієнту при змінної у виразі цільової функції.
4. Коефіцієнти цільової функції двоїстої задачі рівні правим частинам обмеження прямої задачі[9].
3.3 Економічна інтерпретація обмежень двоїстої задачі
Для розв’язання прямої задачі справедливою є рівність:
Коефіцієнт при в z + рядку рівний:
Для інтерпретації цієї рівності скористаємося аналізом розмірностей вхідних до нього величин.
Коефіцієнт - дохід на одиницю «виходу» j-го виду виробничо діяльності. Далі, оскільки представляє дохід, сума , яка входить в рівність з протилежним знаком, повинна відповідати витратам.