Сетевые модели: нахождение потока наименьшей стоимости

Автор работы: Пользователь скрыл имя, 15 Июня 2014 в 12:03, курсовая работа

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

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

Содержание

ВВЕДЕНИЕ 3
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 4
Сетевая модель 4
Сетевая модель как задача линейного программирования 4
Алгоритм симплекс-метода для сетей с ограниченной пропускной способностью 6
Транспортная задача 8
Метод северо-западного угла 9
Метод наименьшей стоимости 9
Метод потенциалов 10
ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ 12
Постановка задачи 12
Нахождение первоначального плана методом северо-западного угла 13
Нахождение первоначального плана методом наименьшей стоимости 14
Метод потенциалов 15
ЗАКЛЮЧЕНИЕ 19
ЛИТЕРАТУРА 20

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

Курсовая ИСО.docx

— 83.38 Кб (Скачать файл)

 

Метод потенциалов

Наиболее простым методом ТЗ является метод потенциалов. Потенциалами называются условные числа Ui ,Vj , приписанные определённым образом каждому поставщику и потребителю.

Теорема(условия оптимального плана): Сумма потенциалов поставщика и потребителя равна тарифной ставке для занятых клеток; сумма потенциалов поставщика и потребителя не превышает тарифную ставку для свободных клеток

 


 

Опорный план должен быть не вырожденным (r=m+n-1 – невырожденный план)

Алгоритм решения:

  1. Строим начальные планы методом северо-западного угла и методом наименьшей стоимости из них выбираем лучший
  2. Находим потенциалы поставщика и потребителя, пользуясь первым условием оптимальности плана Ui + Vj < Cij
  3. Проверяем второе условие оптимальности плана для свободных клеток

 

Если оно выполнено, то план оптимален, если нет то улучшаем план.

  1. Улучшение плана:
      • При не выполнении второго условия в клетку заносим нарушение со знаком плюс. Такие клетки называются потенциальными. Среди всех потенциальных клеток выбираем клетку с наибольшим нарушением.
      • Строим для выбранной клетки замкнутый контур, состоящий из вертикальных и горизонтальных отрезков прямой, причем вершины контура лежат в занятых клетках. За исключением той клетки, для которой строится контур
      • Вершины контура поочерёдно помечаем знаками плюс и минус, начиная с клетки, для которой строится контур.
      • Среди клеток помеченных знаком минус выбираем наименьшею перевозку и на эту величину увеличиваем перевозку в клетках помеченных знаком плюс и уменьшаем в клетках помеченных знаком минус в результатах переназначения освобождается одна клетка.
  1. Вновь полученный план проверяем на оптимальность.

 

 Метод аппроксимации Фогеля

Данный метод состоит в следующем:

  1. На каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;
  2. Находят max Δcij и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

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

 

ПРАКТИЧЕСКАЯ РЕАЛИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ СИМПЛЕКС-МЕТОДОМ

Постановка задачи

Имеются три пункта поставки мониторов: Склад №1, Склад №2, Склад №3. И пять магазинов: Магазин "Терабайт", Магазин "Лидер", Магазин "Эксперт", Магазин "Ока-сервис", "Владимирский рынок", потребления этого товара. Найти оптимальный план распределения товаров с минимальными затратами.

Дано:

Склад №1=200 шт.

Склад №2=250шт.

Склад №3=200шт.

Требуется доставить штук:

Магазин "Терабайт"= 190шт.

Магазин "Лидер"= 100 шт.

Магазин "Эксперт" = 120 шт.

Магазин "Ока-сервис" =110 шт.

"Владимирский рынок" =130 шт.

Сетка тарифов:

28

 27

18

27

24

18

26

27

32

21

27

 33

23

31

34


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

Магазины:

Магазин "Терабайт"= B1

Магазин "Лидер"= B2

Магазин "Эксперт" = B3

Магазин "Ока-сервис" = B4

"Владимирский рынок" = B5

Товары:

Склад №1= A1

Склад №2 = A2

Склад №3= A3

Тогда матрица будет выглядеть так:

 

 B1

B2

B3

B4

B5

 Запасы

A1

28

 27

18

27

24

200

A2

18

26

27

32

21

250

A3

27

 33

23

31

34

200

Потребности

190

100

120

110

130

 

Следуя данной модели можно найти опорный план и решение поставленной задачи.

Нахождение первоначального плана методом северо-западного угла

Используя построенную матрицу тарифов найдём оптимальный опорный план методом северо-западного угла.

 

 B1

 B2

 B3

B4

B5

 Запасы

A1

28

 27

18

27

24

200

 A2

18

26

27

32

21

250

 A3

27

 33

23

31

34

200

Потреб.

190

100

120

110

130

 

Проверим необходимое и достаточное условие разрешимости задачи.

 

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

 

 B1

B2

B3

B4

B5

Запасы

A1

28 [190]

27 [10]

18

27

24

200

 A2

18

26 [90]

27 [120]

32 [40]

21

250

 A3

27

33

23

31 [70]

34 [130]

200

Потреб.

190

100

120

110

130

 

 

Решение задачи методом северо-западного угла всегда начинается с левого, верхнего тарифа([A1;B1]). Полностью удовлетворяем потребность данного тарифа. Исключаем первый столбец. Дальше смотрим если запасы ещё остались, рассматриваем рядом стоящий тариф ([A2;B1]), если нет, то исключаем и первую верхнею строк. И рассматриваем следующий тариф по аналогичной схеме. В результате получен опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F=28*190+27*10+26*90+27*120+32*40+31*70+34*130=19040

Результат: Затраты на распределение товаров между магазинами найденные методом северо-западного угла составят 19040 рублей.

Нахождение первоначального плана методом наименьшей стоимости

Используя построенную матрицу тарифов, найдём оптимальный опорный план методом наименьшей стоимости.

 

 B1

B2

B3

B4

B5

 Запасы

A1

28

 27

18

27

24

200

 A2

18

26

27

32

21

250

 A3

27

 33

23

31

34

200

Потреб.

190

100

120

110

130

 

Проверим необходимое и достаточное условие разрешимости задачи.

Условие баланса соблюдается. Запасы равны потребностям. Построим опорный план транспортной задачи:

 

 B1

B2

B3

B4

B5

Запасы

A1

28

27[10]

18[120]

27

24[70]

 200

 A2

18 [190]

 26

 27

 32

21[60]

 250

 A3

 27

33 [90]

 23

31 [110]

 34

 200

Потреб.

190

100

120

110

130

 

Для решения задачи методом наименьшей стоимости сначала из все матрицы тарифов выбираем наименьший тариф ([A2;B1]). Полностью удовлетворяем его потребность. Исключаем из решения столбец в котором он находился. Ищем следующий минимальный тариф ([A1;B3]). Удовлетворяем его потребности. Исключаем из решения столбец в котором он находился. Дальше продолжаем до тех пор, пока все запасы не будут розданы.

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

Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Подсчитаем затраты на распределение товаров:

F=27*10+18*120+24*70+18*190+21*60+33*90+31*110=15170

Результат: Затраты на распределение товаров между магазинами найденные методом наименьшей стоимости составят 15170 рублей.

Метод потенциалов

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

Для данной задачи минимальным является метод наименьшей стоимости.

Опорный метод этого плана и будем использовать для решения задачи методом потенциалов:

 

 B1

B2

B3

B4

B5

Запасы

A1

28

27[10]

18[120]

27

24[70]

 200

 A2

18[190]

 26

 27

 32

21[60]

 250

 A3

 27

33[90]

 23

31[110]

 34

 200

Потреб.

190

100

120

110

130

 

Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij

Для этого построим систему уравнений:

Из этой системы уравнений находим потенциалы , полагая, что u1 = 0:

v1=21, v2=27, v3=18, v4=25, v5=24, u1=0, u1=-3, u3=6

 

 v1=21

 v2=27

 v3=18

 v4=25

 v5=24

 u1=0

 28

27[10]

18[120]

 27

24[70]

 u2=-3

18[190]

26

27

32

21[60]

 u3=6

27

33[90]

 23

31[110]

34


Опорный план не является оптимальным, так как существуют оценки свободных клеток для которых ui + vi > cij, (3;3): 6 + 18 > 23

Выбираем максимальную оценку свободной клетки (3;3): 23

Для этого в перспективную клетку (3;3) поставим знак "+", а в остальных вершинах многоугольника чередующиеся знаки "-", "+", "-". Цикл приведен в таблице.

Из грузов стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 2) = 90. Прибавляем 90 к объемам грузов, стоящих в плюсовых клетках и вычитаем 90 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

 B1

B2

B3

B4

B5

Запасы

A1

28

27[100]

18[30]

 27

24[70]

 200

 A2

18[190]

26

27

32

21[60]

 250

 A3

 27

 33

23[90]

31[110]

 34

 200

Потреб.

190

100

120

110

130

 

Проверим оптимальность опорного плана. Найдем потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij (Алгоритм нахождения потенциалов описан выше).

 

 v1=21

 v2=27

 v3=18

 v4=26

 v5=24

 u1=0

28

27[100]

18[30]

27

24[70]

 u2=-3

18[190]

26

27

32

21[60]

 u3=5

27

33

23[90]

31[110]

34

Информация о работе Сетевые модели: нахождение потока наименьшей стоимости