matlab线性规划

1、单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级1单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级1 单击此处编辑母版副标题样式1单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.1数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 12002.5.重庆大学数理学院国家级精品课程数学实验课件数学实验之线性规划SHUXUESHIYANZHIXIANXINGGUIHUA课件制作：数学实验课程组 你可以自由的从网站 单击此处编辑母版文本样式 第二

2、级 第三级 第四级 第五级2单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2 单击此处编辑母版副标题样式2单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.2数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 22002.5.1理解优化模型的三个要素:决策变量，目标函数和约束条件；掌握用MATLAB优化工具箱求解线性规划的方法；了解线性规划模型中的灵敏度分析方法；掌握如何使用软件来实现分析；体验由实际问题建立线性规划模型的全过程。实验目的单击此处编辑母版标题样式 单击此处

3、编辑母版文本样式 第二级 第三级 第四级 第五级3单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级3 单击此处编辑母版副标题样式3单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.3数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 32002.5.成功的优化例子成功的优化例子“最优人员安排”为美国航空每年节约两千万美元. 单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级4单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级

4、第四级 第五级4 单击此处编辑母版副标题样式4单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.4数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 42002.5.成功的优化例子成功的优化例子 “改进的出货流程”每年为Yellow Freight 公司节约一千七百多万美元.单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级5单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级5 单击此处编辑母版副标题样式5单击此处编辑母版标题样式 单击此处编辑

5、母版文本样式 第二级 第三级 第四级 第五级2002.5.5数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 52002.5.成功的优化例子成功的优化例子 “改进的卡车分派”为 Reynolds 公司每年节约七百万美元 .单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级6单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级6 单击此处编辑母版副标题样式6单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.6数学实验之线性规划实验目的 引 例优化

6、问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 62002.5.成功的优化例子成功的优化例子 “最优全局供应链”为数字设备行业节约超过三亿美元.单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级7单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级7 单击此处编辑母版副标题样式7单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.7数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 72002.5.成功的优化例子成功的优化例子 宝洁公司重建

7、北美业务, 减少 20%的工厂, 每年节约两亿美元.单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级8单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级8 单击此处编辑母版副标题样式8单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.8数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 82002.5.成功的优化例子成功的优化例子 大阪Hanshin高速的 “最优交通控制”每年节约一千七百万人小时 ,为他们带来三亿二千万美圆的收益.单击此处编

8、辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级9单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级9 单击此处编辑母版副标题样式9单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.9数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 92002.5.单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级10单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级10 单击此处编辑母版副标题样式10

9、单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.10数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 102002.5.引例单耗 甲 乙 丙限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件) 4 3 2在一定的条件下，问生产数量为多少时, 利润达到最大？数据表生产计划问题生产计划问题引例运输问题运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500

10、600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450里程(km)目标：运费达到最小单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级12单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级12 单击此处编辑母版副标题样式12单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.12数学实验之线性规

11、划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 122002.5.特点：从若干可能的计划（方案）中寻求某种意义下的最优方案，数学上将这种问题称为最优化问题（optimization).1、生产计划问题；2、运输问题；最优化问题简介最优化问题简介单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级13单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级13 单击此处编辑母版副标题样式13单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.13数学实验之线性规划实验

12、目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 132002.5.优化问题的表述优化问题的表述 最优化是企业运作、科技研发和工程设计中常见的问题。要表述一个最优化问题（即建立数学模型），应明明确三样东西：决策变量、约束条件 和目标函数决策变量：它们是决策者（你）所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值。约束条件：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义。 目标函数：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。单击此处编辑母版标题样式 单击此处编辑母版

13、文本样式 第二级 第三级 第四级 第五级14单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级14 单击此处编辑母版副标题样式14单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.14数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 142002.5.1232334xxx规划模型利润材料工时人力单耗 甲 乙 丙 x1 x2 x3限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件) 4 3 2生产计划问题生产计划问题123432Zxxxmax目标

14、函数123,0 x x x 123321.536xxx12332540 xxx约束条件决策变量x1, x2, x3单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级15单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级15 单击此处编辑母版副标题样式15单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.15数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 152002.5.单耗 甲 乙 丙 x1 x2 x3限额材料工时工人 2 3 1 3 2

15、 1.5 3 2 5343640利润(元/件) 4 3 2生产计划问题生产计划问题123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x规划模型利润材料工时人力最优化问题运输问题运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A

16、14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450里程(km)目标：运费达到最小单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级17单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级17 单击此处编辑母版副标题样式17单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.17数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 172002.5.cij 单位运费；ai 在第i 厂提供的量； bj 第j 地需要量；求从si

17、运多少钢管到Aj, 可使总运费最少.决策变量: xij 从si运到Aj的钢管数量s1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级18单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级18 单击此处编辑母版副标题样式18单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.18数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 182002.

18、5.s1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj151. .,1,2,.,7ijijstxai71511minijijijc x 711,2,.,15ijjixbj0,1,7,1,15ijxij单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级19单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级19 单击此处编辑母版副标题样式19单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.19数学实验之线性规划实验目的 引 例优化

19、问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 192002.5.三个基本要素1、决策变量（decision variables);2、约束条件（constraints);3、目标函数（objective function)最优化问题分类线性、非线性静态、动态整数、非整数随机、非随机等 最优化问题单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级20单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级20 单击此处编辑母版副标题样式20单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002

20、.5.20数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 202002.5.最优化数学模型的分类 线性规划(LP) 非线性规划(NLP) 二次规划(QP) 整数规划(IP)多目标规划 动态规划 最优化问题单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级21单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级21 单击此处编辑母版副标题样式21单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.21数学实验之线性规划实验目的 引 例优化问题线性

21、规划软件求解 范 例 布置实验 结 束课堂延伸 212002.5.生产计划问题生产计划问题该模型的目标函数和约束条件均为线性函数, 满足线性规划的要求,故该问题为一线性规划问题,其模型为线性规划模型.123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x利润材料工时人力线性规划单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级22单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级22 单击此处编辑母版副标题样式22单击此处编辑母版标题样式 单击此处编辑母版文本样

22、式 第二级 第三级 第四级 第五级2002.5.22数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 222002.5.生产计划问题生产计划问题max cTxs.t. Axb x0矩阵形式：TT123c4, 3, 2, ,2 3134A3 2 1.5 ,b363 2540 x x xx123123123123123max4322334321.536. .32540,0Zxxxxxxxxxstxxxx x x利润材料工时人力线性规划模型单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级23单击此处编辑母版标题样式 单击此

23、处编辑母版文本样式 第二级 第三级 第四级 第五级23 单击此处编辑母版副标题样式23单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.23数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 232002.5.min (max) cTxs.t. Axb, (或Ax = b) x0 (或a x b)标准形式其中：xRn，A Rmn， bRm， cRn线性规划单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级24单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级

24、第四级 第五级24 单击此处编辑母版副标题样式24单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.24数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 242002.5.2 X1 + X2 = 40X1 + 2 X2 = 50 X1 X2abcd可行点可行域凸多面体v内点边界点顶点vB线性规划解的若干概念线性规划模型max z = 5x1+3x2s.t. 2x1+x240 x1+2x250 x1，x20单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级25单击此处编辑母版

25、标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级25 单击此处编辑母版副标题样式25单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.25数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 252002.5.线性规划解的图示线性规划模型max z = 5x1+3x2s.t. 2x1+x240 x1+2x250 x1，x202 X1 + X2 = 40X1 + 2 X2 = 50 X1 X2a20 x1=10,x2=2025问问: :什么样的问题可以使用图解法什么样的问题可以使用图解法? ?

26、你从图中得到什么启示你从图中得到什么启示? ?P=0P=50P=110Max z = 3x1+x2s.t. -x1+x22 -L1 x1-2x22 -L2 3x1+2x214 -L3 x1，x20 x1x2L2L1L30 x1x2L2L1L30 x1x2L2L10 x1x2L2L1L30z=c 无最优解 无可行解 最优解不唯一线性规划的基本性质线性规划的基本性质可行域 线段组成的凸多边形目标函数 等值线为直线最优解 凸多边形的某个顶点LP的基本性质： 可行域存在时，必是凸多面体； 可行解对应于可行域中的点； 最优解存在时，必在可行域的顶点取得。LP的通常解法是单纯形法。超平面组成的凸多面体等值

27、线是超平面凸多面体的某个顶点2 维n 维单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级28单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级28 单击此处编辑母版副标题样式28单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.28数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 282002.5. Matlab中求解线性规划的命令为: linprog, 解决的线性规划的标准格式为： min c cTx x x xR Rn n s.t. A

28、x x 0：收敛=0: 到最大迭代次数时都还未收敛0：infeasible或方法失败迭代次数和算法类型MATLABMATLAB软件求解软件求解单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级31单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级31 单击此处编辑母版副标题样式31单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.31数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 312002.5.看一个小例子 程序: c=-5,3; A=

29、2,1;1,2; b=40,50; L=0, 0; x,fmin=linprog(c,A,b,L); Pmax=-fmin x1=x(1), x2=x(2) 输出结果: Pmax=110, x1=10, x2=20.模型: max P=5 X1 + 3 X2 s.t. 2 X1 + X2 40 X1 + 2 X2 50 X10, X20 MATLABMATLAB软件求解软件求解单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级32单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级32 单击此处编辑母版副标题样式32单击此处编辑母版

30、标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.32数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 322002.5.加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 每天：范范 例例x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 5021 xx劳动时间 48081221 xx加工能力 10031x决策变量 目标函数

31、216472xxzMax每天获利约束条件非负约束 0,21xx1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 加工奶制品的生产计划加工奶制品的生产计划单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级34单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级34 单击此处编辑母版副标题样式34单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.34数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 34200

32、2.5.LINDO 6.1LINDO 6.1程序程序 max 72x1+64x2max 72x1+64x2st st2 2）x1+x250 x1+x2503 3）12x1+8x248012x1+8x24804 4）3x11003x1100endendDO RANGE (SENSITIVITY) ANALYSIS? NoNo加工奶制品的生产计划加工奶制品的生产计划范范 例例单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级35单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级35 单击此处编辑母版副标题样式35单击此处编辑母版标题样

33、式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.35数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 352002.5. OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.0000

34、00 NO. ITERATIONS= 220桶牛奶生产A1, 30桶生产A2，利润3360元。 范范 例例单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级36单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级36 单击此处编辑母版副标题样式36单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.36数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 362002.5. OBJECTIVE FUNCTION VALUE 1) 3360.000 V

35、ARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2原料无剩余时间无剩余加工能力剩余40三种资源“资源” 剩余为零的约束为紧约束（有效约束） 单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级37单击此处编辑母版标题样式 单击此处编辑母版文本样式

36、第二级 第三级 第四级 第五级37 单击此处编辑母版副标题样式37单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.37数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 372002.5. OBJECTIVE FUNCTION VALUE 1) 3360.000 VARIABLE VALUE REDUCED COST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 48.000

37、000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO. ITERATIONS= 2最优解下“资源”增加1单位时“效益”的增量 原料增加1单位, 利润增长48 时间增加1单位, 利润增长2 加工能力增长不影响利润影子价格影子价格 结果解释 单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级38单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级38 单击此处编辑母版副标题样式38单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.38数学实验之线

38、性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 382002.5. 35元可买到1桶牛奶，要买吗？35 48, 应该买！ 聘用临时工人付出的工资最多每小时几元？ 2元！加工奶制品的生产计划加工奶制品的生产计划范范 例例单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级39单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级39 单击此处编辑母版副标题样式39单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.39数学实验之线性规划实验目的 引 例优化问题线

39、性规划软件求解 范 例 布置实验 结 束课堂延伸 392002.5.RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 5

40、0.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000DO RANGE(SENSITIVITY) ANALYSIS? Yes最优解不变时目标函数系数允许变化范围 (约束条件不变)x1系数范围(64,96) x2系数范围(48,72) x1系数由24 3=72增加为303=90，在允许范围内 A1获利增加到 30元/千克，应否改变生产计划 不变！单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级40单击此处编辑母版标题样式 单击此处编辑

41、母版文本样式 第二级 第三级 第四级 第五级40 单击此处编辑母版副标题样式40单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.40数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 402002.5.RANGES IN WHICH THE BASIS IS UNCHANGED: OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X1 72.000000 24.000000 8.000000

42、 X2 64.000000 8.000000 16.000000 RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围 (目标函数不变)原料最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？最多买10桶!范范 例例单击此处编辑母版标题样式 单击此处编辑

43、母版文本样式 第二级 第三级 第四级 第五级41单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级41 单击此处编辑母版副标题样式41单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.41数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 412002.5.课堂延伸课堂延伸 重要事件重要事件 重要人物重要人物 优化技术成功应用的故事优化技术成功应用的故事单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级42单击此处编辑母版标题样式 单击此处编辑

44、母版文本样式 第二级 第三级 第四级 第五级42 单击此处编辑母版副标题样式42单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.42数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 422002.5.课堂延伸课堂延伸重要事件重要事件 在1762年, Lagrange 解仅含等式约束的最优化问题 在1820年, Gauss利用消去法解线性方程组. 在1945年, 计算机出现. 在1947年, Dantzig 发明单纯形法. 在1968年, Fiacco and McCormick 引进内点法. 在1984

45、年, Karmarkar 提出了解线性规划的有效算法.单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级43单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级43 单击此处编辑母版副标题样式43单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.43数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 432002.5.课堂延伸课堂延伸重要人物重要人物 John Von Neumann George B. Dantzig Leonid Vitaly

46、evich Kantorovich Narendra Karmarkar Harry Max Markowitz单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级44单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级44 单击此处编辑母版副标题样式44单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.44数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 442002.5.重要人物重要人物 John Von Neumann 约翰冯诺依曼(190

47、31957),美藉匈牙利人.20世纪最杰出的数学家之一,被誉为”计算机之父”,”博弈论之父”.被认为是数学规划的三大创始人之一.课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级45单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级45 单击此处编辑母版副标题样式45单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.45数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 452002.5.George B. Dantzig Ge

48、orge B. Dantzig(1914-2005),美国人,线性规划单纯形法的创始人,被誉为”线性规划之父”.美国科学院三院院士,美国军方数学顾问,教授.并以其名字设立Dantzig奖.数学规划的三大创始人之一. 发现算法时非常年轻,以至到日本时,人们以为”线性规划之父”是个老人,而对他无人问津.课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级46单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级46 单击此处编辑母版副标题样式46单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五

49、级2002.5.46数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 462002.5.Leonid Vitalyevich Kantorovich Kantorovich(1912-1986)苏联人,著名数学家和经济学家,教授,年仅18岁获博士学位.因在经济学上提出稀缺资源的最优配置获诺贝尔奖.线性规划对偶理论的提出者,数学规划的三大创始人之一.课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级47单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级47 单击此处编辑母版

50、副标题样式47单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.47数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 472002.5.课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级48单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级48 单击此处编辑母版副标题样式48单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.48数学实验之线性规划实验目的 引 例优化问题线性规划软件

51、求解 范 例 布置实验 结 束课堂延伸 482002.5. 在1990年,Markowitz因为金融经济学方面的贡献和另外两位学者分获诺贝尔经济学奖.左边的文字说明了他获奖的原因以及关于他的理论的简介.课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级49单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级49 单击此处编辑母版副标题样式49单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.49数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验

52、结 束课堂延伸 492002.5.课堂延伸课堂延伸优化技术成功应用的故事优化技术成功应用的故事在现实世界中，都有一些什么成功应用优化技术的故事呢 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 AT&TAT&T网络的快速恢复及优化网络的快速恢复及优化 香港国际货柜码头装卸的优化决策香港国际货柜码头装卸的优化决策 联合包裹服务公司优化空中与地面运输计划联合包裹服务公司优化空中与地面运输计划 得克萨斯儿童医院最小化金融风险得克萨斯儿童医院最小化金融风险单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级50单击此处编辑母版标题样式 单击此处编辑母版文本样

53、式 第二级 第三级 第四级 第五级50 单击此处编辑母版副标题样式50单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.50数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 502002.5.问题：甚至在九一一恐怖袭击事件之前, 美国大陆航空公司总裁就考虑到对大型航空公司,应该制定一个危机计划,以应对紧急情况。 突发事件,包括恶劣的天气,飞机机械故障在现实世界中，都有一些什么成功应用优化技术的故事呢 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 乘务组缺班，航空公司会面临航班中断,航班延误

54、,取消等情况。 由于乘务组未必能够保证剩余的定期航班的正常飞行. 航空公司必须尽快让乘务组完成补偿飞行计划，并返回自己的原时刻表。这个决策要满足成本最小、政府规定、合同约定以及对生活品质的要求。 解决这些问题需要专门的能进行复杂建模并平衡多种因素的运筹研究技术。 课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级51单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级51 单击此处编辑母版副标题样式51单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.51数学实验之线性规

55、划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 512002.5. 运筹学解决方案： 大陆航空公司采用Caleb技术,研发了CrewSolver决策支持系统，生成全局最优或接近最优的乘务组补救方案. 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 效果：大陆航空公司自实施此计划以来，在每一次严重的突发事件中,都能实现乘务组快速补救,取得价值数百万美元的效益。 公司估计,在2001年CrewSolver系统帮助它节省约了4000万美元。由于该系统,使美国航空业自2001年9月11日后开始复苏,从那时起,五家航空公司已采用了类似的基于运筹学的软件用于突发

56、事件后航班时刻表、飞行员安排等的补救计划。课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级52单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级52 单击此处编辑母版副标题样式52单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.52数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 522002.5.背后的故事： 1995年，美国大陆航空公司邀请于刚教授为他们编写决策支持系统。于刚领导他的研究人员克服了重重困难，取得了一个又

57、一个的突破性成果，为大陆航空公司编写了三个决策支持系 统，解决了当航空系统遭遇恶劣天气、飞机故障等干扰后，飞机航班的最优恢复问题、机组人员的调度问题和机组人员的计划、培训、休假等总体决策的最优方案。2001年9月11日，震惊世界的“9.11”恐怖事件不幸发生了。这次事件给美国航空业带来了灾难性的打击。但是，就是通过这次突发的灾难性事件，于刚的实时决策系统的优越性得到了充分体现。大陆航空公司由于采用了他的优化实时决策系统，比其他航空公司提前两天开始正常运营，为公司挽回3000多万美元的损失。由于有了于刚的完备的决策支持系统，大陆航空公司在整个“9.11”事件中避免了上亿美元的损失。 课堂延伸课堂

58、延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级53单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级53 单击此处编辑母版副标题样式53单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.53数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课堂延伸 532002.5. 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 该案例使旅美华裔著名运筹学家于刚教授荣获2002年度运筹与管理科学应用Franz Edelman 奖，Franz E

59、delman奖是由世界著名的运筹和管理科学家Franz Edelman于1971年创立的。它作为运筹和管理科学在国际上的一项最高荣誉，一年一度地颁发给在这一领域取得了最突出成就的科学家和企业家。课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级54单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级54 单击此处编辑母版副标题样式54单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第五级2002.5.54数学实验之线性规划实验目的 引 例优化问题线性规划软件求解 范 例 布置实验 结 束课

60、堂延伸 542002.5.问题：AT&T是一个全球性电信公司，提供多种服务,如远程语音数据、视频、无线通讯、卫星及互联网服务。 AT&T面对的问题是防止网络出错,并提供应对失误发生时的快速反应。AT&T在发生网络 故障时，要快速改换通讯通道,这要求网络有足够的恢复能力来传送相应需求。 这个问题很重要,因为服务的失败,直接影响到公司的核心服务和客户忠诚度。解决它需要运筹学研究专门技术,因为这个问题涉及到全系统而运筹学有强大的能力来处理众多的参数。 AT&TAT&T网络的快速恢复及优化网络的快速恢复及优化课堂延伸课堂延伸单击此处编辑母版标题样式 单击此处编辑母版文本样式 第二级 第三级 第四级 第