Logo GenDocs.ru

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

Загрузка...

Контрольная работа - Математика в экономике - файл 1.rtf


Контрольная работа - Математика в экономике
скачать (8805.7 kb.)

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

1.rtf8806kb.09.12.2011 02:07скачать

содержание
Загрузка...

1.rtf

Реклама MarketGid:
Загрузка...
Задача 1.



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

Определим минимальное значение целевой функции F(X) = 11x1 + 44x2 при следующих условиях-ограничений.

3x1 + 5x2≥18

x1 + 9x2≥30

2x1 + 7x2≥27

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≥) вводим базисную переменную x3 со знаком минус. В 2-м неравенстве смысла (≥) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.

3x1 + 5x2-1x3 + 0x4 + 0x5 = 18

1x1 + 9x2 + 0x3-1x4 + 0x5 = 30

2x1 + 7x2 + 0x3 + 0x4-1x5 = 27

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

-3x1-5x2 + 1x3 + 0x4 + 0x5 = -18

-1x1-9x2 + 0x3 + 1x4 + 0x5 = -30

-2x1-7x2 + 0x3 + 0x4 + 1x5 = -27

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
Решим систему уравнений относительно базисных переменных:

x3, x4, x5,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,-18,-30,-27)

Базис

B

x1

x2

x3

x4

x5

x3

-18

-3

-5

1

0

0

x4

-30

-1

-9

0

1

0

x5

-27

-2

-7

0

0

1

F(X0)

0

11

44

0

0

0


План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

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

Базис

B

x1

x2

x3

x4

x5

x3

-18

-3

-5

1

0

0

x4

-30

-1

-9

0

1

0

x5

-27

-2

-7

0

0

1

F(X)

0

11

44

0

0

0

θ

0

11 : (-1) = -11

44 : (-9) = -48/9

-

-

-


Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B

x1

x2

x3

x4

x5

x3

-11/3

-24/9

0

1

-5/9

0

x2

31/3

1/9

1

0

-1/9

0

x5

-32/3

-12/9

0

0

-7/9

1

F(X0)

-1462/3

61/9

0

0

48/9

0


План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.

На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-7/9).

Базис

B

x1

x2

x3

x4

x5

x3

-11/3

-24/9

0

1

-5/9

0

x2

31/3

1/9

1

0

-1/9

0

x5

-32/3

-12/9

0

0

-7/9

1

F(X)

-1462/3

61/9

0

0

48/9

0

θ

0

61/9 : (-12/9) = -5

-

-

48/9 : (-7/9) = -62/7

-


Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис

B

x1

x2

x3

x4

x5

x3

12/7

-14/7

0

1

0

-5/7

x2

36/7

2/7

1

0

0

-1/7

x4

45/7

14/7

0

0

1

-12/7

F(X1)

-1695/7

-14/7

0

0

0

62/7


В базисном столбце все элементы положительные.

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (- , 36/7 : 2/7 , 45/7 : 14/7 ) = 3

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (14/7) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

min

x3

12/7

-14/7

0

1

0

-5/7

-

x2

36/7

2/7

1

0

0

-1/7

131/2

x4

45/7

14/7

0

0

1

-12/7

3

F(X1)

-1695/7

-14/7

0

0

0

62/7

0


Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x3

6

0

0

1

1

-2

x2

3

0

1

0

-2/11

1/11

x1

3

1

0

0

7/11

-9/11

F(X1)

-165

0

0

0

1

5


Конец итераций: индексная строка не содержит отрицательных элементов - найден оптимальный план

Окончательный вариант симплекс-таблицы:

Базис

B

x1

x2

x3

x4

x5

x3

6

0

0

1

1

-2

x2

3

0

1

0

-2/11

1/11

x1

3

1

0

0

7/11

-9/11

F(X2)

-165

0

0

0

1

5


Оптимальный план можно записать так:

x3 = 6

x2 = 3

x1 = 3

F(X) = 0•6 + 44•3 + 11•3 = 165
Задача 2


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

F = ∑∑cijxij, (1)

при условиях:

∑xij = ai, i = 1,2,…, m, (2)

∑xij = bj, j = 1,2,…, n, (3)

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




1

2

3

4

Запасы

1

6

12

15

4

150

2

12

11

5

3

250

3

9

17

14

10

200

Потребности

100

180

160

160





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

∑a = 150 + 250 + 200 = 600

∑b = 100 + 180 + 160 + 160 = 600

Занесем исходные данные в распределительную таблицу.




1

2

3

4

Запасы

1

6

12

15

4

150

2

12

11

5

3

250

3

9

17

14

10

200

Потребности

100

180

160

160





^ Этап I. Поиск первого опорного плана.

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




1

2

3

4

Запасы

1

6[100]

12[50]

15

4

150

2

12

11

5[90]

3[160]

250

3

9

17[130]

14[70]

10

200

Потребности

100

180

160

160





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

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

Значение целевой функции для этого опорного плана равно:

F(x) = 6*100 + 12*50 + 5*90 + 3*160 + 17*130 + 14*70 = 5320

^ Этап II. Улучшение опорного плана.

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




v1=6

v2=12

v3=9

v4=7

u1=0

6[100]

12[50]

15

4

u2=-4

12

11

5[90]

3[160]

u3=5

9

17[130]

14[70]

10


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

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

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




1

2

3

4

Запасы

1

6[100]

12[50][-]

15

4[+]

150

2

12

11

5[90][+]

3[160][-]

250

3

9

17[130][+]

14[70][-]

10

200

Потребности

100

180

160

160





Цикл приведен в таблице (1,4; 1,2; 3,2; 3,3; 2,3; 2,4; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 50. Прибавляем 50 к объемам грузов, стоящих в плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.




1

2

3

4

Запасы

1

6[100]

12

15

4[50]

150

2

12

11

5[140]

3[110]

250

3

9

17[180]

14[20]

10

200

Потребности

100

180

160

160





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




v1=6

v2=9

v3=6

v4=4

u1=0

6[100]

12

15

4[50]

u2=-1

12

11

5[140]

3[110]

u3=8

9

17[180]

14[20]

10


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

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

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




1

2

3

4

Запасы

1

6[100][-]

12

15

4[50][+]

150

2

12

11

5[140][+]

3[110][-]

250

3

9[+]

17[180]

14[20][-]

10

200

Потребности

100

180

160

160





Цикл приведен в таблице (3,1; 3,3; 2,3; 2,4; 1,4; 1,1; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 20. Прибавляем 20 к объемам грузов, стоящих в плюсовых клетках и вычитаем 20 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.




1

2

3

4

Запасы

1

6[80]

12

15

4[70]

150

2

12

11

5[160]

3[90]

250

3

9[20]

17[180]

14

10

200

Потребности

100

180

160

160





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




v1=6

v2=14

v3=6

v4=4

u1=0

6[80]

12

15

4[70]

u2=-1

12

11

5[160]

3[90]

u3=3

9[20]

17[180]

14

10


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

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

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




1

2

3

4

Запасы

1

6[80][-]

12[+]

15

4[70]

150

2

12

11

5[160]

3[90]

250

3

9[20][+]

17[180][-]

14

10

200

Потребности

100

180

160

160





Цикл приведен в таблице (1,2; 1,1; 3,1; 3,2; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 1) = 80. Прибавляем 80 к объемам грузов, стоящих в плюсовых клетках и вычитаем 80 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.




1

2

3

4

Запасы

1

6

12[80]

15

4[70]

150

2

12

11

5[160]

3[90]

250

3

9[100]

17[100]

14

10

200

Потребности

100

180

160

160





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




v1=4

v2=12

v3=6

v4=4

u1=0

6

12[80]

15

4[70]

u2=-1

12

11

5[160]

3[90]

u3=5

9[100]

17[100]

14

10


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

Минимальные затраты составят:

F(x) = 12*80 + 4*70 + 5*160 + 3*90 + 9*100 + 17*100 = 4910

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


Задача 3



^ 1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях.

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

Игроки

B1

B2

B3

B4

a = min(Ai)

A1

2

7

4

9

2

A2

6

10

8

7

6

A3

3

11

12

5

3

b = max(Bi )

6

11

12

9

0


Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 6, которая указывает на максимальную чистую стратегию A2.

Верхняя цена игры b = min(bj) = 6.

Седловая точка (2, 1) указывает решение на пару альтернатив (A2,B1). Цена игры равна 6.


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

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

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