《线性规划理论与模型应用02》由会员分享，可在线阅读，更多相关《线性规划理论与模型应用02（51页珍藏版）》请在金锄头文库上搜索。
1、主要内容2.1 对偶规划 2.2 对偶定理 2.3 对偶单纯形法 2.4 灵敏度分析2.1对偶规划1.食谱问题设有n种食物,各含m种营养素,第j种食物中第i种营 养素的含量为aij, 所有n种食物价格分别为 c1,c2,cn,营养素的价格分别为w1,w2,wm,要求食 谱中m种营养素的含量分别不低于b1,b2,bm,食谱 中n种食物的数量为x1,x2, ,xn,如下表所示:对 偶 规 划n消费者希望费用最低且满足营养要求，则有n食谱厂家在确定营养素价格时，希望收益最大且 能吸引消费者，则有对 偶 规 划前述的两个规划是同一问题的两个方面:n消费者希望费用最低；n营养厂家希望收益最大。 这一对问
2、题即是我们要研究的线性规划的对偶问 题.对 偶 规 划n对称形式下对偶规划 考虑以下两种形式的线性规划问题对 偶 规 划定义2.1 称以上两种形式的线性规划问题为一对对偶线 性规划问题，其中LP问题为原规划，LD问题为对偶规划。其矩阵形式表示为其中其中定义2.2 满足下列条件的线性规划问题为成为具有对称 形式：变量均具有非负约束；当目标求极小时约束条 件均为“”，当目标求极大时约束条件均为“”。对 偶 规 划如果将对偶规划(LD)作为原规划，其形式为其对偶规划是其对偶规划是即是原规划即是原规划定理定理2.12.1 对偶规划的对偶规划是原规划，即对偶规划的对偶规划是原规划，即LDLD是是LPLP
3、的的 对偶规划时，对偶规划时，LPLP也也是是LDLD的对偶规划。的对偶规划。对 偶 规 划对称形式下原规划和对偶规划转换规则：u原规划min问题，对偶规划max问题u右端项与目标系数互相转换；u系数矩阵互为转置关系；u原规划约束条件对应对偶规划的变量 约束，对偶规划对应 的变量0；u原规划的变量对应对偶规划的约束条件 变量0，对偶规划中对应 的约束为 约束 非对称形式下的特点 线性规划问题的约束条件有、=、 约束，变量中有0、0、自由变量对 偶 规 划n非对称形式下对偶规划 例2.1 写出下述线性规划问题的对偶规划对 偶 规 划将约束全变为“”此问题的对偶问题为对 偶 规 划此问题的对偶问题
4、为对 偶 规 划非对称形式下原规划和对偶规划转换规则：u原规划min问题，对偶规划max问题u右端项与目标系数互相转换；u系数矩阵互为转置关系；u原规划约束条件t约束，对偶规划对应 的变量0；t约束，对偶规划对应 的变量0；t=约束，对偶规划对应 的变量无约束(自 由变量)；u原规划的变量约束t0的变量，对偶规划中对应 的约束为约 束；t0的变量，对偶规划中对应 的约束为约 束；t自由变量，对偶规划中对应 的约束为=约 束。对 偶 规 划例2.2 写出下述线性规划问题的对偶规划2.2对偶定理为便于讨论，本节仅对对称形式的对偶规划进行讨论， 非对称形式的对偶规划同样可证明类似的结论。为方便起见，
5、LP简称为P,LD简称为D。对 偶 定 理1. 弱对偶定理 定理2.2 设x0是P的可行解，w0是D的可行解，则u cx0 w0b； u若x*、w*分别是P、D的可行解且cx*=w*b，则x*、 w*分别是P、D的最优解； u若P、D中有一个目标函数值无界，则另一个可行 域为空集； uP、D都有最优解的充要条件是P、D都有可行解。证：1) 因为Ax0 b，x0 0，w0Ac，w0 0，对Ax0 b两 边左乘w0则有w0Ax0 w0b；对w0Ac两边右乘x0则有 w0Ax0 cx0；从而有cx0 w0b。2) 设x0是P的任意可行解，由1)有cx0 w*b=cx*从而x* 是P的最优解；同样可证
6、w*是D的最优解。 用1)的结论可容易证明3)和4)成立。对 偶 定 理2. 强对偶定理 定理2.3 一对对偶规划P和D中的一个有最优解的充要 条件是另一个有最优解，且两问题的最优值相等。 证：对问题P引入松弛变量v=(xn+1,xn+m)T将其变成设该问题的最优解为x*，B为最优基，则有令w*=cBB-1，则有w*是D的可行解又w*b= cBB-1b=cx*，由定理2.2可知 w* 是D的最优解。对 偶 定 理3. 互补松弛定理及其应用 定理2.4(互补松弛定理)已知x*,w*分别是P和D的可行 解，则它们分别是P和D的最优解的充要条件是 w*(Ax* - b)= 0 , (c - w*A)
7、x* = 0 证：因为x*,w*分别是P和D的可行解，从而w*b w*Ax* cx*必要性：若x*,w*分别是P和D的最优解，则w*b=cx*， 从而上式中两“”号等式成立，显然结论成立。 充分性：若w*(Ax*-b)= 0，则w*Ax* = w*b， 若(c- w*A)x*=0，则cx* = w*Ax* 从而cx* = w*b，即x*,w*分别是P和D的最优解对 偶 定 理将互补松弛定理的结论写成如下形式：以上两式表示 P规划的约束严格不等号成立(松)时，D规划相应的变 量必取0 (紧)； D规划的约束严格不等号成立(松)时，P规划相应的变 量必取0 (紧)，非基变量； 第二式也就是j xj
8、=0(j=1,2,n)表示在P规划中检验数 与变量互为松弛。对 偶 定 理例2.3 求解线性规划问题其对偶问题：对 偶 定 理对偶规划是两个变量的问题可用图解法求解，得对偶规 划 的最优解显然，第1、5个约束等式成立 ， 其它严格不等式成立，由互补 松弛定理原规划的最优解中 x2* =x3*=x4* =0，因为w1*和w2*均 不 等于0，从而原规划的最优解 中 两个约束是紧的，即对 偶 定 理例2.4 求解线性规划问题的对偶问题：对 偶 定 理用单纯形表格求解线性规划问题对 偶 定 理原问题的最优解为对偶问题的最优解为作业P74：4，5，72.3对偶单纯形法1.理论基础 考虑线性规划标准形其
9、对偶规划为对 偶 单 纯 形 法n由对偶定理，若有x*, w*满足Ax*=b, x* 0, w*A c, cx*=w*b，则x*, w*是P,D的最优解；n考虑单纯形法的迭代过程，若x是基可行解，B是相应 的可行基，则Ax=b,x 0。令w=cBB-1，则cx=wb，检 验数可表示为=c - cBB-1A=c wA；n在单纯形法的迭代中，对偶定理中的4个条件由3个条 件Ax=b, x 0, cx=wb始终满足；n单纯形法的迭代过程实际上可看作验证检验数是否满 足0的过程，也就是验证D问题约束条件wAc是否 满足的过程;n单纯形法迭代也可看作是从原问题P的基可行解逐步 迭代到对偶问题D的可行解的
10、过程（两问题的目标函 数值始终相等）。n对偶单纯形法的本质是从对偶问题的可行解逐步迭代 到原问题P的可行解的过程。对 偶 单 纯 形 法n定义 若A=(B,N), 其中B非奇异，w=cBB-1称为D的一个基解，若c -cBB-1A 0,即wAc，称w为D的一个基可行解，此时称B为原规划的一个正则基， 称为原规划问题的一个正则基解。n对偶单纯形法的基本思想：若有一个正则基B，则w=cBB-1满足wAc，Ax=b，cx=wb，若x 0，则x已是最优解，否则求另一个正则基解，直到满足若x 0为止。n原规划单纯形迭代是在满足Ax=b和x 0前提下逐步使解达到最优；对偶单纯形法迭代是在满足Ax=b和最优
11、性条件前提下逐步使解满足x0。对 偶 单 纯 形 法2.对偶单纯形表格 不妨设前m个为基变量，表格形式仍然如同单纯形表 格区别在于检验数始终满足j 0，不再要求bi 0。迭代 思想是，如果br0，则为xr出基变量；选进基变量xk使所有j 0仍然成立，进行转轴变换使xk所在列为单位向 量。对 偶 单 纯 形 法对检验数行消元之后，目标函数形式为为保证j 0仍然成立，显然下式确定的k即可如果yr,j0，则原问题无可行解。如何使所有如何使所有 j j 0 0仍然成立，考虑仍然成立，考虑x xr r所在方程和目标函数。所在方程和目标函数。对 偶 单 纯 形 法例2.6 用对偶单纯形法求解下述线性规划问
12、题解：转化为标准形取x4, x5为基变量，方程两边乘以-1，则有如下标准形对 偶 单 纯 形 法此问题x4, x5为基变量时，检验数均为正，是一个正则基 ， 对偶单纯形表格为x4为出基变量，x2为进基变量，以y12为主元做转轴变换 得对 偶 单 纯 形 法x5为出基变量，x3为进基变量，以y23为主元做转轴变换 得原问题的最优解x=(0, , )T，最优值z*=17/2。作业P77：82.4 灵敏度分析 目标系数的灵敏度分析 目标系数变化对最优解的影响 为求出数据变化后的最优解，不必从最初的阶段开始求解，仅从原问题最后的单纯形表的基础之上，重新 计算检验数，然后求出最优解并与原最优解比较。 不
13、影响最优基变化时系数ck的变化范围灵敏度分析，是讨论线性规划问题中原始数据灵敏度分析，是讨论线性规划问题中原始数据a aij ij，b bi i，c cj j的变的变 化对最优解的影响，所谓对最优解的影响主要有两个层面，化对最优解的影响，所谓对最优解的影响主要有两个层面， 一是对最优解的影响，另一是当某个数据在什么范围内变化一是对最优解的影响，另一是当某个数据在什么范围内变化 时，最优基将不会改变。本节讨论时，最优基将不会改变。本节讨论b bi i和和c cj j的变化、增加变量对的变化、增加变量对 最优解的影响。最优解的影响。灵 敏 度 分 析设目标系数ck的改变量为 ,其中 为 变化之后的
14、系数。v当xk不是基变量时，此时只对检验数k产生影 响，只要考虑保持k0即可。v当xk是基变量时，此时ck的变化将对所有检验 数产生影响。设xk对应第i个方程，基的新旧目 标系数为灵 敏 度 分 析灵 敏 度 分 析例2.7 某工厂用甲乙两种原料生产A、B、C、D四种 产品，每种产品的利润、原料数量、每种产品消耗 原料定额如下表所示：问应怎样组织生产才能使总利润最大？如果产品问应怎样组织生产才能使总利润最大？如果产品A A 、D D 的利润均变到的利润均变到1515万元，最优解有何变化？又各产品的利万元，最优解有何变化？又各产品的利润在何范围内变化时，最优基不变润在何范围内变化时，最优基不变？
15、 解：解：1) 1) 设设x x1 1，x x2 2，x x3 3， x x4 4分别表示分别表示A A、B B、C C、D D四种产品四种产品的生产数量，可建立如下模型：的生产数量，可建立如下模型：灵 敏 度 分 析化为标准形用单纯形法得到最后一个表格如下，最优解产品用单纯形法得到最后一个表格如下，最优解产品C C生产生产 1 1万件，产品万件，产品D D生产生产2 2万件，总利润万件，总利润8888万元。万元。灵 敏 度 分 析2) 计算c1，c4改变后的检验数代入上表格(在当前基下 )灵 敏 度 分 析3) 讨论cj(j=1,2,3,4)的变化范围(1) 非基变量x1，x2的检验数为1=4，2=2/3，系数的变化范围是从而c1，c2变化范围分别是(2)基变量x3，x4的系数，先考虑c3变化范围灵 敏 度 分 析从而c3变化范围分别是再考虑c4变化范围得到c4变化范围分别是灵 敏 度 分 析2. 右端项的灵敏度分析 v 右端项的几个分量改变对最优解的影响，此时不影响 检验数，但可能影响基变量的非负性，如果B-1b0， 当前解仍然是最优解，否则，用对偶单纯形法求出最 优解。 v 另一类有意义的问题是当某一个分量在什么范围内变 化，才不影响基变量，设bk的改变量为 ，记当前 最优解的基解为 ，改变后的基解为 ，则有设设 ，如果，如果 ，则应
