МІНІСТЕРСВО ОСВІТИ І НАУКИ УКРАЇНИ
Національний Авіаційний Університет
РОЗРАХУНКОВО-ГРАФІЧНА РОБОТА
з дисципліни
“Дослідження операцій”
Виконав: студент 411 гр. ФКС
Гіндюк О.В.
Варіант № 4
Прийняв: Артамонов Є.Б.
Київ – 2004
Дані варіанту
1) Розрахувати задачу графічно і симплекс-методом.
F(x) = -7x1 + x2 max
9x1 + 4x2 110
11x1 - 3x2 24
2x1 - 7x2 15
xj 0.
2) Побудувати математичну модель і розрахувати транспортну задачу.
На 3 бази А1, А2, А3 потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 3 пункти призначення В1, В2, В3 відповідно у кількості 90, 50 і 60 од. Тарифи перевезень, одиниць вантажу кожного з пунктів відправлення та призначення виставляються студентом самостійно.
1) Вирахуємо задачу графічним методом:
F(x) = -7x1 + x2 max
9x1 + 4x2 110
11x1 - 3x2 24
2x1 - 7x2 15
xj 0.
Побудуємо на графіку обмеження:
9x1 + 4x2 110
11x1 - 3x2 24
2x1 - 7x2 15
xj 0
Знайдемо область допустимих рішень (ОДР). Рішення задачі повинно лежати на границях ОДР.
Тепер підставимо точки (вершини) ОДР у функцію і знайдемо максимальне значення:
F(0;-8) = -7*0 - 8 = -8
F(1,9;-1,6) = -7*1,9 - 1,6 = -14,9
F(0;-2,1) = -7*0 – 2,1 = -2,1
Таким чином, ми бачимо, що значення функції у цих точках від’ємні, отже, задача не має розв’язку.
Симплекс-метод
F(x) = -7x1 + x2 max
9x1 + 4x2 110
11x1 - 3x2 24
2x1 - 7x2 15
xj 0.
Приведемо систему обмежень до розширеного вигляду:
9x1 + 4x2 + x3= 110
11x1 - 3x2 + x4 = 24
-2x1 + 7x2 + x5= -15
xj 0
Симплекс-таблиця:
Базисні елементи F X1 X2 X3 X4 X5
Рядок коеф. цільової ф-ї Коеф. при базисних елементах 0 -7 1 0 0 0
X3 0 110 9 4 1 0 0
X4 0 24 11 -3
0 1 0
X5 0 -15 -2 7 0 0 1
Δ Рядок оцінок 0 7 -1
0 0 0
:7(3)(-4)
Дивлячись на рядок оцінок, ми вибираємо направляючий стовпець, тобто той, в якому Δ мінімальна. В цьому стовпці вибираємо найбільший невід’ємний елемент. Якщо таких невід’ємних чисел декілька, то ми ділимо їх на вільні члени і дивимось, який з них найбільший. А потім потрібно рядок, де був знайдений найбільший невід’ємний елемент додати до інших рядків так, щоб у цьому направляючому стовпці отримати нулі.
Дивимось, що отримали в результаті:
Базисні елементи F X1 X2 X3 X4 X5
Рядок коеф. цільової ф-ї Коеф. при базисних невідомих 0 -7 1 0 0 0
X3 0 118,4 10,12 0 1 0 -0,56
X4 0 17,7 10,16 0 0 1 0,42
X2 1 -2,1 -0,28 1 0 0 0,14
Δ Рядок оцінок -2,1 6,72 0 0 0 0,14
Як бачимо, і симплекс-метод теж показав, що задача не має розв’язку, так як значення функції від’ємне.
2.Транспортна задача
На 3 бази А1, А2, А3 потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 3 пункти призначення В1, В2, В3 відповідно у кількості 90, 50 і 60 од. Тарифи перевезень, одиниць вантажу кожного з пунктів відправлення та призначення виставляються студентом самостійно.
Дані у вигляді таблиці:
В1 В2 В3 Запаси
А1 6 2 1 70
А2 4 8 2 50
А3 1 5 4 80
Заявки 90 50 60
Математична модель транспортної задачі буде мати вигляд:
F=i=1m j=1n cijхij
Де Хij – це кількість товару, який перевозиться із Аi в Вj,
Сij – ціна перевезення.
Задачу потрібно перевірити, чи є вона збалансованою.
i=1m хij = bj (j=1, n ) = 90 + 50 + 60 = 200
j=1n хij = ai (i=1, m ) = 70 + 50 +80 = 200
де аi - запаси продукції, bj – заявки на продукцію.
Ми бачимо, що задача є збалансованою.
Складемо початковий план за методом Фогеля. Для цього визначимо штрафи по всіх рядках і стовпцях (різниця між двома мінімальними цінами рядка або стовпця). Потім вибираємо найбільший штраф і в рядку або стовпчику з максимальним штрафом вибираємо найменшу ціну і заповнюємо клітину максимально можливим перевезенням. При цьому вибуває з розгляду або постачальник або споживач.
Заповнивши всі перевезення, треба перевірити, щоб кількість базових клітин була m + n – 1 (кількість постачальників + кількість споживачів - 1).
В1 В2 В3 Запаси
А1 6
— 2
50 1
20 70 1 1 5 -
А2 4
10 8
— 2
40 50 2 2 2 2
А3 1
80 5
— 4
— 80 3 - - -
Заявки 90 50 60
3 3 1
2 6 1
2 - 1
4 - 2
Підрахуємо базові клітини:
m + n –1 = 3 + 3 – 1 = 5
Все вірно. Значення функції, яку ми мінімізували:
F = 10*4 + 80*1 + 50*2 + 20*1 + 40*2 = 320
Тепер перевіримо, чи оптимальний план за допомогою методу потенціалів. Потенціали – це числа Ui і Vj, що приписуються кожному постачальнику і кожному споживачу. Потенціали розставляються за базисними клітинами так, щоб виконувалась рівність: Ui + Vj = Cij
Один з потенціалів можна вибрати довільно. Найчастіше покладають U1 =0.
Для всіх порожніх клітин має виконуватись нерівність
Ui + Vj ≤ Cij
Якщо ця нерівність не виконується для порожніх клітин, то ці клітини називаються “поганими” і вони вимагають перевезення.
В1 В2 В3 Запаси аi
А1 6
— 2
50 1
20 70 0
А2 4
10 8
— 2
40 50 1
А3 1
80 5
— 4
— 80 -2
Заявки 90 50 60
βj 3 2 1
Поганих клітин немає, отже, початковий план і буде оптимальним.
Fмін = 320
Список використаної літератури:
1. Конспект