Задача № 7. На трёх базах А1, А2, А3, находится однородный груз в количестве а1 т, a2 т, а3 т

На трёх базах А₁, А₂, А₃, находится однородный груз в количестве а₁ т, a₂ т, а₃ т. Этот груз необходимо развести пяти потребителям В₁, В₂, В₃, В₄, В₅, потреб­ности которых в данном грузе составляют b₁ т, b₂ т, b₃ т, b₄ т, b₅ т соответственно.

Известны тарифы, т.е. затраты на перевозку одной тонны груза от каждого склада до каждого потребителя и значения а₁, а₂, а₃, b₁, b₂, b₃, b₄, b₅ , которые приведены в таблице. Требуется:

1) найти первый опорный план методом минимальных тарифов;

2) построить оптимальный план перевозок методом потенциалов.

Таблица № 1

Построение исходного опорного плана транспортной задачи методом минимальной стоимости.

1) В таблице №1 находим клетку с наименьшим тарифом. Это клетка (1,1). Ее будем заполнять первой.

В нее вместо x₁₁ надо записать поставку, которую находим как минимум значения а₁ = 200 m запаса груза на первой базе и значения b₁ = 70 т заявки от первого магазина, т.е. x₁₁ = min{200, 70} =70.

Потребности в грузе первого магазина удовлетворены. Поэтому заполняем оставшиеся клетки первого столбца нулями.

Запасы груза у первого поставщика уменьшились на величину 70 m. Это запишем в последнем столбце первой строки.

В результате получим таблицу № 2.

Таблица № 2

2. В оставшейся таблице № 2 снова находим пустую клетку с наименьшим тарифом. Это клетки (1,4) и (3,2), в них c₁₄=c₃₂=5. Выбираем любую, например (3,2).

Вместо неизвестной поставки x₃₂ записываем значение, которое находим как минимум значения a₃ = 100 m запаса груза на третьей базе и значения b₂= 80 m заявки от второго магазина: x₃₂ = тin{100, 80} =80.

Потребности в грузе второго магазина удовлетворены. пустые клетки второго столбца заполняем нулями. Запасы груза у первого поставщика уменьшились на величину 80 m. Это отметим в последней строке второго столбца.

В результате получим таблицу № 3.

Таблица № 3

3. В оставшейся части таблицы №3 опять находим клетку с наименьшим тарифом. Это клетка (1,4), для нее c₁₄= 5. Вместо неизвестной поставки x₁₄ записываем значение, которое находим как минимум значения остатков запаса груза на первой базе 200-70=130m. и значения b₄ =110 m заявки четвертого магазина: x₁₄ = min{130, 110} = 110.

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

Запасы груза у первого поставщика еще уменьшились на величину 110 m и составили 130 - 110 = 20 m. Записываем это в последнем столбце первой строки и получаем таблицу № 4.

Таблица № 4

4. Среди пустых клеток таблицы № 4 находим клетку с наименьшим тарифом. Это клетка (1,3), в ней с₁₃= 6.

Находим неизвестную поставку x₁₃ как минимум значения остатка запаса груза на первой базе 130-110=20 m и значения b₃= 150 m заявки третьего магазина: x₁₃ = min{20, 150} =20.

Запасы груза у первого поставщика израсходованы полностью, поэтому все пустые клетки первой строки заполняем нулями. Но потребности в грузе третьего магазина удовлетворены не полностью, оставшаяся потребность составляет 150 - 20 = 130m. Отражаем все это в таблице № 5.

Таблица № 5

5. Среди пустых ячеек таблицы № 5 ищем клетку с наименьшим тарифом. Это клетка (2,3), ее тариф c₂₃ = 9.

Неизвестную поставку х₂₃ найдем как минимум значения запаса груза на второй базе a₂= 200 m и значения оставшейся потребности в грузе у третьего магазина 150 - 20 = 130 m : x₂₃ = min{200, 130} = 130.

Потребности в грузе третьего магазина полностью удовлетворены. Пустые клетки третьего столбца заполняем нулями. Запасы груза у второго поставщика уменьшились на величину 130 m и теперь равны 200 - 130 = 70 m. В результате получаем таблицу № 6.

Таблица № 6

6. Для рассмотрения остался последний пятый столбец, соответствующий потребителю В₅. Наименьший тариф в оставшихся для заполнения клетках с₂₅= 10.

Находим неизвестную поставку x₂₅ как минимум значения остатка запаса груза на второй базе 200 - 130= 70 m и значения b₅ = 90 m : x₂₅=min{70,90} =70.

Запасы груза у второго поставщика израсходованы полностью. Вторую строку вычеркиваем. Потребности в грузе пятого потребителя удовлетворены не полностью, оставшаяся потребность составляет 90 - 70 = 20 m.

Таблица № 7

7. Заполнение последней клетки (3,5) не составляет никаких трудностей. Наконец - то все грузы развезены, а каждый потребитель получил полностью все заказанное.

Опорный план транспортной задачи, построенный методом минимальных тарифов, в своем окончательном виде представлен в таблице № 9. В ней значения запасов груза и заявок сохранены первоначальными.

Таблица № 9

8. Проверим полученный опорный план на вырожденность. Считаем количество ненулевых клеток в таблице 9, их семь. Значение m+n-1=3+5-1=7 также равно семи, значит, полученный опорный план невырожденный.[2]

9. Вычисляем транспортные расходы при таком плане перевозок, перемножая значения, стоящие в нижних и верхних уголках каждой из ненулевых клеток:

II. Нахождение оптимального плана транспортной задачи методом потенциалов.

За основу берем построенный ранее методом минимальных тарифов опорный план транспортной задачи (см. табл. №9). Воспроизведем ее еще раз.

Таблица № 10

1. Определим потенциалы каждого поставщика А_i и каждого потребителя В_j. Для этого поставим в соответствие:

поставщику А₁, т.е. первой строке, потенциал a₁,

поставщику А₂, т.е. второй строке, потенциал a₂,

поставщику А₃, т.е. третьей строке, потенциал a₃,

потребителю B₁, т.е. первому столбцу, потенциал b₁,

потребителю B₂, т.е. второму столбцу, потенциал b₂,

потребителю B₃, т.е. третьему столбцу, потенциал b₃,

потребителю B₄, т.е. четвертому столбцу, потенциал b₄,

потребителюB₅, т.е. пятому столбцу, потенциал b₅.

2. Для нахождения потенциалов составляем для каждой ненулевой клетки соотношения a_i + b_j = с_ij :

Для решения системы полагаем a₁=0. Тогда из первого уравнения получаем b₁ = 4; из второго 0 +b₃ = 6 Þ b₃ = 6; из третьего 0 +b₄, = 5, Þ b₄ = 5.

Подставляем найденное значение b₃ = 6 в четвертое уравнение системы a₂ + b₃ = 9, тогда a₂ + 6 = 9, т.е. a₂ = 3.

Далее подставляем значение a₂ = 3 в пятое уравнение системы

a₂ + b₅ = 10, отсюда 3+b₅ = 10, или b₅ =7.

Следующее уравнение системы пропускаем, т.к. в нем обе переменные неизвестные.

А в последнее уравнение a₃ + b₅ = 20 подставляем найденное значение b₅ =7, получим:, a₃ + 7 = 20, т.e. a₃ = 13.

Возвращаемся к шестому уравнению: a₃ + b₂ = 5, подставляем a₃ = 13, получаем 13 + b₂ = 5 или b₂ = - 8.

Выпишем найденные значения потенциалов:

Занесем их в таблицу №10. В результате получим таблицу № 11.

Таблица № 11

3. Определим косвенные тарифы с_ij^* для каждой незаполненной клетки таблицы №11.

Косвенным тарифом с_ij для клетки с номером (i,j) таблицы перевозок называется алгебраическая сумма потенциалов i-той строки и j-ого столбца, на пересечении которых находится эта клетка, то есть с_ij* = a_i + b_j.

Отсюда следует, что для всех заполненных (базисных) клеток косвенный тариф равен истинному, т.е. с_ij* = с_ij .

Для свободных клеток в общем случае с_ij* ¹ с_ij.

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

для клетки с номером (1, 2): с₁₂*= a₁ + b₂ = 0 - 8 = -8,

для клетки с номером (1, 5): с₁₅* = a₁ + b₅ =0 + 7 = 7,

для клетки с номером (2, 1): с₂₁* = a₂ + b₁ = 3 + 4 = 7,

для клетки с номером (2, 2): с₂₂* = a₂ + b₂ = 3 - 8 = -5

для клетки с номером (2, 4): с₂₄* = a₂ + b₄ = 3 + 5 = 8,

для клетки с номером (3, 1): с₃₁* = a₃ + b₁ = 13 + 4 = 17,

для клетки с номером (3, 3): с₃₃* = a₃ + b₃ = 13 + 6 = 19,

для клетки с номером (3, 4): с₃₄* = a₃ + b₄ = 13 + 5 = 18.

4. Проверим полученный план перевозок на оптимальность. Сформируем сначала общие правила проведения такой проверки:

1) для всех незаполненных клеток вычисляем величину , представляющую собой разницу между косвенным и истинным тарифом.

2) если для всех свободных клеток таблицы перевозок значение критерия оптимальности d_ij ≤ 0, то этот план перевозок является оптимальным. Причемесли для всех свободных клеток значение критерия оптимальности d_ij<0, то этот оптимальный план перевозок является к тому же и единственным. Если же для некоторых свободных клеток значение критерия оптимальности d_ij = 0, то этот оптимальный план перевозок не является единственным;

3) если имеются свободные клетки, для которых критерий оптимальности d_ij > 0, то полученный план перевозок не является оптимальным.

В соответствии с вышеизложенным записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:

с₁₂* = -8 с₁₂ = 11 d₁₂ = -8 – 11 = -19 £ 0

с₁₅* = 7 с₁₅ = 15 d₁₅ = 7 – 15 = -8 £ 0

с₂₁* = 7 с₂₁ = 8 d₂₁ = 7 – 8 = -1 £ 0

с₂₂* = -5 с₂₂ = 7 d₂₂ = -5 – 7 = -12 £ 0

с₂₄* = 8 с₂₄ = 13 d₂₄ = 8 – 13 = -5 £ 0

с₃₁* = 17 с₃₁ = 10 d₃₁ = 17 – 10 = 7 > 0

с₃₃* = 19, с₃₃ = 12 d₃₃ = 19 – 12 = 7 > 0

с₃₄* = 18, с₃₄ = 7 d₃₄ = 18 – 7 = 12 > 0.

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

5. Для удобства изложения воспроизведем опорный план перевозок (таблица № 11) еще раз как таблицу № 12.

Таблица № 12

Для клеток (3,1), (3,3), (3,4) d_ij > 0. Среди них выбираем клетку с максимальным значением d_ij. Это клетка с номером (3, 4). Ставим в ней знак "+".

Для нее строим цикл, вычеркивая в таблице №12 те столбцы и строки, в которых есть только одна поставка, считая, что в клетке (3, 4) также есть поставка.

Вычеркнутыми будут первый и второй столбец, выделим их серым цветом. Все остальные заполненные клетки образуют цикл а) на рис 3.

Каждой вершине цикла будут соответствовать чередующиеся знаки "+" или "-", расставлять которые надо, начиная с "9" в клетке (3, 4), для которой мы строим этот цикл.

Затем в тех вершинах, где стоит знак "-", находим наименьшую поставку min{ 130, 110, 20}. Это 20 в вершине (3, 5).

Обозначим эту величину Δ = 20, и теперь величину Δ вычитаем из поставок в вершинах со знаком "-" и прибавляем в те вершины, где стоит "+" (см. рис. 3б). Новый цикл, полученный после пересчета, представлен на рис.3в.

Рис. 3. Цикл пересчёта для клетки (3, 4):

а) цикл в исходном плане; б) пересчёт по циклу; в) новый цикл.

6. Заменяя старый цикл в таблице № 12 на новый, получаем таблицу №13. Обратите внимание, что после пересчёта по циклу суммы поставок по строкам и столбцам не изменились и полученный план также невырожденный.

Таблица № 13

7. Проверим его на оптимальность, пользуясь методом потенциалов.

Определяем потенциалы каждого поставщика А_iи каждого потребителя В_j. Для чего записываем для каждой заполненной клетки таблицы № 13 соотношения a_i + b_j = с_ij

Полагаем a₁ = 0 и решаем систему уравнений аналогично тому, как это было сделано в п.2. В результате получаем:

8. Определим косвенные тарифы с^*_ij для каждой незаполненной клетки таблицы №13:

для клетки с номером (1, 2): с₁₂* = a₁ + b₂ = 0 + 3 = 3,

для клетки с номером (1, 5): с₁₅* = a₁ + b₅ = 0 + 7 = 7,

для клетки с номером (2, 1): с₂₁* = a₂ + b₁ = 3 + 4 = 7,

для клетки с номером (2, 2): с₂₂* = a₂ + b₂ = 3 + 3 = 6,

для клетки с номером (2, 4): с₂₄* = a₂ + b₄ = 3 + 5 = 8,

для клетки с номером (3, 1): с₃₁* = a₃ + b₁ = 2 + 4 = 6,

для клетки с номером (3, 3): с₃₃* = a₃ + b₃ = 2 + 6 = 8,

для клетки с номером (3, 5): с₃₅* = a₃ + b₅ = 2 + 7 = 9.

9. Записываем рядом косвенные и истинные тарифы, а также критерий оптимальности:

с₁₂* = 3, с₁₂ = 11; d₁₂ = 3 – 11 = -8 < 0,

с₁₅* = 7, с₁₅ = 15; d₁₅ = 7 – 15 = -8 < 0,

с₂₁* = 7, с₂₁ = 8; d₂₁ = 7 – 8 = -1 < 0,

с₂₂* = 6, с₂₂ = 7; d₂₂ = 6 – 7 = -1 < 0,

с₂₄* = 8, с₂₄ = 13; d₂₄ = 8 – 13 = -5 < 0,

с₃₁* = 6, с₃₁ = 10; d₃₁ = 6 – 10 = -4 < 0,

с₃₃* = 8, с₃₃ = 12; d₃₃ = 8 – 12 = -4 < 0,

с₃₅* = 9, с₃₅ = 20; d₃₅ = 9 – 20 = -11 < 0.

Критерий оптимальности d_ij £ 0 выполнен для всех клеток, кроме того, все значения d_ij < 0. А это значит что полученный план перевозокоптимальный и единственный.

10. Вычисляем затраты на все планируемые перевозки:

11. Сравним найденное значение F_опт с затратами F, полученными при составлении первоначального опорного плана по методу наименьшей стоимости. Видим, что транспортные расходы уменьшились на величину:

DF = F - F_опт = 3620 - 3400 = 220 (тыс. руб.).

Ответ:1) Первоначальный опорный план перевозок, построенный по методу наименьшей стоимости, приведён в таблице № 9. При этом плане перевозок транспортные расходы составляют F=3620 тыс. руб.

2) Оптимальный план перевозок приведен в таблице № 13. При этом плане перевозок транспортные расходы составляют:F_опт=3400 тыс. руб. Экономия от улучшения этого опорного плана составляет DF=F-F_опт=220тыс. руб.