Глава 2. Решение задачи об оптимизации плана перевозок и получении минимальных издержек

2.1. Постановка задачи

На предприятие имеются шесть складов для хранения готовых изделий, предназначенных для отправки потребителю. Склады имеют различную вместимость и относятся к производственным цехам №1, №2, №3 и №4 соответственно.

На предприятие поступил заказ от точек продаж на поставку кондитерских изделий, упаковки которых уложены в короба, в различные города в количестве: Москва – 190 кор., Смоленск – 170 кор., Орел – 210 кор., Новгород – 160 кор., Воронеж - 230 коробов. При этом предприятию необходимо учесть возможности поставок с каждого из складов при максимальном удовлетворении запросов потребителей и затраты на перевозку единицы изделия.

На первом складе имеется 300 кор. сахаристых изделий, на втором – 270, на третьем – 250, на четвертом – 180. Требуется минимизировать затраты на перевозку.

Стоимость доставки единицы товара с каждого склада представлена в таблице (табл. 2.1).

Таблица 2.1

Стоимость доставки единицы груза.

Потребители Склады	Москва	Брянск	Орел	Новгород	Воронеж
1	9	6	3	6	3
2	5	4	9	7	8
3	7	3	7	2	9
4	4	5	6	8	2

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

Представим данную задачу в виде транспортной (табл.2.2):

Таблица 2.2

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

Потребители Склады	Москва	Брянск	Орел	Новгород	Воронеж	Ресурсы
1	9	6	3	6	3	300
2	5	4	9	7	8	270
3	7	3	7	2	9	250
4	4	5	6	8	2	180
Заказ	190	170	210	160	230

Для нахождения планов транспортных задач используется множество способов (диагональный метод или метод северо-западного угла, метод минимального элемента, метод наименьшей стоимости, метод аппроксимации Фогеля и т.д.), но наиболее оптимальные планы могут быть получены при использовании метода потенциалов и метода дифференциальных рент.

Для решения нашей задачи будем использовать метод дифференциальных рент, так как он имеет более простую логическую схему расчетов, чем метод потенциалов [1].

2.2. Описание метода дифференциальных рент для решения транспортной задачи

При нахождении решения транспортной задачи методом дифференциальных рент сначала наилучшим образом распределяются между пунктами назначения часть груза (так называемое условно оптимальное распределение) и на последующих итерациях постепенно уменьшают общую величину нераспределенных поставок. Первоначальный вариант распределения груза определяют следующим образом. В каждом из столбцов таблицу данных транспортной задачи находят наименьший тариф. Найденные числа заключают в кружки, а клетки, в которых стоят указанные числа, заполняют. В них записывают максимально возможные числа. В результате получают некоторое распределение поставок груза в пункты назначения. Это распределение в общем случае не удовлетворяет ограничениям исходной транспортной задачи. Поэтому в результате последующих шагов следует постепенно сокращать нераспределенные поставки груза так, чтобы при этом общая стоимость перевозок оставалась минимальной. Для этого определяют избыточные и недостаточные строки.

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

После того как определены избыточные и недостаточные строки, для каждого из столбцов находят разности между числом в кружке и ближайшем к нему тарифом, записанным в избыточной строке. Если число в кружке находится в положительной строке, то разность не определяют. Среди полученных чисел находят наименьшее. Это число называется промежуточной рентой. После определения промежуточной ренты переходят к новой таблице. Эта таблица получается из предыдущей таблицы прибавлением к соответствующим тарифам, стоящим в отрицательных строках, промежуточной ренты. Остальные элементы остаются прежними. При этом все клетки новой таблицы считают свободными. После построения новой таблицы начинают заполнение ее клеток. Теперь уже число заполняемых клеток на одну больше, чем на предыдущем этапе. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все остальные клетки находятся по одной в каждом из столбцов и в них записаны наименьшие для данного столбца числа, заключенные в кружки. Заключены в кружки и два одинаковых числа, стоящих в столбце, в котором в предыдущей таблице была записана промежуточная рента.

Поскольку в новой таблице число заполняемых клеток больше, чем число столбцов, то при заполнении клеток следует пользоваться специальным правилом, которое состоит в следующем. Выбирают некоторый столбец (строку), в котором имеется одна клетка с помеченным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данный столбец (строку). После этого берут некоторую строку (столбец), в которой имеется одна клетка с помещенным в ней кружком. Эту клетку заполняют и исключают из рассмотрения данную строку (столбец). Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Если к тому же удается распределить весь груз, имеющийся в пунктах отправления, между пунктами назначения, то получают оптимальный план транспортной задачи. Если же оптимальный план не получен, то переходят к новой таблице. Для этого находят избыточные и недостаточные строки, промежуточную ренту и на основе этого строят новую таблицу. При этом могут возникнуть некоторые затруднения при определении знака строки, когда ее нераспределенный остаток равен нулю. В этом случае строку считают положительной при условии, что вторая заполненная клетка, стоящая в столбце, связанном с данной строкой еще одной заполненной клеткой, расположена в положительной строке.

После конечного числа описанных выше интеграций нераспределенный остаток становится равным нулю. В результате получают оптимальный план данной транспортной задачи [2,3].