WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей - Реферат

Теорія двоїстості та двоїсті оцінки в аналізі розв’язків лінійних оптимізаційних моделей - Реферат


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1. Геометрична інтерпретація двоїстих задач.
2. Приклади розв'язування пари двоїстих задач.
3. Література
Економічна інтерпретація двоїстих задач.
Економічну інтерпретацію двоїстих задач і двоїстих оцінок розглянемо на прикладі.
Задача 1.1. Для виробнпицтва трьох видів предметів А, В і С використовують три види сировини.Кожний з видів сировини може бути використаний в кількості, відповідно не більше 180,210 і 244 кг. Норми затрат кожного з видів сировини на одиницю продукції даного виду і ціна одиниці продукції кожного виду наведені в таблиці.
Вид сировини Норми витрат сировини(кг.) на одиницю продукції
А В С
1 4 2 1
2 3 1 3
3 1 2 5
Ціна одиниці продукції(грн.) 10 14 12
Вибрати план випуска продукції , при якому забезпечується її максимальна вартість,і оцінити кожний вид сировини, який використаний для виготовлення продукції. Оцінки, що приписуються кожному з видів сировини, повинні бути такими , щоб оцінка всієї використаної сировини була мінімальною,а сумарна оцінка сировини, що використовується на виробництво одиниці продукції кожного виду, - не менше ціни одиниці продукції даного виду.
Розв'язок: Припустимо, що створюється виробів А, виробів В і виробів С. Для визначення оптимального плану виробництва потрібно розв'язати задачу, зміст якої максимізує цільову функцію.
(1)
при умовах: (2)
(3)
Припишем кожному з видів сировини, які використовуються для виробництвах продукції, двоїсту оцінку, відповідно рівну . Тоді загальна оцінка сировини ,використаної на виробництво продукції, складає (4)
Згідно умови, двоїсті оцінки повинні бути такими, щоб загальна оцінка сировини, використаної на виробництво одиниці продукції кожного виду, була не менша ціни одиниці продукції даного виду, повинні задовольняти таку систему нерівностей:
(5)
(6)
Як бачимо з задачі (1)-(3) і (4)-(5) створюють симетричну пару двоїстих задач. Розв'язок прямої задачі дає оптимальний план виробництва предметів А, В і С, а роєв'язок двоїстої - опртимальну систему оцінок стровини, використаної для виробництва цих предметів. Щоб знайти розв'язок цих задач, потрібно спочатку розв'язок будь-якого одного з них. Так як система обмеження задачі (1) - (3) складає лиш нервність виду " ", тому краще спочатку знайти розв'язок цієї задачі. Її розвязок наведено в таблиці.
і Базис
10 14 12 0 0 0
1
14 82 19/8 1 0 5/8 0 -1/8
2
0 80 23/8 0 0 1/8 1 -5/8
3
12 16 -3/4 0 1 -1/4 0 1/4
1340 57/4 0 0 23/4 0 5/4
З цієї таблиці видно, що оптимальним планом виробництва предметів є такий, при якому виготовлення 82 предметів В і 16 предметів С. При даному плані виробництва залишаються не використаними 80 кг. сировини другого виду, а загальна вартість предметів дорівнює 130 грн. З таблиці також видно, що оптимальним розв'язком двоїстої задачі є ; ; .
Використання і позначають умови двоїстої оцінки сировини, відповідно 1 і 3 видів . Ці оцінки відмінні від 0, а сировина 1і 3 видів повністю використовується при оптимальному плані виробництва продукції. Двоїста оцінка одиницісировини 2 виду дорівнює нулю. Цей вид сировини не повністю використовується при оптимальному плані виробництва продукції.
Таким чином,позитивну двоїсту оцінку мають лише ті види сировини, які повністю використовуються при оптимальному плані виробництва предметів.Тому двоїсті оцінки визначають дефіцитність використаного виробництвом сировини. Більше того,величина даної двоїстої оцінки показує, на скільки зросте максимальне значення цільвої функції прямої задачі при збільшенні кількості сировини відповідного виду на 1кг. Так, збільшення кількості сировини 1 виду на 1кг. приведе до того, що з'явиться можливість знайти новий оптимальний план виробництва предметів, при якому загальна вартість виробляючої продукції зросте на 5,75 грн. і буде дорівнювати 1340+5,75=1345,75грн. При цьому числа, розташовані в стовпці вектора таблиці, показують, що вказане збільшення загальної вартості виготовленої продукції може бути досягнуто за рахунок збільшення випуску предметів В на 5/8 од. і скорочення випуску предметів С на1/4од. Послідовність цього використана сировини 2 виду зменшується на 1/8 кг. Так само збільшення на 1кг. сировини 3 виду дозволить знайти новий оптимальний план виробництва предметів, при якій загальна вартість виробляючої продукції зросте на 1,25 грн. і складе 1340+1,25=1341,25 грн. Це буде досягнуто в результаті збільшення випуску предметів С на 1/4 од. і зменшення виробництва предметів В на 1/8 од. причому об'єм використаної сировини 2 виду зросте на 5/8 кг.
Продовжимо перегляд оптимальних двоїстих оцінок . Обчислюючи мінімальне значення цільової функції двоїстої задачі
Тут ми бачимо, що воно співпадає з максимальним значенням цільової функції вихідної задачі.
При підстановці оптимальних двоїстих оцінок в систему обмеження двоїстої задачі дістанемо :
Перше обмеження двоїстої задачі виконується як строга нерівність. Це означає, що двоїста оцінка сировини, використаної на виробництво одного предмета виду А, вище ціни цього предмету і, послідовно, випускати предмети виду А невигідно. Його виробництво і не передбачено оптимальним планом прямої задачі. Друге і третє обмеження двоїстої задачі виконується як строга рівність.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве