Консультация онлайн # 202212

Раздел: Исследование операций
Автор вопроса: kabanov.anton2010 (Посетитель)
Дата: 22.02.2022, 10:51 Консультация неактивна
Поступило ответов: 1
Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос:
На три базы А1, А2, А3 поступил однородный груз в количестве а1 т. на базу А1, а2 т. на базу А2, а3 т. на базу А3. Полученный груз требуется перевезти в пять пунктов: в1 т. в пункт В1, в2 т. в пункт В2, в3 т. в пункт В3, в4 т. в пункт В4, в5 т. в пункт В5.
Стоимость перевозок пропорциональна расстоянию и количеству перевозимого груза. Матрица тарифов и значения а1, а2, а3 и в1, в2, в3, в4, в5 – известны. Требуется записать модель и спланировать перевозки так, чтобы их общая стоимость была минимальной.
a1=280;a2=300;a3=220
B1=170;b2=120;b3=190;b4=140;b5=180


C=(28 12 7 18 7)
35 14 12 15 3
30 16 11 25 15
Вопрос перенесен из раздела Математика
1. Транспортная модель будет иметь следующий вид: требуется составить план перевозок x = (x11, x12,..., x15, x21,..., x25, x31,..., x35), удовлетворяющий условиям


и минимизирующий целевую функцию


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

2. Метод наименьших стоимостей состоит в следующем:
выбираем перевозку с наименьшей стоимостью (если таких несколько, выбираем любую);
определяем максимально возможную отгрузку как минимум из величины потребности соответствующего потребителя и запаса соответствующего поставщика;
уменьшаем потребность и запас на величину отгрузки;
если потребность стала равна нулю, то исключаем соответствующего потребителя из дальнейшего рассмотрения;
аналогично, если запас стал равен нулю, то исключаем соответствующего поставщика;
повторяем для оставшихся потребителей и поставщиков, пока не будут распределены все запасы и удовлетворены все потребности.
Метод удобно реализовать в виде таблицы, которая в данном случае будет иметь следующий вид:
28127187280
351412153300
3016112515220
170120190140180800
Здесь правый столбец содержит запасы, нижняя строка - потребности, нижняя правая клетка - общий баланс, остальные клетки - стоимость перевозок. Наименьшая стоимость перевозки в таблице равна 3 (клетка 2:5). Потребность равна 180, запас - 300, поэтому отгрузка будет равна min(180,300)=180.
28127187280
351412153300
3016112515220
170120190140180800
Потребность потребителя 5 стала равна 180-180=0, запас поставщика 2 стал равен 300-180=120, поэтому исключаем из дальнейшего рассмотрения пятый столбец (соответствующую потребителю 5).
28127187280
351412153*180120
3016112515220
1701201901400620
В оставшейся части таблицы наименьшая стоимость перевозки будет равна 7 (клетка 1:3). Потребность равна 190, запас - 280, поэтому отгрузка будет равна min(190,280)=190.
28127187280
351412153*180120
3016112515220
1701201901400620
Потребность потребителя 3 стала равна 190-190=0, запас поставщика 1 стал равен 280-190=90, поэтому исключаем из дальнейшего рассмотрения третий столбец.
28127*19018790
351412153*180120
3016112515220
17012001400430
Дальше действуем аналогично: клетка 1:2 (стоимость 12) с отгрузкой min(120,90)=90 и исключением первого поставщика
2812*907*1901870
351412153*180120
3016112515220
1703001400340
клетка 2:2 (стоимость 14) с отгрузкой min(30,120)=30 и исключением второго потребителя
2812*907*1901870
3514*3012153*18090
3016112515220
170001400310
клетка 2:4 (стоимость 15) с отгрузкой min(140,90)=90 и исключением второго поставщика
2812*907*1901870
3514*301215*903*1800
3016112515220
17000500220
для единственного оставшегося поставщика 3 отгрузки выбираются однозначно
2812*907*1901870
3514*301215*903*1800
30*170161125*50150
000000
Все строки и столбцы исключены (то есть оставшиеся потребности и запасы равны нулю), следовательно, опорный план построен верно. Вычислим общую стоимость перевозок:


3. Метод потенциалов для оптимизации опорного решения выглядит следующим образом:
всем поставщикам i и потребителям j ставим в соответствие некоторые значения ui и vj, называемые потенциалами. Один из потенциалов задаём (например, u1=0), остальные определяем исходя из того, что для стоимости cij поставки, входящей в опорное решение, должно выполняться равенство cij=ui+vj;
находим для всех поставок оценки по формуле ?ij=cij-(ui+vj). Для поставок, входящих в опорное решение, они будут нулевые, для остальных могут отличаться от нуля;
если нет отрицательных оценок, то текущее решение является оптимальным, и оптимизация заканчивается;
в противном случае выбираем ячейку с наименьшей оценкой (то есть с максимальной по абсолютной величине отрицательной оценкой;
начиная с выбранной ячейки, строим в таблице замкнутый цикл, содержащий ячейки опорного решения;
обходим ячейки цикла в произвольном порядке, помечая их по очереди как "положительные" и "отрицательные" (выбранная ячейка с наименьшей оценкой помечается как "положительная");
находим минимальное значение величины поставки для всех "отрицательных" ячеек;
уменьшаем на эту величину объёмы поставок для всех "отрицательных" ячеек цикла и увеличиваем - для всех "положительных";
получаем новое опорное решение, для которого повторяем всё сначала.

Используем метод потенциалов для оптимизации полученного опорного решения:
2812*907*190187280
3514*301215*903*180300
30*170161125*5015220
170120190140180800
Вычислим потенциалы:
u1=0;
c12=u1+v2=12v2=12-0=12;
c13=u1+v3=7v4=7-0=7;
c22=u2+v2=14u2=14-12=2;
c24=u2+v4=15v4=15-2=13;
c25=u2+v5=3v5=3-2=1;
c34=u3+v4=25u3=25-13=12;
c31=u3+v1=30v1=30-12=18
добавим их в таблицу:
2812*907*1901872800
3514*301215*903*1803002
30*170161125*501522012
170120190140180800
18127131
найдём оценки поставок:
Δ11=c11-(u1+v1)=28-(0+18)=10;
Δ14=c14-(u1+v4)=18-(0+13)=5;
Δ15=c15-(u1+v5)=7-(0+1)=7;
Δ21=c21-(u2+v1)=35-(2+18)=15;
Δ23=c23-(u2+v3)=12-(2+7)=3;
Δ32=c32-(u3+v2)=16-(12+12)=-8;
Δ33=c33-(u3+v3)=11-(12+7)=-8;
Δ35=c35-(u3+v5)=15-(12+1)=2
(остальные равны 0) и добавим их в таблицу (для ячеек, не входящих в опорное решение):
28/1012*907*19018/57/7280
35/1514*3012/315*903*180300
30*17016/-811/-825*5015/2220
170120190140180800
(значения потенциалов больше не требуются). Отрицательную оценку (-8) содержат две ячейки - 3:2 и 3:3. Выберем любую, например 3:2. Вместе с ячейками 2:2, 2:4 и 3:4 она образует замкнутый цикл, в котором ячейки 3:2 и 2:4 - "положительные", а 2:2 и 3:4 - "отрицательные":
28/1012*907*19018/57/7280
35/1514*3012/315*903*180300
30*17016/-811/-825*5015/2220
170120190140180800
Среди "отрицательных" ячеек наименьшее значение поставки достигается в 2:2 (30). Уменьшаем на 30 объём поставок для ячеек 2:2 и 3:4, увеличиваем на 30 объём поставок для ячеек 3:2 и 2:4. Получаем новое опорное решение:
2812*907*190187280
35141215*1203*180300
30*17016*301125*2015220
170120190140180800
и вычисляем новую стоимость перевозок:

Можно заметить, что по сравнению с исходным опорным решением стоимость изменилась на величину -240 = -8·30, равную произведению оценки выбранной ячейки (-8) на величину изменения объёмов поставок для ячеек цикла (30).
Вычислим потенциалы:
u1=0;
c12=u1+v2=12v2=12-0=12;
c13=u1+v3=7v3=7-0=7;
c32=u3+v2=16u3=16-12=4;
c31=u3+v1=30v1=30-4=26;
c34=u3+v4=25v4=25-4=21;
c24=u2+v4=15u2=15-21=-6;
c25=u2+v5=3v5=3-(-6)=9
добавим их в таблицу
2812*907*1901872800
35141215*1203*180300-6
30*17016*301125*20152204
170120190140180800
26127219
найдём ненулевые оценки поставок:
Δ11=c11-(u1+v1)=28-(0+26)=2;
Δ14=c14-(u1+v4)=18-(0+9)=9;
Δ15=c15-(u1+v5)=7-(0+9)=-2;
Δ21=c21-(u2+v1)=35-(-6+26)=15;
Δ22=c22-(u2+v2)=14-(-6+12)=8;
Δ23=c23-(u2+v3)=12-(-6+7)=11;
Δ33=c33-(u3+v3)=11-(4+7)=0;
Δ35=c35-(u3+v5)=15-(4+9)=2
и добавим их в таблицу:
28/212*907*19018/97/-2280
35/1514/812/1115*1203*180300
30*17016*3011/025*2015/2220
170120190140180800
Отрицательную оценку (-2) содержит ячеёка 1:5. Вместе с ячейками 1:2, 3:2, 3:4, 2:4 и 2:5 она образует замкнутый цикл, в котором ячейки 1:5, 3:2 и 2:4 - "положительные", а 1:2, 3:4 и 2:5 - "отрицательные":
28/212*907*19018/97/-2280
35/1514/812/1115*1203*180300
30*17016*3011/025*2015/2220
170120190140180800
Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 3:4. Уменьшаем на 20 объём поставок для ячеек 1:2, 3:4 и 2:5, увеличиваем на 20 объём поставок для ячеек 1:5, 3:2 и 2:4. Получаем новое опорное решение:
2812*707*190187*20280
35141215*1403*160300
30*17016*50112515220
170120190140180800
и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u1=0;
c12=u1+v2=12v2=12-0=12;
c13=u1+v3=7v3=7-0=7;
c15=u1+v5=7v5=7-0=7;
c25=u2+v5=3u2=3-7=-4;
c24=u2+v4=15v4=15-(-4)=19;
c32=u3+v2=16u3=16-12=4;
c31=u3+v1=30v1=30-4=26;
добавим их в таблицу
2812*707*190187*202800
35141215*1403*160300-4
30*17016*501125152204
170120190140180800
26127197
найдём ненулевые оценки поставок:
Δ11=c11-(u1+v1)=28-(0+26)=2;
Δ14=c14-(u1+v4)=18-(0+19)=-1;
Δ21=c21-(u2+v1)=35-(-4+26)=13;
Δ22=c22-(u2+v2)=14-(-4+12)=6;
Δ23=c23-(u2+v3)=12-(-4+7)=9;
Δ33=c33-(u3+v3)=11-(4+7)=0;
Δ34=c34-(u3+v4)=25-(4+19)=2;
Δ35=c35-(u3+v5)=15-(4+9)=2
и добавим их в таблицу:
28/212*707*19018/-17*20280
35/1314/612/915*1403*160300
30*17016*5011/025/215/2220
170120190140180800
Отрицательную оценку (-1) содержит ячеёка 1:4. Вместе с ячейками 2:4, 2:5 и 3:5 она образует замкнутый цикл, в котором ячейки 1:4 и 2:5 - "положительные", а 2:4 и 1:5 - "отрицательные":
28/212*707*19018/-17*20280
35/1314/612/915*1403*160300
30*17016*5011/025/215/2220
170120190140180800
Среди "отрицательных" ячеек наименьшее значение поставки (20) достигается в 1:5. Уменьшаем на 20 объём поставок для ячеек 1:5 и 2:4, увеличиваем на 20 объём поставок для ячеек 1:4 и 2:5. Получаем новое опорное решение:
2812*707*19018*207280
35141215*1203*180300
30*17016*50112515220
170120190140180800
и вычисляем новую стоимость перевозок:

либо как

Для нового решения вычислим потенциалы:
u1=0;
c12=u1+v2=12v2=12-0=12;
c13=u1+v3=7v3=7-0=7;
c14=u1+v4=18v4=18-0=18;
c24=u2+v4=15u2=15-18=-3;
c25=u2+v5=3v5=3-(-3)=6;
c32=u3+v2=16u3=16-12=4;
c31=u3+v1=30v1=30-4=26;
добавим их в таблицу
2812*707*19018*2072800
35141215*1203*180300-3
30*17016*501125152204
170120190140180800
26127186
найдём ненулевые оценки поставок:
Δ11=c11-(u1+v1)=28-(0+26)=2;
Δ15=c15-(u1+v5)=7-(0+5)=2;
Δ21=c21-(u2+v1)=35-(-3+26)=12;
Δ22=c22-(u2+v2)=14-(-3+12)=5;
Δ23=c23-(u2+v3)=12-(-3+7)=8;
Δ33=c33-(u3+v3)=11-(4+7)=0;
Δ34=c34-(u3+v4)=25-(4+18)=3;
Δ35=c35-(u3+v5)=15-(4+6)=5.
Отрицательных оценок нет, следовательно, последнее решение со стоимостью 10770 является оптимальным. Соответствующий план перевозок можно записать как

Последнее редактирование 27.02.2022, 20:13 Коцюрбенко Алексей Владимирович (Старший модератор)


Коцюрбенко Алексей Владимирович

Старший модератор
27.02.2022, 17:59
5

Мини-форум консультации # 202212

Коцюрбенко Алексей Владимирович

Старший модератор

ID: 312929

324575

= общий =    25.02.2022, 03:11
Экспертам раздела
Обратите внимание на консультацию, перенесённую из другого раздела
Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.