最全的运筹学复习题及答案

四、将下列线性规划问题转化为标准形式：2、minZ=2x1-x2 2x3五、根据每个题目的要求。线性规划数学模型的建立1.一个工厂生产三种产品，甲、乙、丙，以及每种产品的原材料消耗、机器小时消耗和这些资源的限制。单位产品利润如下表所示：根据客户订单，三种产品的最低月需求量分别为200件、250件和100件，最大月销售量分别为250件、280件和120件。月销售额分别为250件、280件和120件。询问如何安排生产计划以最大化总利润。2.一个建筑工地有一批长度为10米的同类型钢筋。今天，90根3米长的钢筋和60根4米长的钢筋将被切断。如何切断钢筋以节约原材料？1.运输公司需要在春节期间一天24小时加班。所需人员数量如下表所示：出发时间服务员数量2-66-1010-1414-18岁18-2222-248107124每个工作人员连续工作八小时，并在周期开始时开始工作。如何安排它，以满足上述要求，并尽量减少去工作的人数？5.下列线性规划问题分别用图解法和单纯形法求解。指出单纯形迭代的每一步都对应于图解法可行域中的哪个顶点。六、单纯形法用于解决下列线性规划问题：七、用大M法解决下列线性规划问题。并指出问题的解决方法。下表是使用单纯形法时某一步骤的表格。已知线性规划的目标函数是maxZ=5x1 3x2，约束形式是“”，X3和X4是松弛变量。将表中的解代入目标函数后，Z=10特大号X2X3X410b-1fgX32CO11/5特大号ade01(1)在表中找出A G的值(2)表中给出的解是最优解吗？(1)a=2b=0c=0d=1)a=2b=0 c=0d=1 e=4/5 f=0g=-5(2 2)表中给出的解是最佳解第四章线性规划的对偶理论5.写出下列线性规划问题的对偶问题1.minZ=2x1 2x2 4x3六、已知的线性规划问题应用对偶理论证明问题最优解的目标函数值不大于25七、已知的线性规划问题maxZ=2x1 x2 5x3 6x4对偶问题的最优解是YL 4和Y2 1。利用对偶问题的性质，试图找到原问题的最优解。七、对偶单纯形法用于解决下列线性规划问题：八、已知的线性规划问题(1)写出它的对偶问题(2)已知原问题的最优解是x u t=(2，2，4，0) T。尝试直接根据对偶理论找到对偶问题的最优解。W*=16第七章整数规划一、填空1.用分枝定界法求解最大化整数规划问题时，任何可行解的目标函数值都是问题目标函数值的下界。2.在分支定界法中，如果选择XR=4/3进行分支，结构的约束条件应为X11且X12。3.如果整数规划问题P0是已知的，其相应的松弛问题被表示为P0，如果问题P0没有可行解，那么问题P0就没有可行解。4.在0-1整数规划中，变量值可以是_0或1。5.对于一个有n个任务需要n个人来完成的指派问题，解中值为1的变量个数是n。6.分枝定界法和截平面法都是基于求解整数规划的线性规划方法。7.如果在X1所在的行中得到X11/7x3 2/7x5=13/7，则以x1为源行的行的截平面方程为_-x3-X5 0 _。8.当用截平面法求解整数规划问题时，所有变量必须是整数。9.当使用截平面法求解整数规划问题时，如果约束条件中有非整数的系数，则应在约束的两端展开适当的倍数，以转换所有系数12.当匈牙利法用于解决分配问题时，最终的分配元素应该是独立的零元素。13.分支定界法通常一次有两个分支。第二，单一主题1.在整数规划问题中，变量值可以是dA.整数b.0或1c。大于零的非整数d。这三者都是可能的2.在下面的整数规划问题中，分枝定界法和截平面法都可以采用aA.纯整数规划b .混合整数规划c.0-1规划d .线性规划3.下面的方法被用来解决分配问题D_。A.单纯形表b .分支定界法c .表运算法d .匈牙利法三、多种选择1.以下解释对美国广播公司来说是不正确的。A.整数规划可以通过求解其相应的松弛问题，然后舍入其非整数值解来获得整数解。分枝定界法用于求解最大化整数规划问题。当得到一个以上可行解时，通常取其中一个作为下界。当用割平面法求解整数规划时，构造的割平面可能会切掉一些不属于最优解的整数解。当用截平面法求解整数规划问题时，必须先将原问题的非整数约束系数和右常数转化为整数。2.解决整数规划问题时，可能会出现基本知识。A.唯一最优解b .没有可行解c .多重最优解d .无限多重最优解3.以下关于分配的陈述是正确的。A.指派问题是一个高度退化的运输问题b。指派问题可以通过表运算c来解决。指派问题的最小元素可以从效益矩阵中逐行取出，以获得指派问题，该指派问题可以通过最佳指派方案d .匈牙利方法来解决，该方法要求一个人只能完成一项工作，同时只有一个人可以做一项工作。4.整数规划类型包括(CDE)线性规划，非线性规划，纯整数规划，混合整数规划，e 0-1规划5.对于某种整数规划来说，可能涉及到的解决问题的内容是(ABCDE)为了找到它的松弛问题b，在它的松弛问题c上加一个约束方程c，用单纯形法或图解法切断一部分非整数解e，以便多次切断三。名词1.纯整数规划：如果所有的决策变量都需要取整数，这样的问题就变成了纯整数规划问题。2.0-1规划问题：在线性规划问题中，如果所有的决策变量都要求为0或1，这样的问题称为0-1规划。3.混合整数规划：在线性规划问题中，如果一些决策变量需要取整数，这个问题称为混合整数规划。4.分支定界法用于解决以下整数规划问题：(提示：可以用图解法)maxZ=40x1 90x25.用切面法求解六、下列整数规划问题它说明了整数规划的可行解是否可以通过先求解相应的线性规划问题然后取整来获得。答：不考虑整数约束，求解相应线性规划的最优解是x1=10/3，x2=x3=0。当使用四乘五方法时，x1=3，x2=x3=0，其中第二个约束不能满足，因此这是不可行的。第七，如果钻井队想从以下10个备选井位中确定5口钻井勘探井。将钻井总成本降至最低。如果10个井位的代码是S2 S1，S10，相应的钻井费用是C1、C2、C10，井位的选择应满足以下限制：(1)最多只能选择s1、s2和S4中的两个；(2)选择S5和s6中的至少一个；(3)选择s3、s6、S7和S8中的至少两个；尝试为这个问题建立一个整数规划模型八、有四项任务需要四个人完成：甲、乙、丙、丁。每项任务只允许一个人完成。每个人只完成了一项任务。众所周知，每个人都按照以下时间表完成了每项任务。问：为了最大限度地减少总的时间消耗，每个人都应该完成哪项任务？工作人iABC钟声151961918237212l22162324181917第二章线性规划问题的基本概念3.本章典型案例分析示例：单纯形法解决方案：首先更改为标准形式：将标准表格中的系数列成表格。基础SX1X2X3X4解决办法S1-20-15岁000X302310600X402101400第一次迭代：调入x1，调出x4基础SX1X2X3X4解决办法S10-50104000X30021-1200X1011/201/2200第二次迭代：调用x2，调用x3基础SX1X2X3X4解决办法S1005/215/24500X20011/2-1/2100X1010-1/43/41504.本章的家庭作业参见本章练习题。3.本章典型案例分析例：写出下列线性规划问题的对偶问题解决方案：双重问题是：4.本章的家庭作业参见本章练习题。第二，写出下列线性规划问题的对偶问题：s.t .(1)s.t .(2)管理运营研究综述首先，考虑以下线性规划(20分)MaxZ=2X1 3X22X1 2X2 X3=12X1 2X2 X4=84X1 X5=164X2 X6=12Xj0(j=1，2，6)最佳单纯形表如下：基本变量X1X2X3X4X5X6X30001-1-1/40X1410001/40X64000-21/21X220101/2-1/80j000-3/2-1/801)当C2=5时，找到一个新的最优解2)当b3=4时，找到新的最优解3)当添加约束条件2X1 X212时，询问最优解是否已经改变，如果是，询问新的解？当C2=5时4=-5/2 5=1/8 0，因此最优解发生变化基本变量X1X2X3X4X5X60X30001-1-1/402X1410001/400X64000-21/215X220101/2-1/80j000-5/21/800X32001-201/22X1210010-1/20X58000-4125X23010001/4j000-20-1/4最优解是X1=2，x2=3，z=192)当b3=4时基本变量X1X2X3X4X5X60X33001-1-1/402X1110001/400X6-3000-21/213X25/20101/2-1/80j000-3/2-1/800X39/20010-1/212X1110001/400X43/20001-1/4-1/23X27/4010001/4j0000-1/2-3/4最优解是X1=1，x2=7/4，z=29/43)添加约束条件基本变量X1