《运筹学》课程教学课件（PPT讲稿）第一章 线性规划及单纯形法（Linear Programming, LP）

第一章线性规划及单纯形法 (Linear Programming,LP) 。线性规划模型 ■图解法 。单纯形法原理 。单纯形法计算步骤 ·单纯形法的进一步讨论 数据包络分析 2025/4/6

2025/4/6 2 第一章 线性规划及单纯形法 (Linear Programming, LP) ◼ 线性规划模型 ◼ 图解法 ◼ 单纯形法原理 ◼ 单纯形法计算步骤 ◼ 单纯形法的进一步讨论 ◼ 数据包络分析

§1一般线性规划问题的数学模型 1.1引例 例1、生产计划问题 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 I,Ⅱ各生产多少，可获最大利润？ 2025/4/6

2025/4/6 3 §1 一般线性规划问题的数学模型 1.1 引例 例1、生产计划问题 Ⅰ Ⅱ 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 Ⅰ，Ⅱ各生产多少, 可获最大利润?

解：设产品I,Ⅱ产量分别为变量x1,x2 max Z=2x1+3x2 2x1+2x2≤12 4X1 ≤16 5x2≤15 x1,x2≥0 注意模型特点 2025/4/6

2025/4/6 4 2x1+2x2  12 4x1  16 5x2  15 x1， x2  0 注意模型特点 max Z= 2x1 +3x2 解:设产品Ⅰ, Ⅱ产量分别为变量x1 ， x2

线性规划模型特点 决策变量：向量X=(x1.Xn)T决策人要考虑 和控制的因素，非负 ■约束条件：关于X的线性等式或不等式 ■目标函数：Z=f(x1.xn)为关于X的线性函数， 求Z极大或极小 2025/4/6

2025/4/6 5 线性规划模型特点 ◼ 决策变量：向量X=(x1. xn ) T 决策人要考虑 和控制的因素，非负 ◼ 约束条件：关于X的线性等式或不等式 ◼ 目标函数：Z=ƒ(x1 . xn ) 为关于X 的线性函数， 求Z极大或极小

1.2线性规划问题的数学模型 三个组成要素： 1.决策变量：是决策者为实现规划目标采取的 方案、措施，是问题中要确定的未知量。 2.目标函数：指问题要达到的目的要求，表 示为决策变量的函数。 3.约束条件：指决策变量取值时受到的各种可 用资源的限制，表示为含决策变量的等式或 不等式。 2025/4/6

2025/4/6 6 1.2 线性规划问题的数学模型 三个组成要素： 1.决策变量:是决策者为实现规划目标采取的 方案、措施，是问题中要确定的未知量。 2.目标函数:指问题要达到的目的要求，表 示为决策变量的函数。 3.约束条件:指决策变量取值时受到的各种可 用资源的限制，表示为含决策变量的等式或 不等式

般线性规问题的数学模型： 目标函数：max(或min)z=cX1+c2x2++cn×n aX1+a12X2+.+a1nXn≤（或=，≥）b1 a2X1+a22X2+.+a2mXm≤（或=，≥）b2 约束条件： amlX1+anm2X2+.+amXn≤（或=，≥）bm X1,X2,.,Xn≥0 2025/4/6

2025/4/6 7 一般线性规划问题的数学模型：           + + +  =  + + +  =  + + +  =  x , x , , x 0 a x a x a x , b a x a x a x , b a x a x a x , b 1 2 n m1 1 m2 2 mn n m 2 1 1 2 2 2 2n n 2 1 1 1 1 2 2 1n n 1      （或 ） （或 ） （或 ） 目标函数： 约束条件： 1 1 2 2 n xn max（或min）z = c x +c x ++c

简写形式： max(或m)z=∑c,x i=1 aX,5(或-，≥)h,(i-,m） j=1 X1≥0 (j=1,.,n) 2025/4/6

2025/4/6 8 简写形式：       =  =  = =   = = （ ， ， ） （或 ，） （ ， ， ） （或 ） x 0 j 1 n a x b i 1 m max min z c x j i n j 1 i j j n j 1 j j  

矩阵形式表为： max(或min)z=CX AX≤（或=，≥）b X≥0 其中： C=(G,C2,.,cn） 01 012 X=(x,x2,.,xn)YA= C21 022 。 02n : b=(b,b2,.,bnY am 0m2 2025/4/6

2025/4/6 9 矩阵形式表示为：      =  = 0 max min X AX b z CX （或 ，） （或 ） 其中：               = m m mn n n a a a a a a a a a A       1 2 21 22 2 C (c c cn ) 11 12 1 , , , = 1 2  ( ) T n X x , x , , x = 1 2  ( ) T b b b bm , , , = 1 2 

1.3 线性规划问题的标准形式 标准形式：maxz=∑c,X, i= a,x,=b,(i=b,m) i=1 x,≥0 (j=1,.,n) 标准形式特点： 1.目标函数为求极大值； 2.约束条件全为等式： 3.约束条件右端常数项全为非负； 4,决策变量取值非负。 2025/4/6 10

2025/4/6 10 1.3 线性规划问题的标准形式 标准形式：       = = = =   = = （ ， ， ） （ ， ， ） x 0 j 1 n a x b i 1 m max z c x j i n j 1 i j j n j 1 j j   标准形式特点： 4. 决策变量取值非负。 1. 目标函数为求极大值； 2. 约束条件全为等式； 3. 约束条件右端常数项全为非负；

一般线性规问题如何化为标准型： 1.目标函数求极小值： mimz=∑c,x j=1 令：z'=-z,即化为： maxz'=max(-z）=-minz =-2c,-(c,k 2025/4/6

2025/4/6 11 一般线性规划问题如何化为标准型： 1. 目标函数求极小值： = = n j j j z c x 1 min 令： z' = −z ，即化为：  ( ) = = = − = −  = − = − n j j j n j j j c x c x z z z 1 1 max max( ) min