线性规划数学模型及图解法

第一章线性规划第一节线性规划的数学模型第三节图解法及几何理论第一章线性规划线性规划问题举例线性规划问题的数学模型线性规划问题的标准形将一般的线性规划模型化为标准形第一节线性规划的数学模型线性规划1-1例1：1B2BnB1A2AmA1c2cnc2ama1a11a12ana121a22ana21ma2mamna问：应如何选用各种原料即确定各种原料的数量，使每公斤混合饲料的成本最低？营养成分原料(营养问题)某饲料厂利用n种原料生产混合饲料，已知每种原料的单价为cj(元/公斤)，又知第j种原料含第i种营养成分的数量为aij(克/公斤)。要求每公斤混合饲料中含第i种营养成分的数量至少是ai(克)。线性规划1-11B2BnB1A2AmA1c2cnc2ama1a11a12ana121a22ana21ma2mamna例1：解：nnxcxcxc2211Smin121nxxx11212111axaxaxann22222121axaxaxannmnmnmmaxaxaxa2211njxj,,2,10，nx2x1x成本最低1B2BnB1A2AmA1c2cnc2ama1a11a12ana121a22ana21ma2mamna设每公斤混合饲料应取原料的数量为公斤jBjx线性规划1-1例2：（下料问题）某车间有一批长度为500厘米的条材，要截成长度分别为85厘米和70厘米的两种毛坯，其中长85厘米的毛坯需要3000根，长70厘米的毛坯需要5000根。问：应如何下料，才能使所用的原料数量最少？解：85厘米543210300070厘米1234575000余料长度520355065101B3B4B5B6B2B下料方式：线性规划1-1例2：解：85厘米543210300070厘米1234575000余料长度520355065101B3B4B5B6B2B5x1x6x4x3x2x654321xxxxxxSmin300002345654321xxxxxx500075432654321xxxxxx6,,2,10jxj，原料数量最少设用种下料方式的条材根数为根jBjx线性规划1-1例3：（最优国民经济计划问题）假设国民经济分三个部门，每个部门生产单位产值所消耗的各部门的产值、占用的资金数量及消耗的劳动量如下表。已知三个部门现有资金700个单位，劳动力200个单位。部门1部门2部门3部门10.01090.15180.0038部门20.13180.18220.0845部门30.05500.05990.0647资金占用量2.02.51.8劳动力消耗量0.20.30.2问：三个部门总产值，最终产品产值各为多少时可使国民经济的最终产品总值最大？700200线性规划1-1部门1部门2部门3部门10.01090.15180.0038部门20.13180.18220.0845部门30.05500.05990.0647资金2.02.51.8劳动力0.20.30.2解：Smax321yyy132110038.01518.00.0109yxxxx232120845.01822.00.1318yxxxx332130647.00599.00.0550yxxxx7008.15.22321xxx2002.03.02.0321xxx3,2,10jyxjj，，最终产品总值最大1y2y3y1x2x3x700200设是第j个部门的总产值jx设是第j个部门的最终产品产值jy例3：例4：(连续投资问题)某部门在今后5年内(每年年初)考虑给下列项目投资，已知：12345投资要求A√√√√次年末回收本利115%B√第5年末回收本利125%，最大投资额不超过40万元C√第5年末回收本利140%，最大投资额不超过30万元D√√√√√购买国债，当年归还，并加利息6%年初投资项目该部门现有资金100万元，问它应如何确定这些项目每年的投资额，使到第5年末拥有的资金本利总额为最大？12345投资要求A√√√√次年末回收本利115%B√第5年末回收本利125%，最大投资额不超过40万元C√第5年末回收本利140%，最大投资额不超过30万元D√√√√√购买国债，当年归还，并加利息6%年初投资项目(1)确定变量：分别表示第i年初项目A,B,C,D的投资额,,,iAiBiCiDxxxx1Ax2Ax3Ax4Ax3Bx2Cx1Dx2Dx3Dx4Dx5Dx(2)投资额应等于资金额：第一年：该部门年初有资金100万元，所以有11100ADxx（万元）12345投资要求A√√√√次年末回收本利115%B√第5年末回收本利125%，最大投资额不超过40万元C√第5年末回收本利140%，最大投资额不超过30万元D√√√√√购买国债，当年归还，并加利息6%年初投资项目1Ax2Ax3Ax4Ax3Bx2Cx1Dx2Dx3Dx4Dx5Dx第一年：该部门年初拥有资金100万元，所以有11100ADxx第二年：该部门年初拥有资金，所以有22211.06ACDDxxxx(2)投资额应等于资金额：1(16%)Dx第三年：该部门年初拥有资金，所以有333121.151.06ABDADxxxxx12(115%)(16%)ADxx12345投资要求A√√√√次年末回收本利115%B√第5年末回收本利125%，最大投资额不超过40万元C√第5年末回收本利140%，最大投资额不超过30万元D√√√√√购买国债，当年归还，并加利息6%年初投资项目1Ax2Ax3Ax4Ax3Bx2Cx1Dx2Dx3Dx4Dx5Dx(2)投资额应等于资金额：第三年：该部门年初拥有资金，所以有12(115%)(16%)ADxx第四年：该部门年初拥有资金，所以有44231.151.06ADADxxxx23(115%)(16%)ADxx333121.151.06ABDADxxxxx第五年：该部门年初拥有资金，所以有5341.151.06DADxxx34(115%)(16%)ADxx此外，3240,30BCxx12345投资要求A√√√√次年末回收本利115%B√第5年末回收本利125%，最大投资额不超过40万元C√第5年末回收本利140%，最大投资额不超过30万元D√√√√√购买国债，当年归还，并加利息6%年初投资项目1Ax2Ax3Ax4Ax3Bx2Cx1Dx2Dx3Dx4Dx5Dx(3)目标函数：4235max1.151.401.251.06ACBDZxxxx要求第5年末该部门拥有的资金额达到最大，因此(4)数学模型：4235max1.151.401.251.06ACBDZxxxx11100ADxx22211.06ACDDxxxx333121.151.06ABDADxxxxx44231.151.06ADADxxxx5341.151.06DADxxx3240,30BCxx11100ADxx12221.060DACDxxxx123331.151.060ADABDxxxxx23441.151.060ADADxxxx3451.151.060ADDxxx3240,30BCxx,,,0,iAiBiCiDxxxx1,2,3,4,5i第一章线性规划线性规划问题举例线性规划问题的数学模型线性规划问题的标准形将一般的线性规划模型化为标准形第一节线性规划的数学模型线性规划1-1二.线性规划的数学模型：例1：Sminnnxcxcxc221111212111axaxaxann22222121axaxaxannmnmnmmaxaxaxa2211121nxxxnjxj,,2,10，线性规划1-1例2：Smin654321xxxxxx300002345654321xxxxxx500075432654321xxxxxx6,,2,10jxj，线性规划1-1例3：Smax321yyy132110038.01518.00.0109yxxxx232120845.01822.00.1318yxxxx332130647.00599.00.0550yxxxx7008.15.22321xxx2002.03.02.0321xxx3,2,10jyxjj，，线性规划1-1)(LP11212111bxaxaxann22222121bxaxaxannmnmnmmbxaxaxa2211njxj,,2,10，nnxcxcxcS2211max(min)injjijbxa1mi,,2,1njxj,,2,10，njjjxcS1max(min)，，二.线性规划的数学模型：LinearProgramming则称为(LP)的最优解。线性规划1-1可行解：)(LP可行域：XDXDCXCX若，且对有，最优解：最优值：CXSnjjjxcS1min1nijjijaxbmi,,2,1njxj,,2,10，CX),,,(21ncccCnxxxX21若满足所有的约束条件，则称X为可行解。12(,,,)TnXxxx(LP)可行解的全体构成的集合称为可行域D。X第一章线性规划线性规划问题举例线性规划问题的数学模型线性规划问题的标准形将一般的线性规划模型化为标准形第一节线性规划的数学模型线性规划1-111212111bxaxaxann22222121bxaxaxannmnmnmmbxaxaxa2211njxj,,2,10，nnxcxcxcS2211minnjjjxcS1mininjjijbxa1mi,,2,1njxj,,2,10，)(LP三.线性规划的标准型：(max)1minnjjjScx1nijjijaxbmi,,2,1njxj,,2,10，注释：单纯形法是针对线性规划问题的标准形进行求解的。第一章线性规划线性规划问题举例线性规划问题的数学模型线性规划问题的标准形将一般的线性规划模型化为标准形第一节线性规划的数学模型四.将一般的线性规划数学模型化为标准形例1：2134maxxxS0,2210212121xxxxxx2134)min(xxS0,,0,22104321421321xxxxxxxxxx称为剩余变量4x称为松弛变量3xSS线性规划1-1X线性规划1-1四.将一般的线性规划数学模型化为标准形：例2：212maxxxS为自由变量212121043583xxxxxx212)min(xxS0,43432xxxxx43122)min(xxxS0,0,,43358836543164315431xxxxxxxxxxxxx第一章线性规划线性规划问题举例线性规划问题的数学模型线性规划问题的标准形将一般的线性规划模型化为标准形第一节线性规划的数学模型第一章线性规划第一节线性规划的数学模型第三节图解法及几何理论第一章线性规划图解法线性规划问题解的几种情况几何理论第三节图解法及几何理论线性规划1-3一.图解法：(只适用于二维的问题)例1：2143maxxxS12122122632122,0xxxxxxx1.画出可行域2.画出目标函数等值线3.移动等值线求最优解2143xxS