В следующих транспортных задачах найти такие объёмы перевозок однородной продукции от поставщиков к потребителям при которых общие затраты на перевозку продукции будут минимальными. В таблицах заданы объёмы запасов продукции у поставщиков (Ai), объемы потребности в продукции потребителей (Bj) и удельные затраты на перевозку единицы продукции от поставщиков к потребителям (пересечение соответствующих строк и столбцов таблицы).
Решение
Проверим необходимое и достаточное условие разрешимости задачи.∑a = 193 + 159 + 192 + 24 + 190 = 758∑b = 176 + 99 = 275
Как видно, суммарная потребность груза в пунктах назначения меньше запасов груза на базах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительную (фиктивную) потребность, равной 483 (758-275). Тарифы перевозки единицы груза к этому потребителю полагаем равны нулю.
Занесем исходные данные в распределительную таблицу.
B1 B2 B3 Запасы
A1 7 4 0 193
A2 7 0 0 159
A3 4 2 0 192
A4 6 2 0 24
A5 6 1 0 190
Потребности 176 99 483
Этап I. Поиск первого опорного плана.
1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.
Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.
Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Искомый элемент равен c22=0
. Для этого элемента запасы равны 159, потребности 99. Поскольку минимальным является 99, то вычитаем его.x22 = min(159,99) = 99.
7 x 0 193
7 0 0 159 - 99 = 60
4 x 0 192
6 x 0 24
6 x 0 190
176 99 - 99 = 0 483
Искомый элемент равен c31=4. Для этого элемента запасы равны 192, потребности 176. Поскольку минимальным является 176, то вычитаем его.x31 = min(192,176) = 176.
x x 0 193
x 0 0 60
4 x 0 192 - 176 = 16
x x 0 24
x x 0 190
176 - 176 = 0 0 483
Искомый элемент равен c13=0. Для этого элемента запасы равны 193, потребности 483. Поскольку минимальным является 193, то вычитаем его.x13 = min(193,483) = 193.
x x 0 193 - 193 = 0
x 0 0 60
4 x 0 16
x x 0 24
x x 0 190
0 0 483 - 193 = 290
Искомый элемент равен c23=0. Для этого элемента запасы равны 60, потребности 290. Поскольку минимальным является 60, то вычитаем его.x23 = min(60,290) = 60.
x x 0 0
x 0 0 60 - 60 = 0
4 x 0 16
x x 0 24
x x 0 190
0 0 290 - 60 = 230
Искомый элемент равен c33=0
Задать вопрос
на новый заказ в Автор24.
