第六章 数学规划方法建模 第六章 数学规划方法建模 6.1 线性规划模型 6.2 非线性规划模型 6.3 整数规划模型.

Presentation on theme: "第六章 数学规划方法建模 第六章 数学规划方法建模 6.1 线性规划模型 6.2 非线性规划模型 6.3 整数规划模型."— Presentation transcript:

1 第六章 数学规划方法建模 第六章 数学规划方法建模 6.1 线性规划模型 6.2 非线性规划模型 6.3 整数规划模型

2 6.1 线性规划模型 例6.1生产计划问题 6.1.1 引例及线性规划模型 某工厂制造甲,乙 两种产品，资料如下：
6.1 线性规划模型 6.1.1 引例及线性规划模型 例6.1生产计划问题 某工厂制造甲,乙 两种产品，资料如下： 单位消耗 产品 原料 甲（吨） 乙（吨） 现有原料 总 量 钢材（吨） 电力（千瓦时） 工作日（个） 360 200 330 单位产品的利润 （万元/吨） 问：甲，乙 两种各应生产多少吨，才能获利最大？

3 解 6.1 线性规划模型 6.1.1 引例及线性规划模型 设生产甲 产品 吨，设生产 乙 产品 吨， 表示利润，则 且 甲 乙 现有原料
6.1 线性规划模型 6.1.1 引例及线性规划模型 解 设生产甲 产品 吨，设生产 乙 产品 吨， 表示利润，则 甲 乙 现有原料 总 量 钢材 电力 工作日 360 200 330 利润 且

4 6.1.1 引例及线性规划模型 解 写成线性规划的数学模型为： 目标函数 的线性函数 约束条件 的线性不等式 线性规划模型，简写成LP

5 例6.2 运输问题 6.1.1 引例及线性规划模型 有m个产地 A1，A2，…，Am 生产某种产品，
例6.2 运输问题 有m个产地 A1，A2，…，Am 生产某种产品， n 个销地B1，B2，…，Bn ,需要该种物资。 第i个产地Ai的产量为ai 而第j个销地Bj的销量为bj 已知由产地Ai到销地Bj的单位运价为ci j 且 （称为产销平衡问题）。 问：如何调用，才能使运费最省？

6 6.1.1 引例及线性规划模型 解 设 运到 的物资为 , 表示运费，则 满足产量的限制、销量的限制、非负限制等 可得线性规划的数学模型

7 解 6.1.1 引例及线性规划模型 线性规划模型的一般形式为(以最小目标为例) 写成矩阵形式为 目标函数的系数向量 决策变量
约束方程组的系数矩阵 可行域 写成矩阵形式为

8 线性规划模型的标准形为 非标准形的线性规划都可以化为标准形

9 线性规划模型的解法 两个变量的线性规划模型的图解法 例6.3 用图解法求下面的线性规划模型的最优解

10 线性规划模型的解法 解 1) 求可行域 C(4 , 2)

11 解 6.1.2 线性规划模型的解法 2）求目标函数的最优值。 表示以 为参数的一簇平行线，位于 同一条直线的点,函数值相同 称为等值线。
线性规划模型的解法 解 2）求目标函数的最优值。 A B D L1 L2 L3 L4 L5 表示以 为参数的一簇平行线，位于 同一条直线的点,函数值相同 称为等值线。 越往上移动， 值越大。 由图知：在可行域 C(4 , 2) 处， 达到最大值。 最大值为：

12 线性规划模型的解法 例6.4 用图解法求下面的线性规划模型的最优解 A(1 , 0) 在点 A（1 , 0）处达到最优。

13 由上面两个例子可知： 1）线性规划模型的可行域是凸集； 2）当线性规划模型的可行域有界时， 其最优解可在其可行域的顶点上达到。
线性规划模型的解法 由上面两个例子可知： 1）线性规划模型的可行域是凸集； 2）当线性规划模型的可行域有界时， 其最优解可在其可行域的顶点上达到。

14 求解线性规划模型的一种常用的方法就是单纯形法，单纯形法是通过迭代来求问题的最优解:最优解一定能在可行域的顶点上达到。
线性规划模型的解法 用数学软件包求解线性规划模型 我们对于单纯形法不做具体介绍，着重介绍用数学软件包来求解线性规划模型。 求解线性规划模型的一种常用的方法就是单纯形法，单纯形法是通过迭代来求问题的最优解:最优解一定能在可行域的顶点上达到。 目前，求解线性规划模型有不少现成的数学软件，比如LINDO软件、LINGO软件及MATLAB等。

15 例6.6 某厂用甲、乙、丙三种原料生产A、B、C三种产品，每种产品消耗原料定额如表6.2所示。问如何组织生产，才能使利润最大？
表6.2 三种产品的额定消耗与利润 产品 定额（千克/万件） 原料 A B C 现有原料总量（千克） 甲 乙 丙 3 1 2 12 30 7 14 单位产品的利润（万元/万件） 8 35 并进一步回答下列问题： 1）若产品A的价格降低了2（万元/万件），是否改变生产计划？ 2）若产品C的价格上涨了3（万元/万件），是否改变生产计划？ 3）若市场上还可以买到原料甲，其价格为1（万元/千克），是否购 买，最多可以买多少千克？

16 例6.5 用LINDO软件求线性规划模型例6.3的最优解
线性规划模型的解法 例6.5 用LINDO软件求线性规划模型例6.3的最优解 解： LINDO中已规定所有决策变量均为非 负，因此模型中的第四个约束条件不 必输入； 式中不能有括号，右端不能有数学符 号； 不等号 写成 （二者与 < 和> 等价）； 程序中第1行为目标函数，标号 2）, 3）,4）是标示各约束条件，以便从输 出结果中查找相应信息（标号可以 省略）； 程序以“end”结束。 打开LINDO执行文件， 编程如下： max 2x1+2x2 st 2) x1<4 3) x2<3 4) x1+2x2<8 end

17 例6.5 用LINDO软件求线性规划模型例6.3的最优解
输入程序后，选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“否（N）”，则可得到如下输出： LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X X ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) NO. ITERATIONS= 从上面输出我们得到：模型的最优解为 最优值

18 6.1.2.3 线性规划模型的灵敏性分析 灵敏度分析是指由于系统环境发生变化， 而引起系统目标变化的敏感程度。
线性规划模型的灵敏性分析 线性规划模型的灵敏性分析 灵敏度分析是指由于系统环境发生变化， 而引起系统目标变化的敏感程度。 对于线性规划模型(3)，我们总假设A ， b ，c 都是常数向量，但实际上这些数值往 往是通过测量和预测得到的，实际中多种原 因都能引起它们的变化。 现在的问题是：这些参数在多大的范围内 变化时，使线性规划模型的最优解不变。

19 6.1.2.3 线性规划模型的灵敏性分析 灵敏度分析主要研究下面几个问题： 1）市场条件变化。
线性规划模型的灵敏性分析 灵敏度分析主要研究下面几个问题： 1）市场条件变化。 目标函数的系数 变化，即第 j 种产品的价格变动。 2）资源条件变化。 约束条件右端常数项 变化, 即第i种原料数量变动。 3）工艺技术条件变化。 系数矩阵中 变化，即单位产品所需耗材变动。 我们要研究的是上述三种变化引起生产计划的改变及利润的变化情况。在什么条件下，要改变生产计划。

20 例6.6 求解 2. 模型求解 1. 建立数学模型 设A、B、C三种产品计划生产量分别为万件，利润为z万元，则可得如下线性规划模型
应用LINDO软件来求解模型. 打开LINDO执行文件，编程如下： max 12x1+8x2+35x3 st 2) 3x1+2x2+12x3<30 3) x1+x2+2x3<7 4) 2x1+x2+x3<14 end

21 例6.6 求解 从左面输出的第1～7行我们得到： 线性规划模型(4)的 最优解为 最优值
选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X X X ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) NO. ITERATIONS= 即A、B、C三种产品的生产量分别为4, 0和1.5万件，利润为100.5万元。 3. 结果分析。一般将三个约束条件的右端看作三种“资源”，上面输出的第8～11行“SLACK OR SURPLUS”给出了三种资源在最优解下是否有剩余： 2）原料甲，3)原料乙的剩余均为零，4）原料丙剩余4.5千克。 我们称“资源”剩余为零的约束为紧约束（或称为有效约束）

22 例6.6 求解 目标函数可以看作“效益”,成为紧约束的“资源”一旦增加,就必然会引起“效益”增长.
选择菜单“Solve”进行求解，若对提示: “DO RANGE(SENSITIVITY)ANALYSIS?”(是否进行灵敏性分析？) 回答“是（Y）”，则可如下输出： LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X X X ROW SLACK OR SURPLUS DUAL PRICES 2) 3) 4) NO. ITERATIONS= 第8～11行“DUAL PRICES”给出3种原料在最优解下“资源”增加1个单位时“效益”的增量： 2）原料甲增加1千克时，利润增长 万元； 3）原料乙增加1千克时，利润增长6.5万元； 4）增加原料丙(非紧约束)不会使利润增长。 在经济学上，把在最优解下某种“资源”增加1个单位时的“效益”增量，称为该种“资源”的影子价格。在本问题中，原料甲的影子价格为 万元，原料乙的影子价格为6.5万元，原料丙的影子价格为0。

23 例6.6 求解 目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。 输出的第14～19行“CURRENT COEF” 的“ALLOWABLE INCREASE”与“ALLOWABLE DECREASE”给出了最优解不变条件下目标函数系数的允许变化范围： 的系数为: RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X X INFINITY X RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE INFINITY 的系数为: 的系数为: 注意： 的系数的允许变化范围是指在 和 的系数不变的条件下的,其余相同.

24 例6.6 求解 目标函数的系数发生变化时(假定约束条件不变),最优解和最优值是否会改变,这是灵敏性分析的任务。 2 原料甲的范围
RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X X INFINITY X RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE INFINITY 2 原料甲的范围 3 原料乙的范围 4 原料丙的范围 对“资源”的影子价格做进一步分析，影子价格的作用是有限制的。 输出的第20～25行“CURRENT RHS”的 “ALLOWABLE INCREASE”与 “ALLOWABLE DECREASE”给出了影子价格有意义条件下约束右端的限制范围。

25 例6.6 求解 通过以上的灵敏性分析我们可以对问题 1),2),3)给出解答.
1）若产品A的价格降低了2（万元/万件），则产品A利润 变成了10万元/万件，在允许范围( , )之外，应 该改变生产计划。 2）若产品C的价格上涨了3（万元/万件），则产品C利润 变成了38万元/万件，在允许范围(35-11, 35+13)内，因此， 不应改变生产计划。 3）由于原料甲的影子价格为 万元，因此，应该在 市场上以1（万元/千克）的价格购买原料甲，但最多只可以 买12千克。

26 例6.7 投资方案的确定 6.1.3 线性规划模型实例 某部门要进行投资，现有四个投资项目：
线性规划模型实例 例6.7 投资方案的确定 某部门要进行投资，现有四个投资项目： 项目A： 从第一年到第四年的每年年初需要投资，并于次年年末回收本利115％；项目B：从第三年年初需要投资，到第五年末回收本利125％，但规定最大投资额不超过40万元；项目C：第二年初需要投资，到第五年末才能回收本利140％，但规定最大投资额不超过30万元；项目D：五年内每年的年初可买公债，于当年年末归还，并可获得6％的利息。 已知该部门现有资金100万元，试为该部门确定投资方案，使得第五年末它拥有的资金本利总额最大？

27 求解例6.7 6.1.3 线性规划模型实例 1. 模型建立 1）决策变量 决策变量为每年年初向四个项目的投资额， 设第 i
线性规划模型实例 求解例6.7 1. 模型建立 1）决策变量 决策变量为每年年初向四个项目的投资额， 设第 i 年年初向A、B、C、D 四个项目的投资额为 (万元) 2）目标函数 设第五年年末拥有的资金本利总额为z，将 所有可能的投资列于表6.3 。

28 目标函数应该是四项投资在第五年年末回收的本利之和， 于是，目标函数为
线性规划模型实例 表6.3 可能的投资方案 年份 项目 1 2 3 4 5 投资限额 （万元） A B 40 C 30 D 目标函数应该是四项投资在第五年年末回收的本利之和， 于是，目标函数为

29 线性规划模型实例 3）约束条件 (a)为了获得最大的投资收益，每年的年初应将手头的全部资金投出去，因此第一年的投资总额应是100万元， (b)第二年的投资总额应是第一年年底回收的各项投资的本利，即 同理，第三、四、五年的投资总额应是上一年年底回收的各项投资本利，即

30 线性规划模型实例 （c）由于投资限制，因此还有 由此得投资问题的数学模型为

31 线性规划模型实例 2. 模型求解 用LINDO软件求解，为了能应用LINDO软件，编制程序时应将各约束条件的右端的决策变量移到左端。求得投资方案的最优解为 其余决策变量均为零。 最优值

32 线性规划模型实例 例6.8 配料问题 一饲养场饲养供实验用的动物，已知动物生长对饲料中的三种营养成分—蛋白质、矿物质和维生素特别敏感，每个动物每天至少需要蛋白质70g、矿物质3g、维生素10mg，该场能搞到五种饲料，每种饲料10kg的成本如表6.4。每一千克饲料中所含的营养成分如表6.5。 饲料 A1 A2 A3 A4 A5 成本（元） 2 7 4 3 5 表6.4 饲料 蛋白质（g） 矿物质(g) 维生素(mg) A1 0.03 0.10 0.05 A2 2.00 A3 1.00 0.02 A4 0.60 0.20 A5 1.80 0.08 表6.5 试确定既能满足需要,又使总成本为最低的饲料配方,建立数学模型.

33 例6.8 配料问题 6.1.3 线性规划模型实例 模型建立 1）决策变量。设动物每天食用的混合饲料中所含的第j 种饲料Aj的数量为 kg
线性规划模型实例 例6.8 配料问题 模型建立 1）决策变量。设动物每天食用的混合饲料中所含的第j 种饲料Aj的数量为 kg 2）目标函数。设混合饲料的总成本为z，则 3）约束条件。 （a）蛋白质的限制； （b）矿物质的限制； （c）维生素的限制。

34 线性规划模型实例 例6.8 配料问题 由此的上述问题的数学模型为 2. 模型求解 用LINDO软件求解，得到最优解为： 最优值

35 例6.9 货机装运 6.1.3 线性规划模型实例 前仓： 后仓： 中仓： 10;6800 8;5300 16；8700 飞机平衡
线性规划模型实例 例6.9 货机装运 三个货舱最大载重(吨),最大容积(米3) 前仓： 10;6800 中仓： 16；8700 后仓： 8;5300 飞机平衡 三个货舱中实际载重必须与其最大载重成比例 重量（吨） 空间( 米3/吨） 利润（元/吨） 货物1 18 480 3100 货物2 15 650 3800 货物3 23 580 3500 货物4 12 390 2850 如何装运,使本次飞行获利最大？

36 例6.9 货机装运 模型假设 模型建立 6.1.3 线性规划模型实例 每种货物可以分割到任意小； 每种货物可以在一个或多个货舱中任意分布；
线性规划模型实例 例6.9 货机装运 模型假设 每种货物可以分割到任意小； 每种货物可以在一个或多个货舱中任意分布； 多种货物可以混装，并保证不留空隙； 模型建立 xij--第i 种货物装入第j 个货舱的重量(吨） i=1,2,3,4, j=1,2,3 (分别代表前、中、后仓) 决策变量

37 例6.9 货机装运 模型建立 6.1.3 线性规划模型实例 xij--第i 种货物装入第j 个货舱的重量 目标函数(利润) 货舱重量
线性规划模型实例 例6.9 货机装运 模型建立 xij--第i 种货物装入第j 个货舱的重量 目标函数(利润) 货舱重量 10；6800 16；8700 8；5300 约束条件 货舱容积

38 例6.9 货机装运 模型建立 6.1.3 线性规划模型实例 xij--第i 种货物装入第j 个货舱的重量 平衡要求 约束条件 货物供应
线性规划模型实例 例6.9 货机装运 模型建立 xij--第i 种货物装入第j 个货舱的重量 平衡要求 10；6800 16；8700 8；5300 约束条件 货物供应

39 例6.9 货机装运 模型求解 6.1.3 线性规划模型实例 货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3；货物4: 中仓3。
线性规划模型实例 例6.9 货机装运 模型求解 OBJECTIVE FUNCTION VALUE 1) VARIABLE VALUE REDUCED COST X X X X X X X X X X X X 货物2：前仓10,后仓5； 货物3: 中仓13, 后仓3；货物4: 中仓3。 最大利润约121516元 运输问题 货物~供应点 货舱~需求点 平衡要求 运输问题的扩展