Файл: Теория систем2.pdf

26

Раздел 2. Распределительные задачи

2.1. Классификация распределительных задач

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

Элементы Cij , стоящие в клетках матрицы, соответствуют затратам

или доходу, отвечающим выделению одной единицы ресурса Ri на работу

распределительную задачу.

Для их решения были развиты методы линейного программирования.

n

Если общий объем наличных ресурсов ∑aj равен общей потребности

j=1

n

вних ∑bi , то имеет место сбалансированная (закрытая) распределительная

i=1

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

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

2.2. Транспортная задача

28

Рассмотрим задачу, возникающую перед транспортным отделом фирмы, имеющей 3 предприятия и 4 оптовых склада. Перечни заявок каждого склада и производственные мощности каждого предприятия на каждый месяц известны. Известны транспортные расходы по доставке продукции с каждого предприятия на каждый склад. Требуется распределить поставляемую предприятиями продукцию по складам таким образом, чтобы минимизировать общие транспортные расходы. Такой критерий оптимальности можно принять только тогда, когда общая производственная мощность предприятий в точности равна общему спросу на их продукцию, т.е. когда задача сбалансирована (закрытая модель).

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

2.2.1. Методы нахождения начального решения

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

Рассмотрим методы отыскания начальных решений. Обозначения:

29

xij – объем груза, отправляемого с предприятия i на склад j;

Cij – удельные затраты при такой перевозке.

Метод северо-западного угла

Распределение всегда начинают с клетки (1,1).

Выбираем клетку (1,1) и находим, что наибольшая возможная поставка (x11) равна 5, так как это все, что требуется складу 1. Выбрав эту поставку, переходим к клетке (1,2), так как столбцу 1 больше не требуется никаких поставок. Наибольшая поставка по этой клетке равна 2, так как это весь остаток мощности предприятия 1 после того, как произведена поставка x11=5. Таким образом, принимаем x12=2. Переходим к клетке (2,2), поскольку складу 2 еще требуется 6 единиц продукции, т.е. x22=6. Теперь спрос склада 2 удовлетворен и переходим к клетке (2,3) и т.д. Перемещаясь по матрице только вправо и вниз, получим остальные назначения.

x23=3, x33=4, x34=14.

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

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

5*19+2*20+6*30+3*40+4*70+14*20=1015 (ед.стоим.).