《{交通运输管理}对偶问题和运输问题》由会员分享，可在线阅读，更多相关《{交通运输管理}对偶问题和运输问题（76页珍藏版）》请在金锄头文库上搜索。
1、原问题与对偶问题的关系,例3 写对偶问题,Min z=2x1+3x2-5x3+x4 x1+x2-3x3+x4=5 2x1 +2x3-x4=0 x4无约束,Max z=5y1+4y2+6y3 y1+2y2 =0 y1 +y3=0,y2=0, y3无约束,3.对偶定理 (原问题与对偶问题解的关系） 考虑（LP）和（DP）,定理3-1 (弱对偶定理） 若 x, y 分别为（LP) 和（DP）的可行解，那么cTx bTy。,推论 若（LP）可行，那么（LP） 无有限最优解的充分必要条件是（LD） 无可行解。,1.线性规划对偶问题,定理3-2 (最优性准则定理) 若x,y分别(LP),(DP)的可行解,
2、且 cTx=bTy ，那么x,y分别为(LP)和(DP) 的最优解。,定理3-3 (主对偶定理) 若(LP)和(DP)均可行 那么(LP)和 (DP)均有最优解,且最优值相等。,以上定理、推论对任意形式的相 应性规划的对偶均有效,1.线性规划对偶问题,4、原始问题和对偶问题最优解之间的互补松弛关系,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,对偶,引进松弛变量,引进松弛变量,XTWS=0 WTXS=0,互补松弛关系,五、对偶的
3、经济解释,1、原始问题是利润最大化的生产计划问题,单位产品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,影子价
4、格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,1.线性规划对偶问题,需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，影子价格的经济含义（2），是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增
5、加。这个问题还将在灵敏度分析一节中讨论。,1.线性规划对偶问题,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 0,1.线性规划对偶问题,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,单纯形表和对偶,对偶问题,原始问题,引进松
6、弛变量,引进松弛变量,max z=CTX s.t. AX+XS=b X, XS0,min y=bTW s.t. ATW-WS=C W, WS0,WT=CBTB-1 WST=WTA- CT,-cBTB-1,I,B=(p1, p4,p2 ),oT,B-1,最优解 x1 = 50 x2 = 250 x4 = 50 影子价格 y1 = 50 y2 = 0 y3 = 50 , B-1对应的检验数 T = cBTB-1 。,1.线性规划对偶问题,例3.2：求解线性规划问题：,标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+
7、x5= -4 x1,x2,x3,x4,x5 0,Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0,2.对偶单纯形法,对偶单纯形法的基本思想 对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。,2.对偶单纯形法,如果得到的基本解的分量皆非负则该基本解为最优解
8、。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,2.对偶单纯形法,对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,2.对偶单纯形法,1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的满足min bk0基变量为出基变量,转3
9、3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,对偶单纯形法求解线性规划问题 过程：,2.对偶单纯形法,例3.2：求解线性规划问题：,标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0,Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x
10、1 - x2 + x3 4 x1 , x2 , x3 0,2.对偶单纯形法,表格对偶单纯形法,2.对偶单纯形法,单纯形法和对偶单纯形法步骤,对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线性规划问题,2.对偶单纯形法,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏
11、度分析中有时也要用到对偶单纯形方法，可以简化计算。,2.对偶单纯形法,单纯形表的理解（例题）,上表中6个常数 a1 , a2 , a3 , b , 1 , 2 取值在什么范围可使 1、现可行解最优，且唯一？何时不唯一？ 2、现基本解不可行； 3、问题无可行解； 4、无有限最优解； 5、现基本解可行，由 x1 取代 x6 目标函数可改善。,进一步理解最优单纯性表中各元素的含义考虑问题 Max z = c1 x1 + c2 x2 + + cn xn s.t. a11x1 + a12x2 + + a1nxn = b1 a21x1 + a22x2 + + a2nxn = b2 . . . am1x1
12、+ am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0,3.灵敏度分析,3、灵敏度分析,无防设，xj = 0 j = m+1, , n ; xi = bi i = 1 , , m 是基本可行解, 对应的目标函数典式为：z = -f + m+1xm+1+ nxn 以下是初始单纯形表： m m 其中：f = - ci bi j = cj - ci aij 为检验数。 向量 b = B-1 b i = 1 i = 1 A= p1, p2, , pn , pj = B-1 pj, pj = ( a1j , a2j , , amj )T ， j = m+1, , n,ci , bj发
13、生变化 增加一约束或变量及A中元素发生变化通过例题学会处理,对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基 B 的逆矩阵 B-1 ， B-1b 以及 B-1N，检验数 j 等。,3.灵敏度分析,价值系数c发生变化： m 考虑检验数 j = cj - cri arij j =1,2,n i = 1,1. 若ck是非基变量的系数： 设ck变化为 ck + ck k= ck + ck -cri arik = k+ ck 只要 k 0 ,即 ck - k ，则 最优解不变；否则，将最优单纯形表 中的检验数 k 用 k取代，继续单 纯形法的表格计算。,3.灵敏度分析,例3.3: Max
14、z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 0,3.灵敏度分析,例：最优单纯形表,从表中看到3= c3+c3-(c2a13+c1a23 ) 可得到c3 9/5 时，原最优解不变。,3.灵敏度分析,2、若 cs 是基变量的系数： 设 cs 变化为 cs + cs ，那么 j= cj -cri arij - ( cs + cs ) asj = j - cs asj ， i s,对所有非基变量，只要对所有非基变量 j 0 ，即 j cs asj ，则最优解 不变；否则，将最
15、优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。 Maxj/asjasj0csMinj/asjasj0,3.灵敏度分析,例3.4: Max z = 2x1 + 3x2 + 0 x3 + 0 x4+ 0 x5,s.t. x1 + 2x2 + x3 = 8 4x1 + x4 = 16 4x2 + x5 = 12 x1 , x2 , x3 , x4 , x5 0,3.灵敏度分析,例: 下表为最优单纯形表,考虑 基变量系数c2发生变化,从表中看到 j=cj-(c1a1j+c5 a5j+(c2+c2) a2j)j=3,4 可得到 -3c21时，原最优解不变。,3.灵敏度分析,右端项 b 发生变化 设分量 br 变化为 br + br ，根据第1章的讨论，最优解的基变量 xB = B-1b，那么只要保持 B-1(b + b) 0 ，则最优基不变，即基变量保持，只有值的变化；否则，需要利用对偶单纯形法继续计算。 对于问题 (LP) Max z = cT x s.t. Ax b x 0,3.
