运筹学练习题.doc

一、选择1、若某线性规划问题存在基可行解，则该问题（ C ）。A一定有最优解 B具有无界解 C有非空的可行域 D可能无可行解2、关于线性规划，（ B ）是错误的。 A当最优解多于一个时，最优解必有无穷多个 B当有可行解时必有最优解C当有最优解时必能在可行域的某顶点达到 D当有可行解时必有基可行解 3、互为对偶的两个问题的解存在关系有（ D ）。A原问题无可行解，对偶问题一定无可行解 B原问题有无界解，对偶问题可能有可行解C原问题有最优解，对偶问题可能没有最优解 D原问题无界解，对偶问题一定无可行解4、用表上作业法求解3个产地4个销地的运输问题，若某步求得空格的检验数为，下列说法中正确的是（ A ）。A增加空格处的运输量将使总成本降低 B当前方案是最优运输方案C由至的运输量增加1个单位，可使总运费增加2 D为使总运费更小，应使至的运输量减少2二、填空题1、对偶单纯形法求解最大化线性规划问题时，要求初始单纯形表中的检验数都 小于等于零 。2、在运输问题中，当总供应量S小于总需求量R时，求解时需虚设一个供应量等于 （R-S）的虚拟供应点。3、某钻井队要从编号为1、2、3、4、5的五个井位中选择若干钻井探油，则“要么选择钻井2，要么选择钻井5” 可用的线性表达式表示为（x2+x5=1），其中选择第号钻井时，否则，。4、下图给出某城市部分道路的分布情况，现要沿道路铺埋输水管，为了使铺设的管线最短，要求按道路分布图的最小支撑树来设计管线，则所铺设管线的最小总长度应该是(11 )（单位km）。一、 某厂计划生产甲、乙两种产品，需在A、B两种设备上加工，并消耗一定的原料资源，单位产品所需资源等相关数据如下表设备A设备B原料单位利润（万元）产品甲0612产品乙5211资源限量152451、应如何安排生产使该工厂获利最多？建立该问题的线性规划模型，并写出其对偶问题；2、用单纯形法确定使总利润最大的生产计划，并求出最高总利润；解：1、设甲、乙两种产品的产量分别为，建立线性规划模型 设对偶变量为，则原问题的对偶问题为 2、引入变量，得原问题的标准形式 2单纯形法求解21000CBXBbx1x2x3x4x50x315051000x4246201040x55110015210000x3150510032x1411/301/60120x5102/301/613/201/301/300x315/20015/415/22x17/21001/41/21x23/20101/43/20001/41/2 二、某房地产公司计划在一个住宅小区建设5栋不同类型的楼房,，由四家建筑公司进行投标。经过投标得出建筑公司对新楼的预算费用如上表所示。试确定最优分派方案，使房地产公司支付的总费用最少，其中规定每家建筑公司要承建12栋楼房。二、 建筑公司 楼房A1A2A3A4B19437B24656B35475B47523B510674三、解析题友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。这三种作物每亩所施化肥分别为0.12吨、0.20吨、0.15吨。预计秋后玉米每亩可收获500公斤，售价为0.24元/公斤，大豆每亩可收获200公斤，售价为1.20元/公斤，小麦每亩可收获300公斤，售价为0.70元/公斤。农场年初规划时需要按优先级别考虑：年终收益尽可能达到350万元；：希望总产量不低于1250万公斤；：由于销量原因，小麦产量以500万公斤为宜；：农场现能提供5000吨化肥，若不够，可在市场高价购买，但希望高价采购数量愈少愈好。试对该农场的种植计划建立线性目标规划模型。解：设种植玉米亩，大豆亩，小麦亩，建立模型为备注 建立模型时单位没有统一的每处扣1分。 四、最短路问题四、1、用Dijkstra标号算法求右图中到其它各点的最短路，并给出最短路长。2、用Dijkstra标号算法求右图中到其它各点的最短路，并给出最短路长。五、计算：知下述线性规划问题 （ 1 ）用单纯形法求解此问题；（ 2 ）当约束条件的右端常数由20变为30时，最优解如何变化？（ 3 ）目标函数中的变量x3的系数由13变为8时，最优解如何变化？解：(1) 首先，写出其标准型为： （2分）据此列出初始单纯形表，如表一：（5分）表一551300iCBXBbx1x2x3x4x50x420-1131020/30x59012410019j551300 表一中非基变量x1,x2,x3的检验数均为正数，因此当前解不是最优解。选取x3为入基变量，x4为出基变量，迭代结果如表二所示（7分）表二551300iCBXBbx1x2x3x4x513x320/3-1/31/311/300x570/346/32/30-10/3135/23j-260/328/32/30-13/30表二中仍有正的检验数，选x1为入基变量，x5为出基变量，再次迭代，结果如表三所示（9分）表三551300iCBXBbx1x2x3x4x513x3165/2308/2316/231/46165/85x135/2311/230-5/233/4635j-2320/2306/230-53/23-14/23同理，表三中的解仍不是最优解，选取x2为入基变量，x3为出基变量，再次迭代，得最终单纯形表（表四）（11分）表四551300iCBXBbx1x2x3x4x55x2165/80123/83/41/165x15/810-1/8-1/41/16j-425/400-3/4-5/2-5/8（11分）表四中所有非基变量的检验数均小于零，所以得到唯一最优解，最优解为： ，最优值Z*=106.25。（13分）(2)当b1由20增加为30时，因 则有， 解中出现负值，需要用对偶单纯形方法迭代求解。将其替换到最优单纯形表中（表四），得到表五，求解过程如表五-表七所示：表五551300iCBXBbx1x2x3x4x55x2225/80123/83/41/165x1-15/810-1/8-1/41/16j-425/400-3/4-5/2-5/8表六551300iCBXBbx1x2x3x4x55x2-152310-53/213x315-8012-1/2j-120-600-1-1表七551300iCBXBbx1x2x3x4x50x43-23/5-1/501-3/1013x396/52/5101/10j-117-53/5-1/500-13/10新的最优解为 ，目标函数最优值为117。（6分）(2) 当目标函数中x3的系数由13减为8时，由于在最终单纯形表（表四）中，x3为非基变量，因此，c3的变化仅影响它自身检验数的计算，且有： ，因此，最优解和最优值均保持不变。（6分）六、计算题某企业需要指派甲、乙、丙、丁、戊五个人去做A、B、C、D、E五项不同的工作，要求每人只承担一项工作，每项工作只能由一人来完成，每人做各项工作所消耗的时间如下表，表中单位为小时，试用匈牙利法求使总消耗时间最短的任务分配方案。ABCDE甲382103乙87297丙64275丁84235戊9106910【解】（1）变换效率矩阵cij：每行和每列减去相应的最小值，具体过程如下：（3分） （2）进行试指派：（6分）在bij中，寻找不在同一行、不在同一列的独立零元素，结果为：，可见，独立零元素的个数m=4n=5，因此当前解不是最优解，需要对效率矩阵bij进一步地变换。（3）调整（10分）(a) 打勾、划线 ，覆盖所有零元素的最少直线数目l=4=mn。(b) 调整：在上面矩阵中，所有没有被线划到的元素