Планирование перевозок
Товары с т баз поставляются в п магазинов. Потребности магазинов в товарах равны b j тыс. ед. j 1,...,n . Запасы товаров на базах составляют a i - тыс. ед., i 1,...,m. Затраты на перевозку 1 тыс. ед. товара в ден. ед. представлены матрицей затрат Cmn . Запланировать перевозку с минимальными затратами при заданном дополнительном условии.
Требуется:
свести исходные данные в таблицу;
Магазин B1 B2
Bn
Запасы
…
товаров на
База
базах, тыс.ед.
A1 c11 c12 … c1n a1
A2 c21 c22 … c2n a2
... … ... …
…
Am
cm1 cm2 … cmn
am
c2 n
Потребности
m
магазинов,
ai
тыс. ед. b1 b2 … bn
i 1
n
b j
j 1
1019175-2924810004106545-113030000
2)составить математическую модель задачи;
3)привести ее к стандартной транспортной задаче (с балансом);
4)построить начальный опорный план задачи (методом минимального элемента);
5)решить задачу, используя MS Excel;
6)проанализировать результаты решения.
30480013017500
Решение
-709975172900Магазин
База В1
В2
В3 В4
В5 Запасы товаров на базах, тыс. ед.
А1
5 4 3 2 5 16
А2
7 3 6 2 4 11
А3 1 4 2 4 6 12
А4
7 4 6 8 5 13
Потребности магазинов, тыс. ед. 10 9 8 15 7 -70741830252
49
Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 16 + 11 + 12 + 13 = 52
∑b = 10 + 9 + 8 + 15 + 7 = 49
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 3 (52—49). Тарифы перевозки единицы груза к этому магазину полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 B4 B5 B6 Запасы
A1 5 4 3 2 5 0 16
A2 7 3 6 2 4 0 11
A3 1 4 2 4 6 0 12
A4 7 4 6 8 5 0 13
Потребности 10 9 8 15 7 3
Этап I. Поиск первого опорного плана.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен c31=1
. Для этого элемента запасы равны 12, потребности 10. Поскольку минимальным является 10, то вычитаем его.
x31 = min(12,10) = 10.
x 4 3 2 5 0 16
x 3 6 2 4 0 11
1 4 2 4 6 0 12 - 10 = 2
x 4 6 8 5 0 13
10 - 10 = 0 9 8 15 7 3
Искомый элемент равен c14=2. Для этого элемента запасы равны 16, потребности 15. Поскольку минимальным является 15, то вычитаем его.
x14 = min(16,15) = 15.
x 4 3 2 5 0 16 - 15 = 1
x 3 6 x 4 0 11
1 4 2 x 6 0 2
x 4 6 x 5 0 13
0 9 8 15 - 15 = 0 7 3
Искомый элемент равен c33=2. Для этого элемента запасы равны 2, потребности 8. Поскольку минимальным является 2, то вычитаем его.
x33 = min(2,8) = 2.
x 4 3 2 5 0 1
x 3 6 x 4 0 11
1 x 2 x x x 2 - 2 = 0
x 4 6 x 5 0 13
0 9 8 - 2 = 6 0 7 3
Искомый элемент равен c13=3. Для этого элемента запасы равны 1, потребности 6. Поскольку минимальным является 1, то вычитаем его.
x13 = min(1,6) = 1.
x x 3 2 x x 1 - 1 = 0
x 3 6 x 4 0 11
1 x 2 x x x 0
x 4 6 x 5 0 13
0 9 6 - 1 = 5 0 7 3
Искомый элемент равен c22=3. Для этого элемента запасы равны 11, потребности 9. Поскольку минимальным является 9, то вычитаем его.
x22 = min(11,9) = 9.
x x 3 2 x x 0
x 3 6 x 4 0 11 - 9 = 2
1 x 2 x x x 0
x x 6 x 5 0 13
0 9 - 9 = 0 5 0 7 3
Искомый элемент равен c25=4. Для этого элемента запасы равны 2, потребности 7. Поскольку минимальным является 2, то вычитаем его.
x25 = min(2,7) = 2.
x x 3 2 x x 0
x 3 x x 4 x 2 - 2 = 0
1 x 2 x x x 0
x x 6 x 5 0 13
0 0 5 0 7 - 2 = 5 3
Искомый элемент равен c45=5. Для этого элемента запасы равны 13, потребности 5
Задать вопрос
на новый заказ в Автор24.
