《运筹学研究生辅导课件》天津大学运筹学练习题整理.docx

例9 已知某线性规划问题用单纯形法迭代时，得到的中间某两步的单纯形表如表2.8。请将表中空白的数字填上。表2.8354000bx1x2x3x4x5x6(1)5x210000x505-100x60401Z0-400(2)5x24x33x1Z表2.9bx1x2x3x4x5x6x2010x3001x1100Z000例 16 某厂准备生产三种产品A,B,C,需消耗劳动力和原料两种资源，其有关数据如表2.15.表2.15.表 2.15 产品 单位消耗资源A B C资源限量劳动力原料6 3 53 4 545（单位）30（单位）单位利润3 1 5(1)用单纯形法确定总利润最大的生产计划.(2) 分别求出劳动力和原料的影子的价格.若原料不够,可到市场上购买,市场价格0.8问是否要购进,最多可购进多少?总利润增加多少?（3）当产品A,C的单位利润在何范围变化时，最优生产计划不变？（4）劳动力可减少多少而不改变原最优计划？解 (1) 该问题的线性规划模型为s.t.其中分别为产品A,B,C的产量.用单纯形法迭代的最优表如表2.16所示表 2.16 因而最优生产计划为生产A,B产品均为0，生产C产品可使利润最大，最大利润为30.(2)劳动力和原料的影子价格分别为0和1.这说明在企业最优安排中,劳动里资源没有用完(实际用了30个单元),而原料资源已耗尽.若原料市场价格0.8影子价格1,因此应适量购进原料扩大生产.设购进的原材料数为,为保持最优基不变,必须有,而=解得 因而最多可购进原料15单位，总利润增加.净利润增加15-0.815=3单位.（3）产品A()在最优方案中是非基变量，设变化为则当（为的检验数），即当时，原最优计划不变.产品在最优方案中是基变量,设变化为,要使最优计划不变,则所有非基变量检验数应非负,即即 因此当产品C的单位利润时，最优计划不变（4）设劳动力减少，即右边常数列变化为，为使最优计划不变，则即 所以 即劳动力可减少15单位，原最优计划不变.（实际上减去的是富余劳动力）.例1 某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为s1,s2,…s10,相应的钻探费用为c1,c2, …c10,并且井位选择上要满足下列限制条件：或选择s1和s7，或选择s8;选择了s3或s4就不能选s5,或反过来也一样；在s5，s6，s7，s8，中最多只能选两个。试建立这个问题的整数规划模型。例3某科研项目由三个小组用不同方法独立进行研究，它们失败的概率分别为0.40,0.60和0.80为了减少三个小组都失败的可能性,现决定暂派两名高级科学家参加这一科研项目,把这两个分配到各组后,各小组仍失败的概率如表4.4所示,问应如何分派这两各高级科学家以使三个小组都失败的概率最小?表4.4高级科学家人数小 组1230120.400.200.150.600.400.200.800.500.30解(1)建立动态规划模型按小组数将问题划分3个阶段,阶段变量状态变量表示第阶段初可用于分配的科学家数,决策变量表示第阶段分配给第个小组的高级科学家人数.状态转移方程:允许决策集合:阶段指标过程指标函数因而基本方程采用乘积形式,即(2)采用逆序法求解:当=3时,因为(即尚未分配给第1和第2小组的全部分配给第3小组).计算结果如表4.5所示.表4800.500.30当=2时,计算结果如表4.6所示.表4.60120.480.300.180.320.200.160020.480.30.0.16当时,计算结果如表4.7所示.表 4.7 s1x1=0x1=1x1=220.0640.0600.07210.060由表4.7可知x1*= 1 , = 0.060, 由s1= 1查表4.6可得x2*= 0 ; 由s3= 1查表4.5得x3*=1. 因而此问题的最优解为x1* = 1, x2*= 0 ，x3*= 1. 即把两名高级科学家分派到第1和第3两小组各一名，可使三个小组都失败的概率减小到0.060.注：此问题还有一种更简捷的解法，将它化为最短路模型.即将各阶段状态作为结点，各小组失败的概率为弧线上的数据，见图4.1.然后在图上用逆序法计算，计算结果标于图上的方框 内. 0.60 0.15 0.80 0.40 0.20