Экономико-математическое моделирование

Автор работы: Пользователь скрыл имя, 28 Января 2013 в 17:34, контрольная работа

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

Решенные задачи по Экономико-математическому моделированию

Вложенные файлы: 1 файл

Вариант 97.doc

— 494.50 Кб (Скачать файл)

Вариант 97(13)

Контрольная работа №1

  Вариант 97

Задача  №1

  1. Построить оптимальный план перевозок каменного угля с 5 станций до 9-ти крупных потребителей, имеющих подъездные пути .
  2. Определить объем тонно-километровой работы начального и оптимального планов перевозки грузов.

Запишем условие задачи в матричной  форме. В строке Ai указываем размер ресурсов у отправителей, а в столбце Bj – размер потребностей у получателей. В верхнем правом углу каждой клетки значение Cij – критерия оптимальности перевозки грузов от i поставщика к j потребителю. Cij означает расстояние перевозки от i поставщика до j потребителя. Размер всех ресурсов у отправителей равен общей потребности получателей. Если клетка имеет ограничение пропускной способности, то в левом верхнем углу клетки указывается число dij.

Необходимо найти такие неотрицательные  значения величин объемов перевозок xij, при которых сумма произведений значений критерия Cij на размер перевозок будет минимальной, т.е. .

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

Ai

Bj

B1

B2

B3

B4

B5

B6

B7

B8

B9

Ui

165

105

85

95

75

115

90

125

145

 

A1

 

90

 

30

 

100

 

110

 

150

30

50

 

60

 

80

 

90

 

150

150

                 

A2

 

10

 

40

 

45

 

50

 

25

 

70

30

15

 

30

10

30

 

160

15

105

40

             

A3

10

20

 

35

 

80

 

160

 

90

 

80

 

70

 

40

 

60

 

400

   

45

95

75

115

70

     

A4

 

50

 

5

 

40

 

30

 

120

 

40

 

75

 

30

40

20

 

150

           

20

90

40

 

A5

 

15

15

25

 

10

20

35

 

25

 

80

 

20

 

70

 

90

 

140

             

35

105

 

Vj

                                     

 Объем работы по перевозке  грузов в тонно-километрах для  данного плана 73750 ед.

Число базисных клеток начального плана равно  , где m – число строк, а n – число столбцов. K=5+9-1=13. Число базисных клеток начального плана равно 13, что совпадает с рассчитанным по формуле. Клетка C49 не является базисной.

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

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

Такой строкой  является А3. Тогда потенциал U3=100.

Рассчитаем  остальные потенциалы по формулам: для j-го столбца  ; для i-той строки .

V3=U3+C33=100+80=180;

V4=U3+C34=100+160=260;

V5=U3+C35=100+90=190;

V6=U3+C36=100+80=180;

V7=U3+C37=100+70=170;

U2=V3-C23=180-45=135;

V2=U2+C22=135+40=175;

V1=U2+C21=135+10=145;

U1=V1-C11=145-90=55;

U4=V7-C47=170-75=95;

V8=U4+C48=95+30=125;

U5=V8-C58=125-70=55;

V9=U5+C59=55+90=145.

Проверим условия оптимальности:

Vj – потенциал j-го столбца; Ui – потенциал i-той строки; Сij – расстояние перевозки от i-го поставщика до j-го потребителя; xij – корреспонденция (размеры перевозок) от i-го поставщика до j-го потребителя; dij – величина пропускной способности ij клетки.

Для  удобства запишем расчеты  в таблицу:

 

V1

V2

V3

V4

V5

V6

V7

V8

V9

   

V1

V2

V3

V4

V5

V6

V7

V8

V9

U1

90

120

125

205

135

125

115

70

90

 

U1

90

30

100

110

150

50

60

80

90

U2

10

40

45

125

55

45

35

-10

10

 

U2

10

40

45

50

25

70

15

30

30

U3

45

75

80

160

90

80

70

25

45

 

U3

20

35

80

160

90

80

70

40

60

U4

50

80

85

165

95

85

75

30

50

 

U4

50

5

40

30

120

40

75

30

20

U5

90

120

125

205

135

125

115

70

90

 

U5

15

25

10

35

25

80

20

70

90


   

Нарушения условий есть в ячейках х12, х13, х14, х17, х16, х24, х25, х27, х31, х32, х42, х43, х44, х46, х51, х52, х53, х54, х55, х56, х57.

Максимальное нарушение в клетке х54=205-35=170. Для этой клетки строим замкнутый контур, в который входят только базисные клетки и клетка с нарушением. Из клетки х54 проводим ломаную линию, заканчивающуюся в той же клетке, направление движения при этом изменяется под прямым углом только в базисных клетках. Клетка с нарушением имеет №1, корреспонденцию улучшения плана находим из следующего выражения: . На эту величину изменяются все корреспонденции контура, начиная с клетки с нарушением: уменьшаются корреспонденции, записанные в четных клетках, и увеличиваются корреспонденции, записанные в нечетных клетках контура.

Контур для улучшения плана: х54→х34→х37→х47→х48→х58→х54

хул=min[х34=95, х47=85, х58=35; х54=20, ∞, ∞]=20.

х54=0+20=20; х34=95-20=75; х37=70+20=90; х47=20-20=0; х48=90+20=110; х58=35-20=15. Строим новую матрицу перевозок.

Продолжая расчеты, получим матрицу  оптимального плана перевозок:

Ai

Bj

B1

B2

B3

B4

B5

B6

B7

B8

B9

Ui

A1

0

30

0

0

0

30

90

0

0

150

A2

155

0

0

0

5

0

0

0

0

160

A3

10

75

0

0

15

30

0

125

145

400

A4

0

0

0

95

0

55

0

0

0

150

A5

0

0

85

0

55

0

0

0

0

140

Vj

165

105

85

95

75

115

90

125

145

 

Объем работы по перевозке грузов в тонно-километрах для оптимального плана 37025 ед.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача №2

Вариант №13

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

Целевая функция:

Ограничения:

Решение

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

При этом найдены  уравнения прямых – границ полуплоскостей. Каждая прямая разбивает плоскость  на две полуплоскости. Искомую полуплоскость  отмечают в соответствии со смыслом  неравенства.

Прямые  строим по точкам.

: координаты первой точки х1=5, х2=1; координаты второй точки х1=4, х2=5.

: координаты первой точки  х1=6, х2=4; координаты второй точки х1=5, х2=6.

: координаты первой точки  х1=3, х2=0; координаты второй точки х1=0, х2=6.

: координаты первой точки  х1=0, х2=-1; координаты второй точки х1=1, х2=0.

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

Система неравенств противоречива. Задача не имеет решений.

 

Задача №3

Вариант № 13

Найти оптимальное значение функции  при заданной системе ограничений.

Целевая функция: .

Ограничения: .

Решение.

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

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

Ограничения: .

Целевая функция: .

Найдем  вид канонической задачи линейного  программирования. Для этого выразим  базисные неизвестные через свободные. Число базисных неизвестных равно числу ограничений, остальные переменные – свободные. Получим:

Выразим целевую  функцию через свободные неизвестные.

При этом при  нулевых значениях свободных  неизвестных базисные положительны.

Для уменьшения целевой функции следует увеличивать  переменную х2. В первом ограничении можно увеличивать переменную до 15, во втором – до в третьем – до 20.

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

Получим:

В выражение для целевой функции  обе переменных входят с положительными коэффициентами. Поэтому можно утверждать, что найден оптимальный план: х34=0. Остальные неизвестные: х1=16,667, х3=6,667, х5=13,333.

Оптимальное значение функции  равно 23,333.

 

 

 

 

 

 

 

Контрольная работа №2

Задача №1

Вариант №9

Требуется найти оптимальную трассу участка железнодорожного пути между пунктами А и В, из которых второй лежит к северо-востоку от первого. Местность, по которой пройдет магистраль, является пересеченной и включает лесистые зоны, холмы, болота, реку. Поэтому стоимость строительства равных по длине участков пути может быть различной. Требуется так провести дорогу из пункта А в пункт В, чтобы суммарные затраты на сооружение участка были минимальными.

№5

13

№11

68

№17

10

№23

11

№29

13

№35

8

№41

10

В

12

 

9

 

11

 

13

 

10

 

7

 

15

 

10

№4

13

№10

10

№16

10

№22

12

№28

14

№34

8

№40

11

№46

10

 

12

 

12

 

13

 

8

 

9

 

13

 

11

№3

11

№9

13

№15

13

№21

14

№27

8

№33

10

№39

10

№45

9

 

12

 

15

 

9

 

10

 

10

 

12

 

15

№2

10

№8

11

№14

14

№20

10

№26

9

№32

8

№38

12

№44

14

 

9

 

29

 

11

 

14

 

12

 

10

 

10

№1

15

№7

12

№13

10

№19

88

№25

12

№31

10

№37

13

№43

12

 

9

 

10

 

13

 

10

 

11

 

9

 

13

А

13

№6

8

№12

8

№18

12

№24

13

№30

11

№36

10

№42

Информация о работе Экономико-математическое моделирование