运筹学复习资料知识点习题.doc

第一局部线性规划问题的求解一、两个变量的线性规划问题的图解法：㈠概念准备：定义：满足所有约束条件的解为可行解；可行解的全体称为可行〔解〕域定义：到达目标的可行解为最优解㈡图解法：图解法采用直角坐标求解：*1——横轴；*2——竖轴1、将约束条件〔取等号〕用直线绘出；2、确定可行解域；3、绘出目标函数的图形〔等值线〕，确定它向最优解的移动方向；注：求极大值沿价值系数向量的正向移动；求极小值沿价值系数向量的反向移动4、确定最优解及目标函数值㈢参考例题：〔只要求下面这些有唯一最优解的类型〕例1：*厂生产甲、乙两种产品，这两种产品均需在A、B、C三种不同的设备上加工，每种产品在不同设备上加工所需的工时不同，这些产品销售后所能获得利润以及这三种加工设备因各种条件限制所能使用的有效加工总时数如下表所示：品产耗消备设 A B C利润〔万元〕甲乙3 5 99 5 37030有效总工时540 450 720——问：该厂应如何组织生产，即生产多少甲、乙产品使得该厂的总利润为最大.〔此题也可用“单纯形法〞或化“对偶问题〞用大M法求解〕解：设*1、*2为生产甲、乙产品的数量。

⑴ma* z = 70*1+30*2 ⑵s.t. ⑸、⑹ ⑷ ⑶可行解域为oabcd0，最优解为b点由方程组 解出*1=75，*2=15∴**==〔75，15〕T∴ma* z =Z*= 70×75+30×15=5700例2：用图解法求解 ⑴ma* z = 6*1+4*2 ⑵s.t. ⑸、⑹ ⑷ ⑶解：可行解域为oabcd0，最优解为b点由方程组 解出*1=2，*2=6∴**==〔2，6〕T∴ma* z = 6×2+4×6=36例3：用图解法求解 ⑴min z =－3*1+*2s.t. ⑵ ⑶ ⑷ ⑸ ⑹、⑺解：可行解域为bcdefb，最优解为b点由方程组解出*1=4，*2=∴**==〔4，〕T∴min z =－3×4+=－11二、标准型线性规划问题的单纯形解法：㈠一般思路：1、用简单易行的方法获得初始根本可行解；2、对上述解进展检验，检验其是否为最优解，假设是，停顿迭代，否则转入3；3、根据θL规则确定改良解的方向；4、根据可能改良的方向进展迭代得到新的解；5、根据检验规则对新解进展检验，假设是最优解，则停顿迭代，否则转入3，直至最优解。

㈡具体做法〔可化归标准型的情况〕：设ma* z = c1*1+ c2*2+…+*ns.t.对第i个方程参加松弛变量*n+i，i =1，2，…，m，得到列表计算，格式、算法如下：CB*Bbc1c2…+mθL*1*2…*n+m+1*n+1b1a11a12…a1 n+mc n+2*n+2b2a21a22…a2 n+m.........…………+m*n+mbnam1am2…am n+mz1z2…zn+mσ1σ2…σn+m注①： zj =+1a1j++2a2j +…++mamj=，〔j=1，2，…，n+m〕σj =cj－zj ,当σj ≤0时，当前解最优注②：由ma*{σj}确定所对应的行的变量为“入基变量〞；由θL=确定所对应的行的变量为“出基变量〞，行、列穿插处为主元素，迭代时要求将主元素变为1，此列其余元素变为0例1：用单纯形法求解〔此题即是本资料P2“图解法〞例1的单纯形解法；也可化“对偶问题〞求解〕ma* z =70*1+30*2s.t.解：参加松弛变量*3，*4，*5，得到等效的标准模型：ma* z =70*1+30*2+0 *3+0 *4+0 *5s.t.列表计算如下：CB*Bb7030000θL*1*2*3*4*50*354039100540/3 =1800*445055010450/5 =900*5720〔9〕3001720/9 =800000070↑300000*33000810- 1/3300/8 =37.50*4500〔10/3〕01 - 5/950/10/3 =1570*1801 1/300 1/980/1/3 =2407070/30070/9020/3↑00－70/90*3180001－12/5130*215010 3/10- 1/670*175100- 1/10 1/6570070300220/3000-2－20/3∴**=〔75，15，180，0，0〕T∴ma* z =70×75+30×15=5700例2：用单纯形法求解ma* z =7*1+12*2s.t.解：参加松弛变量*3，*4，*5，得到等效的标准模型：ma* z =7*1+12*2+0 *3+0 *4+0 *5s.t.列表计算如下：CB*Bb712000θL*1*2*3*4*50*336094100360/4 =900*420045010200/5 =400*53003〔10〕001300/10 =3000000712↑0000*324078/10010- 2/5240/78/10 =2400/780*450〔5/2〕001- 1/250/5/2 =2012*2303/10100 1/1030/3/10 =10018/512006/517/5↑000－6/50*384001－78/2529/257*1201002/5- 1/512*224010－3/254/28428712034/2511/35000－34/25－11/35∴**=〔20，24，84，0，0〕T∴ma* z =7×20+12×24=428三、非标准型线性规划问题的解法：1、一般地，对于约束条件组：假设为“≤〞，则加松弛变量，使方程成为“＝〞；假设为“≥〞，则减松弛变量，使方程成为“＝〞。

我们在前面标准型中是规定目标函数求极大值如果在实际问题中遇到的是求极小值，则为非标准型可作如下处理：由目标函数min z=变成等价的目标函数ma*〔－z〕=令－z=z/，∴min z=－ma* z/2、等式约束——大M法：通过加人工变量的方法，构造人造基，从而产生初始可行基人工变量的价值系数为－M，M是很大的正数，从原理上理解又称为“惩罚系数〞〔课本P29〕类型一：目标函数仍为ma* z，约束条件组≤与＝例1：ma* z =3*1+5*2s.t.解：参加松弛变量*3，*4，得到等效的标准模型：ma* z =3*1+5*2s.t.其中第三个约束条件虽然是等式，但因无初始解，所以增加一个人工变量*5，得到： ma* z =3*1+5*2－M*5s.t.单纯形表求解过程如下：CB*Bb3500－MθL*1*2*3*4*50*34〔1〕01004/1 =40*41202010——－M*5183200118/3 =6－3M－2M00－M3M＋3↑5＋2M0003*1410100——0*4120201012/2 =6－M*560〔2〕－3016/2 =33－2M3＋3M0－M05↑－3－3M003*14101004/1 =40*4600〔3〕1－16/3 =25*2301－3/201/23/(－2/3) =－9/235－9/205/2009/2↑0－M－5/2305*12100－1/31/3*320011/3－1/3*260101/20363503/21000－3/2－M－1∴**=〔2，6，2，0〕T∴ma* z =3×2+5×6=36类型二：目标函数min z，约束条件组≥与＝。

例2：用单纯形法求解min z =4*1+3*2s.t.解：减去松弛变量*3，*4，并化为等效的标准模型：ma* z/ =－4*1－3*2s.t.增加人工变量*5、*6，得到：ma* z/ =－4*1－3*2－M*5－M*6s.t单纯形表求解过程如下：CB*Bb－400－M－MθL*1*2*3*4*5*6－M*5162〔4〕－101016/4=4－M*612320－10112/2=6－5M－6MMM－M－M5M－46M－3↑－M－M。