В хозяйстве необходимо за время уборки при заготовке силоса перевезти 4000 т зеленой массы с пяти полей (табл

В хозяйстве необходимо за время уборки при заготовке силоса перевезти 4000 т зеленой массы с пяти полей (табл. 4) к четырем фермам (табл. 5).
Расстояние перевозки зеленой массы с полей к фермам приведено в таблице 6.
Т а б л и ц а 4
Количество поступаемой зеленой массы с полей, т
№ варианта
(по предпоследней цифре номера зачетной книжки) Поле

1-е 2-е 3-е 4-е 5-е
0
1
2
3
4
5
6
7
8
9 800
1000
1200
400
600
1200
1000
400
800
600 1000
1200
400
600
800
1000
400
800
600
1200 1200
400
600
800
1000
400
800
600
1200
1000 400
600
800
1000
1200
800
600
1200
1000
400 600
800
1000
1200
400
600
1200
1000
400
800
Т а б л и ц а 5
Потребность ферм в зеленой массе, т
№ варианта
(по последней цифре номера зачетной книжки) Ферма

1-я 2-я 3-я 4-я
0
1
2
3
4
5
6
7
8
9 1000
600
800
1600
1000
1600
600
800
1000
800 600
800
1600
1000
1600
600
800
1000
800
1600 800
1600
1000
600
600
800
1000
1600
1600
600 1600
1000
600
800
800
1000
1600
600
600
1000
Т а б л и ц а 6
Расстояние от полей до ферм, км
Поля Фермы

1-я 2-я 3-я 4-я
1-е
2-е
3-е
4-е
5-е 5
9
7
5
6 6
7
1
2
4 2
4
4
2
3 2
6
5
4
4

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

1 2 3 4 Запасы
1 5 6 2 2 800
2 9 7 4 6 600
3 7 1 4 5 1200
4 5 2 2 4 1000
5 6 4 3 4 400
Потребности
600 800 1000 1600

∑a = 800 + 600 + 1200 + 1000 + 400 = 4000
∑b = 600 + 800 + 1000 + 1600 = 4000

1 2 3 4 Запасы
1 5 6 2 2 800
2 9 7 4 6 600
3 7 1 4 5 1200
4 5 2 2 4 1000
5 6 4 3 4 400
Потребности
600 800 1000 1600

I.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

1 2 3 4 Запасы
1 5 6 2[800] 2 800
2 9[600] 7 4 6 600
3 7 1[800] 4 5[400] 1200
4 5 2 2[200] 4[800] 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n – 1 = 8. Следовательно, опорный план является вырожденным.

F(x) = 2*800 + 9*600 + 1*800 + 5*400 + 2*200 + 4*800 + 4*400 = 15000

1 2 3 4 Запасы
1 5 6 2[800] 2 800
2 9[600] 7 4 6 600
3 7 1[800] 4 5[400] 1200
4 5 2 2[200] 4[800] 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
2
F(x) = 2*800 + 9*600 + 1*800 + 5*400 + 2*200 + 4*800 + 4*400 = 15000

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9[600] 7 4 6 600
3 7 1[800] 4 5[400] 1200
4 5 2 2[1000] 4 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
2.
F(x) = 2*800 + 9*600 + 1*800 + 5*400 + 2*1000 + 4*400 = 13400

1 2 3 4 Запасы
1 5 6 2[800] 2 800
2 9[600] 7 4 6 600
3 7 1 4 5[1200] 1200
4 5 2[800] 2[200] 4 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
2.
F(x) = 2*800 + 9*600 + 5*1200 + 2*800 + 2*200 + 4*400 = 16600

1 2 3 4 Запасы
1 5 6 2[600] 2[200] 800
2 9[600] 7 4 6 600
3 7 1[800] 4 5[400] 1200
4 5 2 2 4[1000] 1000
5 6 4 3[400] 4 400
Потребности
600 800 1000 1600
2.
F(x) = 2*600 + 2*200 + 9*600 + 1*800 + 5*400 + 4*1000 + 3*400 = 15000

1 2 3 4 Запасы
1 5 6 2[400] 2[400] 800
2 9 7 4[600] 6 600
3 7[400] 1[800] 4 5 1200
4 5 2 2 4[1000] 1000
5 6[200] 4 3 4[200] 400
Потребности
600 800 1000 1600
2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n – 1 = 8. Следовательно, опорный план является невырожденным.
F(x) = 2*400 + 2*400 + 4*600 + 7*400 + 1*800 + 4*1000 + 6*200 + 4*200 = 13600
II.
Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 2; 0 + v3 = 2; v3 = 2
u2 + v3 = 4; 2 + u2 = 4; u2 = 2
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u4 + v4 = 4; 2 + u4 = 4; u4 = 2
u5 + v4 = 4; 2 + u5 = 4; u5 = 2
u5 + v1 = 6; 2 + v1 = 6; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v2 = 1; 3 + v2 = 1; v2 = -2

v1=4 v2=-2 v3=2 v4=2
u1=0 5 6 2[400] 2[400] u2=2 9 7 4[600] 6
u3=3 7[400] 1[800] 4 5
u4=2 5 2 2 4[1000] u5=2 6[200] 4 3 4[200] Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;3): 3 + 2 > 4; ∆33 = 3 + 2 – 4 = 1
(4;1): 2 + 4 > 5; ∆41 = 2 + 4 – 5 = 1
(4;3): 2 + 2 > 2; ∆43 = 2 + 2 – 2 = 2
(5;3): 2 + 2 > 3; ∆53 = 2 + 2 – 3 = 1
max(1,1,2,1) = 2
Выбираем максимальную оценку свободной клетки (4;3): 2

1 2 3 4 Запасы
1 5 6 2[400][-] 2[400][+] 800
2 9 7 4[600] 6 600
3 7[400] 1[800] 4 5 1200
4 5 2 2[+] 4[1000][-] 1000
5 6[200] 4 3 4[200] 400
Потребности
600 800 1000 1600
Цикл приведен в таблице (4,3 → 4,4 → 1,4 → 1,3).

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9 7 4[600] 6 600
3 7[400] 1[800] 4 5 1200
4 5 2 2[400] 4[600] 1000
5 6[200] 4 3 4[200] 400
Потребности
600 800 1000 1600
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u4 + v4 = 4; 2 + u4 = 4; u4 = 2
u4 + v3 = 2; 2 + v3 = 2; v3 = 0
u2 + v3 = 4; 0 + u2 = 4; u2 = 4
u5 + v4 = 4; 2 + u5 = 4; u5 = 2
u5 + v1 = 6; 2 + v1 = 6; v1 = 4
u3 + v1 = 7; 4 + u3 = 7; u3 = 3
u3 + v2 = 1; 3 + v2 = 1; v2 = -2

v1=4 v2=-2 v3=0 v4=2
u1=0 5 6 2 2[800] u2=4 9 7 4[600] 6
u3=3 7[400] 1[800] 4 5
u4=2 5 2 2[400] 4[600] u5=2 6[200] 4 3 4[200] Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(4;1): 2 + 4 > 5; ∆41 = 2 + 4 – 5 = 1
Выбираем максимальную оценку свободной клетки (4;1): 5

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9 7 4[600] 6 600
3 7[400] 1[800] 4 5 1200
4 5[+] 2 2[400] 4[600][-] 1000
5 6[200][-] 4 3 4[200][+] 400
Потребности
600 800 1000 1600
Цикл приведен в таблице (4,1 → 4,4 → 5,4 → 5,1).

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9 7 4[600] 6 600
3 7[400] 1[800] 4 5 1200
4 5[200] 2 2[400] 4[400] 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u4 + v4 = 4; 2 + u4 = 4; u4 = 2
u4 + v1 = 5; 2 + v1 = 5; v1 = 3
u3 + v1 = 7; 3 + u3 = 7; u3 = 4
u3 + v2 = 1; 4 + v2 = 1; v2 = -3
u4 + v3 = 2; 2 + v3 = 2; v3 = 0
u2 + v3 = 4; 0 + u2 = 4; u2 = 4
u5 + v4 = 4; 2 + u5 = 4; u5 = 2

v1=3 v2=-3 v3=0 v4=2
u1=0 5 6 2 2[800] u2=4 9 7 4[600] 6
u3=4 7[400] 1[800] 4 5
u4=2 5[200] 2 2[400] 4[400] u5=2 6 4 3 4[400] Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;4): 4 + 2 > 5; ∆34 = 4 + 2 – 5 = 1
Выбираем максимальную оценку свободной клетки (3;4): 5

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9 7 4[600] 6 600
3 7[400][-] 1[800] 4 5[+] 1200
4 5[200][+] 2 2[400] 4[400][-] 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
Цикл приведен в таблице (3,4 → 3,1 → 4,1 → 4,4).

1 2 3 4 Запасы
1 5 6 2 2[800] 800
2 9 7 4[600] 6 600
3 7[0] 1[800] 4 5[400] 1200
4 5[600] 2 2[400] 4 1000
5 6 4 3 4[400] 400
Потребности
600 800 1000 1600
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v4 = 2; 0 + v4 = 2; v4 = 2
u3 + v4 = 5; 2 + u3 = 5; u3 = 3
u3 + v1 = 7; 3 + v1 = 7; v1 = 4
u4 + v1 = 5; 4 + u4 = 5; u4 = 1
u4 + v3 = 2; 1 + v3 = 2; v3 = 1
u2 + v3 = 4; 1 + u2 = 4; u2 = 3
u3 + v2 = 1; 3 + v2 = 1; v2 = -2
u5 + v4 = 4; 2 + u5 = 4; u5 = 2

v1=4 v2=-2 v3=1 v4=2
u1=0 5 6 2 2[800] u2=3 9 7 4[600] 6
u3=3 7[0] 1[800] 4 5[400] u4=1 5[600] 2 2[400] 4
u5=2 6 4 3 4[400]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят: F(x) = 2*800 + 4*600 + 1*800 + 5*400 + 5*600 + 2*400 + 4*400 = 12200

Таким образом,
Из 1-го поля направить в 4-ю ферму
Из 2-го поля направить в 3-ю ферму
Из 3-го поля направить во 2-ю ферму (800), в 4-ю ферму (400)
Из 4-го поля направить в 1-ую ферму (600), в 3-ю ферму (400)
Из 5-го поля направить в 4-ю ферму

user_logo

user431306 4.7

Помогу с написанием работ по профилям: Гос. и мун. управление, Менеджмент организации, Экономика, Управление персоналом, Городское хозяйство, Вышмат! С моим дипломом можно ознакомиться в портфолио!

Нанять автора

Готовые работы на продажу

Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Нажимая "Купить" вы будете перенаправлены на страницу карточки работы.

Гарантия на работу 10 дней.