Курсовая работа: Линейное программирование как метод оптимизации
12
↓
→ 10 8
Число занятых клеток должно быть m+n-1; 3+5-1=7, следовательно опорный план является невырожденным
F = 5X11+4X12+3X13+4X14+3X21+2X22+5X23+5X24+X31+6X32 +3X33+2X34 → min
X11+X12+X13+X14+X15=48
X21+X22+X23+X24+X25=42
X31+X32+X33+X34+X35=18
X11+X21+X31=24
X12+X22+X32=24
X13+X23+X33=18
X14+X24+X34=24
Xij ≥ 0, i = 1,2,3,4, j = 1,2,3, X15+X25+X35 ≤ 18
Определим значение целевой функции
F (X1) = 3*6+18+24*2+3*18+4*24+6*0+12*0 = 234
Проверим оптимальность опорного плана
ά1=0 ά1=0ά1=0
ά1+β3=3 β3=3β3=3
ά1+β4=4 β4=4β4=4
ά1+β5=0 β5=0β5=0
ά2+β1=3 → β1=3 →β1=3
ά2+β2=2 β2=2β2=2
ά2+β5=0 ά2+0=0ά2=0
ά3+β1=1 ά3+3=1ά3=-2
Занесем найденные значения потенциалов в таблицу 4 вычеслим оценки свободных клеток
∆ ij= (β j+ ά i) - Cij
Таблица 4
| β1=3 | β2=2 | β3=3 | β4=4 | β5=0 | |
| ά1=0 | 5 | 4 | 3 18 | 4 24 | 0 6 |
| ά2=0 | 3 6 | 2 24 | 5 | 5 | 0 12 |
| ά3=-2 | 1 18 | 6 | 3 | 2 | 0 |
∆11 (0+3) - 5=-2; ∆12 (0+2) - 4=-2; ∆23 (0+3) - 5=-2; ∆24 (0+4) - 4=0; ∆32 (-2+2) - 2=-2; ∆33 (-2+3) - 3=-2; ∆34 (-2+4) - 2=0; ∆35 (-2+0) - 0=-2,
т.к. среди оценок нет значений больше 0, то план является оптимальным.