Имя материала: Исследование операций в экономике

Автор: И.Н. Мастяева

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

 

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

 

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

 

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

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

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

 

m n

 

n

I Xj = a , 1 = 1,_,m;

m

I xj = bj. j = 1,^,n;

i=1

mn

I a<    =   I bj ;

X1j > 0, 1 = 1,...,m; j = 1,...,n.

 

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

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

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

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

 

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

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

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

 

m n

с = SSs- xij min

i=1 j=1

n

S xn = ai , i = 1,...,m;

m

S Xv = bj.   j = 1,-,n;

=1

mn

Sa = S bs;

i=1 j=1 Xij > 0, i = 1,...,m; j = 1,_,n.

Задача календарного планирования производства.

 

Рассмотрим задачу календарного планирования производства на N последовательных этапах. Спрос изменяется во времени, но детерминирован. Спрос можно удовлетворить либо путем изменения уровня запаса при постоянном объеме производства, либо за счет изменения объема производства при постоянном уровне запаса, либо путем изменения и уровня запаса, и выпуска. Изменения объема производства можно добиться, проводя сверхурочные работы, а изменения уровня запаса можно обеспечить за счет создания постоянного положительного запаса, либо за счет неудовлетворенного спроса.

Нужно отыскать календарный план производства на N этапов, минимизирующий суммарные затраты. В модели предполагаются нулевые затраты на оформление заказа для любого этапа. В общем случае допускается дефицит при условии, что весь задолженный спрос должен быть удовлетворен к концу этапа N. Эти условия можно записать в виде транспортной задачи.

Введем следующие обозначения для этапа i; i= 1,2,...,N:

а - производственные затраты на единицу продукции при обычном

режиме работы,

di - производственные затраты на единицу продукции при работе в сверхурочное время ( di > Сі ),

hi - затраты на хранение единицы продукции, переходящей из этапа i в этап

Pi - потери от дефицита на единицу продукции, требуемой на этапе

i, но поставляемой на этапе i+1,

ari - производственная мощность (в единицах продукции) при

обычном режиме работы,

ati - производственная мощность (в единицах продукции) при

работе в сверхурочное время,

bi - спрос (в единицах продукции).

 

Модель без дефицита.

 

В соответствии с терминологией транспортной модели поставщики представлены обычным и сверхурочным производством для различных этапов. Потребители задаются спросом соответствующих этапов. Затраты на «транспортировку» единицы продукции от любого поставщика к любому потребителю представляются суммой соответствующих производственных затрат и затрат на хранение единицы продукции.

Дополнительный столбец используется для балансировки транспортной задачи, т.е. S = la "ХЬ . Затраты на единицу продукции

j J

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

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

k k

Z(aRj+ aTi ) * ZbJ , k = 1,2,...,N.

г = 1    j =1

Так как спрос на этапе i должен быть удовлетворен прежде, чем спрос на этапах i+1, i+2,... , N, и поскольку на функцию производственных затрат наложены специальные требования, нет необходимости применять общий алгоритм решения транспортной задачи. Сначала путем последовательного назначения максимально возможных поставок по наиболее дешевым элементам первого столбца удовлетворяется спрос на этапе 1. Затем корректируются значения аг, которые после этого определяют оставшиеся мощности для различных этапов. Далее рассматривается этап 2, и его спрос удовлетворяется наиболее дешевыми поставками в пределах новых ограничений на производственные мощности. Процесс продолжается до тех пор, пока не будет удовлетворен спрос этапа N.

1

2

 

3

4

Избыток

 

R 1

2

100

2,1

2,2

2,3

0

100

T 1

3

20

3,1

3,2 20

3,3

0 10

50; 30; 10

R 2

 

2

150

2,1

2,2

0

150

T 2

 

3

50

3,1 30

3,2

0

80; 30

R 3

 

 

2

100

2,1

0

100

 

 

 

 

 

 

 

T 3

 

 

3

100

3,1

0

100

R 4

 

 

 

2 200

0

200

T 4

 

 

 

3

0

50

50

 

120 20

200 50

 

250

150 50 20

200

60

10

 

 

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

Упражнение:

а) Определите следующие величины:

объем производства на этапе 1 для этого же этапа - (120 единиц). объем производства на этапе 1 для этапа 2 - (нулевой). объем производства на этапе 1 для этапа 3 - (20 единиц). объем производства при обычном режиме работы и в сверхурочное время на этапе 1 - (100 и 40 единиц соответственно).

запас, переходящий из этапа 1 в этап 3 - (20 единиц). запас, переходящий из этапа 2 в этап 3 - (50 единиц). запас, переходящий из этапа 3 в этап 4 - (нулевой).

б) Предположив, что на этапе 4 требуется 55 дополнительных единиц продукции, определите, каким образом эту продукцию нужно выпустить. (50 единиц в сверхурочное время на этапе 4 и 5 единиц в сверхурочное время на этапе 1).

 

Модель с дефицитом.

 

Рассмотрим обобщение описанной выше модели при условии, что допускается дефицит. Предполагается, что задолженный спрос должен быть удовлетворен к концу N-этапного горизонта планирования. Таблицу 1 можно легко модифицировать, чтобы учесть влияние задолженности, введя соответствующие удельные издержки в заблокированные маршруты.

Так , например, если pi - удельные потери от дефицита (т.е. на

единицу продукции) в случае, когда продукция требуется на этапе i, а поставляется на этапе i+1, то удельные расходы, соответствующие ячейкам (RNд) и (TN1), составляют:        {cN + p1+ p2 +... + pN-1} и

{dN + p + p2 +... + pN-1} соответственно.

 

Заметим, что в общем случае описанный выше алгоритм может не привести к оптимальному решению.

 

Пример 4.5. Рассмотрим трехэтапную модель, в которой используется обычное и сверхурочное производство. Производственные мощности для трех этапов следующие:

 

 

Период

Мощность

обычная сверхурочная

1

2 3

15 15 20

10

0

15

 

Удельные производственные затраты составляют 5 при обычном режиме работы и 10 при сверхурочной работе. Затраты на хранение и потери от дефицита равны 1 и 2 соответственно. Для трех этапов требуется 20, 35 и 15 единиц продукции соответственно. Исходные данные соответствующей транспортной модели приведены в таблице. На этапе 2 сверхурочные работы не проводятся, так как соответствующая мощность равна нулю.

В таблице приведено решение задачи, полученное с использованием описанного выше алгоритма. Суммарные затраты составляют (15 х 5 + 5 х 7 + 5 х 11 +10 х 5 + 20 х 7 +15 х10= 505) денежных единиц.

Данное решение не является оптимальным и, следовательно, необходимо применять общий алгоритм решения транспортной задачи. В результате использования метода минимальной стоимости сразу получим оптимальный план:

1       2      3 Избыток

Суммарные затраты в этом случае составят 15 х 5 + 5 х10 + 5 х 11+15 х 5 + 5 х 7 +10 х12 +15 х 5 = 485 денежных единиц.

 

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

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

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

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

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

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

 

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

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

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

cij= i > j.

i <j,

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

 

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

с11 = 4 долл.,

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

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

Таблица 4.10

 

1.Составить оптимальное распределение специалистов четырех профилей, имеющихся в количествах 60, 30, 45, 25 между пятью видами работ, потребности в специалистах для каждого вида работ соответственно равны 20, 40, 25, 45, 30, а матрица

(7         5          2          0          4^

0          8          6          3

6          0          9          8

4          5          7          6,

характеризует эффективность использования специалиста на данной работе.

 

2. Выпуск продукции на трех заводах составляет 500 , 700 и 600 , причем затраты на производство единицы равны 9,8 и 2 соответственно. Потребности четырех потребителей на эту продукцию составляют 350 , 200, 450 и 100. Матрица С транспортных расходов на доставку единицы продукции с i - го завода j - му потребителю:

( 3   4   6   1 ^

C

2 8

 

Определить оптимальный план прикрепления потребителей к заводам при условии минимизации суммарных затрат на производство и транспортировку .

 

3. Строительный песок добывается в трех карьерах с производительностью за день 46, 34 и 40 т. И затратами на добычу одной тонны 1 , 2 и 3 руб. Соответственно; песок доставляется на четыре строительные площадки, потребность которых составляет 40, 35, 30, 45 т. Транспортные расходы на перевозку одной тонны песка заданы матрицей:

(4   3   2   5 ^

C

6

9

 

Недостающее количество песка - 30 т. В день можно обеспечить

Подпись: что го сдвумя путями : увеличением производительности а) 1 -повлечет дополнительные затраты в 3 руб. На добычу дополнительными затратами в 2 руб. / т.

Определить    оптимальный    план закрепления

го карьера

1 т.; б) 2 -

строительных

площадок за карьерами и оптимальный вариант расширения поставок песка.

4. Имеется три сорта бумаги в количествах 10, 8 и 5 т., которую необходимо использовать на издание четырех книг тиражом в 8000, 6000, 15000 и 10000 экз. Расход бумаги на одну книгу составляет 0,6; 0,8; 0,4 и 0,5 кг, а себестоимость ( в коп.) печатания книги при использовании i - го сорта бумаги задается матрицей :

 

C

(24   16   32   25^ 18   24   24 20 30   24   16 20

 

Определить оптимальное распределение бумажных ресурсов.

5. Четыре ремонтные мастерские могут за год отремонтировать соответственно 700, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 350, 350, 300, 300 и 200 машин.

Избыточные мощности 1-й и 2-й мастерских могут быть использованы для обслуживания других видов работ.

Дана матрица

' 40

20

60

10

20 N

10

80

30

40

30

70

30

30

50

10

v 50

10

40

50

40 ,

 

характеризующая транспортные расходы на доставку машины с і-й ав-тобазы в j-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема ремонтных работ по всем автобазам. Составить программу ремонтных работ, имеющую минимальную стоимость.

6.         Решить задачу из примера 4.6 при условии, что затраты на

производство единицы изделий составляют 4; 4,2; 4,1; 4 долларов в

первый, второй, третий и четвертый месяцы соответственно.

Решить задачу из примера 4.6 при условии, что затраты на производство единицы изделий увеличиваются от месяца к месяцу на одну и ту же величину, равную 0,2 доллара.

Решить задачу из примера 4.6 при условии, что штрафы за каждое изделие, выпускаемое в счет невыполненных заказов, равны 2; 1,5 и 2 долларам во второй, третий и четвертый месяцы соответственно.

Решить задачу из примера 4.6 при условии, что стоимость хранения единицы изделий уменьшается от месяца к месяцу на одну и ту же величину, равную 0,1 доллара.

10.       Решить задачу из примера 4.6 при условии, что стоимость

хранения единицы изделий меняется от месяца к месяцу и составляет

0,4; 0,3 и 0,7 долларов для первого, второго и третьего месяцев

соответственно.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |