Контрольная работа по «Высшей математике»

 

5. В экономическом районе четыре  предприятия, выпускающие однородную  продукцию, объемы которых соответственно равны а1,а2 и а3, и удовлетворяющие потребности потребителей в объемах, которые равны b1,b2 , b3, b4.

 

Решение

Стоимости перевозки единицы продукции от предприятия к потребителю заданы матрицей (С)=cij. Требуется:

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

 

Мощности поставщиков	Мощности потребителей
	50	60	60	40
80	5	4	3	6
70	8	3	2	1
40	7	3	5	1

 

Запишем целевую функцию, которая минимизирует затраты на перевозку продукции, введя также Xij – объем перевозимой продукции

F(x)= 5x11 + 4x12 + 3x13 + 6x14+ 8x21 + 3x22 + 2x23 + x24 + 7x31 + 3x32 + 5x33 + x34

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

x11 + x12 + x13 + x14 =80

x21 + x22 + x23 + x24 =70

x31 + x32 + x33 + x34 =40

x11 + x21 + x31 ≤50

x12 + x22 + x32 ≤60

x13 + x23 + x33 ≤60

x14 + x24 + x34 ≤40

Для преобразования задачи в задачу закрытого типа вводим фиктивного потребителя с недостающей потребностью в 20 ед. и нулевыми тарифами.

Решим задачу методом потенциалов. Для начала определим начальный план методом минимального элемента.

	50	60	60	40
80	5                                 30	4                  20	3                  30	6
70	8	3	2                  30	1                   40
40	7	3                   40	5	1
20	0                  20	0	0	0

 

План невырожден, так как число занятых клеток равно 7=4+4-1. Далее найдем потенциалы и оценки свободных клеток.

	50	60	60	40	U
80	5                                 30	4                20	3                30	6	0
70	8	3	2                30	1                40	-1
40	7	3                40	5	1	-1
20	0                20	0	0	0	-5
V	5	4	3	2

 

S14 =6-0-2=4

S21 =8-(-1)-5=4

S22 =3-(-1)-4=0

S31 =7-(-1)-5=3

S33 =5-3-(-1)=3

S34 =1-2-(-1)=0

S42 =0-4-(-5)=1

S43 =0-3-(-5)=2

S44 =0-2-(-5)=3

Так как все оценки положительны, можем рассчитать целевую функцию

F(x)= 5*30 + 4*20 + 3*30 + 2*30 + 40 + 3*40 = 540 ден.ед.

В данных условиях остался неудовлетворенный спрос у первого потребителя в размере 20 ед.

 

 

6. Для реконструкции и модернизации  производства выделены денежные  средства в объеме 100 тыс.дол., которые  следует распределить между 4 цехами. По каждому из них известен прирост zi(x) выпуска продукции в зависимости от выделенной суммы. Требуется:

1) построить математическую модель  задачи в виде уравнений Беллмана

2) найти оптимальное распределение  средств, обеспечивающее максимальный  прирост выпуска продукции.

 

Ден.средства, тыс.дол.	z1(x)	z2(x)	z3(x)	z4(x)
0	0	0	0	0
20	12	14	11	16
40	28	26	24	21
60	39	40	43	36
80	47	51	51	49
100	69	68	68	72

 

Решение

Обозначим через ui количество средств, выделенных i–му предприятию. Суммарная прибыль равна

 Z= .                                                   (6.1)

Переменные xk удовлетворяют ограничениям

=100, xi ³ 0, i = 1, 2, 3, 4.                            (6.2)

Требуется найти переменные x1, x2, x3, x4, удовлетворяющие (6.2) и обращающие в максимум функцию (6.1).

Схема решения задачи ДП: процесс решения распределения средств q0 = 4 можно рассматривать как четырехшаговый, номер шага совпадает с номером предприятия; выбор переменных x1, x2, x3, x4 – управление соответственно на 1, 2, 3 и 4 шагах; — конечное состояние процесса распределения – равно 0, т.к. все средства должны быть вложены. Схема распределения показана на рис. 6.1.

 

 

 

              

         

                                                                

Рис. 6.1

 

Уравнения состояний в данной задаче имеют вид qk  = qk–1 – xk, k=1, 2, 3, 4, где qk – параметр состояния – количество средств, оставшихся после k–го шага, т.е. средства, которые остается распределить между оставшимися 4–k предприятиями.

Zk*(qk–1) – условная оптимальная прибыть, полученная от k–го, (k+1)–го, …, 4 предприятий, если между ними оптимальным образом распределялись средства qk–1. Допустимые управления на k–м шаге удовлетворяют условию  0 £ хk £ qk–1.

Уравнения Беллмана имеют вид:

    к = 4,  q4=0 Þ Z4*(q3)=max f4(x4), 0 £ x4 £ q3;

Z3*(q2)=max {f3(x3) + Z4*(q3)},  0 £ x3 £ q2;

Z2*(q1)=max {f2(x2) + Z3*(q2)},  0 £ x2 £ q1;

Z1*(4)=max {f1(x1) + Z2*(q1)},  0 £ x3 £ 100.

4 шаг (i = 4). В таблице z4(x) прибыли монотонно возрастают, поэтому все средства, оставшиеся к IV шагу, следует вложить в 4–е предприятие. Для возможных значений q3  = 0, 20, 40, 60, 80, 100 получим Z4*(q3)=z4(q3) и x4*(q3)=q3.

3 шаг (i = 3). Делаем все предположения относительно остатка средств q2 к 3 шагу, т.е. после выбора u1 и u2. q2  = 0, 20, 40, 60, 80, 100 (0 – все средства отданы 1 и 2–му предприятиям, 100 – 1–е и 2–е предприятия ничего не получили и т.д.) В зависимости от этого выбираем 0 £ x3 £ q2, находим q3=q2 – x3 и сравниваем для разных x3 при фиксированном q2 значения суммы z3(x3)+Z4*(q3). Для каждого q2 наибольшее из этих значений есть Z3*(q2) – условная оптимальная прибыль, полученная при оптимальном распределении q2 между 3–м и 4–м предприятиями.

2 шаг. Условный оптимум приведен в той же таблице и для i = 2.  Для всех возможных значений q2 значения Z2*(q1) и x2*(q1) находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 – значения z2(x2) взяты из  таблицы, а вторые слагаемые взяты из столбца 5 таблицы при q2=q1–x2.

1 шаг. Условный оптимум приведен  и для i = 1 при q0  = 100.

 

Таблица 6.1

qi–1	xi	qi	i=3			i=2			i=1
			z3(x3)+ Z4*(q3)	Z3*(q2)	x3*(q2)	z2(x2)+ Z3*(q2)	Z2*(q1)	x2*(q1)	z1(x1)+ Z2*(q1)	Z1*(q0)	x1*(q0)
1	2	3	4	5	6	7	8	9	10	11	12
0	0	0	0	0	0	0	0	0	0	0	0
20	0 20	20 0	0+16=16 11+0=11	16	0	0+16=16 14+0=14	16	0	0+16=16 12+0=12	16	0
40	0 20 40	40 20 0	0+21=21 11+16=27 24+0=24	27	20	0+27=27 14+16=30 26+0=26	30	20	0+30=30 12+16=28 28+0=28	30	0
60	0 20 40 60	60 40 20 0	0+36=36 11+21=32 22+16=38 43+0=43	43	60	0+43=43 14+27=41 26+16=42 40+0=40	43	0	0+43=43 12+30=42 28+16=44 39+0=39	44	40
80	0 20 40 60 80	80 60 40 20 0	0+49=49 11+36=47 24+21=45 43+16=59 51+0=51	59	60	0+59=59 14+43=57 26+27=53 40+16=56 51+0=51	59	0	0+59=59 12+43=55 28+30=58 39+16=55 47+0=47	59	0
100	0 20 40 60 80 100	100 80 60 40 20 0	0+72=72 11+49=60 24+36=60 43+21=64 51+16=67 68+0=68	72	0	0+72=72 14+59=73 26+43=69 40+27=67 51+16=67 68+0=68	73	20	0+73=73 12+59=71 28+43=71 39+30=69 47+16=63 69+0=69	73	0

 

Итак, максимум суммарной прибыли Zmax=Z1*(100)=73 у. е. при

х1*=х1*(100)=0®

® q1*=100–0=100 Þ х2*=х2*(100)=20 ®

® q2*=100–20=80 Þ х3*=х3*(80)=60 ®

® q3*=80–60=20 Þ х4*=х4*(20)=20.

Выделение средств различным предприятиям:

1–му выделено 0 у. е.

2–му выделено 20 у. е.

3–му выделено 60 у. е.

4–му выделено 20 у. е.

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. Экономико-математические методы и модели: Учеб. пособие /Н.И. Холод, А.В. Кузнецов, Я.Н. Жихар и др. – Мн.: БГЭУ, 1999.
2. А.В. Кузнецов, В.А. Сакович, Н.И. Холод. Высшая математика. Математическое программирование. – Мн.: Вышэйшая школа. – 1994.
3. Замков О.О. и др. Математические методы в экономике. –М.: ДИС, 1997.