第三章线性规划的应用及计算机求解
- 格式:doc
- 大小:11.10 MB
- 文档页数:29
课程:管理运筹学管理运筹学作业第二章线性规划的图解法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时,你能断定其对偶价格是否发生变化吗?为什么?。
《管理运筹学》第四版课后习题解析(上)第2章线性规划的图解法1.解:(1)可行域为OABC。
(2)等值线为图中虚线部分。
? (3)由图2-1可知,最优解为B 点,最优解 x =12, x ??15 727图2-1 ;最优目标函数值 69。
72.解:(1)如图2-2所示,由图解法可知有唯一解?x 1 ??0.2,函数值为3.6。
?x 2图2-2(2)无可行解。
(3)无界解。
(4)无可行解。
? (5)无穷多解。
?x ? (6)有唯一解 ??1? 203,函数值为 92 。
8 3x ? ??2 33.解: (1)标准形式max f ??3x 1 ??2x 2 ??0s 1 ??0s 2 ??0s 39x 1 ??2x 2 ??s 1 ??30 3x 1 ??2x 2 ??s 2 ??13 2x 1 ??2x 2 ??s 3 ??9 x 1, x 2 , s 1, s 2 , s 3 ≥ 0(2)标准形式min f ??4x 1 ??6x 2 ??0s 1 ??0s 23x 1 ??x 2 ??s 1 ??6x 1 ??2x 2 ??s 2 ??10 7x 1 ??6x 2 ??4x 1, x 2 , s 1, s 2 ≥ 0(3)标准形式min f ??x 1????2x 2????2x 2??????0s 1 ??0s 2?3x 1 ??5x 2????5x 2??????s 1 ??70 2x 1????5x 2????5x 2??????50 3x 1????2x 2????2x 2??????s 2 ??30 x 1?, x 2??, x 2????, s 1, s 2 ≥ 0 4.解: 标准形式max z ??10x 1 ??5x 2 ??0s 1 ??0s 23x 1 ??4x 2 ??s 1 ??95x 1 ??2x 2 ??s 2 ??8x1, x2 , s1, s2 ≥0≤松弛变量(0,0)最优解为 x 1 =1,x 2=3/2。
《数据、模型和决策》作业一学号: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到+∞范围内时,其对偶价格为零。
第三章线性规划问题的计算机求解3-1(1)甲、乙两种柜的日产量是分别是4和8,这时最大利润是2720。
(2)油漆工艺生产增加1小时,可以使总利润提高13.333元。
(3)常数项的上下限是指常数项在指定的范围内变化时,与其对应的约束条件的对偶价格不变。
比如油漆时间变为100,因为100在40和160之间,所以其对偶价格不变仍为13.333。
(4)不变,因为还在120和480之间。
3-2(1)最优决策为截第一种钢板6张,第二种钢板7张。
(2)需要A种规格的小钢板成品个数在12和27范围内时,第一个约束条件的对偶价格不变。
(3)B种规格的小钢板成品的剩余变量值为4,表示此决策下,截得B种规格成品的实际数量比B种规格的成品的需求量多了4个。
3-3(1)农用车有12辆剩余。
(2)300到正无穷范围内。
(3)每增加一辆大卡车,总运费降低192元。
3-4(1)是最优解。
(2)此常数项在-∞到2范围内变化时,约束1的对偶价格不变。
3-5(1)圆桌和衣柜的生产件数分别是350和100件,这时最大利润是3100元。
(2)相差值为0代表,不需要对相应的目标函数系数进行改进就可以生产该产品。
(3)最优解不变,因为C1允许增加量200-6=140;C2允许减少量为100-30=70,所有允许增加百分比和允许减少百分比之和(75-60)/140+(100-90)/70<100%,所以最优解不变。
3-6(1)1150x=,270x=,即产品I的产量为150,产品II的产量为70;目标函数最优值103 000,即最大利润为103 000。
(2)1、3车间的加工工时数已使用完;2、4车间的加工工时数没用完;没用完的加工工时数为2车间330小时,4车间15小时。
(3)50,0,200,0。
含义:1车间每增加1工时,总利润增加50元;3车间每增加1工时,总利润增加200元;2车间与4车间每增加一个工时,总利润不增加。
(4)3车间,因为增加的利润最大。
毕业论文(设计)课题名称线性规划模型的求解及应用业数学与应用数学(S)2010级数学2班指导教师________________________________ 学生姓名______________________________隹木期大学数务处word文档可自由复制編辑线性规划模型的求解及应用佳木斯大学理学院数学系2014年6月线性规划是运筹学的一个重要分支,它辅助人们进行科学管理,是国际应用数学、经济、计算机科学界所关注的垂要研究领域.线性规划主要研究有限资源最佳分配问题,即如何对有限的资源进行最佳地调配和最有利地使用,以便最充分发挥资源的效能来获取最佳的经济效益.线性规划运用数学语言描述某些经济活动的过程,形成数学模型,以一定的算法对模型进行计算,为制定最优计划方案提供依据•其解决问题的关键是建立符合实际情况的数学模型,即线性规划模型.在各种经济活动中,常采用线性规划模型进行科学、定量分析, 安排生产组织与计划,实现人力物力资源的最优配置,获得最佳的经济效益.目前,线性规划模型被广泛应用与经济管理、交通运输、工农业生产等领域.本文主要介绍线性规划的两种基本解法即图解法和单纯形法,并讨论了这两种方法的优缺点和在一些实际问题屮的应用.关键词:线性规划:图解法:单纯形法:数学模型:应用AbstractLinear progianmiing is an iinpoilant branch of operations research, which assist people to scientific management is an important area of research iiitemationally applied mathematics, economics, computer science conmiunity^s concerns. The main study of linear programming optimal allocation of limited resomces, namely liow to limited resoiuces optimally deploy and most advantageously used in order to most hilly effective resources to get the best value for money.Linear progianmiing using mathematical language to describe the process of certain economic activities, the fonnation of mathematical models to a certain algorithm to calculate the model toword文档可自由复制編辑provide a basis for the fonnulation of the optimal plan for. The key to solve the problem is to create a mathematical model in line with the actual situation, namely linear progranmiing model. In various economic activities, often using linear progianuning model for scientific, quantitative analysis, organization and planning for production to achieve the optimal allocation of hiunan and material resources, to get the best value for money. At present, the linear progianmiing model is widely used in economic management, tiansportation, industrial and agricultural production and other fields.This paper describes two basic solution that giaphical method for linear programming and the simplex method, and discuss the advantages and disadvantages of both methods and applications in a number of practical problems・Key words:Linear Programming: Graphic method; simplex method; mathematical model;Application摘要........................................................................... Abstract .................................................................................................................................第1章绪论 ....................................................................1.1线性规划的基本概念......................................................1.1.1线性规划简介........................................................1.1.2线性规划由來的时间简史..............................................1.2线性规划的研究目的及意义................................................第2章线性规划问题的数学模型..................................................2.1线性规划模型的建立......................................................2.2线性规划模型的求解方法..................................................2.2.1图解法..............................................................2.2.2单纯形法............................................................ 第3章线性规划在实际问题中的应用..............................................3.1线性规划在企业管理中的应用 ..............................................3.1.1线性规划在企业管理中的应用范围......................................3.1.2如何实现线性规划在企业管理中的应用..................................3.2线性规划在企业生产计划中的应用 ..........................................33线性规划在运输问题中的应用............................................... 结论........................................................................... 參考文献.......................................................................第[章绪论1.1.1线性规划简介线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支, 它是辅助人们进行科学管理的一种数学方法.在经济管理、交通运输、工农业生产等经济活动中,提高经济效果是人们不可缺少的要求,而提高经济效果一般通过两种途径:一是技术方面的改进,例如改善生产工艺,使用新设备利新型原材料.二是生产组织与计划的改进,即合理安排人力物力资源.线性规划所研究的是:在一定条件下,合理安排人力物力等资源,使经济效果达到最好.一般地,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题•满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域.决策变量、约束条件、目标函数是线性规划的三要素.1.1.2线性规划由来的时间简史法国数学家J. - B. - J.傅里叶和C.瓦莱一普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意.1939年苏联数学家fl.B.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视.1947年美国数学家G. B. Dantzing提出求解线性规划的单纯型法,为这门学科奠定了基础.1947年美国数学家J. von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域, 扩大了它的应用范围和解题能力.1951年美国经济学家T. C.库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖.50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法.例如,1954年C.莱姆基提出对偶单纯形法,1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析利参数规划问题,1956年A.塔克提出互补松弛定理,1960年G.B•丹齐克和P.沃尔夫提出分解算法等.线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究.由于数字电子计算机的发展,出现了许多线性规划软件,如MPSX, OPHEIE, UMPIRE等,可以很方便地求解几「个变量的线性规划问题.1979年苏联数学家L. G. Khachian提出解线性规划问题的椭球算法,并证明它是多项式时间算法.1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法. 用这种方法求解线性规划问题在变屋个数为5000时只要单纯形法所用时间的1/50.现已形成线性规划多项式算法理论.50年代后线性规划的应用范用不断扩人.建立线性规划模型的方法第2章线性规划问题的数学模型2.1线性规划模型的建立线性规划是合理利用、调配资源的一种应用数学的方法•它的基本思路是在满足一定的约束条件下,使预定的目标达到最优•它的研究内容可归纳为两个方面:一是系统的任务资源数量己定,精细安排,用最少的资源去实现这个任务:二是资源数量己定,如何合理利用、调配,使任务完成的最多.前者是求极小,后者是求极大.线性规划的一般定义如下:对于求取一组变量Xj (j=l,2,-,n),使之既满足线性约束条件,又使具有线性特征的目标函数取得极值的一类最优化问题称为线性规划问题.线性规划模型建立需具备以下条件:一是最优目标.问题所要达到的目标能用线性函数來描述,且能够使用极值(最大或最小)来表示.二是约束条件•达到目标的条件是有一定限制的,这些限制可以用决策变量的线性等式或线性不等式來表示.三是选择条件,有多种方案可以供选择,以便从中找出最优方案.线性规划问题的一般数学模型如下:max(或min) Z = c1x l + c2x2 ------- 1- c n x n(1)r a1I x1 + a.2x2 + -+a.B x n< (=,b t+a22x2 4-- + a2a x c < (=,>) h2s.t. / : :: ⑵a:x l+a m2x2+ - + a mn x n 兰(=,>)b maV x:x2 ........... x n > 0(< 0)Xj (j = 1,2,“n) 称为决策变量word文档町“由复制编辑bj(j = 1,2, ...,n) 称为约束右端系数屯(}= 1,2,= 1,2, ...r n) 称为约束系数 其中式(1)为目标函数,式(2)称为约束条件•由于目标函数和约束条件内容和形式上的差别,线性规划问题有多种表达式,为了便 于讨论和制定统一的算法,规定标准形式如下:(1) 标准形式 iaxz = CiXj+C?%+••• + %£a n x i + + ・• • + a in\ =b 】a 21X l • • • + + ・•・ + ** * • • • a 2n X n =■ + 3^X3+ •••+ a nm\ =X )n 0 (j = 1,…,n)(2) £记号简写式nmax z =工 C J X Jj ・i■n E a u x j =b : (i = l ,2,.・.m)[Xj=O (j =1,2,...41)(3) 矩阵形式max z = CXjAX = b(X>O式中c=(C v ...,c n ), X= (xp.— xj 311 a 12 …a lnL 0A= 321 a 22 …a 2n ,b = b, ■ ,0 = 0• • • • • • ••• • • • • • ••• a ml a m2 …a mn b 3 0■ Cj(j = 1,2,…,n)称为1=1标函数系数max z = CXf Pkbn x>o式中C, X, b, 0的含义与矩阵的表达式相同,而Pj = [a ir a 2?-^a mj]0 = 12 …,n)即 A= (p 1,p 2r»>p n )将非标准形式化为标准形式的情况(3种基本情况)(1) 目标函数为求极小值minZ=CA ;则作 Z=-CX,即 maxZ^-CX(2) 右端项小于0只需要将两端同乘(-1),不等号改变方向,然后再将不等式改为等式(3) 约束条件为不等式 若约束条件为“兰”则在不等式左侧增加一个非负松驰变最,使其转化为若约束条件为“X”,则在不等式左侧减去一个非负剩余变量(也称松驰变暈),使其转化 为 “ =” •2.2线性规划模型的求解方法线性规划可以在一定条件下合理安排人力、物力等资源,使经济效果达到最好.一般 来说,求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问 题.满足线性约束条件的解叫做可行解,由所有可行解组成的集合叫做可行域.决策变星、 约束条件、目标函数是线性规划的三要素.然而图解法不适合解大规模的线性规划的问 题,局限性比较大.但对于只有两个或考三个变量的线性规划问题,可以用图解法求最优 解,也就是作出约束条件的可行域,利用图解的方法求出最优解,其特点是过程简洁、 图形清晰,简单易懂•下面仅做只有两个变量的线性规划问题.只含两个变量的线性规划问题,可以通过在平而上作图的方法求解,步骤如下:(4)向量形式 2. 2.1 解法(1)以变量X】为横坐标轴,X:为纵坐标轴,适当选取单位坐标长度建立平面坐标直角坐标系.由变量的非负性约束性可知,满足该约束条件的解均在第一象限内.(2)图示约束条件,找出可行域(所有约束条件共同构成的图形).(3)画出目标函数等值线,并确定函数增大(或减小)的方向.(4)可行域中使目标函数达到最优的点即为最优解.卜面举出一个实例来说明:例1•某木器厂生产圆桌和衣柜两种产品,现有两种木料,第一种有72m3,第二种有56假设生产每种产品都需要用两种木料,生产一张圆桌和一个衣柜分别所需木料如下表所示.每生产一张圆桌可获利60元,生产一个衣柜可获利100元.木器厂在现有木料条件下,圆桌和衣柜各生产多少,才使获得利润最多?解:设生产圆束x张,生产衣柜y个,利润总额为n元,则由已知条件得到的线性规划模型为:max z = 60x+ 100y,s.t. 0.18x+ 0.009y <72,0.08x+0.28y < 56,x>0,y>0.图2-1这是二维线性规划,可用图解法解,先在xy坐标平面上作出满足约束条件的平面区域,即可行域S,如上图所示.再作直线l:60x-F100y=0,即l:3x+5y=O,把直线1半移至的位置时,直线经过可行域上点M,且与原点距离最远,此时z=60x+100y取最大值,为了得到M点坐标解方程组(°层+。