下载文档原格式
一、单选题1、下列说法正确的是（）。
A.分枝定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分枝迭代求出最优解B.用割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解C.用分枝定界法求解一个极大化的整数规划时，当得到多于一个可行解时，通常可任取其中一个作为下界，再进行比较剪枝D.整数规划问题最优值优于其相应的线性规划问题的最优值正确答案：A2、整数规划的最优解中，决策变量满足（）。
A.决策变量不是整数B.没有要求C.决策变量至少有一个是整数D.决策变量必须都是整数正确答案：D3、下列（）可以求解指派问题。
A.梯度法B.牛顿法C.单纯形法D.匈牙利法4、整数规划中，通过增加线性约束条件将原规划可行域进行切割，切割后的可行域的整数解正好是原规划的最优解的方法是（）。
A.隐枚举法B.0-1规划法C.分支定界法D.割平面法正确答案：D5、标准指派问题（m人，m件事）的规划模型中，有（）个决策变量。
A.都不对B. m*mC. mD.2m正确答案：B二、判断题1、匈牙利法可以直接求解极大化的指派问题。
（）正确答案：×2、整数规划的可行解集合是离散型集合。
（）正确答案：√3、用分支定界法求一个极大化的整数规划时，任何一个可行解的目标函数值是该问题的目标函数值的下界。
（）4、用分支定界法求一个极大化的整数规划时，当得到多于一个可行解时，通常可以任取一个作为下界值，在进行比较和剪枝。
（）正确答案：×5、用割平面求纯整数规划时，要求包括松弛变量在内的全部变量都取整数。
（）正确答案：√。
运筹学中的整数规划问题分析运筹学是运用数学和定量分析方法，通过对系统的建模和优化，来解决实际问题的学科。
其中整数规划是运筹学中的一个重要分支，它在许多实际情况中得到广泛应用。
本文将对整数规划问题进行分析，并探讨其解决方法与应用领域。
一、整数规划问题定义及特点整数规划是一类线性规划问题的扩展，其目标函数和约束条件中的变量取值限定为整数。
通常，整数规划问题可以形式化表示为：Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙs.t.a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + a₂₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ∈ Z其中，Z为目标函数值，x₁, x₂, ..., xₙ为待求解的整数变量，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右端常数。
整数规划问题的特点在于整数约束条件的引入，使其解空间变得有限，增加了问题的复杂性。
与线性规划问题相比，整数规划问题更接近实际情况，能够更准确地描述和解决很多实际问题。
二、整数规划问题的解决方法解决整数规划问题的方法主要有以下几种：穷举法、剪枝法、分支定界法、动态规划法等。
具体使用哪种方法需要根据问题的规模和特点来确定。
1. 穷举法是最简单直观的方法，通过枚举搜索整数解空间中的每一个可能解来寻找最优解。
然而，由于整数解空间往往非常大，这种方法在实际问题中往往是不可行的。
2. 剪枝法是一种通过对解空间进行剪枝操作，减少搜索空间的方法。
通过合理选择剪枝条件，可以避免对明显无解的解空间进行搜索，从而提高求解效率。
3. 分支定界法是一种将整数规划问题不断分解为子问题，并对子问题进行界定的方法。
通过不断缩小问题规模，并计算上下界确定最优解的位置，可以有效地求解整数规划问题。
《运筹学》作业参考答案作业一一、是非题：1.图解法与单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。
（√）2.线性规划问题的每一个基解对应可行解域的一个顶点。
（╳）3.如果线性规划问题存在最优解，则最优解一定可以在可行解域的顶点上获得。
（√）4.用单纯形法求解Max型的线性规划问题时，检验数Rj＞0对应的变量都可以被选作入基变量。
（√）5.单纯形法计算中，如果不按最小比值规划选出基变量，则在下一个解中至少有一个基变量的值为负。
（√）6.线性规划问题的可行解如为最优解，则该可行解一定是基可行解。
（╳）7.若线性规划问题具有可行解，且可行解域有界，则该线性规划问题最多具有有限个数的最优解。
（╳）8.对一个有n个变量，m个约束的标准型线性规划问题，其可行域的顶点数恰好为mnC个。
（╳）9.一旦一个人工变量在迭代中变为非基变量后，该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果。
（√）10.求Max型的单纯形法的迭代过程是从一个可行解转换到目标函数值更大的另一个可行解。
（√）二、线性规划建模题：1.某公司一营业部每天需从A、B两仓库提货用于销售，需提取的商品有：甲商品不少于240件，乙商品不少于80台，丙商品不少于120吨。
已知：从A仓库每部汽车每天能运回营业部甲商品4件，乙商品2台，丙商品6吨，运费200元/每部；从B仓库每部汽车每天能运回营业部甲商品7件，乙商品2台，丙商品2吨，运费160元/每部。
问：为满足销售量需要，营业部每天应发往A、B两仓库各多少部汽车，并使总运费最少？解：设营业部每天应发往A、B两仓库各x1，x2部汽车,则有：12 121212min200160 47240 2280 621200(1,2)jW x xx xx xx xx j=++≥⎧⎪+≥⎪⎨+≥⎪⎪≥=⎩2.现有一家公司准备制定一个广告宣传计划来宣传开发的新产品，以使尽可能多的未来顾客特别是女顾客得知。
第一部分绪论第二部分线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的；(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点；(e)对取值无约束的变量x i,通常令其中,在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量；(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若x1,x2分别是某一线性规划问题的最优解,则也是该线性规划问题的最优解,其中λ1,λ2可以为任意正的实数；(1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为X ai为人工变量),但也可写为,只要所有k i均为大于零的常数；(m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好为个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解；(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号,将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品,建立线性规划模型求解得到的最优解中,最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系相对较小。
第四章 整数规划与分配问题一、建立下列问题的数学模型1、P143, 4.1 利用0－1变量对下列各题分别表示成一般线性约束条件 (a) 221≤+x x 或53221≥+x x ； (b) x 取值0,3,5,7中的一个； (c) 变量x 或等于0，或50≥； (d) 若21≤x ，则12≥x ，否则42≤x ； (e) 以下四个约束条件中至少满足两个：6225433121≥+≥≤≤+x x x x x x ，，，。
解：(a) 设⎩⎨⎧=否则。
，个条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。
则有 ⎪⎩⎪⎨⎧=+≥++≤+1y y My -5x 3x 2My 2x x 21221121(b) 设⎩⎨⎧=≠=ix i x y i ,1,0，7,5,3,0=i ，则原条件可表示为⎩⎨⎧=++++++=1753075307530y y y y y y y y x(c) 设⎩⎨⎧≥==50,10,0x x y ，则原条件可表示为⎪⎩⎪⎨⎧≥--≥≤0)1(50x M y x yM x(d)⎩⎨⎧=否则。
，组条件起作用；第1i ,0y i （i=1,2）,M 为任意大正数。
则有⎪⎪⎪⎩⎪⎪⎪⎨⎧=++≤->-≥+≤.1,4,2,1,22122211211y y My x My x My x My x (e)设⎩⎨⎧=个条件不成立第个条件成立第i ,1i ,0y i ，4,3,2,1i =，则原条件可表示为：⎪⎪⎪⎩⎪⎪⎪⎨⎧≤+++-≥+-≥+≤+≤+2y y y y My 6x x My 2x M y 2x M y 5x x 43214433321121 2、P143, 4.2 某钻井队要从以下10个可供选择的井位确定5个钻井探油，目的是使得总的钻探费用最小。
若10个井位代号为101S ,...,S ，相应的钻探费用为101C ,...,C ，并且井位的选择要满足下列条件：（1）或选择1S 和7S ，或选择8S ；（2）选择了3S 或4S 就不能选择5S ，反过来也一样； （3）在10962S ,S ,S ,S 中最多只能选两个。
第六章整数规划6.1 用图形将一下列线性规划问题的可行域转换为纯整数问题的可行域(在图上用“×”标出)。
1、 max z=3x1+2x2S.T. 2x1+3x2≤122x1+x2≤9x1、x2≥0解：2、 min f=10x1+9x2S.T. 5x1+3x2≥45x1≥8x2≤10x1、x2≥06.2 求解下列整数规划问题1、 min f=4x1+3x2+2x3S.T. 2x1-5x2+3x3≤44x1+x2+3x3≥3x2+x3≥1x1、x2、x3=0或1解：最优解（0，0，1），最优值：22、 min f=2x1+5x2+3x3+4x3S.T. -4x1+x2+x3+x4≥2-2x1+4x2+2x2+4x2≥4x1+x2-x2+x2≥3x1、x2、x3、x3=0或1解：此模型没有可行解。
3、max Z=2x1+3x2+5x3+6x4S.T. 5x1+3x2+3x3+x4≤302x1+5x2-x2+3x2≤20-x1+3x2+5x2+3x2≤403x1-x2+3x2+5x2≤25x1、x2、x3、x3=正整数解：最优解（0，3，4，3），最优值：474、min z =8x1 +4 x2+3 x3+5 x4+2 x5＋3 x6＋4 x7＋3 x8+4 x9+9 x10+7 x11+5 x12 +10 x13+4 x14+2 x15+175 x16+300 x17+375 x18 +500 x19约束条件x1 + x2+x3≤30x4+ x5＋x6-10 x16≤0x7+ x8＋x9-20 x17≤0x10+ x11＋x12-30 x18≤0x13+ x14＋x15-40 x19≤0x1 + x4+ x7+x10+ x13＝30x2 + x5+ x8+x11+ x14＝20x3 + x6+ x9+x12+ x15＝20x i为非负数（i=1,2…..8）x i为非负整数（i=9,10…..15）x i为为0－1变量（i=16,17…..19）解：最优解（30，0，0，0，0，0，0，0，0，0，0，0，0，20，20，0，0，0，1），最优值：8606.3 一餐饮企业准备在全市范围内扩展业务，将从已拟定的14个点中确定8个点建立分店，由于地理位置、环境条件不同，建每个分店所用的费用将有所不同，现拟定的14个店的费用情况如下表：公司办公会决定选择原则如下：（1）B5、B3和B7只能选择一个。
实验六、用EXCEL 求解整数规划用单纯形法求解线性规划问题，最优解可能是整数，也可能不是整数，但在很多实际问题中，要求全部或部分变量的取值必须是整数，如所求的解是安排上班的人数，按某个方案裁剪钢材的根数，生产设备的台数等等。
对于整数解的线性规划问题，不是用四舍五入或去尾法对线性规划的非整数解加以处理都能解决的，而要用整数规划的方法加以解决，如分枝定界法和割平面算法。
这些算法比单纯形法更为复杂，因此，一般的学习者要想掌握整数规划的数学算法有一定的困难。
然而事实上，由于Excel 的[工具][规划求解]可以求解整数规划问题，所以，对于一个真正有志于运用运筹学方法解决生产经营中问题的管理者来说，算法将不是障碍因素。
一、实验目的1、 掌握如何建立整数线性规划模型，特别是0～1逻辑变量在模型中的应用。
2、 掌握用Excel 求解整数线性规划模型的方法。
3、 掌握如何借助于Excel 对整数线性规划模型进行灵敏度分析，以判断各种可能的变化对最优方案产生的影响。
4、 读懂Excel 求解整数线性规划问题输出的运算结果报告和敏感性报告。
二、 实验内容1、 整数规划问题模型该问题来自于《运筹学基础及应用》（第四版）胡运权主编P126习题4.13,题目如下: 需生产2000件某种产品，该种产品可利用A 、B 、C 、D 设备中的任意一种加工，已知每种设备的生产准备结束费用、生产该产品时的单件成本以及每种设备限定的最大加工数量（件）如表1所示，问企业应该如何安排设备生产该产品才能使得总的生产成本最少，试建立该问题的数学模型并求解。
该产品可以利用四种不同的设备加工，由于采用不同的设备加工需要支付不同的准备结束费用，而如果不采用某种设备加工，是不需要支付使用该设备的准备结束费用的，所以必须借助于逻辑变量来鉴定准备结束费用的支付。
再设，种设备加工的产品数量为利用第设;4,3,2,1=j j x j⎪⎩⎪⎨⎧=>=）种设备生产（即，若不使用第）种设备生产（即若使用第000,1j j i x j x j y 4,3,2,1=j则问题的整数规划模型为：43214321281624207008009801000min x x x x y y y y z +++++++=⎪⎪⎪⎪⎩⎪⎪⎪⎪⎨⎧==≥≤≤≤≤=+++4,3,2,110,01600120010009002000..443322114321j y x y x y x y x y x x x x x t s j j，或2、 [工具][规划求解]命令求解下面我们用Excel 中的[工具][规划求解]对该问题进行求解。
