Будь умным!


У вас вопросы?
У нас ответы:) SamZan.net

тематики КУРСОВАЯ РАБОТА по дисциплине Прикладная математика

Работа добавлена на сайт samzan.net:

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

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 24.11.2024

30

ГОСУДАРСТВЕННЫЙ   УНИВЕРСИТЕТ   УПРАВЛЕНИЯ

Кафедра прикладной математики

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

по дисциплине «Прикладная математика»

Выполнил(а)    ………………..

Институт     

Отделение    

Курс     II

Группа     ……………….

Руководитель      ……………….

Дата сдачи на проверку ..............................

Дата защиты                   ..............................

Оценка                             ..............................

Подпись руководителя   ..............................

Москва - 2002


Оглавление

[1]
Оглавление

[2]
Линейная производственная задача

[3]
Двойственная задача

[4]
Транспортная задача

[4.0.0.1] Zmin =

[4.0.0.2] Zmin =

[4.0.0.3] Zmin =

[4.0.0.4] Zmin =

[5]
Метод динамического программирования

[6]
Динамическая задача управления производством и запасами

[7]
Матричная модель сотрудничества и конкуренции

[8]
Задача о максимальном потоке в сети

[9]
Список литературы


Линейная производственная задача

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

Сформулировать линейную производственную задачу и составить ее математическую модель.

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

В последней симплексной таблице указать обращенный базис Q-1, соответствующий оптимальному набору базисных неизвестных. Проверить выполнение соотношения

H = Q-1 * B.

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

Исходные данные

Предприятие выпускает 4 вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица A, в которой каждый элемент aij означает необходимое количество i-го ресурса для выпуска j-го вида продукции:

2

0

2

3

А =

1

5

4

2

3

4

0

1

Известен вектор B объемов ресурсов, каждый элемент которого bi означает предельное количество i-го ресурса для выпуска всего объема продукции:

142

В =

100

122

Также известен вектор удельной прибыли C, элементы которого cj означают прибыль от производства единицы продукции j-го вида:

С =

34

20

8

23

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

Решение

Математическая модель задачи: найти производственную программу

1, х2, х3, х4),

максимизирующую прибыль

Z = 34 * х1 + 20 * х2 +  8 * х3 + 23 * х4

при ограничениях по ресурсам

2 * х1

+

2 * х3

+

3 * х4

<=

142

   х1

+

5 * х2

+

4 * x3

+

2 * х4

<=

100

(1)

3 * х1

+

4 * х2

 

 

+

   х4

<=

122

где по смыслу задачи

x1 >= 0; x2 >= 0; x3 >= 0; x4 >= 0

Введя дополнительные неотрицательные неизвестные х5, х6, х7, заменяем неравенства (1) уравнениями вида:

2 * х1

+

2 * х3

+

3 * х4

+

х5

=

142

   х1

+

5 * х2

+

4 * x3

+

2 * х4

+

х6

=

100

3 * х1

+

4 * х2

 

 

+

   х4

+

х7

=

122

Решаем полученную задачу симплексным методом (методом направленного перебора базисных допустимых решений) (см. Таблицу 1).


Таблица 1

34

20

8

23

0

0

0

C

Базис

Hi

х1

х2

х3

х4

х5

х6

х7

0

х5

142

2

0

2

3

1

0

0

0

х6

100

1

5

4

2

0

1

0

0

х7

122

3

4

0

1

0

0

1

z – z0

0

-34

-20

-8

-23

0

0

0

0

х5

182/3

0

-8/3

2

7/3

1

0

-2/3

0

х6

178/3

0

11/3

4

5/3

0

1

-1/3

34

х1

122/3

1

4/3

0

1/3

0

0

1/3

z – z0

4148/3

0

76/3

-8

-35/3

0

0

34/3

23

х4

26

0

-8/7

6/7

1

3/7

0

-2/7

0

х6

16

0

39

18/7

0

-5/7

1

1/7

34

х1

32

1

12

-2/7

0

-1/7

0

3/7

z – z0

1686

0

12

18

0

5

0

8

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

х1 = 32, х2 = 0, х3 = 0, х4 = 26,

а максимальная прибыль равна

Zmax = 1686

При этом 1-й и 3-й ресурсы будут исчерпаны полностью (х5=0, х7=0), а 2-й ресурс будет иметь остаток х6 = 8 единиц.

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

    

3/7

0

-2/7

Q –1  =

-5/7

1

1/7

-1/7

0

3/7

Для того, чтобы убедиться в правильности полученного решения, следует проверить отношение Н = Q-1 * В:

3/7

0

-2/7

142

426/7 – 244/7

26

Q-1 * В =

-5/7

1

1/7

*

100

=

-710/7 + 100 + 122/7

=

16

-1/7

0

3/7

122

-142/7 + 366/7

32

Следовательно, полученное решение верно.

Так как х2 = 0, х3= 0, можно составить математическую модель задачи с двумя переменными (х1 и х4):

Z =

34 * х1

+

23 * х4

->

max

2 * х1

+

3 * х4

<=

142

   х1

2 * x4

<=

100

3 * х1

+

х4

<=

122

Графическое решение такой модели изображено на Рисунке 1.

Рисунок 1

Решая систему двух линейных уравнений, получаем оптимальный результат:

2 * х1

+

3 * х4

=

142

3 * х1

+

х4

=

122

х1

=

32

х3

=

26

Zmax

=

1686

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


Двойственная задача

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

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

Применить найденные двойственные оценки ресурсов к решению следующей задачи.

Сформулировать задачу о расшивке “узких мест” производства и составить математическую модель. Определить область устойчивости двойственных оценок, где сохраняется структура программы производства. Решить задачу о “расшивке узких мест производства” при условии, что дополнительно можно получить от поставщиков не более 1/3 первоначального объема ресурса каждого вида (если задача окажется с двумя переменными, то только графически); найти план приобретения дополнительных объемов ресурсов, дополнительную возможную прибыль.

Исходные данные – см. Задачу 1.

Решение

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

Найти вектор двойственных оценок

1, у2, у3),

минимизирующий общую всех ресурсов

f = 142 * y1 + 100 * y2 + 122 * y3

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


 2 * у1

+

   у2

+

3 * y3

>=

34

5 * у2

+

4 * у3

>=

20

2 * у1

+

4 * y2

 

 

>=

8

3 * у1

+

2 * y2

+

   у3

>=

23

причем оценки ресурсов не могут быть отрицательными

у1 >= 0, у2 >= 0, у3 >= 0.

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

х1 * (

 2 * у1

+

   у2

+

3 * y3

-

34

) = 0

х2 * (

5 * у2

+

4 * у3

-

20

) = 0

х3 * (

2 * у1

+

4 * y2

 

 

-

8

) = 0

х4 * (

3 * у1

+

2 * y2

+

   у3

-

23

) = 0

у1 * (

2 * х1

+

2 * х3

+

3 * х4

-

142

) = 0

у2 * (

   х1

+

5 * х2

+

4 * x3

+

2 * х4

-

100

) = 0

у3 * (

3 * х1

+

4 * х2

 

 

+

   х4

-

122

) = 0

Ранее (см. Задачу 1) было найдено, что в решении исходной  задачи х1>0 и х4>0. Поэтому

 2 * у1

+

   у2

+

3 * y3

-

34

= 0

3 * у1

+

2 * y2

+

   у3

-

23

= 0

Если же учесть, что 2-й ресурс был избыточным и, согласно той же теореме двойственности, его двойственная оценка равна нулю:

y2 = 0

то приходим к системе уравнений

2 * у1

+

3 * y3

-

34

= 0

3 * у1

+

   у3

-

23

= 0

откуда следует

у1 = 5,

у3 = 8.

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

у1 = 5, у2 = 0, у3 = 8,

причем общая оценка всех ресурсов равна

fmin = 1686

Заметим, что это решение содержалось в последней строке симплексной таблицы исходной задачи.

Экономический смысл

Двойственная оценка 1-го ресурса  у1 = 5 показывает, что добавление одной единицы этого ресурса обеспечит прирост прибыли в 5 единиц, двойственная оценка 3-го ресурса у3 = 8 - что добавление одной единицы 3-го ресурса обеспечит прирост прибыли в 8 единиц. Двойственная оценка 2-й технологии D2 = 12 показывает, что если произвести одну единицу продукции 2-го вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 12 единиц, оценка 3-й технологии  D3 = 18 - что производство одной единицы продукции 3-го вида снизит прибыль на 18 единиц.

При выполнении оптимальной производственной программы 1-й и 3-й ресурсы используются полностью, т.е. образуют “узкие места производства”. Будем их заказывать дополнительно. Пусть T(t1, t2, t3) - вектор дополнительных объемов ресурсов.  Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q-1 * T >= 0

Задача состоит в том, чтобы найти вектор

T (t1, t2, t3)

максимизирующий суммарный прирост прибыли

w = 5 * t1 + 8 * t3      (1)

при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

26

3/7

0

-2/7

t1

0

16

+

-5/7

1

1/7

*

0

>=

0

(2)

32

-1/7

0

3/7

t3

0

предполагая, что дополнительно можно надеяться получить дополнительно не более 1/3 первоначального объема ресурса каждого вида

t1

142

0

=<

1/3

*

100

(3)

t3

122

причем по смыслу задачи

t1 >= 0, t3 >= 0   (4)

Переписав неравенства (2) и (3) в виде

-3 * t1

+

 2 * t3

=<

182

5 * t1

-

t3

=<

112

t1

-

3 * t3

=<

224

(5)

t1

=<

47.33

t3

=<

40.67

приходим к задаче линейного программирования: максимизировать (1) при условиях (4), (5).

Эту задачу решаем графическим методом (см. Рисунок 2).

Рисунок 2

Решаем систему уравнений:

5 * t1

-

t3

=

112

t3

=

40.67

Программа “расшивки” имеет вид

t1 = 30.53, t2 = 0, t3 = 40.67

и прирост прибыли составит

w = 478.01

Сводка результатов приведена в Таблице 2.

Таблица 2

cj

30

28

9

23

bi

x4+i

yi

ti

2

0

2

3

142

0

5

30.53

aij

1

5

4

2

100

16

0

0

3

4

0

1

122

0

8

40.67

xj

32

0

0

26

1686

478.01

 D j

0

12

18

0


Транспортная задача

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

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

Исходные данные

 

Стоимости перевозок:

2

7

2

3

1

5

4

2

3

4

6

1

Вектор объемов производства:

А = (80, 60, 30).

Вектор объемов потребления:

В = (34,   40,   38,   53).

Решение

Так как  размеры объемов производства превышают размеры объемов потребления на 5 единиц, вводим фиктивного b5=5 потребителя и определяем первоначальный опорный план методом северо-западного угла:

b1=34

b2=40

b3=38

b4=53

b5=5

a1=80

2

34

7

40

2

6

3

0

a2=60

1

5

 

4

32

2

28

0

a3=30

3

4

6

 

1

25

0

5

Находим оптимальное решение транспортной задачи методом потенциалов.

b1=34

b2=40

b3=38

b4=53

b5=5

a1=80

2

34

-        7

40

+        2

6

3

0

p1 = 0

a2=60

1

+        5

*  

-        4

32

2

28

0

p2 = 2

a3=30

3

4

6

 

1

25

0

5

p3 = 1

q1 = 2

q2 = 7

q3 = 2

q4 = 0

q5 = -1

D21 = 3

D22 = 4

D33 = -3

D14 = -3

D15 = -1

D31 = 0

D32 = 4

D25 = 1

Zmin =

565

b1=34

b2=40

b3=38

b4=53

b5=5

a1=80

2

34

-       7

8

2

38

3

+       0

*

p1 = 0

a2=60

1

+       5

 32

4

-       2

28

0

p2 = -2

a3=30

3

4

6

 

+       1

25

-       0

5

p3 = -3

q1 = 2

q2 = 7

q3 = 2

q4 = 4

q5 = 3

D21 = -1

D32 = 0

D13 = -4

D14 = 1

D15 = 3

D31 = -4

D33 = -7

D25 = 0

Zmin =

441

b1=34

b2=40

b3=38

b4=53

b5=5

a1=80

2

34

-       7

3

2

38

+       3

*

0

5

p1 = 0

a2=60

1

+       5

 37

4

-       2

23

0

p2 = -2

a3=30

3

4

6

 

1

30

0

p3 = -3

q1 = 2

q2 = 7

q3 = 2

q4 = 4

q5 = 0

D21 = 0

D32 = 0

D23 = -4

D14 = 1

D25 = -2

D31 = -4

D33 = -7

D35 = -3

Zmin =

426


b1=34

b2=40

b3=38

b4=53

b5=5

a1=80

2

34

7

2

38

3

3

0

5

p1 = 0

a2=60

1

5

 40

4

2

20

0

p2 = -1

a3=30

3

4

6

 

1

30

0

p3 = -2

q1 = 2

q2 = 6

q3 = 2

q4 = 3

q5 = 0

D21 = 0

D12 = -1

D23 = -3

D25 = -1

D31 = -3

D32 = 0

D33 = -6

D35 = -2

Zmin =

423

Все потенциалы свободных клеток Dij неположительные, следовательно, решение, представленное в последней таблице, является оптимальным, причем минимальная стоимость всех перевозок составляет 423 единицы.


Метод динамического программирования

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

Методом динамического программирования решить задачу распределения капитальных вложений между четырьмя предприятиями производственного объединения, располагающего суммой в 700 тыс. руб. (выделяемые суммы кратны 100 тыс. руб.).

Исходные данные

Значения функции fjj) приведены в Таблице 1 (считаем их заданными, их определение - довольно трудоемкая экономическая задача):

Таблица 1

xj

0

100

200

300

400

500

600

700

f1(xj)

0

20

33

42

48

53

56

58

f2(xj)

0

22

37

49

59

68

76

82

f3(xj)

0

10

29

42

52

60

65

69

f4(xj)

0

16

27

37

44

48

50

56

Решение

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

Введем параметр состояния x - количество рублей, выделяемых нескольким предприятиям, и определим функцию состояния Fk(x) - максимальная прибыль на первых k предприятиях, если они вместе получат хk  рублей.

Табулируя последовательно функции  Fk(x), получим решение, ход которого приведен в Таблицах 2-6.


Таблица 2

 x2

0

100

200

300

400

500

600

700

х2

F(x-x2)

f2(x2)

0

20

33

42

48

53

56

58

0

0

0

20

33

42

48

53

56

58

100

22

22*

42*

55

64

70

75

78

200

37

37

57*

70*

79

85

90

300

49

49

69

82*

91

97

400

59

59

79

92*

101*

500

68

68

88

101*

600

76

76

96

700

82

82

Таблица 3

x

0

100

200

300

400

500

600

700

F2(x)

0

22

42

57

70

82

92

101

x2(x)

0

100

100

200

200

300

400

400/500

Таблица 4

 x3

0

100

200

300

400

500

600

700

х3

F(x-x3)

f3(x3)

0

22

42

57

70

82

92

101

0

0

0*

22*

42*

57*

70

82

92

101

100

10

10

32

52

67

80

92

102

200

29

29

51

71*

86*

99*

111

300

42

42

64

84

99*

112*

400

52

52

74

94

109

500

60

60

82

102

600

65

65

87

700

69

69

Таблица 5

x

0

100

200

300

400

500

600

700

F2(x)

0

22

42

57

71

86

99

112

x2(x)

0

0

0

0

200

200

200/300

300


Таблица 6

  x4

0

100

200

300

400

500

600

700

х4

F(x-x4)

f4(x4)

0

22

42

57

71

86

99

112

0

0

112

100

16

115*

200

27

113

300

37

108

400

44

101

500

48

90

600

50

72

700

56

56

Zmax = 115 тыс. руб.,

причем четвертому предприятию должно быть выделено

х4* = х4(700) = 100 тыс. руб.

На долю остальных трех предприятий остается 600 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено

  1.  х3* = х3(700 - х4*) = х3(600) = 200 тыс. руб.
  2.  х3* = х3(700 - х4*) = х3(600) = 300 тыс. руб.

Продолжая обратный процесс, находим

  1.  х2* = х2(700 - х4* - х3*) = х2(400) = 200 тыс. руб.
  2.  х2* = х2(700 - х4* - х3*) = х2(300) = 200 тыс. руб.

На долю первого предприятия останется

  1.  х1* = 700 - х4* - х3* - х2* = 200 тыс. руб.
  2.  х1* = 700 - х4* - х3* - х2* = 100 тыс. руб.

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

  1.  х1* = 200; х2* = 200; х3* = 200; х4* = 100
  2.  х1* = 100; х2* = 200; х3* = 300; х4* = 100

Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 115 тыс. руб.

В качестве проверки правильности решения задачи можно использовать равенство

f1(x1*) + f2(x2*) + f3(x3*) + f4(x4*) = Zmax

  1.  f1(200) + f2(200) + f3(200) + f4(100)  = 33 + 37 + 29 + 16 = 115 = Zmax
  2.  f1(100) + f2(200) + f3(300) + f4(100)  = 20 + 37 + 42 + 16 = 115 = Zmax

Следовательно, полученные решения верны.


Динамическая задача управления производством и запасами

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

Рассмотреть динамическую задачу управления производством и запасами.

Исходные данные

Спрос (заявки) потребителей на продукцию составляют: на первый этап d1 = 5 единиц, на второй –  d2 = 1, на третий -  d3 = 2 единицы. К началу первого этапа на складе имеется только 4 единицы продукции, т.е. начальный уровень запаса равен y1=4. Затраты на хранение единицы продукции на разных этапах различны  и составляют соответственно h1 = 2, h2 = 1, h3 = 1. Затраты на производство xj единиц продукции на j-м этапе определяются функцией

j(xj) = 2 * xj2 +  6      (1)

т.е. а = 2; b = 0; с = 6. Требуется указать, сколько единиц продукции на отдельных этапах следует производить, чтобы заявки потребителей были удовлетворены, а общие затраты на производство и хранение за все три этапа были наименьшими.

Решение

Воспользовавшись  рекурентными  соотношениями,   последовательно   вычисляем F1 ( = y2),  F2 ( = y3), ...,  Fk ( = yk+1), ...    и  соответственно  находим   1 (= y2), 2 ( = y3 ), ..., k ( = yk+1), ...

Положим k = 1. Тогда имеем

F1(= y2) = min{2 * xj2 + 6 + 2 * y2}    (2)

Учтем, что параметр состояния = у2 может принимать целые значения на отрезке

0  у2  d2 + d3

0  y2  3

т.е.

у2 = 0, 1, 2, 3

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

0  х1  d1 + у2

0  х1  5 + у2

Из балансового уравнения

х1 + у1 - d1 = у2

непосредственно следует, что объем производства связан со значением параметра состояния  = у2 соотношением

 x1 =  y2 + d1 - y1 = y2 + 5 - 4 = y2 + 1  (3)

Каждому значению у2 отвечает единственное значение х1 и потому

F1( = y2) = 1 (x1, y2)

Придавая у2 различные целые значения от 0 до 3 и учитывая (3), находим

y2 = 0, x1 = 1, 1 (1;0) = 2 * 12  + 6 + 2 * 0 =   8

y2 = 1, x1 = 2, 1 (2;1) = 2 * 22  + 6 + 2 * 1 = 16

y2 = 2,  x1 = 3, 1 (3;2) = 2 * 32  + 6 + 2 * 2 = 28

y2 = 3,  x1 = 4, 1 (4;3) = 2 * 42  + 6 + 2 * 3 = 44

Значения функции состояния F1() представлены в Таблице 1.

                                                                                                Таблица 1

= y2

0

1

2

3

F1 ( = y2)

8

16

28

44

x1(=y2)

1

2

3

4

Переходим ко второму этапу. Полагаем k = 2 и табулируем функцию F2( = y3):

F2( = y3) = min 1 (x1, y2) = min{a * x22 + b * x2 + c + h2 * y3 + F1(y2)} =  

= min {2 * x22 + 6 + y3 + F1(y2)}                       (4)

Здесь минимум берется по единственной переменной х2, которая может изменяться в пределах

0 x2  d2 + y3    или    0 x2  1 + y3             (5)

где верхняя граница зависит от параметра состояния = у3, который принимает значения на отрезке

0  y3  d3 ,    т.е.   0  y3  2     (6)

а аргумент у2 в последнем слагаемом справа в соотношении (4) связан с х2 и у3 балансовым уравнением

x2 + y2 - d2 = y3

откуда следует

y2 = y3 + d2 - x2 = y3 + 1 - x2              (7)

Придавая параметру состояния различные значения от 0 до 2, будем последовательно вычислять  2 (x2, ), а затем определять F2( ) и 2( ).

Положим = у3 = 0. Тогда, согласно (5),

0 x2  1,

т.е. переменная х2 может принимать значения 0, 1, которым отвечает значение у2, вычисляемое по формуле (7):

у2 = 1 - х2 

Последовательно находим:

x2 = 0, y2 = 1 - 0 = 1, 2 (0,0) = 2 * 02 + 6 + 0 + F1(1) = 6 + 16 = 22

x2 = 1, y2 = 1 - 1 = 0, 2 (1,0) = 2 * 12 + 6 + 0 + F1(0) = 8 +   8 = 16*

Наименьшее из полученных значений 2 есть F2 (0), т.е.

F2 ( = y3 = 0) = min 2 (x2,0) = min (22, 16) = 16,

                  x2

причем минимум достигается при значении х2, равном

2 ( = y3 = 0) = 1

Положим = у3 = 1. Тогда, согласно (5),

0 x2  2,

т.е. переменная х2 может принимать значения: 0, 1, 2, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (7):

у2 = 2 - х2

Последовательно находим:

x2 = 0, y2 = 2 - 0 = 2, 2 (0,1) = 2 * 02 + 6 + 1 + F1(2) =    7 + 28 = 35

x2 = 1, y2 = 2 - 1 = 1, 2 (1,1) = 2 * 12 + 6 + 1 + F1(1) =    9 + 16 = 25

x2 = 2, y2 = 2 - 2 = 0, 2 (2,1) = 2 * 22 + 6 + 1 + F1(0) =  15 +   8 = 23*

Наименьшее из полученных значений 2 есть F2 (1), т.е.

F2 ( = y3 = 1) = min 2 (x2,1) = min (35, 25, 23) = 23,

                   x2

причем минимум достигается при значении х2, равном

2 ( = y3 = 1) = 2

Положим = у3 = 2. Тогда, согласно (5),

0 x2  3,

т.е. переменная х2 может принимать значения: 0, 1, 2, 3, а каждому значению х2 отвечает определенное значение у2, вычисляемое по формуле (7):

у2 = 3 - х2

Последовательно находим:

x2 = 0, y2 = 3 - 0 = 3, 2 (0,2) = 2 * 02 + 6 + 2 + F1(3) =   8 + 44 = 52

x2 = 1, y2 = 3 - 1 = 2, 2 (1,2) = 2 * 12 + 6 + 2 + F1(2) = 10 + 28 = 38

x2 = 2, y2 = 3 - 2 = 1, 2 (2,2) = 2 * 22  + 6 + 2 + F1(1) = 16 + 16 = 32*

x2 = 3, y2 = 3 - 3 = 0, 2 (3,2) = 2 * 32 + 6 + 2 + F1(0) = 26 +   8 = 34

Наименьшее из полученных значений 2 есть F2 (2), т.е.

F2 ( = y3 = 2) = min 2 (x2,2) = min (52, 38, 32, 34) = 32,

             x2

причем минимум достигается при значении х2, равном

2 ( = y3 = 2) = 2

Результаты табулирования функции F2( = y3) сведены в Таблице 2.

Таблица 2

= у3

0

1

2

F2 (= y3)

16

23

32

(= y3)

1

2

2

Переходим к следующему этапу. Полагаем k=3 и табулируем функцию F3 ( = y4):

F3 ( = y4) = min{a * x32 + b * x3 + c + h3 * y4 + F2(y3)} =

= min{2 * x32 + 6 + y4 + F2(y3)}

Вычисляем значение функции состояния только для одного значения аргумента = у4 = 0, так как не имеет смысла оставлять продукцию в запас в конце исследуемого периода.

Тогда, согласно (5),

0 x3  2,

т.е. переменная х3 может принимать значения: 0, 1, 2, а каждому значению х3 отвечает определенное значение у3, вычисляемое по формуле (7):

у3 = 2 - х3 

Последовательно находим:

x3 = 0, y3 = 2 - 0 = 2, 2 (0,0) = 2 * 02 + 6 + 0 + F2(2) =   6 + 32 = 38

x3 = 1, y3 = 2 - 1 = 1, 2 (1,0) = 2 * 12 + 6 + 0 + F2(1) =   8 + 23 = 31

x3 = 2, y3 = 2 - 2 = 0, 2 (2,0) = 2 * 22 + 6 + 0 + F2(0) = 14 + 16 = 30*

Получаем

F3 ( = y4) = min 3 (x3,0) = min (38, 31, 30) = 30,

                                    x3

причем минимум достигается в двух значениях  переменной х3

  3 ( = y4 = 0) = 2

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

x3* = 2

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

х3 + у3 - d3 = y4

2 + у3 - 2 = 0,

у3 = 0,

Из   таблицы 2 значений  находим

x2*= 2 ( = y3 = 0) = 1

Аналогично, продолжая двигаться в обратном направлении и учитывая, что

х2 + у2 - d2 = y3

1 + у2 - 1 = 0,

у2 = 0

                                                                  

из таблицы (1) значений х1() находим

x1*= 1 ( = y2 = 0) = 1

Итак, оптимальный план производства имеет вид

х1 = 1

х2 = 1

х3 = 2

а минимальные общие затраты составляют 30 единиц.


Проверка полученного результата

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

 у1 + х1  d1  у2 + х2  d2  у3 + х3  d3 

 4  + 1    5  0  + 1    1  0  + 2    2

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

у1 + х1 + х2 + х3 = d1 + d2 + d3

4 + 1 + 1 + 2 = 5 + 1 + 2

8 = 8

причем это достигается при наименьших возможных затратах на производство и хранение продукции

1) + 2) + 3) + h1у2 + h2у3 = F3(y4=0)

8 + 8 + 14 + 2 * 0 + 1 * 0 = 30

30 = 30


Матричная модель сотрудничества и конкуренции

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

Рассмотреть матричную игру как модель сотрудничества и конкуренции. Найти графическое решение игры. Указать, как проявляется конкуренция между игроками и сотрудничество между ними.

Исходные данные

1

2

4

0

2

0

-2

3

Решение

Сведем данный случай матричной игры (2*4) к анализу игры 2*2. Для этого необходимо графическое решение (см. Рисунок 3).

Рисунок 3

Как видно из Рисунка 3, данная матричная игра сводится к варианту

0

2

3

0

Рассчитаем оптимальные стратегии игроков P* и Q*:


p*1 = (a22 - a21) / (a11 + a22 - a12 - a21) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5

p*2 = (a11 - a12) / (a11 + a22 - a12 - a21) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5

q*1 = (a22 - a12) / (a11 + a22 - a12 - a21) = (0 - 2) / (0 + 0 – 2 – 3) = 2/5

q*2 = (a11 - a21) / (a11 + a22 - a12 - a21) = (0 - 3) / (0 + 0 – 2 – 3) = 3/5

P* = (3/5, 2/5)

Q* = (2/5, 3/5)

Рассчитаем цену игры v:

n     m

v = S  S aij * pi * qj = 0 * 3/5 * 2/5 + 3 * 2/5 * 2/5 + 2 * 3/5 * 3/5 + 0 * 2/5 * 3/5 = 6/5

j=1 i=1

Рассчитаем среднюю дисперсию и риск:

  n    m                                     n    m                                       n    m

D* = S  S aij2 * p*i * q*j - (S  S aij * p*i * q*j)2 = S  S aij2 * p*i * q*j - v2 =

j=1 i=1                                     j=1 i=1                                         j=1 i=1

= 0 * 3/5 * 2/5 + 9 * 2/5 * 2/5 + 4 * 3/5 * 3/5 + 0 * 2/5 * 3/5 – 36/25 = 36/25

r = Ö D* = Ö 36/25 = 6/5 = 1.2

Рассчитаем риски игры r для Первого  и Второго игроков:

             n

Dj = S ai2 * p*i - v2

           i=1

D1 = 0 * 3/5 + 9 * 2/5 – 36/25 = 54/25

D2 = 4 * 3/5 + 0 * 2/5 – 36/25 = 24/25

r1(1) = Ö 54/25 = 1.47

r1(2) = Ö 24/25 = 0.98

Зависимость риска Первого в малой окрестности его оптимальной стратегии показана на Рисунке 4.

r1(2) = 0.98                   r = 1.2                      r1(1) = 1.47

6/5

Рисунок 4

Как видно из Рисунка 4, при отходе Первого от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-ой строки, Второй отвечает своей 1-ой чистой стратегией и риск Первого скачком увеличивается до r1(1) = 1.47, а при отходе Первого от своей оптимальной стратегии влево Второй отвечает своей 2-ой чистой стратегией и риск Первого скачком снижается до r1(2) = 0.98.

Аналогично - в отношении второго:

             n

Di = S aj2 * q*j - v2

           j=1

D1 = 0 * 2/5 + 4 * 3/5 – 36/25 = 24/25

D2 = 9 * 2/5 + 0 * 3/5 – 36/25 = 54/25

r2(1) = Ö 24/25 = 0.98

r2(2) = Ö 54/25 = 1.47

Зависимость риска Второго в малой окрестности его оптимальной стратегии показана на Рисунке 5.

r2(1) = 0.98                      r = 1.2                      r2(2) = 1.47

6/5

Рисунок 5

Как видно из Рисунка 5, при отходе Второго от своей оптимальной стратегии вправо, т.е. при увеличении вероятности выбора им 1-го столбца, Первый отвечает своей 2-ой чистой стратегией и риск Второго скачком увеличивается до r2(2) = 1.47, а при отходе Второго от своей оптимальной стратегии влево его риск скачком снижается до r2(1) = 0.98.

Величина r* = min(r1(1), r1(2), r2(1), r2(2)) - риск всей игры.

r* = min(1.47, 0.98, 0.98, 1.47) = 0.98.

С таким риском можно играть только при сотрудничестве обеих сторон. Для достижения такого риска игроки должны играть следующим образом: Первый игрок использует свою оптимальную стратегию P*(3/5, 2/5), а Второй отвечает своей 2-ой чистой стратегией, либо Второй игрок использует свою оптимальную стратегию Q*(2/5, 3/5), а Первый отвечает своей 1-й чистой стратегией.


Задача о максимальном потоке в сети

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

Рассмотреть задачу о максимальном потоке в сети. Решить конкретную задачу на сети с 8-9 вершинами.

Исходные данные

Определить максимальный поток в сети, изображенной на Рисунке 6 из вершины x0 в вершину x8, где числа на дугах, снабженные стрелками, означают пропускные способности этих дуг в указанных направлениях.

Рисунок 6

Решение

Составим матрицу пропускных способностей дуг данной сети и представим сеть в матричной форме (см. Таблицу 1).


Таблица 1

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

4

2-

x1

1

5

x2

3

x3

+

5

1

6-

x4

2

5

x5

4

1

3

x6

2

8

x7

+

5

2

В качестве начального возьмем нулевой поток z0ij = 0. Найдем какой-нибудь путь, идущий из x0 в x7 по ненасыщенным дугам. Для этого в нулевой строке таблицы выберем какой-нибудь элемент cij, отличный от нуля, например c03. Из вершины x0 можно перейти в x3. Для наглядности дугу (x0, x3) проведем прямо в нулевой строке таблицы из нулевого столбца в 3-й. Теперь мы находимся в вершине x3. Чтобы зафиксировать это, сместимся по пятому столбцу до строки с тем же 3-м номером. В 3-й строке имеется 3 ненулевых элемента соответственно в 4-м, 5-м и 7-м столбцах. Это означает, что из x3 можно перейти или в x4, в x5 или в x7. Пойдем в сток x7. Этот переход изображен стрелкой в 3-й строке с началом в 3-м столбце и концом в 7-м. Таким образом, по таблице пропускных способностей дуг сети мы нашли путь, ведущий по ненасыщенным дугам из источника в сток:

m1 = [x0, x3, x7].

Теперь по таблице надо узнать пропускную способность q1 найденного пути и уменьшить пропускные способности всех дуг этого пути на q1, а симметричных им дуг – увеличить на q1. Для этого отмечаем знаком «-» числа в тех клетках, где находятся концы дуг, а числа в клетках, симметричных указанным относительно главной диагонали, отмечаем знаком «+». Пропускная способность найденного пути, очевидно, равна наименьшему среди чисел, отмеченных знаком «-» (Таблица 1).

q1 = 2

Из всех чисел, отмеченных знаком «-», вычитаем наименьшую пропускную способность q1. Получаем Таблицу 2. Это – сеть с измененными пропускными способностями дуг.


Таблица 2

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

4-

x1

1

5

x2

+

3-

x3

2

5

1

4

x4

2+

5-

x5

4

1

3

x6

2

8

x7

2

5+

2

Ищем новый путь, идущий из источника в сток по ненасыщенным дугам и процедуру повторяем. Получаем путь m2 и пропускную способность q2:

m2 = [x0, x2, x4, x7]

q2 = 3

Далее

Таблица 3

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2-

1

x1

+

1

5-

x2

3

x3

2

5

1

4

x4

5

2

x5

4+

1

3-

x6

2+

8-

x7

2

8

2+

m3 = [x0, x1, x5, x6, x7]

q3 = 2


Таблица 4

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

1

x1

2

1

3

x2

3

x3

2

5

1

4

x4

5

2

x5

6

1

1

x6

4

6

x7

2

8

4

Из Таблицы 4 видно, что не существует ни одного пути из источника в сток. (Из x0 можно перейти только в x2, а оттуда – обратно в x0). Следовательно, увеличить поток нельзя.

Для определения величины полученного максимального потока вычитаем из элементов Таблицы 1 соответствующие элементы Таблицы 4. Записывая только положительные из найденных разностей, получаем Таблицу 5, указывающую максимальный поток в заданной сети с величиной

w* = z37 + z47 + z67 = q1 + q2 + q3 = 7

Таблица 5

xj

xi

x0

x1

x2

x3

x4

x5

x6

x7

x0

2

3

2

x1

2

x2

3

x3

2

x4

3

x5

2

x6

2

x7


Список литературы

Карандаев И.С. и др. Математические методы исследования операций в примерах и задачах: Учебное пособие / ГАУ. М., 1993, 72 с.

Карандаев И.С., Юнисов Х.Х. Прикладные задачи исследования операций. Учебное пособие для студентов всех специальностей. М.: МИУ имени Серго Орджоникидзе. – 79 с.

Математические методы принятия решений в экономике: Учебник / Под ред. В.А. Колемаева / ГУУ. – М.: ЗАО «Финстатинформ», 1999. – 386 с.

Методические указания к выполнению курсовой работы по дисциплине “Прикладная математика” / Сост.: Колемаев В.А., Карандаев И.С., В.И. Малыхин, Т.М. Гатауллин, Ю.Г. Прохоров, Х.Х. Юнисов; ГУУ, М., 2000. 73 с.


x

x

0

x

2

x

1

3

x

4

x

5

x

6

x

7

2

0

5

4

3

2

8

2

6

0

1

1

1

0

2

0

4

0

3

2

5

5

5

0




1. Вирусные заболевания приматов
2. Суды и судоустройство
3. Особенности применения правового института купли-продажи в отношении земельных участков
4. Зверинец Джемрака был номинирован на премию Ornge Prize for Fiction и вошел в шортлист Mn Booker Prize за 2011 год
5. лекция доц.Папин М.html
6. Лингвистический аспект светскости
7. Сфери проникнення англіцизмів в інші мови - російську, українську
8. Отрасли права- понятие и виды
9. Интерьер с~зіні~ ма~ынасы ~имаратты~ ішін ~р т~рлі жолмен стильмен ~рлендіру ~Р ~она~ ~й ~ызметін пайд
10. Из дневника Философия жизни Иосипа Видмара Миф и действительность От кубизма к абстракции Феномен
11. реферату- Гендерні проблеми у засобах масової інформації управлінський аспектРозділ- Менеджмент Гендерні
12. Сущность, виды и роль денег в современной экономике
13. на тему- Финансовый анализ деятельности ОАО Уралкалий за 20112012 год Выполнила- студентка 4 курс
14. МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ ДЛЯ ОБУЧАЮЩИХСЯ по дисциплине онкология для специальности 060101 ~ Лечебное д
15. Курсовая работа- Личные подсобные хозяйств
16. Физика для студентов всех специальностей вуза Утверждено на заседании ученого совета ДГ
17. Технология превращения мечты в цель или как выбрать хорошую профессию является эффективным ИНСТРУМЕНТОМ
18. Трофическая структура и экологические пирамиды
19. Пежо я чертыхаясь вглядывалась в шоссе
20. Три основы и их доказательстваДа вознаградит его Аллах за его трудКонспект подготовила наша сестра Умму А