目标规划整数规划第三、四、五章.ppt

1第三章运输问题第四章目标规划第五章整数规划41252**********求运费最小的运输方案。一、引例某部门三个工厂生产同一产品的产量、四个销售点的销量及单位运价如下表:A1B1B216cijA21012148求最小运费的运输方案??运输问题图示:产地销地B3B4A32214共产48共销48minZ=4x11+12x12+4x13+11x14+2x21+10x22+3x23+9x24+8x31+5x32+11x33+6x34x11+x12+x13+x14=16x21+x22+x23+x24=10x31+x32+x33+x34=22x11+x21+x31=8x12+x22+x32=14x13+x23+x33=12x14+x24+x34=14xij0i=1,2,3j=1,2,3,4xij0其中,x11x12x13x14x21x22x23x24x31x32x33x3411111111111111**********个4个t1t2t3t4t5t6t77个条件线性相关任6个线性无关基变量6个系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0、1。(2)元素xij对应于每一个变量在前3个约束方程中(第i个方程中)出现1次,在后四个约束方程中(第3+j个方程中)也出现1次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。(5)运输问题基变量的个数:6个A1AmB1B2Bna1……cijA2a2ambnb2b1……求最小运费的运输方案??:产地销地销地产地B1B2…Bn产量A1x11x12…x1na1A2x21x22…x2na2………………Amxm1xm2…xmnam销量b1b2…bnc11c12cm1c21c22c2nc1ncmncm2i=1,2,…,mj=1,2,…,nxij0典型运输问题的数学模型:x11x12…x1nx21x22…x2n…xm1xm2…xmn11…111…1………………………………11…11…111…1………………………………11…1mnm*n三、运输问题数学模型的特点:运输问题一定有最优解;运输问题约束条件的系数矩阵的特点:(1)约束条件的系数矩阵的元素只有两个:0、1。(2)元素xij对应于每一个变量在前m个约束方程中(第i个方程中)出现一次,在后n个约束方程中(第m+j个方程中)也出现一次。(3)产销平衡问题为等式约束。(4)产销平衡问题中各产地产量之和与各销售地点的销量之和相等。:m+n-1个