运筹学 第一章 线性规划 (第三版) 与单纯形 型法 第6节 《运筹学》教材编写组编 应用举例 钱颂迪制作 清华大学出版社
运筹学 (第三版) 《运筹学》教材编写组 编 清华大学出版社 第一章 线性规划 与单纯形 型法 第6节 应用举例 钱颂迪 制作
第6节应用举例 般讲,一个经济、管理问题凡满足以下条件 时,才能建立线性规划的模型。 ·(1)要求解问题的目标函数能用数值指标来表示, 且Z=x)为线性函数; (2)存在着多种方案 (3)要求达到的目标是在可以量化的,并要有足够 数据的一定约束条件下实现的;这些约束条件可用 线性等式或不等式来描述。 ·下面举例说明线性规划在经济管理等方面的应用
第6节 应 用 举 例 一般讲，一个经济、管理问题凡满足以下条件 时，才能建立线性规划的模型。 • (1) 要求解问题的目标函数能用数值指标来表示， 且Z=f(x)为线性函数； • (2) 存在着多种方案； • (3) 要求达到的目标是在可以量化的，并要有足够 数据的一定约束条件下实现的；这些约束条件可用 线性等式或不等式来描述。 • 下面举例说明线性规划在经济管理等方面的应用
例10合理利用线材问题。现要做100套钢架,每套需 用长为29m,2.1m和1.5m的元钢各一根。已知原料长 74m,问应如何下料,使用的原材料最省 解最简单做法是,在每一根原材料上 截取29m,2.1m和1.5m的元钢各一根组 成一套,每根原材料剩下料头0.9m(7.4- 29-2.1-15=09)。为了做100套钢架,需 用原材料100根,共有90m料头。若改为 用套裁,这可以节约原材料。下面有几 种套裁方案,都可以考虑采用 见表1-1l
例10 合理利用线材问题。现要做100套钢架，每套需 用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长 7.4m，问应如何下料，使用的原材料最省。 • 解 最简单做法是，在每一根原材料上 截取2.9m，2.1m和1.5m的元钢各一根组 成一套，每根原材料剩下料头0.9m（7.4- 2.9-2.1-1.5=0.9)。为了做100套钢架，需 用原材料100根，共有90m料头。若改为 用套裁，这可以节约原材料。下面有几 种套裁方案，都可以考虑采用。 • 见表1-11
表1-11套裁方案 下料根数 方 案 长度(m 2.9 2.5 2 合计 7.4 7.2 6.6 料头 0.1 0.2 0.30.8
表1-11 套裁方案 下料根数 方 案 长度(m) Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 2.9 2.5 1.5 1 0 3 2 1 2 2 1 2 1 3 合计 料头 7.4 0 7.3 0.1 7.2 0.2 7.1 0.3 6.6 0.8
为了得到100套钢架,需要混合使用各种下料 方案。设按Ⅰ方案下料的原材料根数为x,Ⅱ方案为 x2,Ⅲ方案为x2,Ⅳ方案为x4,V方案为x。根据表 1-11的方案,可列出以下数学模型: minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5 x1+2x2 100 2x3+2x4+x5=100 3x1+x,+2x +3xx=100 Max 2,354 ≥0
为了得到100套钢架，需要混合使用各种下料 方案。设按Ⅰ方案下料的原材料根数为x1 ,Ⅱ方案为 x2，Ⅲ方案为x3，Ⅳ方案为x4 ,Ⅴ方案为x5。根据表 1-11的方案，可列出以下数学模型： + + + = + + = + + = = + + + + , , , , 0 3 2 3 100 2 2 100 2 100 min 0 0.1 0.2 0.3 0.8 1 2 3 4 5 1 2 3 5 3 4 5 1 2 4 1 2 3 4 5 x x x x x x x x x x x x x x x z x x x x x
在以上约束条件中加入人工变量x6,x,x8; 然后用表1-12进行计算 0 0.2 0.3 0.8 M 0 X X X 5 X6 X XO M 0 0 100|100/1 -M X7 1000 0 2 010 M|x8100[3 0|0|1100/1 4M|-01+3M|-02+4M|03+3M-08+4M000
在以上约束条件中加入人工变量x6 ,x7 ,x8； 然后用表1-12进行计算。 cj→ 0 0.1 0.2 0.3 0.8 -M -M -M θi CB XB b x1 x2 x3 x4 x5 x6 x7 x8 -M -M -M x6 x7 x8 100 100 100 1 0 [3] 2 0 1 0 2 2 1 2 0 0 1 0 1 0 0 0 1 0 0 0 1 100/1 － 100/1 cj -zj 4M -0.1+3M -0.2+4M -0.3+3M -0.8+4M 0 0 0
第1次计算 一 0 0.1 0.2 0.30.8-MMM0 CⅩ B M|x620030 5/3 2/3 10-1/3200/3 -M|x71000 0100/2 1x1|10031 1/3 2/3 100|13 0-01+5/3M-02+4/3M-03+M-0.8004/3M
第1次计算 cj→ 0 0.1 0.2 0.3 0.8 -M -M -M θi CB XB b x1 x2 x3 x4 x5 x6 x7 x8 -M -M 1 x6 x7 x1 200/3 100 100/3 0 0 1 5/3 0 1/3 -2/3 2 2/3 1 [2] 0 -1 1 1 1 0 0 0 1 0 -1/3 0 1/3 200/3 100/2 － cj -zj 0 -0.1+5/3M -0.2+4/3M -0.3+3M -0.8 0 0 -4/3M
第2次计算 0.20.30 M -M-M 0 Mx6503053]530-32|1-12|15015 03x45001 12 012 0x1|1003 /3 2/3 cz0-0+sM41015M163M0153M-43M
cj→ 0 0.1 0.2 0.3 0.8 -M -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 θi -M -0.3 0 x6 x4 x1 50/3 50 100/3 0 0 1 [5/3] 1 1/3 -5/3 1 2/3 0 1 0 -3/2 1/2 1 1 0 0 -1/2 1/2 0 -5 -2 1 150/15 － 100/1 cj -zj 0 -0.1+5/3M 0.1-5/3M 0 -0.65-3/2M 0 .15-3/2M -4/3M 第2次计算
例1-1的最终计算表(第3次计算) 00.1020.30.8 1001 3/10 0.3 5000|1 X=01 1/3 0 1/3 0 0x1|3010 013/10 1/5 1/10 2/5 c-z■L0000074M+006|M+02M02 有非基变量的检验数为零,所以存在多重最优解
例1-11的 最终计算表（第3次计算） cj→ 0 0.1 0.2 0.3 0.8 -M -M -M θi CB XB b x1 x2 x3 x4 x5 x6 x7 x8 0.1 -0.3 0 x2 x4 x1 10 50 30 0 0 1 1 0 0 -1 1 1 0 1 0 -9/10 1/3 13/10 3/5 0 -1/5 -3/10 1/3 1/10 -1/5 0 2/5 cj -zj 0 0 0 0 -0.74 -M+0.06 -M+0.12 -M-0.02 有非基变量的检验数为零，所以存在多重最优解
由计算得到最优下料方案是: 按Ⅰ方案下料30根 Ⅱ方案下料10根; Ⅳ方案下料50根。 即需90根原材料可以制造100套 钢架
由计算得到最优下料方案是： • 按Ⅰ方案下料30根； • Ⅱ方案下料10根； • Ⅳ方案下料50根。 • 即需90根原材料可以制造100套 钢架