Задача по "Математике"

МІНІСТЕРСВО ОСВІТИ І НАУКИ УКРАЇНИ

Національний Авіаційний Університет

 

 

 

 

 

 

 

РОЗРАХУНКОВО-ГРАФІЧНА РОБОТА

з дисципліни

“Дослідження  операцій”

 

 

 

 

 

 

 

                                                                                    

 

    

Виконав: студент 411 гр. ФКС

                                                                           Гіндюк О.В.

Варіант № 4

  Прийняв: Артамонов  Є.Б.                              

                                  

 

 

 

 

Київ – 2004

 

Дані варіанту

1. Розрахувати задачу графічно і симплекс-методом.

 F(x) = -7x₁ + x₂  ® max

9x₁ + 4x₂ £ 110

11x₁ - 3x₂ £ 24

 2x₁ - 7x₂ ³ 15

  x_j ³ 0.

 

2. Побудувати математичну модель і розрахувати транспортну задачу.

На 3 бази А₁, А₂, А₃ потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 3 пункти призначення В₁, В₂, В₃ відповідно у кількості 90, 50 і 60 од. Тарифи перевезень, одиниць вантажу кожного з пунктів відправлення та призначення виставляються студентом самостійно.

 

 

1. Вирахуємо задачу графічним методом:

F(x) = -7x₁ + x₂  ® max

9x₁ + 4x₂ £ 110

11x₁ - 3x₂ £ 24

 2x₁ - 7x₂ ³ 15

  x_j ³ 0.

Побудуємо на графіку  обмеження:

9x₁ + 4x₂ £ 110

11x₁ - 3x₂ £ 24

 2x₁ - 7x₂ ³ 15

     x_j ³ 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) = -7x₁ + x₂  ® max

9x₁ + 4x₂ £ 110

11x₁ - 3x₂ £ 24

2x₁ - 7x₂ ³ 15

  x_j ³ 0.

Приведемо систему обмежень до розширеного  вигляду:

9x₁ + 4x₂ + x₃= 110

11x₁ - 3x₂ + x₄ = 24

-2x₁ + 7x₂ + x₅= -15

  x_j ³ 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 бази А₁, А₂, А₃ потрапив однорідний вантаж у кількості, відповідно рівній 70, 50 і 80 од. Цей вантаж потрібно перевезти в 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=

Де Х_ij – це кількість товару, який перевозиться із А_i в В_j,

С_ij – ціна перевезення.

Задачу потрібно перевірити, чи є  вона збалансованою.

= b_j (j=) = 90 + 50 + 60 = 200

= a_i (i=) = 70 + 50 +80 = 200

 де а_i - запаси продукції, b_j – заявки на продукцію.

 

Ми бачимо, що задача є  збалансованою.

 

Складемо початковий план за методом Фогеля. Для цього визначимо штрафи по всіх рядках і стовпцях (різниця між двома мінімальними цінами рядка або стовпця). Потім вибираємо найбільший штраф і в рядку або стовпчику з максимальним штрафом вибираємо найменшу ціну і заповнюємо клітину максимально можливим перевезенням. При цьому вибуває з розгляду або постачальник або споживач.

Заповнивши всі перевезення, треба перевірити, щоб кількість  базових клітин була 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

Тепер перевіримо, чи оптимальний  план за допомогою методу потенціалів. Потенціали – це числа U_i і V_j, що приписуються кожному постачальнику і кожному споживачу. Потенціали розставляються за базисними клітинами так, щоб виконувалась рівність: U_i + V_j = C_ij

Один з потенціалів  можна вибрати довільно. Найчастіше покладають U₁ =0.

Для всіх порожніх клітин має виконуватись нерівність

U_i + V_j ≤ C_ij

Якщо ця нерівність не виконується для порожніх клітин, то ці клітини називаються  “поганими” і вони вимагають перевезення.

 

 

 

	В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. Конспект