第一章 线性规划及单纯形法(Linear Programming, LP)线性规划模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论数据包络分析2025/4/5
2025/4/5 2 第一章 线性规划及单纯形法 (Linear Programming, LP) ◼ 线性规划模型 ◼ 图解法 ◼ 单纯形法原理 ◼ 单纯形法计算步骤 ◼ 单纯形法的进一步讨论 ◼ 数据包络分析
S1一般线性规划问题的数学模型1. 1 引例例1、生产计划问题IIT能力22设备A1240设备B160设备C51523利润I，IⅡI各生产多少，可获最大利润？2025/4/5
2025/4/5 3 §1 一般线性规划问题的数学模型 1.1 引例 例1、生产计划问题 Ⅰ Ⅱ 能力 设备A 2 2 12 设备B 4 0 16 设备C 0 5 15 利润 2 3 Ⅰ，Ⅱ各生产多少, 可获最大利润?
解：设产品I，I产量分别为变量xi，X2max Z= 2x +3x22x;+2x, ≤ 12≤ 164x15x2 ≤ 15Xi, X, ≥ 0注意模型特点2025/4/5
2025/4/5 4 2x1+2x2 12 4x1 16 5x2 15 x1， x2 0 注意模型特点 max Z= 2x1 +3x2 解:设产品Ⅰ, Ⅱ产量分别为变量x1 ， x2
线性规划模型特点决策变量：向量X=(x1..Xn)T决策人要考虑和控制的因素，非负一约束条件：关于X的线性等式或不等式■目标函数：Z=f(x1xn)为关于X的线性函数求乙极大或极小2025/4/5
2025/4/5 5 线性规划模型特点 ◼ 决策变量：向量X=(x1. xn ) T 决策人要考虑 和控制的因素，非负 ◼ 约束条件：关于X的线性等式或不等式 ◼ 目标函数：Z=ƒ(x1 . xn ) 为关于X 的线性函数， 求Z极大或极小
1.2线性规划问题的数学模型三个组成要素：1.决策变量：是决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。2.目标函数：指问题要达到的目的要求，表示为决策变量的函数。3.约束条件：指决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。2025/4/5
2025/4/5 6 1.2 线性规划问题的数学模型 三个组成要素： 1.决策变量:是决策者为实现规划目标采取的 方案、措施，是问题中要确定的未知量。 2.目标函数:指问题要达到的目的要求，表 示为决策变量的函数。 3.约束条件:指决策变量取值时受到的各种可 用资源的限制，表示为含决策变量的等式或 不等式
一般线性规划问题的数学模型：目标函数：max（或min）z=c,X,+C2X2+···+cXnanX +ai2X2 +...+ainXn≤(或=,≥) bia2iX +a22X2 +...+a2nXn ≤(或=,≥) b,约束条件：amiX+am2X2 +...+amXn≤(或=,≥) bmXi,X2,",Xn ≥02025/4/5
2025/4/5 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(或min）z=cx;j=12aai;X;≤(或=,≥）b(i=l,.，m) j=1X,≥0(j=l,.., n)2025/4/5
2025/4/5 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≤（或=,≥)bX≥0其中:C=(ciC.,, cn)ala12aina21a22a2nX =(x,x2,*, xn)A=..:..b=(b,b2,..,bm)amlam2amn)2025/4/5
2025/4/5 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线性规划问题的标准形式11之oxZ=.max标准形式j-1[之arx,=b. (i=l,.., m)j-1[x,≥0(j= l,..., n)标准形式特点：1．目标函数为求极大值：2.约束条件全为等式；3.约束条件右端常数项全为非负；4.决策变量取值非负。2025/4/510
2025/4/5 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.目标函数求极小值：min z =C,xj-1令： z'=-z，即化为:max z' = max(-z) = -min z--Zcx, -Z(-c,)x,12025/4/5
2025/4/5 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