Рішення задач дослідження операцій

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

скачати

Курсова робота
з дисципліни
Дослідження операцій
Керівник:
Плотнікова М. В.
«____» ___________ 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 Рішення задач дослідження операцій

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
Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Контрольна робота
201.5кб. | скачати


Схожі роботи:
Дослідження операцій та прийняття рішення
Рішення задач на графах
Рішення транспортних задач
Рішення економічних задач
Рішення задач з вищої математики
Рішення задач на уроках хімії
Рішення задач з дисципліни Страхування
Рішення задач способом пропорцій
Рішення задач симплекс методом
© Усі права захищені
написати до нас