浙江大学mba教材-.ppt

《浙江大学mba教材-.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）是基础可行解，表示可行域的一个极点。

3、目标函数值为：z=18基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，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）是基础解

4、，但不是可行解。基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。=目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换=基变量=进基变量离基变量目标函数约束条件右边常数==目标函数约束条件新的基矩阵右边常数==进基

5、变量离基变量目标函数约束条件基矩阵==目标函数约束条件新的基矩阵右边常数=基础解、基础可行解maxz=x1+3x2Ds.t.x1+x2+x3=6B-x1+2x2+x4=8x4=0Cx3=0x1,x2,x3,x4≥0x1=0EOx2=0A单纯形表求解线性规划问题写成标准化形式写出单纯形表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-1

6、101411010x20得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）minz’=-86，maxz=86线性规划的矩阵表示=====CBTB-1aj-cj=zj-cj称为非基变量的检验数（ReducedCost）B-1aj=Yj，B-1b=，CBTB-1b=z0第二章对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系—互补松弛关系最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL一、对偶的定义原始问

7、题minz=CTXs.t.AX≥bX≥0对偶问题maxy=bTWs.t.ATW≤CW≥0≥minbACTCATbT≤maxmnmn二、对偶问题的性质1、对偶的对偶就是原始问题maxz’=-CTXs.t.-AX≤-bX≥0miny=-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

8、=bTWs.t.ATW≤CW≥0minz=CTXs.t.AX=bX≥0maxy=bTWs.t.ATW≤CW：unr三、原始对偶关系1、可行解的目标函数值之间的关系设XF、WF分别是原始问题和对偶问题的可行解z=CTXF≥WTAXF≥WTb=y2、最优解的目标函数值之间的关系设Xo、Wo分别是原始问题和对偶问题的最优解z=CTXo=WoTAXo=WoTb=y3、原始问题和对偶问题最优解之间的互补松弛关系XTWS=0WTXS=0m