第四章数学规划模型 实际问题中Mm(或Mx)=f(x)x=(x2…x) 的优化模型 s.81(x)≤0,t=1,2,…m x决策变量 x)目标函数gx)≤0~约束条件 决策变量个数n和 多元函数约束条件个数m较大学 数线性规划 规非线性规划 条件极值最优解在可行域划整数规划 的边界上取得
第四章数学规划模型 实际问题中 的优化模型 st g x i m Min Max z f x x x x i T n . . ( ) 0, 1,2, ( ) ( ), ( , ) 1 = 或 = = x~决策变量 f(x)~目标函数 gi (x)0~约束条件 多元函数 条件极值 决策变量个数n和 约束条件个数m较大 最优解在可行域 的边界上取得 数 学 规 划 线性规划 非线性规划 整数规划
例1加工奶制品的生产计划 桶 12小时 3公斤A一获利24元/公斤 牛奶或 8小时4公斤A2}获利16元公斤 每天:50桶牛奶时间480小时至多加工100公斤A1 制订生产计划,使每天获利最大
例1 加工奶制品的生产计划 1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划，使每天获利最大 每天：
1桶 12小时 3公斤A1获利24元/公斤 牛奶或 公斤A2获利16元/公斤 8小时 每天50桶牛奶时间480小时至多加工100公斤A1 决策变量x桶牛奶生产A1x2桶牛奶生产A2 目标函数获利24×3s+6432哪 获利16×4x2 每天获利 原料供应 x+x≤50 约束条件劳动时间 12x1+8x2≤480 模型 加工能力 3x1≤100 (LP) 非负约束 ≥0
1桶 牛奶 3公斤A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 x1桶牛奶生产A1 x2桶牛奶生产A2 获利 24×3x1 获利 16×4 x2 原料供应 x1 + x2 50 劳动时间 12x1 +8x2 480 加工能力 3x1 100 决策变量 目标函数 72 1 64 2 每天获利 Max z = x + x 约束条件 非负约束 x1 , x2 0 线性 规划 模型 (LP) 时间480小时 至多加工100公斤A1 每天 50桶牛奶
模型求解图解法 +x,<50 约 x1+x2=50 束12x1+8≤4804:12x+8x2=480 B 3x,<100 l,:3x,=100 件 x,x≥0 l4:x1=0,l5 0 0 Mx2=72x1+64x2 Is D xI 目标 函数 =02=2400 z=c(常数)~等值线在B(0,30)点得到最优解 目标函数和约束条件是线性函数 最优解一定在凸多边 可行域为直线段围成的凸多边形形的某个顶点取得。 目标函数的等值线为直线
模型求解 图解法 x1 x2 0 A B C D l1 l2 l3 l4 l5 x1 + x2 50 12x1 +8x2 480 3x1 100 x1 , x2 0 约 束 条 件 l 1 : x1 + x2 = 50 l 2 :12x1 +8x2 = 480 l 3 :3x1 =100 l 4 : x1 = 0, l 5 : x2 = 0 72 1 64 2 Max z = x + x 目标 函数 Z=0 Z=2400 Z=3360 z=c (常数) ~等值线 c 在B(20,30)点得到最优解 目标函数和约束条件是线性函数 可行域为直线段围成的凸多边形 目标函数的等值线为直线 最优解一定在凸多边 形的某个顶点取得
模型求解 软件实现 LINDO 6.1 max 72x1+64x2 OBJECTIVE FUNCTION VALUE 3360.000 2)x1+x2<50 VARIABLE VALUE REDUCED COST 3)12x1+8x2<480 XI 20.000000 0.000000 4)3x1<100 X2 30.000000 0.000000 end ROW SLACK OR SURPLUS DUAL PRICES 0.000000 48.000000 DO RANGE 0.000000 2.000000 SENSITIVITY ANALYSIS? No 4) 40.000000 0.000000 NO ITERATIONS= 2 20桶牛奶生产A1,30桶生产A2,利润3360元
模型求解 软件实现 LINDO 6.1 max 72x1+64x2 st 2）x1+x2<50 3）12x1+8x2<480 4）3x1<100 end OBJECTIVE FUNCTIONVALUE 1) 3360.000 VARIABLE VALUE REDUCEDCOST X1 20.000000 0.000000 X2 30.000000 0.000000 ROW SLACK OR SURPLUS DUALPRICES 2) 0.000000 48.000000 3) 0.000000 2.000000 4) 40.000000 0.000000 NO.ITERATIONS= 2 DO RANGE (SENSITIVITY) ANALYSIS? No 20桶牛奶生产A1 , 30桶生产A2，利润3360元
例2奶制品的生产销售计划 12小时3千克A,获利24元/公斤 1桶 牛奶或 8小时4公斤A2一获利16元/公斤 元 50桶牛奶,480小时 0.75千克B2,一获利32元/千克 2小时,3元 三至多100公斤A1制订生产计划,使每天净利润最大
例2 奶制品的生产销售计划 1桶 牛奶 3千克A1 12小时 8小时 4公斤A2 或 获利24元/公斤 获利16元/公斤 0.8千克B1 2小时,3元 1千克 获利44元/千克 0.75千克B2 2小时,3元 1千克 获利32元/千克 制订生产计划，使每天净利润最大 50桶牛奶, 480小时 至多100公斤A1
12小时3千克A 获利24元/千克 1桶 牛奶或 8小时4千克A一获利16元/g 决策出售x1千克A,x2千克A2,x3千克B,x千克B2 变 x5千克A1加工B1,x6千克A2加工B2 目标 函数利润M24x1+162+41+32x-3x-3 原料x+x≤50 加工能力x+x≤100 约束供应 4 x,=0.8x 条件劳动4x+x)+2(x+x 附加约束 x=0.75 时间+2x+2x≤480非负约束x:x。0
1桶 牛奶 3千克 A1 12小时 8小时 4千克 A2 或 获利24元/千克 获利16元/kg 0.8千克B1 2小时,3元 1千克 获利44元/千克 0.75千克B2 2小时,3元 1千克 获利32元/千克 出售x1 千克 A1 , x2 千克 A2， X3千克 B1 , x4千克 B2 原料 供应 劳动 时间 加工能力 决策 变量 目标 函数 利润 约束 条件 非负约束 x1 , x6 0 x5千克A1加工B1， x6千克A2加工B2 1 2 3 4 5 6 Max z = 24x +16x + 44x + 32x − 3x − 3x 50 3 4 1 5 2 6 + + x + x x x 2 2 480 4( ) 2( ) 5 6 1 5 2 6 + + + + + x x x x x x x1 + x5 100 附加约束 3 0 8 5 x = . x 4 6 x = 0.75x
模型求解 OBJECTIVE FUNCTION VALUE 1)3460.800 软件实现 LINDO6 VARIABLE VALUE REDUCED COST 2)+x。,x2+x6≤0 0.000000 1.680000 4 X2168.0000000.000000 X319.2000010.000000 2)4x+3x2+4x3+3x6≤60x40.0000 X524.0000000.000000 3)4(x1+x5)+2(x2+x6 X60.000000 1.520000 +2x+2x。<480 ROW SLACK OR SURPLUS DUAL PRICES 0.000000 3.160000 3)4x+2x2+6x+4x≤48030o 3.260000 76.000000 0.000000 DO RANGE 5)0.00000440000 (SENSITIVITY) 6)0.00000320000 ANALYSIS? NO NO ITERATIONS= 2
模型求解 软件实现 LINDO 6.1 50 3 4 2) 1 5 2 6 + + x + x x x 2 2 480 3) 4( ) 2( ) 5 6 1 5 2 6 + + + + + x x x x x x OBJECTIVE FUNCTIONVALUE 1) 3460.800 VARIABLE VALUE REDUCEDCOST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUALPRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO.ITERATIONS= 2 2) 4 3 3 600 x1 + x2 + 4x5 + x6 3) 4 2 6 4 480 x1 + x2 + x5 + x6 DO RANGE (SENSITIVITY) ANALYSIS? No
OBJECTI 1)3460800 结果解释 VARIABLE REDUCED COST XI 0.00000 1.680000 每天销售168千克A2 X2168.000000 和19.2千克B1 X319.200001 0.000000 利润3460.8(元) X4 0.00000 0.000000 X524.000 0.000000 8桶牛奶加工成A1,42桶 X6 1.520000 牛奶加工成A2, ROW SLACK OR SURPLUS DUAL PRICES 2)0.00000 3.160000 将得到的24千克A全部 3) 0.000000 3.260000 加工成B1 4)76.00000 0.000000 5)0.000044000 60.0000032.0000 除加工能力外均 NO. ITERATIONS 为紧约束
OBJECTIVE FUNCTIONVALUE 1) 3460.800 VARIABLE VALUE REDUCEDCOST X1 0.000000 1.680000 X2 168.000000 0.000000 X3 19.200001 0.000000 X4 0.000000 0.000000 X5 24.000000 0.000000 X6 0.000000 1.520000 ROW SLACK OR SURPLUS DUALPRICES 2) 0.000000 3.160000 3) 0.000000 3.260000 4) 76.000000 0.000000 5) 0.000000 44.000000 6) 0.000000 32.000000 NO.ITERATIONS= 2 结果解释 每天销售168 千克A2 和19.2 千克B1， 利润3460.8（元） 8桶牛奶加工成A1，42桶 牛奶加工成A2， 将得到的24千克A1全部 加工成B1 除加工能力外均 为紧约束
例3自来水输送 水库供水量千吨 A:50 甲:30; B:60 乙:70; 丙:10;20 小区基本用水量千吨 C:50 (以天计) 丁:10;40 收入:900元/千吨元/千吨甲乙丙丁 支出引水管理费 160130220170 140130190150 其他费用:450元/千吨 ABC 190200230/ 应如何分配水库供水量,公司才能获利最多? 若水库供水量都提高一倍,公司利润可增加到多少?
其他费用:450元/千吨 • 应如何分配水库供水量，公司才能获利最多？ • 若水库供水量都提高一倍，公司利润可增加到多少？ 元/千吨 甲 乙 丙 丁 A 160 130 220 170 B 140 130 190 150 C 190 200 230 / 引水管理费 例3 自来水输送 收入：900元/千吨 支出 A：50 B：60 C：50 甲：30；50 乙：70；70 丙：10；20 丁：10；40 水 库 供 水 量 ( 千 吨 ) 小 区 基 本 用 水 量 ( 千 吨 ) 小 区 额 外 用 水 量 ( 千 （以天计） 吨 )