《数值最优化方法》课程教学课件（讲稿）线性规划（Linear Programming）

Chapter1线性规划 (Linear Programming) 本章主要内容： LP的数学模型 0 图解法 单纯形法 ·单纯形法的进一步讨论一人工变量法 0 LP模型的应用

Chapter1 线性规划 (Linear Programming) LP的数学模型 图解法 单纯形法 单纯形法的进一步讨论－人工变量法 LP模型的应用 本章主要内容：

线性规划问题的数学模型 Page 2 1.规划问题 生产和经营管理中经常提出如何合理安排，使人力 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题： (1)当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源（如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标 (2)在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多、利润最大）

线性规划问题的数学模型 Page 2 1. 规划问题 生产和经营管理中经常提出如何合理安排，使人力、 物力等各种资源得到充分利用，获得最大的效益， 这就是规划问题。 线性规划通常解决下列两类问题： （1）当任务或目标确定后，如何统筹兼顾，合理安排，用 最少的资源（如资金、设备、原标材料、人工、时间等） 去完成确定的任务或目标 （2）在一定的资源条件限制下，如何组织安排生产获得最 好的经济效益（如产品量最多、利润最大.）

线性规划问题的数学模型 Page 3 例1.1如图所示，如何截取x使铁皮所围成的容积最 大？ v=(a-2x}·x w-0 2(a-2x)x·(-2)+(a-2x)2=0 x-8

线性规划问题的数学模型 Page 3 例1.1 如图所示，如何截取x使铁皮所围成的容积最 大？ x a v = (a − x)  x 2 2 = 0 dx dv 2( 2 ) ( 2) ( 2 ) 0 2 a − x  x  − + a − x = 6 a x =

线性规划问题的数学模型 Page 4 例1.2某企业计划生产甲、乙两种产品。这些产品分 别要在A、B、C、D、四种不同的设备上加工。按工 艺资料规定，单件产品在不同设备上加工所需要的台 时如下表所示，企业决策者应如何安排生产计划，使 企业总的利润最大？ 设备 A B C D 利润（元） 产品 甲 2 1 4 0 2 Z 2 2 0 4 3 有效台时 12 8 16 12

线性规划问题的数学模型 Page 4 例1.2 某企业计划生产甲、乙两种产品。这些产品分 别要在A、B、C、D、四种不同的设备上加工。按工 艺资料规定，单件产品在不同设备上加工所需要的台 时如下表所示，企业决策者应如何安排生产计划，使 企业总的利润最大？ 设 备 产 品 A B C D 利润（元） 甲 2 1 4 0 2 乙 2 2 0 4 3 有 效 台 时 12 8 16 12

线性规划问题的数学模型 Page 5 解：设x1、x,分别为甲、乙两种产品的产量，则数学模型为： max Z=2x+3x2 2x1+2x2≤12 X1+2x2≤8 s.t. 4x1 ≤16 4x2≤12 X120,X2≥0

线性规划问题的数学模型 Page 5 解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为： max Z = 2x1 + 3x2 x1 ≥ 0 , x2 ≥ 0 s.t. 2x1 + 2x2 ≤ 12 x1 + 2x2 ≤ 8 4x1 ≤ 16 4x2 ≤ 12

线性规划问题的数学模型 Page 6 2.线性规划的数学模型由三个要素构成 决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints 怎样辨别一个模型是线性规划模型？ 其特征是： (1)问题的目标函数是多个决策变量的线性函数， 通常是求最大值或最小值； (2)问题的约束条件是一组多个决策变量的线性不 等式或等式

线性规划问题的数学模型 Page 6 2. 线性规划的数学模型由三个要素构成 决策变量 Decision variables 目标函数 Objective function 约束条件 Constraints 其特征是： （1）问题的目标函数是多个决策变量的线性函数， 通常是求最大值或最小值； （2）问题的约束条件是一组多个决策变量的线性不 等式或等式。 怎样辨别一个模型是线性规划模型？

线性规划问题的数学模型 Page7 3.线性规划数学模型的一般形式 目标函数： max (min)=c+c++c 01X1+412x2+.+41mXm≤(=·≥)b 约束条件： 0m1x1+a2x2++Amnn≤(=≥)bnm x1≥0xn≥0 简写为：1 mas (rin) 2,se2场 =12.m) x≥0 G=1.2.n)

线性规划问题的数学模型 Page 7 0 0 ( ) ( ) max (min) 1 1 1 2 2 1 1 1 1 2 2 1 1 1 1 2 2   + + +  =   + + +  =   = + + + n m m m n n m n n n n x x a x a x a x b a x a x a x b z c x c x c x          目标函数：  约束条件： 3. 线性规划数学模型的一般形式 0 (j 1 2 ) ( ) (i 1 2 ) max (min) Z 1 1 x n a x b m c x j n j ij j i n j j j    =   =   =  =   = = 简写为：

线性规划问题的数学模型 Page 8 向量形式：max(min)z=CX 图6n 其中：C=(C1c2.cn) Y= B= b

线性规划问题的数学模型 Page 8 向量形式： ( ) C = c1 c2  c n           = n x x X  1           = m j j j a a P  1           = m b b B  1      =   =  0 ( ) max (min) X p x B z CX j j 其中：

线性规划问题的数学模型 Page9 矩阵形式： max (min)Z=CX AX≤(=·≥)B 1X≥0 其中：C=(c1c2·cn) A=

线性规划问题的数学模型 Page 9 矩阵形式：           = m m n n a a a a A      1 1 1 1      =   = 0 ( ) max (min) X AX B Z CX 其中： ( ) C = c1 c2  c n           = n x x X  1           = m b b B  1

线性规划问题的数学模型 Page 10 3.线性规划问题的标准形式 s.t aix,=b i=1,2,.,m x,≥0，j=1,2,n 特点： (1)目标函数求最大值（有时求最小值） (2)约束条件都为等式方程，且右端常数项b,都大于或等于零 (3)决策变量x为非负

线性规划问题的数学模型 Page 10 3. 线性规划问题的标准形式 i m x j n a x b s t Z c x j n j ij j i n j j j 1,2, , 0, 1,2, , . max 1 1   =       = = =   = = 特点： (1) 目标函数求最大值（有时求最小值） (2) 约束条件都为等式方程，且右端常数项bi都大于或等于零 (3) 决策变量xj为非负