解先作出这问题的产销平衡表和单位运价 表,见表3-3,表3-4 表3-3单位运价表 销地|B1B2|B3|B 加工 A1 192|8 41015
解 先作出这问题的产销平衡表和单位运价 表，见表3-3，表3-4 销 地 加工厂 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5 表3-3 单位运价表
表3-4产销平衡表 销地|B1|B2|B3B 加工厂 量 749 A 销量3656
表3-4 产销平衡表 销 地 加工厂 B1 B2 B3 B4 产 量 A1 A2 A3 7 4 9 销量 3 6 5 6
2.1确定初始基可行解 这与一般线性规划问题不同 产销平衡的运输问题总是存在可行解。因有 ∑4=∑b,=d 必存在x;≥0,i=1,…,m,j=1,…,n 这就是可行解。又因0≤x;≤min(a;,b,) 故运输问题必存在最优解
2.1 确定初始基可行解 这与一般线性规划问题不同。 产销平衡的运输问题总是存在可行解。因有 = = = = m i n j ai bj d 1 1 必存在xij≥0，i=1， … ，m，j=1， … ，n 这就是可行解。又因0≤xij≤min(aj，bj ) 故运输问题必存在最优解
确定初始基可行解的方法很多,有西北角法,最小元 素法和伏格尔( Vogel)法。一般希望的方法是既简便,又 尽可能接近最优解。下面介绍两种方法: 1.最小元素法 这方法的基本思想是就近供应,即从单位运价表中最小的 运价开始确定供销关系,然后次小。一直到给出初始基可 行解为止。以例1进行讨论。 第一步:从表3-3中找出最小运价为1,这表示先将A的产 品供应给B1。因a2>b,A2除满足B1的全部需要外,还可多 余1吨产品。在表3-4的(A2,B1)的交叉格处填上3。得表3 5。并将表3-3的B列运价划去。得表3-6
确定初始基可行解的方法很多，有西北角法，最小元 素法和伏格尔(Vogel)法。一般希望的方法是既简便，又 尽可能接近最优解。下面介绍两种方法： • 1. 最小元素法 这方法的基本思想是就近供应，即从单位运价表中最小的 运价开始确定供销关系，然后次小。一直到给出初始基可 行解为止。以例1进行讨论。 第一步：从表3-3中找出最小运价为1，这表示先将A2的产 品供应给B1。因a2＞b1，A2除满足B1的全部需要外，还可多 余1吨产品。在表3-4的(A2，B1 )的交叉格处填上3。得表3- 5。并将表3-3的B1列运价划去。得表3-6
表3-5.表3-6 销地|B1B2|B3B 加工 量 AAA 749 销量3656 销地B2B3B 加工 11 AAA 10 928 t4105
表 3-5 .表3-6 销 地 加工厂 B1 B2 B3 B4 产 量 A1 A2 A3 3 7 4 9 销量 3 6 5 6 销 地 加工厂 B1 B2 B3 B4 A1 A2 A3 3 1 7 11 9 4 3 2 10 10 8 5