复习课运筹学.ppt
《复习课运筹学.ppt》由会员分享,可在线阅读,更多相关《复习课运筹学.ppt(58页珍藏版)》请在三一文库上搜索。
1、复习课 运筹学,绍兴文理学院工学院 计算机系2005.12.,模型、概念 图解法 标准化 单纯形法 对偶理论,线性规划问题,第五章,线性规划的图解法,max z=x1+3x2 约束条件: x1+ x26 -x1+2x28 x10,x20,可行域,目标函数等值线,最优解(4/3,14/3),6,4,-8,6,约束条件 (s.t.),线性规划问题,若干个决策变量x1,x2 ; 2.约束条件(或或); 3.符号约束(非负或非正或自由); 4.目标函数(max或min) 。,图解法,线性规划问题,Min z = 3x1+2x2,约束条件,2x1+9x218 2x1+4x210 3x1+2x212 x1
2、0 , x20,线性规划问题,目标函数 max f=3x1+4x2,线性规划问题,2x1+9x2=18,最优解(3.5,0.75),目标函数 f = 3x1+4x2 =13.5,3x1+2x2=12,2x1+4x2=10,可行解区域,约束条件,线性规划问题,目标函数 Max f=2x1+3x2,线性规划的标准化,用单纯形法求解线性规划要先标准化: 目标函数求极大; 全部是等式约束; 所有决策变量全有非负约束。,Min zMax -z,不等式约束通过添加松弛变量()或剩余变量()化为等式约束。,处理非正和自由的变量,LP问题的单纯形法,用单纯形法求解下列线性规划,求最大;,全是的不等式;,常数项
3、 b0;,全有非负约束。,这类最适用: 单纯形法,LP问题的单纯形法,标准化;列初始单纯形表;迭代。,引入松弛变量x3 ,成x1+2x2+x3=2,引入松弛变量x4 ,成2x1+x2+x4=2,极小化极大。,两个松弛变量,LP问题的单纯形法,初始单纯形表,基变量是哪两个?,x3,x4,2,3,0,0,0,0,CB=?,LP问题的单纯形法,初始单纯形表,头两行? Zj=? 末行?,2 3 0 0,1 2 1 0 2,2 1 0 1 2,0,0,LP问题的单纯形法,单纯形表,最优? 谁进基? 比值? 谁出基?,1 2,LP问题的单纯形法,迭代,X2进基,x3出基,红格要变成几?,LP问题的单纯形法
4、,第一次迭代,是最优解?谁进基?谁出基?,LP问题的单纯形法,第二次迭代,是最优解?最优解是?max?,LP问题的单纯形法,标准化;列初始单纯形表;迭代。,引入松弛变量x4 ,成x1+x4=2,引入松弛变量x5 ,成x1+x2+2x3+x5=4,三个松弛变量,引入松弛变量x6 ,成3x2+4x3+x6=6,LP问题的单纯形法,初始单纯形表,基变量是哪三个?,x,x5,1,2,0,0,x6,4,0,0,0,0,CB=?,1 0 0 1 0 0 2,1 1 2 0 1 0 4,0 3 4 0 0 1 6,0 0 0 0 0 0,0,1 2 4 0 0 0,线性规划,例1.一目标函数是Max Z的L
5、P问题,用单纯形法解的过程中,得到如下数据有缺的单纯形表。,其中u为常数,求表中(*处)所有缺失的数。,分析,CB列中可确定哪几个?,0,6,0,0,0,Zj行中可确定哪几个?,6,0,0,0,0,0,0,0,Z1= ?,j行中可确定哪几个?,C1-1=6,6,6u,3,5-6u,-3,1,150,a12=?,右下角=?,基变量列中可确定哪几个?,续,u = ? 时已得到唯一最优解。,u 5/6,u = 0 时有最优解吗?,无有界最优解.,u = 0.5 时有唯一最优解吗?,迭代一次得最优解.,对偶线性规划,LP问题对偶规划的提出 求LP问题的对偶规划 LP问题对偶单纯形法,例(对偶理论):原
6、问题,几个变量?,这是要求X1 , X2 使销售收入最_的LP问题,LP的对偶理论,设X1 , X2 为产品1,产品2的产量,大,约束条件有几个? 等式还是不等式约束?,Min f= y1 y2 y3 y4,其对偶有几个变量? 约束条件有几个? 求极大?极小?,4,2,极小,12,+16,+12,y1 y2 y3 y4,y1 y2 y3 y4,y1 y2 y3 y4,2,+,+4,+0,2,+2,+0,+4,2,3,0,,,,,,,+8,例1、写出下面问题的对偶规划,Max w=,y1 y2 y3,+2,+3,y1 y2 y3,y1 y2 y3,y1 y2 y3,y1 y2 y3,+,+0,+
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复习 运筹学
链接地址:https://www.31doc.com/p-3130523.html