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

1、运 筹 学主 讲 教 师 第一章 线性规划与单纯形法 3 线性规划问题的标准型与解的概念3.1 线性规划的标准型型maxz=c1x1+c2x2+cnxn a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1,x2,xn0 通常称cj(j=1,2n)为价值系数，bi（i=1,2,m)为资源系数；aij为技术系数，或约束系数。在模型中它们是常数。若记 x=（x1,x2xn）t,c=（c1,c2cn）,b=（ b1,b2bm）ta=（aij）nm =（p1,p2pn）则标准型亦可记作 maxz= cx ax=b x0 或maxz

2、=njjx1jc pjxj= b xj0, j=1,2n目标函数是 minz=cx，则可令 z=-z，将目标函数变为：maxz =-cx 约束条件为不等式：ai1x1+ai2x2+ainxnbi则在约束条件的左端加一个非负变量xn+i,称之为松弛变量，即可变为等式: ai1x1+ai2x2+ainxn+ xn+i =bi约束条件为不等式：ai1x1+ai2x2+ainxnbi则可在约束条件的左端减一个非负变量xn+i,称之为剩余变量，即可变为等式: ai1x1+ai2x2+ainxn-xn+i =bixj没有非负限制，则可令xj=xj -xj,其中xj ，xj 0，代入目标函数及约束条件即可。

3、 minz=3x1-x2 x1+x21 x1-x2-1 x10化为标准型。3.2 线性规划解的概念 我们把决策变量的一组取值称为线性规划问题的一个解解。满足约束条件的解称为可行解可行解。所有可行解的集合称为可行可行域域。使目标函数达到最优的可行解称为最优解最优解。 在上一节图解法中，我们求得例1问题的最优解是唯一的，但是线性规划问题的解还可能出现以下几种情况：（1）无穷多个最优解。若例1的目标函数变为maxz=4x1+2x2 ，就会出现这种情况。见图1-1。 ox2605040302010 10 20 30 40 50 x14x1+2x2=120 2x1+3x2=100q3q2q1图1-1ma

4、xz=4x1+2x2z=6x1+4x2 （2）无可行解。如果约束中存在相互矛盾的约束条件，则导致可行域是空集，此时问题无可行解。（3）无有限最优解。对下述线性规划问题 maxz=x1+x2 -x1+x24 x1-x22 x1,x20用图解法求解结果见图1-2。 图1-2x242240 x1 从图中可以看出可行域无界，在可行域中找不到最大值点，目标函数值可以增大到无穷大，称这种情况为无有限最优解或无界解。x1-x2=2-x1+x2=4z=x1+x2线性规划基解的概念 记线性规划问题为 maxz= cx （l） ax=b x0基基：设a是mn阶约束系数矩阵（mn）,秩a=m.a=（ p1,p2,p

5、n ）,则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-1b0，则称该解为基可行解，mncmaxz=2x1+x2 3x1+5x215 6x1+2x224x1,x20maxz=2x1+x2 3x1+5x2 + x3 = 15 6x1+2x2 + +x4= 24 x1,x2, x3, x4 0系数矩阵 a= ,秩a=210260153p1,p2,2653得由2x1x24152653。4x3x2x1x是基可行解,00,43415p1,p3是基可行解。4x2x3x1x,00,34p1,p4是基本解。3x2x4x1x,00,65p2,p3是