ycx1线性规划.pptVIP

第二阶段： 将第一阶段求出的最优解，作为第二阶段的初始基本可行解，然后在原问题的目标函数下进行优化，以决定原问题的最优解。 X*=(4,1,9,0,0);Z(X*)=-2 ≤0 [ ] 两阶段法计算步骤 1.6运输问题 LP 1．6．1运输问题的数学模型 运输问题的一般描述： 设某种物资有m个产地 A1 A2,…,Am , 其产量分别为 a1 a2,…,am , 另外有n个销地 B1 B2,…,Bn , 其销量分别为 b1 b2,…,bn , 已知从Ai到Bj的单位运费为Cij(i=1,2,…,m;j=1,2,…,n)， 试问应如何组织调运才能使总运费最低。 运 输：指物资产品借助运力在空间和时间上所发生的位移。 运输问题：是研究如何制定合理的调运方案，把物资从若干 个生产基地，分别运送到需要这些产品的地区，使总 运价最低。 设：从Ai到Bj的运输量为xij 运输问题的产销平衡表如下 A1 A2 ... B1 B2 ... Bn C11 C12 ... C1n ... ... ... ... 销量 产量 产地 销地 Am C21 C22 ... C2n Cm1 Cm2 ... Cmn b1 b2 ... bn a1 a2 ... am x21 x22 ... x2n x11 x12 ... x1n xm1 xm2 ... xmn ... ... ... ... LP x11+ x12+…+ x1n x11+ x21+…+ xm1 …………………….. xm1+ xm2+…+ xmn x1j+ x2j+…+ xmj x1n+ x2n+…+ xmn = a1 = am = b1 = bj = bn A1 A2 Am B1 B2 ... Bn 销量 产量 产地 销地 a1 a2 am b1 b2 ... bn ... ... c11 c12 ... c1n c21 c22 ... c2n ... ... ... ... cm1 cm2 ... cmn x21 x22 ... x2n ... ... ... ... xm1 xm2 ... xmn x11 x12 ... x1n xi1+ xi2+…+ xin = ai …………………... …………………….. …………………... 1．6．1．1产销平衡问题（ ）模型 ? ? = = = m i n j j i b a 1 1 x11+ x12+…+ x1n= a1 xi1+ xi2+…+ xin= ai xm1+ xm2+…+ xmn= am x11+ x21+…+ xm1= b1 x1j+ x2j+…+ xmj= bj x1n+ x2n+…+ xmn= bn m Σxij = bj i=1 n Σ xij = ai j=1 xij ≥0 (i=1,2,…,m;j=1,2,…,n) (i=1,2,…,m) (m个） (j=1,2,…,n) （n个) m Σcijxij i=1 n Σ j=1 Z= Min LP 模型特点： （1）由平衡条件易知：m+n个方程线性相关，而任意m+n –1个方程线性无关。 （2）基变量的个数为m+n –1，非基变量的个数为mn-（m+n–1）=（m–1）（n –1）≥1，有无限多方案。 （3）系数矩阵只包括1和0 m Σxij =bj i=1 n Σ xij = ai j=1 xij ≥0 (i=1,2,…,m;j=1,2,…,n) (i=1,2,…,m) (m个） (j=1,2,…,n) （n个) m Σcijxij i=1 n Σ j=1 Z= Min LP LP 1．6．1．2产销不平衡问题 最小元素法： 列出运输表，表中xij位置暂先空着，在表中找出单位运价最小者Ckt，取 xkt=min{ ak bt} 把xkt的值填在相应的格内(若有几个单位运价同时达到最小，就任取其中之一）。 （供大于求） （供不应求） （1） （2） 最小元素法 元素差额法 1．6．2表上作业法（运输单纯形） （1）确定初始基本可行解（初始方案） * LP 如果 akbt 划去第t列，第k行的产量调整为ak-bt； A1 A2 A3 B1 B2 B3 B4 6 4 12 6 2 7 7 4 8 8 4 9 5 6 3 3 11 4 2 销量 产量 产地 销地 7 5 1 2 2 5 如果 akbt 划去第k行，第t列的销量调整为bt-ak； 如果 ak=bt划