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

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

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

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

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

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