飞机运输问题及MATLAB编程

1、运输问题的解决方法一、问题背景：这类问题的典型提法是，为了把某种产品从若干个产地调运到若干个销地， 已知每个产地的供应量和每个销地的需求量，如何在许多可行的调运方案中，确 定一个总运输费或总运输量最少的方案。运输型问题具有上述特点的线性规划问题通常被称为运输型问题。现已发现的运输型问题有以下6类:一般运输问题，又称希契科克运输问题，简称 H 问题。网络运输问题，又称图上运输问题，简称T问题。最大流量问题，简称 F问题。最短路径问题，简称S问题。任务分配问题，又称指派问题，简称A 问题。生产计划问题，又称日程计划问题，简称CPS问题。其中一般运输问题、 任务分配问题和生产计划问题通常都可以用表上

2、作业法求解，而网络运输问题、 最大流量问题和最短路径问题一般可用图上作业法或网络技术求解。对于规模不太大的运输问题可用图上作业法或表上作业法求解。生产、生活物资从若干供应点运送到一些需求点，怎样安排输送方案使运费 最小，或利润最大；各种类型的货物装箱，由于受体积、重量等限制，如何搭配 装载，使获利最高，或装箱数量最少往往都要用到运输问题。二、例题：某架货机有三个货舱：前仓、中仓和后仓。三个货舱所能装载货物的最大重 量和体积都有所限制，如下表所示，并且，为了保持飞机的平衡，三个货舱实际 装载的重量必须与允许最大的重量成比例。表2-1三个货舱最大允许装载的货物的重量和体积前仓中仓后仓重量限制（吨）

3、10168体积限制（米3）680087005300现有四类货物供该货机本次飞行装运，其有关信息如表2-2，最后一列指装运后所获得的利润。表2-2四类装运货物的信息重量（吨）空间（米3/吨）利润（元/吨）货物1184803100货物2156503800货物3235803500货物4123902850应如何安排装运，使该货机本次飞行获利润最大 ？ 模型假设：问题中没有对货物装运提出其它要求，我们可作如下假设：1）每种货物可以分割到任意小；2）每种货物可以在一个或多个货舱中任意分布；3）多种货物可以混装，并保证不留空隙。模型建立：决策变量：用Xjj表示第i种货物装入第j个货舱的重量（吨），货舱j =

4、 l, 2 ,3分别 表示前仓、中仓、后仓.决策目标是最大化总利润，即Max Z = 3100（X11 + X12 + X13）+ 3800（X21 + X22 + X23）+3500（X31 + X32 +X33）+2850（X41+X42+X43）（1）约束条件包括以下4个方面：1）供装载的四种货物的总重量约束，即X11 + X12 + X13 18(2)X21 + X22 + X23 15(3)X31 + X32 + X33 23 (4)X41 + X42 + X43 12 (5)2) 三个货舱的重量限制，即X11 + X21 + X31 + X41 10(6)X12 + X22 + X

5、32 + X42 16 (7)X13+ X23 + X33 + X43 8(8)3) 三个货舱的空间限制，即480X11 +650X21+580X3计 390X41 6800(9)480X12+ 650X22+ 580X32+ 390X42 ' 8700(10)480X13+ 650X23+ 580X33+ 390X43 5300 (11)4) 三个货舱装入重量的平衡约束，即5) X11X43这12个变量都为非负数才有实际意义，即X11 X43>013)将(1)至(13)组合就得到了本次问题的的标准线性规划模型。三、模型求解：3.1说明：线性规划为min fval = f *x(

6、输入时f为行向量或列向量都行)s.t A*x : b, Aeq*x = beq, lb： x :ub设置linprog(f, A, b, Aeq, beq, lb, ub)中参数时，若后面全空缺可不写，中间有空缺时用代替，如 linprog(f, A, b, , ,lb), linprog(f, A, b)等.3.2matlab 程序：f=-3100 3100 3100 3800 3800 3800 3500 3500 3500 2850 2850 2850; ?Aeq=8 -5 0 8 -5 0 8 -5 0 8 -5 0;8 0 -10 8 0 -10 8 0 -10 8 0 -10;be

7、q=0 0;A=1 1 1 0 0 0 0 0 0 0 0 0;?0 0 0 1 1 1 0 0 0 0 0 0;?0 0 0 0 0 0 1 1 1 0 0 0;?0 0 0 0 0 0 0 0 0 1 1 1;1 0 0 1 0 0 1 0 0 1 0 0;0 1 0 0 1 0 0 1 0 0 1 0;0 0 1 0 0 1 0 0 1 0 0 1;480 0 0 650 0 0 580 0 0 390 0 0;0 480 0 0 650 0 0 580 0 0 390 0;0 0 480 0 0 650 0 0 580 0 0 390;b=18 15 23 12 10 16 8 680

8、0 8700 5300; lb=zeros(12,1);x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb)3.3 运行结果：运行后，要知道结果，则Optimization terminated.x =0.00000.00000.00008.62270.00006.37731.377312.94741.62270.00003.0526 0.0000fval =-1.2152e+005exitflag =1output =iterations: 8algorithm: 'large-scale: interior point

9、9;cgiterations: 0message: 'Optimization terminated.'lambda =ineqlin: 10x1 doubleeqlin: 2x1 doubleupper: 12x1 doublelower: 12x1 double实际上，不妨将所得最优解作四舍五入，结果为货物 2装入前仓 9 吨、装 入后仓 6 吨；货物 3 装入前仓 1 吨、装入中仓 13 吨、装入后仓 2 吨; 货物 4 装 入中仓 3 吨。最大利润约 121500 元.四、评注4.1 本例在解题决时，为了简化问题引用了很多假设。但在实际问题中， 往往这些假设只是理想状态，具体情况还需具体分析。