Экономико- математические методы и прикладные модели (вариант 10)

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

f(x₁,x₂) = 2x₁+x₂о max, min

x₁+2 ³ 3

21 + 32 £ 15

21 - 2,52 £ 10

0£2£4

x₁³0

1. Построим ОДР задачи (рис. 1).

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

Функциональные ограничения (неравенства) определяют область, являющуюся пересечением нижних полуплоскостей с граничными прямыми:

       I.      1+2 = 3

    II.      21 + 32 <= 15

.      21 - 2,52 <= 10

IV.      2 = 4

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

2. Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину Ñ(2,1) с началом координат О (0,0).

3. Построим некоторую линию уровня 21 + 12 = а. Пусть, например, = 0. На рис.1 такой линии уровня отвечает прямая Х, перпендикулярная вектор-градиенту.

4. При максимизации ЦФ необходимо перемещать линию уровня Х в направлении вектор-градиента, при минимизации - в противоположном направлении. Предельными точками при таком движении линии уровня Х являются соответственно точка A и точка B. Далее она выходит из ОДР.

X

F

B

E

D

C

Рис. 1

Определим координаты точки A, являющейся точкой пересечения третьей прямой и оси абсцисс:

21 - 2,52 = 10

х₂ = 0

х₁ = 5

Таким образом, ЦФ в ЗЛП принимает при х₁ = 5; 2 = 0 максимальное значение, равное 1, х₂) = 5´2 + 0´1 = 10.

Определим координаты точки В, являющейся точкой пересечения первой прямой и оси ординат:

x₁+2 = 3

х₁ = 0

х₂ = 3

Таким образом, ЦФ в ЗЛП принимает при х₁ = 0; 2 = 3 минимальное значение, равное 1, х₂) = 0´2 + 3´1 = 3.

2.1.

min f(X) = x₁ - 4x₂

x₁ + x₂ ≤ 5

3x₁ - x₂ ≤ 3

x_1,2 ≥ 0

Решение.

После приведения к канонической форме получим

f(X)=x₁ -4x₂ +0*x₃ +0*x₄ максимизируется

Ограничения приобрели следующую форму:

1*x₁ +1*x₂ +1*x₃ +0*x₄ =5

3*x₁ -1*x₂ +0*x₃ +1*x₄ =3

В результате получим следующую симплекс-таблицу:

Ci/Cj	B	Базис	1	2	3	4	Q
0	5	3	1	1	1	0	5
0	3	4	3	-1	0	1	1
дельта			-1	4	0	0
0	4	3	0	1,	1	-0,
1	1	1	1	-0,	0	0,
дельта	1		0	3,66	0	0,33

решение достигнуто при х₁ = 1 и х₂ = 0 и равно 1.

2.2.

max f(X) = (x₁ - 24x₂ + 12x₃)

-x₁ - 3x₂ + 2x₃ ≤ 1

-x₁ + 4x₂ - x₃ ≥ 2

x_1,2,3 ≥ 0

Решение.

После приведения к канонической форме получим

f(X)=1*x₁ -24*x₂ +12*x₃ +0*x₄ +0*x₅ +0*x₆ максимизируется

Ограничения приобрели следующую форму:

-1*x₁ -3*x₂ +2*x₃ +1*x₄ +0*x₅ +0*p₁ =1

-1*x₁ +4*x₂ - 1*x₃ +0*x₄ -1*x₅ +1*p₁ =2

В результате получим следующую симплекс-таблицу:

Ci/Cj	B	Базис	1	2	3	4	5	P1	Q
0	1	4	-1	-3	2	1	0	0	-0,
-m	2	P1	-1	4	-1	0	-1	1	0,5
дельта			m-1	-4m+24	m-12	0	m	0
0	2,5	4	-1,75	0	1,25	1	-0,75	0	2
-24	0,5	2	-0,25	1	-0,25	0	-0,25	0	-2
дельта			5	0	-6	0	6	0
12	2	3	-1,3	0	1	0,8	-0,5	0	-1,42857142857143
-24	1	2	-0,5	1	0	0,2	-0,4	0	-1,7
дельта			-3,4	0	0	4,8	2,4	0

решения нет, так как Q<0

3.

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

Вид ресурсов	Нормы расхода ресурсов на ед. продукции	Запасы ресурсов
I вид	II вид	вид
Труд	3	6	4	2
Сырье 1	20	15	20	15
Сырье 2	10	15	20	7400
Оборудование	0	3	5	1500
Цена изделия	6	10	9

При решении задачи на максимум общей стоимости выпускаемой продукции (вся готовая продукция реализуется) были получены следующие результаты: X₁ = 520, X₂ = 0, X₃ = 110.

Требуется:

1) сформулировать прямую оптимизационную задачу на максимум общей стоимости выпускаемой продукции, пояснить нулевые значения X₂;

2) сформулировать двойственную задачу и найти ее оптимальный план;

3) проанализировать использование ресурсов в оптимальном плане;

4) определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении запаса сырья 1 на 24 ед.;

5) определить целесообразность включения в план изделия четвертого вида ценой 11 ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.

Решение:

Обозначим через х_j,

max (61+102 + 93)

31 + 6х₂ + 4х₃ £ 2

201 + 15х₂ + 20х₃ £ 15

10x₁ + 15х₂ + 20х_{3 а}£ 7400

3х₂ + 5х_{3 а}£ 1500

x_j³0,

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

Проверим, как довлетворяется система функциональных ограничений оптимальным планом X^* = (1 = 520,2 = 0,х₃ = 110) :

3*520 + 6*0 + 4*110 = 2

20*520 + 15*0 + 20*110 =12600 < 15 (*)

10*520 + 15*0 + 20*110 _а= 7400

3*0 + 5*110 =550 < 1500

Значение целевой функции на этом плане равно

f(X) = 6

Двойственная задача имеет вид:

min (21+152 +7400у₃+1500y₄)

3у₁+20y₂+10y₃³6

6y₁+15y₂+15y₃+3y₄³10

4y₁+20y₂+20y₃+5y₄³9

y_1,2,3,4³0.

Для нахождения оценок у₁, у₂, у₃ используем вторую теорему двойственности. Поскольку второе и четвертое ограничения в (*) выполняется как строгое неравенство, то у₂ = 0, у₄ = 0. Так как х₁ > 0 и 3 > 0, то:

31^* + 202^* + 103^* - 6 = 0

4y₁^*+ 20y2^* + 20y₃^*+5y₄^* - 9 = 0.

Итак, для получения двойственных оценок имеем систему линейных уравнений:

y₂^* = 0

y₄^* = 0

3y₁^* + 20y₂^* + 10y₃^* = 6

4y₁^*+ 20y2^* + 20y₃^*+5y₄^* = 9.

т.е. y₁^* =3/2, y₂^* = 0, y₃^* = 3/20, y₄^* = 0.

Вычислим значение целевой функции двойственной задачи:

2y₁+15y₂ +7400у₃+1500y₄

j(Y) = 2x3/2 + 15x0 + 7400x3/20 + 1500x0 = 4110, т.е. f(X^*) = *) = 4110.

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

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

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

В рассматриваемом примере величение фонда труда на 1 час привело бы к росту максимальной суммы прибыли на 1,5 (у₁ = 3/2), величение сырья 2 не повлияет на оптимальный план выпуска продукции и сумму прибыли.

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

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

В данном примере недефицитным ресурсом является сырье 1 поскольку у₂ = 0 и оборудование, поскольку y₄=0.

Острее ощущается дефицитность труда (у₁ = 3/2) - он более дефицитен, чем сырье 2 (у₃= 3/20).

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

В нашем примере относительная заменяемость ресурсов определяется соотношением (нормой) 3/20 : 3/2 = 1:10.

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

если а<- выгодно,

если D_j > 0 - невыгодно.

Предположим в рассматриваемом примере следует решить вопрос о целесообразности включения в программу изделия четвертого вида ценой 11 ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.

С четом сказанного будем иметь в двух рассматриваемых случаях:

8*3/2+4*0+20*3/20+6*0-11 = 4>0 - невыгодно расширение ассортимента;

Ответим на вопрос, как изменится объем выпуска продукции и прибыль от ее реализации, сырье 1 величится на 24 ед.

Предполагая, что эти изменения проходят в пределах стойчивости двойственных оценок аимеем:

201 + 15*0 + 20х₃ = 15024

Отсюда определяется что в новых производственных словиях задача решения не имеет, то есть прибыль не изменится, сырья 1 будет при этом избыток.

4.

Оптовый склад обслуживает 30 предприятий-потребителей материалов. Каждое из предприятий направляет на склад автомашину в среднем один раз в смену (смена - 8 ч). Средняя продолжительность погрузки одной автомашины составила 48 мин, т.е. 0,1 смены. Погрузка осуществляется кранами. Потери склада, связанные с простоем крана (включая крановщика и стропальщиков) из-за отсутствия автомашин, равны 5 у.е./ч.

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

Отсюда следует m=30, l<=1, t_об=0,1.

Определите:

1) оптимальное количество необходимых складу кранов, при котором суммарные ожидаемые потери склада, связанные с простоем кранов (из-за отсутствия автомашин) и простоем автомашин в очереди, были бы минимальными;

2) коэффициент простоя крана;

3) среднее число автомашин, находящихся в очереди (длину очереди);

4) коэффициент и среднее время простоя автомашины в очереди.

Решение.

Так как из словия следует, что для полного обслуживания 30 машин требуется как минимум 3 крана, то при расчетах количества кранов n примем n от 3 до 7. Получим:

При n<=3 рассчитаем P_k при k от 0 до 30 по формулам P_k<= kP₀, (1 £ аи

k<=kP₀, (Затем, так как

0=1/28,97257374=0,034515401. Отсюда найдем P_1-30 и по формуле , где анайдем коэффициент простоя автомобиля. Далее по формуле , где анайдем коэффициент простоя крана. Тогда потери от простоя кранов и автомашин будут равняться 2,6´30´1+5´3=7,68 у.е.

k	Pk*p0	Pk	(k-n)Pk		(n-k)Pk
0	1	0,034515	0		0,103546
1	3	0,103546	0		0,207092
2	4,35	0,150142	0		0,150142
3	4,06	0,140133	0		0
4	3,654	0,126119	0,126119		0
5	3,1668	0,109303	0,218607		0
6	2,639	0,091086	0,273258		0
7	2,2	0,072869	0,291476		0
8	1,618587	0,055866	0,279331		0
9	1,186963556	0,040969	0,245811		0
10	0,830874489	0,028678	0,200746		0
11	0,553916326	0,019119	0,152949		0
12	0,350813673	0,012108	0,108976		0
13	0,210488204	0,007265	0,072651		0
14	0,119276649	0,004117	0,045286		0
15	0,063614213	0,002196	0,026348		0
16	0,031807106	0,001098	0,014272		0
17	0,014843316	0,512	0,007173		0
18	0,006432104	0,	0,00		0
19	0,002572841	8,88E-05	0,001421		0
20	0,943375	3,26E-05	0,554		0
21	0,314458	1,09E-05	0,195		0
22	9,43375E-05	3,26E-06	6,19E-05		0
23	2,51567E-05	8,68E-07	1,74E-05		0
24	5,86989E-06	2,03E-07	4,25E-06		0
25	1,17398E-06	4,05E-08	8,91E-07		0
26	1,95663E-07	6,75E-09	1,55E-07		0
27	2,60884E-08	9E-10	2,16E-08		0
28	2,60884E-09	9E-11	2,25E-09		0
29	1,73923E-10	6E-12	1,56E-10		0
30	5,79742E-12	2E-13	5,4E-12		0
Сумма	28,97257374	Коэф. Прост. Автом.	0,068953	Коэф. Прост. Кранов	0,153594
l	1
n	3
m	30
tоб	0,1
P0	0,034515401
Потери	7,688263
средняя длина очереди	2,068586634
Среднее время простоя требования в очереди на обслуживание	0,068952

налогично рассчитаем суммы потерь для n=4,5,6,7 (данные в таблицах).

n<=4

k	Pk*p0	Pk	(k-n)Pk		(n-k)P
0	1	0,051226	0		0,204905
1	3	0,153679	0		0,461036
2	4,35	0,834	0		0,445668
3	4,06	0,207978	0		0,207978
4	2,7405	0,140385	0		0
5	1,781325	0,091251	0,091251		0
6	1,113328125	0,057032	0,114063		0
7	0,667996875	0,034219	0,102657		0
8	0,384098203	0,019676	0,078704		0
9	0,211254012	0,010822	0,054109		0
10	0,110908356	0,005681	0,034088		0
11	0,055454178	0,002841	0,019885		0
12	0,026340735	0,001349	0,010795		0
13	0,011851	0,607	0,005465		0
14	0,005037665	0,258	0,002581		0
15	0,002015066	0,103	0,001135		0
16	0,75565	3,87E-05	0,465		0
17	0,264477	1,35E-05	0,176		0
18	8,59552E-05	4,4E-06	6,16E-05		0
19	2,57866E-05	1,32E-06	1,98E-05		0
20	7,0913E-06	3,63E-07	5,81E-06		0
21	1,77283E-06	9,08E-08	1,54E-06		0
22	3,96E-07	2,04E-08	3,68E-07		0
23	7,91E-08	4,09E-09	7,76E-08		0
24	1,3961E-08	7,15E-10	1,43E-08		0
25	2,09415E-09	1,07E-10	2,25E-09		0
26	2,61769E-10	1,34E-11	2,95E-10		0
27	2,61769E-11	1,34E-12	3,08E-11		0
28	1,96327E-12	1,01E-13	2,41E-12		0
29	9,81633E-14	5,03E-15	1,26E-13		0
30	2,45408E-15	1,26E-16	3,27E-15		0
Сумма	19,52125277	Коэф. Прост. Автом.	0,017182	Коэф. Прост. Кранов	0,329897
l	1
n	4
m	30
tob	0,1
P0	0,051226221
Потери	7,938138029
средняя длина очереди	0,515461855
Среднее время простоя требования в очереди на обслуживание	0,017182062

n=5

k	Pk*p0	Pk	(k-n)Pk
0	1	0,055853	0		0,279265
1	3	0,167559	0		0,670236
2	4,35	0,24296	0		0,721
3	4,06	0,226763	0		0,453526
4	2,7405	0,153065	0		0,153065
5	1,42506	0,079594	0		0
6	0,71253	0,039797	0,039797		0
7	0,3420144	0,019103	0,038205		0
8	0,157326624	0,008787	0,026361		0
9	0,069223715	0,003866	0,015465		0
10	0,02907396	0,001624	0,008119		0
11	0,011629584	0,65	0,003897		0
12	0,004419242	0,247	0,001728		0
13	0,001590927	8,89E-05	0,711		0
14	0,540915	3,02E-05	0,272		0
15	0,173093	9,67E-06	9,67E-05		0
16	5,19279E-05	2,9E-06	3,19E-05		0
17	1,45398E-05	8,12E-07	9,75E-06		0
18	3,78035E-06	2,11E-07	2,74E-06		0
19	9,07284E-07	5,07E-08	7,09E-07		0
20	1,99602E-07	1,11E-08	1,67E-07		0
21	3,99205E-08	2,23E-09	3,57E-08		0
22	7,18569E-09	4,01E-10	6,82E-09		0
23	1,14971E-09	6,42E-11	1,16E-09		0
24	1,60959E-10	8,99E-12	1,71E-10		0
25	1,93151E-11	1,08E-12	2,16E-11		0
26	1,93151E-12	1,08E-13	2,27E-12		0
27	1,54521E-13	8,63E-15	1,9E-13		0
28	9,27126E-15	5,18E-16	1,19E-14		0
29	3,7085E-16	2,07E-17	4,97E-16		0
30	7,41701E-18	4,14E-19	1,04E-17		0
Сумма	17,90415386	Коэф. Прост. Автом.	0,00449	Коэф. Прост. Кранов	0,456995
l	1
n	5
m	30
tob	0,1
P0	0,055852961
Потери	11,77507748
средняя длина очереди	0,134697983
Среднее время простоя требования в очереди на обслуживание	0,004489933

n=6

k	Pk*p0	Pk	(k-n)Pk
0	1	0,056985	0		0,341908
1	3	0,170954	0		0,854769
2	4,35	0,247883	0		0,991532
3	4,06	0,231358	0		0,694073
4	2,7405	0,156166	0		0,312
5	1,42506	0,081206	0		0,081206
6	0,593775	0,033836	0		0
7	0,23751	0,013534	0,013534		0
8	0,0910455	0,005188	0,010376		0
9	0,08335	0,001902	0,005707		0
10	0,011684173	0,	0,002663		0
11	0,003894724	0,	0,00		0
12	0,001229	7,03E-05	0,422		0
13	0,36	2,11E-05	0,148		0
14	0,104833	5,97E-06	4,78E-05		0
15	2,79E-05	1,59E-06	1,43E-05		0
16	6,97E-06	3,98E-07	3,98E-06		0
17	1,63074E-06	9,29E-08	1,02E-06		0
18	3,53326E-07	2,01E-08	2,42E-07		0
19	7,06652E-08	4,03E-09	5,23E-08		0
20	1,29553E-08	7,38E-10	1,03E-08		0
21	2,15921E-09	1,23E-10	1,85E-09		0
22	3,23882E-10	1,85E-11	2,95E-10		0
23	4,31843E-11	2,46E-12	4,18E-11		0
24	5,03817E-12	2,87E-13	5,17E-12		0
25	5,03817E-13	2,87E-14	5,45E-13		0
26	4,19847E-14	2,39E-15	4,78E-14		0
27	2,79898E-15	1,59E-16	3,35E-15		0
28	1,39949E-16	7,97E-18	1,75E-16		0
29	4,66497E-18	2,66E-19	6,11E-18		0
30	7,77495E-20	4,43E-21	1,06E-19		0
Сумма	17,54859792	Коэф. Прост. Автом.	0,001134	Коэф. Прост. Кранов	0,54597
l	1
n	6
m	30
tob	0,1
P0	0,05698461
Потери	16,46757489
средняя длина очереди	0,034027493
Среднее время простоя требования в очереди на обслуживание	0,00113425

n=7

k	Pk*p0	Pk	(k-n)Pk
0	1	0,057242	0		0,400696
1	3	0,171727	0		1,030362
2	4,35	0,249004	0		1,245021
3	4,06	0,232404	0		0,929615
4	2,7405	0,156873	0		0,470618
5	1,42506	0,081574	0		0,163147
6	0,593775	0,033989	0		0,033989
7	0,20358	0,011653	0		0
8	0,066890571	0,003829	0,003829		0
9	0,021022751	0,001203	0,002407		0
10	0,006306825	0,361	0,001083		0
11	0,00180195	0,103	0,413		0
12	0,489101	2,8E-05	0,14		0
13	0,125769	7,2E-06	4,32E-05		0
14	3,05438E-05	1,75E-06	1,22E-05		0
15	6,98145E-06	4E-07	3,2E-06		0
16	1,49602E-06	8,56E-08	7,71E-07		0
17	2,99205E-07	1,71E-08	1,71E-07		0
18	5,55E-08	3,18E-09	3,5E-08		0
19	9,52571E-09	5,45E-10	6,54E-09		0
20	1,4969E-09	8,57E-11	1,11E-09		0
21	2,13842E-10	1,22E-11	1,71E-10		0
22	2,7494E-11	1,57E-12	2,36E-11		0
23	3,14217E-12	1,8E-13	2,88E-12		0
24	3,14217E-13	1,8E-14	3,06E-13		0
25	2,69329E-14	1,54E-15	2,78E-14		0
26	1,92378E-15	1,1E-16	2,09E-15		0
27	1,0993E-16	6,29E-18	1,26E-16		0
28	4,7113E-18	2,7E-19	5,66E-18		0
29	1,34609E-19	7,71E-21	1,7E-19		0
30	1,92298E-21	1,1E-22	2,53E-21		0
Сумма	17,46959135	Коэф. Прост. Автом.	0,264	Коэф. Прост. Кранов	0,610493
l	1
n	7
m	30
tob	0,1
P0	0,057242324
Потери	21,38786196
средняя длина очереди	0,007931
Среднее время простоя требования в очереди на обслуживание	0,264367

В ререзультате анализа данных получим, что минимальная сумма потерь будет равна 7,68 у. е. при n=3. Тогд коэффициент простоя крана будет равен 0,153594, длина очереди 2,068586634 (рассчитывается по формуле