Математическая постановка задачи

Классическая постановка транспортной задачи. Пусть имеется т поставщиков А₁, А₂,..., А_i,.., А_т однородного груза в количествах соответственно a₁, a₂, …, a_i, …, a_mединиц и п потребителей В₁, В₂,..., B_j,..., В_п этого груза, потребность которых составляет соответственно b₁, b₂, …, b_j, …, b_nединиц.

Известны стоимости перевозок единицы груза от (i-го поставщика к j-му потребителю — С _ij (i= 1, т; j=1, п).

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

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

Прежде чем приступить к построению модели задачи, необходимо обозначить неизвестные. Исходя из условия задачи, неизвестной величиной является количество единиц груза, перевозимого от каждого поставщика к каждому потребителю. Обозначим через x_ij (i=1, m; j=1, n)- количество единиц груза, перевозимого от i-го поставщика к j-му потребителю.

Чтобы лучше представить условие задачи, сведём исходные данные в табл. 1. Строка таблицы соответствует поставщику, а столбец - потребителю.

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

∑ ai = ∑ bj (1)

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

Таблица

b1

b2

…

bj

…

bn

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

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

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

Методы построения исходного плана

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

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

Определение значений Х_ijначи­нается с левой верхней клетки таблицы (это соответствует севе­ро-западному углу на географической карте). Находим значение Х₁₁из соотношения

Х₁₁=min {a₁, b₁}

Возможны три варианта:

1) если a₁< b₁, то Х₁₁ = a₁строка i=1исключается из дальней­шего рассмотрения, а потребность первого потребителя b₁ (стол­бец j=1) уменьшается на величину a₁.;

2) если a₁> b₁ \, то Х₁₁ = b₁, столбец j=1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика
а ₁(строка i=1 ) уменьшается на величину b₁.

3) если a₁ = b₁, то Х₁₁ = a₁ = b₁, строка i= 1и столбец j=1 исключаются из дальнейшего рассмотрения. Данный вариант при­водит к вырождению исходного плана.

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

После завершения описанного процесса необходимо провести проверку полученного плана на вырожденность. Если количество заполненных клеток равно m+n — 1, то план является невырож­денным, в противном случае — вырожденным.

Если план вырожденный, т. е. количество заполненных клеток оказалось меньше m+n—1, то незаполненные клетки с мини­мальными стоимостями перевозок заполняются нулями, чтобы об­щее количество заполненных клеток стало равным m+n—1. Однако при расстановке нулей необходимо помнить, что в таблице не должно быть ни одного прямоугольника, все вершины которого являются заполненными клетками. Например, переменные x₂₁, x₂₂ или x₁₁, x_1n, x₂₁, x_2n(табл. 1) не могут быть одновре­менно базисными.

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

Метод минимального элемента.

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

Определение значений Х_ijначинается с клетки, имеющей ми­нимальную стоимость перевозки (если таких клеток более одной, то договоримся выбирать первую по порядку).

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

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

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

Проверка полученного плана на вырожденность и расстановка (в случае вырож­денности плана) нулей осуществляется так же, как это описано для метода северо-за­падного угла.

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