Xreferat.com » Рефераты по экономико-математическому моделированию » Экономико-математический практикум

Экономико-математический практикум

align="LEFT" />Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум

Рис.3. пересчет перевозок по потенциалам


Во второй строке выписываем ребра, принадлежащие циклу пересчета. В первой строке, над ребрами с помощью стрелок укажем направление перевозок, а в третьей строке – объем перевозимого груза. В четвертой строке полученной конструкции запишем Экономико-математический практикум, если направление перевозки совпадает с разрешающей стрелкой и Экономико-математический практикум, в противном случае.


Экономико-математический практикум


Изменяем распределение поставок. Определяем Экономико-математический практикум величину корректировки плана. Поскольку перевозки х8,10,х11,9 направлены против разрешающей стрелки, величина Экономико-математический практикум полагается меньшей из них Экономико-математический практикум

Включаем в базис ребро (7,8), а объем перевозки полагаем равным величине корректировки Экономико-математический практикум Ребро (7,9) исключаем из базиса.

После пересчета получим значение функции:

Экономико-математический практикум


Задача № 5


Задача о назначениях

Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей Экономико-математический практикум задачи о разборчивой невесте. Решить задачу методом потенциалов и венгерским методом.




44







31 13 11 41 10 17 38 25


35 20 26 8 17 14 38 36


12 37 38 49 38 22 10 13


28 21 48 43 44 29 26 12


37 22 39 46 26 20 44 49


22 49 19 2 20 30 45 16


45 27 5 21 30 21 34 23


43 33 20 29 3 46 33 21


Решение.

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

Начальный вариант выбора Экономико-математический практикум найдем методом максимального элемента (Табл. 5.1).

Шаг 1. Максимальным элементом является с3,4=49. Назначим третьей невесте четвертого жениха. Вычеркнем третью строку.

Шаг 2. Из невычеркнутых элементов матрицы максимальным элементом является с5,8=49. Назначим пятой невесте восьмого жениха. Вычеркнем пятую строку.

Шаг 3. Из невычеркнутых элементов матрицы максимальным элементом является с6,2=49. Шестая невеста выбирает второго жениха, вычеркиваем шестую строку.

Шаг 4. Из невычеркнутых элементов матрицы максимальным элементом является с4,3=48. Четвертая невеста выбирает третьего жениха, вычеркиваем четвертую строку.

Шаг 5. Из невычеркнутых элементов матрицы максимальным элементом является с8,6=46. Восьмая невеста выбирает шестого жениха, вычеркиваем восьмую строку.

Шаг 6. Из невычеркнутых элементов матрицы максимальным элементом является с7,1=45. Седьмая невеста выбирает первого жениха, вычеркиваем седьмую строку.

Шаг 7. Из невычеркнутых элементов матрицы максимальным элементом является с1,4=41. Но четвертого жениха уже выбрала третья невеста, поэтому в клетку (1,4) поместим 0. В дальнейшем, х1,4=0 будем считать базисной переменной. Вычеркнем четвертый столбец.

Шаг 8. Из невычеркнутых элементов матрицы максимальным элементом является с1,7=38. Первая невеста назначается седьмому жениху, вычеркиваем первую строку.

Шаг 9. Из невычеркнутых элементов матрицы максимальным элементом является с2,7=38. Но седьмой жених уже выбран, поэтому в клетку (2,7) поместим 0. Х2,7=0 - базисная переменная. Вычеркнем седьмой столбец.

Шаг 10. Из невычеркнутых элементов матрицы максимальным элементом является с2,8=36. На восьмой жених уже выбран, поэтому в клетку (2,8) поместим 0. Х2,8=0 - базисная переменная. Вычеркнем восьмой столбец.

Шаг 11. Из невычеркнутых элементов матрицы максимальным элементом является с2,1=35. Но первый жених уже занят, поэтому в клетку (2,1) поместим 0. Х2,1=0 - базисная переменная. Вычеркнем первый столбец.

Шаг 12. Из невычеркнутых элементов матрицы максимальным элементом является Х2,3=26. Но третий жених уже занят, поэтому в клетку (2,3) поместим 0. Х2,3=0 - базисная переменная. Вычеркнем третий столбец.

Шаг 13. Из невычеркнутых элементов матрицы максимальным элементом является Х1,5=23. Но пятый жених уже занят, поэтому в клетку (1,5) поместим 0. Х1,5=0 - базисная переменная. Вычеркнем пятый столбец.

Шаг 14. Из невычеркнутых элементов матрицы максимальным элементом является с2,2=20. Но второй жених уже занят, поэтому в клетку (2,2) поместим 0. Х2,2=0 - базисная переменная. Вычеркнем второй столбец.

Шаг 15. Из невычеркнутых элементов матрицы максимальным элементом является с2,5=17. Вторая невеста назначается пятому жениху, вычеркиваем вторую строку.

В табл. 5.1 номер шага, на котором были получены базисные переменные, указан в скобках. После 15 шага получим пробный вариант назначения Х0: х1,7=х2,5= х3,4=х4,3=х5,8=х6,2= х7,1=х8,6=1. Это означает, что первая невеста выходит замуж за седьмого жениха, вторая невеста за пятого жениха, третья невеста за четвертого жениха, четвертая невеста за третьего жениха, пятая невеста за восьмого жениха, шестая невеста за второго жениха, седьмая невеста за первого жениха, восьмая невеста за шестого жениха.


Таблица 5.1.









31 13 11 41 10 17 38 25



0(7)

0(13)


1(8)










35 20 26 8 17 14 38 36

0(11)

0(14)

0(12)


1(15)


0(7)

0(10)

12 37 38 49 38 22 10 13



1(1)





28 21 48 43 44 29 26 12


1(4)






37 22 39 46 26 20 44 49







1(2)

22 49 19 2 20 30 45 16

1(3)







45 27 5 21 30 21 34 23

1(6)








43 33 20 29 3 46 33 21





1(5)




Суммарная эффективность, отвечающая полученному варианту выбора равна:

Экономико-математический практикумусловных единиц эффективности

Вариант выбора Экономико-математический практикум проверим на оптимальность. Для этого вычислим потенциалы и оценки.


Экономико-математический практикум


Отсюда вычислим потенциалы:


Экономико-математический практикум


Для небазисных переменных вычислим оценки по соответствующей формуле:


Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикум

Экономико-математический практикумЭкономико-математический практикум


И так далее расчеты по соответствующим формулам и данным приведены в таблице 5.2.


Таблица 5.2

Х0

28

13

19

41

10

44

38

29


31 13 11 41 10 17 38 25

0




0(7)

0(13)


1(8)


Оценка1

-3 0 8

27

4


35 20 26 8 17 14 38 36

7

0(11)

0(14)

0(12)


1(15)


0(7)

0(10)

Оценка2




40
37

8

12 37 38 49 38 22 10 13




1(1)





Оценка3

24 -16 -11
-20 30 36 24
29 28 21 48 43 44 29 26 12



1(4)






Оценка4

29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20








1(2)

Оценка5

11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)







Оценка6

42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)








Оценка7


3

31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2




1(5)



Оценка8

-6 -11 8 -19 16
7 17

Cреди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Экономико-математический практикум Строим цикл пересчета: (3,5), (2,5), (1,7), (1,4), (3,5) замыкающийся на разрешающей клетке. Вычислим величину корректировки Экономико-математический практикум. Базисный нуль 03,5 перемещается в клетку (1,7), переменная х1,7 включается в базис, а переменная х3,5 выходит из базиса. Получим новую комбинацию расстановки единиц и нулей (Табл. 5.3). Суммарная эффективность равна:

Экономико-математический практикумусловных единиц эффективности


Таблица 5.3

Х0

28

13

19

41

10

44

38

29


31 13 11 41 10 17 38 25

0




1(7)

0(13)


0(8)


Оценка1

-3 0 8

27

4


35 20 26 8 17 14 38 36

7

0(11)

0(14)

0(12)


0(15)


1(7)

0(10)

Оценка2




40
37

28

12 37 38 49 38 22 10 13





1(7)




Оценка3

44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)






Оценка4

29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20








1(2)

Оценка5

11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)







Оценка6

42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)








Оценка7


3

31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2




1(5)



Оценка8

-6 -11 8 -19 16
7 17

Заново вычисляем потенциалы и оценки.

Экономико-математический практикум


Отсюда вычислим потенциалы:


Экономико-математический практикум


Для небазисных переменных вычислим оценки в таблице 5.3.

Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Экономико-математический практикум Строим цикл пересчета: (8,4), (2,4), (2,2), (8,2),(8,4) замыкающийся на разрешающей клетке. Вычислим величину корректировки Экономико-математический практикум. Базисная переменная х2,2=0 перемещается в клетку (8,4), переменная х8,4 включается в базис, а переменная х2,2 выходит из базиса. (Табл. 5.4).


Таблица 5.4

Х1

28

13

19

41

10

44

38

29


31 13 11 41 10 17 38 25

0




1(7)

0(13)


0(8)


Оценка1

-3 0 8

27

4


35 20 26 8 17 14 38 36

7

0(11)


0(12)


0(15)


1(7)

0(10)

Оценка2




40
37

28

12 37 38 49 38 22 10 13





1(7)




Оценка3

44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)






Оценка4

29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20








1(2)

Оценка5

11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)







Оценка6

42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)








Оценка7


3

31 37 -3 40 21 23

43 33 20 29 3 46 33 21
2


0(14)


1(5)



Оценка8

-6 -11 8 -19 16
7 17

Суммарная эффективность не изменилась и равна:

Экономико-математический практикумусловных единиц эффективности

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.

Среди вычисленных оценок имеются отрицательные, это означает, что выбранный вариант назначения не является оптимальным. Наименьшая из отрицательных оценок Экономико-математический практикум Строим цикл пересчета: (2,4), (2,5), (5,5), (5,2),(2,2) замыкающийся на разрешающей клетке. Вычислим величину корректировки Экономико-математический практикум. Базисная переменная х5,2=0 перемещается в клетку (2,4), переменная х2,4 включается в базис, а переменная х5,2 выходит из базиса. (Табл. 5.5).


Таблица 5.5

Х2

28

13

19

41

10

44

38

29


31 13 11 41 10 17 38 25

0




1(7)

0(13)


0(8)


Оценка1

-3 0 8

27

4


35 20 26 8 17 14 38 36

7

0(11)


0(12)


0(15)


1(7)

0(10)

Оценка2




40
37

28

12 37 38 49 38 22 10 13





1(7)




Оценка3

44 4 9 20
50 56 44
29 28 21 48 43 44 29 26 12



1(4)






Оценка4

29 21
27 -5 44 41 46

37 22 39 46 26 20 44 49

20








1(2)

Оценка5

11 11 0 15 4 44 14

22 49 19 2 20 30 45 16
36

1(3)







Оценка6

42
36 75 26 50 29 49

45 27 5 21 30 21 34 23
17

1(6)








Оценка7


3

31 37 -3 40 21 23

43 33 20 29 3 46 33 21
21


0(14)


1(5)



Оценка8

6 11 20
29
26 29

Заново вычисляем потенциалы и оценки. Расчеты оценок приведены в таблице 5.5.

Отрицательных оценок нет. Назначение Х2 оптимально, обозначим его через Х2*.

Суммарная эффективность, отвечающая полученному варианту назначения равна:

Экономико-математический практикумусловных единиц эффективности

Назначение Х2 оптимально. Итак, оптимальный вариант назначения имеет вид:

х1,4=1 (первая невеста выберет четвертого жениха),

х2,7=1 (вторая невеста выберет седьмого жениха),

х3,5=1 (третья невеста выбрала пятого жениха),

х4,3=1 (четвертая невеста выбрала третьего жениха),

х5,8=1 (пятая невеста выберет восьмого жениха),

х6,2=1 (шестая невеста выберет второго жениха),

х7,1=1 (седьмая невеста выберет первого жениха),

х8,6=1 (восьмая невеста выберет шестого жениха).

При этом варианте назначений получим максимальную эффективность Экономико-математический практикум единиц эффективности.

Венгерский метод.

Предварительный этап. Исходная матрица C:


31 13 11 41 10 17 38 25
35 20 26 8 17 14 38 36
12 37 38 49 38 22 10 13
28 21 48 43 44 29 26 12
37 22 39 46 26 20 44 49
22 49 19 2 20 30 45 16
45 27 5 21 30 21 34 23
43 33 20 29 3 46 33 21

Шаг 1. Обозначим через Экономико-математический практикум наибольший элемент столбца Экономико-математический практикум матрицы Экономико-математический практикум (r1=45, r2=49, r3=48, r4=49, r5=44, r6=46, r7=45, r8=49). Каждый элемент Экономико-математический практикум-го столбца вычтем из Экономико-математический практикум, результаты вычислений будем помещать на место вычитаемого. Аналогичные преобразования проводим в остальных столбцах. Получим неотрицательную матрицу Экономико-математический практикум, в каждом столбце которой есть хотя бы один нуль.


C1 =

14

36

37

8

34

29

7

24


10

29

22

41

27

32

7

13


33

12

10

0

6

24

35

36


17

28

0

6

0

17

19

37


8

27

9

3

18

26

1

0


23

0

29

47

24

16

0

30


0

22

43

28

14

25

11

23


2

16

28

20

41

0

12

25


Шаг 2. Преобразуем матрицу Экономико-математический практикум. Для этого обозначим через Экономико-математический практикум минимальный элемент строки Экономико-математический практикум, который последовательно вычтем из элементов той же строки, результаты поместим на место уменьшаемого. Наименьший элемент первой строки матрицы Экономико-математический практикум равен 7. Проведем вычисления для элементов первой строки: (d11=7, d12=29, d13=30, d14=1, d15=27, d16=22, d17=0, d18=17). Такие же вычисления проведем для остальных строк, получим неотрицательную матрицу Экономико-математический практикум, в каждом столбце и каждой строке которой есть хотя бы один нуль.


D=

7

29

30

1

27

22

0*

17


3

22

15

34

20

25

0

6


33

12

10

0*

6

24

35

36


17

28

0*

6

0

17

19

37


8

27

9

3

18

26

1

0*


23

0*

29

47

24

16

0

30


0*

22

43

28

14

25

11

23


2

16

28

20

41

0*

12

25


Основной этап. После второго шага предварительного этапа получим неотрицательную матрицу Экономико-математический практикум, эквивалентную матрице эффективностей Экономико-математический практикум:

П.1. В первом столбце матрицы Экономико-математический практикум отметим звездочкой 0*7,1 ,во втором столбце – 06,2 , в третьем столбце – 04,3, в четвертом столбце – 0*3,4 , в шестом столбце – 08,6, в седьмом столбце – 01,7 , в восьмом столбце – 05,8. Нули в пятом столбце – 04,5 нельзя отметить звездочкой, так как они лежат в строке, в которой уже есть нуль со звездочкой – 04,3,. Число звездочек равно семи, что меньше размерности матрицы (8), переходим к п.2.


D= + + + +
+ + +

7

29

30

1

27

22

0*

17



3

22

15

34

20

25

0’

6



33

12

10

0*

6

24

35

36



17

28

0*

6

0’

17

19

37

+

8

27

9

3

18

26

1

0*



23

0*

29

47

24

16

0’

30



0*

22

43

28

14

25

11

23



2

16

28

20

41

0*

12

25



Экономико-математический практикум ε=2

П.2. Помечаем знаком «+» сверху столбцы: 1, 2, 3, 4,6, 7,8 и считаем эти столбцы занятыми. Незанятый нуль находится в четвертой строке пятого столбца 04,5 , во второй строке и шестой строках седьмого столбца. Помечаем их штрихом 0'4,5 , 0'2,7 , 0'6,7. Переходим к пункту 3.

П.3. Столбец 3 считаем незанятым и знак «+» сверху снимаем (обводим в рамку), а четвертую строку объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу п.2.

П.2. Незанятых нулей нет, переходим к п.5.

П.5. Среди незанятых элементов находим минимальный, который обозначим через Экономико-математический практикум, ε=d3,5=6. Преобразуем матрицу Экономико-математический практикум

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: