3.3.2 Метод дифференциальных рент

Математическая постановка задачи. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза изmпунктов отправлениявnпунктов назначения. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим черезтарифы перевозки единицы грузаi-го пункта отправления вj-й пункт назначения, через- запасы груза вi-м пункте отправлении, через- потребности вj-м пункте назначения, а черезколичество единиц груза, перевозимого изi-го пункта отправления вj-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

(3.20)

при условиях

(3.21)

(3.22)

(3.23)

Поскольку переменныеудовлетворяют системам линейных уравнений (3.21) и (3.22) и условию не отрицательности (3.23), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, а также исключаются обратные перевозки.

Определение: Всякое неотрицательное решение систем линейных уравнений (3.21) и (3.22), определяемое матрицейназывается планом транспортной задачи.

Определение:План,при котором функция (3.20) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные записывают в виде таблицы:

Таблица 3.18

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равнееединиц. Если общая потребность в грузе в пунктах назначения равна запасу в пунктах отправления, т.е.

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

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

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

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

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

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

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

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

Таблица 3.19

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

Таблица 3.20

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

В результате заполнения отмеченных выше клеток получен так называемый условно оптимальный план, согласно которому полностью удовлетворяются потребности пунктов назначения B₂,B₃иB₅и частично – пункта назначенияB₁иB₄. При этом полностью распределены запасы пункта отправления А₂, так как запасы пункта отправления А₂полностью использованы, а потребности пункта назначенияB₁удовлетворены частично. Величина недостатка равна 2 ед.

Строки А₁и А₃являются избыточными, поскольку запасы пунктов отправления А₁и А₃ распределены не полностью. При этом величина избытка строки А₁равна 1 ед., а строки А₃– 2 ед. Общая величина избытка 1+2=3 совпадает с общей величиной недостатка, равной 3.

После определения избыточных и недостаточных строк по каждому из столбцов находим разности между минимальными тарифами, записанными в избыточных строках, и тарифами, стоящими в заполненных клетках. В данном случае эти разности соответственно равны 4,5,10 (таблица 3.20). Для столбцов B₂иB₅ разность не определена, так как число, записанное в кружке в данных столбцах, находится в положительной строке. В столбцеB₁число, стоящее, стоящее в кружке, равно 8, а в избыточных строках в клетках данного столбца наименьшим является число 12. Следовательно, разность для данного столбца равна 12-8=4. Аналогично находим разности для других столбцов.

Выбираем наименьшую из найденных разностей, которая является промежуточной рентой. В данном случае промежуточная рента равна 4 и находится в столбце B₁. Найдя промежуточную ренту переходим к таблице 3.21.

Таблица 3.21

В этой таблице в строках А₁и А₃(являющихся избыточными) переписываем соответствующие тарифы из строк А₁и А₃таблицы 3.20. Элемент строк А₂и А₄, которые были недостаточными получаются в результате прибавления к соответствующим тарифам, находящимся в строках А₂и А₄(таблицы 3.20) промежуточной ренты, то есть 4.

В таблице 3.21 число заполняемых клеток возросло на одну. Это обусловлено тем, что число минимальных тарифов, стоящих в каждом из столбцов данной таблицы, возросло на 1, а именно столбце B₁теперь имеются два минимальных элемента 12. Эти числа заключаем в кружки; клетки, в которых они стоят, следует заполнить. Необходимо заполнить и клетки, в которых стоят наименьшие для других столбцов тарифы. Это клетки таблицы 3.21, в которых соответствующие тарифы заключены в кружки. После того как указанные клетки определены, устанавливаем последовательность их заполнения. Для этого находим столбцы (строки), в которых имеется лишь одна клетка для заполнения. Определив и заполнив некоторую клетку, исключаем из рассмотрения соответствующий столбец(строку) и переходим к заполнения следующей клетки. В данном случае заполнение клеток проводим в такой последовательности. Сначала заполняем клеткиA₃B₂,A₄B₃,A₄B₄,A₁B₅, так как они являются единственными клетками, для заполнения в столбцахB₂,B₃,B₄,B₅. После заполнения указанных клеток заполняем клетку А₂B₁, поскольку она является единственной для заполнения в строке А₂, заполнив эту клетку (таблица 3), исключаем из рассмотрения строку А₂. Тогда в столбцеB₁остается лишь одна клетка для заполнения. Эта клетка А₃B₁, которую заполняем. После заполнения клеток устанавливаем избыточные и недостаточные строки (таблицы 3.21). Как видно из таблицы 3, еще имеется не распределенный остаток. Следовательно, получен условно оптимальный план задачи, и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (таблица 3.21). Среди этих разностей наименьшая равна 4. Это и есть промежуточная рента. Переходим к новой таблице 3.22.

Таблица 3.22

В новой таблице элементы строки А₁получены в результате прибавления к соответствующим числам строки А₁(являющихся недостаточными) таблицы 3.3.8 промежуточной ренты, т.е. 4. В результате в таблице 3.22 число клеток для заполнения возросло еще на одну и стало равным 7. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₃B₂, А₄B₃,A₄B₄,A₁B₅, а затем А₂В₁, А₁В₁, А₃В₁. Как видно из таблицы 3.22, еще имеется не распределенный остаток. Следовательно, получен условно оптимальный план задачи, и нужно перейти к новой таблице. Для этого по каждому из столбцов находим разности между числом, записанным в кружке данного столбца, и наименьшим по отношению к нему числом, находящимся в избыточных строках (таблица 3.22). Среди этих разностей наименьшая равна 1. Это и есть промежуточная рента. Переходим к новой таблице 3.23

Таблица 3.23

.

В новой таблице элементы строки А₄получены в результате прибавления к соответствующим числам строки А₄(являющихся недостаточными) таблицы 3.22 промежуточной ренты, т.е. 1. В результате в таблице 3.23 число клеток для заполнения возросло еще на одну и стало равным 8. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₃B₂,A₄B₄,A₁B₅, а затем А₂В₁, А₁В₁, А₃В₁, А₃В₃, А₄В₃. В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 8, и все они имеют наименьший показатель с_ij. Следовательно, получен оптимальный план исходной транспортной задачи.

При этом плане перевозок общие затраты таковы: