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

a_i b_j

На 1-м этапе определяем тип задачи и закрепляем потребителей за поставщиками (таблица 6.2 и 6.3).

a_i =60+100+120=280.

b_j =30+100+40+110=280.

a_i = b_j – закрытая транспортная задача.

В методе северо-западного угла первой заполняется клетка (1,1) по принципу x ₁₁=min{ a ₁, b ₁}, т.е. либо полностью удовлетворяется первый потребитель, либо полностью истощается первый поставщик, а затем остальные клетки 1-й строки: x ₂=min{ a ₁- b ₁, b ₂}, если a₁> b ₁ или переходит к заполнению соседней клетки (2,1), если a ₁< b ₁ и т.д.

После заполнения матрицы перевозок по методу северо-западного угла значение целевой функции будет:

f ()=4 30+5 30+3 70+6 30+7 10+4 110=1170ед.

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

Метод наименьших стоимостей учитывает этот момент. Рассмотрим одну из модификаций метода – «двойное предпочтение», в соответствии с которым в первую очередь заполняются клетки с наименьшими значениями с_ij по строке и по столбцу (два кружка – отметины), затем клетки с наименьшими значениями или по строке, или по столбцу (один кружок – отметина).

Таблица 6.3

Матрица перевозок с применением метода наименьших стоимостей

b_j a_i 100 U _i

60 40

1 30

-1

V _j

Значение целевой функции значительно уменьшилось:

f ()=1 30+2 100+2 40+2 70+3 20+4 20=590ед.

На 2-м этапе по методу потенциалов проверяем оптимальность плана. Рассмотрим процесс нахождения потенциалов для исходного плана по методу северо-западного угла. Зададимся значением U₁, т.к. одним значением U _i всегда можно задаться. Определяем по (6.5) для первой строки по заполненным клеточкам:

V₁=U₁+ с ₁₁т.к. U₁=0 V₁= с ₁₁; V₁=4.

V₂=U₁+ с ₁₂V₂= с ₁₂; V₂=5.

С другой стороны для второго столбца должно выполняться:

V₂=U₁+ с ₁₂и V₂=U₂+ с ₂₂.

Но V₂=5, тогда U₂= V₂ – с ₂₂= 5 – 3 = 2.

Продолжая сравнение потенциалов по строке и столбцам, определяем все потенциалы (таблица 6.4).

Таблица 6.4

Потенциалы для метода северо-западного угла

b_j a_i U₁

V _j

В таблице 6.3 даны потенциалы для метода наименьших стоимостей. Чтобы оценить оптимальность распределения, для всех клеток (i, j) матрицы перевозок, определяют их оценки d_ij по формуле:

d_ij = (U _i + с _ij) – V _j.

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

Оценки обычно представляются в виде матрицы оценок. Составим матрицу оценок для таблицы 6.4:

[ d_ij ]= .

Очевидно, что план далек от оптимального, т.к. большое число отрицательных оценок.

На 3-м этапе производим корректировку исходного плана. Выбирается клетка с наибольшей по абсолютной величине отрицательной оценкой, и строится прямоугольный контур, начальная вершина которого лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках (d_ij =0). Вершинам контура присваиваются поочередно по контуру знаки «+», «–», начиная со знака «+» в выбранной свободной клетке.

Выбирается наименьшая величина поставок в клетках со знаком «–» и на эту величину увеличивается поставки в клетках со знаком «+». Для таблицы 6.4 наибольшая по абсолютной величине оценка равна 6. Строим прямоугольный контур (таблица 6.4). Наименьшая величина в клетках со знаком «–» равна 30. Получаем:

Таблица 6.5

Преобразованная матрица перевозок

b_j a_i U₁

-5

V _j -1

Новое значение целевой функции будет:

f ()=4 30+5 0+2 30+3 100+7 10+4 110=990<1170,

что меньше исходного значения.

Определяем новые потенциалы и составляем матрицу оценок:

[ d_ij ]=

и процесс повторяется, т.е. возвращаемся к пункту 2.

Транспортные задачи, в базисном плане, перевозки которых имеют место занятые клетки с нулевой поставкой называются вырожденными. В этом случае существует опасность зацикливания. При нахождении потенциала V₂была использована занятая клетка (1;2) с нулевой подстановкой. Значит, это задача является вырожденной.

Матрица оценок, составленная для распределения (плана) методом наименьших стоимостей (таблица 6.3), показывает, что он оптимален, т.к. нет отрицательных оценок, а оценки всех свободных клеток строго больше нуля:

[ d_ij ]= .

Пример 6.2. Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участок ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ (в у.е.) на перевозку 1 тонны песка с карьеров на ремонтные участки. Числовые данные приведены в таблице 6.6. Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.

Таблица 6.6

Матрица транспортных затрат

В _j А _i 30 40 U₁

40

10 7

Методом наименьших стоимостей определим начальный опорный план перевозок (таблица 6.6 для закрытой транспортной задачи, т.к. a_i =100т и b _j =100т.

Вначале заполняем клеточки с«двойным предпочтением», затем клеточки с«предпочтением» и нехватку в 5тдля 1-го ремонтного участка – клеточка (3;1) – в самом конце, исходя из минимума затрат.

Составим матрицу оценок по таблице 6.6:

[ d_ij ]= ,

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

Величина транспортных издержек определится:

f _min ()=3 10+4 20+4 10+3 20+4 5+3 30+4 5=340у.е.,

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