北京理工大学：《运筹学》课程PPT教学课件（讲稿）第二章 线性规划建模及单纯形法

课 制作:北景狸工夫吴新泉奇 器因翻 数学术

运筹学课件 制作：北京理工大学 吴祈宗等

第二章 线性规灲建模及单纯形法 本章内容重点 线性规刈模型与解的主要概念 线性规划的单纯形法,线性规 划多解分析 线性规划应用 建模

2 第二章 线性规划建模及单纯形法 本章内容重点 线性规划模型与解的主要概念 线性规划的单纯形法，线性规 划多解分析 线性规划应用——建模

1.线性规划的概A 例2.1:某工厂拥有A、BC三种类型的 设备,生产甲、乙两种产品。每件产品在 生产中要占用的设备机时数。每件产品 可以获得的利润以及三种设备可利用的时 数如下表所示 午品甲产品乙设备能力 设备A 2 65 设备B 320 40 设备C 3 75 利润(元/件) 1500 2500

3 1.线性规划的概念 例2.1:某工厂拥有A、B、C三种类型的 设备，生产甲、乙两种产品。每件产品在 生产中需要占用的设备机时数，每件产品 可以获得的利润以及三种设备可利用的时 数如下表所示： 产品甲 产品乙 设备能力 （h） 设备A 3 2 65 设备B 2 1 40 设备C 0 3 75 利润（元/件） 1500 2500

1.线性规划的概念 问题:工厂应如何安排生产可获得最 大的总利润? 解:设变量x;为第i种(甲、乙)产 品的生产件数(i=1,2)。根据题意 我们知道两种产品的生产受到设备能力 (机时数)的限制。对设备A,两种产品 生产所占用的机时数不能超过65,于是我 们可以得到不等式:3x,+2x2≤65 对设备B.两种产品生产所占用的机 时数不能超过40.于是我们可以得到不等 式:2x1+x2≤40;

4 问题：工厂应如何安排生产可获得最 大的总利润？ 解：设变量xi为第i种（甲、乙）产 品的生产件数（i＝1，2）。根据题意， 我们知道两种产品的生产受到设备能力 （机时数）的限制。对设备A，两种产品 生产所占用的机时数不能超过65，于是我 们可以得到不等式：3 x1 + 2 x2 ≤ 65； 对设备B，两种产品生产所占用的机 时数不能超过40，于是我们可以得到不等 式：2 x1 + x2 ≤ 40； 1.线性规划的概念

L能性规划的概 对设备C两种产品生产所占用的 机时数不能超过75,于是我们可以得到 不等式:3x≤75;另外,产品数不可 能为负,即x1,X2≥0。同时,我们有 一个追求目标,即获取最大利润。于是 可写出目标函数z为相应的生产计划可以 获得的总利润:z1500x+2500x。综合 上述讨论,在加工时间以及利润与产品 产量成线性关系的假设下,把目标函数 和约東条件放在一起,可以建立如下的 线性规划模型

5 对设备C，两种产品生产所占用的 机时数不能超过75，于是我们可以得到 不等式：3x2 ≤75 ；另外，产品数不可 能为负，即 x1 ,x2 ≥0。同时，我们有 一个追求目标，即获取最大利润。于是 可写出目标函数z为相应的生产计划可以 获得的总利润：z=1500x1 +2500x2 。综合 上述讨论，在加工时间以及利润与产品 产量成线性关系的假设下，把目标函数 和约束条件放在一起，可以建立如下的 线性规划模型： 1.线性规划的概念

L.线性规的概 目标函数Maxz=1500x,+2500x 约東条件S.t.3X+2x≤65 2xx≤40 3X公75 x1,x2>0

6 目标函数 Max z =1500x1 +2500x2 约束条件 s.t. 3x1 +2x2≤ 65 2x1 +x2≤ 40 3x2≤ 75 x1 ,x2 ≥0 1.线性规划的概念

L.线性规的概 这是一个典型的利润最大化的生 产计划问题。其中,“Max是英文单 词“ Maximize'的缩写,含义为“最大 化” 66 S.t.是 66 subject to的缩 写,表示“满足于.”。因此,上述 模型的含义是:在给定条件限制下, 求使目标函数z达到最大的X,,X的取 值

7 这是一个典型的利润最大化的生 产计划问题。其中， “Max”是英文单 词“Maximize”的缩写，含义为“最大 化”；“s.t.”是“subject to”的缩 写，表示“满足于……” 。因此，上述 模型的含义是：在给定条件限制下， 求使目标函数z达到最大的x1 ,x2 的取 值。 1.线性规划的概念

1。线性规划的概念 般形式 目标函数: Max()z=Cr+ Caxa+.+ cnX 约束条件 a11x+a2X2+…+a1nX )6 21H a2x2+.+ax≤(=,>)b 1m1+2+…,+amx(=,>)b 9 ●● ,xn>0

8 •一般形式 •目标函数： Max(Min)z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1+a12x2+…+a1nxn≤( =, ≥ )b1 a21x1+a22x2+…+a2nxn≤( =, ≥ )b2 .. . am1x1+am2x2 +…+amnxn≤( =, ≥ )bm x1 ，x2 ，… ，xn ≥ 0 1.线性规划的概念

1.线性规划的概 标准形式 目标函数 Max Z=CX,+ C2x,+ ·约束条件 a a aox bb 组x1+a2x2+…+mxn=b 0

9 •标准形式 •目标函数： Max z = c1x1 + c2x2 + … + cnxn •约束条件： a11x1 + a12x2 + … + a1nxn = b1 a21x1 + a22x2 + … + a2nxn = b2 ... am1x1 + am2x2 + … + amnxn = bm x1 ，x2 ，… ，xn ≥ 0 1.线性规划的概念

1.线性规划的概 可以看出,线性规划的标准 形式有如下四个特点:目标最大 化、约束为等式、决策变量均非 负、右端项非负。 对于各种非标准形式的线性 规划问题,我们总可以通过以下 变换,将其转化为标准形式

10 可以看出，线性规划的标准 形式有如下四个特点：目标最大 化、约束为等式、决策变量均非 负、右端项非负。 对于各种非标准形式的线性 规划问题，我们总可以通过以下 变换，将其转化为标准形式: 1.线性规划的概念