Контрольная работа по "Математические методы и модели"

х₁↔ у₅,    х₂↔ у₄,   х₃↔ у₁,   х₄↔ у₂,  х₅↔ у₃

Таблица 4

х1	х2	х3	х4	х5
0	0	0	10	5
у4	у5	у1	у2	у3

 

Тогда оптимальное  базисное решение двойственной задачи:

У=(0;10;5;0;0), откуда у₁ =0, у₂ =10 , у₃ =5.

zmin=560*0 + 300*10 + 332*5 = 4660,

zmin = fmax= 4660 ден. ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ЗАДАЧА 2. «ТРАНСПОРТНАЯ  ЗАДАЧА»

 

На три  склада А₁, А₂, А₃ завезли каменный уголь в количестве а₁, а₂, а₃ тонн соответственно. Уголь требуется завезти в пять котелен В₁, В₂, В3, В₄, В₅  в количествах b₁, b₂, b₃, b₄, b₅ тонн соответственно. Стоимость перевозки одной тонны угля с i-го склада на j-ю котельную равна с_ij.

 

Потребители Базы	В1	В2	В3	В4	В5	Запасы  аi
А1	с11	с12	с13	с14	с15	а1
А2	с21	с22	с23	с24	с25	а2
А3	с31	с32	с33	с34	с35	а3
Потребности, bj	b1	b2	b3	b4	b5	Sаi =Sbj

 

Требуется спланировать перевозки так, чтобы  их общая стоимость была минимальной.

 

Замечание. При решении транспортной задачи первый опорный план находить методом  минимальной стоимости. Оптимальный  план искать методом потенциалов.

 

	В1	В2	В3	В4	В5	аi
А1	14	8	17	5	3	120
А2	21	10	7	3	10	150
А3	4	5	12	8	17	100
bj	85	65	90	60	70	370

 

Решение:

 

Потребители Базы	В1	В2	В3	В4	В5	Запасы  аi
А1	14	8	17	5	3	120
А2	21	10	7	3	10	150
А3	4	5	12	8	17	100
Потребности, bj	85	65	90	60	70	370

 

Опорный план задачи составим методом наименьших затрат.

 

 min c_ij = c₁₅ = 3, a₁ = 120, b1 =70, min{120; 70} = 70. Число 70 записываем в клетку (1;5), теперь a₁ =120-70=50, b₅ = 0.

 

min c_ij = c₂₄ = 3, a₂= 150, b4 =60, min{150; 60} = 60. Число 60 записываем в клетку (2; 4), теперь a₂ =90, b₄ = 0.

 

min c_ij = c₃₁ = 4, a₃ =100, b1 = 85, min{100; 85} = 85. Число 85 записываем в клетку (3; 1), теперь a₃ = 15, b₁=0.

 

min c_ij = c₃₂ = 5, a₃ = 15, b3 = 65, min{15; 65} =15. Число 15 записываем в клетку (3;2), теперь a₃ = 70, b₃ = 0.

 

Распределяем таким образом грузы до тех пор, пока все запасы не будут исчерпаны, а все поставки не будут удовлетворены. Получим первый опорный план задачи:

 

Таблица 6

ui	Потребители Базы	В1		В2		В3		В4		В5		Запасы  аi
0	А1	-	14	50	8	-	17	0	5	70	3	120
-2	А2	-	21	-	10	90	7	60	3	-	10	150
-3	А3	85	4	15	5	-	12	-	8	-	17	100
	Потребности, bi	85		65		90		60		70
	vj	7		8		9		5		3

 

Стоимость перевозок: f = 8 * 50 + 3 * 70 + 7 * 90 + 3 * 60 + 4 * 85 + 5 * 15 = 1835.

Число занятых  клеток m+n-1=3+5-1=7, значит план невырожденный, поэтому решим задачу методом  потенциалов.

Поскольку, число базисных клеток - 7, а общее  количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать  произвольно.

Примем  u₁ = 0

v2 + u1 = c12

v2 + u1 = 8

v2 = 8 - 0 = 8

v4 + u1 = c14

v4 + u1 = 5

v4 = 5 - 0 = 5

v5 + u1 = c15

v5 + u1 = 3

v5 = 3 - 0 = 3

v4 + u2 = c24

v4 + u2 = 3

u2 = 3 - 5 = -2

v2 + u3 = c32

v2 + u3 = 5

u3 = 5 - 8 = -3

v3 + u2 = c23

v3 + u2 = 7

v3 = 7 - ( -2 ) = 9

v1 + u3 = c31

v1 + u3 = 4

v1 = 4 - ( -3 ) = 7

 

Условия оптимальности  для не занятых клеток u_i + v_i ≤ c_ij  выполняется, следовательно, найдено оптимальное решение.

 

 

 

 

 

 

ЗАДАЧА 3.

 

Даны  работы(i; j) и их длительность t_ij. Построить сетевую модель, разбить по слоям вершины и дуги, найти критический путь.

Работа(i; j)	Время tij	Работа (i; j)	Время  tij
(0, 1)	6	(2, 3)	3
(1, 2)	7	(2, 5)	8
(1, 3)	5	(3, 5)	9
(1, 4)	4	(4, 5)	6

 

 

 

 

 

 

 

Решение:

 

Сетевая модель представляет собой  план выполнения некоторого комплекса  взаимосвязанных работ, заданного  в специфической форме сети, графическое  изображение которой называется сетевым графиком (графом).

Зададим граф в виде матрицы смежности, разобьём по слоям вершины и дуги:

0

1

2

3

4

5

6

7

5

4

8

3

9

6

1 слой

2 слой

3 слой

4 слой

5 слой

 

Полный путь называется критическим, если сумма времён выполнения работ, в него входящих, самая большая среди времён всех других полных путей.

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

τ = t (0; 1)+ t (1; 2)+ t (2; 3)+ t (3; 5) = 6+7+3+9 = 25

Критический путь имеет вид: 0→1→2→3→5