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




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

Пример № 3.

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


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

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

Решение транспортных задач с ограничениями производится аналогично решению задачи без ограничений. Однако имеется ряд особенностей. Рассмотрим это на примере.
Для транспортной задачи, представленной в матричной форме с ограничениями пропускной способности, необходимо найти оптимальный план, при котором будет выполняться условие наименьшего суммарного объема тонно-километровой работы. Для этого необходимо выполнить следующие действия:

  • составить математическую модель задачи;

  • составить начальный план, проверить по условию “вырождения”, рассчитать суммарный объем тонно-километровой работы;

  • решить задачу методом потенциалов, рассчитать суммарный объем тонно-километровой работы оптимального плана;

  • сравнить начальный и оптимальный варианты.

Исходные данные к задаче приведены в табл.11.

Таблица 11

Объем отправления и потребления грузов

Станция

отправления

Ресурсы,

тыс. т

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

В1

В2

В3

В4

В5

В6

В7

В8

В9

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

90

90

190

130

170

80

100

100

50

А1

200

70

40

105

65

200

75

20*

60**

80

45

А2

250

25

30

45

40

25

65

30

15

60

25

А3

100

75

35

75

120

80

40

70

20

40

80

А4

250

15

55

45

10

20

65

110

75

30

20

А5

200

15

25

15

15

20

35

25

80

20

70

85

Примечания: 20* – расстояние перевозки от i-й станции отправления до j-й станции назначения, км, 60** – ограничение пропускной способности.

Решение начинается с составления математической модели задачи. Целевой функцией является минимальная тонно-километровая работа, которая определяется по формуле

min ,

где lij — расстояние перевозки от i-й станции отправления до j-й станции назначения;

xij — объем перевозки от i-й станции отправления до j-й станции назначения.
Система ограничений для данной задачи

, (i = 1,2,...,5),

 

, (j = 1,2,...,9),

xij > = 0, (i = 1,2,...,5; j = 1,2,...,9).

Для решения задачи составляется начальный план. Исходный опорный план составляется с помощью одного из методов (см. пример № 1).

Таблица 12

Исходный опорный план


Станция

отправления

Ресурсы,

тыс. т

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

В1

В2

В3

В4

В5

В6

В7

В8

В9

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

90

90

190

130

170

80

100

100

50

А1

200

70

40

90

105

65

200

75

20

60 60

80

45

50

А2

250

25

90

30

45

40

25

100

65

30

15

60 60

25

А3

100

75

35

75

120

80

40

60

70

20

40 40

80

А4

250

15

55

45

10

190

20

60

65

110

75

30

20

А5

200

15

25

15

15

20

35 70

25

70

80

20

20

40

70

85
В данном примере воспользуемся методом наименьшего критерия в строке. Назначенные перевозки записываются в правом нижнем углу клетки и подчеркиваются. В клетке с ограничением пропускной способности не может быть записана перевозка большая, чем само ограничение (клетки A1B7, A2B8, A3B8, A5B4). Исходный опорный план, полученный с помощью этого метода представлен в табл.12.

В полученном плане в клетке A5B4 назначенная перевозка превышает пропускную способность (70 > 35). Эта перевозка была назначена для того, чтобы удовлетворить потребность столбца B4. Следовательно, данный план необходимо скорректировать. Строится контур корректировки (A5B3 – A5B4 – A4B4 – A4B3). В данном контуре необходимо снять лишнюю перевозку в размере 35 в клетке A5B4. Для этого значения назначенных перевозок в клетках вершин контура изменяют на необходимую величину (35), поочередно отнимая и прибавляя выбранное значение к существующим значениям перевозок в клетках вершин контура. Получаем скорректированный исходный опорный план (табл.13).

Таблица 13

Скорректированный исходный опорный план

Станция

отправления

Ресурсы,

тыс. т

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

В1

В2

В3

В4

В5

В6

В7

В8

В9

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

90

90

190

130

170

80

100

100

50

А1

200

70

40

90

105

65

200

75

20

60 60

80

45

50

А2

250

25

90

30

45

40

25

100

65

30

15

60 60

25

А3

100

75

35

75

120

80

40

60

70

20

40 40

80

А4

250

15

55

45

10

155

20

95

65

110

75

30

20

А5

200

15

25

15

15

35

20

35 35

25

70

80

20

20

40

70

85

Начальное значение целевой функции (суммарный объем тонно-километровой работы) составит

Fнач = f (x) = 90· 40 + 60· 20 + 50· 45 + 90· 25 + 100· 25 + 60· 15 + 60· 40 + 40· 20 +155 ·10 + 95· 20 + 35· 15 + 35 · 20 + 70 · 25 + 20 · 80 + 40· 20 = 24725 тыс. ткм.

Полученный исходный план проверяется на условие “вырождения” [см. формулу (6)]:

Nз  n + m – 1, где Nз – число занятых базисных клеток.

Клетка называется базисной, если в ней назначена перевозка. Однако, занятая клетка, в которой перевозка равна ограничению пропускной способности, не является базисной (в примере – клетки A1B7, A2B8, A3B8, A5B4). Такая клетка называется насыщенной. В то же время клетка с перевозкой, меньшей чем ограничение пропускной способности в той же клетке, является базисной.

В полученном плане количество клеток Nз = 11, а суммарное число строк и столбцов m + n – 1 = 5 + 9 – 1 = 13. Задача “вырожденная”, необходимо назначить две фиктивные перевозки (в примере – в клетки A5B2 и A4B8). Клетки с фиктивными перевозками считаются базисными.

Полученный исходный план проверяется на оптимальность. Для этого всем строкам и столбцам присваиваются потенциалы (табл.14).

Таблица 14

Присвоение потенциалов

Для транспортной задачи с ограничениями план считается оптимальным, если соблюдаются следующие условия:

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

Vj – Ui = cij, (14)

при a ij > xij > 0 (базисная клетка),

Vj – Ui ≥ cij, при xij = a ij (перевозка в клетке равна ограничению), где Vj – потенциал j–го столбца; Ui – потенциал i-й строки; a ij – ограничение пропускной способности.

В данном исходном плане имеются три клетки с нарушением условий оптимальности [см. формулу (14)]. Для клетки А1В6 разность потенциалов V6 – U1 = 180 – 75 = 105, что больше стоимости перевозки в данной клетке, равной 75 единиц. Нарушение первого условия оптимальности составляет Н16 = 105 – 75 = 30. Записываем его в правом верхнем углу матрицы перевозок (табл.14). Аналогично, для клетки А2В6 разность потенциалов V6 – U2 = 180 – 100 = 80, при стоимости перевозки 65, нарушение первого условия оптимальности составляет Н26 = 80 – 65 = 15. В клетке А3В8 определено нарушение третьего условия оптимальности, которое составляет Н38 = 25.

Так как данный исходный план не является оптимальным, он может быть улучшен за счет клеток с нарушениями. Для улучшения плана выбирается клетка с наибольшим нарушением А1В6 (нарушение 30).

Следуя формальному правилу улучшения плана (см.пример №1), “ходом шахматной ладьи” строится контур корректировки с вершинами в выбранной клетке с нарушением и в базисных клетках (А1В2 – А1В6 – – А5В2 – А5В6). Вершины контура нумеруются начиная с клетки с нарушением. Определяется минимальная перевозка в четных вершинах контура min{20; 90} = 20 в клетке А5В6. Данная перевозка “переносится” по контуру, в нечетные клетки найденное значение прибавляется, из четных – вычитается. Получается новый скорректированный улучшенный план (табл.15).

Таблица 15

Итоговый план перевозок

Станция

отправления

Ресурсы,

тыс. т

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

 

 

Ui

В1

В2

В3

В4

В5

В6

В7

В8

В9

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

90

90

190

130

170

80

100

100

50

А1

200

70

40

70

105

65

200

75

20

20

60 60

80

45

50

75

А2

250

25

90

30

45

40

25

100

65

30

15

60 60

25

100

А3

100

75

35

75

120

80

40

60

70

20

40 40

80

110

А4

250

15

55

45

10

155

20

95

65

110

75

30

0

20

105

А5

200

15

25

15

20

15

35

20

35 35

25

70

80

20

40

70

85

100

Vj

125

115

115

125

125

150

120

135

120




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

Fкон = f (x) = 70· 40 + 20· 75 + 60· 20 + 50· 45 + 90· 25 + 100· 25 + 60· 15 + 60· 40 + + 40· 20 + 155· 10 + 95· 20 + 20· 15 + 35· 15 + 35· 20 + 70· 25 + 40· 20 = 24125 тыс. ткм.

Полученный скорректированный план перевозок проверяется на оптимальность по формуле (14).

В данном плане отсутствуют нарушения условий оптимальности для всех клеток, следовательно, план оптимален и итоговый план перевозок улучшен по сравнению с исходным на 600 ткм (Fнач – Fкон = 24725 – 24125).
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
Главная страница

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