Курсова робота
з дисципліни
Дослідження операцій
Керівник:
Плотнікова М. В.
«____» ___________ 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
- Кількість пального, що доставляється зі складу 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 менше нуля, значить знайдене рішення не є оптимальним.
Складемо Симплекс таблицю:
Вибір в якості роздільної рядка х2с обумовлений тим, що саме в цьому рядку відношення вільного члена до змінної х1с мінімально. Виконаємо необхідні перетворення над елементами Симплекс таблиці:
Всі коефіцієнти при вільних змінних недодатні, отже, знайдене рішення є оптимальним. Запишемо його:
x1a = 10; x1b = 60; x1c = 10;
x2a = 80; x2b = 0; x2c = 0;
x3a = 0; x3b = 0; x3c = 80;
L = 620;
Для перевірки правильності обчислень можна скласти транспортну таблицю:
Після аналізу таблиці можна зробити висновок, що обчислювальних помилок при розрахунках зроблено не було.
Відповідь:
x1a = 10 x1b = 60 x1c = 10
x2a = 80 x2b = 0 x2c = 0
x3a = 0 x3b = 0 x3c = 80
L = 620
Цільова функція задачі має вигляд:
Нехай змінні x1 і x2 - вільні, а змінні x3, x4 і x5 - базисні.
Далі необхідно представити систему обмежень у стандартному вигляді. Для цього проведемо ряд перетворень:
Підставимо вирази для x3 і x4 у третє рівняння системи обмежень:
Спростимо отримане вираження і висловимо x5:
Тепер можна уявити систему обмежень у стандартному вигляді:
Необхідно також висловити цільову функцію через вільні змінні:
Тепер можна заповнити Симплекс-таблицю
Виходячи з того, що всі вільні члени позитивні, можна зробити висновок про те прийняте рішення є опорним.
Далі потрібно вибрати дозволяє елемент. В якості дозволяє стовпця доцільно прийняти стовпець x1, так як коефіцієнт при x1 в цільової функції менше коефіцієнта при x2. Роздільної рядком буде рядок x5, так як відношення вільного члена цього рядка до коефіцієнта при x1 мінімально. Відзначимо знайдений дозволяє елемент в таблиці, а також заповнимо необхідні клітини:
Перерісуем таблицю з урахуванням заміни x2 на x3:
Коефіцієнт при х2 в цільовій функції негативний, значить необхідно провести ще одну заміну. Як роздільної рядка приймемо x3. Таким чином, що дозволяє буде елемент, що стоїть на перетині рядка x3 та стовпця x2.
У результаті отримаємо:
Коефіцієнти при вільних змінних в цільовій функції позитивні, значить, знайдене рішення є оптимальним.
Відповідь:
x1 = 4
x2 = 3
x3 = 0
x4 =- 5
x5 = 0
L = 14
Застосуємо до задачі метод «Північно-Західного кута». Для цього заповнимо таблицю починаючи з лівого верхнього кута без урахування вартості перевезень:
У таблиці заповнено n + m-1 = 7 клітин, значить знайдене рішення є опорним. Далі необхідно поліпшити план перевезень відповідно до вартостями доставки вантажів. Для цього використовуємо циклічні перестановки в тих циклах, де ціна негативна.
У даній таблиці у верхній частині клітинки вказана вартість перевезення, а в нижній кількість перевезеного вантажу. Прямокутником виділено негативний цикл γ1 = 25 +22-40-12 =- 5. Мінімальне значення перевезень, що стоять в негативних вершинах одно k1 = 100. У результаті отримаємо зменшення вартості перевезення:
ΔL1 =- 5 * 100 =- 500
Транспортна таблиця прийме наступний вигляд:
γ2 = 12 +32-45-22 =- 23 k2 = 200 ΔL2 =- 23 * 200 =- 4600
γ3 = 10 +18-50-25 =- 47 k3 = 100 ΔL3 =- 47 * 100 =- 4700
γ4 = 10 +23-12-50 =- 29 k4 = 200 ΔL4 =- 29 * 200 =- 6800
Негативних циклів в транспортній таблиці більше немає. Отже, можна припустити, що знайдене рішення є оптимальним. Для перевірки застосуємо метод потенціалів.
Складемо систему:
Покладемо β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.
Знайти мінімум функції 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 в якості базисних:
Складемо Симплекс таблицю:
У результаті отримаємо
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
з дисципліни
Дослідження операцій
Керівник:
Плотнікова М. В.
«____» ___________
Автор:
Студент групи ПС-346
Попов О. Є..
«____» ___________
Робота захищена
з оцінкою
«____» ___________
Зміст
\ 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
Для складання математичної моделі задачі введемо змінні: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 в якості вільних (даний вибір дозволяє легко висловити базисні змінні через вільні).
Далі відповідно до алгоритму Симплекс методу необхідно висловити базисні змінні через вільні:
Наступний крок рішення - представлення цільової функції через вільні змінні:
Складемо Симплекс таблицю:
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 |
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 |
bi | x5 | x2 | |
L | 2 | 1 | -4 |
x3 | 3 | 1 | 1 |
x4 | 1 | -1 | 2 |
x1 | 1 | 1 | -1 |
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 |
ПН ПЗ | 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 |
Δ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 |
ПН ПЗ | 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 |
ПН ПЗ | 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 |
ПН ПЗ | 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