数学实验教学课件--线性规划

单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级1单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级1单击此处编辑母版副标题样式1单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.1数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 1理解优化模型的三个要素:决策变量，目标函数和约束条件；掌握用MATLAB优化工具箱求解线性规划的方法；了解线性规划模型中的灵敏度分析方法；掌握如何使用软件来实现分析；体验由实际问题建立线性规划模型的全过程。实验目的2019.5.1单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2单击此处编辑母版副标题样式2单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.2数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 应用场景应用场景_成功的优化例子成功的优化例子“最优人员安排”为美国航空每年节约两千万美元.2019.5.2单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级3单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级3单击此处编辑母版副标题样式3单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.3数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 “改进的出货流程”每年为Yellow Freight 公司节约一千七百多万美元.应用场景应用场景_成功的优化例子成功的优化例子2019.5.3单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级4单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级4单击此处编辑母版副标题样式4单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.4数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 “改进的卡车分派”为 Reynolds 公司每年节约七百万美元.应用场景应用场景_成功的优化例子成功的优化例子2019.5.4单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级5单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级5单击此处编辑母版副标题样式5单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.5数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 “最优全局供应链”为数字设备行业节约超过三亿美元.应用场景应用场景_成功的优化例子成功的优化例子2019.5.5单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级6单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级6单击此处编辑母版副标题样式6单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.6数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 宝洁公司重建北美业务,减少 20%的工厂,每年节约两亿美元.应用场景应用场景_成功的优化例子成功的优化例子2019.5.6单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级7单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级7单击此处编辑母版副标题样式7单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.7数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 成功的优化例子成功的优化例子 大阪Hanshin高速的“最优交通控制”每年节约一千七百万人小时,为他们带来三亿二千万美圆的收益.2019.5.7单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级8单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级8单击此处编辑母版副标题样式8单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.8数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 2019.5.8单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级9单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级9单击此处编辑母版副标题样式9单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.9数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 引例单耗 甲 乙 丙限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件)4 3 2在一定的条件下，问生产数量为多少时,利润达到最大？数据表生产计划问题生产计划问题2019.5.9引例运输问题运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450里程(km)目标：运费达到最小单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级11单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级11单击此处编辑母版副标题样式11单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.11数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 特点：从若干可能的计划（方案）中寻求某种意义下的最优方案，数学上将这种问题称为最优化问题（optimization).1、生产计划问题；2、运输问题；最优化问题简介最优化问题简介2019.5.11单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级12单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级12单击此处编辑母版副标题样式12单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.12数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 优化问题的表述优化问题的表述 最优化是企业运作、科技研发和工程设计中常见的问题。要表述一个最优化问题（即建立数学模型），应明明确三样东西：决策变量、约束条件 和目标函数决策变量：它们是决策者（你）所控制的那些数量，它们取什么数值需要决策者来决策，最优化问题的求解就是找出决策变量的最优取值。约束条件：它们是决策变量在现实世界中所受到的限制，或者说决策变量在这些限制范围之内取值才有实际意义。目标函数：它代表决策者希望对其进行优化的那个指标。目标函数是决策变量的函数。2019.5.12单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级13单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级13单击此处编辑母版副标题样式13单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.13数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 规划模型利润材料工时人力单耗 甲 乙 丙 x1 x2 x3限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件)4 3 2生产计划问题生产计划问题max目标函数约束条件决策变量x1,x2,x32019.5.13单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级14单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级14单击此处编辑母版副标题样式14单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.14数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 单耗 甲 乙 丙 x1 x2 x3限额材料工时工人 2 3 1 3 2 1.5 3 2 5343640利润(元/件)4 3 2生产计划问题生产计划问题规划模型利润材料工时人力2019.5.14最优化问题运输问题运输问题A1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道铁路公路S1S7 钢管厂火车站450里程(km)目标：运费达到最小单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级16单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级16单击此处编辑母版副标题样式16单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.16数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 cij 单位运费；ai 在第i 厂提供的量；bj 第j 地需要量；求从si运多少钢管到Aj,可使总运费最少.决策变量:xij 从si运到Aj的钢管数量s1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj2019.5.16单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级17单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级17单击此处编辑母版副标题样式17单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.17数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 s1s2sis7 A1A2AjA15 C11C12C1jC1,15Ci,jaia1a2a7b15b1b2bj2019.5.17单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级18单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级18单击此处编辑母版副标题样式18单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.18数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 三个基本要素1、决策变量（decision variables);2、约束条件（constraints);3、目标函数（objective function)最优化问题分类线性、非线性静态、动态整数、非整数随机、非随机等 最优化问题2019.5.18单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级19单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级19单击此处编辑母版副标题样式19单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.19数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 最优化数学模型的分类 线性规划(LP)非线性规划(NLP)二次规划(QP)整数规划(IP)多目标规划 动态规划 最优化问题2019.5.19单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级20单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级20单击此处编辑母版副标题样式20单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.20数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 生产计划问题生产计划问题该模型的目标函数和约束条件均为线性函数,满足线性规划的要求,故该问题为一线性规划问题,其模型为线性规划模型.利润材料工时人力线性规划2019.5.20单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级21单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级21单击此处编辑母版副标题样式21单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.21数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 生产计划问题生产计划问题max cTxs.t.Axb x0矩阵形式：利润材料工时人力线性规划模型2019.5.21单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级22单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级22单击此处编辑母版副标题样式22单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.22数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 min cTxs.t.Ax=b x0 (或a x b)标准形式其中：xRn，A Rmn，bRm，cRn线性规划2019.5.22单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级23单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级23单击此处编辑母版副标题样式23单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.23数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 2 X1+X2=40X1+2 X2=50 X1 X2abcd可行点可行域凸多面体v内点边界点顶点vB线性规划解的若干概念线性规划模型max z=5x1+3x2s.t.2x1+x240 x1+2x250 x1，x202019.5.23单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级24单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级24单击此处编辑母版副标题样式24单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.24数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 线性规划解的图示线性规划模型max z=5x1+3x2s.t.2x1+x240 x1+2x250 x1，x202 X1+X2=40X1+2 X2=50 X1 X2a20 x1=10,x2=2025问问:什么样的问题可以使用图解法什么样的问题可以使用图解法?你从图中得到什么启示你从图中得到什么启示?P=0P=50P=1102019.5.24求解LP的特殊情形Max z=3x1+x2s.t.-x1+x22 -L1 x1-2x22 -L2 3x1+2x214-L3 x1，x20 x1x2L2L1L30 x1x2L2L1L30 x1x2L2L10 x1x2L2L1L30z=c 无最优解 无可行解 最优解不唯一线性规划的基本性质线性规划的基本性质可行域 线段组成的凸多边形目标函数 等值线为直线最优解 凸多边形的某个顶点LP的基本性质：可行域存在时，必是凸多面体；可行解对应于可行域中的点；最优解存在时，必在可行域的顶点取得。LP的通常解法是单纯形法。超平面组成的凸多面体等值线是超平面凸多面体的某个顶点2 维n 维单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级27单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级27单击此处编辑母版副标题样式27单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.27数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 Matlab中求解线性规划的命令为:linprog,解决的线性规划的标准格式为：min c cTx x x xR Rn n s.t.Ax x 0：收敛=0:到最大迭代次数时都还未收敛0：infeasible或方法失败迭代次数和算法类型MATLABMATLAB软件求解软件求解2019.5.29单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级30单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级30单击此处编辑母版副标题样式30单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.30数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 看一个小例子 程序:c=-5,3;A=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软件求解软件求解2019.5.30单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级31单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级31单击此处编辑母版副标题样式31单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.31数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 加工奶制品的生产计划加工奶制品的生产计划1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 每天：范范 例例2019.5.31x1桶牛奶生产A1 x2桶牛奶生产A2 获利 243x1 获利 164 x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利约束条件非负约束 1桶牛奶 3公斤A1 12小时 8小时 4公斤A2 或获利24元/公斤 获利16元/公斤 加工奶制品的生产计划加工奶制品的生产计划单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级33单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级33单击此处编辑母版副标题样式33单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.33数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 LINDO 6.1LINDO 6.1程序程序 max 72x1+64x2max 72x1+64x2stst2 2）x1+x250 x1+x2503 3）12x1+8x248012x1+8x24804 4）3x11003x1100endendDO RANGE(SENSITIVITY)ANALYSIS?NoNo加工奶制品的生产计划加工奶制品的生产计划范范 例例2019.5.33单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级34单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级34单击此处编辑母版副标题样式34单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.34数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 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.000000 NO.ITERATIONS=220桶牛奶生产A1,30桶生产A2，利润3360元。范范 例例2019.5.34单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级35单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级35单击此处编辑母版副标题样式35单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.35数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 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.000000 NO.ITERATIONS=2原料无剩余时间无剩余加工能力剩余40三种资源“资源”剩余为零的约束为紧约束（有效约束）2019.5.35单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级36单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级36单击此处编辑母版副标题样式36单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.36数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 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.000000 NO.ITERATIONS=2最优解下“资源”增加1单位时“效益”的增量 原料增加1单位,利润增长48 时间增加1单位,利润增长2 加工能力增长不影响利润影子价格影子价格 结果解释 2019.5.36单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级37单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级37单击此处编辑母版副标题样式37单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.37数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 35元可买到1桶牛奶，要买吗？35 48,应该买！聘用临时工人付出的工资最多每小时几元？2元！加工奶制品的生产计划加工奶制品的生产计划范范 例例2019.5.37单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级38单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级38单击此处编辑母版副标题样式38单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.38数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 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 50.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元/千克，应否改变生产计划 不变！2019.5.38单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级39单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级39单击此处编辑母版副标题样式39单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.39数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 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 50.000000 10.000000 6.666667 3 480.000000 53.333332 80.000000 4 100.000000 INFINITY 40.000000影子价格有意义时约束右端的允许变化范围(目标函数不变)原料最多增加10 时间最多增加53 35元可买到1桶牛奶，每天最多买多少？最多买10桶!范范 例例2019.5.39单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级40单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级40单击此处编辑母版副标题样式40单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.40数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 背景聚焦背景聚焦重要事件重要事件重要人物重要人物2019.5.40单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级41单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级41单击此处编辑母版副标题样式41单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.41数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 重要事件重要事件 在1762年,Lagrange 解仅含等式约束的最优化问题 在1820年,Gauss利用消去法解线性方程组.在1945年,计算机出现.在1947年,Dantzig 发明单纯形法.在1968年,Fiacco and McCormick 引进内点法.在1984年,Karmarkar 提出了解线性规划的有效算法.背景聚焦背景聚焦2019.5.41单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级42单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级42单击此处编辑母版副标题样式42单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.42数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 重要人物重要人物 John Von NeumannGeorge B.Dantzig Leonid Vitalyevich KantorovichNarendra Karmarkar Harry Max Markowitz背景聚焦背景聚焦2019.5.42单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级43单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级43单击此处编辑母版副标题样式43单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.43数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 重要人物重要人物 John Von Neumann 约翰冯诺依曼(19031957),美藉匈牙利人.20世纪最杰出的数学家之一,被誉为”计算机之父”,”博弈论之父”.被认为是数学规划的三大创始人之一.背景聚焦背景聚焦2019.5.43单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级44单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级44单击此处编辑母版副标题样式44单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.44数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 George B.DantzigGeorge B.Dantzig(1914-2019),美国人,线性规划单纯形法的创始人,被誉为”线性规划之父”.美国科学院三院院士,美国军方数学顾问,教授.并以其名字设立Dantzig奖.数学规划的三大创始人之一.发现算法时非常年轻,以至到日本时,人们以为”线性规划之父”是个老人,而对他无人问津.背景聚焦背景聚焦2019.5.44单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级45单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级45单击此处编辑母版副标题样式45单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.45数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 Leonid Vitalyevich Kantorovich Kantorovich(1912-1986)苏联人,著名数学家和经济学家,教授,年仅18岁获博士学位.因在经济学上提出稀缺资源的最优配置获诺贝尔奖.线性规划对偶理论的提出者,数学规划的三大创始人之一.背景聚焦背景聚焦2019.5.45单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级46单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级46单击此处编辑母版副标题样式46单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.46数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 背景聚焦背景聚焦2019.5.46单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级47单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级47单击此处编辑母版副标题样式47单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.47数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 在1990年,Markowitz因为金融经济学方面的贡献和另外两位学者分获诺贝尔经济学奖.左边的文字说明了他获奖的原因以及关于他的理论的简介.背景聚焦背景聚焦2019.5.47单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级48单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级48单击此处编辑母版副标题样式48单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.48数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事美国电话电报公司网络美国电话电报公司网络的快速恢复及优化的快速恢复及优化 大陆航空公司乘务组大陆航空公司乘务组快速补救计划快速补救计划香港国际货柜码头香港国际货柜码头装卸的优化决策装卸的优化决策2019.5.48单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级49单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级49单击此处编辑母版副标题样式49单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.49数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 问题：甚至在九一一恐怖袭击事件之前,美国大陆航空公司总裁就考虑到对大型航空公司,应该制定一个危机计划,以应对紧急情况。突发事件,包括恶劣的天气,飞机机械故障 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 乘务组缺班，航空公司会面临航班中断,航班延误,取消等情况。由于乘务组未必能够保证剩余的定期航班的正常飞行.航空公司必须尽快让乘务组完成补偿飞行计划，并返回自己的原时刻表。这个决策要满足成本最小、政府规定、合同约定以及对生活品质的要求。解决这些问题需要专门的能进行复杂建模并平衡多种因素的运筹研究技术。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.49单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级50单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级50单击此处编辑母版副标题样式50单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.50数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 运筹学解决方案：大陆航空公司采用Caleb技术,研发了CrewSolver决策支持系统，生成全局最优或接近最优的乘务组补救方案.大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 效果：大陆航空公司自实施此计划以来，在每一次严重的突发事件中,都能实现乘务组快速补救,取得价值数百万美元的效益。公司估计,在2019年CrewSolver系统帮助它节省约了4000万美元。由于该系统,使美国航空业自2019年9月11日后开始复苏,从那时起,五家航空公司已采用了类似的基于运筹学的软件用于突发事件后航班时刻表、飞行员安排等的补救计划。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.50单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级51单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级51单击此处编辑母版副标题样式51单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.51数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 背后的故事：2019年，美国大陆航空公司邀请于刚教授为他们编写决策支持系统。于刚领导他的研究人员克服了重重困难，取得了一个又一个的突破性成果，为大陆航空公司编写了三个决策支持系 统，解决了当航空系统遭遇恶劣天气、飞机故障等干扰后，飞机航班的最优恢复问题、机组人员的调度问题和机组人员的计划、培训、休假等总体决策的最优方案。2019年9月11日，震惊世界的“9.11”恐怖事件不幸发生了。这次事件给美国航空业带来了灾难性的打击。但是，就是通过这次突发的灾难性事件，于刚的实时决策系统的优越性得到了充分体现。大陆航空公司由于采用了他的优化实时决策系统，比其他航空公司提前两天开始正常运营，为公司挽回3000多万美元的损失。由于有了于刚的完备的决策支持系统，大陆航空公司在整个“9.11”事件中避免了上亿美元的损失。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.51单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级52单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级52单击此处编辑母版副标题样式52单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.52数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 大陆航空公司乘务组快速补救计划大陆航空公司乘务组快速补救计划 该案例使旅美华裔著名运筹学家于刚教授荣获2019年度运筹与管理科学应用Franz Edelman 奖，Franz Edelman奖是由世界著名的运筹和管理科学家Franz Edelman于1971年创立的。它作为运筹和管理科学在国际上的一项最高荣誉，一年一度地颁发给在这一领域取得了最突出成就的科学家和企业家。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.52单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级53单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级53单击此处编辑母版副标题样式53单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.53数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 问题：AT&T是一个全球性电信公司，提供多种服务,如远程语音数据、视频、无线通讯、卫星及互联网服务。AT&T面对的问题是防止网络出错,并提供应对失误发生时的快速反应。AT&T在发生网络 故障时，要快速改换通讯通道,这要求网络有足够的恢复能力来传送相应需求。这个问题很重要,因为服务的失败,直接影响到公司的核心服务和客户忠诚度。解决它需要运筹学研究专门技术,因为这个问题涉及到全系统而运筹学有强大的能力来处理众多的参数。AT&TAT&T网络的快速恢复及优化网络的快速恢复及优化拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.53单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级54单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级54单击此处编辑母版副标题样式54单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.54数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 运筹学解决方案：一个由运筹学专家、网络设计师、管理者组成的AT&T团队提出了一种方法，在任何单一链接出现故障时，通过确定修复能力要求的适当的数量和位置,来恢复需求。该办法使网络恢复成本最小化,并产生新的恢复路径。价值：在约10个月内，AT&T团队以此方法为工具,优化恢复能力的配置.这一工具被扩展到交换中心出现故障时的恢复，并用于重新优化整个修复网络。该项目有助于AT&T实现高质量的服务,同时节省宝贵的资源,节约成本数亿美元，增加了收入。AT&TAT&T网络的快速恢复及优化网络的快速恢复及优化拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.54单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级55单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级55单击此处编辑母版副标题样式55单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.55数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 问题：在90年代,拥有世界上最繁忙的港口货物处理设施的香港国际货柜码头（HIT）,在更有效率的华南沿海新兴港口的冲击下，面临着丢失市场份额的严重威胁。香港地区蓬勃的出口制造业为主的经济,加上大幅度上升的进口货物，港口要处理每一天成千上万通过码头的海运集装箱货物显得捉襟见肘。香港国际货柜码头存在的严重及持续的物理空间上的制约，并不是新的港口竞争的问题,它的原因在于在存储和调度航运货柜中的低效率.运筹学解决方案：在2019，HIT认识到必须采用一个新的,基于运筹学的决策支持工具,大大提高码头操作工作效率,以容纳和处理每星期约125停靠港口船只的货物。香港国际货柜码头装卸的优化决策香港国际货柜码头装卸的优化决策拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.55单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级56单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级56单击此处编辑母版副标题样式56单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.56数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 机来卸货,一个起重机需要安排多少车来接货，何时安排卡车依次搬运走船上的集装箱出码头.使用定制算法,即智能业务规则，3P对基本的终端业务提供优化决策支持.价值：HIT应用3P使得其集装箱处理能力在不增加人员,设备或地产情形下，增加50%。3P的基本收益,从港口客户的角度而言,是体现在船舶周转时间和装卸费用上。3P系统减少了30%的船舶周转时间,降低了35%每个集装箱的平均处理成本.3P也有一定的环境效益:更有效率的码头作业减少了一半在港口设施中利用柴油车往来搬运集装箱的污染。香港国际货柜码头装卸的优化决策香港国际货柜码头装卸的优化决策运筹学解决方案：尤其是“3P”(即生产力+程序),将有助改善及加速基本决策，如何规划在院子里的集装箱货车路径,抵港集装箱应在设施那里贮存，每艘船舶应该用多少起重拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.56单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级57单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级57单击此处编辑母版副标题样式57单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.57数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 奖奖项项：香港国际货柜码头在发展及应用创新科技方面精益求精，多次获得业界大奖。2019年11月5日，凭借自行开发的新一代码头 管 理 系 统 （Next Generation Terminal Management System，nGen），（3p3p的的前前身身）香港国际货柜码头成功击败十个优秀竞争对手，夺得了亚太资讯及通讯科技大奖2019(APICTA)工业应用项目大奖；另外，在2019香港资讯及通讯科技奖中，香港国际货柜码头再接再厉，获颁电子商务大奖；其新一代码头管理系统获得了电子商务（应用）组别的金奖。叶承智（左）从唐英年手中接过电子商务大奖拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.57单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级58单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级58单击此处编辑母版副标题样式58单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.58数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 问题：作为世界上最大的包裹公司，联合包裹服务公司（UPS）依靠高效率的规划和枢纽航线与支线航线网络的运作，包括七个枢纽中心和 联合包裹服务公司优化空中与地面运输计划联合包裹服务公司优化空中与地面运输计划 美国国内近100个机场，每晚运送次日到达户主的物品超过100万个。要使这样一个庞大的系统具有更大的效率是一个挑战。目前已知的求解大型网络设计问题的算法对规划UPS的航空网络是不够的,主要的障碍是复杂而庞大的空中运输,涉及超过17000从始点到终点的流量，9种不同类型超过160架的飞机。解决这些问题需要在大规模优化、整数规划等运筹学研究专门技术。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.58单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级59单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级59单击此处编辑母版副标题样式59单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.59数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 联合包裹服务公司优化空中与地面运输计划联合包裹服务公司优化空中与地面运输计划运筹学解决方案：UPS航空工作组与美国麻省理工学院的专家在运输系统方面进行了合作,联合研究和开发出基于最优化设计的UPS航空网络计划系统。为确保隔夜交货,此方案能同时确定具有最小成本的飞机航线,车队作业计划以及配套的路线。项目组建立的整数规划模型,与常规网络设计类似,但却能极大改善基于线性规划的解的范围.此方案对原有规划要解决的实际问题的求解时间,一般不超过6小时,在许多情况下,不超过一小时,大幅度节省了时间。价值:UPS规划者现在利用此系统产生的方案和见解来实现计划的优化。UPS的管理者确信,此系统及伴随的业务变化，已给公司节省超过870万美元,并预计在未来十年可再节省1.89亿美元。此方案带来的其他的好处包括：减少了网络规划时间,减少了高峰和非高峰期的成本,减少了飞机队需求量并改进了计划。拓拓 展展 _优化技术成功应用的故事优化技术成功应用的故事2019.5.59单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级60单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级60单击此处编辑母版副标题样式60单击此处编辑母版标题样式单击此处编辑母版文本样式第二级第三级第四级第五级2002.5.60数学实验之线性规划实验目的 应用场景实验原理软件实现 范 例 布置实验 结 束背景聚焦 拓 展 问题：医疗保健行业经济的急剧变化使得克萨斯儿童医院面临着风险，成本不断上涨的医疗服务和设备,来自私人保险和公共医疗融资方案,如 得克萨斯儿童医院最小化金融风险得克萨斯儿童医院最小化金融风险 医疗补助对吸纳这些较高的成本的阻力，使得这个全国最大的儿科医疗保健机构面临艰难决策。此外,新合同偿还结构,其中包括“诊断相关组”(DRG)和“固定门诊费用”(预付)的安排,可能会转移巨额财务风险到得克萨斯儿童医院,因此医院要有合同谈判的更有