Контрольная работа по "Методам оптимальных решений"

 

Цикл приведен в таблице (1,2; 1,3; 3,3; 3,1; 2,1; 2,2; ).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 13. Прибавляем 13 к объемам грузов, стоящих в плюсовых клетках и вычитаем 13 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

	1	2	3	4	Запасы
1	8	3[13]	6[7]	0	20
2	4[15]	2	5	0	15
3	9[2]	4	7[18]	0[10]	30
Потребности	17	13	25	10

 

Проверим оптимальность  опорного плана. Найдем предварительные  потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₃ = 6; 0 + v₃ = 6; v₃ = 6

u₃ + v₃ = 7; 6 + u₃ = 7; u₃ = 1

u₃ + v₁ = 9; 1 + v₁ = 9; v₁ = 8

u₂ + v₁ = 4; 8 + u₂ = 4; u₂ = -4

u₃ + v₄ = 0; 1 + v₄ = 0; v₄ = -1

	v1=8	v2=3	v3=6	v4=-1
u1=0	8	3[13]	6[7]	0
u2=-4	4[15]	2	5	0
u3=1	9[2]	4	7[18]	0[10]

 

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты  составят:

F(x) = 3*13 + 6*7 + 4*15 + 9*2 + 7*18 + 0*10  = 285

Ответ:

Из 1-го склада необходимо груз направить в 2-й магазин (13), в 3-й магазин (7)

Из 2-го склада необходимо весь груз направить в 1-й магазин

Из 3-го склада необходимо груз направить в 1-й магазин (2), в 3-й магазин (18)

На 3-ом складе остался  невостребованным груз в количестве 10 ед.

Минимальные затраты  составят 285 у.е.

Задача №4.

Найти кратчайший путь от вершины х₀ до остальных вершин графа. Граф описывается перечнем всех своих дуг (верхняя строка) и их длинами (нижняя строка). Дуга х_iх_g с обозначается парой чисел ig.

Решение:

Путь	Возможные пути	Кратчайший путь от вершины  х0
0 - 1	0 – 1 = 16	0 – 1 = 16
0 - 2	0 –2 = 28	0 –2 = 28
0 - 3	0 - 3 = 25	0 - 3 = 25
0 - 4	0 –1 – 4 = 37	0 –1 – 4 = 37
0 - 5	0 – 2 - 5 = 47	0 – 2 - 5 = 47
0 – 6	0 – 6 =19	0 – 6 =19
0 - 7	0 – 2 - 7 = 45	0 – 2 - 7 = 45
0 – 8	0 –6 – 8 = 34	0 –6 – 8 = 34
0 - 9	0 –6 – 9 = 26	0 –6 – 9 = 26
0 - 10	0 – 6– 9 - 10 = 44	0 – 6– 9 - 10 = 44

 

Ответ:

Путь	Кратчайший путь от вершины  х0
0 - 1	0 – 1 = 16
0 - 2	0 –2 = 28
0 - 3	0 - 3 = 25
0 - 4	0 –1 – 4 = 37
0 - 5	0 – 2 - 5 = 47
0 – 6	0 – 6 =19
0 - 7	0 – 2 - 7 = 45
0 – 8	0 –6 – 8 = 34
0 - 9	0 –6 – 9 = 26
0 - 10	0 – 6– 9 - 10 = 44

 

 

Задача № 5.

Найти оптимальный план транспортной задачи, описываемой соответствующей таблицей, удовлетворяющий указанным ниже дополнительным условиям.

ДУ: х₃₂ < 15

Решение:

Математическая модель транспортной задачи:

F = ∑∑c_ijx_ij,    (1)

при условиях:

∑x_ij = a_i,  i = 1,2,…, m,   (2)

∑x_ij = b_j,  j = 1,2,…, n,   (3)

Стоимость доставки единицы  груза из каждого пункта отправления  в соответствующие пункты назначения задана матрицей тарифов

	1	2	3	Запасы
1	13	12	14	25
2	16	11	17	28
3	12	14	11	42
Потребности	25	40	50

 

Проверим необходимое  и достаточное условие разрешимости задачи.

∑a = 25 + 28 + 42 = 95

∑b = 25 + 40 + 50 = 115

Как видно, суммарная  потребность груза&n