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 (ед.стоим.).

30

Метод «здравого смысла»

В методе северно-западного угла мы не заботились о том, чтобы делать назначения в клетки с минимальной стоимостью перевозки. Попробуем сделать это в методе «здравого смысла» (его называют также методом минимальной стоимости). Распределение начинаем с элемента минимальной стоимости.

Элемент минимальной стоимости (8) расположен в клетке (3,2) (см. исходную матрицу). Поэтому с этой клетки начинаем распределять поставки, назначая максимально возможную, т.е. x32=8. Других поставок в этом столбце быть не должно, так как потребности склада 2 исчерпаны. При решении задачи на бумаге рекомендуется вычеркнуть этот столбец из матрицы. Следующий наименьший показатель ищем среди незачеркнутых элементов. Он равен 10 и соответствует клетке (1,4), где вновь выбирается максимально возможная поставка x14=7. Теперь необходимо вычеркнуть первую строку, так как использована вся мощность предприятия 1. Поэтому переходим к клетке (3,4) и т.д. Получим оставшиеся назначения: x34=7, x23=7, x21=2, x31=3.

Снова занесем полученное решение в таблицу.

Общие затраты при этом решении равны

2*70+3*40+8*8+7*40+7*10+7*20=814 (ед.стоим.).

Получили снижение затрат на 201 (ед.стоим.).

Метод штрафов

Во втором методе мы старались использовать минимальные затраты,