Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры)




НазваниеРеферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры)
страница1/5
Дата публикации30.06.2013
Размер0.91 Mb.
ТипРеферат
zadocs.ru > Спорт > Реферат
  1   2   3   4   5


Национальный Технический Университет Украины «КПИ»

Реферат

Тема: РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ МЕТОДАМИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ.
Часть II (примеры)
Выполнил: Дрюк Я.А.

Проверил: Яганов П.О.


КИЕВ 2001

ОГЛАВЛЕНИЕ





ОГЛАВЛЕНИЕ 2

Пример № 1. 2

Транспортная задача закрытого типа без ограничений пропускной способности, представленная в матричной форме 2

Пример № 2. 8

Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности 8

Пример № 3. 10

Транспортная задача закрытого типа, представленная в матричной форме, с ограничениями пропускной способности 10

Пример № 4. 14

Транспортная задача открытого типа, представленная в матричной форме без ограничений пропускной способности 14

Пример № 5. 22

ЛИТЕРАТУРА 30
^

Пример № 1.

Транспортная задача закрытого типа без ограничений пропускной способности, представленная в матричной форме


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

Таблица 1

Исходные данные транспортной задачи

Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

23

28

13

12

16

21

X1,5

X1,6

X1,7

X1,8

X1,9

X1,10

X1,11

2

120

24

17

24

11

11

12

18

X2,5

X2,6

X2,7

X2,8

X2,9

X2,10

X2,11

3

150

8

19

16

18

9

17

15

X3,5

X3,6

X3,7

X3,8

X3,9

X3,10

X3,11

4

50

12

28

18

16

21

20

25

X4,5

X4,6

X4,7

X4,8

X4,9

X4,10

X4,11

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

Это задача закрытого типа, так как суммарное количество избыточных пустых вагонов равно суммарному количеству требующихся вагонов (420 = 420).

Математическая модель задачи будет представлена следующим образом.

Целевая функция (суммарный пробег пустых вагонов) определяется по формуле:


Система ограничений

где ai – ресурсы i-й станции отправления; bj – потребность j-й станции назначения.

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

^ Методы построения исходного опорного плана перевозок

Исходный опорный план перевозок может быть построен различными методами. Здесь приводятся наиболее распространенные из них.

Метод северо-западного угла (диагональный). Построение начального опорного плана начинается с левой верхней клетки (называемой северо-западным углом) матрицы и продолжается, двигаясь далее вправо по строке и вниз по столбцу (табл. 2).

Таблица 2

Исходный опорный план, построенный методом северо-западного угла

Станция отправления



Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

70

23

30

28

13

12

16

21

2

120

24

17

20

24

60

11

30

11

10

12

18

3

150

8

19

16

18

9

40

17

70

15

40

4

50

12

28

18

16

21

20

25

50

Значение целевой функции составит

L = 15·70 + 23· 30 + 17· 20 + 24· 60 + 11· 30 + 11· 10 + 9· 40 + 17· 70 + 15 · 40 +  25· 50 = = 7360 ваг-км

Метод минимального элемента. Построение начального опорного плана начинается с клетки, имеющей минимальное расстояние перевозки в таблице. Эта клетка исключается из дальнейшего рассмотрения матрицы, потом заполняется клетка с очередным минимальным элементом и т.д. (табл. 3).

Таблица 3

Исходный опорный план, построенный методом “минимального элемента”

Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

23

30

28

10

13

12

16

21

60

2

120

24

17

20

24

11

30

11

12

70

18

3

150

8

70

19

16

18

9

50

17

15

30

4

50

12

28

18

50

16

21

20

25

Значение целевой функции составит

L = 23· 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8 · 70 + 9· 50 + 15· 30 +  18· 50 = 6100 ваг-км.

Метод наименьшего критерия в столбце. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в столбце и далее по столбцу (табл. 4).

Таблица 4

Исходный опорный план, построенный методом наименьшего критерия в столбце


Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

23

28

13

12

16

60

21

40

2

120

24

17

50

24

11

30

11

30

12

10

18

3

150

8

70

19

16

60

18

9

20

17

15

4

50

12

28

18

16

21

20

25

50

Значение целевой функции составит

L = 16· 60 + 21· 40 + 17· 50 + 11· 30 + 11· 30 + 12· 10 + 8· 70 + 16· 60 + 9· 20 +  25· 50 = 6380 ваг-км.

Метод наименьшего критерия в строке. Построение начального опорного плана начинается с клетки с минимальным расстоянием перевозки в строке и далее по строке (табл. 5).

Таблица 5

Исходный опорный план, построенный методом наименьшего критерия в строке

Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

20

23

28

13

30

12

50

16

21

2

120

24

17

50

24

11

11

12

70

18

3

150

8

50

19

16

10

18

9

17

15

90

4

50

12

28

18

50

16

21

20

25

Значение целевой функции составит

L = 15· 20 + 13· 30 + 12· 50 + 17· 50 + 12· 70 + 8· 50 + 16· 10 +15· 90 + 18· 50 =  5790 ваг-км.

Метод двойного предпочтения. Сначала просматривают все строки матрицы и в каждой из них (строк) отмечают элемент с минимальной стоимостью (*). Затем просматривают столбцы и также отмечают в них элемент с минимальной стоимостью (+). В клетки с двумя знаками помещают максимально возможные перевозки. Затем заполняются клетки, отмеченные один раз и клетки с возможно меньшей стоимостью (табл. 6).

Таблица 6

Исходный опорный план, построенный методом двойного предпочтения

Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

23

30

28

10

13

12 *

16

21

60

2

120

24

17 +

20

24

11 *+

30

11 *

12 +

70

18

3

150

8 * +

70

19

16 +

18

9 +

50

17

15 +

30

4

50

12 *

28

18

50

16

21

20

25

Значение целевой функции составит

L = 23· 30 + 28· 10 + 21· 60 + 17· 20 + 11· 30 + 12· 70 + 8· 70 + 9· 50 + 15· 30 + 18· 50 = 6100 ваг-км.

Более подробно эти методы рассмотрены в.

Как видно из приведенных расчетов наименьшее значение целевой функции (суммарный пробег пустых вагонов) получено при построении начального опорного плана методом наименьшего критерия в строке (L = 5790 ваг-км). Так как целью данной задачи является получение минимального суммарного пробега пустых вагонов, то для дальнейшего рассмотрения выбирается исходный опорный план, построенный именно этим методом.

Наиболее известным методом решения транспортных задач закрытого типа является метод потенциалов, разработанный академиками Л.А. Канторовичем и М.В. Говуриным.
Алгоритм решения транспортной задачи закрытого типа, представленной в матричной форме, без ограничений пропускной способности методом потенциалов

1. Исходный опорный план проверяется на условие «вырождения».

Согласно теореме Данцига количество занятых клеток в оптимальном плане не должно превышать суммарного числа строк и столбцов (суммы количества пунктов отправления и назначения):

Кз = m + n – 1 ,              (6)

где Кз – число занятых клеток; m – число строк матрицы (пунктов отправления); n – число столбцов (пунктов назначения).
Естественно, этому же условию должен отвечать исходный опорный план. Если это условие не выполняется, то исходный опорный план составлен неверно.
Если Кз = m + n – 1 , задача решается обычным порядком.
Если Кз < m + n – 1 , задача называется «вырожденной» и распадается на несколько самостоятельных задач. Чтобы этого избежать, назначаются дополнительные фиктивные перевозки (перевозки равные 0). В нашем примере условие «вырождения» выполняется во всех случаях (Кз ?  10), однако, в случае построения начального опорного плана методом наименьшего критерия в строке, задача является «вырожденной» (9<10). Для устранения “вырождения” назначаем фиктивную перевозку в клетку на пересечении строки 2 и столбца 9 (табл. 7). Теперь количество занятых клеток равно сумме строк и столбцов.

Таблица 7

Скорректированный исходный опорный план, построенный методом наименьшего критерия в строке

Станция отправления

Избыток пустых вагонов

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

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

20

23

28

13

30

12

50

16

21

2

120

24

17

50

24

11

11

0

12

70

18

3

150

8

50

19

16

10

18

9

17

15

90

4

50

12

28

18

50

16

21

20

25

2. Одной из строк присваивается произвольный потенциал. Удобнее всего начать со строки, имеющей наибольшее число занятых клеток, а величину потенциала выбрать больше, чем любое расстояние (или другой показатель критерия оптимизации) в матрице условий.
^ Экономическая сущность метода потенциалов. Предположим, что в каком-либо пункте отправления, например “1”, стоимость единицы продукции равняется 100 условным единицам. Тогда в пунктах потребления “5”, “8”, “9” стоимость единицы продукции, с учетом стоимости перевозки, будет соответственно равна 100 + 15 = 115, 100 + 13 =113, 100 + 12 =112 условным единицам. Пункт потребления “5” также “связан” с пунктом производства “3” (табл. 8), поэтому он может получать продукцию по своей цене. Тогда стоимость продукции в пункте “3”, с учетом стоимости доставки, будет составлять 115 – 8 = 107 условных единиц и т.д. Стоимости, найденные таким образом для всех пунктов, носят условный характер и называются потенциалами. В дальнейшем, потенциалы строк будут обозначаться Ui , а потенциалы столбцов – Vj.

В примере присваивается потенциал первой строке U1 = 100 (табл.8).

Таблица 8

План перевозок пустых вагонов (начальный)

 

Начальное значение целевой функции составит

Lнач = 15· 20 + 13· 30 + 12· 50 + 17· 50 + 11· 0 + 12· 70 + 8· 50 + 16· 10 +15· 90 +  18· 50 = 5790 ваг-км.

3. Через занятые клетки определяются потенциалы столбцов, связанных с первой строкой по формуле

Vj = Ui + cij,                             (7)

где cij – критерий расстояния (или другой показатель критерия оптимизации) в заданной клетке.

4. Через занятые клетки определяются потенциалы строк, связанных со столбцами, получившими потенциал, по формуле

Ui = Vj - cij.                             (8)

5. Пункты 3 и 4 повторяются до тех пор, пока все столбцы и строки не получат потенциал. Это всегда возможно, если выполняется условие «вырождения» Кз = m + n - 1. Клетки с фиктивными перевозками рассматриваются как занятые.

6. Проверка на оптимальность. План считается оптимальным, если соблюдаются следующие условия:

Vj - Ui  cij, при xij = 0 (клетка свободна),                     (9)

Vj - Ui = cij, при xij > 0 (в клетке назначена перевозка).

В табл. 8 для клетки (1,11) 122 – 100 = 22 >21, т.е. нарушение в данной клетке составляет 1. Для клетки (2, 8) 113 – 101 = 12 >11, нарушение 1. Аналогично, в клетке (2,11) нарушение составляет 3 (122 – 101 = = 21 > 18). Для остальных свободных и занятых клеток условия оптимальности [см. формулу (9)] выполняются. Результаты проверки приведены в табл.8. Так как в матрице перевозок имеются нарушения условий оптимальности, данный начальный опорный план не является оптимальным. Он может быть улучшен за счет клеток с нарушениями. Рекомендуется выбирать клетки с наибольшим нарушением, хотя это не гарантирует упрощения решения. В данном примере можно выбрать клетку (2,11) с нарушением

^ Формальное правило улучшения плана:

а) начиная с клетки, имеющей нарушение, ходом “шахматной ладьи” строится замкнутый контур с вершинами в занятых клетках;

б) начиная с клетки, имеющей нарушение, нумеруются вершины контура (направление обхода контура значения не имеет). Вершине в клетке (2,11) присваивается номер 1, в клетке (3,11) – номер 2, в клетке (3,5) – номер 3, (1,5) – 4, (1,9) – 5, (2,9) – 6;

в) в четных вершинах находится минимальная перевозка: min {90;20;0} = 0 в вершине (2,9);

г) для балансировки матрицы в нечетные клетки найденное значение прибавляется, из четных – вычитается. Получается новый, улучшенный план (табл.9). При этом значение целевой функции составит

L = 15· 20 + 13·30 + 12· 50 + 17· 50 + 12· 70 +18· 0 + 8· 50 + 16· 10 +15· 90 +  18· 50 = 5790 ваг-км.Значение целевой функции осталось неизменным, так как по контуру была перенесена фиктивная перевозка, равная 0.

Таблица 9

План перевозок пустых вагонов (первая корректировка)

Для нового плана перевозок (табл.9) повторяются пункты 1 – 6 алгоритма решения методом потенциалов. Условие “вырождения” [см. формулу (6)] в новой матрице (табл.9) выполняется. Присваиваются потенциалы всем строкам и столбцам [см. формулы (7) и (8)]. Как видно из табл.8 и 9 изменились потенциалы во 2-й строке и в 6-м и 10-м столбцах. Проверяется новая матрица на условие оптимальности [см. формулу (9)]. В новой матрице нарушение имеется только в одной клетке (1,11) и равно 122 – 100 = 22 > 21. Строится новый контур (1,11) – (3,11) – (3,5) – (1,5). Присваиваются номера вершинам контура и определяется минимальная перевозка в четных вершинах. Это будет min {20; 90} = 20 в вершине (1,5). Данная перевозка переносится по контуру.

Таблица 10

Оптимальный план перевозок пустых вагонов

Станция

отправления

Избыток

пустых

вагонов

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

Ui

5

6

7

8

9

10

11

Недостаток пустых вагонов

70

50

60

30

50

70

90

1

100

15

23

28

13

30

12

50

16

21

20

100

2

120

24

17

50

24

11

11

12

70

18

0

103

3

150

8

70

19

16

10

18

9

17

15

70

106

4

50

12

28

18

50

16

21

20

25

104

Vj

114

120

122

113

112

115

121

 

Полученный новый план перевозок (табл.10) имеет конечное значение целевой функции

Lкон = 13· 30 + 12· 50 + 21· 20 + 17· 50 + 12· 70 + 18· 0 + 8· 70 + 16· 10 + 15· 70 +  18· 50 = 5770 ваг-км.

Проверяем новый план перевозок (табл.10) согласно пунктам 1– 6 алгоритма решения методом потенциалов.

Условие “вырождения” [см. формулу (6)] выполняется. После присвоения потенциалов всем столбцам и строкам новой матрицы (табл.10) нарушений условия оптимальности [см. формулу (9)] нет, значит данный план перевозок является оптимальным.

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

2. Транспортная задача закрытого типа, представленная в сетевой форме, без ограничений пропускной способности

Сетевой способ решения задачи не требует составления матрицы перевозок, а позволяет вести расчет прямо на схеме путей сообщения – сети.

Сеть состоит из вершин и звеньев. Квадратами обозначены вершины (станции) отправления. Числитель внутри квадрата – номер вершины (станции) отправления, знаменатель – объем отправляемых вагонов (продукции). Кружками обозначены вершины (станции) назначения, числитель – номер вершины, знаменатель – объем потребления. Числа на звеньях – расстояние перевозок (или другой критерий оптимизации) ci,j+1 между станциями i и j+1.
  1   2   3   4   5

Добавить документ в свой блог или на сайт

Похожие:

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение задач линейного программирования Цель работы
Цель работы: Изучение возможностей пакета Ms Excel при решении задач линейного программирования. Приобретение навыков решения задач...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconКафедра экономико-математических методов и вычислительной техники...
Алгоритм решения задач линейного программирования симплексным методом: Методические указания студентам направления 100700 «Торговое...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconТранспортная задача
Методические указания предназначены для студентов дневного и заочного отделения по направлениям: 250300, 190700, 250400. В методических...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconИсследование операций” Модель и эффективность операции
Индивидуальные задания для решения задач линейного программирования графическим методом

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПонятие программы и программирования. Свойства программ. Назначение...
Системы счисления. Сущность перевода чисел из одной системы счисления в другую: примеры

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПрограммирование для начинающих turbo Pascal 0
В практической части рассмотрены основы алгоритмизации решения задач и их программирования на языке Паскаль. Приводятся примеры разработки...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение. Часть 1
Конституции РФ. Тест состоит из двух частей: первая часть состоит из 20 простых вопросов, на которые предусмотрен только один ответ;...

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconРешение: в 1954 г в компании ibm под руководством Джона Бэкуса был...
Тема: Эволюция и классификация языков программирования. Основные понятия языков программирования

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconЗадачи курса изучение языка программирования Турбо-Паскаль в объеме,...
Знакомство с методами отладки программ. Реше- ние задач с использованием основных пакетов прикладных программ

Реферат Тема: решение транспортных задач методами линейного программирования. Часть II (примеры) iconПрактикум по решению линейных задач математического программирования
Акульшина Т. С., Стебко Т. В. Практикум по решению линейных задач математического программирования. – Симферополь, уэу, 2006 – 44...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
zadocs.ru
Главная страница

Разработка сайта — Веб студия Адаманов