运筹学讲稿第次课12学时本次课题（或教材章节题目）：绪论、第一章线性规划与单纯形法$1.1线性规划的基本概念教学要求：掌握运筹学发展历史、主要分支及工作步骤：掌握线性规划一般形式特点及图解法。重点：运筹学的工作步骤、线性规划一般形式、图解法。难点：线性规划一般形式及特点、线性规划图解法。教学手段及教具：多媒体教学。讲授内容及时间分配：30分钟一、运筹学简史二、运筹学的主要分支10分钟10分钟三、运筹学的工作步骤第一章线性规划与单纯形法S1.1线性规划的基本概念$1.1.1线性规划的数学模型20分钟30分钟$1.1.2图解法P423、（1)、(3)课后作业《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社第1页
运筹学讲稿 第 1 页 第 1 次课 2 学时 本次课题（或教材章节题目）：绪论、第一章 线性规划与单纯形法 §1.1 线性规划的基本概念 教学要求： 掌握运筹学发展历史、主要分支及工作步骤；掌握线性规划一般形式特点及图解法。 重 点：运筹学的工作步骤、线性规划一般形式、图解法。 难 点：线性规划一般形式及特点、线性规划图解法。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 一、运筹学简史 30 分钟 二、运筹学的主要分支 10 分钟 三、运筹学的工作步骤 10 分钟 第一章 线性规划与单纯形法 §1.1 线性规划的基本概念 §1.1.1 线性规划的数学模型 20 分钟 §1.1.2 图解法 30 分钟 课后作业 P42 3、（1）、（3） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿绪论运筹学（operationsresearch）是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系统的数学模型并求解，为决策者制定最优决策提供科学依据。一、运筹学简史二、运筹学的主要分支1.线性规划（LinearProgramming）2.目标规划（GoalProgramming）3.整数规划（IntegerProgramming）4.非线性规划（NonlinearProgramming）5.动态规划（DynamicProgramming）6.图论与网络分析（GraphTheoryandNetworkAnalysis）7.排队论（QueuingTheory）8.存贮论（InventoryTheory）9.对策论（GameTheory）10.决策论（DecisionTheory）三、运筹学的工作步骤1.提出和形成问题2.收集资料，确定参数3.建立模型4.模型求解和检验5.解的控制第一章线性规划与单纯形法s1.1线性规划的基本概念$1.1.1线性规划的数学模型特点：（1）每个行动方案可用一组变量（x1，*，xn）的值表示，这些变量一般取非负值；（2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示；（3）有一个需要优化的目标，它也是变量的线性函数。具备以上三个特点的数学模型称为线性规划（LinearProgramming，简记为LP），一般形式为：max(min) z=c,x, +c,x +...+c.x.ax +ai2x2 +.+ainx,≤(=,≥)b,a21, +a22x2 +..+a2nx,≤(=,≥)b2amlX,+am2X2 +...+amx,≤(=,≥)bmXi,x2,"x,≥0采用求和符号，可以简写为：max(min)Z=Ecxj=l[24x, (2-),i=12,.,mj=l(x,≥0j =1,2,.,n第2页
运筹学讲稿 第 2 页 绪 论 运筹学（operations research）是用数学方法研究各类系统最优化问题的学科。运筹学通过建立系 统的数学模型并求解，为决策者制定最优决策提供科学依据。 一、运筹学简史 二、运筹学的主要分支 1. 线性规划（Linear Programming） 2. 目标规划（Goal Programming） 3. 整数规划（Integer Programming） 4. 非线性规划（Nonlinear Programming） 5. 动态规划（Dynamic Programming） 6. 图论与网络分析（Graph Theory and Network Analysis） 7. 排队论（Queuing Theory） 8. 存贮论（Inventory Theory） 9. 对策论（Game Theory） 10. 决策论（Decision Theory） 三、运筹学的工作步骤 1. 提出和形成问题 2. 收集资料，确定参数 3. 建立模型 4. 模型求解和检验 5. 解的控制 第一章 线性规划与单纯形法 §1.1 线性规划的基本概念 §1.1.1 线性规划的数学模型 特点： （1）每个行动方案可用一组变量（x1，.，xn）的值表示，这些变量一般取非负值； （2）变量的变化要受某些限制，这些限制条件用一些线性等式或不等式表示； （3）有一个需要优化的目标，它也是变量的线性函数。 具备以上三个特点的数学模型称为线性规划（Linear Programming，简记为 LP），一般形式为： ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + + + ≤ = ≥ + + + ≤ = ≥ + + + ≤ = ≥ = + + + , , 0 ( , ) ( , ) ( , ) max(min) 1 2 1 1 2 2 21 1 22 2 2 2 11 1 12 2 1 1 1 1 2 2 n m m mn n m n n n n n n x x x a x a x a x b a x a x a x b a x a x a x b z c x c x c x L L LLLL L L L 采用求和符号Σ，可以简写为： ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = ≤ ≥ = = = ∑ ∑ = = x j n a x b i m z c x j i n j ij j n j j j 0 1,2, , ( , ) 1,2, , max(min) 1 1 L L
运筹学讲稿$1.1.2图解法1.唯一最优例 4maxz=2x, +5x2X+2x,≤85x, +2x, ≤204xz≤12[x,x,≥0+X212S5x/+2x2204上X2=—2/5x/+z/5Q03134x2=12382Xi+2x2=811F00+234561Xi图 1-12.无穷多最优3.无界解（无最优解）第3页
运筹学讲稿 第 3 页 §1.1.2 图解法 1. 唯一最优 例 4 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≤ + ≤ + ≤ = + , 0 4 12 5 2 20 2 8 max 2 5 1 2 2 1 2 1 2 1 2 x x x x x x x z x x 图 1-1 2. 无穷多最优 3. 无界解（无最优解） 1 2 3 4 5 0 1 2 3 4 5 6 x2 x1 Q4 Q3 Q2 Q1 l1 l2 l3 x1+2x2=8 5x1+2x2=20 4x2=12 x2=－2/5x1+z/5
运筹学讲稿第2次课2学时0上次课复习：线性规划一般形式及特点：线性规划图解法。本次课题（或教材章节题目）：1.2线性规划的标准形式和解的性质0教学要求：掌握线性规划的标准形式、基可行解的概念及LP解的性质重点：线性规划的标准形式、特点、基可行解的概念及LP解的性质难点：线性规划的标准形式、基可行解的概念。教学手段及教具：多媒体教学。讲授内容及时间分配：上次课复习5分钟30分钟S1.2.1LP的标准形式$1.2.2LP的基可行解的概念50分钟015分钟$1.2.3LP解的性质P424、(1)、(2)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第4页
运筹学讲稿 第 4 页 第 2 次课 2 学时 注：本页为每次课教案首页 上次课复习： 线性规划一般形式及特点； 线性规划图解法。 本次课题（或教材章节题目）：§1.2 线性规划的标准形式和解的性质 教学要求： 掌握线性规划的标准形式、基可行解的概念及 LP 解的性质 重 点：线性规划的标准形式、特点、基可行解的概念及 LP 解的性质 难 点：线性规划的标准形式、基可行解的概念。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习 5 分钟 §1.2.1 LP 的标准形式 30 分钟 §1.2.2 LP 的基可行解的概念 50 分钟 §1.2.3 LP 解的性质 15 分钟 课后作业 P42 4、（1）、（2） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿$1.2线性规划的标准形式和解的性质S1.2.1LP的标准形式N(1.4)maxZ3Zcxjj=l[Zayx, =b,i=1,2,.,m(1.5)j=l[x, ≥0j=1,2,,n(1.6)变换一般LP为标准形式的方法：n（1）如果原问题目标函数求极小值：minz=c,x=令z=一z，转化为求maxE(-c,)x,Z=j=1（2）若某个右端常数b<0，则以一1乘该约束两端。（3）若某约束为“≤”型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不等式化为等式；若某约束为“≥”型，则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛变量，使不等式转化为等式。（4）若某个x的符号约束为x≤0；那么令x，=一x，则x，≥0；若某个x无符号限制，则可令x=x-x，其中x≥0，x≥0。S1.2.2LP的基可行解的概念maxz=Cxz=CXmax[2Px,=b[AX = bj=l[X≥0[X,",x≥0设系数矩阵A的秩是m，即A的m个行向量是线性无关的。若B是A的m阶满秩子阵，称B为问题的一个基。设B=（P，Ps，，P），称对应的变量x，Xs，，xi为基变量，其它的变量称为非基变量。令非基变量等于0，从方程组可以唯一解出基变量的值，从而得到方程组的一个解，称为基本解：如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为可行基。$1.2.3LP解的性质1.凸集和极点2.线性规划解的性质定理1线性规划的可行域R是凸集。定理2X是线性规划基可行解的充分必要条件是X是可行域的极点。定理3线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。第5页
运筹学讲稿 第 5 页 §1.2 线性规划的标准形式和解的性质 §1.2.1 LP 的标准形式 ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = = = = ∑ ∑ = = x j n a x b i m z c x j i n j ij j n j j j 0 1,2, , 1,2, , max 1 1 L L 变换一般 LP 为标准形式的方法： （1）如果原问题目标函数求极小值： ∑= = n j j j z c x 1 min 令 z1=－z，转化为求 ∑= = − n j j j z c x 1 1 max ( ) 。 （2）若某个右端常数 bi<0，则以－1 乘该约束两端。 （3）若某约束为“≤”型的不等式约束，则在左端加上一个非负变量，称为松弛变量，使不等 式化为等式；若某约束为“≥”型，则在左端减去一个非负变量，称为剩余变量，或者仍然称为松弛 变量，使不等式转化为等式。 （4）若某个 xj 的符号约束为 xj≤0；那么令 xj ′ =－xj，则 xj ′ ≥0；若某个 xj 无符号限制，则可令 xj=xj ′ －xj ″ ，其中 xj ′ ≥0，xj ″ ≥0。 §1.2.2 LP 的基可行解的概念 ⎩ ⎨ ⎧ ≥ = = 0 b max X AX z CX ⎪ ⎩ ⎪ ⎨ ⎧ ≥ = = ∑= , , 0 b max 1 1 n j n j j x x P x z CX L 设系数矩阵 A 的秩是 m，即 A 的 m 个行向量是线性无关的。若 B 是 A 的 m 阶满秩子阵，称 B 为 问题的一个基。设 B=（ 1 Pj ， 2 Pj ，.， jm P ），称对应的变量 1 j x ， 2j x ，.， jm x 为基变量，其它的 变量称为非基变量。令非基变量等于 0，从方程组可以唯一解出基变量的值，从而得到方程组的一个 解，称为基本解；如果它的各个分量非负，即它同时又是可行解，则称之为基可行解，对应的基称为 可行基。 §1.2.3 LP 解的性质 1. 凸集和极点 2.线性规划解的性质 定理 1 线性规划的可行域 R 是凸集。 定理 2 X 是线性规划基可行解的充分必要条件是 X 是可行域的极点。 定理 3 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优 解。 （1.4） （1.5） （1.6）
运筹学讲稿第3次课2学时0上次课复习：线性规划的标准形式、特点；基可行解的概念。本次课题（或教材章节题目）：$1.3单纯形法0教学要求：掌握单纯形法的解题思路、单纯形法要点和单纯形表重点：单纯形表：单纯形法则难点：初始单纯形表：换基送代法则教学手段及教具：多媒体教学。讲授内容及时间分配：10分钟上次课复习及作业$1.3.1单纯形法的解题思路40分钟$1.3.2单纯形法要点和单纯形表40分钟0P437、(1)10分钟P437、(2)课后作业0《运筹学》钱颂迪主编清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社陶谦坎主编《运筹学应用案例》机械工业出版社注：本页为每次课教案首页第6页
运筹学讲稿 第 6 页 第 3 次课 2 学时 注：本页为每次课教案首页 上次课复习： 线性规划的标准形式、特点； 基可行解的概念。 本次课题（或教材章节题目）：§1.3 单纯形法 教学要求： 掌握单纯形法的解题思路、单纯形法要点和单纯形表 重 点：单纯形表；单纯形法则 难 点：初始单纯形表；换基迭代法则 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 10 分钟 §1.3.1 单纯形法的解题思路 40 分钟 §1.3.2 单纯形法要点和单纯形表 40 分钟 P43 7、（1） 10 分钟 课后作业 P43 7、（2） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿$1.3单纯形法81.3.1单纯形法的解题思路由具体例题突出相关概念。$1.3.2单纯形法要点和单纯形表1.检验数的意义和计算公式HmaxC,xj=lxaij=m+I-Za2,x, = b2X2j=m+1Zamx,=bmx.+j=m+1X,X2x,≥0(1.19)o.caji=l2.单纯形表表 1-5..cj"*CmC1C2Cm+1CkCnb.....CBXBXi..XmXm+1XkXnX200bi1....lm+1...akainCIXib2010....C2X2a2m+1a2ka2n.....................bm001Xm...Amm+1amk...amnCm"m0000jc,aim+lCkZc,aikZc,aC.Cm+1L1=1i=li=l3.单纯形法的基本法则法则1最优性判定法则法则2换入变量确定法则设,=max(g,o,>0,则x为换入变量。I法则3换出变量确定法则b.b,ak0/=e=min(1.21)aikak再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一定包含负分量，即不是可行解。第7页
运筹学讲稿 第 7 页 §1.3 单纯形法 §1.3.1 单纯形法的解题思路 由具体例题突出相关概念。 §1.3.2 单纯形法要点和单纯形表 1. 检验数的意义和计算公式 ∑= = n j j j z c x 1 max ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ + = + = + = ∑ ∑ ∑ = + = + = + , , 0 1 2 1 2 1 2 2 1 1 1 1 n m n j m m mj j n j m j j n j m j j x x x x a x b x a x b x a x b L LLLL ∑= = − m i j j iaij c c 1 σ （1.19） 2.单纯形表 表 1-5 cj c1 c2 . cm cm+1 . ck . cn CB XB b x1 x2 . xm xm+1 . xk . xn c1 c2 . cm x1 x2 . xm b1 b2 . bm 1 0 . 0 a1m+1 . a1k . a1n 0 1 . 0 a2m+1 . a2k . a2n . . . . . . 0 0 . 1 amm+1 . amk . amn σj 0 0 . 0 ∑= + − + m i m iaim c c 1 1 1 . ∑= − m i k iaik c c 1 . ∑= − m i n iain c c 1 3. 单纯形法的基本法则 法则 1 最优性判定法则 法则 2 换入变量确定法则 设 = max{ j j > 0} j σ k σ σ ，则 xk为换入变量。 法则 3 换出变量确定法则 lk l ik ik i i a b a a b = ⎭ ⎬ ⎫ ⎩ ⎨ ⎧ θ = min > 0 （1.21） 再强调一下，这个法则的目的是，保证下一个基本解的可行性，违背这一法则，下一个基本解一 定包含负分量，即不是可行解
运筹学讲稿法则4换基选代运算法则z=2x, +5x2max2=8X +2x2 +X35x, +2x2= 20+ X44x2+x, =12[X1,X2,Xg,X4,X, ≥0表 1-625000cj0比CBXBbXiX2X3x4xs08211008/2X32052010020/2X40120001[4] 12/4xs2o5000200[1]0-1/22/1X31451000-1/214/5x45300101/4X2-20000-5/4221010-1/2X140-51200x45310001/4 X20j00-20-1/4最优解X=（(2,3，0，4，0)2=2X2+5X3=19。.第8页
运筹学讲稿 第 8 页 法则 4 换基迭代运算法则 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ + = + + = + + = = + , , , , 0 4 12 5 2 20 2 8 max 2 5 1 2 3 4 5 2 5 1 2 4 1 2 3 1 2 x x x x x x x x x x x x x z x x 表 1-6 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 θ比 0 0 0 x3 x4 x5 8 20 12 1 5 0 2 2 [4] 1 0 0 0 1 0 0 0 1 8/2 20/2 12/4 σj 2 5 0 0 0 0 0 5 x3 x4 x2 2 14 3 [1] 5 0 0 0 1 1 0 0 0 1 0 -1/2 -1/2 1/4 2/1 14/5 — σj 2 0 0 0 -5/4 2 0 5 x1 x4 x2 2 4 3 1 0 0 0 0 1 1 -5 0 0 1 0 -1/2 2 1/4 σj 0 0 -2 0 -1/4 最优解 X* =（2，3，0，4，0）T ，z * =2×2+5×3=19
运筹学讲稿第4次课2学时0上次课复习：单纯形表；单纯形法则；讲解作业3、（3）与4、（1）存在问题。本次课题（或教材章节题目）：$1.3单纯形法$1.3.3关于单纯形法的补充说明0教学要求：掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则；掌握求minz的情况。重点：单纯形判别法则难点：单纯形判别法则及证明；求minz的情况。教学手段及教具：多媒体教学。讲授内容及时间分配：20分钟上次课复习及作业1.无穷多最优解与唯一最优解的判别法则30分钟20分钟2.无最优解（无界解）的判定015分钟3.求minz的情况P437、(3)15分钟P437、(4)课后作业0《运筹学》主编钱颂迪清华大学出版社《运筹学教程》胡运权主编清华大学出版社参考资料《运筹学》牛映武主编西安交大出版社《运筹学应用案例》陶谦坎主编机械工业出版社注：本页为每次课教案首页第9页
运筹学讲稿 第 9 页 第 4 次课 2 学时 注：本页为每次课教案首页 上次课复习： 单纯形表； 单纯形法则； 讲解作业 3、（3）与 4、（1）存在问题。 本次课题（或教材章节题目）：§1.3 单纯形法 §1.3.3 关于单纯形法的补充说明 教学要求： 掌握无穷多最优解与唯一最优解的判别法则、无最优解（无界解）的判定法则； 掌握求 min z 的情况。 重 点：单纯形判别法则 难 点：单纯形判别法则及证明；求 min z 的情况。 教学手段及教具：多媒体教学。 讲授内容及时间分配： 上次课复习及作业 20 分钟 1. 无穷多最优解与唯一最优解的判别法则 30 分钟 2. 无最优解（无界解）的判定 20 分钟 3. 求 min z 的情况 15 分钟 P43 7、（3） 15 分钟 课后作业 P43 7、（4） 参考资料 《运筹学》 钱颂迪 主编 清华大学出版社 《运筹学教程》 胡运权 主编 清华大学出版社 《运筹学》 牛映武 主编 西安交大出版社 《运筹学应用案例》 陶谦坎 主编 机械工业出版社
运筹学讲稿$1.3.3关于单纯形法的补充说明1.无穷多最优解与唯一最优解的判别法则若对某可行解Xi，（1）所有检验数α，≤0，且有一个非基变量x的检验数等于0，则问题有无穷多最优解；（2）所有非基变量的检验数00，但ai≤0，i=1，2，，m即x的系数列向量无正分量，则问题无最优解。3.求minz的情况例14求例2中的LPminz=2x,+2x2+3x(1.22)[20x, +40x2=10-x4(1.23)10x+20x3-x=8[,x2,Xg,x4,x≥0的最优解。表 1-922300cjXBCBbxiX2X3X4Xs21/410-1/400[1/2]X232/51/2010-1/20X3-1/2003/20oi1/2021/2120-1/200Xi30-113/201/40-1/20X300111/403/20第10页
运筹学讲稿 第 10 页 §1.3.3 关于单纯形法的补充说明 1. 无穷多最优解与唯一最优解的判别法则 若对某可行解 X1，（1）所有检验数σj≤0，且有一个非基变量 xk的检验数等于 0，则问题有无穷 多最优解；（2）所有非基变量的检验数σj0，但 aik≤0，i=1，2，.，m 即 xk的系数列向 量无正分量，则问题无最优解。 3.求 min z 的情况 例 14 求例 2 中的 LP ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + − = + − = = + + , , , , 0 10 20 8 20 40 10 min 2 2 3 1 2 3 4 5 1 3 5 1 2 4 1 2 3 x x x x x x x x x x x z x x x 的最优解。 表 1-9 cj 2 2 3 0 0 CB XB b x1 x2 x3 x4 x5 2 3 x2 x3 1/4 2/5 [1/2] 1/2 1 0 0 1 -1/40 0 0 -1/20 σj -1/2 0 0 1/20 3/20 2 3 x1 x3 1/2 3/20 1 0 2 -1 0 1 -1/20 1/40 0 -1/20 σj 0 1 0 1/40 3/20 （1.22） （1.23）