管理运筹学讲义课件

管理运筹学

-管理科学方法谢家平博士教授博士生导师研究领域：管理科学、运营管理、供应链管理讲授课程：管理运筹学-管理科学方法、管理系统工程、运营管理、供应链管理、ERP、国际物流、企业物流管理、管理决策模型与方法单位：上海财经大学工商学院物流管理系E-mail：jiaping@1管理运筹学

-管理科学方法谢家平博士教授1教材与参考书籍教材：谢家平编著.管理运筹学：管理科学方法，中国人民大学出版社，2010参考书：Davidetal.数据、模型与决策，机械工业出版社，2004费雷德里克.数据、模型与决策，中国财政经济出版社，2004Jamesetal.数据、模型与决策，中国人民大学出版社，20062教材与参考书籍教材：232课时讲授提纲绪论第一章线性规划第二章线性规划讨论第三章对偶规划静态规划第四章整数规划第五章目标规划第六章动态规划动态优化第七章网络分析第八章网络计划第九章决策分析第十章方案排序第十一章库存控制第十二章排队理论离散优化随机优化淡化数学算法LINDO求解332课时讲授提纲绪论离散优化随机优化淡化数学算法3考核方式结课考试：笔试（开卷or闭卷？）每章一题80%案例研究：选择合适方法结合企业实际进行应用20%4考核方式结课考试：4管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。

OperationsResearch日本译作“运用学”香港、台湾译为“作业研究”我国译作“运筹学”源于古语“运筹帷幄之中，决胜千里之外”取“运筹”二字，体现运心筹谋、策略取胜ManagementScience管理科学运用数学、统计学和运筹学中的量化分析原理和方法，建立数学模型/计算机仿真，给管理决策提供科学依据。5管理运筹学的称谓管理运筹学是一门研究如何最优安排的学科。5绪

论一、发展历史二、学科作用三、学科性质四、工作程序五、学科体系六、学习要求6绪论一、发展历史6一、发展历史1.早期的运筹思想

齐王赛马•渭修皇宫沈括运军粮•科学管理2.军事运筹学阶段

20世纪40年代诞生于英美1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称OperationalResearch，意为作战研究。美国和加拿大也在军队设立运筹学小组，称OperationsResearch，协助指挥官研究战略及战术问题。3.管理运筹学阶段战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。7一、发展历史1.早期的运筹思想7企业的成功要素中：观念意识更新47％人文文化35％技术优势18％决策意识的科学性成功决策正确决策二、学科作用理念的重要性？8企业的成功要素中：二、学科作用理念的重要性？8二、学科作用1.量化管理的重要性

管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。目的：用科学方法分析管理问题，为管理者决策提供依据目标：在企业经营内外环境的限制下，实现资源效用最大组织中存在的问题定量分析定性分析评价与评估决策量化管理是第一步,它导致控制,并最终实现改进如果不能量化某些事情，那么就不能理解它如果不能理解它，那么就不能控制它如果不能控制它，那么就不能改进它——H.JamesHarrington定性到定量分析，数量界限的重要性：量变引起质变9二、学科作用1.量化管理的重要性组织中存定量分析定性分析听一场音乐会：网络订票的票价500元，不去可退票情况1：在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？二、学科作用2.量化思考使人理性

冰淇淋实验：一杯A有70克，装在50克的杯子里，看上去要溢出了一杯B是80克，装在100克的杯子里，看上去还没装满

单独凭经验判断时，在相同的价格上，人们普遍选择A

实验表明，大部分的回答者仍旧会去听结果却是，大部分人回答说不去了10听一场音乐会：网络订票的票价500元，不去可退票二、学科作用二、学科作用3.量化分析辅助决策

盈亏平衡分析40,00080,000120,000160,00004080120160200Revenue=900xFixedcostLossProfitCost=50,000+400xxBreak-evenpoint=100units利润：I=(P–Cm–Ch)Q-F策略1↑↑↔↔↔↔差异化，领先者战略策略2↑↔↔↔↑↔规模化，大规模市场策略3↑↔↓↔↔↔机械化，第一利润源策略4↑↔↔↓↔↔技能化，第二利润源策略5↑↔↕↕↔↓信息化，第三利润源11二、学科作用3.量化分析辅助决策盈亏平衡分二、学科作用量化辅助决策案例：盈亏平衡分析例：某企业总销售额1100万元物料成本700万元员工工资200万元管理费用100万元现在利润=100万元，目标利润150万元利润实现的方法有：将销售收入增加100%将员工工资减少25%将管理费用减少50%将物料成本减少7.1%12二、学科作用量化辅助决策案例：盈亏平衡分析利润实现的方法有：二、学科作用4.决策意识的重要性

生产计划决策一星期工作5天,每天正常工作8小时一周作业费用：11000(直接人工成本与间接费用)直接人工成本：10/1h(一台机器需一位作业人员)间接费用：人工成本2.5倍甲乙丙原料659565直接工时65分95分65分直接人工121410间接費用303525总成本107144100售价173233170利润668970H18H6H10甲设备数EGHFHGG20H13E6F10裝配E24E15G7DG14G10H7F10G7G4CBA裝配H14乙丙13二、学科作用4.决策意识的重要性生产计划决策一星期工二、学科作用甲产品产量40,乙产品80,丙产品40利润=40×66+80×89+40×70=12560

人员有限如何实现?采取什么薪酬制度?计件工资制，让员工自愿加班甲乙丙单位产品总成本107144100单位产品售价173233170单位产品利润668970市场每周需求408040决策的科学性？方案一14二、学科作用甲产品产量40,乙产品80,丙产品40甲二、学科作用甲产品产量40,乙产品80,丙产品40总收入=40×173+80×233+40×170=32360原料成本=40×65+80×95+40×65=12800营运费用=11000总利润=32360-12800-11000=8560人员有限如何实现?采取什么薪酬制度?岗位工资制（定岗定员），让员工自觉加班甲乙丙原料659565运营费用11000售价173233170市场每周需求408040决策的科学性？方案二15二、学科作用甲产品产量40,乙产品80,丙产品40二、学科作用决策的科学性？产能符合计算甲乙丙总成本107144100售价173233170利润668970乙与丙哪一个产品比较赚钱?

产品市场需求单位产品设备工时消耗EFGH甲400103131乙8030202113丙401502124需求产能3000200037603240可用产能2400240048004800E是瓶颈16二、学科作用决策的科学性？产能符合计算甲乙丙总成本1071二、学科作用方案三：计时工资，且以单位利润率高低为决策意识。

乙比较赚钱,假如80个全部生产需用E产能2400分钟，但是E只有2400分钟可用因此只能生产80个乙(2400/30)，而丙无法生产方案：甲产品40个，乙产品80个，丙产品0个总收入=40×173+80×233+0×170=25560

原料=40×65+80×95+0×65=10200

，营运费用=11000利润=25560-10200-11000=4360方案四：计时工资，但以占用瓶颈资源大小为决策意识。

丙比较赚钱,优先生产40个需用E产能600(40ⅹ15)分钟剩下1800分钟,可生产60个乙(1800/30)方案：甲产品40个，乙产品60个，丙产品40个总收入=40×173+60×233+40×170=27700原材料=40×65+60×95+40×6540=10900

，营运费用=11000利润=27700-10900-11000=580017二、学科作用方案三：计时工资，且以单位利润率高低为决策意识三、学科性质1.研究对象经济和管理活动中能用“数量关系”描述的如运营、规划与组织管理问题解决的理论模型和优化方法实践2.学科特点强调科学性和定量分析强调应用性和实践性强调从整体上进行把握18三、学科性质1.研究对象18四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环境分析确定目标制定准则收集资料数量关系结构分析数学模型制定决策方案选择算法求解方案优选否是方案实施持续改进识别问题量化分析建立模型软件求解结果分析确定方案实施方案控制管理者解的分析19四、工作程序管理者制定决策：管理运筹学的步骤：明确问题环境分五、学科体系1.管理问题

需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响?生产计划在有限资源约束下，生产什么，生产多少，获利最大？资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业的重要次序如何，作业的顺序安排如何?市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？设施选址运营点如何选择，需要哪些运作设施，设施如何布局?库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金资金投放的数量，从何处进行融资，资金成本是多少?排队问题队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务?20五、学科体系1.管理问题需求预测产品的市场需求量有多大五、学科体系2.学科内容

模型类型解决的典型办法线性规划在线性目标和约束条件间取得最优化结果整数规划在线性目标和约束条件间寻求整数决策最优目标规划在相对立的目标间寻得多目标妥协的满意解动态规划寻求多阶段动态系统的整体决策优化问题网络分析寻求网络路径、流量分布、网络瓶颈及其改进网络计划用各种作业和结点的网络排列来说明项目实施计划管理决策依据决策准则权衡比较备选方案的决策结果方案排序综合各方案的优势与不足寻求多指标排名次序库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量统计方法从一个抽样得到普遍结果的推论和曲线拟合排队理论分析正在等待的队列特点及其运行指标仿真模拟动态观察复杂的管理问题的行为，模拟管理系统的结构关系21五、学科体系2.学科内容模型类型解决的典型办法线性规划在五、学科体系3.学科应用管理既是科学又是艺术低层管理的科学成分较多，高层管理的艺术成分较多运营管理需较多管理科学，人力资源管理需较多管理艺术例行管理需要较多管理科学，例外管理需要较多管理艺术M:管理决策问题MC:定量解决方法方案选择依据问题导向技术支持战略决策营销决策生产安排财务分析人力资源方案优选……应用统计线性规划整数规划目标规划网络计划网络分析决策分析动态规划……管理科学：运用合理的分析来改善决策的制定管理者:制定决策22五、学科体系3.学科应用M:管理决策问题MC:定量解决六、学习要求1.学科地位

数学技术科学管理学科基础管理运筹学管理专业课高等数学、概率统计、线性代数…加工技术、工程技术、信息技术…经济学原理、管理学、行为科学…离散、连续，静态、动态的方法…战略、运营、营销、财务、人力…23六、学习要求1.学科地位数学技术科学管理学科基础管理运六、学习要求经济学企业战略、公司治理会计学财务管理人力资源管理组织行为学管理科学方法支持企业B行业企业C企业A商务2商务3商务1职能b职能c职能a小组ii小组iii小组i运营管理市场营销质量管理项目管理……信息管理流程管理物流管理供应链管理……24六、学习要求经济学企业战略、公司治理会计学人力资源管理组织行六、学习要求2.如何学习重点在结合实际的应用发挥自己管理实践经验丰富和理论联系实际的能力强化结合实际问题建立管理优化模型的能力强化解决问题的方案或模型的解的分析与应用能力充分借用管理运筹学教学软件25六、学习要求2.如何学习重点在结合实际的应用25第1章线性规划Subtitle内容提要第一节线性规划的一般模型一、线性规划的三个要素二、线性规划模型的特征三、线性规划的图解方法四、线性规划解的可能性第二节线性规划的单纯形法一、线性规划的标准型式二、线性规划之解的概念三、单纯形法的基本原理26第1章线性规划Subtitle内容提要第一节线性一、线性规划的三个要素第一节线性规划的一般模型

决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小27一、线性规划的三个要素第一节线性规划的一般模型决策变量二、线性规划模型的举例第一节线性规划的一般模型

1、生产计划问题例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。产品设备工时消耗甲乙工时成本元/h生产能力hABC20023420151016103228二、线性规划模型的举例第一节线性规划的一般模型1、生产第一节线性规划的一般模型

(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为2x1≤16同理，设备B的加工能力约束条件表达为2x2≤10设备C的装配能力也有限，其约束条件为3x1+4x2≤32(3)目标函数：目标是企业利润最大化

maxZ=

3x1+5x2

(4)非负约束：甲乙产品的产量为非负

x1≥0，x2≥0综上的LP模型：29第一节线性规划的一般模型(1)决策变量：设x1为甲产品的二、线性规划模型的举例第一节线性规划的一般模型

2、物资运输问题例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从Ai到Bj的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。

销地产地B1B2B3B4产量A1632550A2758420A3329730销量2030104030二、线性规划模型的举例第一节线性规划的一般模型2、物资第一节线性规划的一般模型

(1)决策变量：设从Ai到Bj的运输量为xij，(2)目标函数：运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件：产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34=30销售平衡条件x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40非负性约束

xij≥0(i=1,2,3；j=1,2,3,4)

31第一节线性规划的一般模型(1)决策变量：设从Ai到Bj的二、线性规划模型的举例第一节线性规划的一般模型

3、产品配比问题例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。

决策变量：取45%和92%的硫酸分别为x1和x2吨约束条件：求解二元一次方程组得解非负约束：x1

≥0，x2

≥032二、线性规划模型的举例第一节线性规划的一般模型3、产品第一节线性规划的一般模型

若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？取这5种硫酸分别为

x1、x2、x3、x4、x5

，有有多少种配比方案？何为最好？若5种硫酸价格分别为400,700,1400,1900,2500元/t，则：33第一节线性规划的一般模型若有5种不同浓度的硫酸三、线性规划模型的特征第一节线性规划的一般模型

1、模型隐含假定（1）线性化假定函数关系式f(x)=c1x1+c2x2+…+cnxn，称线性函数。建模技巧：将非线性的函数进行分段线性化。（2）同比例假定决策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。

（4）连续性假定决策变量取值连续。（5）确定性假定所有参数都是确定的，不包含随机因素。34三、线性规划模型的特征第一节线性规划的一般模型1、模型三、线性规划模型的特征第一节线性规划的一般模型

2、一般数学模型用一组非负决策变量表示的一个决策问题；存在一组等式或不等式的线性约束条件；有一个希望达到的目标，可表示成决策变量的极值线性函数。35三、线性规划模型的特征第一节线性规划的一般模型2、一般四、线性规划的图解方法第一节线性规划的一般模型

1、线性规划的可行域可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。maxZ=

3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD36四、线性规划的图解方法第一节线性规划的一般模型1、线性2x1=162x2=10x1x248103583x1+4x2

=320ABCD四、线性规划的图解方法第一节线性规划的一般模型

2、线性规划的最优解目标函数Z=

3x1+5x2

代表以Z为参数的一族平行线。Z=30Z=37Z=15372x1=162x2=10x1x248103583x1+四、线性规划的图解方法第一节线性规划的一般模型

3、线性规划解的特性abcd由线性不等式组成的可行域是凸多边形(凸多边形是凸集)凸集定义：集合内部任意两点连线上的点都属于这个集合可行域有有限个顶点。目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。38四、线性规划的图解方法第一节线性规划的一般模型3、线性五、线性规划解的可能性第一节线性规划的一般模型

1、唯一最优解：只有一个最优点2、多重最优解：无穷多个最优解当市场价格下降到74元，其数学模型变为

2x1=162x2=103x1+4x2

=32x1x248102580ABCDZ=24Z=32Z=1239五、线性规划解的可能性第一节线性规划的一般模型1、唯一最五、线性规划解的可能性第一节线性规划的一般模型

3、无界解：可行域无界，目标值无限增大(缺乏必要约束)40五、线性规划解的可能性第一节线性规划的一般模型3、无界解五、线性规划解的可能性第一节线性规划的一般模型

4、没有可行解：线性规划问题的可行域是空集(约束条件相互矛盾)目标冲突利害冲突目标强冲突利害弱冲突41五、线性规划解的可能性第一节线性规划的一般模型4、没有可一、线性规划的标准型式第二节线性规划的一般模型

1、标准型表达方式(1)代数式

(2)向量式

(3)矩阵式

A：技术系数矩阵，简称系数矩阵；B：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。42一、线性规划的标准型式第二节线性规划的一般模型1、标准一、线性规划的标准型式第二节线性规划的一般模型

2、标准型转换方法(1)如果极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)若某个bi<0，则以－1乘该约束两端，使之满足非负性的要求。(3)对于≤型约束，则在左端加上一个非负松弛变量，使其为等式。

(4)对于≥型约束，则在左端减去一个非负剩余变量，使其为等式。

(5)若某决策变量xk无非负约束，令xk=x'k-x"k，(x'k≥0,x"k≥0)。43一、线性规划的标准型式第二节线性规划的一般模型2、标准二、线性规划之解的概念第二节线性规划的一般模型

基矩阵：一个非奇异的子矩阵（线性无关）。矩阵A中任意m列的线性无关子矩阵B，称为一个基。组成基B的列为基向量，用Pj表示(j=1,2,…,n)。基变量：与基向量Pj相对应的m个变量xj称为基变量其余的n-m个变量为非基变量1、线性规划解之关系

基解：令所有非基变量等于零，得出基变量的唯一解。x3x4x5基变量是x3,x4,x5非基变量是x1,x2令非基变量x1=x2=0，得到一个基解x3=16，x4=10，x5=3244二、线性规划之解的概念第二节线性规划的一般模型基矩阵：二、线性规划之解的概念第二节线性规划的一般模型

1、线性规划解之关系

可行解：满足约束条件AX=b,X≥0的解。可行基：可行解对应的基矩阵。基可行解：满足非负性约束的基解称为基可行解。最优解：使目标函数最优的可行解，称为最优解。

最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解基可行解45二、线性规划之解的概念第二节线性规划的一般模型1、线性二、线性规划之解的概念第二节线性规划的一般模型

2、线性规划基本原理定理1.

若线性规划问题存在可行域，则其可行域一定是凸集。定理2.

线性规划问题的基可行解对应可行域的顶点。定理3.

若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。定理4.

线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。46二、线性规划之解的概念第二节线性规划的一般模型2、线性二、线性规划之解的概念第二节线性规划的一般模型

3、线性规划解题思路先找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。如果是最优解，就得到这个线性规划问题的最优解；如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解；如果还不是，再接着进行下一个可行基变化，直到得到最优解。47二、线性规划之解的概念第二节线性规划的一般模型3、线性三、单纯形法的基本原理第二节线性规划的一般模型

maxZ=3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32

Cj比值CBXBb检验数jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=848三、单纯形法的基本原理第二节线性规划的一般模型ma三、单纯形法的基本原理第二节线性规划的一般模型

162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb检验数jx1x2x3x4x535000检验数j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解:X*=(4,5,8,0,0)T，Z*=3749三、单纯形法的基本原理第二节线性规划的一般模型1620三、单纯形法的基本原理第二节线性规划的一般模型

单纯形的管理启示2x1=162x2=103x1+4x2

=32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,10,0,12)TX1=(4,5,8,0,0)T企业管理过程也是如此，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求完美。50三、单纯形法的基本原理第二节线性规划的一般模型单纯形的第2章线性规划讨论Subtitle内容提要第一节目标函数的描述技巧计件工资岗位工资计时工资

第二节线性规划的适用层次第三节线性规划的典型案例第四节线性规划灵敏度分析价值系数的变动分析资源数量的变动分析51第2章线性规划讨论Subtitle内容提要第一节计件工资体系，目标是企业利润最大化：第一节目标函数的描述技巧一、计件工资

产品甲：产品乙：产品丙：非负性约束计件工资制薪酬体系下，工作时间不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：经Lindo软件求解，得到最优解为Z=12560，产品甲x1=40，产品乙x2=80，产品丙x3=40。52计件工资体系，目标是企业利润最大化：第一节目标函数的描述技第一节目标函数的描述技巧二、岗位工资

岗位工资制薪酬体系，以计时工资制为基础，实行定岗定员。总收入=173x1+233x2+170x3，原料成本=65x1+95x2+65x3，营运费用=11000，则目标函数为maxZ=108x1+138x2+105x3-11000岗位工资制薪酬体系下，工作时间也不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：产品甲：产品乙：产品丙：非负性约束经Lindo软件求解，得到最优解为Z=8560,x1=40,x2=80,x3=40。53第一节目标函数的描述技巧二、岗位工资岗位工资制薪酬体系，第一节目标函数的描述技巧三、计时工资

目标函数为经Lindo软件求解，得到最优解为Z=5800,x1=40,x2=60,x3=40。设备E：设备F：设备G：设备H：产品甲：产品乙：产品丙：市场需求约束设备能力约束54第一节目标函数的描述技巧三、计时工资目标函数为经Lind第二节线性规划的适用层次计划链的层次粗能力计划定单可行不可行CRP主生产计划MPS物料需求计划MRP能力需求计划车间作业计划销售计划可行否作业统计与控制物料清单库存管理外购计划供应商成品、在制品信息生产计划大纲预测当前条件经营计划产值计划或利润计划绝对数量或增长幅度期限:年度单位:万元大类产品销售收入或台套

产品品种和数量如何确定期限:年度单位:万台具体产品在具体时段的出产计划合同订单和预测转换为生产任务将产品出产计划转换成物料需求表大类产品年度生产计划确定产品的品种和数量期限:年度单位:万台55第二节线性规划的适用层次计划链的层次粗能力计划定单可行不第三节线性规划的典型案例配送中心选择例：某企业存在两个供货源（产地），已知原有供货源每月的供货能力是5万台产品，新增供货源的生产能力可以满足产品的需求，且两个货源的价格相同。有三个区域目标市场（销地或销售商），各销地每月的市场需求量为5万台、10万台、5万台。在分销渠道中，拟定在2个地点中选址设立分销中心，执行产品的转运任务。各地之间的单位运输物流成本（由距离和运输方式决定）56第三节线性规划的典型案例配送中心选择例：某企业存在两个第三节线性规划的典型案例决策变量：设从供货源到分销中心的运输量为，从分销中心到需求市场的运输量为。选址规划在于二者的实际取值。如果，则不设置分销中心；反之，则设置,其规模为如果，则不设置分销中心；反之，则设置，其规模为目标函数：各条路段上的实际运输量乘以物流运输的单位费用之总和最小，即存在供应能力约束、市场需求约束、配送中转约束，如下：57第三节线性规划的典型案例决策变量：设从供货源到分销中心的运第三节线性规划的典型案例供应能力平衡约束：市场需求平衡约束配送中心不存留产品所有变量大于等于零58第三节线性规划的典型案例供应能力平衡约束：58第四节线性规划灵敏度分析一、灵敏度分析的必要性线性规划研究的是一定条件下的最优化问题资源环境和技术条件是可变的基础数据往往是测算估计的数值灵敏度分析的概念灵敏度分析又称敏感性分析或优化后分析研究基础数据发生波动后对最优解的影响最优解对数据变化的敏感程度在多大的范围内波动才不影响最优基灵敏度分析解决的问题：参数在什么范围变化而最优基不变已知参数的变化范围，考察最优解(最优基)是否改变59第四节线性规划灵敏度分析一、灵敏度分析的必要性线性规划研第四节线性规划灵敏度分析一、价值系数的变动分析非基变量Cj的变化范围非基变量Cj变化，只影响它自己的检验数Cj35000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/203x14100-2/31/3检验数j000-1/2-1参数Cj的变化范围：价值系数Cj变化影响检验数60第四节线性规划灵敏度分析一、价值系数的变动分析非基变量C第四节线性规划灵敏度分析一、价值系数的变动分析基变量CBl的变化范围CjC15000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/20C1x14100-2/31/3检验数j0002C1/3-5/2-C1/361第四节线性规划灵敏度分析一、价值系数的变动分析基变量CB第四节线性规划灵敏度分析二、右端常量的变动分析参数bi的变化范围

第r个约束的右端项为br，增量br，其它数据不变。新的基解为只要X'B≥0，则可保持最优基不变。62第四节线性规划灵敏度分析二、右端常量的变动分析参数bi的第3章对偶规划Subtitle内容提要第一节对偶规划的数学模型

对偶问题的提出对偶规划的性质

第二节对偶规划的经济解释

影子价值的内涵影子价值的应用

第三节资源定价的决策案例63第3章对偶规划Subtitle内容提要第一节对偶第一节对偶规划的数学模型一、对偶问题的提出若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：①合理安排生产能取得多大利润?②为保持利润水平不降低，资源转让的最低价格是多少？问题①的最优解：x1=4，x2=5，Z*=37。64第一节对偶规划的数学模型一、对偶问题的提出若例1中该厂的产第一节对偶规划的数学模型一、对偶问题的提出出让定价假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有2y1+0y2+3y3≥3同理，对乙产品而言，则有

0y1+2y2+4y3≥5设备台时出让的收益（希望出让的收益最少值）min16y1+10y2+32y3显然还有y1，y2，y3≥065第一节对偶规划的数学模型一、对偶问题的提出出让定价假设出让第一节对偶规划的数学模型一、对偶问题的提出例1的对偶问题的数学模型对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然前者称为线性规划原问题，则后者为对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。min=16y1+10y2+32y3

2y1+0y2+3y3≥3

0y1+2y2+4y3≥5y1，y2，y3≥0

S.t.maxZ=

3x1+5x22x1≤162x2≤103x1+4x2≤32x1,x2≥0S.t.66第一节对偶规划的数学模型一、对偶问题的提出例1的对偶问题的第一节对偶规划的数学模型二、对偶规划的性质1、对称性定理

对偶问题的对偶问题是原问题。根据对偶规划，很容易写出对偶问题的对偶问题模型。2、最优性定理

设，分别为原问题和对偶问题的可行解，且则，分别为各自的最优解。3.对偶性定理

若原问题有最优解，那么对偶问题也有最优解，而且两者的目标函数值相等。4.互补松弛性

最优解的充分必要条件是，67第一节对偶规划的数学模型二、对偶规划的性质1、对称性定理6第二节对偶规划的经济解释一、影子价值的内涵左边是资源bi每增加一个单位对目标函数Z的贡献；对偶变量yi在经济上表示原问题第i种资源的边际价值。对偶变量的值yi*表示第i种资源的边际价值，称为影子价值。若原问题价值系数Cj表示单位产值，则yi称为影子价格。若原问题价值系数Cj表示单位利润，则yi称为影子利润。影子价格=资源成本+影子利润68第二节对偶规划的经济解释一、影子价值的内涵左边是资源bi每第二节对偶规划的经济解释一、影子价值的内涵影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。对资源i总存量的评估：购进or出让对资源i当前分配量的评估：增加or减少第一，影子利润说明增加哪种资源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租/转让的基价第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺69第二节对偶规划的经济解释一、影子价值的内涵影子价格不是资源第三节资源定价的决策方案例：某厂生产甲乙产品，（1）如何安排每周的利润为最大?

（2）如果企业可以不生产，那资源出让如何定价？甲乙资源成本资源拥有量原材料(kg)设备(工时)电力(度)943451020501360200300销售价格(元)390352一、最优生产决策70第三节资源定价的决策方案例：某厂生产甲乙产品，（1）如何安第三节资源定价的决策方案二、资源获利决策如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。设原材料的单位出让获利为y1，设备工时的单位出让获利为y3，电量的单位出让获利为y2。出让决策的线性规划模型：71第三节资源定价的决策方案二、资源获利决策如果决策者考虑自己第4章整数规划Subtitle内容提要第一节整数规划问题纯整数规划0-1规划混合整数规划第二节整数规划求解

分枝定界法

第三节整数规划应用72第4章整数规划Subtitle内容提要第一节整数第一节整数规划问题线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。要求全部或部分决策变量的取值为整数的线性规划问题，称为整数规划(IntegerProgramming)。全部决策变量的取值都为整数，则称为全整数规划(AllIP)仅要求部分决策变量的取值为整数，则称为混合整数规划(MixedIP)要求决策变量只取0或1值，则称0-1规划(0-1Programming)73第一节整数规划问题线性规划的决策变量取值可以是任意非负实数第一节整数规划问题一、纯整数规划产品资源甲乙现有量A219B5735单台利润65例：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示：问如何安排甲、乙两产品的产量，使利润为最大。解：设x1为甲产品的台数，x2为乙产品的台数。maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2

≥0x1,x2取整数74第一节整数规划问题一、纯整数规划产品甲乙现有量A219B5第一节整数规划问题二、0-1规划登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。解：对于每一种物品无非有两种状态，带或者不带，不妨设

序号1234567物品食品氧气冰镐绳索帐篷相机设备重量55261224重要性系数2015181484100-1规划的模型：75第一节整数规划问题二、0-1规划登山队员可携带最大重量为2第一节整数规划问题三、混合整数规划例：某产品有n个区域市场，各区域市场的需求量为bj吨/月；现拟在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选i地建厂，生产能力为ai吨/月，其运营固定费用为F元/月；已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？解：选址建厂与否是个0-1型决策变量，假设yi=1，选择第i址建厂，yi=0，不选择第i址建厂；计划从i址至区域市场j的运输运量xij为实数型决策变量。76第一节整数规划问题三、混合整数规划例：某产品有n个区域市场第二节整数规划求解一、舍入化整法为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到与最优解相近的整数解。这样做除少数情况外，一般不可行，因为化整后的解有可能超出了可行域，成为非可行解；或者虽是可行解，却不是最优解。

不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题对于例1的数学模型，不考虑整数约束的最优解：x1

*=28/9，x2

*=25/9，Z

*=293/9舍入化整x1=3，x2=3，Z=33，不满足约束条件5x1+7x2≤35，非可行解；x1=3，x2=2，Z=28，满足约束条件，是可行解，但不是最优解；x1=4，x2=1，Z=29，满足约束条件，才是最优解。77第二节整数规划求解一、舍入化整法为了满足整数解的要求，自然第二节整数规划求解二、穷举整数法对于决策变量少，可行的整数解又较少时，这种穷举法有时是可行的，并且也是有效的。但对于大型的整数规划问题，可行的整数解数量很多，用穷举法求解是不可能的。例如，指派问题。5x1+7x2=352x1+x2=9•(3,3)••••••••••x1x212312534478第二节整数规划求解二、穷举整数法对于决策变量少，可行的整数第二节整数规划求解三、分支定界法不考虑整数限制，先求出相应线性规划的最优解，若求得的最优解符合整数要求，则是原IP的最优解；若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。依次在缩小的可行域中求解新构造的线性规划的最优解，直到获得原整数规划的最优解。定界的含义：IP是在相应的LP基础上增加整数约束IP的最优解不会优于相应LP的最优解对MaxZ，相应LP的Z*是原IP的上界79第二节整数规划求解三、分支定界法不考虑整数限制，先求出相应第二节整数规划求解三、分支定界法x1≤3x1≥4x2≤2x2≥3x1≤2x1≥3x2≤3x2≥480第二节整数规划求解三、分支定界法x1≤3x1≥4x2≤2第三节整数规划应用一、生产基地规划例：某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问A、B类型基地各建设多少个，可使总生产能力最大？

解：设A、B两类基地各建设x1,x2个，则其模型为：81第三节整数规划应用一、生产基地规划例：某公司拟建设A、B两第三节整数规划应用二、人员安排规划某服务部门各时段(每2小时为一时段)需要的服务人数如表：解：设第j时段开始时上班的服务员人数为xj第j时段来上班的服务员将在第j+3时段结束时下班，故决策变量有x1,x2,x3,x4,x5。按规定，服务员连续工作8小时(4个时段)为一班。请安排服务员的工作时间，使服务员总数最少.82第三节整数规划应用二、人员安排规划某服务部门各时段(每2小第三节整数规划应用三、项目投资选择有600万元投资5个项目，收益如表，求利润最大的方案？83第三节整数规划应用三、项目投资选择有600万元投资5个项目第三节整数规划应用四、互斥约束问题例如关于煤资源的限制，其约束条件为：企业也可以考虑采用天然气进行加热处理：这两个条件是互相排斥的。引入0—1变量y，令互斥问题可由下述的条件来代替，其中M是充分大的数。

84第三节整数规划应用四、互斥约束问题例如关于煤资源的限制，其第三节整数规划应用五、租赁生产问题服装公司租用生产线拟生产T恤、衬衫和裤子。每年可用劳动力8200h，布料8800m2。T恤衬衫裤子劳动力326布料售价250400600可变成本100180300生产线租金(万)201510假设：yj=1，要租用生产线j

yi=0，不租用生产线j

第j种服装生产量xj85第三节整数规划应用五、租赁生产问题服装公司租用生产线拟生产第三节整数规划应用六、任务指派问题甲乙丙丁四个人，ABCD四项任务，如何指派总时间最短？解：引入0-1变量xij，

xij=1：任务j指派人员i去完成

xij=0：任务j不派人员i去完成

一项任务只由一个人完成一人只能完成一项任务86第三节整数规划应用六、任务指派问题甲乙丙丁四个人，ABCD第三节整数规划应用七、设施选址问题拟定在2个地点中选址设立分销中心，执行产品的仓储和转运，一个分销中心拟定设立一个仓库W1、W2。若设立仓库W1，建设成本为10万元，最大库容为20万台，单位产品的月库存成本为2元；若设立仓库W2建造成本为20万元，最大库容为25万台，单位产品的月库存成本为3元。如何选址和安排调运，建造费用+运输费用+仓储费用为最小？解：设从供货源Si到分销中心Wj的运输量为xij，从分销中心到需求市场Rk的运输量为yjk。仓库选址决策引入0-1变量wj：87第三节整数规划应用七、设施选址问题拟定在2个地点中选址设立第三节整数规划应用七、设施选址问题供应能力平衡约束：市场需求平衡约束：仓储能力限制约束：分销中心不存留产品：所有变量大于等于零：88第三节整数规划应用七、设施选址问题供应能力平衡约束：88第5章目标规划Subtitle内容提要第一节多目标规划问题第二节目标规划数学模型目标的期望值正负偏差变量目标达成函数目标优先级别第三节目标规划的图解法第四节目标规划单纯形法第五节目标规划应用案例89第5章目标规划Subtitle内容提要第一节多目第一节多目标规划问题一、线性规划的局限性线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题实际决策中，衡量方案优劣考虑多个目标生产计划决策，通常考虑产值、利润、满足市场需求等生产布局决策，考虑运费、投资、供应、市场、污染等

这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力目标规划（GoalProgramming）

多目标线性规划含有多个优化目标的线性规划90第一节多目标规划问题一、线性规划的局限性线性规划的局限性9第一节多目标规划问题二、多目标规划的提出例：甲乙产品的最优生产计划。产品资源甲乙现有资源设备A2016设备B0210设备C3432单位利润35解：线规划模型：

maxZ=3x1+5x2

2x1

≤162x2≤103x1+4x2≤32x1，x2≥0根据市场需求/合同规定：希望尽量扩大甲产品减少乙产品产量。又增加二个目标：

maxZ1=3x1+5x2

maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32

x1，x2≥0

这些目标之间相互矛盾，一般的线性规划方法不能求解91第一节多目标规划问题二、多目标规划的提出例：甲乙产品的最优第一节多目标规划问题三、多目标规划的解法加权系数法：为每一目标赋一权数，把多目标转化成单目标。但权系数难以科学确定。

优先等级法：各目标按重要性归不同优先级而化为单目标。

有效解法：寻求能照顾到各目标而使决策者感到满意的解。但可行域大时难以列出所有有效解的组合。

目标规划法：对每一个目标函数引入正的或负的偏差变量；引入目标的优先等级和加权系数。92第一节多目标规划问题三、多目标规划的解法加权系数法：92第二节目标规划的数学模型一、目标期望值每一个目标希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。二、偏差变量目标约束目标的实际值和期望值之间可能存在正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标的dk+和dk-中至少有一个必须为零。引入正负偏差变量，对各个目标建立目标约束(软约束)93第二节目标规划的数学模型一、目标期望值每一个目标希望达到的第二节目标规划的数学模型上例中要求：目标一是利润最大，拟定利润目标是30；目标二是减少乙产品产量但希望不低于4件；目标三是甲产品产量希望不少于6件；对各目标引入正、负偏差变量：3x1+5x2+d1--d1+=30x2

+d2--d2+=4x1+d3–-d3+=694第二节目标规划的数学模型上例中要求：94第二节目标规划的数学模型三、目标达成函数目标达成函数：偏差变量之和为最小值。若要求尽可能达到规定的目标值正负偏差变量dk+

,dk-都尽可能小，即minSk=dk++dk-若希望尽可能不低于期望值(允许超过)负偏差变量dk-尽可能小,不关心超出量dk+

：minSk=

dk-

若允许某个目标低于期望值，但希望不超过正偏差变量dk+尽可能小,不关心低于量dk-

：minSk=

dk+

四、优先等级权数目标重要度不同，用优先等级因子Pk

表示第k等级目标。优先等级因子Pk

是正的常数，Pk

>>Pk+1。同一优先等级下目标的相对重要性赋以不同权数w。95第二节目标规划的数学模型三、目标达成函数目标达成函数：偏差第二节目标规划的数学模型例如P1级目标实现利润至少30元；P2级目标是甲乙产品的产量假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2minG=P1d1-+P2(2d2-+d3+

)3x1+5x2+d1--d1+=30

x2

+d2--d2+=4

x1+d3--d3+=6x1,x2,dk-,dk+≥0(k=1,2,3)96第二节目标规划的数学模型例如96第三节目标规划的图解法目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。F2x1=162x2=10BCx14A103x1+4x2=326x20D2642EGHx1=5,x2=497第三节目标规划的图解法目标规划的图解法F2x1=162x第四节目标规划的应用案例一、无穷多满意解解：设x1,x2表示A、B产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小目标达成函数目标约束条件P2：利润额希望不能低于100元，负偏差最小目标达成函数目标约束条件计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。98第四节目标规划的应用案例一、无穷多满意解解：设x1,x2表2A24BDx26810x1第四节目标规划的应用案例一、无穷多满意解由于材料供应限量为8单位，所以有系统约束条件，如下该问题的目标规划模型如下，图解法求解如图CG992A24BDx26810x1第四节目标规划的应用案例一、无第四节目标规划的应用案例二、加班时间问题例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。

商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。100第四节目标规划的应用案例二、加班时间问题例：某音像店有5名第四节目标规划的应用案例二、加班时间问题首先，确定目标约束的优先级。如下：P1：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间x2；达不到销售目标的偏差d1-，超过销售目标的偏差d1+。

101第四节目标规划的应用案例二、加班时间问题首先，确定目标约束第四节目标规划的应用案例二、加班时间问题

（2）正常工作时间约束。设全体全职售货员下月的停工时间d2-，加班时间d2+

；全体兼职售货员下月的停工时间d3-，加班时间d3+。（3）加班时间的限制。设全体全职售货员下月的加班不足100小时的偏差d4-，加班超过100小时的偏差d4+。两类售货员区别对待，权重比d2+:d3+=1:3，另一加班目标约束为102第四节目标规划的应用案例二、加班时间问题（2）正常工作时第四节目标规划的应用案例二、加班时间问题

第三，按目标的优先级，写出相应的目标规划模型：运用LINGO软件求解得x1=900,x2=500，下月共销售CD盘27500张，获利27500×1.5-800×15-100×22.5-500×10=22000。103第四节目标规划的应用案例二、加班时间问题第三，按目标的优第四节目标规划的应用案例三、目标管理方案

例：某公司准备生产甲、乙产品，据市场调查：甲产品的最大市场需求3台，乙产品的最大市场需求2台。

在满足现有电力资源严格供给约束的前提下，该厂长考虑两个目标：一是总利润不低于3600元；二是充分利用设备台时，但尽量少加班。问应如何制定产品甲、乙的产量，试建立其目标规划的数学模型。104第四节目标规划的应用案例三、目标管理方案例：某公司准备生第四节目标规划的应用案例三、目标管理方案

1.利润期望优先目标规划数学模型：运用图解法进行求解FECx1=8x2=65x1+5x2=600x12410126ABx20842D10Gx1=8,x2

=3105