Определение оптимального плана перевозок. Решение матричной игры

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

Рубрика Экономико-математическое моделирование
Вид контрольная работа
Язык русский
Дата добавления 09.05.2013
Размер файла 159,9 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Практическое задание

по математике в экономике

Выполнила:

Студентка 2 курса, №120009

Зверева А. В.

Факультет микроэкономики и маркетинга

НИМБ 2012

Задание 1

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

(x)= - x1 -x3 -x5>min

Решение:

Приведем задачу к каноническому виду:

В начальный базис войдут вектора A6 и А7 при переменных х6 и х7 соответственно. Симплекс-таблица имеет вид:

1

0

1

0

1

0

0

-

базис

Сб

В

А1

А2

А3

А4

А5

А6

А7

bi/aij

А6

0

6

1

2

3

-1

-1

1

0

6

А7

0

5

1

-1

-2

1

1

0

1

5

0

-1

0

-1

0

-1

0

0

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

1

0

1

0

1

0

0

базис

Сб

В

А1

А2

А3

А4

А5

А6

А7

bi/aij

А6

0

1

0

3

5

-2

-2

1

-1

1/5

А1

1

5

1

-1

-2

1

1

0

1

-

5

0

-1

-3

-1

-2

0

1

Так как оценки при векторах А2, А3, А4 и А5 отрицательные, то полученное решение является не оптимальным. Минимальная отрицательная оценка соответствует вектору А3, следовательно, он войдет в базис в следующей симплекс-таблице вместо вектора А6.

1

0

1

0

1

0

0

базис

Сб

В

А1

А2

А3

А4

А5

А6

А7

bi/aij

А3

1

1/5

0

3/5

1

-2/5

-2/5

1/5

-1/5

-

А1

1

27/5

1

1/5

0

1/5

1/5

2/5

3/5

27

28/5

0

4/5

0

-1/5

-6/5

3/5

2/5

Так как оценки при векторах А4 и А5 отрицательные, то полученное решение является не оптимальным. Минимальная отрицательная оценка соответствует вектору А5, следовательно, он войдет в базис в следующей симплекс-таблице вместо вектора А1.

1

0

1

0

1

0

0

базис

Сб

В

А1

А2

А3

А4

А5

А6

А7

А3

1

11

2

1

1

0

0

1

1

А5

1

27

5

1

0

1

1

2

3

38

6

2

0

1

0

3

4

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

Координаты точки минимума .

Минимальное значение целевой функции .

Задание 2

Имеется 3 пункта (А12, А3), производства и 4 пункта (В1, В2, В3, В4), его потребления. На пункте Аj (j =1…3) находится аj условных единиц товара. В пункте Вj (j =1…4) условных единиц товара. Стоимость перевозок между производителями и потребителями (в условных денежных единицах) задается матрицей D. Найти план перевозок, при котором затраты на перевозки были бы минимальны.

аj= 300,а2=450, а3=400

b1=310, b2=250, b3=150,b4=440

D=

Решение:

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

Потребители

Запасы

Производители

В1

В2

В3

В4

А1

10

5

6

6

300

А2

12

7

8

6

450

А3

11

6

7

10

400

Потребности

310

250

150

440

Проверим, является ли транспортная задача закрытой (равна ли сумма потребностей сумме запасов).

Сумма потребностей = 310 + 250 + 150 + 440 = 1150

Сумма запасов = 300 + 450 + 400 = 1150

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

Потребители

Запасы

Производители

В1

В2

В3

В4

А1

10

5 250

6 50

6

300 / 50 / 0

А2

12 10

7

8

6 440

450 / 10 / 0

А3

11 300

6

7 100

10

400 / 300 / 0

Потребности

310

10

0

250

0

150

100

0

440

0

Все запасы исчерпаны, все потребности удовлетворены, следовательно, назначение полное. Выполняется условие: число заполненных клеток (клеток, имеющих поставки) должно быть равно (3+4-1=6)

Построим оптимальное решение методом потенциалов.

Потребители

Потенциалы

Производители

В1

В2

В3

В4

А1

10

5 250

6 50

6

А2

12 10

7

8

6 440

А3

11 300

6

7 100

10

Потенциалы

Для всех клеток, в которых имеются поставки, должно выполняться условие

.

Число заполненных клеток равно 6, следовательно, система включает 6 уравнений и имеет вид:

Поскольку в системе 7 неизвестных переменных, число возможных решений неограниченно. Примем . Тогда из первого и второго уравнений системы следует, что и . Так как , то из шестого уравнения получаем . Учитывая, что , получаем из пятого уравнения . Поскольку , то из третьего уравнения . Из и четвертого уравнения следует, что .

Потребители

Потенциалы

Производители

В1

В2

В3

В4

А1

10

5 250

6 50

6

А2

12 10

7

8

6 440

А3

11 300

6

7 100

10

Потенциалы

Проверим для каждой не заполненной клетки (в которой нет поставки) критерий оптимальности:

.

Клетка (1;1) критерий оптимальности выполнен

Клетка (1;4) критерий оптимальности выполнен

Клетка (2;2) критерий оптимальности выполнен

Клетка (2;3) критерий оптимальности выполнен

Клетка (3;2) критерий оптимальности выполнен

Клетка (3;4) критерий оптимальности выполнен

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

Рассчитаем минимальную стоимость поставок продукции:

План перевозок можно задать матрицей:

Задание 3

Для охраны автостоянки в течение 4-х месяцев требуется, соответственно, m1, m2, m3, m4 человек, причем, перед началом работы фактически имеется m0 человек. Администрация планирует в конце каждого месяца, кроме последнего, а также в начале работы корректировать число охранников на величину хк, х4=0. На прием одного работника необходимо затратить «а» у.е., а на увольнение «в» у.е. Расходы на содержание избыточного работника составляют «с» у.е., а в случае нехватки персонала приходится нести затраты в размере «d» у.е. за каждое вакантное место. Требуется найти оптимальное значение хк изменения численности работников, при которых суммарные издержки будут минимальными.

№ варианта

m0

m1

m2

m3

m4

a

в

c

d

9

2

3

5

4

2

10

8

7

10

Решение:

Обозначим через - количество работников в i-м месяце, а через - количество работников принятых () или уволенных () в конце i-го месяца.

Пусть - затраты в i-м месяце;

- минимальные затраты в i-м месяце;

- сумма затрат в i-м месяце и минимальных затрат в i+1-м месяце.

В начале решения запишем в аналитической форме функции издержек на прием-увольнение сотрудников (u), а также на содержание ненормативного штата (g). С этой целью введем функции

Оценки эффективности управления на каждом шаге имеют вид:

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

и функции минимальных издержек в зависимости от текущего состояния

1 шаг. Полагаем k=4. Требуемое количество работников .

На данном этапе функция состояния Л4(о) может быть найдена непосредственно, если учесть, что x4*=0 и u(0)=0:

0

1

2

3

4

5

0

0

0

0

0

0

20

10

0

7

14

21

min

2 шаг. Полагаем k=3. Предварительно заполним таблицу значений функции Щ3 (x3, о). Требуемое количество работников .

0

0

40

20

60

min

1

50

10

60

min

2

60

0

60

min

3

70

7

77

4

80

14

94

5

90

21

111

1

-1

38

20

58

0

30

10

40

min

1

40

0

40

min

2

50

7

57

3

60

14

74

4

70

21

91

2

-2

36

20

56

-1

28

10

38

0

20

0

20

min

1

30

7

37

2

40

14

54

3

50

21

71

3

-3

34

20

54

-2

26

10

36

-1

18

0

18

0

10

7

17

min

1

20

14

34

2

30

21

51

4

-4

32

20

52

-3

24

10

34

-2

16

0

16

-1

8

7

15

0

0

14

14

min

1

10

21

31

5

-5

47

20

67

-4

39

10

49

-3

31

0

31

-2

23

7

30

-1

15

14

29

0

7

21

28

min

3 шаг. Полагаем k=2. Предварительно заполним таблицу значений функции Щ2 (x2, о). Требуемое количество работников .

0

0

50

60

110

1

60

40

100

2

70

20

90

min

3

80

17

97

4

90

14

104

5

100

28

128

1

-1

48

60

108

0

40

40

80

1

50

20

70

min

2

60

17

77

3

70

14

84

4

80

28

108

2

-2

46

60

106

-1

38

40

78

0

30

20

50

min

1

40

17

57

2

50

14

64

3

60

28

88

3

-3

44

60

104

-2

36

40

76

-1

28

20

48

0

20

17

37

min

1

30

14

44

2

40

28

68

4

-4

42

60

102

-3

34

40

74

-2

26

20

46

-1

18

17

35

0

10

14

24

min

1

20

28

48

5

-5

40

60

100

-4

32

40

72

-3

24

20

44

-2

16

17

33

-1

8

14

22

min

0

0

28

28

4 шаг. Полагаем k=1. Предварительно заполним таблицу значений функции Щ1 (x1, о). Требуемое количество работников .

0

0

30

90

120

1

40

70

110

2

50

50

100

3

60

37

97

4

70

24

94

min

5

80

22

102

1

-1

28

90

118

0

20

70

90

1

30

50

80

2

40

37

77

3

50

24

74

min

4

60

22

82

2

-2

26

90

116

-1

18

70

88

0

10

50

60

1

20

37

57

2

30

24

54

min

3

40

22

62

3

-3

24

90

114

-2

16

70

86

-1

8

50

58

0

0

37

37

1

10

24

34

min

2

20

22

42

4

-4

39

90

129

-3

31

70

101

-2

23

50

73

-1

15

37

52

0

7

24

31

min

1

17

22

39

5

-5

54

90

144

-4

46

70

116

-3

38

50

88

-2

30

37

67

-1

22

24

46

0

14

22

36

min

5 шаг. На последней итерации, в связи с наличием начального условия о*0 = 2, достаточно вычислить Щ0(x0, 2).

2

-2

-1

0

1

2

3

16

8

0

10

20

30

94

74

54

34

31

36

110

82

54

44

51

66

min

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

В конце первого месяца на работу принимается еще один работник (). Следовательно, число рабочих во втором месяце .

В конце второго месяца никого не нанимают (). Следовательно, число рабочих в третьем месяце .

В конце третьего месяца никого не нанимают (). Следовательно, число рабочих в четвертом месяце .

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

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

Задание 4

перевозка издержка матричная игра

Найти решение матричной игры (любым методом).

Решение:

Рассмотрим матричную игру двух лиц с платежной матрицей H:

Обозначим через - вероятность применения 1-м игроком его i-й чистой стратегии.

Обозначим через - вероятность применения 2-м игроком его j-й чистой стратегии.

Рассмотрим средний выигрыш 1-го игрока, если он применяет свои чистые стратегии, а 2-й игрок - смешанную стратегию (первый игрок стремится получить максимально возможный выигрыш в наихудших условиях).

(1)

v - чистая цена игры.

Рассмотрим средний выигрыш 2-го игрока, если он применяет свои чистые стратегии, а 1-й игрок - смешанную стратегию (второй игрок стремится минимизировать выигрыш 1-го игрока).

(2)

Рассмотрим графическую интерпретацию игры:

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

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

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

Так как

, то .

Цена игры

.

Поскольку точку максимума образует пересечение второй и третьей прямых, то вероятность применения 1-й чистой стратегии вторым игроком равна 0 (). Вероятности и . Найдем их оптимальные значения, решив систему уравнений (1).

Учитывая, что , получим

Решением матричной игры являются смешанные стратегии игроков:

Таким образом, первому игроку необходимо применять свою 1-ю чистую стратегию с вероятностью 1/3 и 2-ю чистую стратегию с вероятностью 2/3. Второму игроку необходимо применять 2-ю чистую стратегию с вероятностью 2/9 и третью чистую стратегию с вероятностью 7/9. Цена игры при этом составит 11/30.

Размещено на Allbest.ru


Подобные документы

  • Решение задачи линейного программирования симплекс-методом. План перевозок при минимальных затратах на них. Определение оптимального значения изменения численности работников. Решение матричной игры двух лиц с применением чистой и смешанной стратегий.

    контрольная работа [152,3 K], добавлен 16.05.2013

  • Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.

    курсовая работа [111,1 K], добавлен 16.01.2011

  • Решение задачи линейного программирования графическим и симплекс-методом. Решение задачи двойственной к исходной. Определение оптимального плана закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей.

    контрольная работа [398,2 K], добавлен 15.08.2012

  • Симплекс метод решения задач линейного программирования. Построение модели и решение задачи определения оптимального плана производства симплексным методом. Построение двойственной задачи. Решение задачи оптимизации в табличном процессоре MS Excel.

    курсовая работа [458,6 K], добавлен 10.12.2013

  • Предмет и задачи теории игр. Сведение матричной игры к задачам линейного программирования. Основные принципы разработки деловых игр для исследования экономических механизмов. Деловая игра "Снабжение". Решение матричной игры в смешанных стратегиях.

    курсовая работа [1,8 M], добавлен 15.10.2012

  • Составление математической модели, целевой функции, построение системы ограничений и симплекс-таблиц для решения задач линейного программирования. Решение транспортной задачи: определение опорного и оптимального плана, проверка методом потенциалов.

    курсовая работа [54,1 K], добавлен 05.03.2010

  • Характеристика направлений перевозок и флота. Расчет нормативов работы судов на схемах движения. Составление математической модели задачи. Нахождение оптимального плана работы флота и оптимальных схем движения судов, построение симплекс таблицы.

    курсовая работа [1,4 M], добавлен 24.10.2012

  • Оптимизация плана перевозок с использованием метода потенциалов. Расчет параметров регрессионных моделей. Проверка надежности найденных статистических показателей и вариаций изменений. Общая задача линейного программирования и решение ее симплекс-методом.

    курсовая работа [367,3 K], добавлен 16.05.2015

  • Типы транспортных задач и методы их решения. Поиск оптимального плана перевозок методом потенциалов. Решение задачи с использованием средств MS Excel. Распределительный метод поиска оптимального плана перевозок. Математическая модель, описание программы.

    курсовая работа [808,7 K], добавлен 27.01.2011

  • Решение задачи линейного программирования графическим способом. Определение экстремальной точки. Проверка плана на оптимальность. Правило прямоугольников. Анализ и корректировка результатов решения задач линейного программирования симплексным методом.

    контрольная работа [40,0 K], добавлен 04.05.2014

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.