资源描述：
《《运筹学习题课》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《运筹学》习题课8/7/20211《运筹学》习题课练习㈠用图解法和单纯形法求如下线性规划问题的最优解：Maxz=4x1+x2x1+3x2≤7 s.t.4x1+2x2≤9 x1,x2≥08/7/20212《运筹学》习题课练习㈠1.用图解法0123456712345(2.25,0)4x1+x2=98/7/20213《运筹学》习题课练习㈠Maxz=4x1+x2x1+3x2≤7 s.t.4x1+2x2≤9 x1,x2≥0解：先要标准化：引入___个剩余变量;0引入___个松弛变量;2Maxz=4x1+x2+0x3+0x4s.t.x1+3x2
2、+x3=74x1+2x2+x4=9x1,x2,x3,x4≥08/7/20214《运筹学》习题课练习㈠2.用单纯形法x3x44100001310742019迭代次数基变量CBx1x2x3x4bi比迭代次数基变量CBx1x2x3x4bi比0zjσj=Cj-zj1zjσj=Cj-zj00000410079/44100x3x10410.500.252.2502.51-0.254.75420190-10-18/7/20215《运筹学》习题课㈡.用图解法和单纯形法求如下线性规划问题的最优解：Minf=2x1+3x2x1+x2≥350 s.t.x
3、1≥125 2x1+x2≤600 x1,x2≥08/7/20216《运筹学》习题课㈡.用图解法0100300400100200300400200(250,100)2x1+3x2=8008/7/20217《运筹学》习题课㈡.用单纯形法求解：Minf=2x1+3x2x1+x2≥350s.t.x1≥1252x1+x2≤600x1,x2≥0解：先标准化，目标函数改为求：z＝－f的极大。Maxz=-f=－2x1－3x2引进两个剩余变量x3,x4，一个松弛变量x5。 Maxz=－2x1－3x2+0x3+0x4+0x5x1+x2－x3＝350 s
4、.t.x1－x4＝1252x1+x2+x5＝600 x1,x2,x3,x4,x5≥08/7/20218《运筹学》习题课Maxz=－2x1－3x2+0x3+0x4+0x5x1+x2－x3＝350 s.t.x1－x4＝125 2x1+x2+x5＝600 x1,x2,x3,x4,x5≥0系数矩阵中有没有三列可组成单位矩阵？它的系数矩阵是：没有！前两行各乘－1,可组成单位矩阵吗？可以,但没用！因为这样做常数项就出现负数！要用人工变量！－＋－＋－8/7/20219《运筹学》习题课它的系数矩阵是：显然x6,x7必须为０,想一想两个M(大正数)的
5、意图。追加两列 ，引进人工变量x6,x7，Maxz=－2x1－3x2+0x3+0x4+0x5－Mx6－Mx7x1+x2－x3+x6＝350 s.t.x1－x4+x7＝125 2x1+x2+x5＝600 x1,x2,x3,x4,x5,x6,x7≥08/7/202110《运筹学》习题课㈡用单纯形法x6x7-475M-M0-2M-MMM0-M-M350x5-M-2+2M–3+M-M-M000125300基变量是谁？CB列填什么？计算Zj求检验数谁最大？x1的-2+2M求比值谁最小？125,谁进基？x1,谁进基？x7,x1-M-20-2
6、25M-2508/7/202111《运筹学》习题课㈡单纯形法(后两次迭代)是最优基，原问题的最优解是:(250,100)，最优值是800。8/7/202112《运筹学》习题课前两个等式约束乘-1,适用对偶单纯形法Maxz=－2x1－3x2+0x3+0x4+0x5x1+x2－x3＝350 s.t.x1－x4＝125 2x1+x2+x5＝600 x1,x2,x3,x4,x5≥0000000-2-3000238/7/202113《运筹学》习题课㈡.用对偶单纯形法谁进基？x1进基.谁出基？x3出基.x2进基.x5出基.8/7/202114《
7、运筹学》习题课㈡.用对偶单纯形法(检验数全非正),常数项全非负,这是最优解。原问题的最优解是：x1=250,x2=100,Minf=800。8/7/202115《运筹学》习题课用单纯形法与对偶单纯形法的比较。单纯形法最好是：约束全是“≤”，且常数项全非负，(求极大还是极小，目标函数的系数正负倒是无所谓的)。此时初始基可行解易得。否则就要利用引进人工变量等方法来寻找初始基可行解。对偶单纯形法最好是：求极大(极小)，且目标函数的系数全负(正)的，全是不等式约束(但约束是“≤”还是“≥”,常数项的符号倒是无所谓)。此时初始正则基易得。要善
8、于选择工具!!!8/7/202116《运筹学》习题课单纯形法中人工变量的引进单纯形法最好是：约束全是“≤”，且常数项全非负，此时初始基可行解易得。引进的人工变量实际上最后必须是0，所以它们在求极大(小)问题的目标函数的系数都是-M(M
