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

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

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

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