Открытая транспортная задача.

а) — излишек продукта

Способ сведения к замкнутой задаче. Пусть b_m+1 — величина избытка продукции, т.е. - штраф за еди­ницу продукта, не реализованного в пункте i; у_i — количество про­дукта, не реализованного в пункте i.

Замкнутая транспортная задача имеет вид

б) — дефицит продукта.

Способ сведения к замкнутой задаче. Пусть а_n+1 — величина дефицита продукции, т.е. - штраф за еди­ницу продукта, недопоставленного в пункт j; у_j — количество про­дукта, недопоставленного в пункту.

Замкнутая транспортная задача имеет вид

3. Транспортная задача с запретами. Пусть Е — множество пар индексов (ij), таких, что из пункта i в пункт j допускается транс­портировка продукта. Между любыми другими двумя пунктами транспортировка не допускается.

Пусть М— большое число, например

Тогда

В оптимальном плане { } транспортной задачи при ограничениях (2)—(4) x_ij = 0, если (i,j) Ï Е.

4. Транспортная задача с фиксированными перевозками. Если объем перевозок между пунктами i и j задан, то в задаче (1)—(4) вводится дополнительное ограничение: x_ij = v_ij, где v_ij — заданный объем перевозок.

5. Транспортная задача с ограничениями на пропускную способ­ность. Если объем перевозок из пункта i в пункт j ограничен ве­личиной w_ij, то в задаче (1)—(4) вводится дополнительное огра­ничение: x_ij £ w_ij.

6. Транспортная задача с фиксированными доплатами. Предпо­ложим, что в открытой транспортной задаче имеет место дефицит продукта и для его устранения в пунктах i = п + 1, ..., k воз­можно создание новых мощностей d_i.

Пусть переменные z_i = 1, если в пункте i (i = п + 1, ..., k) вво­дятся мощности d_i и z_i = 0, если в пункте i мощности не вводят­ся. Издержки на ввод мощностей d, в пункте i (i = n + 1, ..., k)составляют и_i.

С учетом возможности создания новых мощностей транспорт­ная задача может быть записана в следующем виде:

Здесь (5) — целевая функция (минимум затрат на транспортиров­ку и ввод мощностей);

(6) — ограничения по величине предложения в каждом су­ществующем пункте производства;

(7) — ограничения по величине предложения в каждом но­вом пункте производства;

(8) — ограничения по величине спроса в каждом пункте по­требления;

(9) — условия неотрицательности объемов перевозок.

Помимо непрерывных переменных x_ij в модель включены бу­левы переменные z_i,. Задача (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 тыс. руб.