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


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

Страница 1 из 4 | Следующая страница

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

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

Мета роботи: Рішення завдань лінійного програмуваннясимплекс-методом. Варіантиразрешимости завдань лінійного програмування.


1 варіант.

1. Чотири студента: Іванов, Петров, Сидоров і Борис Васильєв пішли шляхом концерт групи «>Чайф», захопивши пиво 2 сортів: «>Русич» і «Прем'єр». Визначити план розпивання напоїв щоб одержати максимального сумарного сп'яніння (в ). Вихідні дані дано у таблиці:


Студент Норма випитого

Запаси

(в літрів)

«>Русич» «Прем'єр»
Іванов 2 2 1.5
Петров 3,5 1 1,5
Сидоров 10 4 4,5
Васильєв 1 0,7
Фортеця напою 16 % 10 %

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

2.1 Керовані параметри

x1[л] – кількість випитого пива «>Русич».

x2[л] – кількість випитого пива «Прем'єр».

– рішення.

2.2 Обмеження

– кількість пива «>Русич», випитого Івановим.

– кількість пива «Прем'єр», випитого Івановим.

– загальна кількість пива, випитого Івановим.

Загальна кількість пива, випитого Івановим, не перевершує наявних проблем нього запасів пива, тому:

(л).

Аналогічно будуємо решта обмежень:

(л).

(л).

(л).


3. Постановка завдання.

Знайти*, де досягається максимальне значення функції мети:

4. Рішення.

при:

Наведемо завдання до канонічного виду:

>Определим початковий опорний план: .

Таке рішення є опорним,т.к. вектора умов при позитивних компонентах рішення лінійно незалежні, також , де , але не оцінки позитивні (, де )

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

Припустимо, що , тоді:

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

=>

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

З обмеження (2) маємо: .

Підставляючи до функцій мети: отримуємо:

>Оформим даний етап завдання у виглядісимплекс-таблици:

Початковасимплекс-таблица:


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X3

2 2 1 0 0 0 1,5
0

X4

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

X5

10 4 0 0 1 0 4,5
0

X6

0 1 0 0 0 1 0,7

F -16 -10 0 0 0 0 0

;

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


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У
0

X3

0 1,428 1 -0,572 0 0 0,642
16

X1

1 0,286 0 0,286 0 0 0,428
0

X5

0 1,14 0 -2,86 1 0 0,214
0

X6

0 1 0 0 0 1 0,7

F 0 -5,424 0 4,576 0 0 6,857

;

Перерахувавши все оцінки, бачимо, що , отже критерій можна поліпшити. Будемо збільшувати . Нехай , тоді:

звідки отримуємо:

;

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

=>

>Виведем з базису . Тепер засадничими перемінними є , а вільними .Виразим функцію мети через нові перемінні:

, та якщо з обмежень (2) і (3): . Тоді: ;


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У

0

X3

0 0 1 3 -1,25 0 0,375
16

X1

1 0 0 1 -0,25 0 0,375
10

X2

0 1 0 -2,5 0,875 0 0,1875
0

X6

0 0 0 2,5 -0,875 1 0,5125

F 0 0 0 -9 4,75 0 7,875

Перерахувавши все оцінки, бачимо, що , отже критерій можна поліпшити. Будемо збільшувати . Нехай , тоді:

звідки отримуємо:

;

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

=>

>Виведем з базису . Тепер засадничими перемінними є , а вільними .Виразим функцію мети через нові перемінні:

, та якщо з обмежень (1) і (2): . Тоді: ;


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X4

0 0 0,333 1 -0,416 0 0,125
16

X1

1 0 -0,333 0 0,166 0 0,25
10

X2

0 1 1,833 0 -0,166 0 0,5
0

X6

0 0 -0,833 0 0,166 1 0,2

F 0 0 3 0 1 0 9

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



Бачимо, єдине і буває у кутовий точці області допустимих рішень.


2 варіант.

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

Функція мети: .

Наводимо обмеження до канонічного виду:

=>

Вирішуємосимплекс-методом:


16 6,4 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У
0

X3

2 2 1 0 0 0 1,5
0

X4

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

X5

10 4 0 0 1 0 4,5
0

X6

0 1 0 0 0 1 0,7

F -16 -10 0 0 0 0 0

,


16 6,4 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У
0

X3

0 1,428 1 -0,571 0 0 0,642
16

X1

1 1,286 0 0,286 0 0 0,428
0

X5

0 1,142 0 -2,85 1 0 0,214
0

X6

0 1 0 0 0 1 0,7

F 0 -1,82 0 4,571 0 0 6,857

;


16 6,4 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У
0

X3

0 0 1 3 -1,25 0 0,375
16

X1

1 0 0 1 -0,25 0 0,375
6,4

X2

0 1 0 -2,5 0,875 0 0,1875
0

X6

0 0 0 2,5 -0,875 1 0,5125

F 0 0 0 0 1,6 0 7,2

;

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



16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X4

0 0 0,333 1 -0,416 0 0,125
16

X1

1 0 -0,333 0 0,166 0 0,25
10

X2

0 1 1,833 0 -0,166 0 0,5
0

X6

0 0 -0,833 0 0,166 1 0,2

F 0 0 0 0 1 0 7,2

Якщо оптимальне рішення досягнуто в2-х точках, воно досягається і відрізку з-поміж них. Можна скласти рівняння даного відрізка за такою формулою:

;

;



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

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


3 варіант.

Студент Петров, вирішивши наздогнати за кількістю випитого студента Сидорова, випив 4 частки пива «>Русич» замість запланованих 3,5. Вирішимо завдання за урахуванням змінених даних.

Функція мети:.

Наводимо обмеження до канонічного виду:

=>

Вирішимо завданнясимплекс-методом.


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X3

2 2 1 0 0 0 1,5
0

X4

4 1 0 1 0 0 1,5
0

X5

10 4 0 0 1 0 4,5
0

X6

0 1 0 0 0 1 0,7

F -16 -10 0 0 0 0 0

, .


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

У
0

X3

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

X1

1 0,25 0 0,25 0 0 0,375
0

X5

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

X6

0 1 0 0 0 1 0,7

F 0 -6 0 4 0 0 6

, .


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
10

X2

0 1 1,666 -0,333 0 0 0,5
16

X1

1 0 -0,166 0,333 0 0 0,25
0

X5

0 0 -1 -2 1 0 0
0

X6

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

F 0 0 4 2 0 0 9

,

Дане оптимальне рішення євирожденним,т.к. позитивних компонентів менше ніж обмежень. На існуваннявирожденного оптимального рішення вказує його присутність середсимплекс-таблице нульового вільного члена при знайденому оптимальному рішенні.

Що стосуєтьсявирожденного рішеннясимплекс-таблица може зациклюватися. Існує 2 способу попередження зациклення:

а) – зміну ходу обмеження певні величини . Вони повинні бути малі, щоб зміни були несуттєві.

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



4 варіант.

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

Функція мети: .

Наводимо обмеження до канонічного виду:

=>

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

, у своїй .

Вирішуємо допоміжну завданнясимплекс-методом:



0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
1

X7

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

X8

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

X9

10 4 0 0 -1 0 0 0 1 0 4,5
1

X10

0 1 0 0 0 -1 0 0 0 1 0,7

F 15,5 8 -1 -1 -1 -1 0 0 0 0 0


0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
1

X7

0 1,428 -1 0,571 0 0 1 -0,571 0 0 0,642
0

X1

1 0,285 0 -0,285 0 0 0 0,285 0 0 0,428
1

X9

0 1,142 0 2,857 -1 0 0 -2,85 1 0 0,214
1

X10

0 1 0 0 0 -1 0 0 0 1 0,7

F 0 3.571 -1 3,428 -1 -1 0 -4,42 0 0 1,557


0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
1

X7

0 0 -1 -3 1,25 0 1 3 -1,25 0 0,375
0

X1

1 0 0 -1 0,25 0 0 1 -0,25 0 0,375
0

X2

0 1 0 2,5 -0,875 0 0 -2,5 0,875 0 0,187
1

X10

0 0 0 -2,5 0,875 -1 0 2,5 -0,875 1 0,512

F 0 0 -1 -5,5 2,125 -1 0 4,5 -3,12 0 0,887


0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
1

X8

0 0 -0,333 -1 0,416 0 0,333 1 -0,416 0 0,125
0

X1

1 0 0,333 0 -0,166 0 -,333 0 0,166 0 0,25
0

X2

0 1 -0,833 0 0,166 0 0,833 0 -0,166 0 0,5
1

X10

0 0 0,833 0 -0,166 -1 -0,833 0 0,166 1 0,2

F 0 0 0,5 -1 0,25 -1 -1,5 0 -1,25 0 0,325


0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
1

X8

0 0 0 -1 0,35 -0,4 0 1 -0,35 0,4 0,205
0

X1

1 0 0 0 -0,1 0,4 0 0 0,1 -0,4 0,17
0

X2

0 1 0 0 0 -1 0 0 0 1 0,7
0

X3

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

F 0 0 0 -1 0,35 -0,4 -1 0 -1,35 -0,6 0,205


0 0 0 0 0 0 1 1 1 1

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

в
0

X5

0 0 0 -2,85 1 -1,14 0 2,857 -1 -1,142 0,585
0

X1

1 0 0 -0,285 0 0,285 0 0,285 0 -0,285 0,228
0

X2

0 1 0 0 0 -1 0 0 0 1 0,7
0

X3

0 0 1 -0,571 0 -1,42 -1 -1,571 0 1,428 0,357

F 0 0 0 0 0 0 -1 -1 -1 -1 0

– оптимальне рішення допоміжної завдання. Штучні перемінні є вільними і рівні нулю.Т.о. це рішення є опорним планом вихідної завдання.

Вирішимо вихідну завдання:


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X5

0 0 0 -2,85 1 -1,14 0,585
16

X1

1 0 0 -0,285 0 0,285 0,228
10

X2

0 1 0 0 0 -1 0,7
0

X3

0 0 1 -0,571 0 -1,42 0,357

F 0 0 0 -4,576 0 -5,424 3,648

Критерій можна поліпшити,т.к. , , але не можна знайти таке , у якому базисні перемінні звертаються до 0. Отже завдання нерозв'язна через необмеженість критерію.


5 варіант.

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

Наводимо обмеження до канонічного виду:

=>

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

;


16 10 0 0 0 0

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

в
0

X5

0 0 0 -2,85 1 -1,14 0,585
16

X1

1 0 0 -0,285 0 0,285 0,228
10

X2

0 1 0 0 0 -1 0,7
0

X3

0 0 1 -0,571 0 -1,42 0,357

F 0 0 0 -4,576 0 -5,424 3,648

Бачимо, що оцінки вільних змінних менше нуля, отже рішення оптимальне.

; F = 3,648.

Робимо висновок: оптимальне рішення може існувати й при необмеженість області.


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

11



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

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

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

Завдання:

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


Сировину

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

Компоненти

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і – частка сировиниі-го виду в одиниці отриманого сплаву. Тоді функція мети (собівартість одиниці сплаву в у.о.) запишеться так:

.

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

(1).

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

(2).

Вирішимо це завдання методом штучного базису. І тому складемо розширену завдання:

(3).

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

;

;

Тоді:

.

Запишемо початковусимплекс-таблицу:


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

Зв

>Б.П.

X1

X2

X3

X4

X5

X6

X7

X8

X9

X10

У
M

X9

1 1 1 1 1 0 0 0 1 0 1
0

X6

0,8 0,6 0,1 0,1 0,1 1 0 0 0 0 0,3
M

X10

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

X8

0,1 0,1 0,4 0,6 0,7 0 0 1 0 0 0,4

F -4 -4,5 -5,8 -6 -7,5 0 0 0 0 0 0

FM

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

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


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

FM

0 0 0 0 0 0 0 0 -1 -1 0

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

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

Математична модель й економічна сенс двоїстої завдання.

Завдання, двоїста до початкової, будується так:

1) Вихідна завдання – щонайменше, отже, двоїста завдання – на максимум.

2) Матриця коефіцієнтів системи обмежень являтиметранспонированную матрицю відповідних коефіцієнтів вихідної завдання. У цьому все обмеження мають бути типу, наприклад "більше або одно". Тому перетворимо друге і четверте обмеження до типу "більше або одно", помноживши їх у –1, потімтранспонируем отриману матрицю:

=> .

3) Кількість змінних в двоїстої завданню одно числу обмежень у вихідної, тобто. 4, і навпаки, число обмежень у двоїстої завданню одно числу змінних в вихідної, тобто. 5.Переменная двоїстої завдання відповідає першому обмеження вихідної завдання, змінна – другому, – третьому, а – четвертому.

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

,

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

5)Т.к. все перемінні вихідної завданнянеотрицательни, усі обмеження двоїстої завдання будутьнеравенствами типу «» (оскільки двоїста завдання на максимум). Оскільки першу умову вихідної завдання є рівність, інші ж три – нерівності, вона може приймати будь-які значення, а ,і – лише позитивні.

Отже, математична модель двоїстої завдання наступна:

.

(4).

Проаналізуємо тепер економічний сенс двоїстої завдання. І тому спочатку розглянемо економічний сенс змінних ,, і . З обмежень видно, що обсяг має розмірність [>у.е./ед. сплаву], величина – [>у.е./ед. олова], – [>у.е./ед. цинку ], а – [>у.е./ед. свинцю]. Вказати економічний сенс перемінної неможливо з умови завдання. Що ж до економічного сенсу змінних і , то системі (1) вони відповідає другому і четвертому обмеженням, відбиваючим відносну надмірність ресурсів "олово" і "свинець", тобто. є підстави розглянуті як умовний збиток для власника цього ресурсу, чи ціну, виплачувану його придбавачу. Отже, олово і свинець виступають на даної завданню якантиблага, що економічно й досить абсурдно. Економічний сенс перемінної , що відбиває обмеженість ресурсу "цинк", видно явно: вона становить собою двоїсту оцінку, чи умовну ціну цього ресурсу.

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

Цільова функція даної двоїстої завдання економічно інтерпретується як максимальна прибуток фірми-постачальника ресурсів.

Рішення двоїстої завдання.

1. Рішення з допомогою >IBLP.

Ввівши завдання програму, отримуємо таке оптимальне рішення:


1 -0,3 0,1 -0,4 0 0 0 0 0

Зв

>Б.П.

Y1

Y2

Y3

Y4

Y5

Y6

Y7

Y8

Y9

У
1

Y1

1 0 0,54 -0,46 0 -0,2 1,2 0 0 6,06
-0,3

Y2

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

Y5

0 0 -0,12 -0,12 1 -1,4 0,4 0 0 0,02
0

Y8

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

Y9

0 0 -0,3 -0,3 0 0 -1 0 1 1,7

T 0 0 0,32 0,12 0 0,4 0,6 0 0 5,28

. Значення цільової функції у своїй одно 5,28.

2. Рішення в другий теоремі двоїстості.

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

(5)

(6)

>Покомпонентно нашим завдань ці співвідношення записуються так:

(5).

(6)

З системи (5) видно, в другому і третьому рівняннях в дужках виходить нуль, бо позитивні, . З системи (6) отримуємо, що , що у третьому і четвертому рівняннях в дужках виходять позитивні числа.

З першого вчителя і третього рівнянь системи (5) маємо:

звідки

Отже, .

3. Рішення з допомогоюсимплекс-таблици вихідної завдання.

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


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

FM

0 0 0 0 0 0 0 0 -1 -1 0

З теорії відомо, що справедливі такі формули: (7); (8).

У системі обмежень (2) вихідної завдання перемінної відповідає перше обмеження, що містить базисну зміну , перемінної – друге, що містить базисну зміну , перемінної – третє, що містить базисну зміну і – четверте з перемінної . Запишемо умова (7) для оцінок ,, і наведеноїсимплекс-таблици: ; ; ; ;

Тепер запишемо умова (8) нашого випадку:

, щопокомпонентно записується як: , , , , звідки , , ,

З огляду на те, що ми вирішувалисимплекс-методом не вихідну завдання (1), а завдання канонічної формі (2), тобто. по оптимальноїсимплекс-таблице ми можемо знайти рішення двоїстої завдання до канонічної формі вихідної завдання. Вочевидь, завдання в симетричній і канонічної формі – дві різні завдання, відмінні символом порятунку і кількістю обмежень у двоїстих завданнях. Понад те, бо всі обмеження в канонічної завданню – рівності, то двоїстої завданню всі можуть бути будь-якого знака, тому наші є помилкою. Але ми маємо вирішити не двоїсту до канонічної завданню, а двоїсту до симетричній. Якщо зробити заміну , то двоїста завдання до симетричній завданню прийме форму двоїстої до канонічної завданню. Отже, чи .

4. Рішення через матрицю, зворотний до базисної.

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

.

Одержимо:

,

Звідки .

Отже, бачимо, що всіма чотирма способами отримали один і той ж рішення: ;.

Економічна інтерпретація трьох теорем двоїстості.

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

У нашому випадку пара завдань має оптимальні плани, значення цільових функцій у яких рівні 5,28. Економічний зміст цього у тому, що у оптимальному плані мінімальних витрат фірми виробництва

Страница 1 из 4 | Следующая страница

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

Навігація