运筹学-对偶理论习题

1、第二章线性规划的对偶理论写出下列线性规划问题的对偶问题max z=2xi+2x24x3xi + 3x2+ 3x3 304xi + 2x2 + 4x3 0解:其对偶问题为解:其对偶问题为min w=30y i+ 80y 2yi+ 4y2 23yi + 2y2 23yi + 4y 2 4yi、y2 A 0写出下列线性规划问题的对偶问题min z=2xi+8x2 4x3xi + 3x23x3 30 xi + 5x2 + 4x3 = 804xi + 2x2 4x3 0, x3 无限制解:其对偶问题为解:其对偶问题为max w=30y i+80 y2+50 y3yi y2 + 4 y3 2 3yi+5y

2、2 + 2y3 & 83yi + 4y2 4y 3 = 4yi 0, y2 无限制，y302.3已知线性规划问题max z=xi+2x2+3x3+4x4xi + 2x2 + 2x3 +3x4 202xi + x2 + 3x3 +2x4 0其对偶问题的最优解为yi*=6/5, y2*=i/5。试用互补松弛定理求该线性规划问题的最优解。解：其对偶问题为min w=20y i+20y 2yi + 2y2 =i(i)2yi + y2 22(2)2yi +3y2 2”3(3)3yi +2y 2 )”4(4)yi、y20将yi*=6/5, y2*=1/5代入上述约束条件，得(1)、(2)为严格不等式；由互

3、补松弛定 理可以推得x；=0, x2*=0。又因yi*0, y2*0,故原问题的两个约束条件应取等式， 所以4*q*2x3 +3x4 = 20*3x3 +2x4 = 20解得x3* = x4* = 4。故原问题的最优解为X*= (0, 0, 4, 4) T2.4用对偶单纯形法求解下列线性规划min z=4xi+2x2+6x32xi +4x2 +8x3 244xi + x2 + 4x3 8x1、x2, x3 0解将问题改写成如下形式max ( z) = 4xi 2x2 6x32xi 4x2 8x3+ x4=244xi x2 4x3+x5 = 8xi、x2, x3, x4, x5 0显然，P4、p

4、5可以构成现成的单位基，此时，非基变量在目标函数中的系数全为负数，因此P4、P5构成的就是初始正侧基。整个问题的计算过程列在表27中。表27Cj一 4-2一 600bCbXbxix2x3x4x50 x4-2-4-8i0-240 x5-4-i-40i-8-z-4-2-60000-4/-2-2/-4-6/-i000-2x2i/2i2-i/4060 x5-7/20-2-i/4i-2-z-30-2-i/20-i200-3/(-7/2)0-2/-2(-i/2)/(-i/4)0-2X2-310-1/214-6X37/4011/8-1/24-z-1/200-1/4-1-32最后一个单纯形表中，已得到一个可行

5、的正侧解，因而得到问题的最优解为X*= (0, 4, 4) T最优值为z*=322.5设某线性规划问题的初始单纯形表和最优单纯形表分别为 表29 (初始单纯形表)Cj54300bCbXbX1X2X3X4X50X411110600X52140180-z543000表2 10 (最优单纯形表)Cj54300bCbXbX1X2X3X4X54X201-22-1405X1103-1120-z00-4-3-1-260现在要问：C3在什么范围内变化，表中最优解不变？C3从3变为8,求新的最优解解(1)由于在最优单纯形表中，C3为非基变量的价格系数，因此其变化仅会影 响到检验数 C3= 4 ,因此当 Ac3

6、d3=4时，表中最优解不变。(2)当C3从3变为8时，则表中的检验数 03从一4变为1 ,即表中的最优解将 发生变化，用单纯形法求解得到如表211中所示的新的最优解。表 2 11Cj54800bCbXbX1X2X3X4X54X201-22-1405X1103-1120-z001-3-1-2604X22/3104/3-1/3160/35X31/301-1/31/320/3-z00-4-3-1-740/3单位产品甲乙资源限量（kg）原材料A1390B2180C1145单位产品利润（千兀/件）54若XI、X2分别表示工厂生产甲、乙产品的数量，则使工厂获得最大利润的生产计划 数学模型为：即新的最优解为

7、X*= （0, 160/3, 20/3） T。2.6某工厂在计划期内要安排甲、乙两种产品，已知生产一件产品所消耗的B、C三种原材料的数量以及单位产品的利润如下表所示：表 212A、max z=5xi+4xA、X1 +3X2 & 902xi + x2 80 x1 + x2 0用单纯形法求解该问题时，其初始单纯形表和最优单纯形表分别如表2 13和314所示，试分析使最优基不变的b3的变化范围。表2 13 （初始单纯形表）Cj54000bCbXbx1x2x3x4x50 x313100900 x421010800 x51100145-z540000表2 14 （最优单纯形表）Cj54000bCbXbx

8、1x2x3x4x50 x30012-5255x11001-1354x2010-1210z000-1-3-215解 由表2 13和表214可知，当B= (p3, pi, 时，有1 2525B 1011B 1b 350 1 210当下式成立时，最优基不变。251250255 b3B 1b_ 1B b 35011035b3010012b310b3即25-5Ab30, 35他30, 10+ Ab30解不等式有-5 Ab30即安排生产产品丙是有利的。 一 一 .一 、一. . . .对应X3在最优单纯形表中的列向量为 TOC o 1-5 h z HYPERLINK l bookmark2 o Curre

9、nt Document 1 25 251 HYPERLINK l bookmark22 o Current Document B 1P10 11 43 HYPERLINK l bookmark24 o Current Document 01212代入到最优表214中，并用单纯形法迭代一次得新的最优表217。表 217Cj540008bCbXbX1X2X3X4X5X30X30012-55255X11001-13354X2010-12210-z000-1-31-2158X3001/52/5-1155X110-3/5-1/520204X2012/5-1/50020-z00-1/5-7/5-20-22

10、0由表2- 17,得最优解X = (20, 20, 5) T即该工厂生产产品甲、乙、丙分别为20, 20, 5件，可使工厂获得最大利润 220千元。2.8红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表218所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要 求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使 配备的售货人员的人数最少？（只建模型，不求解）表 218时间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：设X1为星期一开始上班的人数，X2为星期二开始上班的人数， X7星期日开始上班的人数。我们的目标是要求售货人员的总数最少。因为每个售货员都 工作五天，休息两天，所以我们只要计算出连续工作五天的售货人数，也就计算出 了售货员的总数。我们把连续工作五天的售货员按照开始工作的时间分成7类，各类的人数分别为X1, X2,，X7,即有 目标函数：min X1+X2+X3+X4+X5+X6+X7.我们再按照每天所需售货员的人数写出约束条件，例如星期日需要28人，我们知道商场中的全休售货员中除了星期一开始上班和星期二开始上班的人外都应该上 班，即有X3+X4+X5+X6+X728,这样我们就建立了如下的数学模型： 目标函数：min