系统工程与运筹学基础（运筹学部分）

系统工程与运筹学基础（运筹学部分）目录第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第一章线性规划线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示线性规划模型线性规划模型的结构目标函数：max，min约束条件：≥,=,≤变量符号：：≥0,unr,≤0线性规划的标准形式目标函数：min约束条件：=变量符号：≥0unr,0)(Xb),(AX.t.sXCzmax(min)T0XbAX.t.sXCzminT线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2可行域的性质●线性规划的可行域是凸集●线性规划的最优解在极点上凸集凸集不是凸集极点线性规划的基本概念●线性规划的基矩阵、基变量、非基变量==目标函数约束条件行列式≠0基矩阵右边常数maxz=2x1+3x2+x3s.t.x1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30minz’=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60x1+3x2+x3=152x1+3x2-x3=18x1-x2+x3=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=20x1+3x2+x4=152x1+3x2=18x1-x2=3基变量x1、x2、x4，非基变量x3、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1+3x2=152x1+3x2+x5=18x1-x2=3x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0）是基础解，但不是可行解，不是一个极点。x1+3x2=152x1+3x2=18x1-x2+x6=3基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4）是基础可行解，表示可行域的一个极点。目标函数值为：z=18x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3+x4=153x2-x3=18-x2+x3=3基变量x2、x3、x4，非基变量x1、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0）是基础解，但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3+x5=18-x2+x3=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0）是基础可行解，表示可行域的一个极点。目标函数值为：z=15x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=33x2+x3=153x2-x3=18-x2+x3+x6=3基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10）是基础解但不是可行解。x1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3=目标函数约束条件基矩阵右边常数进基变量、离基变量、基变换=基变量=进基变量离基变量目标函数约束条件右边常数==目标函数约束条件新的基矩阵右边常数==进基变量离基变量目标函数约束条件基矩阵==目标函数约束条件新的基矩阵右边常数=基础解、基础可行解maxz=x1+3x2Ds.t.x1+x2+x3=6B-x1+2x2+x4=8x4=0Cx3=0x1,x2,x3,x4≥0x1=0EOx2=0AOABCDE基变量x3x4x1x4x1x2x2x3x2x4x1x3非基变量x1x2x2x3x3x4x1x4x1x3x2x4xj0--------x4x1基础可行解是是是是否否几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线目标函数值等于一个常数的解单纯形表maxz=3x1+4x2-x3+2x4s.t.x1+x2+x3+x4≦25x1+2x2+x3+2x4≦36x1x2x3x4≧0minz'=-3x1-4x2+x3-2x4s.t.x1+x2+x3+x4+x5=25x1+2x2+x3+2x4+x6=36x1x2x3x4x5x6≧0求解线性规划问题写成标准化形式z'x1x2x3x4x5x6RHSz'134-12000011111025012120136写出单纯形表25/136/20-3-20-2-72011/201-1/27/1/21x51/2101/218/1/2071811/21/2x20x6离基，x2进基，x5离基，x1进基，z'x1x2x3x4x5x6RHSz'134-12000x5011111025x6012120136z'x1x2x3x4x5x6RHSz'110-3-20-2-72x501/201/201-1/27x201/211/2101/2180-4-2-2-1-8601102-11x101-1101411010x20得到最优解，最优解为：（x1，x2，x3，x4，x5，x6）=（14，11，0，0，0，0）minz’=-86，maxz=86maxz=2x1+3x2+x3stx1+3x2+x3152x1+3x2-x318x1-x2+x33x1,x2,x30minz’=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60z’x1x2x3x4x5x6RHSz’12310000x401311001515/3x5023-10101818/3x601-110013-minz’=-2x1-3x2-x3stx1+3x2+x3+x4=152x1+3x2-x3+x5=18x1-x2+x3+x6=3x1,x2,x3,x4,x5,x60z’x1x2x3x4x5x6RHSz’12310000x401[3]11001515/3x5023-10101818/3x601-110013-z’x1x2x3x4x5x6RHSz’1100-100-15x201/311/31/30055/1/3x50[1]0-2-11033/1x604/304/31/30188/4/3z’x1x2x3x4x5x6RHSz’10020-10-18x200112/3-1/3044/1x1010-2-1103--x6000[4]5/3-4/3144/4z’x1x2x3x4x5x6RHSz’10020-10-18x200112/3-1/3044/1x1010-2-1103--x6000[4]5/3-4/3144/4x3进基，x6离基z’x1x2x3x4x5x6RHSz’1000-5/6-1/3-1/2-20x200101/40-1/43x10100-1/61/31/25x300015/12-1/31/41最优解:(x1,x2,x3,x4,x5x6)=(5,3,1,0,0,0),maxz=20线性规划的矩阵表示=====zXBXNRHSz1-CBT-CNT0XB0IB-1NB-1bzXRHSz1-CT00AbzXBXNRHSz1-CBT-CNT00BNbzXBXNRHSz10TCBTB-1N-CNTCBTB-1bXB0IB-1NB-1bzXB…xj…RHSz1-CBT…-cj…00B…aj…bzXB…xj…RHSz10T…CBTB-1aj-cj…CBTB-1b0I…B-1aj…B-1bCBTB-1aj-cj=zj-cj称为非基变量的检验数（ReducedCost）B-1aj=Yj，B-1b=，CBTB-1b=z0bzXB…xj…RHSz10T…zj-cj…z0XB0I…Yj…bzXB…xj…RHSz10T…CBTB-1aj-cj…CBTB-1b0I…B-1aj…B-1b第二章对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系—互补松弛关系最优解的Kuhn-Tucher条件对偶可行基对偶单纯形法对偶的经济解释DUAL一、对偶的定义原始问题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=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、原始问题和对偶问题最优解之间的互补松弛关系minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0对偶引进松弛变量引进松弛变量XTWS=0WTXS=0互补松弛关系X，XsW，Wsminz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0XTWS=0WTXS=0mn=WWSATICn=AXS-IbnmmX原始问题和对偶问题变量、松弛变量的维数w1wiwmwm+1wm+jwn+mx1xjxnxn+1xn+ixn+m对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量xjwm+j=0wixn+i=0(i=1,2,…,m;j=1,2,…,n)在一对变量中，其中一个大于0，另一个一定等于0Kuhn-Tucher条件3、原始问题和对偶问题最优解的充分必要条件(1)原始可行条件（PFC）AX-XS=bX,XS≥0(2)对偶可行条件（DFC）ATW+WS=CW,WS≥0(3)互补松弛条件（CSC）XTWS=0WTXS=0四、对偶单纯形法1、用单纯形表求解原始问题的四种形式minz=CTXs.t.AX≥bX≥0minz=CTXs.t.AX≤bX≥0maxz=CTXs.t.AX≥bX≥0maxz=CTXs.t.AX≤bX≥0（2）（3）（4）（1）单纯形表和对偶(1)minz=CTXs.t.AX-XS=bX,XS≥0maxy=bTWs.t.ATW+WS=CW,WS≥0minz=CTXs.t.AX≥bX≥0maxy=bTWs.t.ATW≤CW≥0对偶问题原始问题引进松弛变量引进松弛变量zXXSRHS1-WST-WTCBTB-1b0B-1A-B-1B-1