(4.1.1)--04_1运输问题及其数学模型.pdf

《(4.1.1)--04_1运输问题及其数学模型.pdf》由会员分享，可在线阅读，更多相关《(4.1.1)--04_1运输问题及其数学模型.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、引例某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示：问：应如何调运，使得总运输费最小？设xij表示从产地Ai调运到Bj的运输量(i1,2；j1,2,3)，现将安排的运输量列表如下：使运输费最小的目标函数为：minz6 x11+4 x12+6x13+6x21+5x22+5x23满足产地产量的约束条件为：x11+x12+x13=200 x21+x22+x23=300 xij0满足销地销量的约束条件为：x11+x21150 x12+x22150 x13+x23200运输问题及其模型 有m个产地生产某种物资，有n个地

2、区需要该类物资 令a1,a2,am表示各产地产量，b1,b2,bn表示各销地的销量，ai=bj称为产销平衡 设xij表示产地 i 运往销地 j 的物资量，cij表示对应的单位运费，则我们有运输问题的数学模型如下：运输问题有mn个决策变量，m+n个约束条件。其矩阵形式为C=(c11，c12，c1n，c21，c22，c2n，cm1，cm2，cmn)b=（a1，a2，am，b1，b2，,bn)TX=(x11，x12，x1n，x21，x22，x2n，xm1，xm2，xmn)Txij的系数向量Pij的分量除第i个和第m+j个为1外，其余都为0。Pij=(0，1，0，1，0)T=ei+em+j由于产销平衡条件最多只有m+n1个相互独立，因此，运输问题的基变量最多只有m+n1 个对于m，n2，有m+nmn，R(A)m+n注意到在A中去掉第1行而取出第2，第3，第m+n行，又取出与所对应的列，则由这些取出的行和列的交叉处的元素构成的一个m+n-1级子式D 所以r(A)=m+n-1由此可知，运输问题的任何一组基都由m+n-1个变量组成。