OR01_线性规划与单纯形方法

1第一章线性规划与单纯形方法清华大学经济管理学院运筹学OperationsResearch2解决管理瓶颈的约束理论3Goldratt和他的畅销小说4生产管理软件与畅销小说以色列物理学家Goldratt开发的OPT生产管理软件取得很好的应用效果，由于OPT非常复杂，很多企业关注软件应用细节而忽略了蕴涵其中的基本管理思想，因此失败案例很多。为普及该软件，将OPT原理写成小说“TheGoal”，在全世界销售了400万册，被英国《经济学人》杂志誉为最成功的企业管理小说。从1984至1998年写了4本企业管理小说：目标（TheGoal:AProcessofOngoingImprovement）绝不靠运气（It’sNotLuck）关键链（CriticalChain）仍然不足够（NecessaryButNotSufficient）5“目标”故事梗概故事从一个工厂的危机开始，由于生产效率低、成本高，无法按时交货，工厂面临被关闭的危机，除非他们在3个月内创造奇迹，扭转被动局面；工厂经理罗哥在无路可走的情况下，有病乱投医，请教他母校的一个物理学教授。在教授断断续续，但很关键的指导下，逐渐找到问题所在，通过对瓶颈环节的改进，迅速提高生产效率，不仅在3个月内扭转亏损局面，还成为该行业最具竞争力的工厂。最后被提升为管理三个业务完全不同企业的事业部主管。6“目标”部分章节标题晴天霹雳；机器人真的提高了生产力吗？目标是什么？工厂到底赚不赚钱？有效产出、存货和运营费用；荒野探险的启示；寻找生产瓶颈；小小胜利；改革，再改革；问题蔓延了吗？忙碌不代表有效率；方法其实很简单；缩短生产周期；成本会计的矛盾；“常识管理”新官上任的难题；混乱中建立秩序；成本世界与有效产出世界；打破惯性；7约束理论的核心思想Goldratt1990年发表的“TheoryofConstraints”代表着“约束理论”的正式诞生；传统的管理思想认为，只要不断地在各个环节、各个部门致力于改进，就可以带来整个系统的改进。但TOC却指出：一个系统的产出速度和产出量取决于系统各个环节中的瓶颈环节，管理的目标应该放在寻找并消除瓶颈环节上；以简单常识处理复杂问题8TOC五步法1.约束识别与评价；2.根据某种准则确定最紧的瓶颈约束；3.按瓶颈约束的边际贡献进行决策选择；4.对选择结果进行评价；5.上面步骤中如果任何一个约束被打破，回到第1步；TOC理论试图不停顿地对约束进行识别、评价与改进来改善系统效率。9材料1材料2材料3材料4设备A设备B设备A$10$1510分钟设备C$15设备D设备E5分钟15分钟15分钟设备A材料2$1510分钟10分钟5分钟设备E5分钟设备C5分钟设备D10分钟设备E10分钟$10产品X产品Y产品Z$90$100$7050/周75/周100/周ABCDE材料成本X2001515540Y10105251030Z510510525TOC计算举例需求端供应端生产过程10能力限制如果满足全部市场需求，需要以下加工能力：D的需求大于实际能力，D为瓶颈约束；XYZ合计实际能力负荷率A1000750500225024000.94B07501000175024000.73C750375500162524000.68D75018751000362524001.51E250750500150024000.63瓶颈11其他经济参数*$4000固定成本按加工时间分摊到每种产品上**会计利润＝毛利－分摊的固定成本财务指标XYZ 销售价格9010070材料成本403025加工费222414毛利润284631分摊固定成本20.522.313.0会计利润7.523.718.0市场需求5075100132123直接成本***121.按毛利（利润）顺序排产产品XYZ 合计增减销售价格901007011175100%材料成本4030253562.5加工费2224142535毛利润2846315077.5100%分摊固定成本34.737.922.14000会计利润-6.78.18.91077.5100%占用D能力1525102400市场需求5075100产量决策07552.5212133132.按约束理论排产产品XYZ 合计相对增减销售价格90100701410026.17%材料成本4030255280加工费2224143124毛利润284631569612.18%分摊固定成本28.230.717.94000会计利润-0.215.313.1169657.40%占用D能力1525102400毛利/D能力1.871.843.102.56市场需求5075100产量决策5026100123123约束理论排产找到了最优产量决策，销售额上升26.17%，毛利上升12.18%，净利润上升57.4%，14约束理论存在的问题每次只能考虑一个瓶颈约束，无法很好解决存在多瓶颈的复杂问题；负荷率的计算要求有标定的产量（如市场需求），对市场需求没有限制的问题，如何计算负荷率；无法从理论上证明得到的解是最优解；没有好的求解工具软件；15第一章线性规划与单纯形方法线性规划－研究资源最优配置的最有效方法；也是管理科学方法中应用最为普遍的方法之一，运筹学的很多方法都以线性规划为基础。16本章主要内容§1线性规划模型与图解法§2求解线性规划的单纯形方法§3求解线性规划的软件工具17优化问题什么是优化问题？通过资源的合理匹配与调度，在不增加资源投入的前提下，显著提高资源利用效率，达到增加收入或利润的目的。在企业经营活动中存在什么样的优化问题？制造型企业服务型企业18基于边际分析的优化方法资源优化配置分析常用的方法有：线性规划、整数规划、非线性规划、网络规划等；基于边际分析的决策方法；最优性（均衡）条件：资源利用的边际收益相等；分配资源A单位B单位C单位数量边际收益数量边际收益数量边际收益QBQAQC边际收益相等max:f(Q)s.t.QA+QB+QCQ19§1线性规划模型与图解法家具厂生产计划问题营养配餐问题更一般的资源配置模型线性规划的一般形式线性规划图解法20例1产品组合问题家具厂生产桌子、椅子两种产品，市场售价格分别为100元/件和65元/件。生产一个桌子需要用木工4小时，油漆工2小时；生产一个椅子需要用木工3小时，油漆工1小时；使用木工、油漆工的成本分别为10元/小时和5元/小时。计算可知桌子、椅子的生产成本分别为50、35元/件，销售利润分别为50、30元/件。该厂每周可使用的木工和油漆工工时分别为120和50小时，问：如何生产才能使销售利润最大？典型的产品组合问题（ProductionMix）21生产利润高的产品：最多能生产25个桌子，销售利润1250元；油漆工工时用完，但木工资源剩余20小时。组合生产方案1：调整生产桌、椅的数量生产20个桌子，10个椅子，销售利润1300元；油漆工工时用完，木工资源仍剩余10小时。组合生产方案2：继续调整生产桌、椅的数量生产15个桌子，20个椅子，销售利润1350元；全部工时用完－资源得到有效利用－最优解；优化：选择好的生产方案22如果问题变得更复杂简单的生产问题手工计算有时可以找到好的或最优方案；复杂的生产问题复杂度提高一个数量级：20种产品，20种资源；用传统的手工计算是否可行？问题可能存在无数个可行解，从中找出最优解不是件容易的事。线性规划模型是求解这类问题的最有效工具。23家具厂的数学模型决策变量：桌椅产量x1=生产桌子的数量，x2=生产椅子的数量；目标函数：生产利润最大化maxz=50x1+30x2约束方程：条件限制s.t.木工工时限制：4x1+3x2120油漆工工时限制：2x1+x250非负约束：x10，x2024假定一个成年人每天需要从食物中获取3000大卡热量、55克蛋白质和800毫克钙，市场上有四种食品可供选择。每公斤所含热量和营养及价格见下表，问：如何选择才能在满足营养前提下使费用最小。例2营养配餐问题（DietProblem）序号食品热量蛋白质钙价格名称(大卡)(g)(mg)(元)1猪肉100050400142鸡蛋8006020063大米9002030034白菜20010500225营养配餐模型变量：xj购入j种食品数量。目标函数：采购成本最小min:z=14x1+6x2+3x3+2x4约束方程：s.t.满足热量:1000x1+800x2+900x3+200x43000满足蛋白质：50x1+60x2+20x3+10x455满足钙：400x1+200x2+300x3+500x4800非负约束：x1，x2，x3，x4026例3更一般的资源优化配置模型某经济组织利用m种资源从事n种经营活动（如采购、制造、销售等）；从事第j（j=1,…,n）种经营活动需要使用数量为aij的第i（i=1,…,m）种资源，并可为组织带来cj的收益，组织可使用资源的限制为bi，问：该组织如何经营，并使其收益最大化；求解n种经营活动竞争使用m种资源的资源优化配置问题，设模型的变量xj为第j种经营活动的活动规模；27模型可以写为：max:z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxnb1······am1x1+am2x2+…+amnxnbmx1,x2,…,xn0表现为线性规划模型的一般形式；资源优化配置模型矩阵表示:maxcxs.t.Axbx028决策变量：x1,...,xn为决策变量，表示第n种经济活动的活动规模；目标函数：z=c1x1++cnxn反映经营活动目标。cj为目标函数系数（或价值系数），表示与经营活动相关的收益（cj0为费用）；约束：ai1x1+…+ainxnbi使用第i种资源的限制；约束系数：aij也称技术系数或投入产出系数，代表第j种经营活动需要第i种资源的数量；右边项：b=(b1,...,bm)代表m种资源的可用数量非负约束：xj0决策变量的取值范围的限制。线性规划模型的一般形式29线性规划隐含的假定线性规划要求目标函数和约束方程必须是线性函数隐含了如下假定：比例性假定：决策变量的变化与资源消耗成比例，可加性假定：每个决策变量的影响独立于其他变量连续性假定：决策变量可取连续值；确定性假定：线性规划所有参数都是确定性参数，不含随机因素。30线性规划模型小结线性规划是求一个线性函数在满足一组线性等式或不等式方程条件下极值的一类数学问题的统称。线性规划模型由三部分组成：反映决策目标的目标函数，求其最大或最小值；一组线性等式、不等式约束方程；限制决策变量取值范围的非负约束。构造线性规划模型需注意：不是所有变量都需要出现在每一个约束中；注意每个约束内参数量纲（单位）的一致性；31§2线性规划的图解法图解法简单、直观，便于初学者了解线性规划基本原理和几何意义；例1.用图解法求解家具厂生产计划问题max:z=50x1+30x2s.t.4x1+3x21202x1+x250x10，x2032x2x14050302x1+x25020101020304x1+3x2120z=50x1+30x2=600z=50x1+30x2=900z=50x1+30x2=1350(15,20)图解法求解线性规划问题33图解法求解步骤1.画直角坐标系；2.依次做每条约束线，找出可行域；若不存在可行域,该问题无解；3.做目标函数线，根据目标类型平移，直到该线即将离开可行域时与该线接触的最后一点即为一最优解；4.若该线可无限制地在可行域内移动,则该问题无界。5.确定解的数值。34例5：用图解法求解max:z=x1+x2s.t.x1+2x24x1–2x25x1,x20无可行解的线性规划问题14235123x1x2x1+2x24x1-2x2535有无界解的线性规划问题max：x+1/3ys.t.x+y20-2x+5y150x5x0,y0