На трех заводах производится однородная продукции в количестве единиц. Четырем потребителям требуется соответственно единиц продукции. Расходы по перевозке единицы продукции с i-го завода j-му потребителю известны (см. Транспортную таблицу). Требуется спланировать перевозку продукции так, чтобы затраты на транспортировку были минимальными.
1) Записать математическую модель транспортной задачи.
2) Найти опорное решение методом наименьшей стоимости и методом северо-западного угла.
3) Опорное решение проверить методом потенциалов, получить оптимальное решение.
Транспортная таблица
Заводы Потребители Запас
продукции, ед.
В1 В2 В3 В4
А1 8 3 4 6 350
А2 3 2 5 3 450
А3 4 7 9 6 300
Потребность в продукции, ед. 200 300 250 350
Решение
Математическая модель транспортной задачи:F = ∑∑cijxij, (1)при условиях:∑xij = ai, i = 1,2,…, m, (2)∑xij = bj, j = 1,2,…, n, (3)xij ≥ 0Запишем экономико-математическую модель для нашей задачи.Переменные:x11 – количество груза из 1-го завода к 1-у потребителю.x12 – количество груза из 1-го завода к 2-у потребителю.x13 – количество груза из 1-го завода к 3-у потребителю.x14 – количество груза из 1-го завода к 4-у потребителю.x21 – количество груза из 2-го завода к 1-у потребителю.x22 – количество груза из 2-го завода к 2-у потребителю.x23 – количество груза из 2-го завода к 3-у потребителю.x24 – количество груза из 2-го завода к 4-у потребителю.x31 – количество груза из 3-го завода к 1-у потребителю.x32 – количество груза из 3-го завода к 2-у потребителю.x33 – количество груза из 3-го завода к 3-у потребителю.x34 – количество груза из 3-го завода к 4-у потребителю.Ограничения по запасам:x11 + x12 + x13 + x14 ≤ 350 (для 1 базы)x21 + x22 + x23 + x24 ≤ 450 (для 2 базы)x31 + x32 + x33 + x34 ≤ 300 (для 3 базы)Ограничения по потребностям:x11 + x21 + x31 = 200 (для 1-го потребителя.)x12 + x22 + x32 = 300 (для 2-го потребителя.)x13 + x23 + x33 = 250 (для 3-го потребителя.)x14 + x24 + x34 = 350 (для 4-го потребителя.)Целевая функция:8x11+3x12+4x13+6x14+3x21+2x22+5x23+3x24+4x31+7x32+9x33+6x34 → min
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 350 + 450 + 300 = 1100∑b = 200 + 300 + 250 + 350 = 1100
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Отыскиваемый элемент равен c22=2. Для этого элемента запасы равны 450, потребности 300. Т.к. min является 300, то вычитаем его.x22 = min(450,300) = 300.
8 x 4 6 350
3 2 5 3 450 - 300 = 150
4 x 9 6 300
200 300 - 300 = 0 250 350
Отыскиваемый элемент равен c21=3. Для этого элемента запасы равны 150, потребности 200. Т.к. min является 150, то вычитаем его.x21 = min(150,200) = 150.
8 x 4 6 350
3 2 x x 150 - 150 = 0
4 x 9 6 300
200 - 150 = 50 0 250 350
Отыскиваемый элемент равен c13=4. Для этого элемента запасы равны 350, потребности 250. Т.к. min является 250, то вычитаем его.x13 = min(350,250) = 250.
8 x 4 6 350 - 250 = 100
3 2 x x 0
4 x x 6 300
50 0 250 - 250 = 0 350
Отыскиваемый элемент равен c31=4. Для этого элемента запасы равны 300, потребности 50. Т.к. min является 50, то вычитаем его.x31 = min(300,50) = 50.
x x 4 6 100
3 2 x x 0
4 x x 6 300 - 50 = 250
50 - 50 = 0 0 0 350
Отыскиваемый элемент равен c14=6. Для этого элемента запасы равны 100, потребности 350. Т.к. min является 100, то вычитаем его.x14 = min(100,350) = 100.
x x 4 6 100 - 100 = 0
3 2 x x 0
4 x x 6 250
0 0 0 350 - 100 = 250
Отыскиваемый элемент равен c34=6. Для этого элемента запасы равны 250, потребности 250. Т.к. min является 250, то вычитаем его.x34 = min(250,250) = 250.
x x 4 6 0
3 2 x x 0
4 x x 6 250 - 250 = 0
0 0 0 250 - 250 = 0
В результате получен первый опорный план, который является допустимым, так как все грузы из заводов вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
B1 B2 B3 B4 Запасы
A1 8 3 4[250] 6[100] 350
A2 3[150] 2[300] 5 3 450
A3 4[50] 7 9 6[250] 300
Потребности 200 300 250 350
Значение целевой функции для этого опорного плана равно:
F(x) = 4∙250 + 6∙100 + 3∙150 + 2∙300 + 4∙50 + 6∙250 = 4350
Проверим оптимальность опорного плана
. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 4; 0 + v3 = 4; v3 = 4u1 + v4 = 6; 0 + v4 = 6; v4 = 6u3 + v4 = 6; 6 + u3 = 6; u3 = 0u3 + v1 = 4; 0 + v1 = 4; v1 = 4u2 + v1 = 3; 4 + u2 = 3; u2 = -1u2 + v2 = 2; -1 + v2 = 2; v2 = 3
v1=4 v2=3 v3=4 v4=6
u1=0 8 3 4[250] 6[100]
u2=-1 3[150] 2[300] 5 3
u3=0 4[50] 7 9 6[250]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(2;4): -1 + 6 > 3; ∆24 = -1 + 6 - 3 = 2 > 0
Выбираем максимальную оценку свободной клетки (2;4): 3
Для этого в перспективную клетку (2;4) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 8 3 4[250] 6[100] 350
2 3[150][-] 2[300] 5 3[+] 450
3 4[50][+] 7 9 6[250][-] 300
Потребности 200 300 250 350
Цикл приведен в таблице (2,4 → 2,1 → 3,1 → 3,4).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 1) = 150. Прибавляем 150 к объемам грузов, стоящих в плюсовых клетках и вычитаем 150 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 Запасы
A1 8 3 4[250] 6[100] 350
A2 3 2[300] 5 3[150] 450
A3 4[200] 7 9 6[100] 300
Потребности 200 300 250 350
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v3 = 4; 0 + v3 = 4; v3 = 4u1 + v4 = 6; 0 + v4 = 6; v4 = 6u2 + v4 = 3; 6 + u2 = 3; u2 = -3u2 + v2 = 2; -3 + v2 = 2; v2 = 5u3 + v4 = 6; 6 + u3 = 6; u3 = 0u3 + v1 = 4; 0 + v1 = 4; v1 = 4
v1=4 v2=5 v3=4 v4=6
u1=0 8 3 4[250] 6[100]
u2=-3 3 2[300] 5 3[150]
u3=0 4[200] 7 9 6[100]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(1;2): 0 + 5 > 3; ∆12 = 0 + 5 - 3 = 2 > 0
Выбираем максимальную оценку свободной клетки (1;2): 3
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
1 2 3 4 Запасы
1 8 3[+] 4[250] 6[100][-] 350
2 3 2[300][-] 5 3[150][+] 450
3 4[200] 7 9 6[100] 300
Потребности 200 300 250 350
Цикл приведен в таблице (1,2 → 1,4 → 2,4 → 2,2).
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 4) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.
B1 B2 B3 B4 Запасы
A1 8 3[100] 4[250] 6 350
A2 3 2[200] 5 3[250] 450
A3 4[200] 7 9 6[100] 300
Потребности 200 300 250 350
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v2 = 3; 0 + v2 = 3; v2 = 3u2 + v2 = 2; 3 + u2 = 2; u2 = -1u2 + v4 = 3; -1 + v4 = 3; v4 = 4u3 + v4 = 6; 4 + u3 = 6; u3 = 2u3 + v1 = 4; 2 + v1 = 4; v1 = 2u1 + v3 = 4; 0 + v3 = 4; v3 = 4
v1=2 v2=3 v3=4 v4=4
u1=0 8 3[100] 4[250] 6
u2=-1 3 2[200] 5 3[250]
u3=2 4[200] 7 9 6[100]
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vj ≤ cij.
Минимальные затраты составят:
F(x) = 3∙100 + 4∙250 + 2∙200 + 3∙250 + 4∙200 + 6∙100 = 3850
Анализ оптимального плана.
Из 1-го завода необходимо груз направить к 2-у потребителю (100 ед.), к 3-у потребителю (250 ед.).
Из 2-го завода необходимо груз направить к 2-у потребителю (200 ед.), к 4-у потребителю (250 ед.).
Из 3-го завода необходимо груз направить к 1-у потребителю (200 ед.), к 4-у потребителю (100 ед.).
2
Задать вопрос
на новый заказ в Автор24.
