Настя Просто
Профи
(612)
2 недели назад
Для решения данной задачи можно воспользоваться методом потенциалов или методом северо-западного угла. Давайте воспользуемся методом потенциалов.
1. Переведем задачу в вид таблицы, где строки - это пункты поставки (A1, A2, A3), а столбцы - пункты потребления (B1, B2, B3, B4, B5). Заполним ячейки расстояниями.
2. Начнем с пункта с наименьшим расстоянием. Это ячейка (A3, B3) с расстоянием 17. Пометим это как базовую ячейку.
3. Теперь пройдем по строке A3 и столбцу B3. Найдем путь с минимальными затратами. Это будет ячейка (A3, B3) с расстоянием 17.
4. После этого вычеркнем строку и столбец, содержащие выбранные ячейки.
5. Продолжим этот процесс, выбирая следующую наименьшую ячейку из оставшихся.
6. Повторяем этот процесс, пока все ячейки не будут заполнены.
После завершения процесса получится план, где каждому пункту потребления будет назначен пункт поставки, и общие затраты по перевозкам будут минимальными.
Пункты
Пункты потребления
поставки
B1
B2
B3
B4
B5
A1
D11
D12
D13
D14
D15
A2
D21
D22
D23
D24
D25
A3
D31
D32
D33
D34
D35
Найти такой план закрепления потребителей за поставщиками однородного груза, чтобы общие
затраты по перевозкам были минимальными.
а1=200, а2=350, а3=300,
24 50 55 27 16
D=50 47 23 17 21
b1=270, 62=130, b3=190, b4=150, b5=110.
35 59 55 27 41,