1、主讲教师 谭园园联系电话： 15857147552（ 677552）E-mail: 清华大学出版社运筹学教程（第 四 版）运筹学教程运筹学教程胡运权 主编教材上堂课回顾【运筹学】运用数学方法研究经济、民政和国防等部门在内外环境的约束条件下合理分配人力、物力、财力等资源，使实际系统有效运行的技术科学，它可以用来预测发展趋势，制定行动规划或优选方案。【解决问题的过程】1）提出问题，认清问题 分析和表述问题2）问题的抽象 建模3）确定问题的各种方案及确定方案的标准或方法、途径 求解和优化4）评估各个方案，选择最优方案 测量模型及对模型进行必要的修正5）对解进行检验、灵敏性分析等 建立对解的有效控制
2、6）回到实践中 方案实施上堂课回顾【运筹学的分支】| 非线性规划| 动态规划| 图论与网络分析| 存贮论| 排队论| 对策论| 决策论| 规划论多目标规划随机规划 模糊规划等P | 线性规划上堂课回顾1）数学模型的要素规划问题的数学模型的要素包括：（ 1）变量，或决策变量，是问题中待确定的未知量；（ 2）目标函数 它是决策变量的函数。按优化目标有最大化与最小化， 即 max或 min（ 3） 约束条件，指约束变量取值时受到的各种资源条件的限制。2）线性规划的特征（含义）线性规划问题的 特征（含义） ：（ 1）目标函数是决策变量的线性函数（ 2）约束条件是含决策变量的线性等式或不等式实际问题中线
3、性的含义：（ 1）严格的比例性（正、反比）；（ 2）可叠加性上堂课回顾max（ min） z = c1x1 + c2x2 + + cnxn x1， x2 ， ， xn 0st .a11x1 + a12x2 + + a1nxn (或 =,) b1a21x1 + a22x2 + + a2nxn (或 =,) b2am1x1 + am2x2 + + amnxn (或 =,) bn 目标函数约束条件决策变量 xj量称为该问题的决策变量。资源拥有量价值系数在目标函数中 xj的系数 cj称为该决策变量的价值系数。技术系数或工艺系数aij量称为该问题的技术系数或工艺系数。有所有aij组成的矩阵称为约束方程的
4、 系数矩阵 。在问题中， xj的取值受 m项资源的约束， bi称为第 I项资源的拥有量。一、线性规划的数学模型的表示上堂课回顾xj 0 (j=1,2, ,n)st .max（ min） z = cjxjaijxj (或 =,) bi (i=1,2, ,m)max（ min） z =X 0st .CX C=（ c1 , c2 , , cn ）Pjxj (或 =,) b用向量表达Pj=（ a1j , a2j , , amj） -1b=（ b1 , b2 , , bm） -1简化表示X=（ x1 , x2 , , xn） -1其中X 0st .AX (或 =,) b用矩阵表达A= a11 a12 a
5、1n a21 a22 a2n am1 am2 amn 矩阵 A称为约束方程组（约束条件）的系数矩阵。max（ min） z = CX C=（ c1 , c2 , , cn ）上堂课回顾1）线性规划问题的标准格式max z =xj 0 (j=1,2, ,n)st .cjxjaijxj = bi (i=1,2, ,m)其中：1）目标为最大化； 2） bi 为非负数；3） xj 为非负数； 4）约束为等式。 目标为最大化约束为等式bi 为非负数xi 为非负数一个最有代表性的例子min z = x1 + 2x2 + 3x3约束条件-2x1 + x2 + x3 9-3x1 + x2 + 2x3 44x1
6、 - 2x2 - 3x3 = -6x1 0； x2 0 ； x3取值无约束st .步骤1）加入松弛变量和剩余变量把不等式 约束变为等式约束；约束条件-2x1 + x2 + x3 9-3x1 + x2 + 2x3 44x1 - 2x2 - 3x3 = -6x1 0；st . x2 0 ；x3取值无约束 x5 = 4-2x1 + x2 + x3 + x4 = 9x4， x5 0 ；上堂课回顾一个最有代表性的例子min z = x1 + 2x2 + 3x3约束条件-2x1 + x2 + x3 9-3x1 + x2 + 2x3 44x1 - 2x2 - 3x3 = -6x1 0； x2 0 ； x3取
7、值无约束st .1）加入松弛变量和剩余变量把不等式 约束变为等式约束；约束条件4x1 - 2x2 - 3x3 = -6x1 0；st . x2 0 ；x3取值无约束-3x1 + x2 + 2x3 x5 = 4-2x1 + x2 + x3 + x4 = 9 2）把 b0 加等式约束两边同乘以 -1把 b变成 0 约束；-4x1 + 2x2 + 3x3 6x4， x5 0 ；步骤上堂课回顾一个最有代表性的例子min z = x1 + 2x2 + 3x3约束条件-2x1 + x2 + x3 9-3x1 + x2 + 2x3 44x1 - 2x2 - 3x3 = -6x1 0； x2 0 ； x3取值无约束st .1）加入松弛变量和剩余变量把不等式 约束变为等式约束；约束条件 x1 0；st .x2 0 ；x3取值无约束-3x1 + x2 + 2x3 x5 = 4-2x1 + x2 + x3 + x4 = 9 2）把 b0 加等式约束两边同乘以 -1把 b变成 0 约束；-4x1 + 2x2 + 3x3 = 6 3）变量 xi0 ，令 xi/=- xi此时 xi/ 0 ；x1/ 0；4x1/ + 2x2 + 3x3 = 63x1/ + x2 + 2x3 x5 = 42x1/ + x2 + x3 + x4 = 9x4， x5 0 ；步骤上堂课回顾
