线性规划问题的标准型与解的概念.pptVIP

运筹学主讲教师向宇第一章线性规划与单纯形法§3线性规划问题的标准型与解的概念3.1线性规划的标准型我们规定线性规划的标准型如下：maxZ=c1x1+c2x2+‥‥+cnxna11x1+a12x2+‥‥+a1nxn＝b1a21x1+a22x2+‥‥+a2nxn＝b2……………am1x1+am2x2+‥‥+amnxn＝bmx1,x2,‥,xn≥0通常称cj(j=1,2…n)为价值系数，bi（i=1,2,…m)为资源系数；aij为技术系数，或约束系数。在模型中它们是常数。若记X=（x1,x2…xn）T,C=（c1,c2…cn）,则标准型亦可记作maxZ=CX或maxZ=b=（b1,b2…bm）TA=（aij）n×m=（P1,P2…Pn）AX=bX≥0ΣPjxj=bxj≥0,j=1,2…n任何形式的线性规划都可以化为与其等价的标准形式。如果目标函数是minZ=cx，则可令Z=-Z，将目标函数变为：maxZ=-cx则在约束条件的左端加一个非负变量xn+i,称之为松弛变量，即可变为等式:ai1x1+ai2x2+‥‥+ainxn+xn+i=bi（2）如果某约束条件为不等式：ai1x1+ai2x2+‥‥+ainxn≤bi01如果某约束条件为不等式：ai1x1+ai2x2+‥‥+ainxn≥bi则可在约束条件的左端减一个非负变量xn+i,称之为剩余变量，即可变为等式:ai1x1+ai2x2+‥‥+ainxn-xn+i=bi（3）如果xj没有非负限制，则可令xj=xj′-xj″,其中xj′，xj″≥0，代入目标函数及约束条件即可。02化为标准型。minZ=3x1-x2x1+x2≤1解：X1-x2≥-1x1≥0例3将线性规划我们把决策变量的一组取值称为线性规划问题的一个解。满足约束条件的解称为可行解。所有可行解的集合称为可行域。使目标函数达到最优的可行解称为最优解。在上一节图解法中，我们求得例1问题的最优解是唯一的，但是线性规划问题的解还可能出现以下几种情况：无穷多个最优解。若例1的目标函数变为maxZ=4x1+2x2，就会出现这种情况。见图1-1。3.2线性规划解的概念OX26050403020101020304050x14x1+2x2=1202x1+3x2=100Q3Q2Q1图1-1maxZ=4x1+2x2Z=6x1+4x2无可行解。如果约束中存在相互矛盾的约束条件，则导致可行域是空集，此时问题无可行解。无有限最优解。对下述线性规划问题maxZ=x1+x2x1+x2≤4x1-x2≤2x1,x2≥0用图解法求解结果见图1-2。图1-2x242240x1从图中可以看出可行域无界，在可行域中找不到最大值点，目标函数值可以增大到无穷大，称这种情况为无有限最优解或无界解。x1-x2=2-x1+x2=4Z=x1+x2线性规划基解的概念记线性规划问题为maxZ=CX（L）AX=bX≥0基：设A是m×n阶约束系数矩阵（m≤n）,秩A=m.A=（P1,P2,…,Pn）,则A中一定存在m个线性无关的列向量，设为Pj1,Pj2,…,Pjm,称可逆矩阵B=（Pj1,Pj2,…,Pjm）为线性规划（L）的一个基，称B中的列向量对应的变量xj1,xj2,…,xjm为基变量，其余变量称为非基变量。基本解：记基变量为XB=（xj1,xj2,…,xjm）T，非基变量构成的列向量记为XN，并令XN=0，则有AX=ΣPjxj=BXB=b，于是有XB=B-1b。称XB=B-1b，XN=0为线性规划（L）的一个基本解。基（本）可行解：若基本解中XB=B-1b≥0，则称该解为基可行解，这时基B也称为可行基。