运筹学练习参考答案.doc

线性规划问题 1、某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表：IIIIII设备能力（台时）ABC1102142156100600300单位利润（元）1064（1） 求获利最大的产品生产计划；（2） 产品III每件的利润增加到多大时才值得安排生产；（3） 如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：用单纯形法求上述线性规划问题。化为标准形式：1064000b0100111100100060010450106003002260011500106400004000.60.51-0.10200/3106010.40.500.10150018001.250-0.21150-60002-10-106200/3015/65/3-1/6010100/3101/6-2/31/600100004-201-2200/300-8/3-10/3-2/30所以最优解为x* =(100/3，200/3，0，0，0，100)T，即产品I、II、III的产量分别为：100/3，200/3，0；最优解目标函数值z* =2200/3（2）设产品III每件的利润为c3产品III每件的利润增加到20/3时才值得安排生产。（3）设x7为新产品的产量。10640008b6200/3015/65/3-1/601200/310100/3101/6-2/31/600-0100004-2011100-2200/300-8/3-10/3-2/3028200/3015/65/3-1/60110100/3101/6-2/31/6000100/30-119/6-11/31/610-2600/30-2-13/3-20/3-1/300所以最优解为x* =(100/3，0，0，0，0，200/3)T，即产品I的产量：100/3，新产品的产量：200/3；最优解目标函数值z* =2600/32、已知下列线性规划问题： 求：（1）用单纯形法求解，并指出问题属于哪一类解； （2）写出该问题的对偶问题，并求出对偶问题的最优解；解：（1）将原问题划为标准形得：6-33000b060311100200202-24010100603-330012006-3300003004-51-3/2015/26101-1201/20-03006-90-3/215-6003-90-300100011-1/2-2/3615101/201/41/6-3501-3/20-1/41/6-7500-9/20-9/4-1/2最优解为x* =(15，5，0，10，0，0)T 最优解目标函数值z* =75非基变量的检验数0, 为唯一最优解.（2）该问题的对偶问题为：对偶问题的最优解：y* =(0，9/4，1/2)3、已知线性规划问题： 求：（1）用图解法求解； （2）写出其对偶问题； （3）根据互补松弛定理，写出对偶问题的最优解。解：（1）图解法由上图可知：在B(2,4)处，目标函数达到最大值。即最优解为x*=(2,4)T 最优解目标函数值z*=10 为唯一最优解（2）该问题的对偶问题为：（3）原问题的最优解x*=(2,4)T代入约束条件，可知约束条件取等式，因为x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，即对偶问题的最优解及最优目标函数值为：运输问题1、某产品有三个产地、四个销地，各产地的产量、各销地的销量以及产地到销地之间的单位运价见下表： 销地产地B1B2B3B4产量A141241116A22103910A38511622销量8141214（1）用表上作业法求该运输问题的最优调运方案。（15分）（2）该问题是否有多个最优调运方案？若没有，说明为什么；若有，请再求出一个最优调运方案来。（5分）解：（1）先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。求初始基可行解（Vogel法）销地产地B1B2B3B4产量差额A1412124411160 0 0 7 0A28210329101 1 1 6 0A381451186221 2销量8141214差额2225111133222 初始解为：x13=12, x14=4, x21=8, x24=2, x32=14, x34=8，其余变量为0；相应的目标函数值 z= 412+114+28+92+514+68= 244最优性检验（位势法）根据基变量的检验数为0，即sij= cij ui vj =0s13= c13 u1 v3 = 4 u1 v3 =0 s14= c14 u1 v4 = 11 u1 v4 =0s21= c21 u2 v1 = 2 u2 v1 =0 s24= c24 u2 v4 = 9 u2 v4 =0s32= c32 u3 v2 = 5 u3 v2 =0 s34= c34 u3 v4 = 6 u3 v4 =0u1 =0 易得：u2= 2，u3= 5，v1=4，v2=10，v3=4，v4=11计算非基变量的检验数：s11= c11 u1 v1 = 4 0 4=0 s12= c12 u1 v2 = 12 0 10=2s22= c22 u2 v2 = 10 (2) 10=2 s23= c23 u2 v3 = 3 (2) 4=1s31= c31 u3 v1 = 8 (5) 4=9 s33= c33 u3 v3 = 11 (5) 4=12所有非基变量xij的检验数sij0，即得最优解。最优解为：x*13=12, x*14=4, x*21=8, x*24=2, x*32=14, x*34=8，其余变量为0；最优目标函数值 z* = 244（2）因为非基变量x11的检验数s11=0，所以该问题有多个最优调运方案。从非基变量x11出发找一条闭回路（见下表）： 销地产地B1B2B3B4产量A1(+)412124(-)41116A282(-)10329 (+)10A38145118622销量8141214闭回路调整后得到另一最优解：销地产地B1B2B3B4产量A144121241116A2421036910A38145118622销量8141214即最优解为：x*11=4, x*13=12, x*21=4, x*24=6, x*32=14, x*34=8，其余变量为02、一个运输网络有4个发点和4 个收点，发点的发量，收点的收量与单位运价如下表所示 B1B2B3B4供应量A120801020100A210252050200A320302040100A440201030100需求量15050100100求使总运费最小的运输方案。解：产量销量，假想一个销地B5，销量为100先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。求初始基可行解（Vogel法）销地产地B1B2B3B4B5供应量差额A1208001010020010010 10 10A21501050252050020010 10 10 10 5 0 0A3200302040100010020 0 0 0 10 0 0A4400201001030010010 10 10 10 10 0 需求量15050100100100差额101010105555555000101010100初始解x13=0, x14=100, x21=150, x22=50, x32=0, x35=100, x42=0, x43=100,其余变量为0最优性检验（位势法）：根据基变量的检验数为0，即sij= cij ui vj =0s13= c13 u1 v3 = 10 u1 v3 =0 s14= c14 u1 v4 = 20 u1 v4 =0s21= c21 u2 v1 = 10 u2 v1 =0 s22= c22 u2 v2 = 25 u2 v2 =0s32= c32 u3 v2 = 30 u3 v2 =0 s35= c35 u3 v5 = 0 u3 v5 =0s42= c42 u4 v2 = 20 u4 v2 =0 s43= c43 u4 v3 = 10 u4 v3 =0u1 =0 易得：u2= 5，u3= 10，u4= 0，v1=5，v2=20，v3=10，v4=20，v5= -10计算非基变量的检验数：s11= c11 u1 v1 = 20 0 5=15 s12= c12 u1 v2 = 80 0 20=60s15= c15 u1 v5 = 0 0 (-10)=10 s23= c23 u2 v3 = 20 510=5s24= c24 u2 v4 = 50 5 20 =25 s25= c25 u2 v5 = 0 5 (-10) =5s31= c31 u3 v1 = 20 10 5 =5 s33= c33 u3 v3 = 20 10 10 =0s34= c34 u3 v4 = 40 10 20 =10 s41= c41 u4 v1 = 40 0 5 =35s44= c44 u4 v4 = 30 0 20=10 s45= c45 u4 v5 = 0 0 (-10)=10所有非基变量xij的检验数sij0，即得最优解。最优解为：x*13=0, x*14=100, x*21=150, x*22=50, x*32=0, x*35=100, x*42=0, x*43=100,其余变量为0；最优目标函数值 z* = 5750目标规划某工厂计划生产A、B两种产品，需要消耗甲、乙、丙三种资源、单位产品利润及资源限量如表所示： 产品资源AB资源限制甲21140乙1060丙01100产品利润（元/件）3012该厂的经营目标是：首先要求总利润必须超过2500元；然后考虑到产品受市场影响，为避免积压，A、B的产量不超过60件和100 件；由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型。解：设x1，x2 为产品A、B产量，以产品 A、B 的单件利润比 2.5：1 为权系数，目标规划模型如下：整数规划1、在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用见下表，假定每一项已经批准的工程要在整个3年内完成，目标是要选出使总收入达到最大的那些工程，试将这个问题表示成0-1整数规划模型。工程费用（千元）收入（千元）第一年第二年第三年15182024710403392204741155861030最大可用资金（千元）252525-解：设该问题的0-1整数规划模型为：2、分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。（10分） (表中单位：小时)任务人数A B C D E甲乙丙丁戊25 28 31 41 3840 38 26 26 33 35 27 28 40 32 24 42 37 23 45 30 29 26 20 32已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。 解：若不可能完成任务，则效率矩阵相应的元素为M，变换效率矩阵：得到初始分配方案：因为独立0元素个数m=4，不等于矩阵的阶数n=5，转入下步。 此时独立0元素个数有5个，得到最优解，相应的解矩阵为：即分配方案为：甲A，乙E，丙B，丁C，戊D，总时间为：25+33+27+37+20=142小时3、有五个车队将分赴五个地区，各车队去各地区的收入如下表： 地区 纯收入车队B1 B2 B3 B4 B5A1A2A3A4A5 9 4 6 8 5 8 5 9 10 6 9 7 3 5 8 4 8 6 9 5 10 5 3 6 8每个车队去一个地区，每个地区有一个车队去。求使总收入最大的指派方案。解：非标准型指派问题（极大化问题）先转换，变换效率矩阵：得到初始分配方案：因为独立0元素个数m=4，不等于矩阵的阶数n=5，转入下步。此时独立0元素个数有5个，得到最优解，相应的解矩阵为： 即分配方案为：A1B4，A2B3，A3B5，A4B2，A5B1 总收入为：8+9+8+8+10=4312