Алгоритм распределительного метода

1. Проверяют, является ли модель транспортной задачи закрытой. Если модель открытая, то, введя фиктивный пункт отправления (назначе­ния) с нулевыми удельными стоимостями перевозок, сводят ее к закрытой модели.

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

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

4. Если среди оценок свободных клеток найдется хотя бы одна отрица­тельная, то для одной из свободных клеток с отрицательной оценкой строят ее цикл пересчета. Осуществляют сдвиг по этому циклу на число x₀, вычисленное по формуле (7). Получив новое базисное решение, переходят к пункту 3.

Замечание 1. Если имеется несколько свободных клеток с отрица­тельными оценками, то предпочтение среди них можно отдать клетке с минимальной удельной стоимостью. У этой рекомендации нет какого-либо серьезного обоснования, кроме интуитивного соображения о том, что в первую очередь следует заполнять клетки с минимальной удельной стоимо­стью.

Замечание 2. Иногда минимальное значение x₀ достигается в нескольких базисных клетках. В этом случае удаляют ту из базисных клеток, в которой содержится наибольшая удельная стоимость c_pq. В остальных базисных клетках, где достигается минимальное значение x₀, неизвестные при сдвиге по циклу принимают значение 0, т.е. получается вырожденное базисное решение. Вырожденным называется базисное решение, в котором некоторые базисные неизвестные равны 0.

Замечание 3. В тех случаях, когда базисное решение вырождено, может оказаться, что минимальное значение x₀ равно нулю. В такой ситуации нуль сдвигают в свободную клетку и она становится базисной, а базисная клетка, где стоял этот нуль ранее, становится свободной.

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

 

Метод потенциалов

По методу потенциалов пунктам отправления А₁, А₂,..., А_т приписывают потенциалы a₁, a₂,..., a _m, а пунктам назначения В₁, В ₂,..., В_n приписывают потенциалы b₁, b₂,..., b _n. Значения потенциалов находят из системы линейных уравнений вида

a _p + b _q = c _pq (8)

где c _pq — удельная стоимость в базисной (!) клетке (р, q). Число базисных клеток равно т + п – 1, а число потенциалов равно т + п, поэтому, система линейно независимых уравнений вида (8) недоопределена и, следовательно, один из потенциалов можно задать произвольно.

Подставим выражения (8) удельных стоимостей через потенциалы в формулу (6), получим

d _ij = c_ij – c_ik + c_lk – … + c_st – c_sj =

= c_ij – a _i – b _k + a _l + b _k – … + a _s + b _t – a _s – b _j = c_ij – a _i – b _j .

Таким образом, оценка свободной клетки (i, j) равна

d _ij = c_ij – (a _i + b _j ). (9)

 

Таблица 10.

ai \ bj	b1=90	b2=15	b3=20	b4=80
a1 =55
a2 =75
a3 =50
a4 =25

 

Пример 2. Решить транспортную задачу, данные которой приведены в табл. (10). В первом ее столбце указаны запасы груза в четырех пунктах отправления, а в первой строке — потребности пунктов назначе­ния. В левых верхних углах остальных клеток таблицы помещены удельные стоимости перевозок.

Таблица 11.

ai \ bj	b1=90	b2=15	b3=20	b4=80
a1 =55	12 / 50	8 / 0	6 / 0	3 / 5
a2 =75	9 / 0	4 / 0	5 / 0	3 / 75
a3 =50	7 / 35	5 / 15	10 / 0	10 / 0
a4 =25	6 / 5	8 / 0	5 / 20	9 / 0

 

Убедившись в том, что модель рассматриваемой задачи закрытая, рас­пределим груз по методу наименьшей стоимости. Исходное базисное реше­ние заносим в табл. 11. Стоимость полученного плана перевозок равна z =50*12+5*3+75*3+35*7+15*5+5*6+20*5=1290. ^:

Для оценки свободных клеток табл. 11 по методу потенциалов в соответствии с формулой (8) составим для базисных (!) клеток табл. 11 систему уравнений

a ₁ + b ₁ = 12, a ₁ + b ₄ = 3,

a ₂ + b ₄ = 3, (10)

a ₃ + b ₁ = 7, a ₃ + b ₂ = 5,

a ₄ + b ₁ = 6, a ₄ + b ₃ = 5,

из которой найдем потенциалы a _i, b _j, i, j = 1, 2, 3, 4. Для наглядно­сти уравнения в системе (10) расположены также как базисные клетки в матрице перевозок, см. табл. 11.

Положим в системе (10) a ₁ = 3, тогда из уравнений 1-й строки имеем b ₁ = 9, b ₄ = 0.

Далее, используя ранее вычисленные значения, из 2-й строки системы (10) получим a ₂ = 3, из 3-й — a ₃ = –2, b ₂ = 7, из 4-й — a ₄ = –3, b ₃ = 8. Запишем эти потенциалы в табл. 12.

Таблица 12.

ai \ bj	b1=90	b2=15	B3=20	b4=80
a1 =55	12 / 50	8 / –2	6 / –5	3 / 5
a2 =75	9 / –3	4 / –6	5 / –6	3 / 75
a3 =50	7 / 35	5 / 15	10 / 4	10 / 12
a4 =25	6 / 5	8 / 4	5 / 20	9 / 12

 

Заметим, что для вычисления потенциалов нет необходимости выпи­сывать систему (10). Можно в табл. 12 задать один из потенциалов и, двигаясь в табл. 12 через базисные клетки, вычислить последовательно остальные потенциалы, используя равенство (8).

Вычислим по формуле (9) оценку каждой свободной клетки табл. 12 и занесем ее в знаменатель этой клетки:

d ₁₂ = c₁₂ – (a ₁ + b ₂ ) = 8 – (3 + 7) = –2,

d ₁₃ = c₁₃ – (a ₁ + b ₃ ) = 6 – (3 + 8) = –5,

d ₂₁ = c₂₁ – (a ₂ + b ₁ ) = 9 – (3 + 9) = –3,

d ₂₂ = c₂₂ – (a ₂ + b ₂ ) = 4 – (3 + 7) = –6,

d ₂₃ = c₂₃ – (a ₂ + b ₃ ) = 5 – (3 + 8) = –6,

d ₃₃ = c₃₃ – (a ₃ + b ₃ ) = 10 – (–2 + 8) = 4,

d ₃₄ = c₃₄ – (a ₃ + b ₄ ) = 10 – (–2 + 0) = 12,

d ₄₂ = c₄₂ – (a ₄ + b ₂ ) = 8 – (–3 + 7) = 4,

d ₄₄ = c₄₄ – (a ₄ + b ₄ ) = 9 – (–3 + 0) = 12.

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

Выберем в табл. 12 свободную клетку (2, 2) с отрицательной оценкой d ₂₂ = -6 (см. выше замечание 1). Построим цикл пересчета этой клетки, означим его так, чтобы вершина цикла в клетке (2, 2) имела знак "+". Отрицательным вершинам цикла соответствуют значения базисных неизвестных x^–₁₁ = 50, x^–₂₄ = 75, x^–₃₂ = 15. Находим

x₀ =min { x^–₁₁, x^–₂₄, x^–₃₂} = min {50, 75, 15} = x^–₃₂ = 15.

Так какминимум достигается в клетке (3, 2), то, осуществив сдвиг по циклу пересчета на 15, клетку (3, 2) удаляем из числа базисных (она становится свободной). Клетка (2, 2) становится базисной, при этом x₂₂ = 15. Переходим к табл. 13. Снова вычисляем по формулам (8) потенциалы, задав какой-нибудь из них, например a ₂ = 3.

Таблица 13.

ai \ bj	b1=90	b2=15	B3=20	b4=80
a1 =55	12 / 35	8 / –4	6 / –5	3 / 20
a2 =75	9 / –3	4 / 15	5 / –6	3 / 60
a3 =50	7 / 50	5 / 6	10 / 4	10 / 12
a4 =25	6 / 5	8 / 4	5 / 20	9 / 12

 

Уместно заметить, что выбор того или иного значения для задаваемого потенциала сказывается на значениях всех потенциалов следующим образом. Если все вычисленные потенциалы, например, для пунктов отправле­ния увеличить (уменьшить) на одно и тоже число, то все потенциалы для пунктов назначения уменьшатся (увеличатся) на то же число. Вычисляем теперь оценки свободных клеток табл. 13 по формулам (9). Выберем в табл. 13 свободную клетку (2, 3) с отрицательной оценкой d₂₃ = –6. Построив для этой клетки цикл пересчета, осуществляем сдвиг по нему на

x₀ = min { x^–₁₁, x^–₂₄, x^–₄₃} = min {35, 60, 20} = x^–₄₃ = 20.

Клетка (2, 3) становится базисной вместо клетки (4, 3), которая ста­новится свободной. Переходим к табл. 14.

Таблица 14.

ai \ bj	b1=90	b2=15	B3=20	B4=80
a1 =55	12 / 15	8 / –4	6 / –1	3 / 40
a2 =75	9 / –3	4 / 15	5 / 20	3 / 40
a3 =50	7 / 50	5 / 6	10 / 10	10 / 12
a4 =25	6 / 25	8 / 10	5 / 6	9 / 12

 

Вычислим потенциалы и оценки свободных клеток табл. 14. В ней одна свободная клетка (2, 1) имеет отрицательную оценку d₂₁ = –3. По циклу пересчета этой клетки осуществляем сдвиг на

x₀ = min { x^–₁₁, x^–₂₄ } = min {15, 40} = x^–₁₁ = 15.

Клетка (2,1) становится базисной вместо клетки (1,1), которая становится свободной. Переходим к табл. 15.

Таблица 15.

ai \ bj	b1=90	b2=15	B3=20	B4=80
a1 =55	12 / 3	8 / 4	6 / 1	3 / 55
a2 =75	9 / 15	4 / 15	5 / 20	3 / 25
a3 =50	7 / 50	5 / 6	10 / 10	10 / 12
a4 =25	6 / 25	8 / 10	5 / 6	9 / 12

 

Все оценки свободных клеток табл. 15 положительны, следовательно, табл. 15 содержит оптимальное решение, в котором

x₁₄ = 55, x₂₁ = 15, x₂₂ = 15, x₂₃ = 20, x₂₄ = 25, x₃₁ = 50, x₄₁ = 25.

Остальные неизвестные равны нулю. Полученное решение указывает оп­тимальный план перевозок. Например, x₂₃ = 50 означает, что из 2-го пун­кта отправления в 3-й пункт назначения следует перевезти 50 ед. груза. Общая стоимость перевозок по этому плану будет наименьшей по сравне­нию с любым другим планом. Она равна

z = 55 • 3 + 15 • 9 + 15 • 4 + 20 • 5 + 25 • 3 + 50 • 7 + 25 • б = 1035.

 

Полезно еще раз обсудить экономический смысл оценок свободных клеток. Как отмечалось ранее, оценка свободной клетки для данного базисного решения равна изменению стоимости перевозок при сдвиге по циклу перес­чета рассматриваемой свободной клетки на единицу груза. Оценка свобо­дной клетки (2, 1) табл. 14 равна d₂₁ = –3. Следовательно, при переходе от табл. 14 к табл. 15, когда был осуществлен сдвиг на 15 ед. груза по циклу пересчета клетки (2, 1), стоимость перевозок уменьшилась на (–Dz) = 3 • 15 = 45, т.е. план перевозок, соответствующий базисному реше­нию, содержащемуся в табл. 14, дороже оптимального плана на 45 единиц стоимости и стоит 1080 единиц.

 

Замечание 4. Если оценка одной из свободных клеток в таблице с оптимальным решением равна нулю, то может оказаться, что оптимальное решение не единственно. Например, для задачи, решение которой привело к табл. 16, бесконечное множество оптимальных решений дает табл. 17. Частное решение определяется значениями параметра q, 0 £ q £ 40. При q = 0, q = 40 решения будут базисными.

Таблица 16.

ai \ bj	b1=6	b2=5	b3=4	b4=4
a1 =0	7 / 1	5 / 40	4 / 40	8 / 4
a2 =3	10 / 1	8 / 50	8 / 1	7 / 50
a3 =4	11 / 1	10 / 1	8 / 0	8 / 60
a4 =2	8 / 45	9 / 2	6 / 25	10 / 4

Таблица 17.

ai \ bj	b1=45	b2=90	B3=65	B4=110
a1 =80		5 / 40+ q	4 / 40– q
a2 =100		9 / 50– q		7 / 50+ q
a3 =60			8 / q	8 / 60– q
a4 =70	8 / 45		6 / 25

 

Геометрически это значит, что множество оптимальных решении пред­ставляет собой отрезок в евклидовом пространстве соответствующей размерности и гиперплоскость уровня z = 1035 касается многогранника допу­стимых решений по ребру, которое и является этим отрезком.

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

 

 

⇐ Предыдущая12

Поделиться:

Воспользуйтесь поиском по сайту: