线性规划模型(LP) max 3x,+5x2+4* st 2x1+3x,≤1500 2r,+4x,<800 3r,+2x,+5x,<2000 x,≥0 192,3 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 6 max 3 1 5 2 4 3 x + x + x s.t.2x1 + 3x2 1500 2x2 + 4x3 800 3x1 + 2x2 + 5x3 2000 x1 , x2 , x3 0 线性规划模型(LP)
计算结果 OBJECTIVE FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST XI 375000000 0.000000 250.000000 0.000000 75000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 0.000000 1.050000 0.000000 0.625000 0.000000 0.300000 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 7 OBJECTIVE FUNCTION VALUE 2675.000 VARIABLE VALUE REDUCED COST X1 375.000000 0.000000 X2 250.000000 0.000000 X3 75.000000 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 1) 0.000000 1.050000 2) 0.000000 0.625000 3) 0.000000 0.300000 计算结果
运输问题( Hitchcock问题) 实例:(1)一个制造厂要把若干单位的同一种产品从 两个仓库A;i=1,2发送到零售点B;j=1,2,3,4。 (2仓库A能供应的产品数量为4;=12,零售点B 所需要的产品的数量为b=12,34。 (假设总供和总需求量b 相等,且已知 从仓库A运一个单位产品往B的运价为C。 询问:应如何组织运输才能使总运费最小? 2021/1/27 山东大学软件学院 8
2021/1/27 山东大学 软件学院 8 实 例：(1)一个制造厂要把若干单位的同一种产品从 两个仓库 Ai ;i = 1,2发送到零售点 Bj ; j = 1,2,3,4 。 (2)仓库 Ai 能供应的产品数量为 ai ;i =1,2 ，零售点 Bj 所需要的产品的数量为bj ; j =1,2,3,4。 (3)假设总供给量= 2 i 1 ai 和总需求量= 4 j 1 bj 相等，且已知 从仓库 Ai 运一个单位产品往 Bj 的运价为 ij c 。 询问：应如何组织运输才能使总运费最小？ 运输问题（Hitchcock问题）
问题分析 可控因素:从仓库4运往B的产品数量设为x,1≤i≤2, 1≤j≤4 目标:总运费最小。费用函数 ∑∑Cx i=l j=l 约束条件:从每个仓库运出总量不超过其可用总量, 运入每个零售点的数量不低于其需求量。 由于总供给量等于总需求量,所以都是等号。即 x;+x2+xa3+x;4=1;i=1,2 x1+x2=b;j=1,2,3,4 蕴含约束:数量非负x≥0;i=12,=1,2,3,4 2021/1/27 山东大学软件学院
2021/1/27 山东大学 软件学院 9 可控因素：从仓库 Ai 运往 Bj 的产品数量设为 xij, 1 i 2, 1 j 4。 目标：总运费最小。费用函数= = 2 1 4 i j 1 ij xij c 约束条件：从每个仓库运出总量不超过其可用总量， 运入每个零售点的数量不低于其需求量。 由于总供给量等于总需求量，所以都是等号。即 xi1 + xi2 + xi3 + xi4 = ai ;i = 1,2 x1 j + x2 j = bj ; j = 1,2,3,4 蕴含约束：数量非负 xi j 0;i = 1,2, j = 1,2,3,4 问题分析
运输问题的LP mm∑∑cx S t x1+x2+x3+x4=a1,i=1,2 + b 1.2.3.4 i=1,2,j=1,2,3,4 说明:当变量为整数变量、a;和b,都等于1时,运输 问题即变为二分图上的最小权重匹配问题,称为 Assignment(指派)问题。 可证明,最小权重匹配问题和最大权重匹配问题是 等价的。 2021/1/27 山东大学软件学院 10
2021/1/27 山东大学 软件学院 10 0, =1,2, =1,2,3,4 + = , =1,2,3,4 s.t. + + + = , =1,2 min 1 2 1 2 3 4 2 =1 4 =1 x i j x x b j x x x x a i c x i j j j j i i i i i i j i j i j ≥ ∑∑ 运输问题的LP 说明：当变量为整数变量、ai 和 bj 都等于1时，运输 问题即变为二分图上的最小权重匹配问题，称为 Assignment（指派）问题。 可证明，最小权重匹配问题和最大权重匹配问题是 等价的