Решение транспортных задач методами линейного программирования

Автор работы: Пользователь скрыл имя, 12 Февраля 2013 в 23:18, реферат

Краткое описание

Транспортная задача закрытого типа без ограничений пропускной способности, представленная в матричной форме
На 4 станциях имеется избыток пустых вагонов в размере соответственно 100, 120, 150 и 50 вагонов. Необходимо распределить данные вагоны по 7 станциям с недостатком порожняка (соответственно 70, 50, 60, 30, 50, 70 и 90 вагонов).

Вложенные файлы: 1 файл

transport.doc

— 1.63 Мб (Скачать файл)

Все строки в зависимости  от знака разности классифицируются на избыточные и недостаточные. Строка считается абсолютно избыточной, если Ri > 0 и абсолютно недостаточной, если Ri < 0. Строки, где Ri = 0 классифицируются на относительно избыточные и относительно недостаточные, согласно пункту 1 примечаний к данному алгоритму решения. В примере первая и вторая строки абсолютно избыточные, а третья, четвертая и пятая строки абсолютно недостаточные.

Корректировка матрицы стоимостей. Эта корректировка включает в  себя следующие действия:

а) в каждом столбце, имеющем  поставку в недостаточной строке определяется клетка с минимальной стоимостью в избыточной строке minCijизб. Например, в первом столбце, в недостающих строках поставок нет, поэтому такая клетка не определяется. Во втором столбце – это будет клетка А2В2 с себестоимостью minC22изб= min{40; 30} = 30 руб./т. В третьем столбце – клетка А2В3 с себестоимостью minC23изб= min{90; 45} = 45 руб./т. В четвертом столбце – клетка А2В4, в пятом не определяется, в шестом – клетка А2В6 и в седьмом – клетка А2В7;

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

Cijзан(-)  по формуле  (16)

 

 

Для первого  столбца D 1 не определяется из-за отсутствия minCijизб, для второго столбца D 2 = 30 – 25 = 5, для третьего – D 3 = 45 – 10 = 35 и т.д. Значения D j фиксируются во вспомогательной строке матрицы перевозок (см. табл.17);

в) определяется наименьшее значение из всех D j (D = min D j), которое прибавляется ко всем стоимостям во всех клетках недостающих строк (в том числе и в столбцах, где D j не определялось). Для плана перевозок, представленного в табл. 17, D = min{5;35;20;35;10} = 5. Получаем новую скорректированную матрицу стоимостей (табл.18).

5. Определяются связи между строками, возникшие в результате преобразования матрицы стоимостей в пункте 4 данного алгоритма.

Строка s считается  связанной с другой строкой при  соблюдении следующих двух условий:

а) в каком-либо столбце k имеется совпадение стоимостей, Csk = Cik;

б) в клетке sk имеется поставка xsk >0.

Связь строк  указывает возможное направление  переноса поставки, так как в результате корректировки матрицы стоимостей выравниваются стоимости в клетках связанных строк и в матрице появляется новая допустимая клетка с минимальной стоимостью в столбце. Так, после корректировки стоимостей, во втором столбце они выравнялись в клетках А2В2 и А4В222 = С42 = 30).

6. Через клетки с выравненными стоимостями строится замкнутый контур от избытка в избыточной строке до недостатка в недостаточной строке. В табл. 17 такая цепь показана пунктирной линией.

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

D x = min {Rнач; Rкон; Хijнеч },              (17)

где Rнач – избыток в избыточной строке, с которой начинается контур переноса; Rкон – недостаток в недостаточной строке, с которой заканчивается контур переноса; Хijнеч – поставки в нечетных вершинах построенного контура.

Для плана перевозок, представленного в табл. 17 Dx=min{20;30;90} = 20.

8. Осуществляется перенос выбранного значения D x и корректируются поставки в матрице перевозок. Для этого найденное значение D x вычитается от цифровых значений в нечетных вершинах контура и прибавляется к цифровым значениям в четных вершинах. В результате получается новый скорректированный план перевозок (табл.18). Далее выполняются пункты 1–8 алгоритма решения задачи методом условно-оптимальных планов. Согласно пункту 2 алгоритма в новом скорректированном плане перевозок имеются строки с разнозначными разностями Ri, следовательно расчеты необходимо продолжить (табл. 19–21).

Примечания:

При классификации  строк на избыточные и недостаточные в таблице могут встретиться нулевые строки (например, вторая строка в табл.18). Для определения знака таких строк находится связь с какой-либо из строк через клетки с выравненными стоимостями и нулевой строке присваивается наименование относительно избыточной или относительно недостаточной в зависимости от того, с какой строкой обнаружится связь. В примере вторая строка табл.19 является относительно недостаточной, так как имеется её связь с четвертой строкой посредством клеток А2В2 – А4В2 .

Относительно  недостаточные строки могут в следующем плане перевозок оказаться относительно избыточными и наоборот. В табл.19 вторая строка стала относительно избыточной, так как имеется её связь через занятые клетки А1В5 – А2В5 с абсолютно избыточной первой строкой, четвертая строка является относительно избыточной из-за её связи с относительно избыточной второй строкой посредством А2В2 – А4В2.

При построении замкнутого контура его очертания  могут не повторять очертания  прямоугольника, т.е. иметь более  четырех вершин. Например, в табл.18 контур был построен исходя из того, что кроме новой связи А1В5 – А2В5 сохранилась и старая связь через клетки с выравненными себестоимостями А2В2 – А4В2.

 

Таблица 18

Скорректированный план перевозок  (первая корректировка) 

 

Для плана перевозок, представленного в табл. 18

 

D = min{70; 10; 75; 75; 5; 40; 55} = 5; D x = min {200; 150; 70; 10} = 10.

 

 

 

 

 

 

 

 

 

 

Таблица 19

Скорректированный план перевозок (вторая корректировка)

Для плана перевозок, представленного  в табл. 19,

D = min{5; 20; 5} = 5; D x = min {190; 140; 150; 80} = 80.

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 20

Скорректированный план перевозок (третья корректировка)

Для плана перевозок, представленного  в табл. 20, D = min{15} = 15; D x = min {110; 60; 60; 160; 60} = 60.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Таблица 21

Скорректированный план перевозок (четвертая корректировка)

Станция

отправления

Ресурсы,

тыс. т

Станция назначения

Ri

(избыток, недостаток)

В1

В2

В3

В4

В5

В6

В7

Объем потребления, тыс. т

80

90

190

130

150

160

150

А1

200

80

40

90

100

35

150

75

80

+50

А2

250

15

80

35

90

50

45

35

70

35

80

+0

А3

100

50

65

90

90

110

60

100

100

+0

А4

250

50

35

20

190

35

75

60

60

70

+0

А5

200

30

65

35

35

130

55

95

35

70

+0




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

 

 

 

 

 

 

 

 

 

Таблица 22

Конечный план перевозок

Станция

отправления

Ресурсы,

тыс. т

Станция назначения

Ri

(избыток, недостаток)

В1

В2

В3

В4

В5

В6

В7

Объем потребления, тыс. т

80

90

190

130

150

160

150

А1

200

80

40

90

100

35

50

75

80

 

А2

250

10

80

30

90

45

40

30

65

30

80

 

А3

100

20

35

60

60

80

30

100

70

 

А4

250

40

25

10

90

25

65

50

60

60

 

А5

200

15

50

20

20

130

40

80

20

70

 

Конечное значение целевой функции (суммарная себестоимость  перевозок конечного плана) составит

Cкон = f (x) =150· 35 + 80· 10 + 90· 30 + 80· 30 + 100· 30 + 190· 10 + 60· 50 + 130· 20 + 70· 20 = 23050 тыс. руб.

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

Так как методом  потенциалов можно решать только транспортные задачи закрытого типа, данную транспортную задачу открытого типа необходимо привести к закрытому виду. Для этого вводится дополнительный фиктивный потребитель Bфикт с объемом потребления равным = 1000 – 950 = 50 тыс./т.

 

 

Себестоимость перевозок в клетках, связанных  с фиктивным потребителем, принимается равной нулю (табл.23).

 

Таблица 23

Проверка решения  методом потенциалов

Станция

отправления

Ресурсы,

тыс. т

Станция назначения

 

В1

В2

В3

В4

В5

В6

В7

Вфикт

Ui

Объем потребления, тыс. т

 

80

90

190

130

150

160

150

50

 

А1

200

80

40

90

100

35

150

75

80

0

50

100

А2

250

10

80

30

90

45

40

30

0

65

0

30

80

0

105

А3

100

20

35

60

60

80

30

100

70

0

140

А4

250

40

25

10

190

25

65

50

60

60

0

120

А5

200

15

50

20

20

130

40

80

20

70

0

115 

Vj

115

135

130

135

135

170

135

100

 

Информация о работе Решение транспортных задач методами линейного программирования