运筹学习题

运筹学习题1．线性规划数学模型的结构及各要素的特征。2．什么是线性规划问题的标准型式，如何将一个非标准型的线性规划问题转化为标准型式。3．试说明线性规划问题的可行解、基解、基可行解、最优解的概念以及上述解之间的相互关系。4．如何从单纯形表上来判别该线性规划问题具有唯一最优解、无穷多个最优解、无界解或无可行解。5．判断下列说法是否正确：√（1）图解法同单纯形法虽然求解形式不同，但从几何上理解，两者是一致的；√（2）线性规划模型中增加一个约束条件，可行域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大；×（3）线性规划问题的每一个基可行解对应于可行域的一个顶点，如果线性规划问题存在最优解，则最优解一定对应可行域边界上的一个点；√（4）用单纯形法求解标准型式的线性规划问题时，检验数j0对应的非基变量xj都可以被选作为换入变量；×（5）在单纯形法计算中，选取最大正检验数k对应的变量xk作为换入变量，将使目标函值得到最快的增长；√（6）一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；×（7）线性规划问题的任一可行解都可以用全部基可行解的线性组合来表示；×（8）X1、X2分别是某线性规划问题的最优解，则X=1X1+2X2也是该线性规划问题的最优解，其中1、2为正的实数；×（9）有n个变量、m个约束条件的标准型线性规划问题，其可行域的顶点恰好为Cnm个。√（10）在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；√（11）任何线性规划问题存在并具有唯一的对偶问题；√（12）对偶问题的对偶问题一定是原问题；√（13）线性规划的原问题有无穷多个最优解，则其对偶问题也一定具有无穷多个最优解；√（14）已知yi*0为线性规划问题的对偶问题的最优解，若yi*0，则说明在最优生产计划中第i种资源已完全耗尽；×（15）已知yi*为线性规划问题的对偶问题的最优解，若yi*=0，则说明在最优生产计划中第i种资源一定有剩余；（参考下面的举例说明）×（16）若某种资源的影子价格等于k0，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k；（参考下面的举例说明）√（17）当用对偶单纯形算法求解线性规划时，若单纯形表中某一基变量xi0，又xi所在行的元素全部≥0，则可以判断出其对偶问题具有无界解；×（18）线性规划问题中的bi、cj值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况；√（19）在线性规划问题的最优解表中，如某一变量xj为非基变量，则在原问题中，无论改变它在目标函数中的系数cj或在各约束条件中相应的技术系数aij，反映到最终单纯形表中，除该列数字有变化外，将不会引起其他列数字的变化。（15）结论是错误的，现举例如下：0,,84164820,841648232max51524132121212121xxxxxxxxxxxxxxxxxZ利用单纯形法求解如下：CBXBbx1x2x3x4x50x38121000x416400100x580[4]001检验数230000x34[1]010-1/20x416400103x2201001/4检验数2000-3/42x141010-1/20x4000-41[2]3x2201001/4检验数00-201/42x141001/400x5000-21/213x22011/2-1/80检验数0-1-200即原问题的最优解为（x1，x2，x3，x4，x5）=（4，2，0，0，0），对偶问题的最优解应对应于原问题松弛变量x3，x4，x5的检验数，所以为：（y1，y2，y3）=（2，0，0）。此时y2=0，y3=0，其对应原问题最优解x1=4，x2=2，下的后两种资源已全部用完并无剩余。（16）结论是错误的，现举例如下：对于上述问题，最优解为x1=4，x2=2，第一种资源即机器台时的影子价格为y1=20，现在我们增加5个机器台时，则上述问题变成：0,,841641320,8416458232max51524132121212121xxxxxxxxxxxxxxxxxZ我们仍然利用单纯形算法求解此问题得如下表：CBXBbx1x2x3x4x50x313121000x416400100x580[4]001检验数230000x391010-1/20x416[4]00103x2201001/4检验数2000-3/40x35101-1/4-1/22x140001/403x2201001/4检验数000-1/2-3/4即原问题的最优解为（x1，x2，x3，x4，x5）=（4，2，5，0，0），最优目标函数值仍然为Z=2×4+3×3=14≠14+y1×5=14+2×5=24。(20)运输问题是一种特殊的线性规划模型,因而求解结果也可能出现下列情况之一：有唯一最优解、有无穷多最优解、无界解和无可行解；(×)(21)在运输问题中，只要给出一组含（m+n–1）个非负的{xij}，且满足axinjij1，bxjmiij1，就可以作为一个初始基可行解；(×)(22)表上作业法实质上就是求解运输问题的单纯形法；(√)(23)按最小元素法（或伏格尔法）给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路；(√)(24)如果运输问题的单位运价表的某一行（或某一列）元素分别乘上一个常数k，最优调运方案将不会发生变化；(×)(25)如果运输问题的单位运价表的某一行（或某一列）元素分别加上一个常数k，最优调运方案将不会发生变化；(√)(26)当所有产地产量和销地的销量均为整数时，用表上作业法求得的运输问题的最优解也为整数解。(√)二应用题：2.1已知某工厂计划生产I、II、III三种产品，各产品需要在A、B、C三种设备上加工，各有关数据见如下表，试回答：（1）如何充分发挥设备能力，使生产盈利最大？（2）若为了增加产量，可借用别的工厂的设备B，每月可借用60台时，租金为1.8万元，问借用设备B是否合算？（3）若另有两种新产品IV、V，其中IV需用设备A—12台时，B—5台时，C—10台时,单位产品盈利2.1千元；V需用设备A—4台时，B—4台时，C—12台时,单位产品盈利1.87千元。如果A、B、C三种设备台时不增加，分别回答这两种新产品投产在经济上是否合算？（4）若对产品工艺重新进行设计和结构改造，而改进后生产每件产品I需用设备A—9台时，设备B—12台时，设备C—4台时,单位产品盈利4.5千元，问这对原计划有何影响？IIIIII设备有效台时（每月）A8210300B1058400C21310420单位产品利润（千元）322.9解：设每月生产产品I、II、III的数量分别为x1、x2、x3。依题意，本问题的线性规划模型为：0,,42010132400851030010289.223max321321321321321xxxxxxxxxxxxxxxZ0,,42010132400851030010289.223max61632153214321321xxxxxxxxxxxxxxxxxZ（1）利用单纯形法求解如下：CBXBbx1x2x3x4x5x60x4300[8]2101000x540010580100x642021310001检验数322.90003x137.510.251.250.125000x5250[2.5]-4.5-1.25100x6345012.57.5-0.2501检验数01.25-0.85-0.375003x135101.70.25-0.102x21001-1.8-0.50.400x622000[30]6-51检验数001.40.25-0.503x1338/15100-9/10011/60-17/3002x2116/5010-7/501/103/502.9x322/30011/5-1/61/30检验数000-3/100-4/15-7/150即原问题的最优解为（x1，x2，x3，x4，x5）=（338/15，116/5，22/3，0，0）。目标函数的最优值为：Z=3×338/15+2×116/5+2.9×22/3=135.27（千元）。对偶问题的最优解应对应于原问题松弛变量x4，x5，x6的检验数，所以为：（y1，y2，y3）=（3/100，4/15，7/150）。（2）算得：对偶单纯形算法进行计用式，并利最优解表改造成如下形的出现负分量，将原问题这时，bbBbBbB38514615503,10611060030161515031015073001760111009111CBXBbx1x2x3x4x5x63x1503/15100-9/10011/60-17/3002x2146/5010-7/501/103/502.9x3-8/30011/5[-1/6]1/30检验数000-3/100-4/15-7/1503x1153/51011/1013/1000-1/502x2138/5013/5-1/5002/250x51600-6-6/51-1/5检验数00-8/5-7/200-1/10这时的最优解为：（x1，x2，x3，x4，x5）=（153/5，138/5，0，0，16）。目标函数的最优值为：Z=3×153/5+2×138/5=147，147-18=129135.27（千元）；故这时借用设备B不合算。（3）假设新增两种新产品IV、V，他们的数量分别为x4/，x5/，它们的技术向量为：3016151503101507300176011100987.11.21244105121/5/4/5/4BccPP012.0300377513187.115/825/14150/469.22387.1006.016.21.230/5750/29100/739.2231.215/825/14150/46124430/16/15/150/310/150/7300/1760/11100/930/5750/29100/731051230/16/15/150/310/150/7300/1760/11100/9/51/5/5/41/4/4/51/41PBCcPBCcPBPBTBTB0/4由于，增加第IV种新产品的生产不会使总利润增加，因此，在经济上是不合算的；又0/5由于，在原问题最优单纯形表中增加一列得下表：CBXBbx1x2x3x4x5x6x5/3x1338/15100-9/10011/60-17/300-23/752x2116/5010-7/501/103/5014/252.9x322/30011/5-1/61/30[8/15]检验数000-3/100-4/15-7/15037/300CBXBbx1x2x3x4x5x6x5/3x1107/41023/401/407/80-3/8002x231/201-21/20-119/16011/401/4001.87x5/55/40015/83/8-5/161/161检验数00-37/160-61/800-73/320-87/16000这时的最优解为：（x1，x2，x3，x4，x5，x6，x5/）=（107/4，31/2，0，0，0，0，55