В пунктах А и В находятся заводы по производству кирпича, в пунктах С и Д – карьеры, снабжающие их песком. Заводу А необходимо 40 т песка, заводу В – 50 т. Карьер С готов доставить на заводы 70 т песка, а карьер Д – 30 т. Распланируйте перевозки таким образом, чтобы затраты на перевозку были минимальными. Для упрощения задачи в таблицу 9 введен условны1 потребитель Е. Стоимость перевозок песка от карьеров до заводов заданы в табл.1.
Таблица 1
Стоимость перевозок
Заводы
Карьеры А В Е
С 2
х11 6
х12 0
х13 70
Д 5
Х21 3
Х22 0
Х23 30
40 50 10
Решение
1. Составим математическую модель транспортной задачи:
x11+x12+x13+x14=70x21+x22+x23+x24=30x11+x21=40x12+x22=50x13+x23=10xij≥0;i=1,2;j=1,2,3
F=2x11+6x12+0x13+5x21+3x22+0x23→min
2. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 70 + 30 = 100
∑b = 40 + 50 + 10 = 100
Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.
3. Составим первое распределение поставок методом наименьшей стоимости.
Суть данного метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку, и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены
.
Первый искомый элемент равен c11=2. Для этого элемента запасы равны 70, потребности 40. Поскольку минимальным является 40, то вычитаем его.
x11 = min(70,40) = 40.
Второй искомый элемент равен c22=3. Для этого элемента запасы равны 30, потребности 50.
x22 = min(30,50) = 30.
Третий искомый элемент равен c12=6. Для этого элемента запасы равны 30, потребности 20.
x12 = min(30,20) = 20.
Последний искомый элемент равен c13=0. Для этого элемента запасы равны 10, потребности 10.
x13 = min(10,10) = 10.
Таким образом получим следующий опорный план задачи.
Таблица 2
Опорный план
Заводы
Карьеры А В Е
С 2
40 6
20 0
10 70
Д 5
3
30 0
30
40 50 10
В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
Стоимость доставки при таком плане равна:
F=2×40+6×20+0×10+3×30=290 ден
Задать вопрос
на новый заказ в Автор24.
