Курсова робота з дисципліни
Дослідження операцій Керівник:
Плотнікова М. В.
«____»
___________ 2005 р .
Автор:
Студент групи ПС-346
Попов О. Є..
«____» ___________
2005 р .
Робота захищена
з оцінкою
«____» ___________
2005 р .
Зміст
\ T "Заголовок 1; 1" 1 Умови
задач. 3 2 Рішення задач дослідження
операцій. 4 2.1 Рішення задачі 1. 4
2.2 Рішення завдання 2. 8
2.3 Рішення задачі 3. 12
2.4 Рішення задачі 4. 17
1 Умови завдань
2.1 Рішення задачі 1
Для складання
математичної моделі задачі введемо
змінні:
- Кількість пального, що доставляється зі складу A на бензоколонку 1
- Кількість пального, що доставляється зі складу A на бензоколонку 2
x3a - кількість пального, що доставляється зі складу A на бензоколонку 3
x1b - кількість пального, що доставляється зі складу B на бензоколонку 1
x2b - кількість пального, що доставляється зі складу B на бензоколонку 2
x3b - кількість пального, що доставляється зі складу B на бензоколонку 3
x1c - кількість пального, що доставляється зі складу C на бензоколонку 1
x2c - кількість пального, що доставляється зі складу C на бензоколонку 2
x3c - кількість пального, що доставляється зі складу C на бензоколонку 3
На складах A, B, C знаходиться 90, 60, 90 тонн пального
відповідно, отже, можна записати:
На кожну заправку потрібно відправити однакову кількість пального,
рівне (90 +60 +90) / 3:
Відповідно до вартостями перевезень запишемо цільову функцію, яку необхідно мінімізувати:
Маємо класичну
транспортну задачу з числом базисних змінних, рівним n + m-1, де m-число пунктів відправлення, а n - пунктів призначення. У розв'язуваної задачі число базисних змінних дорівнює 3 +3-1 = 5.
Число вільних змінних
відповідно 9-4 = 4.
Приймемо змінні x1a, x1b, x2a, x2с, x3с як базисних, а змінні x1c, x2b, x3а, x3b в якості вільних (даний
вибір дозволяє легко висловити базисні змінні через вільні).
Далі відповідно до алгоритму Симплекс методу необхідно висловити базисні змінні через вільні:
Наступний крок рішення - представлення цільової
функції через вільні змінні:
У завданні потрібно знайти мінімум функції L. Так як коефіцієнт при перемінної x1c менше нуля, значить знайдене рішення не є оптимальним.
Складемо Симплекс таблицю:
| bi
| x3a
| x2b
| x3b
| x1c
|
L
| 630 -10
| -3 1
| -1 0
| -4 4
| 1 -1
|
x1a
| 20 -10
| 0 1
| -1 0
| -1 1
| 1 -1
|
x1b
| 60 0
| 0 0
| 1 0
| 1 0
| 0 0
|
x2a
| 70 10
| 1 -1
| 1 0
| 1 -1
| -1 1
|
x2c
| 10 10
| -1 -1
| 0 0
| -1 -1
| 1 1
|
x3c
| 80 0
| 1 0
| 0 0
| 1 0
| 0 0
|
Вибір в якості роздільної рядка х2с обумовлений тим, що
саме в цьому рядку відношення вільного члена до змінної х1с мінімально. Виконаємо необхідні
перетворення над елементами Симплекс
таблиці:
| bi
| x3a
| x2b
| x3b
| x2c
|
L
| 620
| -2
| -1
| 0
| -1
|
x1a
| 10
| 1
| -1
| 0
| -1
|
x1b
| 60
| 0
| 1
| 1
| 0
|
x2a
| 80
| 0
| 1
| 0
| 1
|
x1c
| 10
| -1
| 0
| -1
| 1
|
x3c
| 80
| 1
| 0
| 1
| 0
|
Всі коефіцієнти при вільних змінних недодатні, отже, знайдене рішення є оптимальним. Запишемо його:
x1a = 10; x1b = 60; x1c = 10;
x2a = 80; x2b = 0; x2c = 0;
x3a = 0; x3b = 0; x3c = 80;
L = 620;
Для перевірки правильності обчислень можна скласти транспортну таблицю:
| A
| B
| C
| |
1
| 10
| 60
| 10
| 80
|
2
| 80
| 0
| 0
| 80
|
3
| 0
| 0
| 80
| 80
|
| 90
| 60
| 90
| |
Після аналізу таблиці можна зробити висновок, що обчислювальних помилок при
розрахунках зроблено не було.
Відповідь:
x1a = 10 x1b = 60 x1c = 10
x2a = 80 x2b = 0 x2c = 0
x3a = 0 x3b = 0 x3c = 80
L = 620
2.2 Рішення задачі 2
Складемо систему обмежень виходячи з умови задачі
Цільова
функція задачі має вигляд:
Нехай змінні x1 і x2 - вільні, а змінні x3, x4 і x5 - базисні.
Далі необхідно представити систему обмежень у
стандартному вигляді. Для цього проведемо ряд перетворень:
Підставимо вирази для x3 і x4 у третє рівняння системи обмежень:
Спростимо отримане вираження і висловимо x5:
Тепер можна уявити систему обмежень у стандартному вигляді:
Необхідно також висловити цільову функцію через вільні змінні:
Тепер можна заповнити Симплекс-таблицю
| bi
| x1
| x2
|
L
| 1
| -1
| -3
|
x3
| 2
| -1
| 2
|
x4
| 2
| 1
| 1
|
x5
| 1
| 1
| -1
|
Виходячи з
того, що всі вільні члени позитивні, можна зробити висновок про те прийняте рішення є опорним.
Далі потрібно вибрати дозволяє елемент. В якості дозволяє стовпця доцільно прийняти стовпець x1, так як коефіцієнт при x1 в цільової функції менше коефіцієнта при x2. Роздільної рядком буде рядок x5, так як відношення вільного члена цього рядка до коефіцієнта при x1 мінімально. Відзначимо знайдений дозволяє елемент в таблиці, а також заповнимо необхідні клітини:
| bi
| x1
| x2
|
L
| 1 1
| -1 1
| -3 -1
|
x3
| 2 1
| -1 1
| 2 -1
|
x4
| 2 -1
| 1 -1
| 1 1
|
x5
| 1 1
| 1 1
| -1 -1
|
Перерісуем таблицю з урахуванням заміни x2 на x3:
| bi
| x5
| x2
|
L
| 2
| 1
| -4
|
x3
| 3
| 1
| 1
|
x4
| 1
| -1
| 2
|
x1
| 1
| 1
| -1
|
Коефіцієнт при х2 в цільовій функції негативний, значить необхідно провести ще одну заміну.
Як роздільної рядка приймемо x3. Таким чином, що дозволяє буде елемент, що стоїть на перетині рядка x3 та стовпця x2.
| bi
| x5
| x2
|
L
| 2 12
| 1 4
| -4 4
|
x3
| 3 3
| 1 1
| 1 1
|
x4
| 1 -6
| -1 -2
| 2 -2
|
x1
| 1 3
| 1 1
| -1 1
|
У результаті отримаємо:
| bi
| x5
| x3
|
L
| 14
| 5
| 4
|
x2
| 3
| 1
| 1
|
x4
| -5
| -1
| 0
|
x1
| 4
| 2
| 1
|
Коефіцієнти при вільних змінних в цільовій функції позитивні, значить, знайдене рішення є оптимальним.
Відповідь:
x1 = 4
x2 = 3
x3 = 0
x4 =- 5
x5 = 0
L = 14
2.3 Рішення задачі 3
Умова задачі задано у вигляді
транспортної таблиці:
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50
| 15
| 10
| 300
|
A2
| 21
| 30
| 20
| 100
|
A3
| 18
| 40
| 25
| 200
|
A4
| 23
| 22
| 12
| 800
|
A5
| 25
| 32
| 45
| 200
|
заявки
| 500
| 300
| 800
| |
Застосуємо до задачі метод «Північно-Західного кута». Для цього заповнимо таблицю починаючи з лівого верхнього кута без урахування вартості перевезень:
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 300
| | | 300
|
A2
| 100
| | | 100
|
A3
| 100
| 100
| | 200
|
A4
| | 200
| 600
| 800
|
A5
| | | 200
| 200
|
заявки
| 500
| 300
| 800
| |
У таблиці заповнено n + m-1 = 7 клітин, значить знайдене рішення є опорним. Далі необхідно поліпшити план перевезень відповідно до вартостями доставки вантажів. Для цього використовуємо циклічні перестановки в тих циклах, де ціна негативна.
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50 300
| 15
| 10
| 300
|
A2
| 21 100
| 30
| 20
| 100
|
A3
| 18 100
| 40 100
| 25
| 200
|
A4
| 23
| 22 200
| 12 600
| 800
|
A5
| 25
| 32
| 45 200
| 200
|
заявки
| 500
| 300
| 800
| |
У даній таблиці у верхній частині клітинки вказана вартість перевезення, а в нижній кількість перевезеного вантажу. Прямокутником виділено негативний цикл γ1 = 25 +22-40-12 =- 5. Мінімальне значення перевезень, що стоять в негативних вершинах одно k1 = 100. У результаті отримаємо зменшення вартості перевезення:
ΔL1 =- 5 * 100 =- 500
Транспортна таблиця прийме наступний вигляд:
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50 300
| 15
| 10
| 300
|
A2
| 21 100
| 30
| 20
| 100
|
A3
| 18 100
| 40
| 25 100
| 200
|
A4
| 23
| 22 300
| 12 500
| 800
|
A5
| 25
| 32
| 45 200
| 200
|
заявки
| 500
| 300
| 800
| |
γ2 = 12 +32-45-22 =- 23 k2 = 200 ΔL2 =- 23 * 200 =- 4600
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50 300
| 15
| 10
| 300
|
A2
| 21 100
| 30
| 20
| 100
|
A3
| 18 100
| 40
| 25 100
| 200
|
A4
| 23
| 22 100
| 12 700
| 800
|
A5
| 25
| 32 200
| 45
| 200
|
заявки
| 500
| 300
| 800
| |
γ3 = 10 +18-50-25 =- 47 k3 = 100 ΔL3 =- 47 * 100 =- 4700
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50 200
| 15
| 10 100
| 300
|
A2
| 21 100
| 30
| 20
| 100
|
A3
| 18 200
| 40
| 25
| 200
|
A4
| 23
| 22 100
| 12 700
| 800
|
A5
| 25
| 32 200
| 45
| 200
|
заявки
| 500
| 300
| 800
| |
γ4 = 10 +23-12-50 =- 29 k4 = 200 ΔL4 =- 29 * 200 =- 6800
ПН ПЗ
| B1
| B2
| B3
| запаси
|
A1
| 50
| 15
| 10 300
| 300
|
A2
| 21 100
| 30
| 20
| 100
|
A3
| 18 200
| 40
| 25
| 200
|
A4
| 23 200
| 22 100
| 12 500
| 800
|
A5
| 25
| 32 200
| 45
| 200
|
заявки
| 500
| 300
| 800
| |
Негативних циклів в
транспортній таблиці більше немає. Отже, можна припустити, що знайдене рішення є оптимальним. Для перевірки застосуємо метод потенціалів.
Складемо систему:
Покладемо β2 = 0, тоді α4 =- 22
β1 = 1, α2 =- 20
β3 =- 10, α2 =- 22
α1 =- 20, α5 =- 32
Всі коефіцієнти α негативні, значить, знайдений план перевезень є оптимальним.
Відповідь:
x21 = 100;
x31 = 200;
x41 = 200;
x42 = 100;
x52 = 200;
x13 = 300;
x43 = 500.
2.4 Рішення задачі 4
Складемо
математичну модель поставленого завдання.
Знайти мінімум функції f (x1, x2)
При обмеженнях
Замінивши
знак функції f (x1, x2) на протилежний, перейдемо до пошуку максимуму функції:
Тепер завдання приведена до
стандартного вигляду задачі квадратичного програмування. Приступимо до рішення.
1) Визначимо стаціонарну точку
Вирішивши систему, отримаємо:
x1 = 10
x2 = 7
Очевидно, що дані координати не задовольняють умовам обмежень. Тому перевіряти стаціонарну крапку на відносний максимум немає необхідності.
2) Складемо функцію Лагранжа:
Застосувавши до функції Лагранжа теорему Куна-Таккера, будемо
мати систему:
3) Перетворимо отриману систему:
З рівняння 3 системи випливає, що x2 = 6-x1:
Для звернення
нерівностей системи в рівності введемо V1, V2, W і перетворимо систему:
4) Запишемо умови доповнює нежорсткої:
5) Введемо в систему рівнянь штучні змінні z1, z2:
Поставимо задачу максимізації функції
.
Для вирішення цього завдання скористаємося Симплекс-методом. Приймемо змінні z1 і z2 в якості базисних:
Складемо Симплекс таблицю:
| bi
| x1
| U1
| U2
| V1
| V2
|
φ
| -17M 0
| -5M 0
| 0 0
| M 0
| M 0
| -M 0
|
z1
| 9 8
| 2 3
| -1 1
| 2 -3
| -1 0
| 0 1
|
z2
| 8 8
| 3 3
| 1 1
| -3 -3
| 0 0
| 1 1
|
W
| 0 0
| -1 0
| 0 0
| 0 0
| 0 0
| 0 0
|
| bi
| x1
| z2
| U2
| V1
| V2
|
φ
| -17M 17M
| -5M M
| 0 M
| M -M
| M -M
| -M M
|
z1
| 17 17 / 5
| 5 1 / 5
| 1 1 / 5
| -1 -1 / 5
| -1 -1 / 5
| 1 1 / 5
|
U1
| 8 -51 / 5
| 3 -3 / 5
| 1 -3 / 5
| -3 3 / 5
| 0 3 / 5
| 1 -3 / 5
|
W
| 0 17 / 5
| -1 1 / 5
| 0 1 / 5
| 0 -1 / 5
| 0 -1 / 5
| 0 1 / 5
|
| bi
| z1
| z2
| U2
| V1
| V2
|
φ
| 0
| M
| M
| 0
| 0
| 0
|
x1
| 17 / 5
| 1 / 5
| 1 / 5
| -1 / 5
| -1 / 5
| 1 / 5
|
U1
| -11 / 5
| -3 / 5
| -2 / 5
| 1 / 2
| 3 / 5
| -2 / 5
|
W
| 17 / 5
| 1 / 5
| 1 / 5
| -1 / 5
| -1 / 5
| 1 / 5
|
У результаті отримаємо
x1 = 17 / 5
x2 = 6-x1 = 13 / 5
Як видно, координати стаціонарної точки сильно відрізняються від координат, отриманих в якості відповіді. Це можна пояснити тим, що стаціонарна точка не задовольняє умовам обмежень.
Умови доповнює нежорсткої
виконуються.
Отже, знайдене рішення є оптимальним.
Знайдемо значення цільової функції:
=- 51 / 5 - 52 / 5 + 289/50 - 221/25 + 169/25 =
= -16.9
Відповідь:
x1 = 17 / 5
x2 = 13 / 5
f (x1, x2) = -16.9