运筹学 一章 线性规划课件.pptVIP

运筹学;课堂要求;参考资料;前言—运筹学简介;运筹学是在第二次世界大战中诞生和发展起来的。由于战争的需要，英国和美国招募了一批年轻的科学家和工程师，在军队将军的领导下研究战争中的问题，例如大规模轰炸的效果，有哪些信誉好的足球投注网站和攻击敌军潜水艇的策略，兵力和军需物质的调运等等。这些研究在战争中取得了很好的效果。当时英国把这些研究成为“作战研究”，英文是Operational Research，在美国称为Operations Research。;战后这些研究成果逐渐公开发表，这些理论和方法被应用到经济计划，生产管理领域，也产生了很好的效果。这样，Operations Research就转义成为“作业研究”。我国把Operations Research译成“运筹学”，非常贴切地涵盖了这个词作战研究和作业研究两方面的涵义。 运筹学的内容十分广泛，包括线性规划、整数规划、动态规划、非线性规划、图论与网络优化、排队论、决策理论、库存理论等。在本课程中，结合管理学科的特点，主要介绍线性规划、对偶问题，整数规划、运输问题、动态规划、图与网络分析。;授课主要内容;第一章 线性规划及单纯形法;本章学习要求;1.1线性规划问题及其数学模型;一、线性规划问题举例说明;例1：美佳公司－生产计划问题;例2：捷运公司;1. 生产计划问题（Production Planning）;2. 配料问题（Material Blending）;3. 背包问题（Knapsack Problem）;4. 运输问题（Transportation）;运价 （元/吨）;运量（吨）;5. 指派问题（Assignment Problem）;张、王、李、赵四位老师被分配教语文、数学、物理化学四门课程，每位老师教一门课，每门课由一位老师教。根据这四位老师以往教课的情况，他们分别教四这门课程的平均成绩如下表。要求确定哪一位老师上哪一门课，使四门课的平均总成绩最高。;设：;6. 下料问题 现将1m长的钢切成A＝0.4m,B=0.3m，C=0.2m长的三种钢，其中A，B，C三种钢分别需要20根，45根和50根，问如何进行切割使得需要的1m钢为最少？;小结;课堂习题 P45 1.13 1.14(1) 课后作业 P46 1.14(2) 1.15;二、线性规划模型标准形式;2.线性规划的标准形式;3.线性规划模型用矩阵和向量表示;线性规划模型用矩阵和向量表示（续）;4.线性规划模型总结;5.线性规划问题的标准化; min z=2x1-3x2+x3 令 z’=-z，z’=-2x1+3x2-x3 新的目标函数 max z’=-2x1+3x2-x3 取得极小化的最优解时，这个最优解同时使原目标函数值取得最大化的最优解。但两个问题最优解的目标函数值相差一个负号。; 2x1+3x2-4x3≤5 引进松弛变量(Slack variable) x4≥0 2x1+3x2-4x3+x4=5 如果有一个以上小于等于约束，要引进不同的松弛变量。例如： 2x1+3x2-4x3≤5 3x1-2x2+5x3≤8 在两个约束中分别引进松弛变量x4，x5≥0 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 +x5=8;没有符号限制的变量，用两个非负变量之差表示。例如： min z=x1+2x2-3x3 s.t. 2x1+3x2-4x3≤5 3x1-2x2+5x3≥8 x1≥0, x2:free, x3≥0 先将目标函数转化为极小化，并在约束中引进松弛变量，把不等式约束变为等式。 Max z’=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3 -x5=8 x1≥0, x2:free, x3, x4, x5≥0; Max z’=-x1-2x2+3x3 s.t. 2x1+3x2-4x3+x4 =5 3x1-2x2+5x3-x5=8 x1≥0, x2:free, x3, x4, x5≥0 然后，令x2=x2’-x2”，其中x2’,x2”≥0。代入模型，消去x2 Max z’=-x1-2(x’2-x”2)+3x3 s.t. 2x1+3(x’2-x”2)-4x3+x4 =5 3x1-2(x’2-x”2)+5x3 -x5=8 x1, x’2, x”2, x3, x4,x5≥0 整理，得到标准形式： Max z’=-x1-2x’2+x”2+3x3 s.t. 2x1+3x’2-3x