Примеры решений Метод Гомори Симплекс-метод Метод Фогеля Транспортная задача Задача о назначениях Распределительный метод Метод потенциалов Задача коммивояжера Открытые и закрытые задачи

Транспортная задача с промежуточными пунктами

Допустим, имеется 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)
Аннуитетные платежи онлайн
Расчет аннуитетных платежей по схеме постнумерандо и пренумерандо с помощью удобного калькулятора.
Аннуитетные платежи онлайн
Подробнее
Профессии будущего
РБК Тренды изучили прогнозы российских и зарубежных футурологов, и составили список самых востребованных профессий в ближайшие 30 лет. Это профессии из 19 отраслей: от медицины и транспорта до культуры и космоса
Подробнее
Налоговый вычет на обучение
√ 120 тыс. руб. - максимальная сумма расходов на обучение
√ вычет от государства
√ вычет от работодателя
Подробнее