《则解MathematicalModeling写成线性规划的数学模型为目标函数课件》由会员分享，可在线阅读，更多相关《则解MathematicalModeling写成线性规划的数学模型为目标函数课件（39页珍藏版）》请在金锄头文库上搜索。
1、第六章 数学规划方法建模,6.1 线性规划模型,6.2 非线性规划模型,6.3 整数规划模型,第六章 数学规划方法建模,6.1 线性规划模型,6.1.1 引例及线性规划模型,某工厂制造甲,乙 两种产品，资料如下：,问：甲，乙 两种各应生产多少吨，才能获利最大？,例6.1生产计划问题,且,6.1 线性规划模型,6.1.1 引例及线性规划模型,表示利润，则,解,写成线性规划的数学模型为：,目标函数,约束条件,解,6.1.1 引例及线性规划模型,的线性函数,的线性不等式,线性规划模型，简写成LP,问：如何调用，才能使运费最省？,例6.2 运输问题,6.1.1 引例及线性规划模型,6.1.1 引例及线
2、性规划模型,解,可得线性规划的数学模型,6.1.1 引例及线性规划模型,线性规划模型的一般形式为(以最小目标为例),解,写成矩阵形式为,线性规划模型的标准形为,非标准形的线性规划都可以化为标准形,6.1.2 线性规划模型的解法,6.1.2.1 两个变量的线性规划模型的图解法,用图解法求下面的线性规划模型的最优解,例6.3,1) 求可行域,6.1.2 线性规划模型的解法,解,同一条直线的点,函数值相同 称为等值线。,越往上移动，,值越大。,最大值为：,2）求目标函数的最优值。,解,6.1.2 线性规划模型的解法,A(1 , 0),在点 A（1 , 0）处达到最优。,用图解法求下面的线性规划模型的
3、最优解,例6.4,6.1.2 线性规划模型的解法,由上面两个例子可知： 1）线性规划模型的可行域是凸集； 2）当线性规划模型的可行域有界时， 其最优解可在其可行域的顶点上达到。,6.1.2 线性规划模型的解法,求解线性规划模型的一种常用的方法就是单纯形法，单纯形法是通过迭代来求问题的最优解:最优解一定能在可行域的顶点上达到。 目前，求解线性规划模型有不少现成的数学软件，比如LINDO软件、LINGO软件及MATLAB等。,6.1.2.2 用数学软件包求解线性规划模型,6.1.2 线性规划模型的解法,例6.6 某厂用甲、乙、丙三种原料生产A、B、C三种产品，每种产品消耗原料定额如表6.2所示。问
4、如何组织生产，才能使利润最大？,表6.2 三种产品的额定消耗与利润,并进一步回答下列问题： 1）若产品A的价格降低了2（万元/万件），是否改变生产计划？ 2）若产品C的价格上涨了3（万元/万件），是否改变生产计划？ 3）若市场上还可以买到原料甲，其价格为1（万元/千克），是否购 买，最多可以买多少千克？,打开LINDO执行文件， 编程如下： max 2x1+2x2 st 2) x14 3) x23 4) x1+2x28 end,例6.5 用LINDO软件求线性规划模型例6.3的最优解,解：,LINDO中已规定所有决策变量均为非 负，因此模型中的第四个约束条件不 必输入； 式中不能有括号，右端不
5、能有数学符 号； 不等号 写成 （二者与 等价）； 程序中第1行为目标函数，标号 2）, 3）,4）是标示各约束条件，以便从输 出结果中查找相应信息（标号可以 省略）； 程序以“end”结束。,6.1.2 线性规划模型的解法,输入程序后，选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“否（N）”，则可得到如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 12.00000 VARIABLE VALUE REDUCED COST X1
6、4.000000 0.000000 X2 2.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.000000 3) 1.000000 0.000000 4) 0.000000 1.000000 NO. ITERATIONS= 2,从上面输出我们得到：模型的最优解为 最优值,例6.5 用LINDO软件求线性规划模型例6.3的最优解,6.1.2.3 线性规划模型的灵敏性分析,灵敏度分析是指由于系统环境发生变化， 而引起系统目标变化的敏感程度。 对于线性规划模型(3)，我们总假设A ， b ，c 都是常数向量，但实际上这些数
7、值往 往是通过测量和预测得到的，实际中多种原 因都能引起它们的变化。 现在的问题是：这些参数在多大的范围内 变化时，使线性规划模型的最优解不变。,6.1.2.3 线性规划模型的灵敏性分析,1）市场条件变化。 目标函数的系数 变化，即第 j 种产品的价格变动。 2）资源条件变化。 约束条件右端常数项 变化, 即第i种原料数量变动。 3）工艺技术条件变化。 系数矩阵中 变化，即单位产品所需耗材变动。 我们要研究的是上述三种变化引起生产计划的改变及利润的变化情况。在什么条件下，要改变生产计划。,6.1.2.3 线性规划模型的灵敏性分析,灵敏度分析主要研究下面几个问题：,1. 建立数学模型,设A、B、
8、C三种产品计划生产量分别为万件，利润为z万元，则可得如下线性规划模型,应用LINDO软件来求解模型. 打开LINDO执行文件，编程如下： max 12x1+8x2+35x3 st 2) 3x1+2x2+12x330 3) x1+x2+2x37 4) 2x1+x2+x314 end,2. 模型求解,例6.6 求解,选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 100.
9、5000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.000000 2.166667 X3 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.833333 3) 0.000000 6.500000 4) 4.500000 0.000000 NO. ITERATIONS= 2,例6.6 求解,即A、B、C三种产品的生产量分别为4, 0和1.5万件，利润为100.5万元。,3. 结果分析。一般将三个约束条件的右端看作三种“资源”，上面输出的第811行“SL
10、ACK OR SURPLUS”给出了三种资源在最优解下是否有剩余： 2）原料甲，3)原料乙的剩余均为零，4）原料丙剩余4.5千克。 我们称“资源”剩余为零的约束为紧约束（或称为有效约束）,选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 100.5000 VARIABLE VALUE REDUCED COST X1 4.000000 0.000000 X2 0.0000
11、00 2.166667 X3 1.500000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 1.833333 3) 0.000000 6.500000 4) 4.500000 0.000000 NO. ITERATIONS= 2,例6.6 求解,在经济学上，把在最优解下某种“资源”增加1个单位时的“效益”增量，称为该种“资源”的影子价格。在本问题中，原料甲的影子价格为1.833333万元，原料乙的影子价格为6.5万元，原料丙的影子价格为0。,目标函数可以看作“效益”,成为紧约束的“资源”一旦增加,就必然会引起“效益”增长.,第81
12、1行“DUAL PRICES”给出3种原料在最优解下“资源”增加1个单位时“效益”的增量：,2）原料甲增加1千克时，利润增长1.833333万元；,3）原料乙增加1千克时，利润增长6.5万元；,4）增加原料丙(非紧约束)不会使利润增长。,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINI
13、TY X3 35.000000 13.000000 11.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000,例6.6 求解,目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。,输出的第1419行“CURRENT COEF” 的“ALLOWABLE INCREA
14、SE”与“ALLOWABLE DECREASE”给出了最优解不变条件下目标函数系数的允许变化范围：,注意： 的系数的允许变化范围是指在 和 的系数不变的条件下的,其余相同.,RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 12.000000 5.500000 1.625000 X2 8.000000 2.166667 INFINITY X3 35.000000 13.000000 11.000
15、000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 30.000000 12.000000 9.000000 3 7.000000 1.285714 2.000000 4 14.000000 INFINITY 4.500000,例6.6 求解,目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。,对“资源”的影子价格做进一步分析，影子价格的作用是有限制的。,输出的第2025行“CURRENT RHS”的 “ALLOWABLE INCREASE”与 “ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的限制范围。,1）若产品A的价格降低了2（万元/万件），则产品A利润变成了10万元/万件，在允许范围(12-1.625, 12+5.5)之外，应该改变生产计划。 2）若产品C的价格上涨了3（万元/万件），则产品C利润变成了38万元/万件，在允
