《对偶问题和运输问题精选PPT.ppt》由会员分享，可在线阅读，更多相关《对偶问题和运输问题精选PPT.ppt（76页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶问题和运输问题第1页，此课件共76页哦例3 写对偶问题Min z=2x1+3x2-5x3+x4 x1+x2-3x3+x4=5 2x1 +2x3-x4=4 x2+x3+x4 =6 x1=0 x4无约束 Max z=5y1+4y2+6y3 y1+2y2 =0 y1 +y3=0 -3y1+2y2+y3=0,y2=0,y3无约束第2页，此课件共76页哦 3.对偶定理(原问题与对偶问题解的关系）考虑（LP）和（DP）定理3-1(弱对偶定理）若 x,y 分别为（LP)和（DP）的可行解，那么cTx bTy。推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（LD）无可行解。1.1.线性规划
2、对偶问题线性规划对偶问题第3页，此课件共76页哦 定理3-2(最优性准则定理)若x,y分别(LP),(DP)的可行解,且cTx=bTy，那么x,y分别为(LP)和(DP)的最优解。定理3-3(主对偶定理)若(LP)和(DP)均可行 那么(LP)和(DP)均有最优解,且最优值相等。以上定理、推论对任意形式的相应性规划的对偶均有效1.1.线性规划对偶问题线性规划对偶问题第4页，此课件共76页哦4、原始问题和对偶问题最优解之间的互补松弛关系min z=CTXs.t.AX-XS=b X,XS0max y=bTWs.t.ATW+WS=C W,WS0min z=CTXs.t.AXb X 0max y=bT
3、Ws.t.ATWC W0对偶引进松弛变量引进松弛变量XTWS=0 WTXS=0互补松弛关系X，XsW，Ws第5页，此课件共76页哦五、对偶的经济解释1、原始问题是利润最大化的生产计划问题单位产品的利润（元/件）产品产量（件）总利润（元）资源限量（吨）单位产品消耗的资源（吨/件）剩余的资源（吨）消耗的资源（吨）第6页，此课件共76页哦2、对偶问题资源限量（吨）资源价格（元/吨）总利润（元）对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min y第7页，此课件共76页哦3、资源影子价
4、格的性质影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0第8页，此课件共76页哦 影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。1.1.线性规划对偶问题线性规划对偶问题第9页，此课件共76页哦 需要指出，影子价格不是固定不变的，当
5、约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。1.1.线性规划对偶问题线性规划对偶问题第10页，此课件共76页哦 5.由最优单纯形表求对偶问题最优解 标准形式：Max z=50 x1+100 x2 s.t.x1+x2+x3 =300 2x1+x2+x4=400 x2+x5=250 x1,x2,x3,x4,x5 01.1.线性规划对偶问题线性规划对偶问题第11页，此课件共76页哦max
6、z=CTXs.t.AX+XS=b X,XS0max y=bTWs.t.ATW-WS=C W,WS0max z=CTXs.t.AX b X 0min y=bTWs.t.ATW C W 0单纯形表和对偶对偶问题原始问题引进松弛变量引进松弛变量第12页，此课件共76页哦max z=CTXs.t.AX+XS=b X,XS0min y=bTWs.t.ATW-WS=C W,WS0WT=CBTB-1WST=WTA-CT第13页，此课件共76页哦-c-cB BT TB B-1-1I IB B=(p p1 1,p,p4 4,p,p2 2)oTB B-1-1最优解 x1=50 x2=250 x4 =50影子价格影
7、子价格 y y1 1=50 =50 y y2 2=0 =0 y y3 3 =50,=50,B B-1-1对应的检验数对应的检验数 T T=c cB BT TB B-1-1 。1.1.线性规划对偶问题线性规划对偶问题第14页，此课件共76页哦例3.2：求解线性规划问题：求解线性规划问题：标准化：标准化：Max z=-2x1-3x2 -4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x3 0 2.2.对偶单纯形法对偶单纯形法第
8、15页，此课件共76页哦 对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基基本本解解出发，此基本解不一定可行，但它对应着一个对对偶偶可可行行解解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。2.2.对偶单纯形法对偶单纯形法第16页，此课件共76页哦 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原
9、规划的可行解时，便得到原规划的最优解。2.2.对偶单纯形法对偶单纯形法第17页，此课件共76页哦 对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。2.2.对偶单纯形法对偶单纯形法第18页，此课件共76页哦 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bk0则选k行的满足min bk0基变量为出基变量,转3 3.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,
10、若有akj0 则选 =minj/akjakj0=r/akr那么 xr为进基变量,转4；4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：2.2.对偶单纯形法对偶单纯形法第19页，此课件共76页哦例3.2：求解线性规划问题：求解线性规划问题：标准化：标准化：Max z=-2x1-3x2 -4x3 s.t.-x1-2x2-x3+x4=-3 -2x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0Min f=2x1+3x2+4x3 S.t.x1+2x2+x3 3 2x1-x2+x3 4 x1,x2,x
11、3 0 2.2.对偶单纯形法对偶单纯形法第20页，此课件共76页哦表格对偶单纯形法2.2.对偶单纯形法对偶单纯形法第21页，此课件共76页哦单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0csMinj/asjasj0brMin-bi/airair03.3.灵敏度分析灵敏度分析第36页，此课件共76页哦 例3.5:上例最优单纯形表如下 3.3.灵敏度分析灵敏度分析第37页，此课件共76页哦 0 0.25 0 这里 B
12、B-1=-2 0.5 1 0.5-0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1,x5,x2分别变为：4+04=4,4+(-2)4=-40,2+0.54=4用对偶单纯形法进一步求解，可得：x*=(4,3,2,0,0)T f*=173.3.灵敏度分析灵敏度分析第38页，此课件共76页哦 增加一个变量 增加变量 xn+1 则有相应的pn+1,cn+1。那么 计算出B B-1pn+1,n+1=cn+1-cri ari n+1 填入最优单纯形表,若 n+1 0 则 最优解不变；否则，进一步用单纯形法求解。3.3.灵敏度分析灵敏度分析第39页，此课件共76页
13、哦例3.6:例3.4增加x6,p6=(2,6,3)T,c6=5 计算得到用单纯形法进一步求解，可得：x*=(1,1.5,0,0,0,2)T f*=16.53.3.灵敏度分析灵敏度分析第40页，此课件共76页哦 增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯形法或对偶单纯形法求解。3.3.灵敏度分析灵敏度分析第41页，此课件共76页哦例3.7:例3.4增加3x1+2x215，原最优解不满足这个
14、约束。于是3.3.灵敏度分析灵敏度分析经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为 13.75第42页，此课件共76页哦 A A中元素发生变化(只讨论 N 中某一列变化情况）与增加变量 xn+1 的情况类似，假设 pj 变化。那么，重新计算出 B B-1pj j=cj-cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。（例子从略）3.3.灵敏度分析灵敏度分析第43页，此课件共76页哦第四章 运输问题运输问题的表示网络图、线性规划模型、运输表初始基础可行解西北角法、最小元素法非基变量的检验数闭回路法、对偶变量法确定进
15、基变量，调整运量，确定离基变量第44页，此课件共76页哦2321341运输问题网络图s2=27s3=19d1=22d2=13d3=12d4=13s1=14供应量供应地运价需求量需求地6753842759106第45页，此课件共76页哦运输问题线性规划模型供应地约束需求地约束第46页，此课件共76页哦运输问题的表格表示第47页，此课件共76页哦初始基础可行解西北角法813131466第48页，此课件共76页哦初始基础可行解最小元素法（1）第49页，此课件共76页哦最小元素法（2）第50页，此课件共76页哦最小元素法（3）第51页，此课件共76页哦最小元素法（4）第52页，此课件共76页哦最小元素
16、法（5）第53页，此课件共76页哦最小元素法（6）第54页，此课件共76页哦-5非基变量xij的检验数zij-cij闭回路法(1)z12-c12=(c11-c21+c22)-c12=6-8+4-7=-5第55页，此课件共76页哦-5闭回路法(2)z13-c13=(c11-c21+c23)-c13=6-8+2-5=-5-5第56页，此课件共76页哦-5闭回路法(3)z14-c14=(c11-c21+c21-c23+c33-c14)-c13=(6-8+2-10+6)-3=-7-7-5第57页，此课件共76页哦-5闭回路法(4)z24-c24=(c23-c33+c34)-c24=(2-10+6)-7
17、=-9-9-5-7第58页，此课件共76页哦-5闭回路法(5)z31-c31=(c21-c23+c33)-c31=(8-2+10)-5=+11+11-5-7-9第59页，此课件共76页哦-5闭回路法(6)z32-c32=(c22-c23+c33)-c32=(4-2+10)-9=+3+3-5-7-9+11第60页，此课件共76页哦非基变量xij的检验数zij-cij对偶变量法(1)v4=0第61页，此课件共76页哦对偶变量法(2)u3+v4=c34u3=6第62页，此课件共76页哦对偶变量法(3)u3+v3=c33v3=4第63页，此课件共76页哦对偶变量法(4)u2+v3=c23u2=-2第6
18、4页，此课件共76页哦对偶变量法(5)u2+v2=c22v2=6第65页，此课件共76页哦对偶变量法(6)u2+v1=c21v1=10第66页，此课件共76页哦对偶变量法(7)u1+v1=c11u1=-4第67页，此课件共76页哦对偶变量法(8)z12-c12=u1+v2-c12=(-4)+6-7=-5-5第68页，此课件共76页哦对偶变量法(9)z13-c13=u1+v3-c13=(-4)+4-5=-5-5-5第69页，此课件共76页哦对偶变量法(10)z14-c14=u1+v4-c14=(-4)+0-3=-7-7-5-5第70页，此课件共76页哦对偶变量法(11)z24-c24=u2+v4
19、-c24=(-2)+0-7=-9-9-5-5-7第71页，此课件共76页哦对偶变量法(12)z31-c31=u3+v1-c31=6+10-5=1111-5-5-7-9第72页，此课件共76页哦对偶变量法(13)z32-c32=u3+v2-c32=6+6-9=+3+3-5-5-7-911第73页，此课件共76页哦选择进基变量,确定离基变量x31进基,minx21,x33=min8,6=6,x33离基+3-5-5-7-911第74页，此课件共76页哦调整运量,重新计算检验数,确定进基、离基变量x14进基,minx11,x34=min14,13=13,x34离基-11-5-5+4+2-8第75页，此课件共76页哦调整运量,重新计算检验数所有zij-cij0,得到最优解。Min z=61+3 13+8 2+4 13+2 12+5 19=142-11-5-5-4-8-2第76页，此课件共76页哦