单纯形法小结

《单纯形法小结》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、单纯形法小结继续返回基本概念线性规划模型三个要素：决策变量、目标函数、约束条件线性性线性规划解的性质线性规划问题的可行域是凸集。最优解必在顶点上得到。线性规划求解方法图解法单纯形法重点掌握内容单纯形法小结一般线性规划问题的标准化及初始单纯形法表.—变量—约束条件单纯形法小结目标函数单纯形法计算步骤框图单纯形法小结引进松弛变量、人工变量列出初始单纯行表计算非基变量各列检验数σj找出最大的正检验数σk所有σj≤0基变量中有人工变量某非基变量检验数为0唯一最优解存在aik>0无可行解无穷多解无界解是是是是否否否否一、已知某LP的初始单纯

2、形表和单纯形法迭代的表，求未知数a~l的值。6bcd101-13e01a-1200fg2-11/204hi11/210-7jkl6bcd101-13e01a-1200fg2-11/204hi11/210-7jkLb=2102c/2=2c=44d/2=-1d=-2-2-2a-1=-7a=33350g=1h=01=-1+ee=225-3/2解：二、LP问题maxz=CX,AX=b，X≥0，如是该问题的最优解，又为某一常数，分别讨论下列情况时最优解的变化。（1）目标函数变为（2）目标函数变为（3）目标函数变为约束条件变为解：（a）仍为最优

3、解，；（b）一般不再是问题的最优解。（c）最优解变为，目标函数值不变。三、考虑LP问题，分别用大M法和两阶段法求解大M法，第一步转化成标准型：第二步建表：-2-3-100-M-Mθx1x2x3x4x5x6x7-Mx68142-10102-Mx763200-1013cj-zj4M-26M-32M-1MM00-3x221/411/2-1/401/408-Mx725/20-11/2-1-1/214/5cj-zj5/2M-5/401/2-MM/2-3/4-M3/4-1/2M0-3x29/5013/5-3/101/103/10-1/10-2x

4、14/510-2/51/5-2/5-1/52/5cj-zj000-1/2-1/2-M+1/2-M+1/2两阶段法：化成标准型：00000-M-Mθx1x2x3x4x5x6x7-Mx68142-10102-Mx763200-1013cj-zj4M-26M-32M-1MM00-3x221/411/2-1/401/408-Mx725/20-11/2-1-1/214/5cj-zj5/2M-5/401/2-MM/2-3/4-M3/4-1/2M0-3x29/5013/5-3/101/103/10-1/10-2x14/510-2/51/5-2/5

5、-1/52/5cj-zj000-1/2-1/2-M+1/2-M+1/2四、已知线性规划问题用单纯形法求解得最终单纯形表如下,表中x4x5为松弛变量试计算确定c1、c2、c3和b1、b2的值。续x1x2x3x4x5x211/5103/5-1/5x333/501-1/52/5cj-zj-7/1000-3/5-4/5解：建立初始单纯形表,根据单纯形法的矩阵描述，有由,解出c1=1.5,c2=2,c3=3及b1=5,b2=5。x1x2x3x4x5x211/5103/5-1/5x333/501-1/52/5cj-zj-7/1000-3/5-4

6、/5续x1x2x3x4x5x4b112110x52b221301cj-zj00五、设线性规划问题（1）分别用图解法和单纯形法求解；（2）对照指出单纯形表中的各基本可行解对应图解法中可行域的哪一顶点。续（3）若目标函数变为讨论c、d的值如何变化，使每个顶点依次使目标函数达到最优。解：化为标准型1221最优解k=-5/2k=-3/4o1050009341008520110500021/5014/51-3/5108/512/501/5010-253/2015/14-3/1410110-1/72/700-5/14-25/14O（0，0）12

7、21k=-5/2k=-3/4ocdc/d最优解的顶点c/d>5/2Q1c/d=5/2Q1,Q2>0>03/40不限Q3>0=0---Q1>0<0不限Q1<0<0不限O单纯形法习题课返回