Открытая транспортная задача.
а) — излишек продукта
Способ сведения к замкнутой задаче. Пусть bm+1 — величина избытка продукции, т.е. - штраф за единицу продукта, не реализованного в пункте i; уi — количество продукта, не реализованного в пункте i.
Замкнутая транспортная задача имеет вид
б) — дефицит продукта.
Способ сведения к замкнутой задаче. Пусть аn+1 — величина дефицита продукции, т.е. - штраф за единицу продукта, недопоставленного в пункт j; уj — количество продукта, недопоставленного в пункту.
Замкнутая транспортная задача имеет вид
3. Транспортная задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транспортировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.
Пусть М— большое число, например
Тогда
В оптимальном плане { } транспортной задачи при ограничениях (2)—(4) xij = 0, если (i,j) Ï Е.
4. Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (1)—(4) вводится дополнительное ограничение: xij = vij, где vij — заданный объем перевозок.
5. Транспортная задача с ограничениями на пропускную способность. Если объем перевозок из пункта i в пункт j ограничен величиной wij, то в задаче (1)—(4) вводится дополнительное ограничение: xij £ wij.
6. Транспортная задача с фиксированными доплатами. Предположим, что в открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах i = п + 1, ..., k возможно создание новых мощностей di.
Пусть переменные zi = 1, если в пункте i (i = п + 1, ..., k) вводятся мощности di и zi = 0, если в пункте i мощности не вводятся. Издержки на ввод мощностей d, в пункте i (i = n + 1, ..., k)составляют иi.
С учетом возможности создания новых мощностей транспортная задача может быть записана в следующем виде:
Здесь (5) — целевая функция (минимум затрат на транспортировку и ввод мощностей);
(6) — ограничения по величине предложения в каждом существующем пункте производства;
(7) — ограничения по величине предложения в каждом новом пункте производства;
(8) — ограничения по величине спроса в каждом пункте потребления;
(9) — условия неотрицательности объемов перевозок.
Помимо непрерывных переменных xij в модель включены булевы переменные zi,. Задача (5)—(9) является задачей линейного программирования со «смешанными» переменными.
Все приведенные модели описывают транспортную задачу в виде задачи линейного программирования. В такой форме она может быть решена стандартными средствами линейного программирования, например симплекс-методом.
Для решения транспортной задачи могут быть использованы также и менее трудоемкие (по объему вычислений) алгоритмы, например метод потенциалов.
Большинство специальных алгоритмов решения транспортной задачи использует исходную информацию в форме транспортной таблицы:
Оптимальный план перевозок имеет вид
Примеры. Пример 1. Определение плана перевозок.
Компания, занимающаяся добычей железной руды, имеет четыре карьера. Производительность карьеров соответственно 170, 130, 190 и 200 тыс. т ежемесячно. Железная руда направляется на три принадлежащие этой компании обогатительные фабрики, мощности которых соответственно 250, 150 и 270 тыс. т в месяц.
Транспортные затраты (в тыс. руб.) на перевозку 1 тыс. т руды с карьеров на фабрики указаны в следующей таблице:
Определите план перевозок железной руды на обогатительные фабрики, который обеспечивает минимальные совокупные транспортные издержки.
Вопросы:
1. Сколько руды следует перевозить с карьера 1 на обогатительную фабрику 2?
2. Сколько руды следует перевозить с карьера 4 на обогатительную фабрику 1?
3. Какой объем мощностей по добыче руды окажется неиспользованным?
4. Каковы минимальные совокупные транспортные издержки?
Решение. Транспортная таблица имеет следующий вид:
Ниже приведены результаты расчетов — объемы перевозок и остаток невывезенной руды (в тыс. т):
В следующей таблице до косой черты указаны объемы перевозок, после черты — соответствующие издержки:
Минимальные совокупные издержки составляют 2710 тыс. руб.
Ответы: 1.10 тыс. т. 2. 60 тыс. т.
3. 20 тыс. т. 4. 2710 тыс. руб.
Пример 2. Задача агрегированного планирования.
Компания «Родник» производит и реализует в России концентрат для приготовления фруктового напитка «Солнышко». Производство осуществляется на заводе в Самаре. Отдел сбыта компании «Родник» заключил договоры на поставку концентрата в следующем объеме: апрель — 55 т, май — 70 т, июнь — 75 т. При работе в две смены на собственном оборудовании компания может производить в месяц до 50 т концентрата. Если использовать сверхурочное время, можно увеличить объем производства на 5 т в месяц. В апреле начальный запас концентрата на складе составит 10 т.
Нетрудно видеть, что даже при использовании сверхурочного времени и складских запасов концентрата выполнить договоры не удастся. Поэтому в целях выполнения договорных обязательств принято решение арендовать оборудование акционерного общества «Волжанка». За счет аренды появляется возможность увеличить производство концентрата на 12 т в апреле, на 12 т в мае и на 10 т в июне.
Известно, что производство 1 т концентрата в регулярном режиме двухсменной работы оборудования обходится в 60 тыс. руб. При использовании сверхурочного времени издержки увеличиваются на 20 тыс. руб. за тонну.
Производство 1 т концентрата на арендованном оборудовании обходится в 90 тыс. руб. Издержки хранения 1 т концентрата в течение месяца — 1 тыс. руб.
Договоры предусматривают штрафные санкции в случае несвоевременной поставки концентрата. При задержке поставок на один месяц компания должна будет заплатить штраф в размере 3 тыс. руб. за тонну.
Составьте план использования собственных и арендуемых мощностей для компании «Родник» на каждый месяц второго квартала.
Вопросы:
1. Чему равно значение коэффициента транспортной таблицы, соответствующего регулярному использованию собственных мощностей компании в апреле для удовлетворения спроса на май?
2. Чему равно значение коэффициента транспортной таблицы, соответствующего регулярному использованию собственных мощностей компании в мае для удовлетворения спроса на апрель?
3. При каких минимальных издержках можно выполнить заключенные на второй квартал договоры?
4. Какое количество концентрата следует производить в апреле на арендуемом оборудовании?
5. Какой размер штрафных санкций за несвоевременную поставку концентрата предусмотрен планом?
6. Какая величина запаса концентрата на начало июня предусмотрена планом?
7. Чему равны издержки выполнения договоров на июнь?
Решение. Для составления плана используем модель транспортной задачи. Транспортная таблица в этом случае имеет следующий вид:
Например, значение 1 коэффициента в первой строке транспортной таблицы (при использовании начального запаса для удовлетворения спроса в мае) показывает, что издержки хранения 1 т концентрата в течение месяца (апрель) составят 1 тыс. руб.
Значение 2 коэффициента в первой строке (при использовании начального запаса для удовлетворения спроса в июне) показывает, что издержки хранения 1 т концентрата в течение двух месяцев (апрель, май) составят 2 тыс. руб.
Значение 60 коэффициента во второй строке матрицы (при регулярном использовании собственных мощностей в апреле для удовлетворения спроса в апреле) соответствует производственным издержкам — 60 тыс. руб./т.
Значение 66 коэффициента в восьмой строке матрицы (при регулярном использовании собственных мощностей в июне для выполнения договоров, заключенных на апрель) превышает производственные издержки (60 тыс. руб./т) на величину штрафных санкций (6 тыс. руб./т) за несвоевременную (с опозданием на два месяца) поставку каждой тонны концентрата.
Используя приведенную выше транспортную таблицу, получаем следующее решение задачи:
В соответствии с этим решением из 50 т концентрата, произведенного на регулярных мощностях в апреле, 45 т следует использовать при выполнении договоров, заключенных на апрель, 5т— при выполнении договоров, заключенных на май.
В апреле на арендуемых мощностях следует произвести 3 т концентрата. При этом резерв мощности составит 9 т.
В мае арендуемые мощности следует использовать полностью (12 т). При этом 2 т из этих 12 следует использовать для выполнения договоров, заключенных на май, а 10 т — для выполнения договоров, заключенных на июнь.
В следующей таблице минимальные совокупные издержки (12 473 тыс. руб.), соответствующие оптимальному плану использования мощностей, специфицированы по различным статьям расходов:
Окончание таблицы
При использовании регулярных мощностей удельные производственные издержки составляют 60 тыс. руб./т.
В случае регулярного использования собственных мощностей в апреле для выполнения договоров, заключенных на май, значение коэффициента транспортной таблицы превышает производственные издержки (60 тыс. руб./т) на величину удельных затрат на хранение концентрата (1 тыс. руб./т). Значение коэффициента равно 61 тыс. руб./т.
В случае регулярного использования собственных мощностей в мае для выполнения договоров, заключенных на апрель, значение коэффициента транспортной таблицы превышает производственные издержки (60 тыс. руб./т) на величину штрафных санкций (3 тыс. руб./т) за несвоевременную (с опозданием на один месяц) поставку каждой тонны концентрата. Значение коэффициента равно 63 тыс. руб./т.
Ответы: 1. 61 тыс. руб./т. 2. 63 тыс. руб./т. 3. 12 473 тыс. руб. 4. 3 т. 5. 0 руб. 6. 10 т. 7. 5210 тыс. руб.
Дата добавления: 2022-07-20; просмотров: 115;