1.Решитеграфическим методом задачу линейного программирования. Найти максимум и минимумфункции f(X) при заданных ограничениях.
f(x1,x2)= 2x1+x2®max, min
x1+x2 ³3
2x1+ 3x2£15
2x1– 2,5x2£10
0£x2£4
x1³0
1. Построим ОДР задачи (рис. 1).
Прямые ограниченияозначают, что область решений будет лежать в первой четверти Декартовой системыкоординат.
Функциональныеограничения (неравенства) определяют область, являющуюся пересечением нижнихполуплоскостей с граничными прямыми:
I. x1+x2 =3
II. 2x1+ 3x2=15
III. 2x1– 2,5x2=10
IV. x2= 4
Пересечениеуказанных полуплоскостей в первой четверти представляет собой многоугольник OBFCDAE(заштрихованная общая область длявсех ограничений задачи ОДР).
2. Для определения направления движения к оптимумупостроим вектор-градиент, соединив его вершину Ñ(2,1) с началомкоординат О (0,0).
3. Построимнекоторую линию уровня 2x1+ 1x2= а.Пусть, например, а = 0. На рис.1 такой линии уровня отвечает прямая Х,перпендикулярная вектор-градиенту.
4. При максимизации ЦФ необходимо перемещать линиюуровня Х в направлении вектор-градиента, а при минимизации — в противоположномнаправлении. Предельными точками при таком движении линии уровня Х являютсясоответственно точка Aи точка B. Далее онавыходит из ОДР.
X
F
B
E
D
C Рис. 1
Определим координаты точки A, являющейся точкой пересечения третьейпрямой и оси абсцисс:
2x1– 2,5x2= 10
х2 = 0
х1 = 5
Такимобразом, ЦФ в ЗЛП принимает при х1 = 5; x2= 0максимальное значение, равное f(x1, х2) = 5´2 + 0´1 = 10.
Определим координаты точки В, являющейся точкойпересечения первой прямой и оси ординат:
x1+x2 = 3
х1 = 0
х2 = 3
Такимобразом, ЦФ в ЗЛП принимает при х1 = 0; x2= 3минимальное значение, равное f(x1, х2) = 0´2 + 3´1 = 3.
2.1.
min f(X) = x1 — 4x2
x1+ x2 ≤ 5
3x1 — x2 ≤ 3
x1,2 ≥ 0
Решение.
После приведения к канонической форме получим
f(X)=x1 -4x2 +0*x3 +0*x4максимизируется
Ограничения приобрели следующую форму:
1*x1 +1*x2 +1*x3 +0*x4 =5
3*x1 -1*x2 +0*x3 +1*x4 =3
В результате получим следующую симплекс-таблицу:
Ci/Cj
B
Базис
А1
А2
А3
А4
Q
5
А3
1
1
1
5
3
А4
3
-1
1
1
дельта
-1
4
4
А3
1,33333
1
-0,33333
1
1
А1
1
-0,33333
0,33333
дельта
1
3,66
0,33
решение достигнуто при х1 = 1 и х2 = 0и равно 1.
2.2.
max f(X) = (x1 — 24x2+ 12x3)
-x1 — 3x2 + 2x3≤ 1
-x1 + 4x2 – x3≥ 2
x1,2,3≥ 0
Решение.
После приведения к канонической форме получим
f(X)=1*x1 -24*x2 +12*x3 +0*x4+0*x5 +0*x6 максимизируется
Ограничения приобрели следующую форму:
-1*x1 -3*x2+2*x3 +1*x4 +0*x5 +0*p1 =1
-1*x1 +4*x2 — 1*x3 +0*x4 -1*x5 +1*p1 =2
В результате получим следующую симплекс-таблицу:
Ci/Cj
B
Базис
А1
А2
А3
А4
А5
P1
Q
1
А4
-1
-3
2
1
-0,333333333333333
-m
2
P1
-1
4
-1
-1
1
0,5
дельта
m-1
-4m+24
m-12
m
2,5
А4
-1,75
1,25
1
-0,75
2
-24
0,5
А2
-0,25
1
-0,25
-0,25
-2
дельта
5
-6
6
12
2
А3
-1,39999
1
0,8
-0,59999
-1,42857142857143
-24
1
А2
-0,59999
1
0,2
-0,4
-1,66666666666667
дельта
-3,4
4,8
2,4
решения нет, так как Q
3.
Для изготовления трех видов продукции используют четыре вида ресурсов.Запасы ресурсов, нормы расхода и цены реализации единицы каждого вида продукцииприведены в таблице.
Вид ресурсов
Нормы расхода ресурсов на ед. продукции
Запасы ресурсов
I вид
II вид
III вид
Труд
3
6
4
2000
Сырье 1
20
15
20
15000
Сырье 2
10
15
20
7400
Оборудование
3
5
1500
Цена изделия
6
10
9
При решении задачи на максимум общей стоимости выпускаемой продукции (всяготовая продукция реализуется) были получены следующие результаты: X1= 520, X2 = 0, X3 = 110.
Требуется:
1) сформулировать прямую оптимизационную задачу на максимум общей стоимостивыпускаемой продукции, пояснить нулевые значения X2;
2) сформулировать двойственную задачу и найти ее оптимальный план;
3) проанализировать использование ресурсов в оптимальном плане;
4) определить, как изменятся общая стоимость продукции и план ее выпуска приувеличении запаса сырья 1 на 24 ед.;
5) определить целесообразность включения в план изделия четвертого видаценой 11 ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.
Решение:
Обозначимчерез хj, j=1,3- объем выпуска продукции j-го вида и запишем математическую модель задачикритерию «максимум прибыли»:
max(6x1+10x2+ 9x3)
3x1+ 6х2 + 4х3 £2000
20x1+ 15х2 + 20х3£15000
10x1+ 15х2 + 20х3 £7400
3х2+ 5х3 £1500
xj³0, j=1,2,3.
В этой модели функциональные ограничения отражаютусловия ограниченности объемов используемых в производстве ресурсов.
Проверим,как удовлетворяется система функциональных ограничений оптимальным планом X*= (x1= 520,x2= 0, х3= 110) :
3*520 + 6*0+ 4*110 = 2000
20*520+ 15*0 + 20*110 =12600
10*520 +15*0 + 20*110 = 7400
3*0 + 5*110=550
Значениецелевой функции на этом плане равно
f(X) = 6x520 + 10x0 + 9x110 = 4110.
Двойственная задача имеет вид:
min(2000y1+15000y2+7400у3+1500y4)
3у1+20y2+10y3³6
6y1+15y2+15y3+3y4³10
4y1+20y2+20y3+5y4³9
y1,2,3,4³0.
Длянахождения оценок у1, у2, у3 используем вторуютеорему двойственности. Поскольку второе и четвертое ограничения в (*)выполняется как строгое неравенство, то у2 = 0, у4 = 0.Так как х1 > 0 и x3> 0,то:
3y1* + 20y2* + 10y3* — 6 = 0
4y1*+ 20y2* +20y3*+5y4* — 9= 0.
Итак, для получения двойственных оценок имеемсистему линейных уравнений:
y2*= 0
y4* = 0
3y1* + 20y2* +10y3* = 6
4y1*+ 20y2* + 20y3*+5y4*= 9.
т.е. y1* =3/2,y2* = 0, y3* = 3/20, y4*= 0.
Вычислим значение целевой функции двойственнойзадачи:
2000y1+15000y2+7400у3+1500y4
j(Y) = 2000x3/2 + 15000x0 + 7400x3/20 + 1500x0 = 4110, т.е. f(X*)= j(Y*) = 4110.
По первой теореме двойственности мы можемутверждать, что действительно найдены оптимальные значения двойственныхпеременных.
Экономико-математическийанализ оптимальных решений базируется на свойствах двойственных оценок. Впределах устойчивости двойственных оценок имеют место следующие свойства.
1. Величина двойственной оценки того или иногоресурса показывает насколько возросло бы максимальное значение целевой функции,если бы объем данного ресурса увеличился на одну единицу (двойственные оценкиизмеряют эффективность малых приращений объемов ресурсов в конкретных условияхданной задачи).
Врассматриваемом примере увеличение фонда труда на 1 час привело бы к ростумаксимальной суммы прибыли на 1,5 (у1 = 3/2), а увеличение сырья 2не повлияет на оптимальный план выпуска продукции и сумму прибыли.
Сказанное позволяет выявить направления «расшивки»узких мест, обеспечивающие получение наибольшего экономического эффекта, атакже целесообразность изменения в структуре выпуска продукции с позиций общегооптимума.
2. Двойственные оценки отражают сравнительнуюдефицитность различных видов ресурсов в отношении принятого в задаче показателяэффективности. Оценки показывают, какие ресурсы являются более дефицитными (онибудут иметь самые высокие оценки), какие менее дефицитными и какие совсемнедефицитны (избыточны).
В данномпримере недефицитным ресурсом является сырье 1 поскольку у2 = 0 иоборудование, поскольку y4=0.
Острее ощущаетсядефицитность труда (у1 = 3/2) — он более дефицитен, чем сырье 2 (у3=3/20).
3. Двойственные оценки позволяют определятьсвоеобразные «нормы заменяемости ресурсов»: имеется в виду не абсолютнаязаменяемость ресурсов, а относительная, т.е. заменяемость с точки зренияконечного эффекта и лишь в конкретных условиях данной задачи.
В нашем примере относительная заменяемость ресурсовопределяется соотношением (нормой) 3/20: 3/2 = 1:10.
4. Двойственные оценки служат инструментомопределения эффективности отдельных хозяйственных решений (технологическихспособов), с их помощью можно определять выгодность производства новых изделий,эффективность новых технологических способов:
если — выгодно,
если Dj> 0 — невыгодно.
Предположим в рассматриваемом примере следует решитьвопрос о целесообразности включения в программу изделия четвертого вида ценой11 ед., если нормы затрат ресурсов 8, 4, 20 и 6 ед.
С учетом сказанного будем иметь в двухрассматриваемых случаях:
8*3/2+4*0+20*3/20+6*0-11 = 4>0-невыгоднорасширение ассортимента;
Ответим навопрос, как изменится объем выпуска продукции и прибыль от ее реализации, сырье1 увеличится на 24 ед.
Предполагая,что эти изменения проходят в пределах устойчивости двойственных оценок имеем:
20x1+ 15*0 + 20х3 = 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 рассчитаем Pk при k от 0 до 30 по формулам Pk= akP0, (1 £k£n), где и Pk=akP0, (n£k£m), где Затем, так как P0=1/28,97257374=0,034515401.Отсюда найдем P1-30 и по формуле , где найдем коэффициентпростоя автомобиля. Далее по формуле , где найдем коэффициентпростоя крана. Тогда потери от простоя кранов и автомашин будут равняться 2,6´30´a1+5´n´a3=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,1112
0,072869
0,291476
0
8
1,618586667
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,000512
0,007173
0
18
0,006432104
0,000222
0,00333
0
19
0,002572841
8,88E-05
0,001421
0
20
0,000943375
3,26E-05
0,000554
0
21
0,000314458
1,09E-05
0,000195
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