数学建模 第一篇第一章

1、 第一篇线性规划模型及应用第一章线性规划问题的数学模型及其解的性质1-1-1线性规划问题的数学模型引例：某工厂生产某种型号的机床，每台机床上需要2.9米、2.1米和1.5米长的三种轴各一根，这些轴需要用同一种圆钢制作，圆钢的长度为7.4米。如果要生产100台机床，应如何下料，才能使得用料最省？分析：对于每一根长为7.4米的圆钢，截成2.9米、2.1米和1.5米长的毛坯，可以有若干种下料方式，把它截成我们需要的长度，有以下8种下料方式（表1-1-1）：下料方式是从大到小、从长到短的顺序考虑的。1假若考虑只用B方式下料，需要用料100根；3若采用木工师傅的下料方法：先下最长的、再下次长的、最后下短

2、的（见表1-1-2）：表1-1-2木工师傅的下料情况的用料表下料方式B1B5B8B合计下料根数2.9米根数2.1米根数1.5米根数50100050330990120048102296100101100动一下脑筋，就可以节约用料4根，降低成本。但这仍然不是最好的下料方法。如果要我们安排下料，暂不排除8种下料方式中的任何一种，通过建立数学模型（线性规划数学模型）进行求解，寻找最好的下料方案。设用B,B,B,B,B,B,B,B方式下料的根数分别为x,x,x,x,x,x,x,x，则可以建TOC o 1-5 h z1234567812345678立线性规划数学模型:minS=X1+X2+X3+X4+X5

3、+X6+X7+X82x+x+x+x10012342x+x+3x+2x+x100s.t.q23567Ix+x+3x+2x+3x+4x100134678Ix1，x2,x3,x4,x5,x6,x7,x80用LINGO10.0软件求解，程序如下：Min=x1+x2+x3+x4+x5+x6+x7+x8;2*x1+x2+x3+x4=100;2*x2+x3+3*x5+2*x6+x7=100;x1+x3+3*x4+2*x6+3*x7+4*x8=100;根据输出结果，得：x=40,x=20,x=0,x=0,x=0,x=30,x=0,x=0,minS=90（最优解12345678不唯一）；或x=10,x=50,x

4、=0,x=30,x=0,x=0,x=0,x=0,minS=90。这就是最优的下料方12345678案。下料问题是在经济管理中经常遇到的问题，引例是条材下料问题、还有板材下料问题（如五金厂生产保险柜、服装厂下料等）或者更复杂的下料问题。请考虑一下，下料方式能不能用计算机来设计？本问题能不能将目标函数确定为余料最少？这都是值得读者思考的问题。在生产管理和经营活动中，经常考虑这样一类问题：如何合理地利用有限的人力、物力和财力等资源，以便得到最好的经济效果。下面分四个方面介绍典型的建立线性规划模型的方法。一、合理下料问题例1某工厂生产某种型号的机床，每台机床上需要2.9米、2.1米和1.5米长的三种轴

5、分别为1根、2根、1根，这些轴需要用同一种圆钢制作，圆钢的长度为7.4米。如果要生产100台机床，应如何下料，才能使得用料最省？关于下料方式的分析如引例，下料方式见表1-1-1，该问题的数学模型为：设用B,B,B,B,B,B,B,B方式下料的根数分别为x,x,x,x,x,x,x,x，贝V：TOC o 1-5 h z1234567812345678minS=x+x+x+x+x+x+x+x123456782x+x+x+x10012342x+x+3x+2x+x200S.t.Q23567x+x+3x+2x+3x+4x100134678x,x,x,x,x,x,x,x012345678可以用LINGO10

6、.0求解，得x=20,x=60,x=0,x=0,x=0,x=40,x=0,x=0;minS=120。12345678注：本题的最优解不唯一。一般下料问题：设用某种材料（条材或板材）下零件A,A,A的毛坯，根据过去的经验，在12m一件原料上有B,B2,B种不同的下料方式，每种合理的下料方式可得各种毛坯个数及每种零件的12n需要量如表1-1-3。问：应怎样安排下料方式，既能满足需要，又使得用料最省？设用B方式下料的数量为x（j=1,2,n），则建立线性规划问题数学模型:jj 123 minS=x+xHbx12ncx+cxHbcxa1111221nn1cx+cxHbcxa2112222nn2s.t.

7、am11m22mnnmx,x，,x0,整数12n或者S工minS=xjj=1厶c.x.a.(i=1,2,m)s.t.0,j=1,2,nj建立线性规划问题数学模型的基本要素：决策变量明确问题中有待确定的未知变量（称为决策变量），并用数学符号表示；约束条件明确问题中所有的限制条件（约束条件）并且用决策变量的一些表达式（线性等式或线性不等式）来表示；目标函数明确解决问题要达到的目标，并用决策变量的线性函数（称为目标函数）表示，按问题的要求，求其最大值或最小值。通常把决策变量、约束条件和目标函数称为线性规划数学模型的三个基本要素。从我们所建立的数学模型来看，目标函数是决策变量的线性函数、约束条件是决策

8、变量的线性等式或不等式，因此我们称此为线性规划（LinearProgramming,简记为LP）模型。二、资源合理利用（资源的最优配置）问题例2某工厂要安排一种产品的生产，该产品有I、II、III三种型号，生产这种产品均需要两种主要资源：原材料和劳动力。每件产品所需资源数、现有资源数量以及每件产品的出售价格如表1-1-4。假定该产品只要生产出来即可销售出去，试确定这三种产品的日产量使总产值最大。表1-1-4资源利用问题的数据产品资源IIIIII现有资源数量原材料（公斤）436120公斤劳动力（小时）245100小时价格（元）453解：设该工厂计划日产产品I、II、III的数量分别为,x2,x3

9、件，则可建立线性规划数学模型:maxS=4x+5x+3x1234x+3x+6x120123s.t.l2x+4x+5x0,x0,x0123通过LINGO10.0求解，程序为：max=4*x+5*x+3*x123;4*x1+3*x2+6*x3=120;2*x+4*x+5*x=100;得到最优解：x=18,x=16,x=0,maxS=152123一般地，用m种资源A,A，,A可以生产n种产品B,B，,B。现有原料数a（可利用资源12m12ni数量）、每单位产品所需原料数c（消耗系数）及每单位产品可得利润b（i=1,2,m;j=1,2,n）如ijj表1-1-5。问：应如何组织生产才能使总利润最大？表1

10、-1-5一般资源利用问题的数据资源产品B1B2Bn现有原料数Accca111121n1Accca221222n2Acccamm1m2mnm单位产品利润b1b2b设x表示生产产品B的数量（j=,n），则可建立线性规划数学模型:jjmaxS=bx+bxH+bx1122nncx+cxHHcxa1111221nn1cxHcxHHcxa2112222nn2StcxHcxHHcx012n这种类型的资源利用（或者称为资源配置）问题是最常见的，而且在经济分析中是最重要的。只要求出最优解，最优计划即可作出，并且可以进一步作经济分析和优化分析。三、配料问题（食谱问题）例3某公司饲养实验用的动物以供出售，已知这些动

11、物的生长对饲料中3种主要营养成分（蛋白质、矿物质和维生素）特别敏感，每个动物每天至少需要蛋白质70g，矿物质3g,维生素10mg，该公司能买到5种不同的饲料州,A2,A3,A4,A5，每种饲料1kg所含各种营养成分和成本如表1-1-6,求既能满足动物生长需要，又使总成本最低的饲料配方。表1-1-6配料（食谱）问题的数据饲料AAAAA吕养最低营养12345要求蛋白质（g）0.3210.61.870矿物质（g）0.10.050.020.20.053维生素（mg）0.050.10.020.20.0810成本（兀）0.20.70.40.30.5解：设配方中需要A的数量别为x（j=123,4,5）kg,

12、则可建立线性规划数学模型:jjminS=02x1H07x2H04x3H03x4H05x50.3x+2x+x+0.6x+1.8x70TOC o 1-5 h z1234501x+0.05x+0.02x+0.2x+0.05x3s.t.J123450.05x+0.1x+0.02x+0.2x+0.08x1012345x1,x2,x3,x4,x50通过LINGO10.0求解，程序为：Min=0.2*x+0.7*x+0.4*x+0.3*x+0.5*x12345;0.3*x+2*x+x+0.6*x+1.8*x=70;123450.1*x+0.05*x+0.02*x+0.2*x+0.05*x=3;TOC o 1

13、-5 h z123450.05*x+0.1*x+0.02*x+0.2*x+0.08*x=10;12345求解，得x1=0，x2=0，x3=0，x4=39.74，x5=25.64，minS=24.74。说明：该模型应该还要增加约束x+x+x+x+xa1111221nn1cxHcxHHcxa2112222nn2StcxHcxHHcxam11m22mnnmx,x，,x012n注：应该还要增加一个约束条件：xHxHHx0(i=1,2;j=1,2,3)ij用LINGO10.0编程：Min=50*x+60*x+70*x+60*x+110*x+60*x111213212223;x11+x12+x13=23;

14、x21+x22+x23=27;x11+x21=18;x12+x22=17;x13+x23=15;通过求解得：x11=6,x12=17,x13=0；x21=12,x22=0,x23=15；minS=2940一般地，某种物资有m个产地：A,A，,A，联合供应n个销地B,B，,B。各产地产量a、TOC o 1-5 h z12m12ni HYPERLINK l bookmark32 o Current Document 各销地销量b、产地A到销地B的单位产品运价c(i=1,2,m;j=1,2,n)如表1-1-9，应如何组jijij织供应才能使得总运费最省？表1-1-9一般运输问题的数据平衡表运价表J、

15、销地产地B1B2Bn产量（吨）B1B2BnA1a1c11c12cA2a2c21c22c2nnAaccc销量（吨）b1b2bTOC o 1-5 h z设x表示产地A供应销地B的数量（i=1,2,m；j=1,2,n）ijij当产销平衡（迟a=b）时，数学模型为：iji=1j=1mnminS=乙乙cxijiji=1j=1工x=ai=1,2,miji文1厶x.=b.j=1,2,nijji=1x.0i=1,2,.,m;j=1,2,.,nij当产销不平衡时，（产量大于销量区aXb）数学模型为:iji=1j=1minS=ijiji=1j=1厶xb)j=1,2，,nijjji=1x.0i=1,2,.,m;j=

16、1,2,.,nij类似的模型还有农作物布局问题：某农场要在B,B，,B这n块土地上种植m种农作物A,A，,A。土地B的面积b、农作12n12mjj物A的计划播种面积a以及作物A在土地B上的单产c(i=1,2,.,m;j=1,2,.,n)如表1-1-10。应如iiijij何安排种植计划，才使总产量最大？表1-1-10农作物布局问题的数据平衡表产量表土地作物B1B2Bn播种面积B1B2BnA1a1e11e12eA2a2e21eeAaeee土地面积b1b2bnTOC o 1-5 h z设x表示土地B种植农作物A的面积(i=1,2,m；j=1,2,n)，则线性规划模型:ijjimaxS=ijiji=1

17、j=1工x=ai=1,2,.,mjisJy?1几“厶x.=b.j=1,2,.,nijji=1x.0i=1,2,.,m;j=1,2,.,nij这个问题的数学模型与运输问题的数学模型相同，还有其它的问题也可以建立类似结构的数学模型，统称为(经典)运输问题，这类数学模型称为康希问题。关于运输问题有专门的求解方法运输问题的表上作业法将在本篇第四章中专门介绍。一般地，线性规划问题的数学模型具有以下形式:min(max)S=ex+ex+.+ex1122nnax+ax+.+ax=b(b,b,b)2112222nn222,s.t.b,0j=1,2,.,nj我们称满足所有约束条件的X=(x1,x2,.,x)T为

18、线性规划问题的可行解；使目标函数取到最小12n值(或最大值，与模型的目标函数要求一致)的可行解称为线性规划问题的最优解。线性规划问题的数学模型是描述实际问题的抽象数学形式，它反映了客观事物数量间的本质规律。建立线性规划数学模型，没有统一的方法，要具体问题具体分析。主要是抓住问题的本质，建立既简单又比较真实反映问题规律的模型。一般的线性规划问题通过计算机软件（Lingo或Matlab等）可以求出最优解。下面先介绍两个变量线性规划问题解的图解法，以便对线性规划的解有一个直观的认识。1-1-2两个变量线性规划问题的图解法例5某工厂在计划期内要安排生产A、B两种产品，已知生产单位产品所需设备台时及对甲

19、、乙两种原材料的消耗，有关数据如表1-1-11。问：应如何安排计划，使工厂获利最大？表1-1-11生产计划问题的数据、产品资源AB可利用资源设备128台时甲4016公斤乙0412公斤单位利润2百元3百元解：设计划生产A、B两种产品的数量分别为x,x,则建立线性规划问题的数学模型为:12maXS=2X1+3X2x+2x824x16s.t.14x22s.t.一2x+3x012解：该问题的可行解区域为无界区域EABCD，当目标函数的等值线向右上方移动时，目标函数值可无限增大（如图1-1-3），因此该问题无有界的最优解。maxS=+（只可能出现在可行解区域无界的情况）。图1-1-3例8用图解法求解线性

20、规划问题minS=2x+x12x+2x212s.t.一2x+3x012解：该问题的可行解区域仍为图1-1-3中的无界区域EABCD，当目标函数的等值线向右上方移动时，目标函数可无限增大。但本题是求目标函数的最小值，目标函数的等值线向左下方移动时，在B点有惟一的最优解（如图1-1-3）。最优解为：x=0,x=1,minS=1。12例9用图解法求解线性规划问题minS=3x+2x122x+x312x,x012解：满足四个约束条件的公共部分不存在（如图1-1-4），本题无可行解，当然亦无最优解。420-2242x2x11+x2=2图1-1-4x1-2x2=3通过以上举例，我们可以看出线性规划解的情况

21、：最优解惟一（例5、例8）有最优解91100250000；用于混合飞机汽油解：设标准汽油1，2，3，4用于混合飞机汽油1的数量分别为x,x,x,x12342的数量分别为x,x,x,x，则可建立数学模型：5678maxZ=x+x+x+x1234x+x380000TOC o 1-5 h z5x+x2622006x+x91x+x+x+x1234107.5x+93x+87x+108x、“门x+x+x+x7.11x+F1.38x+5.69x+28.45x12349.96x+x+x+x12347.11x+11.38x+5.69x+28.45x56782500005678s.t.x+x0说明：其中有4个约束

22、条件是分式不等式，可以化为线性不等式。整理以后就是线性规划模型。maxS=x+x+x+x1234x+x380000TOC o 1-5 h z5x+x2622006x+x4081007x+x0s.t.J12347.5x-7x-13x+8x056782.85x-1.42x+4.27x-18.49x012342.85x-1.42x+4.27x-18.49x05678x+x+x+x2500005678x,x,x,x,x,x,x,x012345678下面我们用LINGO10.0来解这一线性规划问题。输入语句Model:max=x1+x2+x3+x4;x1+x5=380000;x+x=262200;26x

23、3+x7=408100;x4+x8=0;12347.5*x5-7.0*x6-13.0*x7+8.0*x8=0;2.85*x-1.42*x+4.27*x-18.49*x=0;12342.85*x5-1.42*x6+4.27*x7-18.49*x8=0;x5+x6+x7+x8=250000;End说明：开头的Model:和结尾的End可以省略。LINGO规定变量非负的，我们可发现输入方式与我们的数学模型的书写形式基本一致。运行结930400.0果输出如下：Objectivevalue:Totalsolveriterations:VariableValueReducedCostX1264732.80

24、.000000X2132708.90.000000X3408100.00.000000X4124858.20.000000X5115267.20.000000X6129491.10.000000X70.0000000.000000X85241.7540.000000RowSlackorSurplusDualPrice1930400.01.00000020.0000001.00000030.0000001.00000040.0000001.00000050.0000001.00000065123700.0.00000070.0000000.00000080.0000000.00000094771

25、4.000.000000100.000000-1.000000下面给出其结果的一般解释：“Objectivevalue:930400.0”表示最优目标值为930400。“Totalsolveriterations:7”表示用单纯形方法迭代7次求得问题的最优解。“Value”给出最优解中各变量的值。“SlackorSurplus”给出松弛变量的值。本例中第10行松弛变量=0（模型第1行表示目标函数，所以第10行对应第9个约束，以此类推）。“ReducedCost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时，目标函数的变化率，其中基变量的reducecost值应为0,对于非

26、基变量x相应的reducecost值表示xjj增加一个单位（此时假定其他非基变量保持不变）时目标函数减小的量（max型问题）。本例中：X对应的reducecost值为0,表示当x有微小变动时，目标函数值不变。“DualPrice”（对偶价格）列出最优单纯形表中判别数所在行的松弛变量的系数，表示当对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格（影子价格）。若其数值为X，表示对应约束中不等式右端项若增加一个单位，目标函数将增加x个单位（max型问题）。本例中：第10行对应的对偶价格值应为-1，表示当约束x+x+x+x250000变为5678x+x+x+x250001

27、时，目标函数值=930400-1=9303995678当ReducedCost或DualPrice的值为0。表示当微小扰动不影响目标函数。有时，通过分析DualPrice，也可对产生不可行问题的原因有所了解。默认情况下LINGO的灵敏度分析的功能是关闭的。如果要看灵敏度分析结果，必须激活灵敏度分析功能才会在求解时给出灵敏度分析结果。想要激活它，必须运行LINGOIOptions命令，选择GengralSolver，在DualComputation列表框中，选择PricesandRanges（默认Prices）选项并确定。本题的灵敏度分析结果如下：Rangesinwhichthebasisisu

28、nchanged:ObjectiveCoefficientRanges（目标函数系数的灵敏度分析）CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX11.0000000.00.0X21.0000000.00.0X31.000000INFINITY0.0X41.00000015.131860.0X50.00.00.0X60.00.00.0X70.00.0INFINITYX80.00.01.162101RighthandSideRanges（约束条件右端常数项的灵敏度分析）RowCurrentAllowableAllowabl

29、eRHSIncreaseDecrease2380000.039519.5916741.753262200.033601.4179317.484408100.026377.2411174.245130100.02580.5306091.44660.05123700.INFINITY70.01890576.382470.080.047714.00112630.890.047714.00INFINITY10250000.0256061.0175607.2灵敏度分析：如果作灵敏度分析，则系统报告当目标函数的费用系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中INFI

30、NITY表示正无穷，如本例中，目标函数中xx4的变量系数为1,当它在1-0,1+15.13186=1,16.16186范围变化时，最4优基保持不变。第9个约束右端项为250000（飞机汽油2不低于250000），当它在250000-175607.2,250000+256061=74392.8,506061范围内变化时，最优基保持不变，对偶价格-1保持不变。例12两辆铁路平板车的装货问题（美国大学生数学建模竞赛1988年B题）有七种规格的包装箱要装到两辆铁路平板车上去。包装箱的宽和高是一样的，但厚度（t,以厘米计）及重量（w,以公斤计）是不同的。表1-1-14给出了每种包装箱的厚度、重量以及数量

31、。每辆平板车有10.2米长的地方可用来装包装箱（像面包片那样），载重为40吨。由于当地货运的限制，对C5、C6、C7类的包装箱的总数有一个特别的限制：这类箱子所占的空间（厚度）不能超过302.7厘米。试把包装箱（见表1-1-14）装到平板车上去使得浪费的空间最小。表1-1-147种规格的包装箱的厚度、重量及数量C1C2C3C4C5C6C7t（厘米）48.752.061.372.048.752.064.0w（公斤）200030001000500400020001000件数8796648解：设第i辆铁路平板车装载第j种规格的包装箱的数目为xji=1,2;j=123,4,5,6,7），则可以建立整数

32、规划模型。(略)用LINGOIO.O求解的程序如下：max=48.7*x11+48.7*x21+52*x12+52*x22+61.3*x13+61.3*x23+72*x14+72*x24+48.7*x15+48.7*x25+52*x16+52*x26+64*x17+64*x27;x11+x21=8;x12+x22=7;x13+x23=9;x14+x24=6;x15+x25=6;x16+x26=4;x17+x27=8;2*x11+3*x12+x13+0.5*x14+4*x15+2*x16+x17=40;2*x21+3*x22+x23+0.5*x24+4*x25+2*x26+x27=40;48.7

33、*x11+52*x12+61.3*x13+72*x14+48.7*x15+52*x16+64*x17=1020;48.7*x21+52*x22+61.3*x23+72*x24+48.7*x25+52*x26+64*x27=1020;48.7*x15+52*x16+64*x17+48.7*x25+52*x26+64*x2760%15%8.002000B6.002500C20%60%50%4.001200加工费（元千克）2.0161.2售价（元）1361149A1A2B1，B2，B3B1B2A22某厂生产三种产品I、II、III,每种产品都要经过A,B两道工序加工。设该厂有两种规格的设备能完成A工序，它们以A1，A2表示；有三种规格的设备能完成B工序，它们以B1,B2,B3表示。产品I可在A，B任何一种规格的设备上加工，产品II可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品III只能在A2与B2设备上加工。已知在各种设备的单位工时、原材料费