Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Курсовая работа - Разработка управленческих решений - файл РУР.doc


Курсовая работа - Разработка управленческих решений
скачать (61.5 kb.)

Доступные файлы (1):

РУР.doc534kb.29.07.2011 23:35скачать

содержание

РУР.doc

  1   2   3
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ВОЛГО-ВЯТСКАЯ АКАДЕМИЯ ГОСУДАРСТВЕННОЙ СЛУЖБЫ


Факультет ускоренного обучения и магистерской подготовки

Кафедра математики и системного анализа


КУРСОВАЯ РАБОТА


по дисциплине «Разработка управленческих решений»





Выполнил (а): студент



Проверил: научный руководитель

г. Нижний Новгород

2010г.


Решение задачи графическим способом

Задача. Для производства двух видов изделий А и В разных по сложности их изготовления, швейная фабрика «Маяк» использует четыре вида сырья (I, II, III, IV). Условия задачи приведены в таблице. Необходимо составить такой план выпуска изделий, при котором его будут изготавливать определенное количество рабочих за минимальное количество времени.




Вид сырья

Норма расхода

Общее количество сырья, м

А

В

I

2

-1

4

II

-1

1

2

III

3

-2

0

IV

1

-1

0

Время изготовления, мин.

3

-1





Решение:

  1. Составим экономико-математическую модель задачи.

Обозначим: x1 – количество рабочих изготавливаемых изделие А;

x2 - количество рабочих изготавливаемых изделие В.
Тогда система ограничений имеет следующий вид:

2x1 – x2 ≤ 4,

- x1 + x2 ≤ 2,

3x1 - 2x2 ≥ 0,

x1 – x2 ≤ 0;
Целевая функция:

Z(X) = 3x1 – x2 → min

2.Построим многоугольник допустимых решений.


ОАВСD – область допустимых решений. Строим вектор с координатами (3; -1) и перпендикулярную ему линию равную 0. Перемещаем линию уровня по направлению вектора и находим последнюю точку касания линии уровня с областью допустимых решений. Из графика видно, что такой точкой является точка С, найдем ее координаты:

2x1 – x2 ≤ 4,

- x1 + x2 ≤ 2;
Решая систему получаем координаты точки С (6, 8), в которой и будет оптимальное решение, т. е. :

X = (6, 8)

При этом

Zmin = 3 ∙ 6 + 8 = 10

Ответ: Из решения задачи получаем, что 6 рабочих изготавливают изделие А, а 8 рабочих изделие В, т. к. оно более сложное, при этом оба изделия должны быть выполнены за 10 минут.


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

Найти оптимальное решение Венгерским методом


  1. Найдем минимальные элементы в строках и столбцах:

  1. минимальные элементы по строкам:

min

0

4

8

5

7

5

2

0

4

8

6

7

8

4

6

4

1

5

24

8

8

11

6

1

2

2

6

14

6

7

2

2

6

2

14

4

3

8

7

2

4

2

4

8

9

13

10

2

7

21

2

9

14

16

3

2



  1. вычитаем min из каждого элемента по строке и ищем min по столбцам:




0

4

8

5

7

5

2

0

4

2

3

4

0

2

0

4

23

7

7

10

5

0

0

4

12

4

5

0

4

0

12

2

1

6

5

2

0

2

6

7

11

8

5

19

0

7

12

14

1

0

0

0

2

1

0

0



  1. вычитаем min из каждого элемента по столбцам:




0

4

8

3

6

5

2

0

4

2

1

3

0

2

0

4

23

5

6

10

5

0

0

4

10

3

5

0

4

0

12

0

0

6

5

2

0

2

4

6

11

8

5

19

0

5

11

14

1




  1. Найдем строку, в которой содержится одно нулевое значение, выделим его, а нули, оставшиеся в столбце зачеркнем:




0

4

8

3

6

5

2

0

4

2

1

3

0

2

0

4

23

5

6

10

5

0

0

4

10

3

5

0

4

0

12

0

0

6

5

2

0

2

4

6

11

8

5

19

0

5

11

14

1



Суммируем клетки, соответствующие выбранным элементам итоговой таблицы. Получаем:

0+4+1+2+4+2+2=15 – минимальное решение данной задачи.

^ Решение транспортной задачи методом потенциалов.
Стоимость поставки единицы груза из одного пункта отправления в другие пункты назначения задана следующей матрицей расценок:

29

53

39

29

22

33

15

33

16

3

3

18

16

27

16

3

5

32

35

50

39

20

23

17

20

20

20

20

20




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

Σa = 33+18+32+17 = 100

Σb = 20+20+20+20+20=100

Условие баланса соблюдены.
2. Используя метод наименьшей стоимости, строим первый опорный план транспортной задачи.



1

2

3

4

5

a

1


29(10)

53(3)

39(20)

29

22

33

2


15

33

16

3(18)

3

18

3


16(10)

27

16

3(2)

5(20)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





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

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




v1=29

v2=53

v3=39

v4=16

v5=18

u1=0


29(10)

53(3)

39(20)

29

22

u2=-13


15

33

16

3(18)

3

u3=-13


16(10)

27

16

3(2)

5(20)

u4=-3


35

50(17)

39

20

23


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

(2;1): -13 + 29 > 15

(2;2): -13 + 53 > 33

(2;3): -13 + 39 > 16

(2;5): -13 + 18 > 3

(3;2): -13 + 53 > 27

(3;3): -13 + 39 > 16

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

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



1

2

3

4

5

a

1


29(10)[+]

53(3)[-]

39(20)

29

22

33

2


15

33

16

3(18)

3

18

3


16(10)[-]

27[+]

16

3(2)

5(20)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





Наименьшее значение в минусовых клетках в клетке (1, 2) = 3. Прибавим 3 к объемам грузов, стоящих в плюсовых клетках и вычтем 3 из xij, стоящих в минусовых клетках. После чего получим новый опорный план.



1

2

3

4

5

a

1


29(13)

53

39(20)

29

22

33

2


15

33

16

3(18)

3

18

3


16(7)

27(3)

16

3(2)

5(20)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





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



v1=29

v2=40

v3=39

v4=16

v5=18

u1=0


29(13)

53

39(20)

29

22

u2=-13


15

33

16

3(18)

3

u3=-13


16(7)

27(3)

16

3(2)

5(20)

u4=10


35

50(17)

39

20

23


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

(2;1): -13 + 29 > 15

(2;3): -13 + 39 > 16

(2;5): -13 + 18 > 3

(3;3): -13 + 39 > 16

(4;1): 10 + 29 > 35

(4;3): 10 + 39 > 39

(4;4): 10 + 16 > 20

(4;5): 10 + 18 > 23

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

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



1

2

3

4

5

a

1


29(13)[+]

53

39(20)[-]

29

22

33

2


15

33

16[+]

3(18)[-]

3

18

3


16(7)[-]

27(3)

16

3(2)[+]

5(20)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





Наименьшее значение в минусовых клетках в клетке (3, 1) = 7. Прибавем 7 к объемам грузов, стоящих в плюсовых клетках и вычтем 7 из xij, стоящих в минусовых клетках. Получаем новый опорный план.



1

2

3

4

5

a

1


29(20)

53

39(13)

29

22

33

2


15

33

16(7)

3(11)

3

18

3


16

27(3)

16

3(9)

5(20)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





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



v1=29

v2=50

v3=39

v4=26

v5=28

u1=0


29(20)

53

39(13)

29

22

u2=-23


15

33

16(7)

3(11)

3

u3=-23


16

27(3)

16

3(9)

5(20)

u4=0


35

50(17)

39

20

23

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

(1;5): 0 + 28 > 22

(2;5): -23 + 28 > 3

(4;4): 0 + 26 > 20

(4;5): 0 + 28 > 23

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

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



1

2

3

4

5

a

1


29(20)

53

39(13)[-]

29

22[+]

33

2


15

33

16(7)[+]

3(11)[-]

3

18

3


16

27(3)

16

3(9)[+]

5(20)[-]

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20





Наименьшее значение в минусовых клетках в клетке (2, 4) = 11. Прибавим 11 к объемам грузов, стоящих в плюсовых клетках и вычитаем 11 из xij, стоящих в минусовых клетках. Получаем новый опорный план.



1

2

3

4

5

a

1


29(20)

53

39(2)

29

22(11)

33

2


15

33

16(18)

3

3

18

3


16

27(3)

16

3(20)

5(9)

32

4


35

50(17)

39

20

23

17

b


20

20

20

20

20



  1   2   3



Скачать файл (61.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации