第三章线性规划问题的计算机求解

课程：管理运筹学管理运筹学作业第二章线性规划的图解法P23：Q2：（1）－（6）；Q3：(2)Q2：用图解法求解下列线性规划问题，并指出哪个问题具有唯一最优解，无穷多最优解，无界解或无可行解。

（1）Min f＝6X1+4X2约束条件：2X1+X2>=1,3X1+4X2>=3X1, X2>=0解题如下：如图1Min f＝3.6X1=0.2, X2=0.6本题具有唯一最优解。

图1（2）Max z＝4X1+8X2约束条件：2X1+2X2<=10-X1+X2>=8X1,X2>=0解题如下：如图2：Max Z 无可行解。

图2（3） Max z ＝X1+X2 约束条件 8X1+6X2>=24 4X1+6X2>=-12 2X2>=4 X1,X2>=0 解题如下：如图3： Max Z=有无界解。

图3（4） Max Z ＝3X1-2X2 约束条件：X1+X2<=1 2X1+2X2>=4 X1,X2>=0 解题如下：如图4： Max Z 无可行解。

图4(5)Max Z＝3X1+9X2 约束条件：X1+3X2<=22-X1+X2<=4X2<=62X1-5X2<=0X1,X2>=0解题如下：如图5：Max Z =66；X1=4 X2=6本题有唯一最优解。

图5(6)Max Z=3X1+4X2 约束条件：-X1+2X2<=8X1+2X2<=122X1+X2<=162X1-5X2<=0X1,X2>=0解题如下：如图6Max Z =30.669X1=6.667 X2=2.667本题有唯一最优解。

图6Q3：将线性规划问题转化为标准形式（2）min f＝4X1+6X2约束条件：3X1-2X2>=6X1+2X2>=107X1-6X2=4X1,X2>=0解题如下：1）目标函数求最小值化为求最大值：目标函数等式左边min改为max，等式右边各项均改变正负号。

第三章思考题、主要概念及内容“管理运筹学”软件的操作方法“管理运筹学”软件的输出信息分析复习题1.见第二章第7题，设x1为产品Ⅰ每天的产量，x2为产品Ⅱ每天的产量，可以建立下面的线性规划模型：max z=500x1+400x2；约束条件：2x1≤300，3x2≤540，2x1+2x2≤440，1.2x1+1.5x2≤300，x1，x2≥0．使用“管理运筹学”软件，得到的计算机解如图1所示图1根据图3-5回答下面的问题：(1) 最优解即最优产品组合是什么?此时最大目标函数值即最大利润为多少?(2) 哪些车间的加工工时数已使用完?哪些车间的加工工时数还没用完?其松弛变量即没用完的加工工时数为多少?(3) 四个车间的加工工时的对偶价格各为多少?请对此对偶价格的含义予以说明．(4) 如果请你在这四个车间中选择一个车间进行加班生产，你会选择哪个车间?为什么?(5) 目标函数中x1的系数c1，即每单位产品Ⅰ的利润值，在什么范围内变化时，最优产品的组合不变?(6) 目标函数中x2的系数c2，即每单位产品Ⅱ的利润值，从400元提高为490元时，最优产品组合变化了没有?为什么?(7) 请解释约束条件中的常数项的上限与下限．(8) 第1车间的加工工时数从300增加到400时，总利润能增加多少?这时最优产品的组合变化了没有?(9) 第3车间的加工工时数从440增加到480时，从图3-5中我们能否求得总利润增加的数量?为什么?(10) 当每单位产品Ⅰ的利润从500元降至475元，而每单位产品Ⅱ的利润从400元升至450元时，其最优产品组合(即最优解)是否发生变化?请用百分之一百法则进行判断．(11) 当第1车间的加工工时数从300增加到350，而第3车间的加工工时数从440降到380时，用百分之一百法则能否判断原来的对偶价格是否发生变化?如不发生变化，请求出其最大利润．2. 见第二章第8题(2)，仍设xA为购买基金A的数量，xB为购买基金B的数量，建立的线性规划模型如下：max z=5xA+4xB；约束条件：50xA+100xB≤1 200 000，100xB≥300 000，xA，xB≥0．使用“管理运筹学”软件，求得计算机解如图2所示．图2根据图2，回答下列问题：(1) 在这个最优解中，购买基金A和基金B的数量各为多少?这时获得的最大利润是多少?这时总的投资风险指数为多少?(2) 图3-7中的松弛/剩余变量的含义是什么?(3) 请对图3-7中的两个对偶价格的含义给予解释．(4) 请对图3-7中的目标函数范围中的上、下限的含义给予具体说明，并阐述如何使用这些信息．(5) 请对图3-7中的常数项范围的上、下限的含义给予具体说明，并阐述如何使用这些信息．(6) 当投资总金额从1 200 000元下降到600 000元，而在基金B上至少投资的金额从300 000元增加到600 000元时，其对偶价格是否发生变化?为什么?3. 考虑下面的线性规划问题：min z=16x1+16x2+17x3；约束条件：x1+x3≤30，　-x2+6x3≥15，05x13x1+4x2-x3≥20，x1，x2，x3≥0．其计算机求解结果如图3所示．图3根据图3，回答下列问题：(1) 第二个约束方程的对偶价格是一个负数(为-3622)　，它的含义是什么?　，它的含义是什么?(2) x2的相差值为0703(3) 当目标函数中x1的系数从16降为15，而x2的系数从16升为18时，最优解是否发生变化?(4) 当第一个约束条件的常数项从30减少到15，而第二个约束条件的常数项从15增加到80时，你能断定其对偶价格是否发生变化吗?为什么?。

线性规划问题的两种求解⽅式线性规划问题的两种求解⽅式线性规划是运筹学中研究较早、发展较快、应⽤⼴泛、⽅法较成熟的⼀个重要分⽀，它是辅助⼈们进⾏科学管理的⼀种数学⽅法。

线性规划所研究的是：在⼀定条件下，合理安排⼈⼒物⼒等资源，使经济效果达到最好。

⼀般地，求线性⽬标函数在线性约束条件下的最⼤值或最⼩值的问题，统称为线性规划问题。

解决线性规划问题常⽤的⽅法是图解法和单纯性法，⽽图解法简单⽅便，但只适⽤于⼆维的线性规划问题，单纯性法的优点是可以适⽤于所有的线性规划问题，缺点是单纯形法中涉及⼤量不同的算法，为了针对不同的线性规划问题，计算量⼤，复杂繁琐。

在这个计算机⾼速发展的阶段，利⽤Excel建⽴电⼦表格模型，并利⽤它提供的“规划求解”⼯具，能轻松快捷地求解线性模型的解。

⽆论利⽤哪种⽅法进⾏求解线性规划问题，⾸先都需要对线性规划问题建⽴数学模型，确定⽬标函数和相应的约束条件，进⽽进⾏求解。

从实际问题中建⽴数学模型⼀般有以下三个步骤；1、根据所求⽬标的影响因素找到决策变量；2、由决策变量和所求⽬标的函数关系确定⽬标函数；3、由决策变量所受的限制条件确定决策变量所要满⾜的约束条件。

以下是分别利⽤单纯形法和Excel表格中的“规划求解”两种⽅法对例题进⾏求解的过程。

例题：某⼯⼚在计划期内要安排⽣产I、II两种产品，已知⽣产单位产品所需的设备台时分别为1台时、2台时，所需原材料A分别为4单位、0单位，所需原材料B分别为0单位、4单位，⼯⼚中设备运转最多台时为8台时，原材料A、B的总量分别为16单位、12单位。

每⽣产出I、II产品所获得的利润为2和3，问I、II两种产品的⽣产数量的哪种组合能使总利润最⼤？这是⼀个典型的产品组合问题，现将问题中的有关数据列表1-1如下：表1-1I II 限量设备 1 2 8台时原材料A 4 0 16单位原材料B 0 4 12单位所获利润 2 3⾸先对例题建⽴数学模型。

问题的决策变量有两个：产品I的⽣产数量和产品II的⽣产数量；⽬标是总利润最⼤；需满⾜的条件是：(1)两种产品使⽤设备的台时<= 台时限量值(2) ⽣产两种产品使⽤原材料A、B的数量<= 限量值(3)产品I、II的⽣产数量均>=0。

线性规划问题的计算机求解心得体会
线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，它是辅助人们进行科学管理的一种数学方法在经济管理、交通运输、工农业生产等经济活动中，提高经济效果是人们不可缺少的要求，而提高经济效果一般通过两种途径：一是技术方面的改进，例如改善生产工艺，使用新设备和新型原材料。

二是生产组织与计划的改进，即合理安排人力物力资源。

线性规划所研究的是：在一定条件下，合理安排人力物力等资源，使经济效果达到最好一般地，求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。

满足线性约束条件的解叫做可行解，由所有可行解组成的叫做可行域，在可行域中目标函数值最大（或最小）的可行解叫做最优解，最优解的全体称为最优解集合。

决策变量、约束条件、目标函数是线性规划的三大共同点。

线性规划步骤（1）列出约束条件及目标函数（2）画出约束条件所表示的可行域（3）在可行域内求目标函数的最优解及最优值。

在线性规划中有两大模型，一般形式和标准形式。

为了讨论问题的方便，我们经常将线性规划问题约定为某一标准形式。

运筹学（Operational Research）复习资料第一章绪论一、名词解释1.运筹学：运筹学是应用分析、试验、量化的方法，对经济管理系统中的人力、物力、财力等资源进行统筹安排，为决策者提供有依据的最优方案，以实现最有效的管理。

二、选择题1.运筹学的主要分支包括（ABDE ）A图论B线性规划C非线性规划D整数规划E目标规划2. 最早运用运筹学理论的是（ A ）A . 二次世界大战期间，英国军事部门将运筹学运用到军事战略部署B . 美国最早将运筹学运用到农业和人口规划问题上C . 二次世界大战期间，英国政府将运筹学运用到政府制定计划D . 50年代，运筹学运用到研究人口，能源，粮食，第三世界经济发展等问题上第二章线性规划的图解法一、选择题/填空题1.线性规划标准式的特点：（1）目标函数最大化（2）约束条件为等式（3 决策变量为非负（4 ) 右端常数项为非负2. 在一定范围内，约束条件右边常数项增加一个单位：（1）如果对偶价格大于0，则其最优目标函数值得到改进，即求最大值时，最优目标函数值变得更大，求最小值时最优目标函数值变得更小。

（2）如果对偶价格小于0，则其最优目标函数值变坏，即求最大值时，最优目标函数值变小了；求最小值时，最优目标函数值变大了。

（3）如果对偶价格等于0，则其最优目标函数值不变。

3.LP模型（线性规划模型）三要素：（1）决策变量（2）约束条件（3）目标函数4. 数学模型中，“s·t”表示约束条件。

5. 将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左端加上松弛变量。

6. 将线性规划模型化成标准形式时，“≥”的约束条件要在不等式左端减去剩余变量。

7．下列图形中阴影部分构成的集合是凸集的是A【解析】：如何判断是凸集？凸集：两点之间连线在图内凹集：两点之间连线在图外8. 线性规划问题有可行解且凸多边形无界，这时CA没有无界解 B 没有可行解 C 有无界解 D 有有限最优解9. 对于线性规划问题，下列说法正确的是（ D ）A. 线性规划问题可能没有可行解B. 在图解法上，线性规划问题的可行解区域都是“凸”区域C. 线性规划问题如有最优解，则最优解可在可行解区域顶点上到达D. 上述说法都正确第三章线性规划问题的计算机求解一、名词解释1.相差值：相应的决策变量的目标系数需要改进的数量，使得决策变量为正值。

《数据、模型和决策》作业一学号：2461604112 姓名：王康兵班级：2016秋MBA2周末班一、第三章线性规划问题的计算机求解习题6 （P35）答：根据图3-10回答问题如下：（1）最优解即最优产品组合是产品Ⅰ每天的产量是150个，产品Ⅱ每天的产量是70个。

此时最大的目标函数即最大利润为103000元。

（2）车间1和车间3的加工工时数已使用完，车间2和车间4的加工工时数还没用完。

车间2的松弛变量即没用完的加工工时数为330工时，车间4的松弛变量即没用完的加工工时数为15工时。

（3）车间1的加工工时的对偶价格为50元，即增加一个工时就可能使总利润增加50元；车间2的加工工时的对偶价格为0元，即增加一个工时不会使总利润有所增加；车间3的加工工时的对偶价格为200元，即增加一个工时就可能使总利润增加200元；车间4的加工工时的对偶价格为0元，即增加一个工时不会使总利润有所增加。

（4）如果要在这四个车间选择一个车间进行加班生产，我会选择车间3。

因为在车间3的加工工时的对偶价格为200元，即每增加一个工时就可能使总利润增加200元，能为公司创造价值。

（5）目标函数中x1的系数c1，即每单位产品Ⅰ的利润值，当c1在400与+∞之间变化时，最优产品组合不变。

（6）目标函数中x2的系数c2，即每单位产品Ⅱ的利润值，当c2从400元提高到490元时，最优产品组合没有变化。

因为当c2=490元时，0《490《500，仍在c2的系数变化范围内，所以其最优产品组合没有变化。

（7）约束条件中的常数项的现在值由图3-10可知，b1=300，b2=540，b3=440，b4=300。

所谓常数项的上限和下限是指当约束条件中的常数项在此范围内变化时，与其对应的约束条件的对偶价格不变。

具体地说，当车间1的加工工时数在200到440的范围内时，其对偶价格都为50元；当车间2的加工工时数在210到+∞范围内时，其对偶价格为零；当车间3的加工工时数在300到460范围内时，其对偶价格都为200元；当车间4的加工工时数在285到+∞范围内时，其对偶价格为零。