На трёх складах оптовой базы сосредоточен однородный груз в количествах 90, 60 и 150 ед. Этот груз необходимо перевезти в четыре магазина. Каждый из магазинов должен получить соответственно 110, 40, 60 и 80 ед. груза. Тарифы перевозок единицы груза из каждого из складов во все магазины задаются матрицей Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.
Ответ
минимальные транспортные затраты составляют 480 ден.ед.
Решение
Запишем исходные данные в виде матрицы планирования.
Магазины
Склады B1 B2 B3 B4 Запасы
A1 2 3 4 3 90
A2 5 3 1 2 60
A3 2 1 4 2 150
Потребности 110 40 60 80
Обозначим через xij – количество груза, перевозимого от i-ого поставщика (склада) j-ому потребителю (магазину).
Целевая функция – это совокупные транспортные издержки.
fx=i=13j=14Cij*Xij=2x11+3x12+4x13+3x14+5x21+3x22+x23+2x24+2x31+x32+4x33+2x34 min
j=14Xij=ai для i=1,2,3 j=13Xij=bj для j=1,2,3,4 Xij≥0 .
Данная задача является открытой.
ai=90+60+150=300;
bj= 110+40+60+80=290 .
ai≠ bj
Для того, чтобы сделать задачу закрытой, необходимо добавить дополнительный (фиктивный) магазин, равный со значением «10».
Решаем задачу методом потенциалов. Первоначальный план находим по методу северо-западного угла.
Склады Магазины Потенциал Ui
110 40 60 80 10
90 2
90 3
4
3 0
0
60 5
20 3
40 1
+ 2 0
- 0 -3
150 2
1 4
- 60 2
80 0
+ 10 -3
Потенциал Vj
2 0 1 -1 -3
Последовательность заполнения клеток следующая:
x11 = min(90,110) = 90;
x21 = min(60,20) = 20;
x22 = min(40,40) = 40;
x33 = min(150,60) = 60;
x34 = min(90,80) = 80;
x35 = min(10,10) = 10;
Число занятых клеток равно: m n 1 3 4 1 6. Опорный план является вырожденным.
В данном случае необходимо добавить клетку с нулевым значением
. Пусть x25 = 0.
Таким образом, число занятых клеток становится равно 7.
Затраты на перевозку составят:
F = 2*90 + 3*0 + 5*20 + 3*40 + 4*60 + 2*80 + 0*10 = 800 ден. ед.
Находим для каждой строки и каждого столбца потенциалы по формуле: Vj Ui Cij для заполненных клеток.
Полагая U1 0 по клетке (1, 1) находим V1 0 2 2 , по клетке (2, 1) находим
U2 2-5 -3; и т.д.
V2 0;
V5 -3;
U3 = -3;
V3 -1;
V4 -3.
Для проверки плана на оптимальность составляем матрицу оценок:
dij Ui Cij Vj
Получим матрицу:
d=03 3 4 -300-3-2 0-3-2 0 0 0
Наличие отрицательной оценки свидетельствует о том, что план неоптимальный. Т.к. имеем несколько клеток с одинаковым значением «-3», то выбираем любую из них.
Построим контур перераспределения для клетки (2, 3). Он показан пунктиром. Вершинам контура присвоены соответствующие знаки «+» и «-».
Наименьшая поставка в клетке со знаком «-» равна 0. Значит проведем перераспределение поставок, увеличив поставки в клетках со знаком «+» на 0 и уменьшив поставки в клетках со знаком «-» также на 0.
Новый план представлен в таблице.
Склады Магазины Потенциал Ui
110 40 60 80 10
90 2
90 3
4
3 0
0
60 5
- 20 3
40 1
+ 0 2 0
-3
150 2
+ 1 4
- 60 2
80 0
10 -6
Потенциал Vj
2 0 -2 -4 -6
Снова находим для каждой строки и каждого столбца потенциалы по формуле: Vj Ui Cij для заполненных клеток и отображаем их в новой таблице.
Для проверки плана на оптимальность составляем матрицу оценок:
dij Ui Cij Vj
Получим матрицу:
d=03 6 7 -600 0 3 3-6-5 0 0 0
Наличие отрицательной оценки свидетельствует о том, что план неоптимальный
Задать вопрос
на новый заказ в Автор24.
