中南民族大学：《运筹学》第一章 线性规划（叶娟）

第一章线性规划 线性规划的建模 线性规划的模型 线性规划的图解法 线性规划的标准化 口线性规划的基本概念 线性规划的求解

第一章 线性规划 线性规划的建模 线性规划的模型 线性规划的图解法 线性规划的标准化 线性规划的基本概念 线性规划的求解

1、线性规划的建模一例(例1)1 例1:在工厂计划期内要安排生产A、B两 种产品,已知生产单位产品所需的设备 台时及a、b两种原材料的消耗如下表 又该工厂每生产一件A产品可获利2元, 每生产一件B产品可获例3元。问:如何 安排计划使该工厂获利最大? 产品A产品B资源总数 设备 8台时 原材料a 1402 2043 16KG 原材料b 12KG 单位利润 2

2 1、线性规划的建模一例（例1） 例1：在工厂计划期内要安排生产A、B两 种产品，已知生产单位产品所需的设备 台时及a、b两种原材料的消耗如下表。 又该工厂每生产一件A产品可获利2元， 每生产一件B产品可获例3元。问：如何 安排计划使该工厂获利最大？ 产品A 产品B 资源总数 设备 1 2 8台时 原材料a 4 0 16KG 原材料b 0 4 12KG 单位利润 2 3

设产品产品B资源总数 2 8台时 原材料a 4 0 16KG 原材料b 12KG 单位利润 2 解设A、B两种的产量分别为x1,x2(决簟变量),该 问题的数学模型为: 目标函数maxz=2x,x3 x,+2x≤8 约束函数 ( Subject To: s.t.) 4x ≤16 4x≤12 2 xn,x,≥O 3

3 解 设A、B两种的产量分别为 （决策变量），该 问题的数学模型为： 目标函数 约束函数 （Subject To：s.t.） 1 2 x x, max 2 3 1 2 z x x = + 1 2 1 2 1 2 2 8 4 16 4 12 , 0 x x x x x x  +           产品A 产品B 资源总数 设备 1 2 8台时 原材料a 4 0 16KG 原材料b 0 4 12KG 单位利润 2 3

2、线性规划模型 maxz=2x,+3x2 x=(31C=(c1)=(23 X,+2x≤8 ≤16/a1a2 12 22 40 4x 04 4x≤12 b X1。xXC b=b,=16 4

4 2、线性规划模型 max 2 3 1 2 z x x = + 1 2 1 2 1 2 2 8 4 16 4 12 , 0 x x x x x x  +           C c c = = ( 1 2 , 2,3 ) ( ) 1 2 x X x   =     11 12 21 22 31 32 1 2 4 0 0 4 a a A a a a a         = =             1 2 3 8 16 12 b b b b         = =            

线性规划模型解析式标准形式 maxz=Cr +c2x2+:.'CnIn 1x1+a12x2+…+a1nxn 21x1+a2x2+…+a2nxn n1x1+an2x2+……+anXn= bn x1≥0,j=1,…,n

5 线性规划模型解析式标准形式 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 max 0, 1, , . n n n n n n m m mn n m j z c x c x c x a x a x a x b a x a x a x b a x a x a x b x j n = + +  + + + =  + + + =     + + + =    = 

模型形式简记 X1 max 人十 b2 x st x1≥0(j=1,2,…,n) A C=( 6

6 模型形式简记 1 1 max ( 1, 2, , ) . . 0 ( 1, 2, , ) n j j j n ij j i j j Z c x a x b i m s t x j n = = =  = =     =    11 12 1 21 22 2 1 2 n n m m mn a a a a a a A a a a       =       1 2 ( , , , ) C c c c = n 1 2 m b b b b       =       1 2 n x x X x       =       1 2 , 1,2, , j j j mj a a P j n a       = =        

线性规划模型矩阵标准形式 线性规划模型的结构ma(min)z=CX 目标函数:max, min s. AX2(=,≤)b 约束条件:≥=≤ 变量符号::≥0,unr,≤0 X≥(≤)0,mr 线性规划的标准形式 max z=CX 目标函数:max s.t. aX=b 约束条件 变量符号:≥0 X≥0 7

7 线性规划模型矩阵标准形式 线性规划模型的结构 目标函数 ：max，min 约束条件：≥,=,≤ 变量符号：：≥0, unr, ≤0 线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：≥0 max(min) . . ( , ) ( )0, z CX s t AX b X unr =  =    max . . 0 z CX s t AX b X = = 

线性规划模型练习7 三种产品要经过三种不同的工序加工。各 种产品每一件所需时间(分钟),每天各道工 序的加工能力(每天多少分钟)和销售每一种 品的单位利润如下。试建立使总利润达到最 大的线性规划模型 工序 每件时间(分钟) 工序加工能 第1种产品第2种产品第3种产品 力 (分钟/天) 2 430 2 460 420 利润/件 (元) 8

8 线性规划模型练习1 三种产品要经过三种不同的工序加工。各 种产品每一件所需时间（分钟），每天各道工 序的加工能力（每天多少分钟）和销售每一种 产品的单位利润如下。试建立使总利润达到最 大的线性规划模型。 工序 每件时间（分钟） 第1种产品 第2种产品 第3种产品 工序加工能 力 （分钟/天） 1 2 3 1 2 1 3 1 2 1 4 1 430 460 420 利润/件 （元） 3 2 5

线性规划模型练习2 某厂为进行生产需采购A、B两种原材料, 单价分别为70元/公斤和50元/公斤。现 要求购买资金不超过5000元,总购买量 不少于80公斤,而A原材料不少于20公 斤。问如何确定最好的采购方案(即花 掉的资金最少并且购买的总量最大)?

9 线性规划模型练习2 某厂为进行生产需采购A、B两种原材料， 单价分别为70元/公斤和50元/公斤。现 要求购买资金不超过5000元，总购买量 不少于80公斤，而A原材料不少于20公 斤。问如何确定最好的采购方案（即花 掉的资金最少并且购买的总量最大）？

3、线性规划的图解 解决只有两个决策变量的线性规划问题 ■方法:在直角坐标系中画出所有约束方 程的图象,从而得到可行城(端足所有 约東方程的解的集合);然后画出经过 原点的目标函数图象的平行线—目标 函教等值线;寻找经过可行域的使Z达到 最大的目标函数等值线,该直线与可行 域的交集即为最优解集。 10

10 3、线性规划的图解 ◼ 解决只有两个决策变量的线性规划问题 ◼ 方法：在直角坐标系中画出所有约束方 程的图象，从而得到可行域（满足所有 约束方程的解的集合）；然后画出经过 原点的目标函数图象的平行线——目标 函数等值线；寻找经过可行域的使Z达到 最大的目标函数等值线，该直线与可行 域的交集即为最优解集