Построим математическую модель задачи.
Пусть х1-количество изделий вида 1, шт, х2 - количество изделий вида 2, шт, х3 - количество изделий вида 3, штх4 - количество изделий вида 4, шт запланированных к производству. Для их изготовления потребуется (4 х1 +20х2+5х3+2х4) единиц ресурса В1, (3х1 +х2+3х3+5х4) единиц ресурса В2, (5х2+8х3+3х4) единиц ресурса В3, (4х1 +2х2+2х3+4х4) единиц ресурса В4. Так как, потребление ресурсов В1,В2,В3,В не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
4 х1 +20х2+5х3+2х4≤5603х1 +х2+3х3+5х4≤2505х2+8х3+3х4≤6004х1 +2х2+2х3+4х4≤520
Решение
По смыслу задачи переменные х1 ≥ 0, х2 ,х3,х4≥0.
Конечную цель решаемой задачи – получение максимальной прибыли при реализации продукции – выразим как функцию двух переменных х1 и х2.х3,х4
Суммарная прибыль составит 6х1 от реализации продукции 1 и 7х 2 от реализации продукции 5х3 от реализации продукции 3, 3х4от реализации продукции 4, то есть :
F = 6х1 +7х 2+5х3+3х4→max.
2) переход к канонической форме)4x1+20x2+5x3+2x4+x5 = 560 3x1+x2+3x3+5x4+x6 = 250 5x2+8x3+3x4+x7 = 600 4x1+2x2+2x3+4x4+x8 = 520 Базисные переменные : x5, x6, x7, x8 первый опорный план: X0 = (0,0,0,0,560,250,600,520) Базисное решение называется допустимым, если оно неотрицательно.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x5 560 4 20 5 2 1 0 0 0 28
x6 250 3 1 3 5 0 1 0 0 250
x7 600 0 5 8 3 0 0 1 0 120
x8 520 4 2 2 4 0 0 0 1 260
F(X1) 0 -6 -7 -5 -3 0 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.
Базис B x1 x2 x3 x4 x5 x6 x7 x8 min
x2 28 1/5 1 1/4 1/10 1/20 0 0 0 140
x6 222 14/5 0 11/4 49/10 -1/20 1 0 0 555/7
x7 460 -1 0 27/4 5/2 -1/4 0 1 0 -
x8 464 18/5 0 3/2 19/5 -1/10 0 0 1 1160/9
F(X2) 196 -23/5 0 -13/4 -23/10 7/20 0 0 0
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. Получаем новую симплекс-таблицу:
Базис B x1 x2 x3 x4 x5 x6 x7 x8
x2 85/7 0 1 3/56 -1/4 3/56 -1/14 0 0
x1 555/7 1 0 55/56 7/4 -1/56 5/14 0 0
x7 3775/7 0 0 433/56 17/4 -15/56 5/14 1 0
x8 1250/7 0 0 -57/28 -5/2 -1/28 -9/7 0 1
F(X2) 3925/7 0 0 71/56 23/4 15/56 23/14 0 0
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Оптимальный план можно записать так: x1 = 792/7, x2 = 121/7, x3 = 0, x4 = 0 F(X) = 6*792/7 + 7*121/7 + 5*0 + 3*0 = 5605/7
3) двойственная задача линейного программирования будет иметь вид:F(Y)=560Y1+250Y2+600Y3+520Y4 (min)
Ограничения:
4Y1 + 3Y2 + 0Y3 + 4Y4
≥ 6
20Y1 + 1Y2 + 5Y3 + 2Y4
≥ 7
5Y1 + 3Y2 + 8Y3 + 2Y4
≥ 5
2Y1 + 5Y2 + 3Y3 + 4Y4
≥ 3
Y1 ≥ 0
Y2 ≥ 0
Y3 ≥ 0
Y4 ≥ 0
Wmin=3925/7
y1=15/56, y2=19/14, y3=0, y4=0
г)1-й ресурс, является дефицитным (y1 ≠ 0). 2-й ресурс является дефицитным (y2 ≠ 0). ресурс 3-го вида не является дефицитным (y3 = 0)Неиспользованный экономический резерв ресурса 3 составляет 5392/7 (600-605/7).
ресурс 4-го вида не является дефицитным y4 = 0. Неиспользованный экономический резерв ресурса 4 составляет 1784/7 (520-3413/7). 1-й продукт экономически выгодно производить (x1>0). 2-й продукт экономически выгодно производить (x2>0). продукцию 3-го вида производить экономически не выгодно (x3 = 0). При этом разница между ценами (615/56 - 5 = 115/56) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi. продукцию 4-го вида производить экономически не выгодно( x4 = 0).
Анализ устойчивости оптимального плана. Чувствительность решения к изменению коэффициентов целевой функции. Вариант расчета №1.
55/56 3/56
7/4 -1/4
-1/56 3/56
5/14 -1/14
6+Δ c1
7+Δ c2
Отсюда получаем условие устойчивости: 55/56Δc1+3/56Δc2+351/56≥0 7/4Δc1-1/4Δc2+35/4≥0 -1/56Δc1+3/56Δc2+15/56≥0 5/14Δc1-1/14Δc2+23/14≥0 Затем последовательно находим интервалы устойчивости: Δc1≠0, Δc2=0, Δc1≥-351/55, Δc1≥-5, Δc1≤15, Δc1≥-23/5 Δc2≠0, Δc1=0, Δc2≥-117, Δc2≤35, Δc2≥-5, Δc2≤23 Таким образом, 1-й параметр может быть уменьшен на 71/55 или увеличен на 15. Интервал изменения равен: (c1 - ∆c-1; c1 + ∆c1+) [6-71/55; 6+15] = [259/55;21] Если значение c1 будет лежать в данном интервале, то оптимальный план не изменится. 2-й параметр целевой функции может изменяться в пределах: ∆c2- = min [yk/d2k] для d2k>0. ∆c2+ = |max[yk/d2k]| для d2k<0. Таким образом, 2-й параметр может быть уменьшен на 5 или увеличен на 23
Интервал изменения равен: (c2 - ∆c-2; c2 + ∆c2+) [7-5; 7+23] = [2;30] Если значение c2 будет лежать в данном интервале, то оптимальный план не изменится. Верхняя граница для: ∆c3+ ∆c3+ = |max[yk/dk3]| для dk3<0. Таким образом, 3-й коэффициент может быть увеличен на 15/56. ∆c3- = +∞ Интервал изменения равен: (c3 - ∆c3-; +∞) [5-∞;5+15/56] = [-∞;295/56] Верхняя граница для: ∆c4+ ∆c4+ = |max[yk/dk4]| для dk4<0. Таким образом, 4-й коэффициент может быть увеличен на 23/14. ∆c4- = +∞ Интервал изменения равен: (c4 - ∆c4-; +∞) [3-∞;3+23/14] = [-∞;65/14] Чувствительность решения к изменению запасов сырья. Вариант расчета №1. При этом условие устойчивости двойственных оценок задачи исходит из выражения: X1=X0+ΔX=A-1(B+ΔB) в которой компоненты вектора X1 должны быть неотрицательны, т.е
Задать вопрос
на новый заказ в Автор24.
