1、Operations Research Joinus-Wei Web:http:/ School of Management page 1*第二讲第二讲7号楼 B座 215电话： 86689923(O)， 661199(M)E-mail: 人文与管理学院人文与管理学院魏晋才魏晋才Operations Research Joinus-Wei Web:http:/ School of Management page 2*第二讲第二章第二章 线性规划的图解法线性规划的图解法 1 问题的提出 2 图解法 3 图解法的灵敏度分析Operations Research Joinus-Wei Web:ht
2、tp:/ School of Management page 3*第二讲 线性规划的广泛应用是计算机时代的产物。 1902年， Julius Farkas 发表论文，阐述有关线性规划问题。 1938年，英国人康德进行较详细研究。 1947年，美国学者 George Dantzig（丹茨格）发明了求解线性规划的单纯形法（ 1951年发表），从而为线性规划的推广奠定了基础。有人认为，求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。Operations Research Joinus-Wei Web:http:/ School of Management page 4*第二讲第二章 线
3、性规划的图解法第二章 线性规划的图解法在管理中一些典型的线性规划应用 合理利用线材问题：如何在保证生产的条件下，下料最少 配料问题：在原料供应量的限制下如何获取最大利润 投资问题：从投资项目中选取方案，使投资回报最大 产品生产计划：合理利用人力、物力、财力等，使获利最大 劳动力安排：用最少的劳动力来满足工作的需要 运输问题：如何制定调运方案，使总运费最小线性规划的组成：目标函数 Max F 或 Min F约束条件 s.t. (subject to) 满足于决策变量 用符号来表示可控制的因素Operations Research Joinus-Wei Web:http:/ School of M
4、anagement page 5*第二讲例 1. 某工厂在计划期内要安排 、 两种产品的生产，已知生产单位产品所需的设备台时及 A、 B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位 、 产品才能使工厂获利最多？线性规划模型：目标函数： Max z = 50 x1 + 100 x2 约束条件： s.t. x1 + x2 3002 x1 + x2 400x2 250x1 , x2 0Operations Research Joinus-Wei Web:http:/ School of Management page 6*第二讲 建模过程1.理解要解决的问题，了解解题的目标和条
5、件；2.定义决策变量（ x1 ， x2 ， ， xn ），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 一般形式目标函数： Max （ Min） z = c1 x1 + c2 x2 + + cn xn 约束条件： s.t. a11 x1 + a12 x2 + + a1n xn （ =, ） b1a21 x1 + a22 x2 + + a2n xn （ =, ） b2 am1 x1 + am2 x2 + + amn xn （ =, ） bmx1 ， x2 ， ， xn 0 1 问题的提
6、出 问题的提出Operations Research Joinus-Wei Web:http:/ School of Management page 7*第二讲例 1.目标函数：Max z = 50 x1 + 100 x2 约束条件：s.t. x1 + x2 300 (A)2 x1 + x2 400 (B)x2 250 (C)x1 0 (D)x2 0 (E)得到最优解：x1 = 50， x2 = 250 最优目标值 z = 275002 图 解 法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例 1详细讲解其方法：Operations
7、 Research Joinus-Wei Web:http:/ School of Management page 8*第二讲2 图 图 解解 法法(1)分别取决策变量 X1 , X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例 1的每个约束条件都代表一个半平面。x2x1X20X2=0x2x1X10X1=0Operations Research Joinus-Wei Web:http:/ School of Management page 9*第二讲2 图 图 解解 法法（ 2）对每个不等式 (约束条件 )，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100 200 300x1+x2300x1+x2=300100100 2002x1+x24002x1+x2=400300200300400Operations Research Joinus-Wei Web:http:/ School of Management page 10*第二讲（ 3）把五个图合并成一个图，取各约束条件的公共部分，如图 2-1所示。100100x2250x2=250200 300200300x1x2x2=0 x1=0x2=250x1+x2=3002x1+x2=400图 2-1
