第6节应用举例 一般讲，一个经济、管理问题凡满足以下条 件时，才能建立线性规划的模型： (1)要求解问题的目标函数能用数值指标来表 示，且Z=fx)为线性函数； (2)存在着多种方案； (3)要求达到的目标是在一定约束条件下实现 的；这些约束条件可用线性等式或不等式来 描述
第6节 应 用 举 例 一般讲，一个经济、管理问题凡满足以下条 件时，才能建立线性规划的模型： (1) 要求解问题的目标函数能用数值指标来表 示，且Z=f(x)为线性函数； (2) 存在着多种方案； (3) 要求达到的目标是在一定约束条件下实现 的；这些约束条件可用线性等式或不等式来 描述
举例说明线性规划在经济管理等 方面的应用
举例说明线性规划在经济管理等 方面的应用
例10 合理利用线材问题 现要做100套钢架，每套需用长为 2.9m,2.1m和1.5m的元钢各一根。 已知原料长7.4m,问应如何下料， 使所用的原材料最省
例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料头 若改为用套裁，这可以节约原材料。下 面有几种套裁方案，都可以考虑采用
解 • 最简单做法是，在每一根原材料上截取 2.9m，2.1m和1.5m的元钢各一根组成一 套，每根原材料剩下料头0.9m（7.4-2.9- 2.1-1.5=0.9)。为了做100套钢架，需用原 材料100根，共有90m料头 • 若改为用套裁，这可以节约原材料。下 面有几种套裁方案，都可以考虑采用
表1-11 套裁方案 下料根数 方 案 长度(m) I I I V V 2.9 1 2 2.1 0 2 2 1 1.5 3 1 2 3 合计 7.4 7.3 7.2 7.1 6.6 料头 0 0.1 0.2 0.3 0.8
表1-11 套裁方案 下料根数 方 案 长度(m) Ⅰ Ⅱ Ⅲ Ⅳ Ⅴ 2.9 2.1 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套钢架，需要混合使用各种下料 方案。设按I方案下料的原材料根数为x1,Ⅱ方案为 x2,II方案为x3,V方案为x4,V方案为x5。根据表 1-11的方案，可列出以下数学模型： 余料数量 minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5 x1+2x2 X4 =100 2.9m的数量 2x3+2x4+x5=100 2.1m的数量 3x1+x2+2x3 +3x5=100 1.5m的数量 1,x2,X3,x4,x5≥0
为了得到100套钢架，需要混合使用各种下料 方案。设按Ⅰ方案下料的原材料根数为 x 1,Ⅱ方案为 x 2，Ⅲ方案为 x 3，Ⅳ方案为 x 4,Ⅴ方案为 x 5。根据表 1-11的方案，可列出以下数学模型： ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ =+++ =++ =++ ++++= 0,,,, 100323 22 100 2 100 8.03.02.01.00min 54321 321 5 543 21 4 54321 xxxxx xxxx xxx xxx xxxxxz 2.9m的数量 2.1m的数量 1.5m的数量 余料数量
在以上约束条件中加入人工变量x6,x7,xg 然后用表1-12进行计算。 Max C→ 0 -0.1 -0.2 -0.3 -0.8 |-M-M -M CB XB b X1 X2 X3 X4 X5 X6 X7 X8 -M X6 100 1 2 0 1 0 1 0 0 100/1 -M X7 100 0 0 2 2 1 0 1 0 -M X8 100 [3] 1 2 0 0 0 0 1 100/3 G-Zj 4M -0.1 -0.2 -0.3 -0.8 0 0 0 +3M +4M +3M +4M
在以上约束条件中加入人工变量x 6,x 7,x 8； 然后用表1-12进行计算。 cj→ 0 -0.1 -0.2 -0.3 -0.8 -M -M -M θi CB X B b x1 x2 x3 x4 x5 x 6 x 7 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/3 cj-zj 4M -0.1 +3M -0.2 +4M -0.3 +3M -0.8 +4M 0 0 0 Max
第1次计算 C→ 0 -0.1 -0.2 -0.3 -0.8 -M -M -M 6i CB XB b X X2 X3 X4 X5 X6 X] X8 -M X6 200/3 0 5/3 -2/3 1 -1 1 0 -1/3 200/3 -M X1 100 0 0 2 [2] 1 0 1 0 100/2 0 X1 100/3 1 1/3 2/3 0 1 0 0 1/3 Cj-Zj 0 -0.1 -0.2 -0.3 -0.8 0 0 -4/3M +5/3M +4/3M +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 0 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次计算 Cj→ 0 -0.1 -0.2 -0.3 -0.8 -M -M -M e i CB XB b Xi X2 X3 X4 X5 X6 X] X8 -M X6 50/3 0 [5/3] -5/3 0 -3/2 1 -1/2 -5 150/15 -0.3 X4 50 0 1 1 1 1/2 0 1/2 -2 一 0 100/3 1 1/3 2/3 0 1 0 0 1 100/1 -0.1 0.1 -0.65 0.15 Cj-Zj 0 0 0 -4/3M +5/3M-5/3M -3/2M -3/2M
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 0.15 -3/2M -4/3M 第2次计算
例1-11的最终计算表（第3次计算) C→ 0 -0.1 -0.2 -0.3 -0.8 -M -M -M CB XB b X1 X2 X3 X4 X5 X6 X7 X8 -0.1 X2 10 0 1 -1 0 -9/10 3/5 -3/10 -1/5 -0.3 X4 50 0 0 1 1 1/3 0 1/3 0 Xj 30 1 0 1 0 13/10 -1/5 1/10 2/5 -M -M -M Cj-Zj 0 0 -0.74 +0.06 +0.12 -0.02 有非基变量的检验数为零，所以存在多重最优解
cj→ 0 -0.1 -0.2 -0.3 -0.8 -M -M -M 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 有非基变量的检验数为零，所以存在多重最优解 例1-11的 最终计算表（第3次计算）