Таблица 10.3
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | |||||
A2 | |||||
A3 | |||||
Потребности заводов-потребителей |
Определите оптимальный план доставки заготовок на заводы с учетом минимизации совокупных транспортных затрат.
Решение
Обозначим искомые объемы поставок от i -ой базы-поставщика к j -му заводу-потребителю через .
Математическая модель данной задачи будет иметь вид:
I итерация:
этап: проверка сбалансированности запасов и потребностей.
Представленная транспортная задача является открытой, т.к. суммарная мощность баз-поставщиков меньше суммарной потребности заводов-потребителей на 200 ящиков:
,
,
.
Сведем данную транспортную задачу к закрытой: введем фиктивную базу А4 с недостающей мощностью а4 = 200 ящиков:
.
Зададим значения условных транспортных затрат на единицу груза от данной базы к заводам-потребителям равными нулю, результаты занесем в следующую таблицу.
|
|
Таблица 10.4
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей |
С учетом фиктивного поставщика математическая модель будет иметь вид:
2 этап: разработка исходного опорного плана.
Для отыскания исходного опорного плана воспользуемся методом минимальной стоимости. Согласно таблице поставок (таблица 10.4) минимальная стоимость соответствует клеткам строки фиктивного поставщика. Рассмотрим, к примеру, клетку «4-3». Объем поставок для данной пары поставщик-потребитель составит:
Запишем в клетку «4-3» объем поставок x43 =200 (таблица 10.5). Запасы фиктивного поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).
Таблица 10.5
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | 0 | 200-200 = 0 | |||
Потребности заводов-потребителей | 300-200 =100 |
Из свободных клеток минимальная стоимость соответствует клеткам «1-1» и «1-4» (cij =1), выберем, к примеру, клетку «1-4». Вписываем в данную клетку объем поставок x14 =100 (таблица 10.6). Запасы первого поставщика исчерпаны (зачеркиваем остальные клетки данной строки, они в дальнейших рассмотрениях не участвуют).
Таблица 10.6
|
|
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | 1 | 100-100=0 | |||
A2 | |||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей | 300-100 = 200 |
Следующая свободная клетка с наименьшей стоимостью поставок единицы груза – клетка «2-1» (c21 =2). Объем поставок для данной пары поставщик-потребитель составит:
Запишем в клетку «2-1» объем поставок x21 =100 (таблица 10.7). Потребность первого завода-потребителя полностью удовлетворена (зачеркиваем незадействованную клетку данной колонки – «3-1», она в дальнейших рассмотрениях не участвуют).
Таблица 10.7
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | 1 | ||||
A2 | 200-100 = 100 | ||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей | 100-100 = 0 |
Оставшиеся запасы второго поставщика целесообразно направить для удовлетворения потребностей второго завода-потребителя, так как стоимость доставки единицы груза здесь наименьшая (c22 =3). Вписываем в соответствующую клетку объем поставок x22 =100 (таблица 10.8).
Таблица 10.8
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | 1 | ||||
A2 | 100-100 = 0 | ||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей | 100-100 = 0 |
Таким образом, потребность второго завода-потребителя полностью удовлетворена и мощность второго поставщика полностью задействована, поэтому вычеркиваем незадействованные клетки «2-3», «2-4» и «3-2», в дальнейших рассмотрениях они не участвуют.
Продолжая данные рассуждения, в результате получим следующее распределение поставок:
Таблица 10.9
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | 1 | ||||
A2 | |||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей |
Совокупные транспортные издержки для данного плана поставок составят (усл. ден. ед.):
.
3 этап: проверка вырожденности опорного плана.
Количество задействованных клеток в таблице поставок (таблица 10.9): N =6. Ранг r системы ограничений транспортной задачи равен:
.
Так как, , следовательно, опорный план транспортной задачи вырожденный. Определим количество фиктивных поставок:
.
В любой свободной клетке таблицы поставок проектному параметру xij присвоим нулевое значение. Выберем, к примеру, клетку «3-2» (клетки для фиктивных поставок необходимо выбирать таким образом, чтобы в дальнейшем можно было корректно построить контур перераспределения поставок).
Таблица 10.10
Таблица поставок
Заводы-потребители Базы-поставщики | B1 | B2 | B3 | B4 | Запасы баз-поставщиков |
A1 | |||||
A2 | |||||
A3 | |||||
A4 | |||||
Потребности заводов-потребителей |