Методы принятия управленческих решений

Автор: Пользователь скрыл имя, 11 Марта 2013 в 11:59, курсовая работа

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

Одна из наиболее распространенных задач математического программирования — транспортная задача. Транспортная задача (задача Монжа —Канторовича) —математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение. Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления в пункты потребления, с минимальными затратами на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной и входит в класс сложности NP. Когда суммарный объём предложений (грузов, имеющихся в пунктах отправления) не равен общему объёму спроса на товары (грузы), запрашиваемые пунктами потребления, транспортная задача называется несбалансированной (открытой).

Файлы: 1 файл

Курсовая работа МПУР.docx

— 171.84 Кб (Скачать)

20*50 + 21*5 + 23*15 + 31*35 + 15*30 + 27*60 + 34*30 = 5625

Аналогично определяем минимальные затраты:

20*50 + 22*5 + 23*15 + 31*35 + 15*30 + 27*65 + 34*25 = 5595

20*25 + 22*30 + 23*15 + 31*35 + 15*30 + 23*25 + 27*65 = 5370

22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 = 5195

Определяем оценку для  каждой свободной клетки.

В свободную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

 

50

65

65

55

30

70

20[+]

21

22[55]

[-]

23[15]

24

65

22[25]

[-]

28

31[10]

[+]

40

15[30]

90

23[25]

27[65]

34

43

18


Оценка свободной клетки равна Δ11 = 7

Аналогично выполняем  оценку для каждой свободной клетки:

Оценка свободной клетки равна Δ12 = 4

Оценка свободной клетки равна Δ15 = 18

Оценка свободной клетки равна Δ22 = 2

Оценка свободной клетки равна Δ24 = 8

Оценка свободной клетки равна Δ33 = 2

Оценка свободной клетки равна Δ34 = 10

Оценка свободной клетки равна Δ35 = 2

Оценка свободной клетки равна Δ41 = 10

Оценка свободной клетки равна Δ42 = 6

Оценка свободной клетки равна Δ43 = 1

Оценка свободной клетки равна Δ45 = 17.

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

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

Минимальные затраты составят:

22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65  = 5195

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МЕТОД МИНИМАЛЬНОЙ  СТОИМОСТИ

МЕТОД ПОТЕНЦИАЛОВ

Стоимость доставки единицы  груза из каждого пункта отправления  в соответствующие пункты назначения задана матрицей тарифов

 

50

65

65

55

30

70

20

21

22

23

24

65

22

28

31

40

15

90

23

27

34

43

18


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

∑a = 70 + 65 + 90 = 225

∑b = 50 + 65 + 65 + 55 + 30 = 265

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

 

50

65

65

55

30

70

20[50]

21[20]

22

23

24

65

22

28

31[35]

40

15[30]

90

23

27[45]

34[30]

43[15]

18


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

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

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

 

v1=20

v2=21

v3=28

v4=37

v5=12

u1=0

20[50]

21[20]

22

23

24

u2=3

22

28

31[35]

40

15[30]

u3=6

23

27[45]

34[30]

43[15]

18


Опорный план не является оптимальным, так как существуют оценки свободных  клеток, для которых ui + vi > cij

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

 

50

65

65

55

30

70

20[25]

21

22[30]

23[15]

24

65

22

28

31[35]

40

15[30]

90

23[25]

27[65]

34

43

18


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

 

v1=20

v2=24

v3=22

v4=23

v5=6

u1=0

20[25]

21

22[30]

23[15]

24

u2=9

22

28

31[35]

40

15[30]

u3=3

23[25]

27[26]

34

43

18


Опорный план не является оптимальным, так как существуют оценки свободных  клеток, для которых ui + vi > cij

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

Для этого в перспективную  клетку (2;1) поставим знак «+», а в  остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

 

50

65

65

55

30

70

20[25]

[-]

21

22[30][+]

23[15]

24

65

22

[+]

28

31[35]

[-]

40

15[30]

90

23[25]

27[65]

34

43

18


 

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

 

50

65

65

55

30

70

20

21

22[55]

23[15]

24

65

22[25]

28

31[10]

40

15[30]

90

23[25]

27[65]

34

43

18


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

 

v1=13

v2=17

v3=22

v4=23

v5=6

u1=0

20

21

22[55]

23[15]

24

u2=9

22[25]

28

31[10]

40

15[30]

u3=10

23[25]

27[65]

34

43

18


Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 22*55 + 23*15 + 22*25 + 31*10 + 15*30 + 23*25 + 27*65 + 0*40  = 5195

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МЕТОД ФОГЕЛЯ

Стоимость доставки единицы  груза из каждого пункта отправления  в соответствующие пункты назначения задана матрицей тарифов

 

50

65

65

55

30

70

20

21

22

23

24

65

22

28

31

40

15

90

23

27

34

43

18


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

∑ a = 70 + 65 + 90 = 225

∑ b = 50 + 65 + 65 + 55 + 30 = 265

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

 

50

65

65

55

30

70

20

21

22[15]

23[55]

24

65

22[35]

28

31

40

15[30]

90

23[15]

27[65]

34[10]

43

18


Сведем все вычисления в одну таблицу

 

50

65

65

55

30

d1

d2

d3

d4

d5

70

20

21

22[5]

23[55]

24

1

1

-

-

-

65

22[35]

28

31

40

15[30]

7

7

7

6

-

90

23[15]

27[65]

34[10]

43

18

5

5

5

4

4

d1

2

6

9

17

3

 

 

 

 

 

 

 

 

 

 

d2

2

6

9

-

3

 

 

 

 

 

 

 

 

 

 

d3

1

1

3

-

3

 

 

 

 

 

 

 

 

 

 

d4

1

1

3

-

-

 

 

 

 

 

 

 

 

 

 

d5

0

0

0

-

-

 

 

 

 

 

 

 

 

 

 

Информация о работе Методы принятия управленческих решений