2023年最全的运筹学复习题及超详细解析超详细解析答案.pdf

四、把下列线性规划问题化成标准形式：2、minZ=2x1-x2+2x3 五、按各题要求。建立线性规划数学模型 1、某工厂生产 A、B、C三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位产品的利润如下表所示：根据客户订货，三种产品的最低月需要量分别为 200，250 和 100 件，最大月销售量分别为 250，280和 120 件。月销售分别为 250，280 和 120 件。问如何安排生产计划，使总利润最大。2、某建筑工地有一批长度为 10 米的相同型号的钢筋，今要截成长度为 3 米的钢筋 90 根，长度为 4 米的钢筋 60 根，问怎样下料，才能使所使用的原材料最省?1 某运输公司在春运期间需要24 小时昼夜加班工作，需要的人员数量如下表所示：起运时间 服务员数 26 610 10一14 1418 1822 222 4 8 10 7 12 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少?五、分别用图解法和单纯形法求解下列线性规划问题 并对照指出单纯形迭代的每一步相当于图解法可行域中的哪一个顶点。六、用单纯形法求解下列线性规划问题：七、用大 M法求解下列线性规划问题。并指出问题的解属于哪一类。八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 maxZ=5x1+3x2，约束形式为“”，X3，X4为松驰变量表中解代入目标函数后得 Z=10 Xl X2 X3 X4 10 b-1 f g X3 2 C O 1 15 Xl a d e 0 1(1)求表中 ag 的值 (2)表中给出的解是否为最优解?（1）a=2 b=0 c=0 d=1 e=4/5 f=0 g=5 （2）表中给出的解为最优解 第四章 线性规划的对偶理论 五、写出下列线性规划问题的对偶问题 1minZ=2x1+2x2+4x3 六、已知线性规划问题 应用对偶理论证明该问题最优解的目标函数值不大于25 七、已知线性规划问题 maxZ=2x1+x2+5x3+6x4 其对偶问题的最优解为 Yl=4，Y2=1，试应用对偶问题的性质求原问题的最优解。七、用对偶单纯形法求解下列线性规划问题：八、已知线性规划问题 (1)写出其对偶问题 (2)已知原问题最优解为 X=(2，2，4，0)T，试根据对偶理论，直接求出对偶问题的最优解。W*=16 第七章 整数规划 一、填空题 1 用分枝定界法求极大化的整数规划问题时，任何一个可行解的目标函数值是该问题目标函数值的下界。2在分枝定界法中，若选 Xr=43 进行分支，则构造的约束条件应为 X11，X12。3已知整数规划问题 P0，其相应的松驰问题记为 P0，若问题 P0无可行解，则问题 P。无可行解。4在 0-1 整数规划中变量的取值可能是_0 或 1。5对于一个有 n 项任务需要有 n 个人去完成的分配问题，其 解中取值为 1 的变量数为 n 个。6分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。7若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由 X。所在行得 X1+17x3+27x5=137，则以 X1行为源行的割平面方程为_7671X372X50_。8在用割平面法求解整数规划问题时，要求全部变量必须都为整数。9用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适当倍数，将全部系数化为整数。10求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法 _。11求解 01 整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。12 在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。13.分枝定界法一般每次分枝数量为 2 个.二、单选题 1 整数规划问题中，变量的取值可能是 D。A整数 B0 或 1C大于零的非整数 D以上三种都可能 2 在下列整数规划问题中，分枝定界法和割平面法都可以采用的是A。A纯整数规划 B混合整数规划 C01 规划 D线性规划 3 下列方法中用于求解分配问题的是 D_。A单纯形表 B分枝定界法 C表上作业法 D匈牙利法 三、多项选择 1下列说明不正确的是 ABC。A 求解整数规划可以采用求解其相应的松驰问题，然后对其非整数值的解四舍五入的方法得到整数解。B 用分枝定界法求解一个极大化的整数规划问题，当得到多于一个可行解时，通常任取其中一个作为下界。C用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。2在求解整数规划问题时，可能出现的是 ABC。A唯一最优解 B无可行解 C多重最佳解 D无穷多个最优解 3关于分配问题的下列说法正确的是_ ABD。A分配问题是一个高度退化的运输问题 B可以用表上作业法求解分配问题 C从分配问题的效益矩阵中逐行取其最小元素，可得到最优分配方案 D匈牙利法所能求解的分配问题，要求规定一个人只能完成一件工作，同时一件工作也只给一个人做。4.整数规划类型包括（CDE ）A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0 1 规划 5.对于某一整数规划可能涉及到的解题内容为（ABCDE）A 求其松弛问题 B 在其松弛问题中增加一个约束方程 C 应用单形或图解法D 割去部分非整数解 E多次切割 三、名词 1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。2、01 规划问题：在线性规划问题中，如果要求所有的决策变量只能取 0 或 1，这样的问题称为 01 规划。3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。四、用分枝定界法求解下列整数规划问题：(提示:可采用图解法)maxZ=40 x1+90 x2 五、用割平面法求解 六、下列整数规划问题 说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令 x1=3，x2=x3=0，其中第 2 个约束无法满足，故不可行。七、若某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油。使总的钻探费用为最小。若 10 个井位的代号为 S1,S2，S10相应的钻探费用为 C1,C2,C10，并且井位选择要满足下列限制条件：(1)在 s1，s2，S4中至多只能选择两个；(2)在 S5，s6中至少选择一个；(3)在 s3，s6，S7，S8中至少选择两个；试建立这个问题的整数规划模型 八、有四项工作要甲、乙、丙、丁四个人去完成每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少?工作 人 I 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 第二章 线性规划问题的基本概念 3、本章典型例题分析 例：211520maxxxZ 用单纯形法求解 tS 6003221 xx 400221xx 0,21xx 解：先化为标准形式：211520maxxxZ tS 60032321xxx 4002421xxx )4,3,2,1(0jxj 把标准形的系数列成一个表 基 S X1 X2 X3 X4 解 S 1-20-15 0 0 0 X3 0 2 3 1 0 600 X4 0 2 1 0 1 400 第一次迭代：调入 x1,调出 x4 基 S X1 X2 X3 X4 解 S 1 0-5 0 10 4000 X3 0 0 2 1-1 200 X1 0 1 1/2 0 1/2 200 第二次迭代：调入 x2,调出 x3 基 S X1 X2 X3 X4 解 S 1 0 0 5/2 15/2 4500 X2 0 0 1 1/2-1/2 100 X1 0 1 0-1/4 3/4 150 maxZ 450010015021xx 4、本章作业 见本章练习题 3、本章典型例题分析 例：写出下列线性规划问题的对偶问题)3,2,1(0205432553643max321321321jxxxxxxxtSxxxZj 解：其对偶问题为：0,4551433362025min2121212121yyyyyyyytSyyW 4、本章作业 见本章练习题 二、写出下列线性规划问题的对偶问题：（1）432132maxxxxxZ 无约束42314313214321,0,14325xxxxxxxxxxxxxx（2）321422minxxxZ 0,0564373253232321321321xxxxxxxxxxx 管理运筹学复习 一、考虑下列线性规划（20 分）MaxZ=2X1+3X2 2X1+2X2+X3=12 X1+2X2 +X4=8 4X1 +X5=16 4X2 +X6=12 Xj0（j=1,2,6）其最优单纯形表如下：基变量 X1 X2 X3 X4 X5 X6 X3 0 0 0 1-1-1/4 0 s.t.s.t.X1 4 1 0 0 0 1/4 0 X6 4 0 0 0-2 1/2 1 X2 2 0 1 0 1/2-1/8 0 j 0 0 0-3/2-1/8 0 1）当 C2=5 时，求新的最优解 2）当 b3=4 时，求新的最优解 3）当增加一个约束条件 2X1+X212，问最优解是否发生变化，如果发生变化求新解？解当 C2=5 时 4=5/2 5=1/80 所以最优解发生变化 基变量 X1 X2 X3 X4 X5 X6 0 X3 0 0 0 1-1-1/4 0 2 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0-2 1/2 1 5 X2 2 0 1 0 1/2-1/8 0 j 0 0 0-5/2 1/8 0 0 X3 2 0 0 1 2 0 1/2 2 X1 2 1 0 0 1 0-1/2 0 X5 8 0 0 0-4 1 2 5 X2 3 0 1 0 0 0 1/4 j 0 0 0-2 0-1/4 最优解为 X1=2，X2=3,Z19 2）当 b3=4 时 基变量 X1 X2 X3 X4 X5 X6 0 X3 3 0 0 1-1-1/4 0 2 X1 1 1 0 0 0 1/4 0 0 X6-3 0 0 0-2 1/2 1 3 X2 5/2 0 1 0 1/2-1/8 0 j 0 0 0-3/2-1/8 0 0 X3 9/2 0 0 1 0-1/2 1 2 X1 1 1 0 0 0 1/4 0 0 X4 3/2 0 0 0 1-1/4-1/2 3 X2 7/4 0 1 0 0 0 1/4 j 0 0 0 0-1/2-3/4 此时最优解为 X1=1，X2=7/4,Z 29/4 3)增加一个约束条件 基变量 X1 X2 X3 X4 X5 X6 X7 X3 0 0 0 1-1-1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0-2 1/2 1 0 X2 2 0 1 0 1/2-1/8 0 0 X7 12 2 1 0 0 0 0 1 j 0 0 0-3/2-1/8 0 0 X3 0 0 0 1-1-1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0-2 1/2 1 0 X2 2 0 1 0 1/2-1/8 0 0 X7 2 0 0 0 1/2 3/8 0 1 j 0 0 0-3/2-1/8 0 0 由于 X72 大于 0，所以最优解不变