实用数学方法：线性规划实例

1. 问题的提出—— 自来水输送问题

某市有甲、乙、丙、丁四个居民区，自来水由A、B、C三个水库供应。四个区每天必须得到保证的基本生活用水量（单位：103 t）分别为30、70、10、10。但由于水源紧张，三个水库每天最多只能分别供应自来水50、60、50。由于地理位置的差别，自来水公司从各水库向各区送水所需付出的引水管理费不同（见表1.1.1，其中C水库与丁区之间没有输水管道），其他管理费用（单位：元/103 t）都是450。根据公司规定，各区用户按照统一标准900收费。此外，四个区都向公司申请了额外用水量，分别为每天50、70、20、40。该公司应如何分配供水量，才能获利最多?

为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高1倍，问供水方案应如何改变？公司利润可增加到多少？

表1.1.1　从水库向各区送水的引水管理费用

2. 模型的分析和假设

分配供水量就是安排从三个水库向四个区送水的方案，目标是获利最多。而从题目给出的数据看，A、B、C三个水库的供水总量为160，不超过四个区的基本生活用水量与额外用水量之和300，因而总能全部卖出并获利，于是自来水公司每天的总收入是900(50+60+50)=144 000元，与送水方案无关。同样，公司每天的其他管理费用450(50+600+50)=72 000元，也与送水方案无关。所以，要使利润最大，只需使引水管理费最小即可。另外，送水方案自然要受三个水库的供应量和四个区的需求量的限制。

3. 模型的建立

模型一 很明显，决策变量为A、B、C三个水库（i=1,2,3）分别向甲、乙、丙、丁四个区（j=1,2,3,4）的供水量。设水库i向j区的日供水量为xij。由于C水库与丁区之间没有输水管道，即x3 4=0，因此只有11个决策变量。

由以上分析，问题的目标可以从获利最多转化为引水管理费最少，于是

约束条件有两类：一类是水库的供应量限制，另一类是各区的需求量限制。

由于供水量总能卖出并获利，水库的供应量限制可以表示为

考虑到各区的基本生活用水量与额外用水量，各区的需求量限制可以表示为

模型二 如果A、B、C三个水库每天的最大供水量都提高1倍，则公司总供水能力为320，大于总需求量300，水库供水量不能全部卖出，因而不能像前面那样将获利最多转化为引水管理费最少。此时，我们首先需要计算A、B、C三个水库分别向甲、乙、丙、丁四个区供应每103 t水的净利润，即从收入900元中减去其他管理费450元，再减去表1.1.1中的引水管理费，得表1.1.2。

表1.1.2　从水库向各区送水的引水的净利润

于是，决策目标为

由于水库供水量不能全部卖出，所以上面第一组约束的右端增加1倍的同时，应将“=”改成“≤”，即

第二组约束条件不变。

4. 模型的求解(www.xing528.com)

注意：xij≥0。显然，这是一个线性规划模型。

模型一的MATLAB程序：

clc, clear

c=[160; 130; 220; 170; 140; 130; 190; 150; 190; 200; 230];

A=[1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0; 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0; 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1;0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0];

A=[A; -A];

b1=[80; 140; 30; 50]; b2=[30; 70; 10; 10]; b=[b1; -b2];

Aeq=[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0; 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0; 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1];beq=[50; 60; 50];

[x, fval]=linprog(c, A, b, Aeg, beq, zeros(11, 1))

求得送水方案：A水库向乙区供水50，B水库向乙、丁区分别供水50、10，C水库向甲、丙分别供水40、10。引水管理费为24 400元，总利润为144 000 -72 000 -24 400 =47 600元。

模型二的运水方案：A水库向乙区供水100，B水库向甲、乙、丁区分别供水30、40、50，C水库向甲、丙区分别供水50、30，总利润为88 700元。

5. 结果的分析

由于每个区的供水量都能完全满足，所以上面第二组约束条件中每个式子左侧约束可以去掉，右边的“≤”可以改写成“=”。经这样简化后得到的解没有任何变化。本题考虑的是将某种物质从若干供应点运往一些需求点，在供需量约束条件下使总费用最小或总利润最大。这类问题一般称为运输问题，是线性规划应用最广泛的领域之一。在标准的运输问题中，供需量通常是平衡的，即供应点的总供应量等于需求点的总需求量。本题中供需量不平衡，但这并不会引起本质的区别，同样可以方便地建立线性规划模型求解。

习题1.1

1. 用MATLAB求解下列线性规划问题：

2. 用MATLAB求解下列线性规划问题：

3. 加工一种食用油，需要精炼若干种原料油并把它们混合起来。原料油的来源共两类分五种：植物油VEG1、植物油VEG2、非植物油OIL1、非植物油OIL2、非植物油OIL3。购买每种原料油的价格（英镑/吨）如表1.1.3所示，最终产品以150英镑/吨的价格出售。植物油和非植物油需要在不同的生产线进行加工，每个月能加工植物油不超过200吨，非植物油不超过250吨；假定在加工过程中重量没有损失，而且加工费用不计。最终产品要符合硬度的技术条件。按照硬度计量单位。它必须为3～6。假定硬度的混合是线性的，而原料的硬度如表1.1.4所示。应如何安排采购和生产加工计划，才能使利润最大？

表1.1.3　原料油的价格

表1.1.4　原料油的硬度