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

第一章线性规划及单纯形法(Linear Programming, LP)线性规划模型图解法单纯形法原理单纯形法计算步骤单纯形法的进一步讨论2024-10-27

2024-10-27 2 第一章 线性规划及单纯形法 (Linear Programming, LP) n 线性规划模型 n 图解法 n 单纯形法原理 n 单纯形法计算步骤 n 单纯形法的进一步讨论

S1一般线性规划问题的数学模型1. 1 引例例1.生产计划问题能力I11设备A2212设备B40160设备C5152利润3I，IⅡ各生产多少，可获最大利润？2024-10-27

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

解：设产品I,I产量分别为变量x1，x2max Z= 2x, +3x2目标函数2xj+2x2 ≤ 12≤ 164x1约束条件5x2 ≤ 15X1, X2 ≥ 0决策变量Xj X2 >注意模型特点2024-10-27

2024-10-27 4 2x1+2x2  12 4x1  16 5x2  15 x1， x2  0 注意模型特点 max Z= 2x1 +3x2 解:设产品Ⅰ, Ⅱ产量分别为变量x1 ， x2 目标函数 约束条件 x1，x2 决策变量

S1一般线性规划问题的数学模型1.1 引例例2.已知我系有三种不同体系的建筑应予以修建，其耗用资源数量及可用的资源数量如下表。问不同体系的建筑面积各为多少，才能使提供的总面积达到最大？人工造价钢材水泥砖块(元/m2)(kg/m2)(kg/m2)(块/m2)(工日/m2)12砖混结构1051102104.5钢混结构137301903.0框架结构122251803.5资源限量400万工日11000万元2000万kg15000万kg14700万块2024-10-27

2024-10-27 5 §1 一般线性规划问题的数学模型 1.1 引例 例2. 已知我系有三种不同体系的建筑应予以修建，其耗用资 源数量及可用的资源数量如下表。问不同体系的建筑面积各 为多少，才能使提供的总面积达到最大？ 造价 （元/m2） 钢材 （kg/m2） 水泥 （kg/m2） 砖块 （块/m2） 人工 （工日/m2） 砖混结构 105 12 110 210 4.5 钢混结构 137 30 190 3.0 框架结构 122 25 180 3.5 资源限量 11000万元 2000万kg 15000万kg 14700万块 400万工日

解:设三种结构的建筑面积分别为变量x1，x2，x3万m2max Z= X; +x2+x3105xj+137x2 +122x3≤ 1100012xi+ 30x2 + 25x;≤ 2000110x1 +190x2 + 180x3≤ 15000210x1≤ 1470004.5xj+3.0x2+3.5x3≤ 2000Xi, X2, X3 ≥ 0注意模型特点2024-10-276

2024-10-27 6 105x1+137x2 +122x3 11000 12x1+ 30x2 + 25x3 2000 110x1 +190x2 + 180x3 15000 210x1  147000 4.5x1+ 3.0x2 + 3.5x3 2000 x1， x2 ， x3  0 注意模型特点 max Z= x1 +x2+x3 解:设三种结构的建筑面积分别为变量x1 ， x2， x3万m 2

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

2024-10-27 7 线性规划模型特点 n 决策变量：向量X=(x1. xn )T 决策人要考虑 和控制的因素 n 目标函数：Z=ƒ(x1 . xn ) 为关于X 的线性函数， 求Z极大或极小 n 约束条件：关于X的线性等式或不等式

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

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

一般线性规划问题的数学模型：目标函数：max(或min)Z-Cxi+Cx2+.+Chxnaxi+ai2x2 +....+ainxn<(或=, ≥)bia2ixi+a22x2 +...a2nxn≤(或=, ≥) b2约束条件：amiXi+am2X2 +...+amrxn≤(或=, ≥)bmXi, X2, ...., xn≥02024-10-27

2024-10-27 9 一般线性规划问题的数学模型： 目标函数：max(或min)Z=C1x1+C2x2+.+Cnxn 约束条件： a11x1+a12x2 +.+a1nxn(或=，≥)b1 a21x1+a22x2 +.+a2nxn(或=，≥)b2 . am1x1+am2x2 +.+amnxn(或=，≥)bm x1， x2， .， xn 0

简写形式：max(或min) z=Zcjxjj-1nZayx,≤(或=,≥) b, (i=l,, m)j=1x,≥0(j=l,..., n)2024-10-2710

2024-10-27 10 简写形式：                 （ ， ， ） （或 ， ） （ ， ， ） （或 ） x j n a x b i m z c x j i n j ij j n j j j   0 1 1 max min 1 1

矩阵形式表示为：max(或min)z=CX[AX≤(或=,≥) bX≥0其中:C= (Ci,C2,*.,Cn)aar2aina21a22aznX =(x1, X2,*, x,)A=.....:b= (b,b2,...,bm)amlam2amm)112024-10-27

2024-10-27 11 矩阵形式表示为：         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 