Knowledge

QiShunwang

知识分享

线性规划——产销平衡

2021/4/26 17:18:49    来源:

运输问题(产销平衡)

  某商品有m 个产地、n 个销地,各产地的产量分别为a1,a2,...am ,各销地的 需求量分别为b,..bn , , 1 L 。若该商品由i 产地运到 j 销地的单位运价为 cij ,问应该如何调 运才能使总运费最省?

  解:引入变量 xij ,其取值为由i 产地运往 j 销地的该商品数量,数学模型为

在这里插入图片描述

显然是一个线性规划问题,当然可以用单纯形法求解。

  对产销平衡的运输问题,由于有以下关系式存在:

在这里插入图片描述

其约束条件的系数矩阵相当特殊,可用比较简单的计算方法,习惯上称为表上作业法(由 康托洛维奇和希奇柯克两人独立地提出,简称康—希表上作业法)

例题:

  某公司有三个加工厂A1,A2.A3生产某产品,每日的产量分别为:7吨、4吨、9吨;该公司把这些产品分别运往四个销售点B1,B2、B3、B4,各销售点每日销量分别为:3吨、6吨、5吨、6吨;从各工厂到各销售点的单位产品运价如表4-1所示。问该公司应如何调运这些产品,在满足各销售点的需要量的前提下,使总运费最少?

解析: 典型的产销平衡问题,将已知数据做成表格如下:

在这里插入图片描述

  将所有数据列成表格会更加清晰,根据题意可以得到目标函数的表达式如下:

在这里插入图片描述

  然后将已知约束关系整理如下:

在这里插入图片描述

  可见题目中并没有不等式约束关系,同时也没有约束上界ub。

Matlab 程序实现

clc;clear				%清空数据防止干扰
f=[3;11;3;10;1;9;2;8;7;4;10;5];	%价值向量
aeq=[ones(1,4),zeros(1,8);		%线性等式约束	构造矩阵
    zeros(1,4),ones(1,4),zeros(1,4);
    zeros(1,8),ones(1,4);
    1,zeros(1,3),1,zeros(1,3),1,zeros(1,3);
    0,1,zeros(1,2), 0,1,zeros(1,2), 0,1,zeros(1,2);
    zeros(1,2),1,0, zeros(1,2),1,0, zeros(1,2),1,0;
    zeros(1,3),1,zeros(1,3),1,zeros(1,3),1];
beq=[7;4;9;3;6;5;6];			%线性等式约束
[x,y]=linprog(f,[],[],aeq,beq,zeros(12,1))	%求解

题目答案:

x=[0;0;5;2;3;0;0;1;0;6;0;3]
y=85

文章引用:http://www.qishunwang.net/knowledge_show_80535.aspx