Вычисляем значения параметра l.

4. Если l<j, производим перераспределение поставок и получаем новое оптимальное решение. Если l=j, то процесс решения окончен.

Рассмотрим решение транспортной параметрической задачи на конкретном примере.

Пример 14. Имеются три поставщика однородного товара с объемами поставок: а₁=100т, а₂= 200т, а₃=100т, и четыре потребителя с объемами потребления b₁=80т,b₂=120т,b₃=150т,b₄=50т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги, и задана матрицей

от 5 до 11 от 4 до 1 8 от 3 до 6

4 7 от 4 до 10 от 7 до 4

5 3 6 от 1 до 10

Определить оптимальное решение перевозок, обеспечивающее минимальные транспортные затраты.

Решение. В матрицу расходов введем параметр l, где 0£l£3. Получим

5+2l 4-l 8 3+l

4 7 4+2l 7-l

5 3 6 1+3l

Полагая l=0, решаем задачу методом потенциалов, определим оптимальное решение перевозок. Распределительная таблица этого решения будет иметь следующий вид.

В таблице a_i и b_j потенциалы строк и столбцов. Для занятых клеток они определяются из условия

a_i+b_j = c¢_ij+ dc²_ij

Полагая:

a₁+b₁=5+2la₁=0 a₁=0

a₁+b₂=4-la₂=-1-2l a₂=-1-2l

a₂+b₁=4 a₃=-1+l

a₂+b₃=4+2lb₁= 5+2l b₁=5+2l

a₃+b₂=3 b₂= 4-l

a₃+b₄=1+3lb₃=5+4l b₃=5+4l

b₄=2+2l b₄=2+2l

Оценки свободных клеток находим по формуле

D_ij=a_i+b_j – (c¢_ij+ dc²_ij)=

D₁₃=a₁+b₃ – c¢₁₃=5+4l+0-8= -3+4l,

D₁₄=a₁+b₄ – (c¢₁₄+lc²₁₄)=2+2l+0-3-l= -1+l,

D₂₂=a₂+b₂ – c¢₂₂ = -1-2l+4-l-7= -4-3l.

Аналогично находим, что D₂₄=-6+l, D₃₁=-1+3l, D₃₃=-2+5l.

Решение, полученное при l=0, является оптимальным для всех значений параметра l, удовлетворяющих условию

Так как по условию задачи l³0,то оптимальное решение сохраняется при 0£l£1/3. При этом минимальная стоимость транспортных расходов составляет

F(x)_min=30(5+2l)+70(4-l)+50*4+150(4+2l)+50*3+50(1+2l)=1430+440l

Таким образом, при lÎ[0;1/3], F(x₁)_min=1430+440l и

30 70 0 0

Х_опт1= 50 0 150 0

0 50 0 50

Чтобы получить оптимальное решение при l³1/3, перераспределим поставки товаров в клетку (3,1), где l₂=1/3. Вновь полученное распределение представлено в таблице.

Находим оценки свободных клеток:

D₁₁=1-3l, D₁₃= -2+l,

D₁₄= -1+l, D₂₂= -5,

D₂₄= -7+4l, D₃₃= -1+2l.

Определим пределы изменения l:

Полученное в таблице оптимальное решение сохраняется при 1/3£l£1/2. При этом F(x₂)_min=1460+350l.

0 100 0 0

Х_опт2= 50 0 150 0

30 20 0 50

Перераспределим поставки грузов в клетку (3,3), где l₂=1/2. Получим новое распределение:

Находим оценки свободных клеток:

D₁₁=2-5l, D₁₃= -1-l,

D₁₄= -1+l, D₂₂= -6+2l,

D₂₄= -8+6l, D₃₃= -1-2l.

Определим пределы изменения l:

Оптимальное решение сохраняется при 1/2£l£1. При этом F(x₃)_min=1490+290l.

0 100 0 0

Х_опт3= 80 0 120 0

0 20 30 50

Перераспределим поставки товаров в клетку (1,4), где l₂=1.

Оценки свободных клеток:

D₁₁=-1-2l, D₁₃= -1-l,

D₂₂= -6+2l, D₂₄= -7+5l,

D₃₁= 1-2l, D₃₄= -1-l.

Пределы изменения l:

Полученное в предыдущей таблице оптимальное решение сохраняется при 1£l£7/5. При этом F(x₄)_min=1540+240l.

0 50 0 50

Х_опт4= 80 0 120 0

0 70 30 0

Перераспределим поставки грузов в клетку (2,4), где l₂=7/5.

Оценки свободных клеток:

D₁₁=2-5l, D₁₃= -1-l,

D₁₄= 7-5l, D₂₂= -6+2l,

D₃₁= 1-2l, D₃₄= -8-6l.

Пределы изменения l:

l₁ =max (2/5;-1;7/5;1/2;-8/6)=7/5,b_ij<0;

l₂=min (3)=3,b_ij>0.

Оптимальное решение сохраняется при 7/5£l£3. При этом F(x₅)_min=1890-10l.

0 100 0 0

Х_опт5= 80 0 70 50

0 20 80 0

Варианты контрольной работы по теме «Параметрическая транспортная задача»

Имеются три поставщика однородного товара с объектами поставок: а₁=100 т., а₂=200 т., а₃=100 т. И четыре потребителя с объектами потребления b₁=80 т., b₂=120 т., b₃=150 т., b₄=50 т. Стоимость транспортных расходов изменяется в определенном диапазоне в зависимости от загрузки дороги, и задана матрицей

Определить оптимальное решение, обеспечивающее минимальные транспортные затраты.

Транспортная задача в сетевой постановке.

Понятие транспортной сети.

Транспортная задача может быть задана в виде специальной схемы – транспортной сети. Пункты расположения поставщиков и потребителей изображаются кругами и называются вершинами сети. Мощности поставщиков будем отмечать положительными числами, а спрос потребителей – отрицательными числами. Дороги, связывающие поставщиков и потребителей, изображаются в виде линий и называются ребрами сети. Реальный масштаб не соблюдается. Возможны вершины с нулевым запасом груза – нулевые вершины.

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

На план поставок налагаются следующие условия:

1) Все мощности поставщиков должны быть распределены;

2) Весь спрос потребителей должен быть удовлетворен;

3) К каждой вершине должна подходить или выходить из нее хотя бы одна стрелка;

4) Число стрелок = числу -1;

5) Стрелки не должны образовывать замкнутый контур (при этом неважно, двигаемся мы по стрелкам или против них).

Особый случай транспортной задачи в сетевой постановке проявляется в том, что при полном использовании мощностей поставщиков и полном удовлетворении спроса потребителей число стрелок < n – 1, где n – общее число вершин (в том числе и нулевых). Тогда дополнительно вводится нужное количество стрелок. При этом должны образовывать замкнутый контур.

Задана следующая транспортная сеть:

3

4 2

4 7

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

У поставщиков 1, 4 и 7 есть 190, 30 и 250 единиц груза соответственно. Потребителям 2, 3, 5 и 6 требуется 120, 70, 150 и 130 единиц груза соответственно.

Стоимость перевозки единицы груза от поставщика 1 до потребителя 2 равна 1,стоимость перевозки единицы груза от поставщика 7 до потребителя 5 равна 3 и т. д.

Суммарная мощность поставщиков равна 190 + 30 +250 = 470, суммарный спрос потребителей равен 120 + 70 + 150 + 130 = 470. Это закрытая модель.

3.2.3.2 Первоначальный план поставок

Найдем первоначальный план поставок. Способ расстановки стрелок может быть любым. Важно только выполнение условий 1 – 5. Все поставки указаны стрелками.

3

70

1 30

120 4 2

4 7

3 120

У нас 5 стрелок и 7 вершин. Не выполняется следующее условие:

число стрелок = число вершин – 1, так как 5 = 7 – 1. Введем еще одну стрелку с нулевой поставкой. Например, 1 5. Получим следующий первоначальный план поставок.

0

3

1 30

120 4 2

4 7

3 120

Затраты на перевозку равны 120*1 + 70*3 + 0*2 + 30*2 + 120*3 + 130*7 = 1660

3.2.3.3.Проверка плана поставок на оптимальность

Нужно проверить план поставок на оптимальность. Для этого требуется вычислить потенциалы вершин.

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

1) Если мы двигаемся по стрелке, то к потенциалу вершины прибавляем стоимость перевозки единицы груза по этой стрелке (а не число, которое написано на стрелке);

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

После вычисления потенциалов вершин нужно найти характеристики ребер без стрелок по следующему правилу: стоимость перевозки единицы груза для данного ребра – большой потенциал вершин этого ребра + меньший потенциал вершин этого ребра.

Если нет ребер с отрицательными характеристиками, то получен оптимальный план поставок.

Проверим полученный план на оптимальность. Для вершины 1 принимаем потенциал равный 0. Из вершины 1 в вершину 2 ведет стрелка.

1 1

Стоимость перевозки единицы груза для данного ребра равна 1. Поэтому потенциал вершины 2 равен: потенциал вершины 1 + стоимость перевозки груза по ребру 1→2 (двигается по стрелке):

0 + 1 =1

Из вершины 1 в вершину 5 ведет стрелка. Стоимость перевозки единицы груза для данного ребра равна 2. Поэтому потенциал вершины 5 равен 0 (потенциал вершины 1) + 2 (стоимость перевозки единицы груза по ребру 1→5) = 2

В вершину 5 из вершины 7 ведет стрелка. Стоимость перевозки единиц груза для данного ребра равна 3. Поэтому потенциал вершины 7 равен: потенциал вершины 5 минус стоимость перевозки единицы груза по ребру 7→5 (двигаем против направления стрелки):

Повторяем данную процедуру до тех пор, пока не будут найдены потенциалы всех вершин:

Потенциал вершины 3 = 0 + 3 = 3

Потенциал вершины 4 = 2 – 2 = 0

Потенциал вершины 6 = -1 + 7 = 6

3

1 30

4 7

3 120

Далее находим характеристики ребер без стрелок (их оценки)

Характеристика ребра (1,6) = стоимость перевозки единицы груза для ребра (1,6) + меньший потенциал вершин ребра (1,6) = 4 – 6 + 0 = -2 < 0

Характеристика ребра (2,4) = стоимость перевозки единицы груза для ребра (2,4) – большой потенциал вершин ребра (2,4) + меньший потенциал вершин ребра (2,4) = 7 – 1 + 0 = 6

Характеристики ребра (3,4) = стоимость перевозки единицы груза для ребра (3,4) – большой потенциал вершин ребра (3,4) + меньший потенциал вершин ребра (3,4) = 4 – 3 + 0 =1

Характеристика ребра (4,6) = стоимость перевозки единицы груза для ребра (4,6) – большой потенциал вершин ребра (4,6) + меньший потенциал вершин ребра (4,6) = 3 – 6 + 0 = -3 < 0

Характеристики ребер (4,6) и (1,6) отрицательны, поэтому полученный план поставок не является оптимальным. (на схеме оценки отмечаем зеленым цветом – овал)

3

3.2.3.4. Улучшение плана поставок

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

В нашем случае у ребра (4,6) наименьшая отрицательная характеристика (-3). Рисуем к нему стрелку от вершины с меньшим потенциалом (4) к вершине с большим потенциалом (6).

Образуется замкнутый контур из стрелок 4 – 6 – 7 – 5 – 4 (при этом не важно, двигаемся мы по стрелкам или против них). В этом контуре направление стрелок 7→6 и 4→5 противоположно направлению новой стрелки 4→6.

30

2

3 120

Определяем минимум среди поставок для стрелок этого контура, направление которых противоположно направлению новой стрелки.

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

Определим минимум среди поставок для стрелок 7→6 и 4→5:

Min (30, 130) = 30.

Для контура 4 – 6 – 7 – 5 – 4 поставки на стрелках в направлении новой стрелки 4→6 (4→6 и 7→5) увеличим на этот минимум: 0 + 30 = 30 и 120 + 30 = 150 соответственно.

Для контура 4 – 6 – 7 – 5 – 4 поставки на стрелках 7→6 и 4→5 уменьшим на этот минимум: 130 – 30 = 100 и 30 – 30 = 0 соответственно, то есть стрелку 4→5 ликвидируем.

2

3 150

Поставки для стрелок вне контура остаются без изменений. Число стрелок = 6 = число вершин – 1. Получаем следующий план поставок. Исследуем ее оптимальность.

3

4 7

Припишем вершине 1 потенциал 0 и пересчитаем потенциалы других вершин. У нас четыре ребра без стрелок: (1,6), (2,4), (3,4), (4,5). Найдем их характеристики.

Характеристика ребра (1,6) = стоимость перевозки единицы груза для ребра (1,6) – больший потенциал вершина ребра (1,6) + меньший потенциал вершины ребра (1,6) = 4 – 6 + 0 = -2 < 0.

Характеристика ребра (2,4) = стоимость перевозки единицы груза для ребра (2,4) – больший потенциал вершин ребра (2,4) + меньший потенциал вершин ребра (2,4) = 7 – 3 + 1 = 5.

Характеристика ребра (3,4) = стоимость перевозки единицы груза для ребра (3,4) – больший потенциал вершин ребра (3,4) + меньший потенциал вершин ребра (3,4) = 4 – 3 + 3 = 4.

Характеристика ребра (4,5) = стоимость перевозки единицы груза для ребра (4,5) – больший потенциал вершин ребра (4,5) = 2 – 3 + 2 = 1.

Характеристика ребра (1,6) отрицательна. Поэтому полученный план поставок не является оптимальным. Рисуем к ребру (1,6) стрелку от вершины с меньшим потенциалом (1) к вершине с большим потенциалом (6).

0

3

1 4

120 2

4 7

3 150

30 3

Образуется замкнутый контур из стрелок 1 – 6 – 7 – 5 – 1 (при этом не важно, двигаемся ли мы по стрелкам или против них). В этом контуре направление стрелок 7→6 и 1→5 противоположно направлению новой стрелки 1→6.

Определим минимум среди поставок для стрелок 7→6 и 1→5: min (100, 0) = 0. Поэтому все поставки остаются без изменений. Стрелку 1→5 ликвидируем.

Число стрелок = 6 = число вершин – 1. Получаем следующий план поставок. Проверим его на оптимальность.

1 4

120 2

4 7

Убеждаемся, что нет ребер с отрицательными характеристиками, то есть это оптимальный план поставок. Затраты на перевозку равны 120*1 + 70*3 + 0*4 + 30*3 + 150*3 + 100*7 = 1570.

Открытая модель

Открытая модель сводится к закрытой модели.

Фиктивный потребитель

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

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

7

6 5

Суммарная мощность поставщиков равна 40 + 60 + 50 = 150. Суммарный спрос потребителей равен 40 + 60 + 30 = 130. Это открытая модель.

Вводим фиктивного потребителя, которому припишем спрос 150 – 130 = 20. Это будет вершина 7. Соединим ее с вершинами 1, 3, 6 (поставщики).

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

7

4

8 25 6

6 5 25

Фиктивный поставщик

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

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

7 6

11

8 5 9

7

2

Суммарная мощность поставщиков равна 40 + 30 + 10 = 80. Суммарный спрос потребителей равен 20 + 50 + 30 = 100. Это открытая модель.

Вводим фиктивного поставщика, которому припишем мощность 100 – 80 = 20. Это будет вершина 7. Соединим ее с вершинами 1, 3, 6 (потребители).

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

7 6

25 11

Задания к контрольной работе по теме «Транспортная задача в сетевой постановке».

-20	-35	-80	-30	-15	-30	-40	-70	-50	-20	-25	-50	-75	-80	-20
-35	-20	-50	-35	-40	-30	-30	-40	-40	-30	-25	-30	-30	-20	-30
-30	-20	-70	-50	-50	-30	-25	-20	-35	-5	-25	-50	-30	-30	-40
-30	-20	-30	-5	-10	-25	-30	-40	-50	-95	-25	-35	-40	-40	-30
						&n ⇐ Предыдущая15161718192021222324Следующая ⇒ Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычис­лить, когда этот... Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: