运筹学周四专题知识.pptxVIP

求解如下线性规划问题;111-21100011;最优解是;;;12[3]001-24;（无可行解）求解下列线性规划问题

解：

首先将问题化为原则型

令，则

;;（无界解）试用单纯形法求解下列线性规划问题：

解：引入松弛变量x3,x4化为原则型;（退化）求解下述线性规划问题：

解：引入松弛变量

化原则型

;;;无穷多最优解：;;;;;如下表，是某求极大化线性规划问题计算得到旳单纯形表。表中无人工变量，a1，a2，a3，d，c1，c2为待定常数。试阐明这些常数分别取何值时，下列结论成立。

（1）表中解为唯一最优解

（2）表中解为最优解，但存在无穷多最优解

（3）该线性规划问题具有无界解

（4）表中解非最优解，为对解改善，换入变量为x1，换出变量为x6

基BX1X2 X3 X4 X5 X6

X3 d 4 a1 1 0 a2 0

X4 2 -1 -3 0 1 -1 0

X6 3 a3 -5 0 0 -4 1

Cj-Zj c1 c2 0 0 -3 0;（1）当解为最优解时，必有d≥0，c1?0，c2?0。

（2）当解为最优解，但存在无穷多最优解时，必有d≥0，c1≤0，c2=0或d≥0，c1=0，c2≤0

（3）当该问题为无界解时，必有d≥0，c1≤0，c2?0且a1≤0。

（4）当解为非最优，为对解进行改善，当换入变量为x1，换出变量为x6，必有d≥0，c1?0且

c1≥c2，a3?0，;无穷多最优解;退化解