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

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

Имеющих некоторые усложнения в их постановке

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

2. В отдельных ТЗ дополнительным условием является обеспечение перевозки по соответствующим маршрутам определенного количества груза. Пусть, например, из A_i в B_j требуется обязательно перевезти α _ij единиц груза. Тогда в соответствующую клетку таблицы, находящуюся на пересечении строки A_i и столбца B_j, записывают указанное число α _ij и в дальнейшем считают эту клетку свободной со сколь угодно большой стоимостью перевозки М. Для полученной таким образом новой ТЗ находят оптимальный план, который определяет оптимальный план исходной задачи.

3. Иногда требуется найти решение ТЗ, при котором из A_i в B_j должно быть перевезено не менее заданного количества груза α _ij. Для определения оптимального плана такой задачи считают, что запасы A_i и потребности B_j меньше фактических на α _ij единиц. После этого находят оптимальный план новой ТЗ, на основании которого и определяют решение исходной задачи.

Примечание: При целых a_i (i = 1,..., m) и b_j (j = 1,..., n), в силу специфики ограничений ТЗ, любое базисное допустимое решение является целочисленным.

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

Оборудование 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.

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

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

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

Дата добавления: 2014-12-29