运筹学 数学建模.ppt

《运筹学 数学建模.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、运筹学演示课件目录第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排队论第一章线性规划线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示线性规划模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,unr,≤0线性规划的标准形式目标函数：min约束条件：=变量符号：≥0线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集

2、凸集不是凸集极点线性规划的基本概念线性规划的基矩阵、基变量、非基变量==目标函数约束条件行列式≠0基矩阵右边常数基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，

3、3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15基变量

4、x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。=目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换=基变量=进基变量离基变量目标函数约束条件右边常数==目标函数约束条件新的基矩阵右边常数==进基变量离基变量目标函数约束条件基矩阵==目标函数约束条件新的基矩阵右边常数=基础解、基础可行解maxz=x1+3x2Ds.t.x1+x2+x3=6B-x1+2x2+x4=8x4=0Cx3=0x1,x2,x3,x4≥0x1=0EOx2=0A几何概念代数概念约束直线满足一个等式约束的解约束

5、半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线目标函数值等于一个常数的解单纯形表求解线性规划问题写成标准化形式写出单纯形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1/2071811/21/2x20x6离基，x2进基，x5离基，x1进基，0-4-2-2-1-8601102-11x101-1101411010x20得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）minz’=-86，maxz=

6、86线性规划的矩阵表示=====CBTB-1aj-cj=zj-cj称为非基变量的检验数（ReducedCost）B-1aj=Yj，B-1b=，CBTB-1b=z0第二章对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系—互补松弛关系最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL一、对偶的定义原始问题minz=CTXs.t.AX≥bX≥0对偶问题maxy=bTWs.t.ATW≤CW≥0≥minbACTCATbT≤maxmnmn二、对偶问题的性质1、对偶的对偶就是原始问题maxz’=-CTXs.t.-AX≤-bX≥0min

7、y=-bTWs.t.-ATW≥-CW≥0maxy=bTWs.t.ATW≤CW≥0minz=CTXs.t.AX≥bX≥0对偶的定义对偶的定义minz=CTXs.t.AX≤bX≥0maxy=bTWs.t.ATW≤CW≤02、其他形式问题的对偶minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0minz=CTXs.t.AX=bX≥0maxy=bTWs.t.ATW≤CW：unr三、原始对偶关系1、可行解的目标函数值之间的关系设XF、WF分