运筹学演示课件[全文]

运筹学演示课件目录第一章线性规划第二章对偶第三章整数规划第四章运输问题第五章网络优化第六章动态规划第七章排队论第一章线性规划线性规划模型线性规划的图解可行域的性质线性规划的基本概念基础解、基础可行解单纯形表线性规划的矩阵表示线性规划模型线性规划模型的结构目标函数MAX，MIN约束条件,变量符号0,UNR,0线性规划的标准形式目标函数MIN约束条件变量符号0线性规划的图解MAXZX13X2S3TX1X26X12X28X10,X20可行域目标函数等值线最优解64860X1X2可行域的性质线性规划的可行域是凸集线性规划的最优解在极点上凸集凸集不是凸集极点线性规划的基本概念线性规划的基矩阵、基变量、非基变量目标函数约束条件行列式0基矩阵右边常数基变量X1、X2、X3，非基变量X4、X5、X6基础解为（X1，X2，X3，X4，X5，X6）（5，3，1，0，0，0）是基础可行解，表示可行域的一个极点。目标函数值为Z20基变量X1、X2、X4，非基变量X3、X5、X6基础解为（X1，X2，X3，X4，X5，X6）（27/5，12/5，0，2/5，0，0）是基础可行解，表示可行域的一个极点。目标函数值为Z18基变量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）是基础可行解，表示可行域的一个极点。目标函数值为Z18基变量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）是基础可行解，表示可行域的一个极点。目标函数值为Z15基变量X1、X2、X3，非基变量X4、X5、X6基础解为（X1，X2，X3，X4，X5，X6）（0，11/2，3/2，0，0，10）是基础解但不是可行解。进基变量、离基变量、基变换目标函数约束条件基矩阵右边常数基变量进基变量离基变量目标函数约束条件右边常数目标函数约束条件新的基矩阵右边常数进基变量离基变量目标函数约束条件基矩阵目标函数约束条件新的基矩阵右边常数基础解、基础可行解MAXZX13X2DSTX1X2X36BX12X2X48X40CX30X1,X2,X3,X40X10EOX20A几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约束的解约束半平面的交集凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线一组平行线目标函数值等于一个常数的解单纯形表求解线性规划问题写成标准化形式写出单纯形表25/136/20320272011/2011/27/1/21X51/2101/218/1/2071811/21/2X20X6离基，X2进基，X5离基，X1进基，04221860110211X1011101411010X20得到最优解，最优解为（X1，X2，X3，X4，X5，X6）（14，11，0，0，0，0）MINZ86，MAXZ86线性规划的矩阵表示CBTB1AJCJZJCJ称为非基变量的检验数（REDUCEDCOST）B1AJYJ，B1B，CBTB1BZ0第二章对偶线性规划对偶的定义对偶问题的性质原始对偶关系目标函数值之间的关系最优解之间的关系互补松弛关系最优解的KUHNTUCHER条件对偶可行基对偶单纯形法对偶的经济解释DUAL一、对偶的定义原始问题MINZCTXSTAXBX0对偶问题MAXYBTWSTATWCW0MINBACTCATBTMAXMNMN二、对偶问题的性质1、对偶的对偶就是原始问题MAXZCTXSTAXBX0MINYBTWSTATWCW0MAXYBTWSTATWCW0MINZCTXSTAXBX0对偶的定义对偶的定义MINZCTXSTAXBX0MAXYBTWSTATWCW02、其他形式问题的对偶MINZCTXSTAXBX0MAXYBTWSTATWCW0MINZCTXSTAXBX0MAXYBTWSTATWCWUNR三、原始对偶关系1、可行解的目标函数值之间的关系设XF、WF分别是原始问题和对偶问题的可行解ZCTXFWTAXFWTBY2、最优解的目标函数值之间的关系设XO、WO分别是原始问题和对偶问题的最优解ZCTXOWOTAXOWOTBY3、原始问题和对偶问题最优解之间的互补松弛关系MINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW,WS0MINZCTXSTAXBX0MAXYBTWSTATWCW0对偶引进松弛变量引进松弛变量XTWS0WTXS0互补松弛关系X，XSW，WSMINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW,WS0XTWS0WTXS0MNWWSATICNAXSIBNMMX原始问题和对偶问题变量、松弛变量的维数W1WIWMWM1WMJWNMX1XJXNXN1XNIXNM对偶问题的变量对偶问题的松弛变量原始问题的变量原始问题的松弛变量XJWMJ0WIXNI0I1,2,MJ1,2,N在一对变量中，其中一个大于0，另一个一定等于0KUHNTUCHER条件3、原始问题和对偶问题最优解的充分必要条件1原始可行条件（PFC）AXXSBX,XS02对偶可行条件（DFC）ATWWSCW,WS03互补松弛条件（CSC）XTWS0WTXS0四、对偶单纯形法1、用单纯形表求解原始问题的四种形式MINZCTXSTAXBX0MINZCTXSTAXBX0MAXZCTXSTAXBX0MAXZCTXSTAXBX0（2）（3）（4）（1）单纯形表和对偶1MINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW,WS0MINZCTXSTAXBX0MAXYBTWSTATWCW0对偶问题原始问题引进松弛变量引进松弛变量MINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW,WS0WTCBTB1WSTCTWTAMINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW0,WS0MINZCTXSTAXBX0MAXYBTWSTATWCW0单纯形表和对偶2对偶问题原始问题引进松弛变量引进松弛变量MINZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW0,WS0WTCBTB1WSTCTWTAMAXZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW0,WS0MAXZCTXSTAXBX0MINYBTWSTATWCW0单纯形表和对偶3对偶问题原始问题引进松弛变量引进松弛变量MAXZCTXSTAXXSBX,XS0MINYBTWSTATWWSCW0,WS0WTCBTB1WSTWTACTMAXZCTXSTAXXSBX,XS0MAXYBTWSTATWWSCW,WS0MAXZCTXSTAXBX0MINYBTWSTATWCW0单纯形表和对偶4对偶问题原始问题引进松弛变量引进松弛变量MAXZCTXSTAXXSBX,XS0MINYBTWSTATWWSCW,WS0WTCBTB1WSTWTACT2、对偶单纯形法（初始解原始不可行的问题）已获得最优解（X1,X2,X3,X4,X5,X6）（5,7,6,0,0,0）MINZ35对偶问题的最优解为（W1,W2,W3,W4,W5,W6）（1,5,7,0,0,0）MAXY353、初始解原始、对偶都不可行的问题解法1先解决原始可行性在得到原始可行解时同时得到对偶可行解，已获得最优解（X1,X2,X3,X4,X5,X6）（5,7,6,0,0,0）MINZ17对偶问题的最优解为（W1,W2,W3,W4,W5,W6）（7,5,10,0,0,0）MAXY17解法2先解决对偶可行性已得到对偶可行解，再用对偶单纯形法求解得到原始可行解，已获得最优解（X1,X2,X3,X4,X5,X6）（5,7,6,0,0,0）MINZ17对偶问题的最优解为（W1,W2,W3,W4,W5,W6）（7,5,10,0,0,0）MAXY17五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解W1、W2、WM称为M种资源的影子价格（SHADOWPRICE）原始和对偶问题都取得最优解时，最大利润MAXZMINY3、资源影子价格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0W1W2WM4、产品的机会成本机会成本表示减少一件产品所节省的资源可以增加的利润增加单位资源可以增加的利润减少一件产品可以节省的资源机会成本利润差额成本5、产品的差额成本（REDUCEDCOST）差额成本机会成本利润5、互补松弛关系的经济解释在利润最大化的生产计划中（1）边际利润大于0的资源没有剩余（2）有剩余的资源边际利润等于0（3）安排生产的产品机会成本等于利润（4）机会成本大于利润的产品不安排生产第四章运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进基变量，调整运量，确定离基变量运输问题网络图2321341S227S319D122D213D312D413S114供应量供应地运价需求量需求地6753842759106运输问题线性规划模型供应地约束需求地约束运输问题的表格表示初始基础可行解西北角法813131466初始基础可行解最小元素法（1）最小元素法（2）最小元素法（3）最小元素法（4）最小元素法（5）最小元素法（6）5非基变量XIJ的检验数ZIJCIJ闭回路法1Z12C12C11C21C22C12684755闭回路法2Z13C13C11C21C23C136825555闭回路法3Z14C14C11C21C21C23C33C14C1368210637755闭回路法4Z24C24C23C33C34C242106799575闭回路法5Z31C31C21C23C33C318210511115795闭回路法6Z32C32C22C23C33C32421093357911非基变量XIJ的检验数ZIJCIJ对偶变量法1V40对偶变量法2U3V4C34U36对偶变量法3U3V3C33V34对偶变量法4U2V3C23U22对偶变量法5U2V2C22V26对偶变量法6U2V1C21V110对偶变量法7U1V1C11U14对偶变量法8Z12C12U1V2C1246755对偶变量法9Z13C13U1V3C13445555对偶变量法10Z14C14U1V4C144037755对偶变量法11Z24C24U2V4C2420799557对偶变量法12Z31C31U3V1C31610511115579对偶变量法13Z32C32U3V2C3266933557911选择进基变量,确定离基变量X31进基,MINX21,X33MIN8,66,X33离基3557911调整运量,重新计算检验数,确定进基、离基变量X14进基,MINX11,X34MIN14,1313,X34离基1155428调整运量,重新计算检验数所有ZIJCIJ0,得到最优解。MINZ61313824132125191421155482第五章网络优化网络的基本概念网络最小费用流问题网络最大流问题最短路径问题网络的基本概念节点与（有向）边每一条边和两个节点关联，一条边可以用两个节点的标号表示（I，J）JI路径（PATH）前后相继并且方向相同的边序列P1,2,2,3,3,442314231网络由节点和边组成回路（CIRCUIT）起点和终点重合的路径称为回路1,2,2,4,4,1回路中各条边方向相同4231链（CHAIN）前后相继并且方向不一定相同的边序列称为链C1,2,3,2,3,44231连通图任意两个节点之间至少有一条链的图称为连通图24351圈CYCLE起点和终点重合的链称为圈1,2,2,4,3,4,1,3圈中各条边方向不一定相同4231树TREE无圈的连通图称为树树中只与一条边关联的节点称为悬挂节点树的性质任何树至少有一个悬挂节点243512435124351如果树的节点个数为M，则边的个数为M1树中任意两个节点之间只有唯一的一条链在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈网络的生成树由网络的所有节点（M个）和网络的M1条边组成的树称为网络的生成树，网络中不属于生成树的边称为生成树的弦4231423142314231423142314231网络的生成树的变换4231网络的一个生成树，增加一条弦，形成唯一的圈，去掉生成树的一条边，得到一个新的网络的生成树423142314231生成树2生成树3生成树1/网络的生成树和线性规划的关系网络的一个生成树对应于线性规划的一个基生成树上的边对应于线性规划的基变量生成树的弦对应于线性规划的非基变量生成树的变换对应于线性规划单纯形法的进基和离基变换网络最小费用流问题B22B43B35B56B65B15C245C461C133C352C564C344C126234561需求节点供应节点CIJ单位流量的费用初始基础可行解生成树B65B22B43B35B56B15X133X463X358X562X122234561确定非基变量X24和X34B22B65B35B56B15C245C461C133C352C564C344C126234561B43求X24的检验数Z24C24闭回路法Z24C24C46C56C35C13C12C241423653B22B43B35B56B65B15C245C461C133C352C564C126234561求X34的检验数Z34C34闭回路法Z34C34C46C56C35C3414241，X34进基B22B43B35B56B65B15C461C133C352C564C344C126234561变量X34进基，确定离基变量MINX56,X35MIN2,82,X56离基，调整流量，进行基变换B22B43B35B56B65B15X463X133X358X562X340X122234561确定非基变量X24和X56B22B43B35B56B65B15X465X133X356X342X122234561计算X24和X56的检验数Z24C24、Z56C56Z24C24C34C13C12C2443654Z56C56C46C34C35C5614241，获得最优解B22B43B35B56B65B15C245C461C133C352C564C344C126234561最优解最优解的目标函数值为MINZ623342261546B22B43B35B56B65B15X465X133X356X342X122234561网络最大流问题2354671FFU256U422U454U233U137U344U463U361U657U579U678U128边的容量和流量容量UIJ，流量XIJ可行流满足以下条件的流称为可行流1、每一个节点流量平衡2、0XIJUIJ边的容量和流量、可行流21XIJ5UIJ521XIJ3UIJ5饱和边、不饱和边、流量的间隙（1，2）是饱和的2、如果XIJUIJ，边从I到J的方向是不饱和的；（1，2）是不饱和的间隙为12U12X125321、如果XIJUIJ，边从I到J的方向是饱和的；21XIJ0UIJ521XIJ5UIJ53、如果XIJ0，边从J到I的方向是饱和的；（2，1）是饱和的如果XIJ0，边从J到I的方向是不饱和的；（2，1）是不饱和的间隙为12X125给出一个初始的可行流XIJ02354671F0F0U6U2U4U3U7U4U3U1U7U9U8U8X0X0X0X0X0X0X0X0X0X0X0X0找到所有的不饱和边，以及各边可以调整流量的方向2354671F0F0U6U2U4U3U7U4U3U1U7U9U8U8X0X0X0X0X0X0X0X0X0X0X0X0找到一条从1到7的不饱和链链的间隙为MIN8,3,1,81调整链的流量XIJXIJ2354671F0F0U6U2U4U3U7U4U3U1U7U9U8U8X0X0X0X0X0X0X0X0X0X0X03188X0调整流量，F1。继续求出网络的不饱和边2354671F1F1U6U2U4U3U7U4U3U1U7U9U8U8X0X0X0X0X0X0X0X0X1X1X1X1求出一条从1到7的不饱和链2354671F1F1U6U2U4U3U7U4U3U1U7U9U8U8X0X0X0X0X0X0X0X0X1X1X1X11697MIN7,1,6,91,调整流量XIJXIJ1,FF12调整流量，继续求出网络的不饱和边2354671F2F2U6U2U4U3U7U4U3U1U7U9U8U8X1X0X0X1X0X0X0X1X1X1X1X0求出一条从1到7的不饱和链2354671F2F2U6U2U4U3U7U4U3U1U7U9U8U8X1X0X0X1X0X0X0X1X1X1X1X0587MIN7,5,85,调整流量XIJXIJ5,FF5257调整流量，继续求出网络的不饱和边2354671F7F7U6U2U4U3U7U4U3U1U7U9U8U8X6X0X0X1X0X0X0X6X1X1X6X0求出一条从1到7的不饱和链2354671F7F7U6U2U4U3U7U4U3U1U7U9U8U8X6X0X0X1X0X0X0X6X1X1X6X0MIN6,7,4,33,调整流量XIJXIJ3,FF373104436调整流量，继续求出网络的不饱和边2354671F10F10U6U2U4U3U7U4U3U1U7U9U8U8X6X0X3X4X3X0X0X9X1X1X6X0求出一条从1到7的不饱和链2354671F10U6U2U4U3U7U4U3U1U7U9U8U8X6X0X3X4X3X0X0X9X1X1X6X0F101373MIN3,1,3,71,调整流量XIJXIJ1,FF110111调整流量，继续求出网络的不饱和边2354671F11F11U6U2U4U3U7U4U3U1U7U9U8U8X6X0X4X5X3X1X0X9X2X1X6X0已找不到一条从1到7的不饱和链，从1开始可以到达的节点为1，2，3已求得最大流2354671F11U6U2U4U3U7U4U3U1U7U9U8U8X6X0X4X5X3X1X0X9X2X1X6X0F11最大流F11，最小割集为（2,5）（3,4）（3,5）U25U34U3564111最短路径问题237184566134105275934682求从1到8的最短路径237184566134105275934682X1,W10MINC12,C14,C16MIN02,01,03MIN2,1,31X1,4,W41W10W10237184566134105275934682X1,4MINC12,C16,C42,C47MIN02,03,110,12MIN2,3,11,32X1,2,4,W22W10W41W22237184566134105275934682X1,2,4MINC13,C23,C25,C47MIN03,26,25,12MIN3,8,7,33X1,2,4,6,W63W22W41W10W63237184566134105275934682X1,2,4,6MINC23,C25,C47,C67MIN26,25,12,34MIN8,7,3,73X1,2,4,6,7,W73W22W41W10W63W73237184566134105275934682X1,2,4,6,7MINC23,C25,C75,C78MIN26,25,33,38MIN8,7,6,116X1,2,4,5,6,7,W56W22W41W10W63W73W56237184566134105275934682X1,2,4,6,7MINC23,C53,C58,C78MIN26,69,64,38MIN8,15,10,118X1,2,3,4,5,6,7,W38W22W41W10W63W73W56W38237184566134105275934682X1,2,3,4,6,7MINC38,C58,C78MIN86,64,37MIN14,10,1110X1,2,3,4,5,6,7,8,W810W22W41W10W63W73W56W38W810237184566134105275934682X1,2,3,4,6,7,81到10的最短路径为1，4，7，5，8，长度为10。W22W41W10W63W73W56W38W810第六章动态规划最短路径问题资源分配问题背包问题机器负荷分配问题2511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径2511214106104131112396581052C1C3D1AB1B3B2D2EC2F5E02511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D15F5E02511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D22F5E0F4D152511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D22F5E0F3C18F4D152511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D22F5E0F3C27F4D15F3C182511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D22F5E0F3C312F4D15F3C18F3C272511214106104131112396581052C1C3D1AB1B3B2D2EC2F4D22F5E0F3