Составление оптимального плана перевозок На трех базах А1 А2

1. Опорный план перевозок груза диагональным методом.
Экономико-математическая модель транспортной задачи.
Переменные:
x11 – количество груза из 1-й базы к 1-у потребителю.
x12 – количество груза из 1-й базы к 2-у потребителю.
x13 – количество груза из 1-й базы к 3-у потребителю.
x14 – количество груза из 1-й базы к 4-у потребителю.
x15 – количество груза из 1-й базы к 5-у потребителю.
x21 – количество груза из 2-й базы к 1-у потребителю.
x22 – количество груза из 2-й базы к 2-у потребителю.
x23 – количество груза из 2-й базы к 3-у потребителю.
x24 – количество груза из 2-й базы к 4-у потребителю.
x25 – количество груза из 2-й базы к 5-у потребителю.
x31 – количество груза из 3-й базы к 1-у потребителю.
x32 – количество груза из 3-й базы к 2-у потребителю.
x33 – количество груза из 3-й базы к 3-у потребителю.
x34 – количество груза из 3-й базы к 4-у потребителю.
x35 – количество груза из 3-й базы к 5-у потребителю.
Ограничения по запасам:
x11 + x12 + x13 + x14 + x15 ≤ 250 (для 1-й базы)
x21 + x22 + x23 + x24 + x25 ≤ 400 (для 2-й базы)
x31 + x32 + x33 + x34 + x35 ≤ 350 (для 3-й базы)
Ограничения по потребностям:
x11 + x21 + x31 = 300 (для 1-го потребителя)
x12 + x22 + x32 = 160 (для 2-го потребителя)
x13 + x23 + x33 = 220 (для 3-го потребителя)
x14 + x24 + x34 = 180 (для 4-го потребителя)
x15 + x25 + x35 = 140 (для 5-го потребителя)
Целевая функция:
9x11 + 45x12 + 35x13 + 20x14 + 7x15 + 15x21 + 35x22 + 12x23 + 11x24 + 6x25 + 16x31 + 19x32 + 40x33 + 15x34 + 25x35 → min
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 250 + 400 + 350 = 1000
∑b = 300 + 160 + 220 + 180 + 140 = 1000
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
Распределительная таблица:
B1
B2
B3
B4
B5
Запасы
A1
9 45 35 20 7 250
A2
15 35 12 11 6 400
A3
16 19 40 15 25 350
Потребности 300 160 220 180 140
Используя метод северо-западного угла, построим первый опорный план транспортной задачи. План начинается заполняться с верхнего левого угла. Искомый элемент равен c11 = 9. Для этого элемента запасы равны 250, потребности 300. Минимальным является 250, поэтому вычитаем его.
9 x x x x 250 – 250 = 0
15 35 12 11 6 400
16 19 40 15 25 350
300 – 250 = 50 160 220 180 140
Искомый элемент равен c21 = 15. Для этого элемента запасы равны 400, потребности 50. Минимальным является 50, поэтому вычитаем его.
9 x x x x 0
15 35 12 11 6 400 – 50 = 350
x 19 40 15 25 350
50 – 50 = 0 160 220 180 140
Искомый элемент равен c22=35. Для этого элемента запасы равны 350, потребности 160. Минимальным является 160, поэтому вычитаем его.
9 x x x x 0
15 35 12 11 6 350 – 160 = 190
x x 40 15 25 350
0 160 – 160 = 0 220 180 140
Искомый элемент равен c23 = 12. Для этого элемента запасы равны 190, потребности 220. Минимальным является 190, поэтому вычитаем его.
9 x x x x 0
15 35 12 x x 190 – 190 = 0
x x 40 15 25 350
0 0 220 – 190 = 30 180 140
Искомый элемент равен c33 = 40. Для этого элемента запасы равны 350, потребности 30. Минимальным является 30, поэтому вычитаем его.
9 x x x x 0
15 35 12 x x 0
x x 40 15 25 350 – 30 = 320
0 0 30 – 30 = 0 180 140
Искомый элемент равен c34 = 15. Для этого элемента запасы равны 320, потребности 180. Минимальным является 180, поэтому вычитаем его.
9 x x x x 0
15 35 12 x x 0
x x 40 15 25 320 – 180 = 140
0 0 0 180 – 180 = 0 140
Искомый элемент равен c35 = 25. Для этого элемента запасы равны 140, потребности 140. Минимальным является 140, поэтому вычитаем его.
9 x x x x 0
15 35 12 x x 0
x x 40 15 25 140 – 140 = 0
0 0 0 0 140 – 140 = 0
В результате получен первый опорный план:
B1
B2
B3
B4
B5
Запасы
A1
9 [250] 45 35 20 7 250
A2
15 [50] 35 [160] 12 [190] 11 6 400
A3
16 19 40 [30] 15 [180] 25 [140] 350
Потребности 300 160 220 180 140
Этот план является допустимым, т. к. все грузы из баз вывезены, потребность потребителей удовлетворена, а план соответствует системе ограничений транспортной задачи.
Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n – 1 = 7. Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана:
F(x) = 9 × 250 + 15 × 50 + 35 × 160 + 12 × 190 + 40 × 30 + 15 × 180 + 25 × 140 = 18280
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj . по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 15; 9 + u2 = 15; u2 = 6
u2 + v2 = 35; 6 + v2 = 35; v2 = 29
u2 + v3 = 12; 6 + v3 = 12; v3 = 6
u3 + v3 = 40; 6 + u3 = 40; u3 = 34
u3 + v4 = 15; 34 + v4 = 15; v4 = -19
u3 + v5 = 25; 34 + v5 = 25; v5 = -9
v1=9 v2=29 v3=6 v4=-19 v5=-9
u1=0 9 [250] 45 35 20 7
u2=6 15 [50] 35 [160] 12 [190] 11 6
u3=34 16 19 40 [30] 15 [180] 25 [140]
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 34 + 9 > 16; ∆31 = 34 + 9 – 16 = 27 > 0
(3;2): 34 + 29 > 19; ∆32 = 34 + 29 – 19 = 44 > 0
max(27, 44) = 44
Выбираем максимальную оценку свободной клетки (3;2): 19. Для этого в перспективную клетку (3;2) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки. Получим:
1 2 3 4 5 Запасы
1 9 [250] 45 35 20 7 250
2 15 [50] 35 [160] [-] 12 [190] [+] 11 6 400
3 16 19 [+] 40 [30] [-] 15 [180] 25 [140] 350
Потребности 300 160 220 180 140
Цикл: 3,2 → 3,3 → 2,3 → 2,2.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (3, 3) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план:
B1
B2
B3
B4
B5
Запасы
A1
9 [250] 45 35 20 7 250
A2
15 [50] 35 [130] 12 [220] 11 6 400
A3
16 19 [30] 40 15 [180] 25 [140] 350
Потребности 300 160 220 180 140
Снова проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 15; 9 + u2 = 15; u2 = 6
u2 + v2 = 35; 6 + v2 = 35; v2 = 29
u3 + v2 = 19; 29 + u3 = 19; u3 = -10
u3 + v4 = 15; -10 + v4 = 15; v4 = 25
u3 + v5 = 25; -10 + v5 = 25; v5 = 35
u2 + v3 = 12; 6 + v3 = 12; v3 = 6
v1=9 v2=29 v3=6 v4=25 v5=35
u1=0 9 [250] 45 35 20 7
u2=6 15 [50] 35 [130] 12 [220] 11 6
u3=-10 16 19 [30] 40 15 [180] 25 [140]
Этот опорный план не является оптимальным, т. к. существуют оценки свободных клеток, для которых ui + vj > cij
(1;4): 0 + 25 > 20; ∆14 = 0 + 25 – 20 = 5 > 0
(1;5): 0 + 35 > 7; ∆15 = 0 + 35 – 7 = 28 > 0
(2;4): 6 + 25 > 11; ∆24 = 6 + 25 – 11 = 20 > 0
(2;5): 6 + 35 > 6; ∆25 = 6 + 35 – 6 = 35 > 0
max(5, 28, 20, 35) = 35
Выбираем максимальную оценку свободной клетки (2;5): 6. Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки. Получим:
1 2 3 4 5 Запасы
1 9 [250] 45 35 20 7 250
2 15 [50] 35 [130] [-] 12 [220] 11 6 [+] 400
3 16 19 [30] [+] 40 15 [180] 25 [140] [-] 350
Потребности 300 160 220 180 140
Цикл: 2,5 → 2,2 → 3,2 → 3,5.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т. е. у = min (2, 2) = 130. Прибавляем 130 к объемам грузов, стоящих в плюсовых клетках и вычитаем 130 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план:
B1
B2
B3
B4
B5
Запасы
A1
9 [250] 45 35 20 7 250
A2
15 [50] 35 12 [220] 11 6 [130] 400
A3
16 19 [160] 40 15 [180] 25 [10] 350
Потребности 300 160 220 180 140
Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.
u1 + v1 = 9; 0 + v1 = 9; v1 = 9
u2 + v1 = 15; 9 + u2 = 15; u2 = 6
u2 + v3 = 12; 6 + v3 = 12; v3 = 6
u2 + v5 = 6; 6 + v5 = 6; v5 = 0
u3 + v5 = 25; 0 + u3 = 25; u3 = 25
u3 + v2 = 19; 25 + v2 = 19; v2 = -6
u3 + v4 = 15; 25 + v4 = 15; v4 = -10
v1=9 v2=-6 v3=6 v4=-10 v5=0
u1=0 9 [250] 45 35 20 7
u2=6 15 [50] 35 12 [220] 11 6 [130]
u3=25 16 19 [160] 40 15 [180] 25 [10]
И этот опорный план не является оптимальным, т. к. существуют оценки свободных клеток, для которых ui + vj > cij
(3;1): 25 + 9 > 16; ∆31 = 25 + 9 – 16 = 18 > 0
Выбираем максимальную оценку свободной клетки (3;1): 16. Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки. Получим:
1 2 3 4 5 Запасы
1 9 [250] 45 35 20 7 250
2 15 [50] [-] 35 12 [220] 11 6 [130] [+] 400
3 16 [+] 19 [160] 40 15 [180] 25 [10] [-] 350
Потребности 300 160 220 180 140
Цикл: 3,1 → 3,5 → 2,5 → 2,1.
Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е