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

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

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

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


Реферат на тему:
Теорія двоїстості та двоїсті оцінки в аналізі розв'язків лінійних оптимізаційних моделей.
План.
1. Аналіз стійкості двоїстих оцінок.
2. Приклади розв'язування задач.
3. Література
Аналіз стійкості двоїстих оцінок.
Розглянемо основні задачі лінійного програмування :
Задача 1-3.
Основні двоїсті задачі 4-5:
Припустимо, що задача (1) - (3) має не вироджені опорні плани і хоч би один з них являється оптимальним.
Максимальне значення цільової функції (1) задачі (1) - (3) будемо розглядати як функцію вільних членів системи лінійних рівнянь(2): Fmax(b1,b2,…,bm).
Теорема 1.12. В оптимальному плані двоїстої задачі (4) , (5) значення перемінної yi* численно рівне частинній похідній функції Fmax(b1,b2,…,bm) по даному аргументу
Остання задача означає ,що зміна значень величин bi до збільшення чи зменшення Fmax(b1,b2,…,bm) .Ця зміна Fmax(b1,b2,…,bm) визначається величиною і може бути охарактеризована лише тоді , коли змінах величин bi значення перемінних yi* в оптимальному плані відповідає двоїстій задачі (4) , (5) залишаються незмінними. Тому представляє інтерес визначити такі інтервали змін кожного з вільних членів системи лінійних рівнянь (2) , в яких оптимальний план двоїстої задачі (4) , (5) не міняється. Це має місце для всіх тих значень , при котрих стовпець вектора P0 останньої симплекс-таблиці розв'язання задачі (1)-(3) не містить від'ємних чисел тоді , коли серед компонентів вектора
не має від'ємних. Тут B-1 - матриця, обернена до матриці B , складеної із компонентів вектора-базиса , котрий визначає оптимальний план задачі (1) - (3) .
Таким образом , якщо знайдено розв'язання задачі (1) - (3), то не важко провести аналіз стійкості двоїстих оцінок відносно змін bi .Це в свою чергу ,позволяє проаналізувати стійкість оптимального плану задачі (4) , (5) відносно змін вільних системи лінійних рівнянь (2), оцінити степінь впливу змін bi на максимальне значення цільової функції задачі (1) - (3) і дає можливість визначити найбільш цілеспрямований варіант допустимих змін bi.
1.19. Для виготовлення чотирьох видів продукції підприємство використовує три типи ресурсів. Норми витрат ресурсів кожного типу на одиницю продукції , їх наявність в користуванні підприємства , а також ціни одиниці продукції наведені в таблиці 1.
Тип
ресурсів Норма витрат ресурсів на одиницю продукції Наявність ресурсів
A B C D
I
II
III 1
0
4 0
1
2 2
3
0 1
2
4 180
210
800
Ціна одиниці продукції
9
6
4
7
Потрібно: a) сформулювати двоїсту задачу і знайти оптимальні плани прямої і двоїстої задачі; б) знайти інтервали стійкості двоїстих оцінок по відношенню до змін ресурсів кожного типу ; в) вивести зміни спільної ціни виготовленої продукції , визначеною оптимальним планом її виробництва при зменшенні кількості ресурсів I на 60 одиниць і збільшення кількості ресурсів II і III типів відповідно на 120 і 160 одиниць. Провести аналіз допустимих змін спільної ціни продукції як при змінах об'ємів кожного із ресурсів окремо, так і при їх одночасних змінах в вказаних розмірах.
Розв'язання: а) Припустимо , що вироби видів A, B, C, і D будуть вироблені відповідно в кількостях x1,x2,x3 і x4 . Для визначення оптимального плану вироблення продукції слід знайти розв'язання задачі , для визначення максимального значення функції :
F=9x1 + 6x2 + 4x3 + 7x4 (6)
при умовах
(7)
(8)
Припишемо одиниці кожного з використовуваних ресурсів двоїсту оцінку, відповідно рівну . Тоді двоїста задача по відношенню до задачі (6) - (8) складається в визначенні мінімального значення функції
F*= 180y1 + 210y2 + 800y3 (9)
при умовах
(10)
(11)
Як видно , задачі (6) - (8) і (9) - (11) складають симетричну пару двоїстих задач. Розв'язок даної задачі дає оптимальний план виробів видів A , B , C і D, а розв'язок двоїстої - оптимальну систему двоїстих оцінок ресурсів , використаних для виробництва цих виробів . Щоб знайти розв'язок цих задач , потрібно спочатку знайти розв'язок якої-небудь із них . Так як система обмежень задачі (6) - (8) містить лише нерівність виду " " , то спочатку краще знайти розв'язок цієї задачі . Її розв'язок наведено симплексним методом в таблиці 2
i Базис Сб P0 9 6 4 7 0 0 0
P1 P2 P3 P4 P5 P6 P7
1
2
3
4
1
2
3
4
1
2
3
4
1
2
3
4
P5
P6
P7
P1
P6
P7
P1
P6
P2
P1
P5
P2
0
0
0
9
0
0
9
0
6
9
0
6
180
210
800
0
180
210
80
1620
0
170
40
1860
95
85
210
2115
1
0
4
-9
1
0
0
0
1
0
0
0
1
0
0
0
0
1
2
-6
0
1
2
-6
0
0
1
0
0
0
1
0
2
3
0
-4
2
3
-8
14
2
7
-4
-10
-3/2
7/2
3
1/2
1
2
4
-7
1
2
0
2
1
2
0
2
0
1
2
5
1
0
0
0
1
0
-4
9
1
2
-2
-3
0
1
0
0
0
1
0
0
0
1
0
0
0
1
0
0
-1/2
1/2
1
3/2
0
0
1
0
0
0
1
0
0
-1/2
1/2
3
1/4
-1/4
0
9/4
З цієї таблиці видно , що оптимальним планом виробництва виробів являється такий план , при якому виготовляється 95 виробів виду А і 210 виробів виду В . При даному плані виробництва загальна кількість виробів дорівнює 2115 гривень. Із табл. 2 також видно, що оптимальним планом двоїстої задачі являється Y*=(0; 3/2; 9/4).
б) Визначимо тепер інтервали стійкості двоїстих оцінок по відношенню до змін ресурсів кожного виду. Для цього знайдемо компоненти вектора
і визначимо, при яких значеннях b1, b2 і b3 вони додатні. Спочатку як це зробити , відмітимо , що матриця В-1 ,обернена матриці В, складеній із компонентів векторів Р1, Р5, Р2 базису , який визначає оптимальний план задачі (6) - (8) , записана виключно на даних табл.2, а особливо : елементи матриці В-1 взяти із стовпців векторів Р5, Р6 і Р7, утворених першопочатковим одиничним базисом.
Умови додатковості компонентів указаного вище вектора приводить до наступної системи нерівності :
(12)
Очевидно , якщо 2 = 0 , то >-85. Це означає , якщо кількість ресурсів I типу буде збільшено чи зменшено в границях 85 одиниць, то не дивлячись на це , оптимальним планом двоїстої задачі (9) - (11) залишається Y*=(0; 3/2; 9/4).
Далі , якщо b1= 0 і b3 = 0 , то - 170 < b2 < - 190, а якщо b1 = 0 і b2 = 0 , то - 380 < b3 < 340 . Таким образом , якщо кількість одного з типів ресурсів II або III належить відповідно проміжку 40 < b2 < 400 або 420 < b3 < 1140, а кількість інших ресурсів залишається першопочатковим , то двоїста задача (9) - (11) має один і той самий оптимальний план Y*= (0; 3/2; 9/4).
Якщо b1, b2 і b3 змінюється одночасно, то досліджування стійкості двоїстих оцінок трохи ускладнюється, оскільки в даному випадку треба знайти багатогранник системи лінійних нерівностей (12). Точки цього багатогранника визначають кількість ресурсів кожного типу, при котрих двоїсті оцінки залишаються незмінними.
в) В даній задачі одночасно змінюється кількість ресурсів всіх трьох типів. При цьому кількість ресурсів першого типу зменшиться на 60 одиниць ( ), а кількість ресурсів другого і третього типів відповідно збільшуються на 120 і 160 одиниць ( і ). Виходячи з цього, щоб вияснити чи залишається Y*= (0; 3/2; 9/4) оптимальним планом двоїстої задачі (9) - (11) при вказаній змінній кількості ресурсів чи ні, потрібно провірити, чи задовольняють дані значення системи нерівності (12) чи ні. Для цього підкладаємо в нерівність (12) замість їх значення -60, 120 і 160:
Виходячи з цього, не дивлячись на зміни об'ємів ресурсів в вказаних розмірах, оптимального плану двоїстої задачі залишається Y*=(0; 3/2; 3/4).Дане заключення позволяє скористатися рівнянням (72) для визначення приростів максимального значення функції (6) при вказаних змінах кількості ресурсів. В такому випадку
Це означає, що зменшення кількості ресурсів I типу на 60 одиниць і збільшення кількості ресурсів II і III типу відповідно на 120 і 60 одиниць приведе до можливості побудови такого плану виробництва продукції, реалізація якого забезпечить випуск виробів на 540 гривень більше, ніж при плані виробництва продукції, обумовлена першопочатковою кількістю ресурсів. Зменшення кількості ресурсів I типу на 60 одиниць не вплине на зміни максимального значення функції в той час як збільшення кількості ресурсів II і III типу на 120 і 160 одиниць приведе до збільшення максимального значення функції відповідно на і .
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве