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

Оборудование 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. Математическая модель задачи имеет следующий вид:

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

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

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

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