Реферати українською » Математика » Лабораторні роботи з Основ теорії систем


Реферат Лабораторні роботи з Основ теорії систем

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

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

,

тобто. перший і другий "ресурси" використовуються цілком і є дефіцитними. Слід зазначити, перше рівність виконується завжди, інакше завдання має розв'язання. Це логічно зрозуміло, оскільки сума частин завжди дорівнює цілому. Що ж до третього і четвертого ресурсів, всі вони мають нульову двоїсту оцінку, тобто. ці ресурси перестав бути дефіцитним. Розглянемо тепер умова (5). Оскільки , то справедливі нерівності:

.

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

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

Третя теорема двоїстості дозволяє визначити залежність зміни цільової функції початковій завдання через зміну запасів "ресурсів": , тобто. у разі як змінюються мінімальні витрати виробництва одиниці сплаву залежно через зміну "ресурсів". То хай, наприклад, максимальна частка олова збільшиться на 0,1, тобто. до 40 %. Тоді, по третьої теоремі двоїстості, мінімальні витрати виробництва одиниці сплаву зменшаться на [у.о.]. З іншого боку, зміна мінімальної частки цинку чи свинцю не призведе зміну мінімальних витрат, оскільки з їхньою двоїсті оцінки рівні нулю. Але двоїсті оцінки дозволяють про який вплив на цільову функцію не будь-яких змін ресурсів, а лише таких, які не призводять до неприпустимість оптимального рішення.


7



>Лабораторная робота № 4

>Телешовой Єлизавети, грн. 726,

>Послеоптимизационний аналіз завдань лінійного програмування.

>1.Анализ чутливості оптимального виконання завдання зміну вільних членів обмежень.

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


Сировину

Зміст у відсотках

Компоненти

1 2 3 4 5
Свинець 10 10 40 60 70
>Цинк 10 30 50 30 20
>Олово 80 60 10 10 10

Вартість, у. Є.

4 4,5 5,8 6 7,5

Визначити, скільки треба взяти сировини кожного виду, щоб виготовити з мінімальним собівартістю сплав, у якому олова трохи більше 30%, цинку щонайменше 10%, свинцю трохи більше 40%.

Математична модель:

Нехай xі – частка сировиниі-го виду в одиниці отриманого сплаву. Тоді функція мети (собівартість одиниці сплаву в у.о.) запишеться так:

.

Система обмежень матиме вид:

Запишемо систему в канонічному вигляді:

Оптимальнасимплекс-таблица:


4 4,5 5,8 6 7,5 0 0 0 M M

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28

Оптимальний рішення: і знайти оптимальне значення цільової функції: .

Економічно отримане рішення інтерпретується так: щоб одержати одиниці сплаву мінімальної собівартості слід узяти 40% сировини №2 і 60% сировини №3. У цьому сплав містить рівно 30% олова, більш 20% (точніше, 42%) цинку і менше 40% (28%) свинцю. Мінімальна собівартість одиниці сплаву становить 5,28 у.о. Оптимальні двоїсті оцінки .

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

У зв'язку з обчисленням інтервалів стійкості необхідно зауважити про знаках нерівностей. Ми пам'ятаємо, що явно їх зміну ми враховували (< на), але знаки самих нерівностей не змінювали. Сьогодні ми теж змінюватимемо знаки другого і четвертого нерівностей, але приймемо до уваги зворотний знак при розрахунку конкретних значень. (Це робиться більше унаочнюється економічної інтерпретації інтервалів стійкості.)

Нехай вільні члени змінилися на ,, і. Тоді оптимальна рішення нового завдання (базисні компоненти) можна знайти як:

.

>Базисное рішення обчислюється через матрицю, зворотний до базисної, і вільні члени обмежень. З оптимальноїсимплекс-таблици одержимо матрицю, зворотний до базисної, й оптимальний рішення (базисні компоненти):

=>

Усі елементи рішення мають бутинеотрицательни, інакше рішення буде неприпустимим, тобто. базисне рішення залишається оптимальним до того часу, доки воно дозволене. Область стійкості наступна:

.

Тепер знайдемо інтервали стійкості (інтервал стійкості двоїстих оцінок зміну правій частині обмеження чиi-го ресурсу – б таку силу-силеннуi–го ресурсу, у якому двоїсті оцінки не змінюються):

1),:

=> ,

2),:

=> ,

3),:

=> ,.


4),:

=> ,.

Отримані результати економічно означають, що вільний член у першому обмеження не може змінюватися від 0,5 до 1,26, але економічного сенсу це якого немає,т.к. сума складових часткою сплаву завжди 100%. Зміст олова з нового сплаві варіюється від 10% до 60%, цинку – від нуля ( немає економічної інтерпретації) до 42% і свинцю – від 28% до 100% (аналогічно випадку з цинком може бути пояснена економічно). Можливі й різні комбінації змін, які описує область стійкості (інтервали стійкості є своєрідними приватними випадками області стійкості). При даних змінах ресурсів двоїсті оцінки не зміняться, отже, і номери базисних змінних теж зміняться.

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

Приклад практичного застосування інтервалів стійкості.

>Изменим умова завдання так:

а) зміст олова з нового сплаві на повинен перевершувати 15%;

Інтервал стійкості для олова – це . 15% чи 0,15 входить у цей інтервал, отже двоїсті оцінки не зміняться та оптимальну рішення буде (при ).

.

По третьої теоремі двоїстості знайдемо значення критерію у своїй рішенні:

=> .

б) зміст цинку має не меншим 45%;

Інтервал стійкості для цинку - .Т.к. зміст цинку в сплаві має не більше 42%, ат.к. 0,45 не входить у інтервал стійкості двоїстих оцінок, то двоїсті оцінки й номери базисних змінних зміняться ().

.

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


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 -0,03

F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28

>Определим, яку з змінних виведемо з базису. У разі це завжди буде єдина негативна змінна .Введем в базис жодну з вільних змінних, що має коефіцієнт роздільною рядки негативний.Разрешающий стовпець вибирається щодо мінімальної по модулю відношенню оцінок до негативним коефіцієнтам роздільною рядки.Переменой, введеної в базис буде . Після стандартних перетворень однократного заміщення одержимо новусимплекс-таблицу:


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

2 1 0 1 1,5 0 5 0 2,5 -5 0,25
0

X8

0,3 0 0 0,5 0,75 0 1,5 1 0,35 -1,5 0,075
5,8

X3

-1 0 1 0 -0,5 0 -5 0 -1,5 5 0,75
0

X6

-0,3 0 0 -0,5 -0,75 1 -2,5 0 -1,35 2,5 0,075

F -0,8 0 0 -1,5 -3,65 0 -6,5 0 2,55 6,5 5,475

Як кажуть, оцінки як і задовольняють критерію оптимальності і всі базисні переміннінеотрицательни, отже, рішення дозволене й оптимальний. Нове вирішення завдання . Оптимальний значення критерію . Це означає, що з виробництва одиниці сплаву слід узяти 25% другого сировини й 75% третього сировини. У цьому частка цинку з нового сплаві буде рівно 45%, олова 22,5% і свинцю 32,5%. Мінімальна вартість тонни сплаву буде 5,475 у.о.

в) з нового сплаві має бути менш 40% олова і більше 30% цинку;

Запишемо область стійкості двоїстих оцінок, враховуючи нові зміни (; ):

.

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

=>

р) менш 60% олова і більше 40% цинку;

У разі зміни становлять: збільшення змісту олова на 30% і цинку на 30%, тобто і . Тому

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


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 -0,1

F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28

Оптимальнасимплекс-таблица:


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

2 1 0 1 1,5 0 5 0 2,5 -5 0.5
0

X8

0,3 0 0 0,5 0,75 0 1,5 1 0,35 -1,5 0,15
5,8

X3

-1 0 1 0 -0,5 0 -5 0 -1,5 5 0,5
0

X6

-0,3 0 0 -0,5 -0.75 1 -2.5 0 -1.35 2,5 0,25

F -0,8 0 0 -1,5 -3,65 0 -6,5 0 2,55 6,5 5,15

Одержимо таке рішення: , . Отже, виготовлення нового сплаву слід узяти 50% сировини №2 і 50% сировини №3.

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

Припустимо, що з'явилася можливість купувати сировину в інших постачальників за нижчою ціні: цинк по 2 у.о., а й за олово і свинець,т.к. відповідно до економічному змісту завдання є ">антиблагами", ми маємо велику доплату від своїх постачальника: 1,5 у.о. і 0,5 у.о. відповідно. Керівник підприємства виділив на закупівлю ресурсів 3 у.о.

Рішення:

По раніше отриманих результатів знаємо, що це підприємство витрачає мінімум коштів (5,28 у.о.) як у отриманому сплаві рівно 30% олова, 42% цинку і 28% свинцю (вважатимемо для зручності, що з виробництва 10 тонн сплаву необхідно 3 тонни олова, 4,2 тонни цинку і 2,8 тонн свинцю).Т.к. олово і свинець ми маємо з доплатою, то візьмемо в повному обсязі, необхідному для сплаву. Від "купівлі" олова ми матимемо , як від свинцю – , тобто. всього 5,9 у.о. (у зв'язку з їх дохідністю, а чи не збитковістю тимчасово виключимо їх із розгляду).

Будемо вести аналіз закупівель цинку. У першій ітерації ми закуповуємо цинк,т.к. у разі він приносив більше збитку (двоїста оцінка дорівнює нулю проти запропонованої вартістю 2 у.о.). Вирішивши нове завдання без виробництва олова і свинцю, ми безумовно вийдемо поза межі області стійкості двоїстих оцінок. З іншого боку, зміниться рішення: двоїста оцінка цинку збільшиться до 3 і винесла нове значення цільової функції знизиться до запланованих 4 у.о.Вичтем з цих витрат за виробництво сплаву прибуток від отримання олова і цинку: . Це означає, що у виробництво сплаву ми тільки витрачаємо коштів, а й отримуємо прибуток 1,9 у.о.

Зі збільшенням двоїстої оцінки цинку стає вигідно купувати його. Але ми маємо сумою грошей лише 3 у.о. і можемо закупити ними 1,5 тонн замість 2 необхідних. Тепер ми мусимо робити тільки 0,5 тонни цинку. У другий ітерації ми таке ж рішення: критерій дорівнює 4 у.о. і двоїста оцінка цинку, яку ми виробляємо 3 тонни, дорівнює 4.

Отже, ми маємо оптимальне рішення витрати виділених 3 у.о.: "закуповувати" з доплатою 4 тонни олова і п'яти тонн свинцю й за ціною 2 у.о. 1,5 тонни цинку. За такої плані підприємство матиме прибуток з виробництва сплаву у вигляді 1,9 у.о.

>2.Анализ чутливості оптимального виконання завдання зміну коефіцієнтів цільової функції.

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

1. Нехай, спочатку, змінюється ціна другого і третього ресурсів (базисні перемінні).

а).

Тоді оптимальнасимплекс-таблица матиме вид:


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F

0 0

0 0

0

А, щоб рішення залишалося оптимальним, необхідно, щоб усе оцінки булинеположительними (для завдання щонайменше):

=> ,

Це означає, що ціна першого ресурсу не може змінюватися від нуля (безплатний,недефицитний ресурс) до 4,514 у.о. (негативний коефіцієнт в цільової функції у разі немає економічного сенсу,т.к. свідчить про набуття ресурсу з доплатою. І тут ресурс виступає у роліантиблага). Критерій зміниться на .

б)


4 4,5 5,8 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F

0 0

0 0

0

=> ,

Коефіцієнт критерію не може змінюватися від 5,75 у.о. за тонну третього сировини до 6 у.о. У цьому рішення залишатиметься оптимальним, а сам критерій зміниться на .

2. Розглянемо випадок із вільної перемінної.

а) , тоді

Умова оптимальності оцінки: => => .

У разі , .

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

б) Будемо керуватись аналогічними міркуваннями при обчисленні інтервалів стійкості для четвертого і п'ятого ресурсів.

, чи ,.

, чи ,

Оптимальні рішення за конкретних змінах коефіцієнтів.

>а)стоимость другого сировини збільшилася до 4,5 у.о

Інтервал стійкості коефіцієнта цільової функції . Ціна 4,5 у.о. входить у цей інтервал, отже оптимальне рішення не зміниться, а критерій стане у.о.

б) вартість третього сировини зменшилася до 3 у.о

Інтервал стійкості для . 3 у.о. () не належить інтервалу, отже якісь оцінки будуть не оптимальними:

– при : ;

– при : ;

– при : ;

– при : ;

– при : ;

.

>Скорректируемсимплекс-таблицу:


4 4,5 3 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
3

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F 1,1 0 0 -3 -4,5 3 0 0 -9,42 0 3,6

За два ітерації отримуємо оптимальнусимплекс-таблицу:


4 4,5 3 6 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4

X1

1 1 0 -0,666 -1 0 0 -3,33 1,333 0 0
0

X6

0 -0,2 0 0,466 0,7 1 0 2,333 -1,03 0 0,2
3

X3

0 0 1 1,666 2 0 0 3,333 -0,333 0 0,1
0

X7

0 -0,2 0 0,466 0,7 0 1 1,333 -0,033 -1 0,4

F 0 -0,5 0 -3,66 -5,5 0 0 -3,33 4,333 0 3

Одержимо оптимальне рішення . Вартість сплаву знизилася до 3 у.о. за одиницю.

в) витрати першу сировину зросли до 6 у.о

Вартість першого сировини може змінюватися не більше . 6 у.о. входить у інтервал, отже оптимальне рішення не зміниться, і навіть залишиться старому критерій (,).

р) витрати на четвертий ресурс впали до запланованих 4 у.о.

При падінні витрат до запланованих 4 у.о. за 1 тонну оптимальне розв'язання має змінитися,т.к. нижню межу інтервалу стійкості – 5,8 у.о. Оцінка .


4 4,5 5,8 4 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
0

X8

0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12
5,8

X3

-0,4 0 1 1 1 -2 0 0 1,2 0 0,6
0

X7

0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32

F -0,02 0 0 1,8 -1,7 -2,6 0 0 -6,06 0 5,28

Оптимальнасимплекс-таблица:


4 4,5 5,8 4 7,5 0 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
4,5

X2

1,4 1 0 0 0 2 0 0 -0,2 0 0,4
4

X4

0,6 0 0 1 1,5 3 0 5 -2,3 0 0,6
5,8

X3

-1 0 1 0 -0,5 -5 0 -5 3,5 0 0
0

X7

0 0 0 0 0 -1 1 -1 1 -1 0,2

F -1,1 0 0 0 -4,4 -8 0 -9 10,2 0 4,2

З допомогоюсимплекс-метода отримуємо оптимальне рішення та оптимальну значення критерію у.о.

3. Аналіз чутливості оптимального виконання завдання зміну технологічних коефіцієнтів.

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

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

. А, щоб рішення залишалося оптимальним, необхіднанеположительность оцінки: тобто. . Інтервал стійкості коефіцієнта .

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

Схожі реферати:

Навігація