Исследования операций в экономике

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

Министерство образования и науки РФ

Федеральное государственное бюджетное образовательное учреждение

высшего образования

«Владимирский государственный университет

имени Александра Григорьевича и Николая Григорьевича Столетовых»

(ВлГУ)

Кафедра "Функциональный анализ и его приложения"

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

Исследования операций в экономике

Владимир 2016

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

линейный программирование симплекс задача

F = 4x2 + x4 max

x1 + x2 + x3 = 11

2x1 - 3x2 - x4 = 1

-x1 + x2 + x5 = - 3, x1, x2 , x3 , x4 , x5 0

Решение: Выразим из уравнений

х3 = - х1 - х2 + 11 (*)

х4 = 2х1- 3х2 - 1 (**)

х5 = х1 - х2 - 3 (***)

Подставим х4 в F

F = 2x1 + x2 - 1

Из условий неотрицательности х3 х4 х5 получаем задачу ЛП :

F = 2x1 + x2 - 1 > max

- х1 - х2 + 11 0

2х1- 3х2 - 1 0

х1 - х2 - 3 0, х1 0, х2 0,

или в виде ( перенесём числа вправо и умножим на -1)

F = 2x1 + x2 - 1 > max

х1 + х2 11

2х1 - 3х2 1 (1)

х1 - х2 3, х1 0, х2 0.

Решим графически. Построим область допустимых решений (ОДP).

Для этого построим прямые ( заменим в системе (1) знак неравенства на = )

х1 + х2 = 11 (1)

2х1 - 3х2 = 1 (2)

х1 - х2 = 3 (3)

Т.к. все неравенствa-ограничения можно записать в виде

х2 ...,

то штрихуем ниже прямых .

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

ОДР - треугольник ABС. Проводим вектор-градиент, ( его координаты - коэффициенты целевой функции (2; 1) , малиновая стрелка ), он указывает направление максимизации F(X). Поскольку задача на максимум, двигаем линию уровня (красный пунктир) в направлении градиента до последнего касания ОДР в угловой точке С.



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

Она получена при пересечении прямой (1) с ОХ1 , подставим в уравнение прямой (1) х2* = 0, получим х1* = 11.

Максимум ЦФ :

Fmax = 2x1* + x2* - 1 = 2*11 + 0 - 1 = 21.

Найдём х3 х4 х5 по формулам (*)-(**) и проверим неотрицательность

х3* = - х1* - х2* + 11 = - 11 - 0 + 11 = 0 0

х4* = 2х1* - 3х2* - 1 = 22 - 1 = 21 0

х5* = х1* - х2* - 3 = 11 - 3 = 8 0.

Ответ : х1* = 11; х2* = 0; х3* = 0; х4* = 21; х5* = 8; Fmax = 21.

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

Решение:

Прямая задача : F = 4x2 + x4 max

x1 + x2 + x3 = 11

2x1 - 3x2 - x4 = 1

-x1 + x2 + x5 = - 3, x1, x2 , x3 , x4 , x5 0

Расширенная матрица A прямой задачи

1	1	1	0	0	11
2	-3	0	-1	0	1
-1	1	0	0	1	-3
0	4	0	1	0	0

Транспонированная матрица AT

1	2	-1	0
1	-3	1	4
1	0	0	0
0	-1	0	1
0	0	1	0
11	1	-3	0

Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения противоположного смысла двойственной задачи. Получаем двойственную задачу:

Z(Y) = 11y1 + y2 - 3y3 > min

y1+2y2-y3?0

y1-3y2+y3?4

y1?0

-y2?1

y3?0 , y1 y2 y3 - любое число

Hайдём её решение по теоремам двойственности.

Поскольку в оптимальном плане прямой задачи x1* > 0, x4* > 0, x5* > 0, то I, IV и V ограничения в двойственной задаче будут равенствами.

Получим систему

y1 + 2y2 - y3 = 0

-y2 = 1

y3 = 0 ,

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

y1 = 2, y2 = -1, y3 = 0 или Y* = (2; -1; 0)

maxZ(Y) = Z(Y*) = 11*2+(-1)+(-3)*0 = 21

Ответ : y1* = 2, y2* = - 1, y3* = 0 ; Zmin = 21

Задача 3. Решить задачу линейного программирования двумя методами:

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

F = 3x + 4y + 2z max

при условиях 2x + 5y + 4z 20, 4x + 3y + 5z 30, x, y, z 0.

Решение:

ОДР - многогранник АВСОKD. Находим координаты угловых точек ( его вершин ). Обозначим плоскости :

: 4x + 3y + 5z = 30 ,

: 2x + 5y + 4z = 20 .

a) A = OY ; подставим в уравнение : х =0, z = 0 y = 4 ; A(0; 4; 0)

б) В = ХOY ; подставим в уравнение и : z = 0

4x + 3y = 30 ,

2x + 5y = 20 x = 45/7 ; y = 10/7 B(45/7; 10/7; 0)

в) С = OХ ;

подставим в уравнение : у =0, z = 0 x = 7,5 ; C(7,5; 0; 0).

г) D = ХOZ ;

подставим в уравнение и : y = 0

4x + 5z = 30 ,

2x + 4z = 20

x = 10/3 ; z = 10/3 D(10/3; 0; 10/3)

д) K = OZ ;

подставим в уравнение : х =0, y = 0 z = 5 ; K(0; 0; 5).

Найдём значения ЦФ в найденных угловых точках, подставляя в ЦФ их координаты.

f(O) = 0, f(A) = 16, f(B) = 25, f(C) = 22.5, f(D) = 50/3, f(K) = 10.

Cравнивая значения, получим максимум в т. В :

fmax = 25, x* = 45/7, y* = 10/7, z* = 0.

Применим симплекс-метод.

Задача ЛП :

F = 3x + 4y + 2z max

2x + 5y + 4z 20,

4x + 3y + 5z 30, x, y, z 0.

Перейдём к канонической форме.

2x + 5y + 4z + 1x4 + 0x5 = 20

4x + 3y + 5z + 0x4 + 1x5 = 30

Первый опорный план: X0 = (0,0,0,20,30)

Базис	B	x	у	z	x4	x5
x4	20	2	5	4	1	0
x5	30	4	3	5	0	1
F(X0)	0	-3	-4	-2	0	0

План не оптимален, т.к. в индексной строке есть отрицательные коэффициенты.

Определение новой базисной переменной. За ведущий выберем столбец y (наибольший по модулю).

Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее:

min (20 : 5 , 30 : 3 ) = 4

Значит 1-я строка ведущая. Разрешающий элемент равен (5)

Базис	B	x	y	z	x4	x5	min
x4	20	2	5	4	1	0	4
x5	30	4	3	5	0	1	10
F(X0)	0	-3	-4	-2	0	0	0

Выводим из базиса x4 , вводим y.

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

Базис	B	x	y	z	x4	x5
y	4	2/5	1	4/5	1/5	0
x5	18	24/5	0	23/5	-3/5	1
F(X1)	16	-12/5	0	11/5	4/5	0

Опорный план неоптимален, повторяем шаг симплекс-метода

Базис	B	x	y	z	x4	x5	min
y	4	2/5	1	4/5	1/5	0	10
x5	18	24/5	0	23/5	-3/5	1	63/7
F(X1)	16	-12/5	0	11/5	4/5	0	0

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

Базис	B	x	y	z	x4	x5
y	13/7	0	1	3/7	2/7	-1/7
x	63/7	1	0	13/14	-3/14	5/14
F(X2)	25	0	0	21/2	1/2	1/2

В индексной строке нет отрицательных. Получили оптимальный план задачи :

x* = 45/7, y* = 10/7, z* = 0 ; ( или Х* = (45/7 ; 10/7 ; 0) ) ;

maxF(X) = F(X*) =3*63/7 + 4*13/7 + 2*0 = 25.

Решения совпадают.

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

	В1	В2	В3	В4	запасы
А1	6	3	2	4	100
А2	3	5	4	3	200
А3	4	2	3	7	150
А4	8	6	5	2	150
потребности	170	80	140	190

Решение:

Проверим закрытость.

ai = 100+200+150+150 = 600, bj = 170+80+140+190 = 580.

Запасы больше потребностей. Вводим фиктивную потребность В5 с нулевыми тарифами, для которой b5 = 600-580 = 20.

	В1	В2	В3	В4	B5	запасы
А1	6	3	2	4	0	100
А2	3	5	4	3	0	200
А3	4	2	3	7	0	150
А4	8	6	5	2	0	150
потребности	170	80	140	190	20

Запишем экономико-математическую модель задачи.

Переменные:

xij - количество груза из i-го склада (ПО) в j-й магазин (ПН) ( i = 14, j = 15).

Ограничения по запасам:

x11 + x12 + x13 + x14 + х15 = 100

x21 + x22 + x23 + x24 + х25 = 200

x31 + x32 + x33 + x34 + х35 = 150

x41 + x42 + x43 + x44 + х45 = 150

Ограничения по потребностям:

x11 + x21 + x31 + x41 = 150

x12 + x22 + x32 + x42 = 200

x13 + x23 + x33 + x43 = 150

x14 + x24 + x34 + x44 = 150

x15 + x25 + x35 + x45 = 20

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

F = 6x11+3x12 + 2x13 + 4x14 + 3x21 + 5x22 + 4x23 + 3x24+ 4x31 + 2x32 + 3x33 + 7x34 + 8x41 + 6x42 + 5x43 + 2x44 > min

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

	В1	В2	В3	В4	В5	запасы
А1	6	3	1) 2 / 100	4	0	//100
А2	4) 3 / 170	5	4	5) 3 / 30	0	//30-200
А3	4	2) 2 / 80	6) 3 / 40	7) 7 / 10	8) 0 / 20	//20-30-70-150
А4	8	6	5	3) 2 / 150	0	//150
	//170	//80	//40-140	//10-40-190	//20

Стоимость перевозок по этому плану

F = 2*100+3*170+3*30+2*80+3*40+7*10+2*150 = 1450 де.

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

	v1	v2	v3	v4	v5
u1	6	3	2[100]	4	0
u2	3[170]	5	4	3[30]	0
u3	4	2[80]	3[40]	7[10]	0[20]
u4	8	6	5	2[150]	0

u1 + v3 = 2; 0 + v3 = 2 v3 = 2, u3 + v3 = 3; 2 + u3 = 3 u3 = 1 ,

u3 + v2 = 2; 1 + v2 = 2 v2 = 1, u3 + v4 = 7; 1 + v4 = 7 v4 = 6 ,

u2 + v4 = 3; 6 + u2 = 3 u2 = -3, u2 + v1 = 3; -3 + v1 = 3 v1 = 6 ,

u4 + v4 = 2; 6 + u4 = 2 u4 = -4, u3 + v5 = 0; 1 + v5 = 0 v5 = -1

	v1=6	v2=1	v3=2	v4=6	v5=-1
u1=0	6	3	2[100]	4	0
u2=-3	3[170]	5	4	3[30]	0
u3=1	4	2[80]	3[40]	7[10]	0[20]
u4=-4	8	6	5	2[150]	0

Найдём оценки ij свободных клеток по формуле :

ij = cij - (ui + vj)

	v1=6	v2=1	v3=2	v4=6	v5=-1
u1=0	6/ 0	3 / 2	2[100]	4 / -2	0 / 1
u2=-3	3[170]	5 / 7	4 / 5	3[30]	0 / 4
u3=1	4 / -3	2[80]	3[40]	7[10]	0[20]
u4=-4	8 / 6	6 / 9	5 / 7	2[150]	0 / 5

План не оптимален ( есть отрицательные оценки 14 31).

Берём максимальную и строим цикл (3,1 > 3,4 > 2,4 > 2,1).

	1	2	3	4	5	Запасы
1	6	3	2[100]	4	0	100
2	3[170][-]	5	4	3[30][+]	0	200
3	4[+]	2[80]	3[40]	7[10][-]	0[20]	150
4	8	6	5	2[150]	0	150
Потребности	170	80	140	190	20

Из грузов хij стоящих в клетках [-], выбираем наименьшее, т.е.

у = min (3, 4) = 10. Прибавляем 10 к объемам грузов, стоящих в клетках [+] и вычитаем 10 из Хij, стоящих в клетках [-]. Получим новый опорный план.

	1	2	3	4	5	Запасы
1	6	3	2[100]	4	0	100
2	3[160]	5	4	3[40]	0	200
3	4[10]	2[80]	3[40]	7	0[20]	150
4	8	6	5	2[150]	0	150
Потребности	170	80	140	190	20

Найдем потенциалы

u1 + v3 = 2; 0 + v3 = 2 v3 = 2, u3 + v3 = 3; 2 + u3 = 3 u3 = 1 ,

u3 + v1 = 4; 1 + v1 = 4 v1 = 3, u2 + v1 = 3; 3 + u2 = 3 u2 = 0 ,

u2 + v4 = 3; 0 + v4 = 3 v4 = 3, u4 + v4 = 2; 3 + u4 = 2 u4 = -1,

u3 + v2 = 2; 1 + v2 = 2 v2 = 1, u3 + v5 = 0; 1 + v5 = 0 v5 = -1,

Найдём оценки ij

	v1=3	v2=1	v3=2	v4=3	v5=-1
u1=0	6 / 3	3 / 2	2[100]	4 / 1	0 / 1
u2=0	3[160]	5 / 4	4 / 2	3[40]	0 / 1
u3=1	4[10]	2[80]	3[40]	7 / 3	0[20]
u4=-1	8 / 6	6 / 6	5 / 4	2[150]	0 / 2

План оптимален (все оценки свободных клеток неотрицательны ).

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

F(x) = 2*100 + 3*160 + 3*40 + 4*10 + 2*80 + 3*40 + 2*150 = 1420 де.

Оптимальный план перевозок:

Из А1 в В3 100 ед, из А2 в В1 160 ед, из А2 в В4 40 ед, из А3 в В1 10 ед,

из А3 в В2 80 ед, из А3 в В3 40 ед, из А4 в В4 150 ед .

Или в виде матрицы :

На ПО-3 остался не вывезенным груз 20 ед. Все потребности удовлетворены.

Задача 5. Оптимальное поэтапное распределение средств между предприятиями в течении планового периода

Руководство фирмы, имеющей договор о сотрудничестве с тремя малыми предприятия, на плановый годовой период выделила для них оборотные средства в объеме 100000 у. е. Для каждого предприятия известны функции поквартального дохода и поквартального остатка оборотных средств gi(x) в зависимости от выделенной на квартал суммы x. В начале квартала средства распределяются полностью между тремя предприятиями

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

f1(x) = 2x, f2(x) = 3x, f3(x) = 5x, g1(x) = 0,8x , g2(x) = 0,7x , g3(x) = 0,1x .

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

Решение:

Шаг 1 (последний этап).

Т.к. по окончанию последнего этапа нас не интересуют оставшиеся средства, то оптимальное распределение здесь: все средства s выделить III предприятию, гарантирующему максимальный доход. Тогда управление на последнем этапе u=(0,0,s), а функция Беллмана этапа : B1*(s) = 5s.

Шаг 2 (предпоследний этап).

Рассматриваем чистые стратегии.

- I вариант : u(s,0,0) ( 100 - I предприятию, и остаток 0,8s = 80 - третьему, как оптимальному на последнем этапе )

B2(s) = 2s + B1*(0.8s) = 2s + 5*0.8s = 6s

- II вариант : u(0,s,0)

B2(s) = 3s + B1*(0.7s) = 3s + 5*0.7s = 6.5s

- III вариант : u(0,0,s)

B2(s) = 5s + B1*(0.1s) = 5s + 5*0.1s = 5.5s

Оптимален II вариант (В2*(s) = 6.5s.

Шаг 3 (второй этап планирования).

Рассматриваем чистые стратегии.

- I вариант : u(s,0,0)

B3(s) = 2s + B2*(0.8s) = 2s + 6,5*0,8s = 7.2s

- II вариант : u(0,s,0)

B3(s) = 3s + B2*(0.7s) = 3s + 6,5*0,7s = 7.55s

- III вариант : u(0,0,s)

B3(s) = 5s + B2*(0.1s) = 5s + 6,5*0,1s = 5,65s

Оптимален II вариант B3*(s) = 7.55s).

Шаг 4 (первый этап планирования).

Рассматриваем чистые стратегии.

- I вариант : u(s,0,0)

B4(s) = 2s + B3*(0.8s) = (2 + 7,55*0,8)s = 8,04s

- II вариант : u(0,s,0)

B4(s) = 3s + B3*(0.7s) = (3 + 7,55*0,7)s = 8,285s

- III вариант : u(0,0,s)

B4(s) = 5s + B3*(0.1s) = (5 + 7,55*0,1)s = 5,755s

Оптимален II вариант B4*(s) = 8,285s.

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

	Средства, тыс. уе.	I предпр	II предпр	IIIпредпр	Остаток, тыс.уе.	Доход
I квартал	100	0	100	0	70	300
II квартал	70	0	70	0	49	210
III квартал	49	0	49	0	34.3	147
IV квартал	34.3	0	0	34.3		171,5
			Суммарный доход =	828,5

Литература

1. Беспалов М.С. Линейное программирование. Владимир: ВлГУ. 1999

2. Галкин А.А. Математическая экономика. Владимир: ВлГУ. 2006

3. Справочник по математике для экономистов. Под ред. В.И. Ермакова. М.: Высшая школа. 1987.

4. Красс М.С., Чупрынов Б.П. Математика для экономистов. СПб: Питер. 2006.

5. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М.: Высшая школа. 1980.

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

...