第一部分 线性规划问题的求解一、两个变量的线性规划问题的图解法：概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行（解）域。定义：达到目标的可行解为最优解。图解法：图解法采用直角坐标求解：x1横轴；x2竖轴。1、将约束条件（取等号）用直线绘出；2、确定可行解域；3、绘出目标函数的图形（等值线），确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动。4、确定最优解及目标函数值。参考例题：（只要求下面这些有唯一最优解的类型）例1：某厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：品产耗消备设 A B C利润（万元）甲乙3 5 99 5 37030有效总工时540 450 720问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大？（此题也可用“单纯形法”或化“对偶问题”用大M法求解）解：设x1、x2为生产甲、乙产品的数量。 max z = 70x1+30x2 s.t. 、 可行解域为oabcd0，最优解为b点。由方程组 解出x1=75，x2=15X*=（75，15）Tmax z =Z*= 7075+3015=5700例2：用图解法求解 max z = 6x1+4x2 s.t. 、 解：可行解域为oabcd0，最优解为b点。由方程组 解出x1=2，x2=6X*=（2，6）Tmax z = 62+46=36例3：用图解法求解 min z =3x1+x2s.t. 、解：可行解域为bcdefb，最优解为b点。由方程组 解出x1=4，x2=X*=（4，）Tmin z =34+=11二、标准型线性规划问题的单纯形解法：一般思路：1、用简单易行的方法获得初始基本可行解；2、对上述解进行检验，检验其是否为最优解，若是，停止迭代，否则转入3；3、根据L规则确定改进解的方向；4、根据可能改进的方向进行迭代得到新的解；5、根据检验规则对新解进行检验，若是最优解，则停止迭代，否则转入3，直至最优解。具体做法（可化归标准型的情况）：设已知max z = c1x1+ c2x2+ cnxns.t.对第i个方程加入松弛变量xn+i，i =1，2，m，得到列表计算，格式、算法如下：CBXBbc1c2cn+mLx1x2xn+mcn+1xn+1b1a11a12a1 n+mc n+2xn+2b2a21a22a2 n+m.cn+mxn+mbnam1am2am n+mz1z2zn+m12n+m注： zj =cn+1 a1j+ cn+2 a2j + cn+m amj=，（j=1，2，n+m）j =cjzj ,当j 0时，当前解最优。注：由maxj确定所对应的行的变量为“入基变量”；由L=确定所对应的行的变量为“出基变量”，行、列交叉处为主元素，迭代时要求将主元素变为1，此列其余元素变为0。例1：用单纯形法求解（本题即是本资料P2“图解法”例1的单纯形解法；也可化“对偶问题”求解）max z =70x1+30x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：max z =70x1+30x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb7030000Lx1x2x3x4x50x354039100540/3 =1800x445055010450/5 =900x5720（9）3001720/9 =800000070300000x33000810- 1/3300/8 =37.50x4500（10/3）01 - 5/950/10/3 =1570x1801 1/300 1/980/1/3 =2407070/30070/9020/30070/90x318000112/5130x215010 3/10- 1/670x175100- 1/10 1/6570070300220/3000-220/3X*=（75，15，180，0，0）Tmax z =7075+3015=5700例2：用单纯形法求解max z =7x1+12x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：max z =7x1+12x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb712000Lx1x2x3x4x50x336094100360/4 =900x420045010200/5 =400x53003（10）001300/10 =30000007120000x324078/10010- 2/5240/78/10 =2400/780x450（5/2）001- 1/250/5/2 =2012x2303/10100 1/1030/3/10 =10018/512006/517/50006/50x38400178/2529/257x1201002/5- 1/512x224010 3/254/28428712034/2511/3500034/2511/35X*=（20，24，84，0，0）Tmax z =720+1224=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：若为“”，则加松弛变量，使方程成为“”；若为“”，则减松弛变量，使方程成为“”。我们在前面标准型中是规定目标函数求极大值。如果在实际问题中遇到的是求极小值，则为非标准型。可作如下处理：由目标函数min z=变成等价的目标函数max（z）=令z=z/，min z=max z/2、等式约束大M法：通过加人工变量的方法，构造人造基，从而产生初始可行基。人工变量的价值系数为M，M是很大的正数，从原理上理解又称为“惩罚系数”。（课本P29）类型一：目标函数仍为max z，约束条件组与。例1：max z =3x1+5x2s.t.解：加入松弛变量x3，x4，得到等效的标准模型：max z =3x1+5x2s.t.其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量x5，得到： max z =3x1+5x2Mx5s.t. 单纯形表求解过程如下：CBXBb3500MLx1x2x3x4x50x34（1）01004/1 =40x41202010Mx5183200118/3 =63M2M00M3M352M0003x14101000x4120201012/2 =6Mx560（2）3016/2 =332M33M0M0533M003x14101004/1 =40x4600（3）116/3 =25x23013/201/23/(2/3) =9/2359/205/2009/20M5/2305x121001/31/3x320011/31/3x260101/20363503/210003/2M1X*=（2，6，2，0）Tmax z =32+56=36类型二：目标函数min z，约束条件组与。例2：用单纯形法求解min z =4x1+3x2s.t.解：减去松弛变量x3，x4，并化为等效的标准模型：max z/ =4x13x2s.t.增加人工变量x5、x6，得到：max z/ =4x13x2Mx5Mx6s.t单纯形表求解过程如下：CBXBb400MMLx1x2x3x4x5x6Mx5162（4）101016/4=4Mx6123201011