第三章 线性规划
第 三 章 线 性 规 划
3.1线性规划模型 例:某工厂拥有A、B、C三种类型的设备, 生产甲、乙两种产品。每件产品在生产中需 要占用的设备机时数,每件产品可以获得的 利润以及三种设备可利用的时数如下表所示: 产品甲产品乙设备能力 设备A 65 设备B 3_20 40 设备C 75 利润(元/件) 1500 2500
3.1 线性规划模型 例:某工厂拥有A、B、C 三种类型的设备， 生产甲、乙两种产品。每件产品在生产中需 要占用的设备机时数，每件产品可以获得的 利润以及三种设备可利用的时数如下表所示： 产品甲 产品乙 设备能力 （h） 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润（元/件） 1500 2500
3.1线性规划模型 问题:工厂应如何安排生产可获得最 大的总利润? 解:设变量x为第(甲、乙)产品 的生产件数(i=1,2)。根据题意,我 们知道两种产品的生产受到设备能力(机 时数)的限制。对设备A,两种产品生产 所占用的机时数不能超过65,于是我们可 以得到不等式:3x2+2 65 对设备B.两种产品生产所占用的机 时数不能超过40.于是我们可以得到不等 式:2x1+x2≤40;
问题：工厂应如何安排生产可获得最 大的总利润？ 解：设变量xi为第i种（甲、乙）产品 的生产件数（i＝1，2）。根据题意，我 们知道两种产品的生产受到设备能力（机 时数）的限制。对设备A，两种产品生产 所占用的机时数不能超过65，于是我们可 以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机 时数不能超过40，于是我们可以得到不等 式：2 x1 + x2 ≤ 40； 3.1 线性规划模型
3.1线性规划模型 对设备C,两种产品生产所占用的机时 数不能超过75,于是我们可以得到不等式: 3x2≤75;另外,产品数不可能为负,即 x,x2≥0。同时,我们有一个追求目标, 即获取最大利润。于是可写出目标函数为 相应的生产计划可以获得的总利润: z-1500x+2500x2。综合上述讨论,在加工 时间以及利润与产品产量成线性关系的假设 下,把目标函数和约束条件放在一起,可以 建立如下的线性规划模型:
对设备C，两种产品生产所占用的机时 数不能超过75，于是我们可以得到不等式： 3x2 ≤75 ；另外，产品数不可能为负，即 x1 ,x2 ≥0。同时，我们有一个追求目标， 即获取最大利润。于是可写出目标函数z为 相 应 的 生 产 计 划 可 以 获 得 的 总 利 润 ： z=1500x1 +2500x2 。综合上述讨论，在加工 时间以及利润与产品产量成线性关系的假设 下，把目标函数和约束条件放在一起，可以 建立如下的线性规划模型： 3.1 线性规划模型
3.1线性规划模型 目标函数Maxz=15002500x2 约束条件s.t.3x+2x65 2x+x540 3x≤75 x,,X2>0
目标函数 Max z =1500x1 +2500x2 约束条件 s.t. 3x1 +2x2≤ 65 2x1 +x2≤ 40 3x2≤ 75 x1 ,x2 ≥0 3.1 线性规划模型
3.1线性规划模型 这是一个典型的利润最大化的生 产计划问题。其中,“Max”是英文单 词“ Maximize?的缩写,含义为“最大 化 s.t.”是“ subject to”的缩 写,表示“满足于…。因此,上述 模型的含义是:在给定条件限制下 求使目标函数达到最大的x,x2的取 值
这是一个典型的利润最大化的生 产计划问题。其中， “Max”是英文单 词“Maximize”的缩写，含义为“最大 化” ； “ s.t.”是“subject to”的缩 写，表示“满足于……” 。因此，上述 模型的含义是：在给定条件限制下， 求使目标函数z达到最大的x1 ,x2 的取 值。 3.1 线性规划模型
3.1线性规划模型 般形式 目标函数 Max(min)z=Cx,+ C2x,+ n-n 约束条件 auXtajoX ln n a2,X, taooxot.tarn (=,>)b amiX+amax t.tammy(=,>>)b X
•一般形式 •目标函数： Max(Min)z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1+a12x2+…+a1nxn≤( =, ≥ )b1 a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 .. . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ 0 3.1 线性规划模型
3.1线性规划模型 标准形式 目标函数 Max z= cix, t coxo t 约束条件 日X+anaX+ b mn 日,1+a,+ aOX b aX,t oxo tm t a m Inn m X 0
•标准形式 •目标函数： Max z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 ... am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0 3.1 线性规划模型
3.1线性规划模型 可以看出,线性规划的标准 形式有如下四个特点:目标最大 化、约東为等式、决策 均非 负、右端项非负 对于各种非标准形式的线性 规划问题,我们总可以通过以下 变换。将其转化为标准形式
可以看出，线性规划的标准 形式有如下四个特点：目标最大 化、约束为等式、决策变量均非 负、右端项非负。 对于各种非标准形式的线性 规划问题，我们总可以通过以下 变换，将其转化为标准形式: 3.1 线性规划模型
3.1线性规划模型 1.极小化目标函数的问题 设目标函数为 Min f= C,X,+ CoXo t 则可以令z f,该极小化问 题与下面的极大化问题有相同的最优 解。即 Max z= 但必须注意,尽管以上两个问题 最优解相同,但他们最优解的目标 函数值却相差一个符号,即 Min f Max z
1.极小化目标函数的问题： 设目标函数为 Min f = c1 x1 + c2 x2 + … + cn xn 则可以令z ＝ -f ，该极小化问 题与下面的极大化问题有相同的最优 解，即 Max z = -c1 x1 - c2 x2 - … - cn xn 但必须注意，尽管以上两个问题 的最优解相同，但他们最优解的目标 函数值却相差一个符号，即 Min f ＝ - Max z 3.1 线性规划模型