数学规划方法建模市公开课一等奖百校联赛特等奖课件.pptx

MathematicalModelingDepartmentofMathematicsHUST第六章第六章 数学规划方法建模数学规划方法建模 6.1 线性规划模型线性规划模型 6.2 非线性规划模型非线性规划模型6.3 整数规划模型整数规划模型第六章第六章 数学规划方法建模数学规划方法建模 第1页 MathematicalModelingDepartmentofMathematicsHUST6.1线性规划模型线性规划模型6.1.1 引例及线性规划模型引例及线性规划模型某工厂制造甲某工厂制造甲,乙乙 两种产品，资料以下：两种产品，资料以下：问问：甲，乙：甲，乙两种各应生产多少吨，才能赢利最大？两种各应生产多少吨，才能赢利最大？单单位消耗位消耗产产品品原料原料甲（吨）甲（吨）乙（吨）乙（吨）现现有原料有原料总总量量钢钢材（吨）材（吨）电电力（千瓦力（千瓦时时）工作日（个）工作日（个）9545310360200330单位产品利润 （万元/吨）712例例6.1生产计划问题生产计划问题第2页 MathematicalModelingDepartmentofMathematicsHUST 设生产甲设生产甲产品产品吨，设生产吨，设生产 乙乙 产品产品吨，吨，且且甲甲乙乙现现有原料有原料总总量量钢钢材材电电力力工作日工作日9545310360200330利利润润7126.1线性规划模型线性规划模型6.1.1 引例及线性规划模型引例及线性规划模型表示利润，则表示利润，则解解第3页 MathematicalModelingDepartmentofMathematicsHUST写成线性规划数学模型为：写成线性规划数学模型为：目标函数目标函数约束条件约束条件解解 6.1.1引例及线性规划模型引例及线性规划模型线性函数线性函数线性不等式线性不等式线性规划模型，简写成线性规划模型，简写成LP第4页 MathematicalModelingDepartmentofMathematicsHUST问：怎样调用，才能使运费最省？问：怎样调用，才能使运费最省？例例6.2 运输问题运输问题 6.1.1引例及线性规划模型引例及线性规划模型 有有m个产地个产地 A1，A2，Am生产某种产品生产某种产品，n 个销地个销地B1，B2，Bn ,需要该种物资。需要该种物资。第第i个产地个产地Ai产量为产量为ai 而第而第j个销地个销地Bj销量为销量为bj 已知由产地已知由产地Ai到销地到销地Bj单位运价为单位运价为ci j 且且（称为产销平衡问题）。（称为产销平衡问题）。第5页 MathematicalModelingDepartmentofMathematicsHUST设设运到运到 物资为物资为 ,表示运费，则表示运费，则 6.1.1引例及线性规划模型引例及线性规划模型解解可得线性规划数学模型可得线性规划数学模型满足产量限制、满足产量限制、销量限制、非负销量限制、非负限制等限制等第6页 MathematicalModelingDepartmentofMathematicsHUST 6.1.1引例及线性规划模型引例及线性规划模型线性规划模型普通形式为线性规划模型普通形式为(以最小目标为例以最小目标为例)解解写成矩阵形式为写成矩阵形式为目标函数系数向量目标函数系数向量决议变量决议变量约束方程组系数矩阵约束方程组系数矩阵可行域可行域第7页 MathematicalModelingDepartmentofMathematicsHUST线性规划模型标准形为线性规划模型标准形为非标准形线性规划都能够化为标准形非标准形线性规划都能够化为标准形第8页 MathematicalModelingDepartmentofMathematicsHUST6.1.2线性规划模型解法线性规划模型解法 6.1.2.1两个变量线性规划模型图解法两个变量线性规划模型图解法 用图解法求下面线性规划模型最优解用图解法求下面线性规划模型最优解例例6.3 第9页 MathematicalModelingDepartmentofMathematicsHUSTC(4,2)1)求可行域求可行域6.1.2线性规划模型解法线性规划模型解法 解解第10页 MathematicalModelingDepartmentofMathematicsHUST表示以表示以为参数一簇平行线，位于为参数一簇平行线，位于同一条直线点同一条直线点,函数值相同函数值相同称为等值线。称为等值线。越往上移动，越往上移动，值越大值越大。由图知：在可行域由图知：在可行域 C(4,2)处，处，到达最大值。到达最大值。最大值为：最大值为：2）求目标函数最优值。）求目标函数最优值。A B D L1 L2 L3 L4 L5解解6.1.2线性规划模型解法线性规划模型解法 第11页 MathematicalModelingDepartmentofMathematicsHUSTA(1,0)在点在点A（1,0）处到达最优。处到达最优。用图解法求下面线性规划模型最优解用图解法求下面线性规划模型最优解例例6.4 6.1.2线性规划模型解法线性规划模型解法 第12页 MathematicalModelingDepartmentofMathematicsHUST由上面两个例子可知：由上面两个例子可知：1 1）线性规划模型可行域是凸集；）线性规划模型可行域是凸集；2 2）当）当线线性性规规划模型可行域有界划模型可行域有界时时，其最其最优优解可在其可行域解可在其可行域顶顶点上到达。点上到达。6.1.2线性规划模型解法线性规划模型解法 第13页 MathematicalModelingDepartmentofMathematicsHUST求解线性规划模型一个惯用方法就是求解线性规划模型一个惯用方法就是单纯形单纯形法法，单纯形法是经过迭代来求问题最优解，单纯形法是经过迭代来求问题最优解:最最优解一定能在可行域顶点上到达。优解一定能在可行域顶点上到达。当前，求解线性规划模型有不少现成数学软当前，求解线性规划模型有不少现成数学软件，比如件，比如LINDO软件、软件、LINGO软件及软件及MATLAB等。等。6.1.2.2用数学软件包求解线性规划模型用数学软件包求解线性规划模型我们对于单纯形法不做详细介绍，着重介我们对于单纯形法不做详细介绍，着重介绍用数学软件包来求解线性规划模型。绍用数学软件包来求解线性规划模型。6.1.2线性规划模型解法线性规划模型解法 第14页 MathematicalModelingDepartmentofMathematicsHUST例例6.6 某厂用甲、乙、丙三种原料生产某厂用甲、乙、丙三种原料生产A、B、C三种产品，三种产品，每种产品消耗原料定额如表每种产品消耗原料定额如表6.2所表示。问怎样组织生产，才所表示。问怎样组织生产，才能使利润最大？能使利润最大？产品产品定额（千克定额（千克/万件）万件）原料原料ABC现有原料总量（千克）现有原料总量（千克）甲甲乙乙丙丙3 31 12 22 21 11 112122 21 130307 71414单位产品利润（万元/万件）12128 83535表表6.2 三种三种产产品品额额定消耗与利定消耗与利润润并深入回答以下问题：并深入回答以下问题：1）若产品）若产品A价格降低了价格降低了2（万元（万元/万件），是否改变生产计划？万件），是否改变生产计划？2）若产品）若产品C价格上涨了价格上涨了3（万元（万元/万件），是否改变生产计划？万件），是否改变生产计划？3）若市场上还能够买到原料甲，其价格为）若市场上还能够买到原料甲，其价格为1（万元（万元/千克），是否购千克），是否购 买，最多能够买多少千克？买，最多能够买多少千克？第15页 MathematicalModelingDepartmentofMathematicsHUST打开打开LINDO执行文件，执行文件，编程以下：编程以下：max2x1+2x2st2)x143)x234)x1+2x28end例例6.5 用用LINDO软件软件求线性规划模型例求线性规划模型例6.3最优解最优解解：解：LINDO中已要求全部决议变量均为非中已要求全部决议变量均为非负，所以模型中第四个约束条件不负，所以模型中第四个约束条件不必输入；必输入；式中不能有括号，右端不能有数学符式中不能有括号，右端不能有数学符号；号；不等号不等号写成写成（二者与（二者与等价）；等价）；程序中第程序中第1行为目标函数，标号行为目标函数，标号2）,3）,4）是标示各约束条件，方便从输）是标示各约束条件，方便从输出结果中查找对应信息（标号能够出结果中查找对应信息（标号能够省略）；省略）；程序以程序以“end”结束。结束。6.1.2线性规划模型解法线性规划模型解法 第16页 MathematicalModelingDepartmentofMathematicsHUST输入程序后，选择菜单输入程序后，选择菜单“Solve”进行求解，若对提醒进行求解，若对提醒:“DORANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？是否进行灵敏性分析？)回答回答“否（否（N）”，则可得到以下输出：，则可得到以下输出：LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)12.00000VARIABLEVALUEREDUCEDCOSTX14.0000000.000000X22.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0000003)1.0000000.0000004)0.0000001.000000NO.ITERATIONS=2从上面输出我们从上面输出我们得到：模型最优得到：模型最优解为解为最优值最优值例例6.5用用LINDO软件软件求线性规划模型例求线性规划模型例6.3最优解最优解第17页 MathematicalModelingDepartmentofMathematicsHUST6.1.2.3线性规划模型灵敏性分析线性规划模型灵敏性分析灵敏度分析是指因为系统环境发生改变，灵敏度分析是指因为系统环境发生改变，而引发系统目标改变敏感程度。而引发系统目标改变敏感程度。对于线性规划模型对于线性规划模型(3)，我们总假设，我们总假设A，b，c都是常数向量，但实际上这些数值往都是常数向量，但实际上这些数值往往是往是经过测量和预测经过测量和预测得到，实际中各种原得到，实际中各种原因都能引发它们改变。因都能引发它们改变。现在问题是：这些参数在多大范围内现在问题是：这些参数在多大范围内 改变时，使线性规划模型最优解不变。改变时，使线性规划模型最优解不变。6.1.2.36.1.2.3线性规划模型灵敏性分析线性规划模型灵敏性分析线性规划模型灵敏性分析线性规划模型灵敏性分析第18页 MathematicalModelingDepartmentofMathematicsHUST1）市场条件改变市场条件改变。目标函数系数目标函数系数改变，即第改变，即第j种产品价格变动。种产品价格变动。2）资源条件改变资源条件改变。约束条件右端常数项约束条件右端常数项改变改变,即第即第i种原料数量变动。种原料数量变动。3）工艺技术条件改变工艺技术条件改变。系数矩阵中系数矩阵中改变，即单位产品所需耗材变动。改变，即单位产品所需耗材变动。我们要研究是上述三种改变引发生产计划改变及利润我们要研究是上述三种改变引发生产计划改变及利润改变情况。在什么条件下，要改变生产计划。改变情况。在什么条件下，要改变生产计划。6.1.2.3线性规划模型灵敏性分析线性规划模型灵敏性分析灵敏度分析主要研究下面几个问题：灵敏度分析主要研究下面几个问题：第19页 MathematicalModelingDepartmentofMathematicsHUST1.1.建立数学模型建立数学模型设设A、B、C三种产品计划三种产品计划生产量分别为万件，利润生产量分别为万件，利润为为z万元，则可得以下线性万元，则可得以下线性规划模型规划模型应用应用LINDO软件来求解模型软件来求解模型.打开打开LINDO执行文件，编程执行文件，编程以下：以下：max12x1+8x2+35x3st2)3x1+2x2+12x3303)x1+x2+2x374)2x1+x2+x314end2.2.模型求解模型求解例例6.6 求解求解第20页 MathematicalModelingDepartmentofMathematicsHUST选择菜单选择菜单“Solve”进行求解，若对提醒进行求解，若对提醒:“DORANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？是否进行灵敏性分析？)回答回答“是（是（Y）”，则可以下输出：，则可以下输出：LP OPTIMUM FOUND AT STEP 2LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE 1)100.5000 1)100.5000 VARIABLE VALUE REDUCED COST VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X1 4.000000 0.000000 X2 0.000000 2.166667 X2 0.000000 2.166667 X3 1.500000 0.000000 X3 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES ROW SLACK OR SURPLUS DUAL PRICES 2)0.000000 1.833333 2)0.000000 1.833333 3)0.000000 6.500000 3)0.000000 6.500000 4)4.500000 0.000000 4)4.500000 0.000000 NO.ITERATIONS=2 NO.ITERATIONS=2例例6.6 求解求解从左面输出第从左面输出第17行行我们得到：我们得到：线性规划模型线性规划模型(4)最优解最优解为为最优值最优值即即A、B、C三种产品三种产品生产量分别为生产量分别为4,0和和1.5万件，利润为万件，利润为100.5万元。万元。3.结果分析。结果分析。普通将三个约束条件右端看作三种普通将三个约束条件右端看作三种“资源资源”，上，上面输出面输出第第811行行“SLACKORSURPLUS”给出了三种资源在最优给出了三种资源在最优解下是否有剩下：解下是否有剩下：2）原料甲，）原料甲，3)原料乙剩下均为零，原料乙剩下均为零，4）原料丙剩下）原料丙剩下4.5千克。千克。我们称我们称“资源资源”剩下为零约束为紧约束（或称为有效约束）剩下为零约束为紧约束（或称为有效约束）第21页 MathematicalModelingDepartmentofMathematicsHUST选择菜单选择菜单“Solve”进行求解，若对提醒进行求解，若对提醒:“DORANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？是否进行灵敏性分析？)回答回答“是（是（Y）”，则可以下输出：，则可以下输出：LP OPTIMUM FOUND AT STEP 2LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE OBJECTIVE FUNCTION VALUE 1)100.5000 1)100.5000 VARIABLE VALUE REDUCED COST VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X1 4.000000 0.000000 X2 X2 0.000000 0.000000 2.166667 2.166667 X3 1.500000 0.000000 X3 1.500000 0.000000 ROW SLACK OR SURPLUS ROW SLACK OR SURPLUS DUAL PRICESDUAL PRICES 2)0.000000 1.833333 2)0.000000 1.833333 3)0.000000 6.500000 3)0.000000 6.500000 4)4.500000 0.000000 4)4.500000 0.000000 NO.ITERATIONS=2 NO.ITERATIONS=2例例6.6 求解求解在经济学上，把在最优解下某种在经济学上，把在最优解下某种“资源资源”增加增加1个单个单位时位时“效益效益”增量，称为该种增量，称为该种“资源资源”影子价格影子价格。在本。在本问题中，原料甲影子价格为问题中，原料甲影子价格为1.833333万元，原料乙影子万元，原料乙影子价格为价格为6.5万元，原料丙影子价格为万元，原料丙影子价格为0。目标函数能够看作目标函数能够看作“效益效益”,成为成为紧约束紧约束“资源资源”一旦增加一旦增加,就必定会引发就必定会引发“效益效益”增加增加.第第811行行“DUALPRICES”给出给出3种原料在最优解下种原料在最优解下“资源资源”增增加加1个单位时个单位时“效益效益”增量：增量：2）原料甲增加）原料甲增加1千克时，千克时，利润增加利润增加1.833333万元；万元；3）原料乙增加）原料乙增加1 1千克时，千克时，利润增加利润增加6.5万元；万元；4）增加原料丙）增加原料丙(非紧约非紧约束束)不会使利润增加。不会使利润增加。第22页 MathematicalModelingDepartmentofMathematicsHUSTRANGES IN WHICH THE BASIS IS UNCHANGED:RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES OBJ COEFFICIENT RANGES VARIABLE VARIABLE CURRENT ALLOWABLECURRENT ALLOWABLE ALLOWABLEALLOWABLE COEF COEF INCREASE DECREASEINCREASE DECREASE X1 12.000000 5.500000 1.625000 X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINITY X2 8.000000 2.166667 INFINITY X3 35.000000 13.000000 11.000000 X3 35.000000 13.000000 11.000000RIGHTHAND SIDE RANGESRIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000 4 14.000000 INFINITY 4.500000例例6.6 求解求解目标函数系数发生改变时目标函数系数发生改变时(假定约束条件不变假定约束条件不变),),最优最优解和最优值是否会改变解和最优值是否会改变,这这是灵敏性分析任务。是灵敏性分析任务。输出第输出第1419行行“CURRENTCOEF”“ALLOWABLEINCREASE”与与“ALLOWABLEDECREASE”给出了最优解不变条件下目标给出了最优解不变条件下目标函数系数允许改变范围：函数系数允许改变范围：系数为系数为:系数为系数为:系数为系数为:注意：注意：系数允许改变范围是指在系数允许改变范围是指在和和系数不变条件下系数不变条件下,其余相同其余相同.第23页 MathematicalModelingDepartmentofMathematicsHUSTRANGES IN WHICH THE BASIS IS UNCHANGED:RANGES IN WHICH THE BASIS IS UNCHANGED:OBJ COEFFICIENT RANGES OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE COEF INCREASE DECREASE X1 12.000000 5.500000 1.625000 X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINITY X2 8.000000 2.166667 INFINITY X3 35.000000 13.000000 11.000000 X3 35.000000 13.000000 11.000000RIGHTHAND SIDE RANGESRIGHTHAND SIDE RANGES ROW ROW CURRENT ALLOWABLE ALLOWABLECURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000 4 14.000000 INFINITY 4.500000例例6.6 求解求解目标函数系数发生改变时目标函数系数发生改变时(假定约束条件不变假定约束条件不变),),最优最优解和最优值是否会改变解和最优值是否会改变,这是灵敏性分析任务。这是灵敏性分析任务。对对“资源资源”影子价格影子价格做深入分析，影子价格作用是有限制。做深入分析，影子价格作用是有限制。输出第输出第2025行行“CURRENTRHS”“ALLOWABLEINCREASE”与与“ALLOWABLEDECREASE”给出了影子价格有意义条件下约束右端限制范给出了影子价格有意义条件下约束右端限制范围。围。2原料甲范围原料甲范围3原料乙范围原料乙范围4原料丙范围原料丙范围第24页 MathematicalModelingDepartmentofMathematicsHUST1）若产品）若产品A价格降低了价格降低了2（万元（万元/万件），则产品万件），则产品A利润变利润变成了成了10万元万元/万件，在允许范围万件，在允许范围(12-1.625,12+5.5)之外，应该之外，应该改变生产计划。改变生产计划。2）若产品）若产品C价格上涨了价格上涨了3（万元（万元/万件），则产品万件），则产品C利润变利润变成了成了38万元万元/万件，在允许范围万件，在允许范围(35-11,35+13)内内，所以，不，所以，不应改变生产计划。应改变生产计划。3）因为原料甲影子价格为）因为原料甲影子价格为1.833333万元，所以，应该在市万元，所以，应该在市场上以场上以1（万元（万元/千克）价格购置原料甲，但最多只能够买千克）价格购置原料甲，但最多只能够买12千克。千克。经过以上灵敏性分析我们能够对问题经过以上灵敏性分析我们能够对问题 1),2),3)1),2),3)给出解答给出解答.例例6.6 求解求解第25页 MathematicalModelingDepartmentofMathematicsHUST6.1.3 线性规划模型实例线性规划模型实例例6.7 投资方案确定某部门要进行投资，现有四个投资项目：某部门要进行投资，现有四个投资项目：项目项目A：从第一年到第四年每年年初需要投资，并从第一年到第四年每年年初需要投资，并于第二年年末回收本利于第二年年末回收本利115；项目项目B：从第三年年初从第三年年初需要投资，到第五年末回收本利需要投资，到第五年末回收本利125，但要求最大投，但要求最大投资额不超出资额不超出40万元；万元；项目项目C：第二年初需要投资，到第第二年初需要投资，到第五年末才能回收本利五年末才能回收本利140，但要求最大投资额不超出，但要求最大投资额不超出30万元；万元；项目项目D：五年内每年年初可买公债，于当年年五年内每年年初可买公债，于当年年末偿还，并可取得末偿还，并可取得6利息。利息。已知该部门现有资金已知该部门现有资金100100万元，试为该部门确定投资方万元，试为该部门确定投资方案，使得第五年末它拥有资金本利总额最大？案，使得第五年末它拥有资金本利总额最大？第26页 MathematicalModelingDepartmentofMathematicsHUST1）决策变量 决策变量为每年年初向四个项目投资额，设第 i年年初向年年初向A、B、C、D四个项目投资额为 (万元)2）目标函数目标函数设第五年年末拥有资金本利总额为设第五年年末拥有资金本利总额为z，将，将全部可能投资列于表全部可能投资列于表6.3。求解例求解例6.76.1.3 线性规划模型实例线性规划模型实例1.模型建立模型建立第27页 MathematicalModelingDepartmentofMathematicsHUST年份年份项目项目1 12 23 34 45 5投资限额投资限额（万元）万元）AB4040C3030D表表6.3可能投资方案可能投资方案目目标标函函数数应应该该是是四四项项投投资资在在第第五五年年年年末末回回收收本本利利之和，之和，于是，目于是，目标标函数函数为为6.1.3 线性规划模型实例线性规划模型实例第28页 MathematicalModelingDepartmentofMathematicsHUST3）约束条件）约束条件(a)为了取得最大投资收益，每年年初应将手头全部资金投为了取得最大投资收益，每年年初应将手头全部资金投出去，所以第一年投资总额应是出去，所以第一年投资总额应是100万元，万元，(b)第二年投资总额应是第一年年底回收各项投资本利，即第二年投资总额应是第一年年底回收各项投资本利，即同理，第三、四、五年投资总额应是上一年年底回收各项同理，第三、四、五年投资总额应是上一年年底回收各项投资本利，即投资本利，即6.1.3 线性规划模型实例线性规划模型实例第29页 MathematicalModelingDepartmentofMathematicsHUST（c）因为投资限制，所以还有）因为投资限制，所以还有由此得投资问题数学模型为由此得投资问题数学模型为6.1.3 线性规划模型实例线性规划模型实例第30页 MathematicalModelingDepartmentofMathematicsHUST用用LINDO软件求解，为了能应用软件求解，为了能应用LINDO软件，编制软件，编制程序时应将各约束条件右端决议变量移到左端。求得程序时应将各约束条件右端决议变量移到左端。求得投资方案最优解为投资方案最优解为其余决议变量均为零。其余决议变量均为零。最优值最优值2.模型求解模型求解6.1.3 线性规划模型实例线性规划模型实例第31页 MathematicalModelingDepartmentofMathematicsHUST一喂养场喂养供试验用动物，已知动物生长对饲料中三种营养一喂养场喂养供试验用动物，已知动物生长对饲料中三种营养成份成份蛋白质、矿物质和维生素尤其敏感，每个动物天天最少蛋白质、矿物质和维生素尤其敏感，每个动物天天最少需要蛋白质需要蛋白质70g、矿物质、矿物质3g、维生素、维生素10mg，该场能搞到五种饲料，该场能搞到五种饲料，每种饲料每种饲料10kgkg成本如表成本如表6.4。每一千克饲料中所含营养成份如表。每一千克饲料中所含营养成份如表6.5。表表6.4饲料饲料A1A2A3A4A5成本（元）成本（元）2 27 74 43 35 5饲料饲料蛋白质（蛋白质（g）矿物质矿物质(g)维生素维生素(mg)A10.030.100.05A22.000.050.10A31.000.020.02A40.600.200.20A51.800.050.08表表6.5试确定既能满足需要试确定既能满足需要,又使总成本为最低饲料配方又使总成本为最低饲料配方,建立数学模型建立数学模型.6.1.3 线性规划模型实例线性规划模型实例例例6.8 配料问题配料问题 第32页 MathematicalModelingDepartmentofMathematicsHUST1）决议变量。设动物天天食用混合饲料中所含第）决议变量。设动物天天食用混合饲料中所含第j 种饲料种饲料Aj数量为数量为kg2）目标函数。设混合饲料总成本为）目标函数。设混合饲料总成本为z，则，则3）约束条件。）约束条件。（a a）蛋白质限制）蛋白质限制；（b b）矿物质限制）矿物质限制；（c c）维生素限制）维生素限制。6.1.3 线性规划模型实例线性规划模型实例例例6.8 配料问题配料问题 1.模型建立模型建立第33页 MathematicalModelingDepartmentofMathematicsHUST由此上述问题数学模型为由此上述问题数学模型为2.模型求解模型求解用用LINDO软件求解，得到最优解为：软件求解，得到最优解为：最优值最优值6.1.3 线性规划模型实例线性规划模型实例例例6.8 配料问题配料问题 第34页 MathematicalModelingDepartmentofMathematicsHUST怎样怎样装装运运,使此使此次飞行次飞行赢利最赢利最大？大？三个货舱三个货舱最大最大载载重重(吨吨),),最大容积最大容积(米米3 3)重量（吨）重量（吨）空间空间(米米3/吨）吨）利润（元利润（元/吨）吨）货物货物1184803100货物货物2156503800货物货物3235803500货物货物4123902850三个货舱中实际载重必须与其最大三个货舱中实际载重必须与其最大载载重成百分重成百分比比前仓：前仓：10;6800中仓：中仓：16；8700后仓：后仓：8;5300飞机平衡飞机平衡6.1.3 线性规划模型实例线性规划模型实例例例6.9货机装运货机装运第35页 MathematicalModelingDepartmentofMathematicsHUST决议决议变量变量 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量(吨）吨）i=1,2,3,4,j=1,2,3(分别代表前、中、后仓分别代表前、中、后仓)模型假设模型假设 每种货物能够分割到任意小；每种货物能够分割到任意小；每种货物能够在一个或多个货舱中任意分布；每种货物能够在一个或多个货舱中任意分布；各种货物能够混装，并确保不留空隙；各种货物能够混装，并确保不留空隙；模型建立模型建立 6.1.3 线性规划模型实例线性规划模型实例例例6.9货机装运货机装运第36页 MathematicalModelingDepartmentofMathematicsHUST货货舱舱容容积积目标函数目标函数(利润利润)约束约束条件条件模型建立模型建立 货货舱舱重重量量10；680016；87008；5300 xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量6.1.3 线性规划模型实例线性规划模型实例例例6.9货机装运货机装运第37页 MathematicalModelingDepartmentofMathematicsHUST约束约束条件条件平平衡衡要要求求 货货物物供供给给xij-第第i 种货物装入第种货物装入第j 个货舱重量个货舱重量模型建立模型建立 6.1.3 线性规划模型实例线性规划模型实例例例6.9货机装运货机装运10；680016；87008；5300第38页 MathematicalModelingDepartmentofMathematicsHUSTOBJECTIVEFUNCTIONVALUE1)121515.8VARIABLEVALUEREDUCEDCOSTX110.000000400.000000X120.00000057.894737X130.000000400.000000X2110.0000000.000000X220.000000239.473679X235.0000000.000000X310.0000000.000000X3212.9473690.000000X333.0000000.000000X410.000000650.000000X423.0526320.000000X430.000000650.000000货物货物2：前仓：前仓10,后仓后仓5；货物货物3:中仓中仓13,后仓后仓3；货物货物4:中仓中仓3。模型求解模型求解 最大利润约最大利润约121516元元货物货物供给点供给点货舱货舱需求点需求点平衡要求平衡要求运输运输问题问题运输问题扩展运输问题扩展6.1.3 线性规划模型实例线性规划模型实例例例6.9货机装运货机装运第39页