《运筹学基最短路松弛互补教学讲义》由会员分享，可在线阅读，更多相关《运筹学基最短路松弛互补教学讲义（165页珍藏版）》请在金锄头文库上搜索。
1、运筹学,目 录,第一章线性规划 第二章对偶 第三章整数规划 第四章运输问题 第五章网络优化 第六章动态规划 第七章排 队 论,第一章 线性规划,线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 基础解、基础可行解 单纯形表 线性规划的矩阵表示,线性规划模型,线性规划模型的结构 目标函数 ：max，min 约束条件：,=, 变量符号：0, unr, 0 线性规划的标准形式 目标函数：min 约束条件：= 变量符号：0,可行域的性质,线性规划的可行域是凸集 线性规划的最优解在极点上,凸集,凸集,不是凸集,线性规划的基本概念,线性规划的基矩阵、基变量、非基变量,=,=,目标函数,约束条
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，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。,基变量
3、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,基变量x1、x2、x3，非基变量x4、x5、x6,基础解为
4、 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。,目标函数,约束条件,基矩阵,右边常数,进基变量、离基变量、基变换,基变量,进基变量,离基变量,目标函数,约束条件,右边常数,目标函数,约束条件,新的基矩阵,右边常数,进基变量,离基变量,目标函数,约束条件,基矩阵,目标函数,约束条件,新的基矩阵,右边常数,基础解、基础可行解,max z=x1+3x2D s.t. x1+ x2+x3=6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A,几何概念,代数概念,约束直线,满足一个
5、等式约束的解,约束半平面,满足一个不等式约束的解,约束半平面的交集： 凸多边形,满足一组不等式约束的解,约束直线的交点,基础解,可行域的极点,基础可行解,目标函数等值线： 一组平行线,目标函数值等于一个常数的解,单纯形表,求解线性规划问题,写成标准化形式,写出单纯形表,25/1,36/2,0,-3,-2,0,-2,-72,0,1,1/2,0,1,-1/2,7/1/2,1,x5,1/2,1,0,1/2,18/1/2,0,7,18,1,1/2,1/2,x2,0,x6离基，,x2进基，,x5离基，,x1进基，,0,-4,-2,-2,-1,-86,0,1,1,0,2,-1,1,x1,0,1,-1,1,
6、0,14,11,0,1,0,x2,0,得到最优解，最优解为：,（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0） min z=-86，max z=86,线性规划的矩阵表示,=,=,CBTB-1aj-cj=zj-cj 称为非基变量的检验数（Reduced Cost） B-1aj=Yj， B-1b= ，CBTB-1b=z0,第二章 对偶线性规划,对偶的定义 对偶问题的性质 原始对偶关系 目标函数值之间的关系 最优解之间的关系互补松弛关系 最优解的Kuhn-Tucher条件 对偶可行基对偶单纯形法 对偶的经济解释,DUAL,一、对偶的定义,原始问题 min z=CTX s.t.A
7、Xb X 0,对偶问题 max y=bTW s.t. ATWC W 0,min,b,A,CT,C,AT,bT,max,m,n,m,n,二、对偶问题的性质,1、对偶的对偶就是原始问题,2、其他形式问题的对偶,三、原始对偶关系,1、可行解的目标函数值之间的关系 设XF、WF分别是原始问题和对偶问题的可行解 z=CTXF WTAXF WTb=y 2、最优解的目标函数值之间的关系 设Xo、Wo分别是原始问题和对偶问题的最优解 z=CTXo=WoTAXo=WoTb=y,3、原始问题和对偶问题最优解之间的互补松弛关系,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t.
8、 ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,互补松弛关系,min z=CTX s.t.AX-XS=b X, XS 0,max y=bTW s.t. ATW+WS=C W, WS 0,XTWS=0 WTXS=0,m,n,=,W,WS,AT,I,C,n,=,A,XS,-I,b,n,m,m,X,原始问题和对偶问题变量、松弛变量的维数,w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjwm+j=0wi
9、xn+i=0(i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,Kuhn-Tucher 条件,3、原始问题和对偶问题最优解的充分必要条件 (1)原始可行条件（PFC） AX-XS=b X, XS 0 (2)对偶可行条件（DFC） ATW+WS=C W, WS 0 (3)互补松弛条件（CSC） XTWS=0 WTXS=0,四、对偶单纯形法,1、用单纯形表求解原始问题的四种形式,min z=CTX s.t. AXb X 0,min z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0,max z=CTX s.t. AX b X 0
10、,（2）,（3）,（4）,（1）,单纯形表和对偶(1),min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,min z=CTX s.t. AXb X 0,max y=bTW s.t. ATWC W0,对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW+WS=C W, WS0,WT=CBTB-1 WST=CT-WTA,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0,
11、WS0,min z=CTX s.t. AX b X 0,max y=bTW s.t. ATWC W 0,单纯形表和对偶(2),对偶问题,原始问题,引进松弛变量,引进松弛变量,min z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW+WS=C W 0, WS0,WT=CBTB-1 WST=CT-WTA,max z=CTX s.t. AX-XS=b X, XS0,max y=bTW s.t. ATW-WS=C W 0, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,单纯形表和对偶(3),对偶问题,原
12、始问题,引进松弛变量,引进松弛变量,max z=CTX s.t. AX-XS=b X, XS0,min y=bTW s.t. ATW-WS=C W 0, WS0,WT=CBTB-1 WST=WTA- CT,max z=CTX s.t. AX+XS=b X, XS0,max y=bTW s.t. ATW-WS=C W, WS0,max z=CTX s.t. AX b X 0,min y=bTW s.t. ATW C W 0,单纯形表和对偶(4),对偶问题,原始问题,引进松弛变量,引进松弛变量,max z=CTX s.t. AX+XS=b X, XS0,min y=bTW s.t. ATW-WS=
13、C W, WS0,WT=CBTB-1 WST=WTA- CT,2、对偶单纯形法（初始解原始不可行的问题）,已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,3、初始解原始、对偶都不可行的问题,解法1：先解决原始可行性,在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为：
14、 （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,五、对偶的经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（
15、吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1 w2 wm,4、产品的机会成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,差额成本=机会成本 - 利润,5、互补松弛关系的经济解释,在利润最大化的生产计划中
