-对偶问题资料课件

2024/7/25-第2章 对偶问题-1-第 二 章 线性规划的对偶理论Duality 对偶Dual Problem 对偶问题 Dual Linear Programming 对偶线性规划Dual Theory 对偶理论2024/7/252例例 甲方甲方生产计划问题：生产计划问题：能力能力 设备设备A 2 2 12 设备设备B 4 0 16 设备设备C 0 5 15 利润利润 2 3，各生产多少各生产多少,可获最大利润可获最大利润?乙方乙方租借设备：租借设备：甲方以何种价格将设备甲方以何种价格将设备A、B、C租借给乙方比较合理？租借给乙方比较合理？请为请为其定价。其定价。2.1 问题的提出-第2章 对偶问题-2024/7/253而就乙方而言而就乙方而言，希望甲方的租金收入在满足约束的条件下越小越好，希望甲方的租金收入在满足约束的条件下越小越好，这样双方才可能达成协议。这样双方才可能达成协议。于是得到下述于是得到下述 的线性规划模型：的线性规划模型：解：解：假设假设A、B、C的单位租金分别为的单位租金分别为 ，所以生产产品，所以生产产品的资源的资源用于出租时，租金收入应满足：用于出租时，租金收入应满足：类似的，生产产品类似的，生产产品的资源用于出租时，租金收入应满足：的资源用于出租时，租金收入应满足：总的租金收入：总的租金收入：-第2章 对偶问题-思路思路：就甲方而言就甲方而言，租金收入应不低于将设备用于自己生产时的利润。租金收入应不低于将设备用于自己生产时的利润。原问题的对偶问题原问题的对偶问题2024/7/25-第2章 对偶问题-4-例：某企业计划生产甲、乙两种产品，该两种产品均需经 A、B、C、D 四种不同设备加工，按工艺资料规定，在各种不同设备上的加工时间及设备加工能力、单位产品利润如表中所示。问：如何安排产品的生产计划，才能使企业获利最大?2024/7/25-第2章 对偶问题-5-1.最大生产利润模型设 企业生产甲产品为X1件，乙产品为X2件，则 max z=2 X1+3 X2 s.t 2 X1+2 X2 12 X1+2 X2 8 4 X1 16 4 X2 12 X1 0,X2 02.资源最低售价模型(原问题)(对偶问题)设第i种资源价格为yi,（i=1,2,3,4,）则有min w=12y1+8y2+16y3+12 y4s.t 2y1+y2+4y3+0 y4 2 2y1+2y2+0y3+4 y4 3yi 0,(i=1,2,3,4)y1y2y3y42024/7/25-第2章 对偶问题-6-2.2 原问题与对偶问题的关系一般表示式：原问题：max z=c1 X1+c2 X2+cn Xn s.t a11 X1+a12 X2+a1n Xn b1 a21 X1+a22 X2+a2n Xn b2 am1 X1+am2 X2+amn Xn bm xj 0，j=1,2,n 对偶问题：min w=b1 y1+b2 y2+bm ym s.t a11 y1+a21 y2+am1 ym c1 a12 y1+a22 y2+am2 ym c2 a1n y1+a2n y2+amn ym cn yi 0，(i=1,2,m)2024/7/25-第2章 对偶问题-7-典式模型对应对偶结构矩阵表示（1）max z=C X s.t AX b X 0min w=Y b s.t YA C Y 0 对偶问题原问题这是规范形式这是规范形式 的原问题，由此写出其对偶问题如右方所示，那么，当原问题的原问题，由此写出其对偶问题如右方所示，那么，当原问题不是规范形式时，应如何写出其对偶问题？不是规范形式时，应如何写出其对偶问题？可以先将原问题化成规范的可以先将原问题化成规范的原问题，再写出对偶问题。原问题，再写出对偶问题。2024/7/25-第2章 对偶问题-8-对偶模型其他结构关系（2）若模型为 max z=C X s.t AX b X 0max z=C X s.t -AX -b X 0变形min w=Y b s.t YA C Y 0 Min w=Y(-b)st.Y(-A)CY 0令 Y=-Y 对偶问题对偶变量Y2024/7/25-第2章 对偶问题-9-（3）max z=C X s.t AX b X 0变形设X=-Xmax=-CX st.-AX b X 0min w=Y b s.t YA C Y 0则有min w=Y b s.t -YA-CY 02024/7/25-第2章 对偶问题-10-对偶问题典式：用矩阵形式表示：（1）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （2）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 0 （3）max z=C X min w=Y b s.t AX b s.t YA C X 0 Y 011等式、无约束情况的对偶：等式、无约束情况的对偶：原问题对偶问题12推导:原问题化为：即：13 根据对称形式的对偶模型,可直接写出上述问题的对偶问题:14令 ，得对偶问题为：2024/7/25-第2章 对偶问题-15-原问题与对偶问题关系表 原问题(对偶问题)对偶问题(原问题)目标函数系数 约束右端项 约束右端项 目标函数系数 约束条件系数列向量 A约束条件系数行向量 AT 变量个数约束条件个数max min 变量 x j:约束方程 i:x j 0 x j 无约束 =x j 0 约束方程:变量 y i:y i 0 =y i 无约束 y i 0 2024/7/25-第2章 对偶问题-16-2.3 对偶问题的基本性质 Max z=CXMin w=Y b s t.AX b s t.YA C X 0Y 0(1)弱对偶性：若 X0原问题可行解，Y0对偶问题可行解则 CX0 Y0 b证明：Y0 0，AX0 b，Y0 AX0 Y0 b，而 Y0 A C，CX0 Y0AX0 ，CX0 Y0 AX0 Y0 b 推论1:原问题任一可行解的目标函数值是其对偶问题目标函数值的下届；反之，对偶问题任意可行解的目标函数值是其原问题目标函数值的上界。推论2:在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题无可行解；反之不成立。这也是对偶问题的无界性。2024/7/25-第2章 对偶问题-17-（2）最优性：若 X0原问题可行解，Y0对偶问题可行解，且 CX0=Y0 b 则 X0原问题最优解，Y0对偶问题最优解证明：设 X*原问题最优解，Y*对偶问题最优解 则 CX0 CX*Y*b Y0 b 但 CX0=Y0 b，CX0=CX*=Y*b =Y0 b X0=X*，Y0=Y*即 X0原问题最优解，Y0对偶问题最优解证毕。若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。2024/7/25-第2章 对偶问题-18-（3）无界性若原问题最优解无界，则对偶问题无可行解 证：有性质1，C X0 Y0 b，当 CX0 时，则不可能存在Y0，使得 C X0 Y0 b。注：逆定理不成立，即 如果原问题（对偶问题）无可行解，那么 对偶问题（或原问题）“解无界”不成立。2024/7/25-第2章 对偶问题-19-（4）强对偶性（对偶定理）若原问题有最优解，则对偶问题一定有最优解，且有 z max=w min证：由 =C-CB B-1 A 0 令 CBB-1=Y*，得 Y*A C-Y*=-CBB-1 0，Y*0 因此，Y*是对偶问题的可行解，又 CX*=CB(B-1 b)=CB B-1b=Y*b Y*是对偶问题的最优解。还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。2024/7/25-第2章 对偶问题-20-Max z=CX st.AX b X 0Max z=CX st.AX+Xs=b X 0标准形Max z=CBXB+CNXN+0XS st.BXB+NXN+IXS=b，XB,XN,XS 0改写B-1存在Max z=CBXB+CNXN+0XS st.B-1BXB+B-1NXN+B-1I XS=B-1 bXB,XN,XS 0左乘B-1LP模型矩阵变换：|B|0，（XB+B-1NXN+B-1 XS=B-1 b）2024/7/25-第2章 对偶问题-21-单纯形法的矩阵描述：XBXNXSBNIINB-1bbXS XBCBCN0CBCN0=C-CB B-1 A00NSxjcjpj0pjjcjXB=b=B-1 bN=B-1 N N=CN-CBB-1 N 0CBS=-CB B-1 0初始表最终表A=B N I2024/7/25-第2章 对偶问题-22-（5）互补松弛性 n 若 y i*0,则 aij xj*=bi j=1 n 若 a ij xj*0,a ij xj*-bi=0,即 a ij xj*=bi 当 a ij xj*-bi mi 时，企业愿意购进这种资源，单位纯利为yi*mi，则有利可图；如果yi*mi 则购进资源i，可获单位纯利yi*mi 若yi*mi则转让资源i，可获单位纯利miyi单纯形表检验数单纯形表中的检验数与影子价格其中cj表示第j种产品的价格;表示生产该种产品所消耗的各项资源的影子价格的总和,即产品的隐含成本。当产值大于隐含成本时，即 ，表明生产该项产品有利，可在计划中安排；否则 ，用这些资源生产别的产品更有利，不在生产中安排该产品。2024/7/25402.5 对偶单纯形法对偶单纯形法在单纯形表中，在单纯形表中，列对应原问题的基可行解，列对应原问题的基可行解，行行对应对偶问题的一个对应对偶问题的一个基解基解（不一定可行），当（不一定可行），当 时，时，在检验数行就得到对偶问题的在检验数行就得到对偶问题的基可行解基可行解，此时两个问题的目，此时两个问题的目标函数值相等标函数值相等 ，由，由最优性条件最优性条件知，两个知，两个问题都达到了最优解。问题都达到了最优解。单纯形法：单纯形法：找一个初始基可行解，保持找一个初始基可行解，保持b列为正，通过迭代列为正，通过迭代找到下一个基可行解，使目标函数值不断增大，当找到下一个基可行解，使目标函数值不断增大，当检验数行检验数行全部小于等于零全部小于等于零时，达到最优解。时，达到最优解。41原问题基可行解原问题基可行解 最优解判断最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法对偶单纯形法基本思路基本思路单纯形法的基本思路：单纯形法的基本思路：对偶单纯形法是求解线性规划的另一个基本方法。它是根据对偶原理和单纯形法原理而设计出来的，因此称为对偶单纯形法。不要简单理解为是求解对偶问题的单纯形法。找出一个DP的可行基LP是否可行（XB 0）保持DP为可行解情况下转移到LP的另一个基本解最优解是否循环结束u根据对偶问题的对称性，保持对偶问题的解是可行解，即根据对偶问题的对称性，保持对偶问题的解是可行解，即检验数行非负，而原问题从非可行解开始，逐步迭代到基本检验数行非负，而原问题从非可行解开始，逐步迭代到基本可行解，也使原问题和对偶问题达到最优解。可行解，也使原问题和对偶问题达到最优解。2024/7/25-第2章 对偶问题-43-2.5 对偶单纯形法由于单纯表中同时反映原问题与对偶问题的最优解，故可以从求对偶问题最优解角度求解LP模型。例：min z=2x1+3x2 max z=-2x1-3x2+0 x3+0 x4 s.t x1+x23 标准化 s.t x1+x2-x3=3 x1+2x2 4 x1+2x2-x4=4 x10,x20 xj 0,(j=1,2,3,4)max z=-2x1-3x2+0 x3+0 x4 s.t -x1-x2+x3=-3 -x1-2x2+x4=-4 xj 0,(j=1,2,3,4)2024/7/25-第2章 对偶问题-44-Cj x1x2x3x4XBbCB-1 -1 1 0 -1 -2 0 1-2 -3 0 0-3-4x3 x400cj-zj-2-300-1/2 0 1 -1/2 1/2 1 0 -1/2x3 x2-1 2cj-zj-1/2 0 0 -3/2 0-31 0 -2 1 0 1 1 -1x1 x221cj-zj 0 0 -1 -1-2-3列单纯表计算：2024/7/25-第2章 对偶问题-45-对偶单纯形法步骤：1.列初始单纯形表，使得所有检验数j 0；2.出基变量：取min bi0=bl x(l)3.入基变量：min|alk0 选择y作入基变量，py=B-1 py=-0.5 1.5 2 0.25T 继续迭代：2024/7/25-第2章 对偶问题-70-cj 2 3 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 -8 2 x1 4 0 x6 -12 3 x2 60 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -1.5 -0.125 00 x3 -2 2 x1 4 0 x4 6 3 x2 30 0 1 0 -0.5 -0.5 1 0 0 0 0.25 0 0 0 0 1 -0.25 -0.5 0 1 0 0 0 0.25cjzj0 0 0 0 -0.5 -0.750 x5 4 2 x1 3 0 x6 7 3 x2 30 0 -2 0 1 1 1 0 0.5 0 0 -0.25 0 0 -0.5 1 0 -0.25 0 1 0 0 0 0.25cjzj0 0 -1 0 0 -0.25返回右端项变化分析单纯形表：2024/7/25-第2章 对偶问题-71-cj 2 5 0 0 0 0 CB XB b x1 x2 x3 x4 x5 x60 x3 0 2 x1 4 0 x6 4 5 x2 20 0 1 -1 -0.25 0 1 0 0 0 0.25 0 0 0 0 -2 0.5 1 0 1 0 0.5 -0.125 0cjzj0 0 0 -2.5 0.125 00 x3 2 2 x1 2 0 x5 8 5 x2 30 0 1 -2 0 0.5 1 0 0 1 0 -0.5 0 0 0 -4 1 2 0 1 0 0 0 0.25cjzj0 0 0 -2 0 -0.25返回Cj 变化分析单纯形表：2024/7/25-第2章 对偶问题-72-cj 2 3 0 0 0 0 5 CB XB b x1 x2 x3 x4 x5 x6 y0 x3 0 2 x1 4 0 x6 4 3 x2 20 0 1 -1 -0.25 0 -0.5 1 0 0 0 0.25 0 1.5 0 0 0 -2 0.5 1 2 0 1 0 0.5 -0.125 0 0.25cjzj0 0 0 -1.5 -0.125 0 1.250 x3 1 2 x1 1 5 y 2 3 x2 1.50 0 1 -1.5 -0.125 0.25 0 1 0 0 1.5 -0.125 -0.75 0 0 0 0 -1 0.25 0.5 1 0 1 0 0.75 -0.1875 -0.125 0cjzj0 0 0 -0.25 -0.4375 -0.625 0增加新产品（变量y）变化分析单纯形表：2024/7/25-第2章 对偶问题-73-2.7 参数线性规划 1.概念：研究目标函数值随某一参数变化的规律及最优解相应的变化。2.算法：先令变化量=0，当多个参数同时变化时，可以引入一个参数来表示这种变化。如：b列多个值发生变化时，可表示成 再考察随着的增加引起解的变化情况。3.最后，画出目标值随的变化所形成的曲线。2024/7/2574例：例：求解下述参数线性规划问题求解下述参数线性规划问题:解：解：求得求得 时最终单纯形表并将参数的变化填入表中时最终单纯形表并将参数的变化填入表中 ：0003101/20-1/50400-214/5301001/50002024/7/25752 2、是临界点，当是临界点，当 时，时，所以选择所以选择 作为进基变量，迭代一步得到：作为进基变量，迭代一步得到：000062010-2/501640010301001/50001 1、由表可知，当、由表可知，当 时，即时，即 最优解不变最优解不变 。目标函数值。目标函数值是：是：2024/7/25763 3、由上表可知，当、由上表可知，当 时，即时，即 最优解不变最优解不变 。目标函数值。目标函数值是是 4 4、是临界点，当是临界点，当 时，时，所以选择所以选择 作为进基变量，迭代一步得到：作为进基变量，迭代一步得到：0000122210001640010015050010002024/7/25775 5、由上表可知，当、由上表可知，当 时，最优解不再变化。时，最优解不再变化。目标函数值是目标函数值是 6 6、是临界点，当是临界点，当 时，时，所以选择所以选择 作为进基变量，迭代一步得到：作为进基变量，迭代一步得到：00041001/400500-5/25/412011/2-1/40000此时无论此时无论 如何增加，检验数始终为负，最优解不再变化。如何增加，检验数始终为负，最优解不再变化。目标函数值是目标函数值是 2024/7/25781524341-12-2-3342024/7/2579例：例：某文教用品厂利用原材料白坯纸生产原稿纸、日记本、某文教用品厂利用原材料白坯纸生产原稿纸、日记本、练习本三种产品，该厂现有工人练习本三种产品，该厂现有工人100100人，每天白坯纸供应量限人，每天白坯纸供应量限制是制是3 3万万kgkg，如果单独生产各种产品时，每人每天生产原稿纸，如果单独生产各种产品时，每人每天生产原稿纸3030捆、日记本捆、日记本3030打、练习本打、练习本3030箱。已知原材料消耗为每捆原箱。已知原材料消耗为每捆原稿纸用白坯纸稿纸用白坯纸 公斤，每打日记本用白坯纸公斤，每打日记本用白坯纸 公斤，公斤，每箱练习本用白坯纸每箱练习本用白坯纸 公斤。又知每捆原稿纸可盈利公斤。又知每捆原稿纸可盈利2 2元，每打笔记本盈利元，每打笔记本盈利3 3元，每箱练习本盈利元，每箱练习本盈利1 1元。试决定元。试决定（1 1）在现有生产条件下，工厂盈利最大的生产方案；）在现有生产条件下，工厂盈利最大的生产方案；（2 2）如果白坯纸的供应数量不变，当工人人数不足时可招收）如果白坯纸的供应数量不变，当工人人数不足时可招收临时工，其工资支出为每人每天临时工，其工资支出为每人每天4040元，问该厂要不要招收临元，问该厂要不要招收临时工，最多招多少？时工，最多招多少？2024/7/2580例：例：设该厂每天生产原稿纸、日记本、练习本的数量分别是设该厂每天生产原稿纸、日记本、练习本的数量分别是 ，表示招收临时工的数量。则有下列模表示招收临时工的数量。则有下列模 型：型：时，得现有条件下的最优生产计划，如下表。时，得现有条件下的最优生产计划，如下表。2024/7/25812310032000017/31/10-102100010-4/3-1/104000-10/3-1/10-50由表中可知，劳动力的影子价格是由表中可知，劳动力的影子价格是5050元元/人（人（4040），所以可），所以可以雇用工人扩大生产。将参数以雇用工人扩大生产。将参数 反映到最终表中，得：反映到最终表中，得：231003017/31/10-10210-4/3-1/104000-10/3-1/10-502024/7/2582要使得最优基不变，须要使得最优基不变，须 即即 ，当，当 时，时，最优基不变，最优解最优基不变，最优解 目标函数值目标函数值当当 时，时，利用对偶单纯形法迭代一步，得结果如下：利用对偶单纯形法迭代一步，得结果如下：2310000-1/10-7/301/100121483/1000-5-15-6/1002024/7/2583由上表可知，当由上表可知，当 时，最优解是时，最优解是目标函数值是目标函数值是 变化情况可见图。变化情况可见图。2001003002000100008000600040002024/7/25-第2章 对偶问题-84-例：有如下线性规划模型：max z=2x1+3x2 s.t x1+x23 x1+2x2 4+x10,x20（0）max z=2x1+3x2+0 x3+0 x4 s.t x1+x2+x3=3 x1+2x2+x4=4 xj 0,(j=1,2,3,4)（1）当=0 时的最优解；（2）当0时，z 值的变化规律。解：先令=0，有下述模型的标准形利用单纯形法求解：2024/7/25-第2章 对偶问题-85-Cj x1x2x3x4XBbCB1 1 1 0 1 2 0 12 3 0 034x3 x400cj-zj 23001/2 0 1 -1/2 1/2 1 0 1/2x3 x212cj-zj 1/2 0 0 -3/2031 0 2 -1 0 1 -1 1x1 x221cj-zj 0 0 -1 -123（=0）2024/7/25-第2章 对偶问题-86-Cj x1x2x3x4XBbCB2 3 0 02-1+x1 x223cj-zj-1 0 -2 1 1 1 1 0 x4 x2cj-zj-1 0 -3 0030 0 -1 -11 0 2 -1 0 1 -1 1（0 3）当0时，b=B-1b=B-1b(0 )T=(-)T，继续迭代如下：（对偶单纯形法）-2 3（3）其变化曲线如下：2024/7/25-第2章 对偶问题-87-Z()03792024/7/25-第2章 对偶问题-88-例：某大学教授利用部分业余时间从事咨询工作。现有三个A、B、C企业欲聘请，各自每小时的咨询费用分别为10，12，16元。教授每月可用于外出咨询的时间为40小时，但对每个企业而言，用于准备的时间与咨询所花的时间的比例分别为0.1，0.5，0.8，教授每月可用于准备的时间应不超过24小时。若假定三个企业每月要求的咨询时间可分别达到80，60，20小时。现问：教授应作何种决策，才能使收益最大？从目前看，教授有许多咨询机会，但可用的外出咨询时间及准备的时间有限，所以可考虑雇用助手（用于帮助准备），但要支付每小时4元的费用，现帮助教授分析一下，它是否该雇用助手，若需雇用，每月应雇用多少时间？2024/7/25-第2章 对偶问题-89-设 用于三个企业咨询的时间分别为Ax1，Bx2，Cx3，Max z=10 x1+12x2+16x3s.t.x1+x2+x340 0.1x1+0.5x2+0.8x324 x180 x2 60 x3 20 x10,x20,x30+-4