Экономические задачи, сводящие к транспортной задаче.

В этом разделе будет рассмотрено несколько примеров экономических задач, решение которых может быть найдено с помощью транспортной модели.

Оптимальное распределение оборудования

Оборудование m различных видов нужно распределить между n рабочими участками. Производительность единицы оборудования i -го вида на j -ом рабочем участке равна p_ij; i = 1, …, m; j = 1, …, n. Потребность j -го участка в оборудовании составляет b_j, j = 1, …, n. Запас оборудования i -го вида равен a_{i ,} i = 1, …, m. Найти распределение оборудования по рабочим участкам, при котором суммарная производительность максимальна.

Данная задача относится к классу ТЗ при условии, что производительность линейно зависит от количества используемого оборудования. Поставщиками в задаче являются различные виды оборудования, потребителями – рабочие участки.

Обозначим через x_ij число единиц оборудования i -го вида, выделенное на j -й рабочий участок, i = 1, …, m; j = 1, …, n. Математическая модель задачи имеет следующий вид:

P = x_ij ® max;

= a_{i ,} i = 1, …, m;

= b_j, j = 1, …, n;

;

x_ij ³ 0, i = 1, …, m; j = 1, …, n.

Построенная модель является сбалансированной. Если запас оборудования и потребность в нем не равны, то переход к сбалансированной модели осуществляется с помощью преобразований, изложенных в пункте 4.1.2.

В данной задаче требуется максимизировать целевую функцию Р, представляющую суммарную производительность. Для перехода к стандартной транспортной модели надо заменить функцию Р на противоположную функцию, – Р которую нужно будет минимизировать.

При решении в матрице вместо стоимостей перевозок единицы груза будут стоять производительности, взятые с противоположным знаком. Далее задача решается как ТЗ.

Формирование оптимального штата фирмы

Фирма набирает штат сотрудников. Она располагает n группами различных должностей по b_j вакантных единиц в каждой группе, j = 1, …, n. Кандидаты для занятия должностей проходят тестирование, по результатам которого их разделяют на m групп по а_i кандидатов в каждой группе, i = 1, …, m. Для каждого кандидата из i -й группы требуются определенные затраты с_ij на обучение для занятия j-й должности, i = 1, …, m;
j = 1, …, n. (В частности, некоторые c_ij = 0, т.е. кандидат полностью соответствует должности, или c_ij = ¥, т.е. кандидат вообще не может занять данную должность). Требуется распределить кандидатов на должности, затратив минимальные средства на их обучение.

Предположим, что общее число кандидатов соответствует числу вакантных должностей. (Если это не так, то следует просто проделать преобразование раздела 4.1.2). Тогда данная задача соответствует транспортной модели. В роли поставщиков выступают группы кандидатов, а в роли потребителей – группы должностей. В качестве тарифов на перевозки рассматриваются затраты на переобучение.

Математическая модель записывается в виде:

С = x_ij ® min;

= a_{i ,} i = 1, …, m;

= b_j, j = 1, …, n;

;

x_ij ³ 0, i = 1, …, m; j = 1, …, n.

Модель производства с запасами.

Некоторая фирма переводит свой главный завод на производство определенного вида изделий, которые будут выпускаться в течение четырех месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет:

1) избытка произведенных в прошлом месяце изделий, сохраняющихся для реализации в будущем;

2) производства изделий в течение текущего месяца;

3) избытка производства изделий в более поздние месяцы в счет невыполненных заказов.

Затраты на одно изделие в каждый месяц составляют 4 долл. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0, 5 долл. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом 2 долл. в месяц.

Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно.

Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.

Задачу можно сформулировать как ТЗ. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом.

Таблица 4.1. иллюстрирует структуру транспортной модели. Для рассматриваемой задачи стоимость «перевозки» изделия из периода i в период j выражается как:

стоимость производства в i -й период, i = j;

c_ij = стоимость производства в i -й период + стоимость задержки от i до j, i < j;

стоимость производства в i -й период + штраф за нарушение срока,

i > j.

Из определения c_ij следует, что затраты в период i при реализации продукции в тот же период i (i = j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (i < j), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в 1-й период в счет невыполненных заказов { i > j } влечет за собой дополнительные расходы в виде штрафа.

Например,

c ₁₁ = 4 долл.,

с ₂₄ = 4 + (0, 5 + 0, 5) = 5 долл.,

с ₄₁ = 4 + (2 + 2 + 2) = 10 долл.

Таблица 4.2.