运筹学讲稿第次课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）