MBA讲义32课时管理运筹学(谢家平)-上海财大

管理理运运筹筹学学-管理理科科学学方方法法谢家家平平博博士士教教授授博士士生生导导师师研究究领领域域：：管理理科科学学、、运运营营管管理理、、供供应应链链管管理理讲授授课课程程：：管理理运运筹筹学学-管管理理科科学学方方法法、、管管理理系系统统工工程程、、运营营管管理理、、供供应应链链管管理理、、ERP、、国国际际物物流流、、企业业物物流流管管理理、、管管理理决决策策模模型型与与方方法法单位位：：上海海财财经经大大学学工工商商学学院院物物流流管管理理系系E-mail：：jiaping@1教材与参参考书籍籍教材：谢家平编编著.管管理运筹筹学：管管理科学学方法，，中国人民民大学出出版社，，2010参考书：：Davidetal.数数据、模模型与决决策，机机械工业业出版社社，2004费雷德里里克.数数据、、模型与与决策，，中国财财政经济济出版社社，2004Jamesetal.数数据据、模型型与决策策，中国国人民大大学出版版社，2006232课时时讲授提提纲绪论论第一章线线性性规划第二章线线性性规划讨讨论第三章对对偶偶规划静态规划划第四章整整数数规划第五章目目标标规划第六章动动态态规划动态优化化第七章网网络络分析第八章网网络络计划第九章决决策策分析第十章方方案案排序第十一章章库库存控制制第十二章章排排队理论论离散优化化随机优化化淡化数学学算法LINDO求解解3考核方式式结课考试试：笔试（开开卷or闭闭卷？））每章一题题80%案例研究究：选择合适适方法结结合企业业实际进进行应用用20%4管理运筹筹学的称称谓管理运筹筹学是一一门研究究如何最最优安排排的学科科。OperationsResearch日本译作作“运用用学”香港、台台湾译为为“作业业研究””我国译作作“运筹筹学”源于古语语“运筹筹帷幄之之中，决决胜千里里之外””取“运筹筹”二字字，体现现运心筹筹谋、策策略取胜胜ManagementScience管管理理科学运用数学学、统计计学和运运筹学中中的量化化分析原原理和方方法，建建立数学学模型/计算机机仿真，，给管理理决策提提供科学学依据。。5绪论一、发展展历史二、学科科作用三、学科科性质四、工作作程序五、学科科体系六、学习习要求6一、发展展历史1.早早期的运运筹思想想齐王赛马马•渭修皇宫宫沈括运军军粮•科学管理理2.军军事运筹筹学阶段段20世纪纪40年年代诞生生于英美美1940年，英英国为对对付德国国空军的的空袭，，使用了了雷达，，但没有有科学布布局，效效果不好好。为解解决这个个问题，，成立运运筹学小小组，称称OperationalResearch，意为作战研究究。美国和加加拿大也也在军队队设立运运筹学小小组，称称OperationsResearch，协助指指挥官研研究战略略及战术术问题。。3.管管理运筹筹学阶段段战后许多多从事运运筹学研研究的科科学家转转向了民民用问题题的研究究，使运运筹学在在企业管管理方面面的应用用得到了了长足进进展。7企业的成成功要素素中：观念意识识更新47％人文文化化35％技术优势势18％决策意识识的科学学性成功决策策正确决策策二、学科科作用理念的重重要性？8二、学科科作用1.量量化管理理的重要要性管理科学学是对与与定量因素素有关的管管理问题题通过应用科学学的方法法进行辅助管理理决策的一门学学科。目的：：用科科学方方法分分析管管理问问题，，为管管理者者决策策提供供依据据目标：：在企企业经经营内内外环环境的的限制制下，，实现现资源源效用用最大大组织中存在的问题定量分析定性分析评价与评估决策量化管管理是是第一一步,它导导致控控制,并最最终实实现改改进如果不不能量量化某某些事事情，，那么么就不不能理理解它它如果不不能理理解它它，那那么就就不能能控制制它如果不不能控控制它它，那那么就就不能能改进进它——H.JamesHarrington定性到到定量量分析析，数数量界界限的的重要要性：：量变变引起起质变变9听一场场音乐乐会：：网络订订票的的票价价500元元，不不去可可退票票情况1：在在你马马上要要出发发的时时候，，发现现你把把最近近的价价值500元的的电话话卡弄弄丢了了。你你是否否还会会去听听这场场音乐乐会？？情况2：假假设昨昨天花花500元元钱买买一张张今晚晚的音音乐会会取票票单。。在你你出发发时，，发现现把票票单丢丢了。。如果果去听听音乐乐会，，就必必须再再花500元钱钱买张张票，，去还还会不不去？？二、学学科作作用2.量量化化思考考使人人理性性冰淇淋淋实验验：一杯A有70克克，装在在50克克的杯子子里，，看上上去要要溢出出了一杯B是80克克，装在在100克的杯子子里，，看上上去还还没装装满单独凭凭经验验判断断时，，在相相同的的价格格上，，人们们普遍遍选择择A实验表表明，，大部部分的的回答答者仍仍旧会会去听听结果却却是，，大部部分人人回答答说不不去了了10二、学学科作作用3.量量化化分析析辅助助决策策盈亏平平衡分分析40,00080,000120,000160,00004080120160200Revenue=900xFixedcostLossProfitCost=50,000+400xxBreak-evenpoint=100units利润：：I=(P––Cm––Ch)Q-F策略1↑↑↑↔↔↔↔↔↔↔↔差异化化，领领先者者战略略策略2↑↔↔↔↔↔↔↑↑↔↔规模化化，大大规模模市场场策略3↑↔↔↓↓↔↔↔↔↔↔机械化化，第第一利利润源源策略4↑↔↔↔↔↓↓↔↔↔↔技能化化，第第二利利润源源策略5↑↔↔↕↕↕↕↔↔↓↓信息化化，第第三利利润源源11二、学学科作作用量化辅辅助决决策案案例：：盈亏亏平衡衡分析析例：某某企业业总销售售额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二、学科作作用甲产品产量量40,乙乙产品80,丙丙产品40利润=40×66+80×89+40×70=12560人员有限如如何实现?采取什么么薪酬制度度?计件工资制制，让员工工自愿加班班甲乙丙单位产品总成本107144100单位产品售价173233170单位产品利润668970市场每周需求408040决策的科学学性？方案一14二、学科作作用甲产品产量量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二、学科作作用决策的科学学性？产能能符合计算算甲乙丙总成本107144100售价173233170利润668970乙与丙哪一一个产品比比较赚钱?产品市场需求单位产品设备工时消耗EFGH甲400103131乙8030202113丙401502124需求产能3000200037603240可用产能2400240048004800E是瓶颈16二、学科作作用方案三：计时工工资，且以以单位利润润率高低为为决策意识识。乙比较赚钱钱,假如如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四、、工工作作程程序序管理者制定决策：管理运筹学的步骤：明确问题环境分析确定目标制定准则收集资料数量关系结构分析数学模型制定决策方案选择算法求解方案优选否是方案实施持续改进识别问题量化分析建立模型软件求解结果分析确定方案实施方案控制管理者解的分析19五、、学学科科体体系系1.管管理理问问题题需求预测产品的市场需求量有多大，需求类别如何，对企业盈利有何影响?生产计划在有限资源约束下，生产什么，生产多少，获利最大？资源配置需要哪些资源，如何进行最优配置，资源紧缺性如何，以什么代价获取?作业排序作业的重要次序如何，作业的顺序安排如何?市场营销广告预算、媒介选择、产品定价、销售计划等如何安排？运输问题最佳运输线路是哪条？物流配送集载如何优化？物流设施布局如何设置？设施选址运营点如何选择，需要哪些运作设施，设施如何布局?库存控制应保持多大库存量，何时应进行订货，订货批量多少为宜?项目规划项目完工工期多长为宜，哪些作业起关键性作用，资源如何分配?设备更新设备运转状况如何演进，运行可靠性如何，何时和如何更新或改造?人力资源人员需求预测，技能要求，编制与任务指派，绩效测评，留用多长时间?财务资金资金投放的数量，从何处进行融资，资金成本是多少?排队问题队列多长，有无容量限制，多少服务台为宜，能提供什么水平的服务?20五、、学学科科体体系系2.学学科科内内容容模型类型解决的典型办法线性规划在线性目标和约束条件间取得最优化结果整数规划在线性目标和约束条件间寻求整数决策最优目标规划在相对立的目标间寻得多目标妥协的满意解动态规划寻求多阶段动态系统的整体决策优化问题网络分析寻求网络路径、流量分布、网络瓶颈及其改进网络计划用各种作业和结点的网络排列来说明项目实施计划管理决策依据决策准则权衡比较备选方案的决策结果方案排序综合各方案的优势与不足寻求多指标排名次序库存模型寻求订货、存储和缺货等库存成本降至最低的经济批量统计方法从一个抽样得到普遍结果的推论和曲线拟合排队理论分析正在等待的队列特点及其运行指标仿真模拟动态观察复杂的管理问题的行为，模拟管理系统的结构关系21五、、学学科科体体系系3.学学科科应应用用管理理既既是是科科学学又又是是艺艺术术低层层管管理理的的科科学学成成分分较较多多，，高高层层管管理理的的艺艺术术成成分分较较多多运营营管管理理需需较较多多管管理理科科学学，，人人力力资资源源管管理理需需较较多多管管理理艺艺术术例行行管管理理需需要要较较多多管管理理科科学学，，例例外外管管理理需需要要较较多多管管理理艺艺术术M:管理理决决策策问问题题MC:定量量解解决决方方法法方案案选选择择依依据据问题题导导向向技术术支支持持战略略决决策策营销销决决策策生产产安安排排财务务分分析析人力力资资源源方案案优优选选………应用用统统计计线性性规规划划整数数规规划划目标标规规划划网络络计计划划网络络分分析析决策策分分析析动态态规规划划………管理理科科学学：运运用用合合理理的的分分析析来来改改善善决决策策的的制制定定管理理者者:制定定决决策策22六、学习要求求1.学科地地位数学技术科学管理学科基础管理运筹学管理专业课高等数学、概率统计、线性代数…加工技术、工程技术、信息技术…经济学原理、管理学、行为科学…离散、连续，静态、动态的方法…战略、运营、营销、财务、人力…23六、学习要求求经济学企业战略、公公司治理会计学财务管理人力资源管理理组织行为学学管理科学方法支持企业B行业企业C企业A商务2商务3商务1职能b职能c职能a小组ii小组iii小组i运营管理市场营销质量管理项目管理……信息管理流程管理物流管理供应链管理……24六、学习要求求2.如何学学习重点在结合实实际的应用发挥自己管理理实践经验丰丰富和理论联联系实际的能能力强化结合实际际问题建立管管理优化模型型的能力强化解决问题题的方案或模模型的解的分分析与应用能能力充分借用管理理运筹学教学学软件25第1章线性规规划Subtitle内容提要第一节线线性规划的一一般模型一、线性规划划的三个要素素二、线性规划划模型的特征征三、线性规划划的图解方法法四、线性规划划解的可能性性第二节线线性规划的单单纯形法一、线性规划划的标准型式式二、线性规划划之解的概念念三、单纯形法法的基本原理理26一、线性规划划的三个要素素第一节线性性规划的一般般模型决策变量决策问题待定定的量值取值要求非负负约束条件任何管理决策策问题都是限限定在一定的的条件下求解解把各种限制条条件表示为一一组等式或不不等式称约束束条件约束条件是决决策方案可行行的保障约束条件是决决策变量的线线性函数目标函数衡量决策优劣劣的准则，如如时间最省、、利润最大、、成本最低目标函数是决决策变量的线线性函数有的目标要实实现极大，有有的则要求极极小27二、线性规划划模型的举例例第一节线性性规划的一般般模型1、生产计划划问题例.某厂生产甲乙乙两种产品，，生产工艺路路线为：各自自的零部件分分别在设备A、B加工，，最后都需在在设备C上装装配。经测算算得到相关数数据如表所示示。应如何制制定生产计划划，使总利润润为最大。据市场分析，，单位甲乙产产品的销售价价格分别为73和75元元，试确定获获利最大的产产品生产计划划。产品设备工时消耗甲乙工时成本元/h生产能力hABC20023420151016103228第一节线性性规划的一般般模型(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二、线性规划划模型的举例例第一节线性性规划的一般般模型2、物资运输输问题例：某产品商有三三个供货源A1、A2、A3，其经销商有有4个（需求求市场）B1、B2、B3、B4。已知各厂的的产量、各经经销商的销售售量及从Ai到Bj的单位运费为为Cij。为发挥集团团优势，公司司要统一筹划划运销问题，，求运费最小小的调运方案案。销地产地B1B2B3B4产量A1632550A2758420A3329730销量2030104030第一节线性性规划的一般般模型(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二、线性规划划模型的举例例第一节线性性规划的一般般模型3、产品配比比问题例：用浓度45%和92%的的硫酸配置100吨浓度度80%的硫硫酸。决策变量：取45%和92%的硫酸酸分别为x1和x2吨约束条件：求解二元一次次方程组得解解非负约束：x1≥0，x2≥032第一节线性性规划的一般般模型若有5种不同同浓度的硫酸酸可选(30%,45%,73%,85%,92%)会如如何呢？取这5种硫酸酸分别为x1、x2、x3、x4、x5，有有多少种配比比方案？何为最好？若5种硫酸价价格分别为400,700,1400,1900,2500元/t，则则：33三、线线性规规划模模型的的特征征第一节节线线性规规划的的一般般模型型1、模模型隐隐含假假定（1））线性性化假假定函数关关系式式f(x)=c1x1+c2x2+…+cnxn，称线线性函函数。。建模技技巧：：将非非线性性的函函数进进行分分段线线性化化。（2））同比比例假假定决策变变量变变化引引起目目标函函数和和约束束方程程的改改变量量比例例。（3））可加加性假假定决策变变量对对目标标函数数和约约束方方程的的影响响是独独立于于其他他变量量的。。目标函函数值值是决决策变变量对对目标标函数数贡献献的总总和。。（4））连续续性假假定决策变变量取取值连连续。。（5））确定定性假假定所有参参数都都是确确定的的，不不包含含随机机因素素。34三、线线性规规划模模型的的特征征第一节节线线性规规划的的一般般模型型2、一一般数数学模模型用一组组非负负决策策变量量表示示的一一个决决策问问题；；存在一一组等等式或或不等等式的的线性性约束束条件件；有一个个希望望达到到的目目标，，可表表示成成决策策变量量的极极值线线性函函数。。35四、线线性规规划的的图解解方法法第一节节线线性规规划的的一般般模型型1、线线性规规划的的可行行域可行域域：满足所所有约约束条条件的的解的的集合合，即所有有约束束条件件共同同围城城的区区域。。maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD362x1=162x2=10x1x248103583x1+4x2

=320ABCD四、、线线性性规规划划的的图图解解方方法法第一一节节线线性性规规划划的的一一般般模模型型2、、线线性性规规划划的的最最优优解解目标标函函数数Z=3x1+5x2代表表以以Z为参参数数的的一一族族平平行行线线。。Z=30Z=37Z=1537四、、线线性性规规划划的的图图解解方方法法第一一节节线线性性规规划划的的一一般般模模型型3、、线线性性规规划划解解的的特特性性abcd由线线性性不不等等式式组组成成的的可可行行域域是是凸凸多多边边形形(凸凸多多边边形形是是凸凸集集)凸集集定定义义：：集集合合内内部部任任意意两两点点连连线线上上的的点点都都属属于于这这个个集集合合可行行域域有有有有限限个个顶顶点点。。目标标函函数数最最优优值值一一定定在在可可行行域域的的边边界界达达到到，，而而不不可可能能在在其其区区域域的的内内部部。。38五、、线线性性规规划划解解的的可可能能性性第一一节节线线性性规规划划的的一一般般模模型型1、、唯唯一一最最优优解解：：只只有有一一个个最最优优点点2、、多多重重最最优优解解：：无无穷穷多多个个最最优优解解当市市场场价价格格下下降降到到74元元，，其其数数学学模模型型变变为为2x1=162x2=103x1+4x2

=32x1x248102580ABCDZ=24Z=32Z=1239五、线性性规划解解的可能能性第一节线线性规规划的一一般模型型3、无界界解：可可行域无无界，目目标值无无限增大大(缺乏必必要约束束)40五、线性性规划解解的可能能性第一节线线性规规划的一一般模型型4、没有有可行解解：线性性规划问问题的可可行域是是空集(约束条条件相互互矛盾)目标冲突利害冲突目标强冲突利害弱冲突41一、线性性规划的的标准型型式第二节线线性规规划的一一般模型型1、标准准型表达达方式(1)代代数式(2)向向量式(3)矩矩阵式A：技术术系数矩矩阵，简简称系数数矩阵；；B：可用用的资源源量，称称资源向向量；C：决策策变量对对目标的的贡献，，称价值值向量；；X：决策策向量。。42一、线性性规划的的标准型型式第二节线线性规规划的一一般模型型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二、线性性规划之之解的概概念第二节线线性规规划的一一般模型型基矩阵：：一个非奇奇异的子子矩阵（（线性无无关）。。矩阵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二、线性性规划之之解的概概念第二节线线性规规划的一一般模型型2、线性性规划基基本原理理定理1.若线性规规划问题题存在可可行域，，则其可可行域一一定是凸凸集。定理2.线性规划划问题的的基可行行解对应应可行域域的顶点点。定理3.若可行域域有界，，线性规规划的目目标函数数一定可可以在可可行域的的顶点上上达到最最优。定理4.线性规划划如果有有可行解解，则一一定有基基可行解解；如果果有最优优解，则则一定有有基可行行解是最最优解。。46二、线性性规划之之解的概概念第二节线线性规规划的一一般模型型3、线性性规划解解题思路路先找到一一个初始始基可行行解，也也就是找找到一个个初始可可行基，，想办法法判断这这个基可可行解是是不是最最优解。。如果是最最优解，，就得到到这个线线性规划划问题的的最优解解；如果判断出不不是最优解，，就想法由这这个可行基按按一定规则变变化到下一个个可行基，然然后再判断新新得到的基可可行解是不是是最优解；如果还不是，，再接着进行行下一个可行行基变化，直直到得到最优优解。47三、单纯形法法的基本原理理第二节线性性规划的一般般模型maxZ=3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32Cj比值CBXBb检验数jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=848三、单纯形法法的基本原理理第二节线性性规划的一般般模型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三、单纯形法法的基本原理理第二节线性性规划的一般般模型单纯形的管理理启示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计件工资体系系，目标是企企业利润最大大化：第一节目标标函数的描述述技巧一、计件工资资产品甲：产品乙：产品丙：非负性约束计件工资制薪薪酬体系下，，工作时间不不会完全受每每天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第二节线线性规规划的适适用层次次计划链的的层次粗能力计划定单可行不可行CRP主生产计划MPS物料需求计划MRP能力需求计划车间作业计划销售计划可行否作业统计与控制物料清单库存管理外购计划供应商成品、在制品信息生产计划大纲预测当前条件经营计划产值计划划或利润计划划绝对数量量或增长幅度度期限:年年度单单位位:万元元大类产品品销售收收入或台套产品品种种和数量如何确定定期限:年年度单单位位:万台台具体产品品在具体体时段的出出产计划划合同订单单和预测测转换为生生产任务务将产品出出产计划划转换成成物料需需求表大类产品品年度生生产计划划确定产品品的品种种和数量期限:年年度单单位:万台55第三节线线性规规划的典典型案例例配送中心心选择例：某企业存存在两个个供货源源（产地地），已已知原有有供货源源每月的的供货能能力是5万台产产品，新新增供货货源的生生产能力力可以满满足产品品的需求求，且两两个货源源的价格格相同。。有三个个区域域目标标市场场（销销地或或销售售商）），各各销地地每月月的市市场需需求量量为5万台台、10万万台、、5万万台。。在分销销渠道道中，，拟定定在2个地地点中中选址址设立立分销销中心心，执执行产产品的的转运运任务务。各各地之之间的的单位位运输输物流流成本本（由由距离离和运运输方方式决决定））56第三节节线线性规规划的的典型型案例例决策变变量：：设从从供货货源到到分销销中心心的运运输量量为，，从从分销销中心心到需需求市市场的的运输输量为为。。选址址规划划在于于二者者的实实际取取值。。如果，，则则不设设置分分销中中心；；反之，，则设设置,其规规模为为如果，，则则不设设置分分销中中心；；反之，，则设设置，，其规规模为为目标函函数：：各条条路段段上的的实际际运输输量乘乘以物物流运运输的的单位位费用用之总总和最最小，，即存在供供应能能力约约束、、市场场需求求约束束、配配送中中转约约束，，如下下：57第三节节线线性规规划的的典型型案例例供应能能力平平衡约约束：：市场需需求平平衡约约束配送中中心不不存留留产品品所有变变量大大于等等于零零58第四节节线线性规规划灵灵敏度度分析析一、灵灵敏度度分析析的必必要性性线性规规划研研究的的是一一定条条件下下的最最优化化问题题资源环环境和和技术术条件件是可可变的的基础数数据往往往是是测算算估计计的数数值灵敏度度分析析的概概念灵敏度度分析析又称称敏感感性分分析或或优化化后分分析研究基基础数数据发发生波波动后后对最最优解解的影影响最优解解对数数据变变化的的敏感感程度度在多大大的范范围内内波动动才不不影响响最优优基灵敏度度分析析解决决的问问题：：参数在在什么么范围围变化化而最最优基基不变变已知参参数的的变化化范围围，考考察最最优解解(最最优基基)是是否改改变59第四节节线线性规规划灵灵敏度度分析析一、价价值系系数的的变动动分析析非基变变量Cj的变化化范围围非基变变量Cj变化，，只影影响它它自己己的检检验数数Cj35000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/203x14100-2/31/3检验数j000-1/2-1参数Cj的变化化范围围：价值系系数Cj变化影影响检检验数数60第四节节线线性规规划灵灵敏度度分析析一、价价值系系数的的变动动分析析基变量量CBl的变化化范围围CjC15000比值CBXBbx1x2x3x4x50x380014/3-2/35x250101/20C1x14100-2/31/3检验数j0002C1/3-5/2-C1/361第四节节线线性规规划灵灵敏度度分析析二、右右端常常量的的变动动分析析参数bi的变化化范围围第r个个约束束的右右端项项为br，增量量br，其它它数据据不变变。新新的基基解为为只要X'B≥0，则可可保持持最优优基不不变。。62第3章对对偶偶规划划Subtitle内容提提要第一节节对对偶偶规划划的数数学模模型对偶问问题的的提出出对偶规规划的的性质质第二节节对对偶偶规划划的经经济解解释影子价价值的的内涵涵影子价价值的的应用用第三节节资资源源定价价的决决策案案例63第一节节对对偶规规划的一、对偶问问题的提出出若例1中该该厂的产品品平销，现现有另一企企业想租赁赁其设备。。厂方为了了在谈判时时心中有数数，需掌握握设备台时时费用的最最低价码，，以便衡量量对方出价价，对出租租与否做出出抉择。在这个问题题上厂长面面临着两种种选择：自自行生产或或出租设备备。首先要要弄清两个个问题：①合理安排排生产能取取得多大利利润?②为保持利利润水平不不降低，资资源转让的的最低价格格是多少？？问题①的的最优解：：x1=4，x2=5，Z*=37。64第一节对对偶规划的的数学模型型一、对偶问问题的提出出出让定价假设出让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、对称性性定理对偶问题的的对偶问题题是原问题题。根据对偶规规划，很容容易写出对对偶问题的的对偶问题题模型。2、最优优性定理设，，分分别别为原问问题和对对偶问题题的可行行解，且且则，，分分别为为各自的的最优解解。3.对对偶性定定理若原问题题有最优优解，那那么对偶偶问题也也有最优优解，而而且两者的目目标函数数值相等等。4.互互补松弛弛性最优解的的充分必必要条件件是，，67第二节对对偶规规划的经经济解释释一、影子子价值的的内涵左边是资资源bi每增加一一个单位位对目标标函数Z的贡献献；对偶变量量yi在经济上上表示原原问题第第i种资源的的边际价值值。对偶变量量的值yi*表示第i种资源的的边际价价值，称称为影子价值值。若原问题题价值系系数Cj表示单位位产值，，则yi称为影子价格格。若原问题题价值系系数Cj表示单位位利润，，则yi称为影子利润润。影子价格格=资源源成本+影子利利润68第二节对对偶规规划的经经济解释释一、影子子价值的的内涵影子价格格不是资资源的实实际价格格，反映映了资源源配置结结构，其它数据据固定，，某资源源增加一一单位导导致目标标函数的的增量。。对资源i总存量的的评估：：购进or出让对资源i当前分配配量的评评估：增加or减少第一，影影子利润润说明增增加哪种种资源对对经济效效益最有有利第二，影影子价格格告知以以怎样的的代价去去取得紧紧缺资源源第三，影影子价格格是机会会成本，，提示资资源出租租/转让让的基价价第四，利利用影子子价格分分析新品品的资源源效果：：定价决决策第五，利利用影子子价格分分析现有有产品价价格变动动的资源源紧性第六，可可以帮助助分析工工艺改变变后对资资源节约约的收益益第七，可可以预知知哪些资资源是稀稀缺资源源而哪些些资源不不稀缺69第三节资资源定定价的决决策方案案例：某厂生产产甲乙产产品，（1）如如何安排排每周的的利润为为最大?（2）如果果企业可以以不生产，，那资源出出让如何定定价？甲乙资源成本资源拥有量原材料(kg)设备(工时)电力(度)943451020501360200300销售价格(元)390352一、最优生生产决策70第三节资资源定价的的决策方案案二、资源获获利决策如果决策者者考虑自己己不生产甲甲乙两种产产品，而把把原拟用于于生产这两两种产品的的原材料、、设备工时时、电量资资源全部出出售给外单单位，或者者做代加工工，则应如如何确定这这三种资源源的价格。。设原材料的的单位出让让获利为y1，设备工时时的单位出出让获利为为y3，电量的单单位出让获获利为y2。出让决策的的线性规划划模型：71第4章整数数规划Subtitle内容提要第一节整整数规划划问题纯整数规划划0-1规划划混合整数规规划第二节整整数规划划求解分枝定界法法第三节整整数规划划应用72第一节整整数规划问问题线性规划的的决策变量量取值可以以是任意非非负实数，，但许多实实际问题中中，只有当当决策变量量的取值为为整数时才才有意义例如，产品品的件数、、机器的台台数、装货货的车数、、完成工作作的人数等等，分数或或小数解显显然是不合合理的。要求全部或或部分决策策变量的取取值为整数数的线性规规划问题，，称为整数数规划(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第一节整整数规划问问题二、0-1规划登山队员可可携带最大大重量为25公斤。。问都带哪哪些物品的的重要性最最大。解：对于每每一种物品品无非有两两种状态，，带或者不不带，不妨妨设序号1234567物品食品氧气冰镐绳索帐篷相机设备重量55261224重要性系数2015181484100-1规划划的模型：：75第一节整整数规划问问题三、混合整整数规划例：某产品有n个区域市市场，各区区域市场的的需求量为为bj吨/月；现现拟在m个个地点中选选址建生产产厂，一个个地方最多多只能建一一家工厂；；若选i地建厂，生生产能力为为ai吨/月，其其运营固定定费用为F元/月；；已知址i至j区域域市场的运运价为cij元/吨。如如何选址和和安排调运运，可使总总费用最小小？解：选址建厂与与否是个0-1型决决策变量，，假设yi=1，选择择第i址建厂，yi=0，不选选择第i址建厂；计划从i址至区域市市场j的运输运量xij为实数型决决策变量。。76第二节整整数规划求求解一、舍入化化整法为了满足整整数解的要要求，自然然想到“舍舍入”或““截尾”处处理，以得得到与最优优解相近的的整数解。。这样做除少少数情况外外，一般不不可行，因因为化整后后的解有可可能超出了了可行域，，成为非可可行解；或或者虽是可可行解，却却不是最优优解。不考虑整数数约束则是是一个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第三节整数数规划应用一、生产基地地规划例：某公司拟建设设A、B两种种类型的生产产基地若干个个，两种类型型的生产基地地每个占地面面积，所需经经费，建成后后生产能力及及现有资源情情况如下表所所示。问A、、B类型基地地各建设多少少个，可使总总生产能力最最大？解：设A、B两类基地各各建设x1,x2个，则其模型型为：81第三节整数数规划应用二、人员安排排规划某服务部门各各时段(每2小时为一时时段)需要的的服务人数如如表：解：设第j时段开始时上上班的服务员员人数为xj第j时段来上班的的服务员将在在第j+3时时段结束时时下班，故决决策变量有x1,x2,x3,x4,x5。按规定，服务务员连续工作作8小时(4个时段)为为一班。请安安排服务员的的工作时间，，使服务员总总数最少.82第三节整数数规划应用三、项目投资资选择有600万元元投资5个项项目，收益如如表，求利润润最大的方案案？83第三节整数数规划应用四、互斥约束束问题例如关于煤资资源的限制，，其约束条件件为：企业也可以考考虑采用天然然气进行加热热处理：这两个条件是是互相排斥的的。引入0——1变量y，，令互斥问题可由由下述的条件件来代替，其其中M是充分分大的数。84第三节整数数规划应用五、租赁生产产问题服装公司租用用生产线拟生生产T恤、衬衬衫和裤子。。每年可用劳动动力8200h，布料8800m2。T恤衬衫裤子劳动力326布料售价250400600可变成本100180300生产线租金(万)201510假设：yj=1，要租用用生产线jyi=0，不租用用生产线j第j种服装生产量量xj85第三节整数数规划应用六、任务指派派问题甲乙丙丁四个个人，ABCD四项任务务，如何指派派总时间最短短？解：引入0-1变量xij，xij=1：任务j指派人员i去完成xij=0：任务j不派人员i去完成一项任务只由由一个人完成成一人只能完成成一项任务86第三节整数数规划应用七、设施选址址问题拟定在2个地地点中选址设设立分销中心心，执行产品品的仓储和转转运，一个分分销中心拟定定设立一个仓仓库W1、W2。若设立立仓库库W1，建设设成本本为10万万元，，最大大库容容为20万万台，，单位位产品品的月月库存存成本本为2元；；若设立立仓库库W2建造成成本为为20万元元，最最大库库容为为25万台台，单单位产产品的的月库库存成成本为为3元元。如何选选址和和安排排调运运，建建造费费用+运输输费用用+仓仓储费费用为为最小小？解：设设从供供货源源Si到分销销中心心Wj的运输输量为为xij，从分分销中中心到到需需求市市场Rk的运输输量为为yjk。仓库库选址址决策策引入入0-1变变量wj：87第三节节整整数规规划应应用七、设设施选选址问问题供应能能力平平衡约约束：：市场需需求平平衡约约束：：仓储能能力限限制约约束：：分销中中心不不存留留产品品：所有变变量大大于等等于零零：88第5章目目标标规划划Subtitle内容提提要第一节节多多目目标规规划问问题第二节节目目标标规划划数学学模型型目标的