Транспортная задача с промежуточными пунктами
Допустим, имеется m (i=1,m) пунктов производства, n (j=1,n) – пунктов потребления и p (r=1,p) – промежуточных баз. Как и в обычной транспортной задаче, обозначим через ai,bj соответственно объемы поставок и потребления. Пусть dr – мощность r-й базы, cir и crj – соответственно стоимость перевозки единицы продукции от поставщиков на базы и от баз к потребителям. Тогда модель задачи примет вид:
при ограничениях:
В случае полностью сбалансированной задачи, т.е.
схема перевозок от поставщиков до баз не оказывает влияние на схему перевозок от баз до потребителей. В таких условиях задачу можно решать по частям для каждого этапа перевозок: от поставщиков до баз и от баз до потребителей продукции.
В случае частично сбалансированной задачи, а именно
оптимальный план двухэтапной транспортной задачи отличен от плана, полученного объединением оптимальных планов решения транспортной задачи для каждого этапа в отдельности. В таких условиях двухэтапную задачу сводят к классической размерности (m+p)(p+n). Матрица тарифов будет состоять из четырех блоков (табл.).
Таблица - Объединенная матрица тарифов
| d1 | … | dp | b1 | … | bn | |
| a1 | М | М | М | |||
| . | ||cij|| | М | М | М | ||
| am | М | М | М | |||
| d1 | 0 | М | М | |||
| . . . | М | 0 | М | ||cij|| | ||
| dp | М | М | 0 |
В первом левом верхнем блоке будем отражать связи поставщиков с базами (ir), в четвертом – связи баз с потребителями (rj). Второй правый верхний блок показывает связи поставщиков с потребителями, а так как таких непосредственных перевозок нет, то в этом блоке все тарифы считаются равными М (где М – большое число). Третий левый нижний блок размерностью (pxp) отражает связи между базами, поэтому все тарифы также считаются равными М, кроме диагональных.
Диагональные тарифы, отражающие затраты на переезд внутри базы, равны нулю. Сама диагональ называется фиктивной, т.к. поставки, найденные в результате решения задачи, в этих клетках будут означать величину неиспользованной мощности базы.
Решение двухэтапной транспортной задачи на объединенной матрице тарифов начинается с определения допустимого начального плана. Вначале заполняется блок первый или четвертый любым из способов определения начального плана. Затем заполняется фиктивная диагональ и только потом распределяются поставки в другом незаполненном блоке (четвертом или первом).
После определения общего допустимого плана применяют известные методы поиска наилучшего решения. При этом имеется особенность определения контура сдвига: если контур пересчета проходит через фиктивную диагональ, то он обязательно проходит через нее дважды: один раз с пометкой «плюс», другой раз с пометкой «минус».
n (i=1,n)