光明市的菜篮子工程

2012高教社杯全国大学生数学建模竞赛

承 诺 书

我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.

我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。

我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。

我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。

我们参赛选择的题号是（从A/B/C/D中选择一项填写）： A 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 指导教师或指导教师组负责人 (打印并签名)：

日期： 2012年 8 月 21 日

赛区评阅编号（由赛区组委会评阅前进行编号）：

2012高教社杯全国大学生数学建模竞赛

编 号 专 用 页

赛区评阅编号（由赛区组委会评阅前进行编号）：

全国统一编号（由赛区组委会送交全国前编号）：

全国评阅编号（由全国组委会评阅前进行编号）：

光明市的菜篮子工程

摘要

本文研究的是蔬菜市场为满足不同条件的最优调配方案问题，用了Froyd算法、线性规划建立了一系列数学规划模型，并用MATLAB和LINGO软件编程实现。

关于问题一：用Froyd算法结合MATLAB编程求出收购点至个菜市场的最短距离，以用于蔬菜调运及预期的短缺损失为最小为目标建立线性规划模型。用LINGO编程求得日均费用最少为4610元。

关于问题二：在模型一的基础增加各菜市场短缺量一律不超过需求量的20%的约束条件，用LINGO编程求得最少日均费用以及最优供应方案。费用最少为4806元，供应方安见正文。

关于问题三：在模型一的基础上，改为以供货充足、费用最小为目标，建立模型三，用LINGO编程求得日均费用为4770元，增产的蔬菜每天应分给C收购点8000Kg。

关键字：蔬菜市场调配方案 Froyd算法 线性规划

一 问题的重述

光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①⑧的具体位置见图3.2.按常年情况，A,B,C三个收购点每天收购量分别为200，170和160（单位：100 kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表3.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m).

① 7 ②

8 7 7 B ⑥ 8 5 4 7 11 5

6 10 ⑧ 11

⑦ (a) 为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预期的短缺损失为最小；

(b) 若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案； (c) 为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。

二 符号说明

DAii1,2……8 从A到i（各个菜市场）的最短距离 DBii1,2……8 从B到i（各个菜市场）的最短距离 DCii1,2……8 从C到i（各个菜市场）的最短距离 SAii1,2……8 从A到i（各个菜市场）的运货量 SBii1,2……8 从B到i（各个菜市场）的运货量 SCii1,2……8 从C到i（各个菜市场）的运货量

P 总调运费

Q 短缺损失

R 总费用

三 模型假设

1、假设日需求量与缺货损失费用不变。 2、假设在蔬菜调配的过程中无意外发生。 3、假设新增产的蔬菜能够满足缺货量。

四 模型的建立与求解

4.1问题一

4.1.1问题的分析：

为了使用于蔬菜调运及预期的短缺损失为最小，即调运费用与缺货损失之和最小。首先考虑调运费用P，P为距离与送货量的积，因为与送货距离相关，我们必须先求出A、B、C三个采购点至各个菜市场的最短距离。采用Froyd算法，结合MATLAB编程实现。其次考虑缺货损失Q，以题中要求为约束条件，损失最低位目标建立线性规划模型，用LINGO编程求解。

4.1.2模型的建立与求解：

由图和表格的信息知，建立一个线性规划模型，使得蔬菜调运及预期的短缺损失为最小。

调运总费用P为：

PSAiDAiSBiDBiSCiDCi

i1

i1

i1

888

若使调运总费用最少，则应保证A、B、C三个收购点到8个菜市场的路程最短，最短路线的求解过程如图一：

图一：求解过程图

分析上图可知，该路线为无向网络，就该图而言，网络弧集为：

E=[(v1,v2),(v1,v4),(v1,v5),(v2,v1),(v2,v3),(v2,v5),(v2,v6),(v3,v2),.(v3,v6),(v3,v8),(v3,v9),(v4,v1),(v4,v5).(v4,v7),(v4,v10),(v5,v1),(v5,v2),(v5,v4),(v5,v6),(v5,v7),(v5,v8),(v6,v2),(v6,v3),(v6,v5),

(v6,v8),(v7,v4),(v7,v5),(v7,v8),(v7,v11),(v8,v3),(v8,v5),(v8,v6),(v8,v7),(v8,v9),(v8,v11),(v9,v3),

(v9,v8),(v9,v11),(v9,v13),(v9,v15),(v10,v4),(v10,v11),(v10,v12),(v10,v14),(v11,v7),(v11,v8),(v11,v9)(v11,v10),(v11,v12),(v12,v10),(v12,v11),(v12,v13),(v12,v14),(v13,v9),(v13,v12),(v13,v14),

(v14,v10),(v14,v12),(v14,v13),(v15,v9)] 下面来确定网络权矩阵： W=(wij)其中

nn

wii=lij，当（vi,vj）属于E时，lij为弧（vi,vj）的权 wii=0，i=1,2,3……n

（inf为无穷大，n为网络结点个数） wij=inf,当（vi,vj）不属于E时。按上述规定，该网络的权矩阵为：

0 7 inf 5 4 inf inf inf inf inf inf inf inf inf inf 7 0 7 inf 8 3 inf inf inf inf inf inf inf inf inf inf 7 0 inf inf 6 inf 7 11 inf inf inf inf inf inf 5 inf inf 0 6 inf 5 inf inf 7 inf inf inf inf inf 4 8 inf 6 0 7 4 8 inf inf inf inf inf inf inf inf 3 6 inf 7 0 inf 5 inf inf inf inf inf inf inf inf inf inf 5 4 inf 0 4 inf inf 7 inf inf inf inf inf inf 7 inf 8 5 4 0 6 inf 5 inf inf inf inf inf inf 11 inf inf inf inf 6 0 inf 3 inf 6 inf 5 inf inf inf 7 inf inf inf inf inf 0 6 8 inf 10 inf inf inf inf inf inf inf 7 5 3 6 0 6 inf inf inf inf inf inf inf inf inf inf inf inf 8 6 0 10 5 inf inf inf inf inf inf inf inf inf 6 inf inf 10 0 11 inf inf inf inf inf inf inf inf inf inf 10 inf 5 11 0 inf inf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0

因为上述网络有15个结点，故网络的权矩阵均为15阶矩阵。 现在给出网络最短路线的Froyd算法： （1） d1=w.(w为所给网络的n阶权矩阵) （2） dk=(dkij)nn,k=2,3,…,p.

其中dkij=min[d(k1)is+d(k1)sj,i,j=1,2,…,n. 计算次数的确定：

当wij0时，p由下式确定：

pln(n-1)/ln2，这样的dp就确定了网络各点间的最短距离。此处n=15,解出p3.8074

故只需要取p=4即可，即算到d4即可。按照Froyd算法：d1=d,d2=fld(15,d1),d3=fld(15,d2), d4=(fld(15,d3),算的d4为：

0 7 14 5 4 10 8 12 18 12 15 20 24 22 23

7 0 7 12 8 3 12 8 14 19 13 19 20 24 19

14 7 0 16 13 6 11 7 11 18 12 18 17 23 16

5 12 16 0 6 13 5 9 15 7 12 15 21 17 20

4 8 13 6 0 7 4 8 14 13 11 17 20 22 19

10 3 6 13 7 0 9 5 11 16 10 16 17 21 16

8 12 11 5 4 9 0 4 10 12 7 13 16 18 15

12 8 7 9 8 5 4 0 6 11 5 11 12 16 11

18 14 11 15 14 11 10 6 0 9 3 9 6 14 5

12 19 18 7 13 16 12 11 9 0 6 8 15 10 14

15 13 12 12 11 10 7 5 3 6 0 6 9 11 8

20 19 18 15 17 16 13 11 9 8 6 0 10 5 14

24 20 17 21 20 17 16 12 6 15 9 10 0 11 11

22 24 23 17 22 21 18 16 14 10 11 5 11 0 19

23 19 16 20 19 16 15 11 5 14 8 14 11 19 0

d4即为该网络的距离矩阵，距离矩阵的第i行指明了vi到其他各点的最短距离。根据上述矩阵，分别找出A,B,C到①、②、③、④、⑤、⑥、⑦、⑧的最短距离，见表一：

调运量的限制：

SA1SB1SC175SSS60

B2C2A2

SA3SB3SC380

SA4SB4SC470

SA5SB5SC5100 SA6SB6SC655

SA7SB7SC790SSS80

B8C8A8

短缺损失费为：

Q1075SA1SB1SC1860SA2SB2SC2580SA3SB3SC31070SA4SB4SC410100SA5SB5SC5855SA6SB6SC6590SA7SB7SC7880SA8SB8SC8

总费用为：R

PQ

由以上约束条件，用LINGO 软件进行线性规划求解（源程序及完整运行结果见附录），部分运行结果如下：

Global optimal solution found.

Objective value: 4610.000 Infeasibilities: 0.000000 Total solver iterations: 10

Model Class: LP

Total variables: 26 Nonlinear variables: 0 Integer variables: 0

Total constraints: 22 Nonlinear constraints: 0

Total nonzeros: 124 Nonlinear nonzeros: 0

Variable Value Reduced Cost P 3890.000 0.000000 Q 720.0000 0.000000 SA1 75.00000 0.000000 SA2 0.000000 0.000000

SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 70.00000 0.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000 SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 60.00000 0.000000 SB3 80.00000 0.000000 SB4 30.00000 SB5 0.000000 SB6 0.000000 SB7 0.000000 SB8 0.000000 SC1 0.000000 SC2 0.000000 SC3 0.000000 SC4 0.000000 SC5 30.00000 SC6 0.000000 SC7 90.00000 SC8 40.00000

从上述运行结果中可以得出调运方案为：

0.000000 2.000000 11.00000 14.00000 3.000000 21.00000 16.00000 8.000000 2.000000 0.000000 14.00000 0.000000 0.000000

在此种方案下，蔬菜调运及预期的短缺损失为最小，最小金额为4610元。

4.1.3模型的评价与分析：

本模型用Froyd算法快捷的求出了A、B、C三个收购点到8个菜市场的最短路程，用线性规划模型使得费用最低，并给出了上图所示的调配方案。在所得方案中每日只需4610元。

4.2问题二

4.2.1问题的分析：

若按规定各菜市场短缺量一律不超过需求量的20%，则只需要在模型一的基础上在增加一个约束条件：每个菜市场的供应量必须不低于需求量的80%即可。即得到满足条件的模型二。

4.2.2模型的建立与求解：

各菜市场短缺量一律不超过需求量的20%，为满足这一条件，现对方案一进行调整。只需在方案 一中加一限制条件：

SA1SB1SC1750.860SSS600.848

B2C2A2

SA3SB3SC3800.864

SA4SB4SC4700.856

SA5SB5SC51000.880 SA6SB6SC6550.844

SA7SB7SC7900.872SSS800.864

B8C8A8

同理可用LINGO 编程（源程序及完整运行结果见附录），部分运行结果如下：

Global optimal solution found.

Objective value: 4806.000 Infeasibilities: 0.000000 Total solver iterations: 13

Model Class: LP

Total variables: 26 Nonlinear variables: 0 Integer variables: 0

Total constraints: 30 Nonlinear constraints: 0

Total nonzeros: 148 Nonlinear nonzeros: 0

Variable Value Reduced Cost P 4208.000 0.000000 Q 598.0000 0.000000 SA1 75.00000 0.000000 SA2 10.00000 0.000000 SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 60.00000 0.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000

SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 50.00000 0.000000 SB3 64.00000 0.000000 SB4 56.00000 0.000000 SB5 0.000000 2.000000 SB6 0.000000 11.00000 SB7 0.000000 14.00000 SB8 0.000000 3.000000 SC1 0.000000 21.00000 SC2 0.000000 16.00000 SC3 0.000000 8.000000 SC4 0.000000 2.000000 SC5 24.00000 0.000000 SC6 0.000000 14.00000 SC7 72.00000 0.000000 SC8 64.00000 0.000000

从上述运行结果得知调整后的方案为：

调整后的总损失为：4806元。

4.2.3模型的评价与分析：

在增加了供货量的限制条件后，只需在模型一的基础上再增加约束条件即得到模型二。在本模型下日均花费最低为4806元。新的调配方案如上图所示。

4.3问题三

4.3.1问题的分析：

本题的目标有二：一、要满足每个菜市场的供货量充足；二、要使得总费用最低。所以我们在模型一的基础上增加了上述两个限制条件，即得到模型三。使得在供货量充足的情况下最小化日均费用。

4.3.2模型的建立与求解：

要足城市居民的蔬菜供应，增加蔬菜种植面积，则需要保证所有的菜市场都满足日需求量，在问题一得基础上作出以下调整：

SA1SB1SC175SSS60

B2C2A2

SA3SB3SC380

SA4SB4SC470

SA5SB5SC5100 SA6SB6SC655

SA7SB7SC790SSS80

B8C8A8

同理，用LINGO编程求解(源程序及完整运行结果见附录)，部分运行结果如下:

Global optimal solution found.

Objective value: 4770.000 Infeasibilities: 0.000000 Total solver iterations: 12

Model Class: LP

Total variables: 26 Nonlinear variables: 0 Integer variables:

Total constraints: Nonlinear constraints:

Total nonzeros: Nonlinear nonzeros:

0 22 0 124 0 Variable P Q SA1 SA2 SA3 SA4 SA5 SA6 SA7 SA8 SB1 SB2 SB3 SB4 SB5 SB6 SB7 SB8 SC1 SC2 SC3 SC4 SC5 SC6 SC7 SC8 Value 4770.000 0.000000 75.00000 40.00000 0.000000 0.000000 30.00000 55.00000 0.000000 0.000000 0.000000 20.00000 80.00000 70.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 70.00000 0.000000 90.00000 80.00000 Reduced Cost 0.000000 0.6250000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 12.00000 5.000000 11.00000 0.000000 0.000000 0.000000 2.000000 11.00000 14.00000 3.000000 21.00000 16.00000 8.000000 2.000000 0.000000 14.00000 0.000000 0.000000

从结果中可以的知：

SA1SA2SA5SA6200 SB2SB3SB4170 SC5SC7SC8240

故新增的蔬菜8000Kg全部运向C地，这样既能满足城市居民的蔬菜供应，又能使总损失最小，最小为：4770元。

4.3.3模型的评价与分析：

本模型以供货充足和费用最低为目标，利用题中的约束条件解得：在供货量充足的情况下日均花费最低为4770元。并得到了全新的调配方案如上图所示，而且新增蔬菜8000Kg，且全部运向C地。

五 模型的及评价与改进

5.1模型的评价 5.1.1模型的优点：

模型简单易懂，主要用了Froyd算法与线性规划，使问题的求解变得十分方便，能适应更重新的要求。 5.1.2模型的缺点：

上述模型第三问只考虑了运输费用最小，却没有考虑到供过于求造成的货物积压问题。 5.2模型的改进:

由于上述模型第三问只考虑了运输费用最小，却没有考虑到供过于求造成的货物积压问题。可将存货损失计算进去，这样会使这个模型更加完善。

六 参考文献

[1]姜启源，数学模型，北京，高等教育出版社，2003

[2]黄雍检、赖明勇，MATLAB语言在运筹学中的应用，长沙，湖南大学出版社，2005

七 附件

问题一：

MATLAB新建m文件：

function y=fld(n,x) for r=1:n for i=1:n for j=1:n

p(j)=x(i,j)+x(j,r); end

y(r,i)=min(p); end end

输入命令：

d=[0 7 inf 5 4 inf inf inf inf inf inf inf inf inf inf; 7 0 7 inf 8 3 inf inf inf inf inf inf inf inf inf; inf 7 0 inf inf 6 inf 7 11 inf inf inf inf inf inf; 5 inf inf 0 6 inf 5 inf inf 7 inf inf inf inf inf; 4 8 inf 6 0 7 4 8 inf inf inf inf inf inf inf; inf 3 6 inf 7 0 inf 5 inf inf inf inf inf inf inf; inf inf inf 5 4 inf 0 4 inf inf 7 inf inf inf inf; inf inf 7 inf 8 5 4 0 6 inf 5 inf inf inf inf; inf inf 11 inf inf inf inf 6 0 inf 3 inf 6 inf 5; inf inf inf 7 inf inf inf inf inf 0 6 8 inf 10 inf; inf inf inf inf inf inf 7 5 3 6 0 6 inf inf inf; inf inf inf inf inf inf inf inf inf 8 6 0 10 5 inf; inf inf inf inf inf inf inf inf 6 inf inf 10 0 11 inf; inf inf inf inf inf inf inf inf inf 10 inf 5 11 0 inf; inf inf inf inf inf inf inf inf 5 inf inf inf inf inf 0] d1=d

d2=fld(15,d1) d3=fld(15,d2) d4=fld(15,d3)

运行结果：

d =

Columns 1 through 14

0 7 Inf 5 4 Inf Inf 7 0 7 Inf 8 3 Inf Inf 7 0 Inf Inf 6 Inf 5 Inf Inf 0 6 Inf 5 Inf Inf Inf Inf 7 11 Inf Inf Inf Inf Inf Inf Inf Inf 7 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf

4 8 Inf 6 0 7 4 8 Inf Inf Inf Inf Inf Inf

Inf 3 6 Inf 7 0 Inf 5 Inf Inf Inf Inf Inf Inf Inf Inf Inf 5 4 Inf 0 4 Inf Inf 7 Inf Inf Inf Inf Inf 7 Inf 8 5 4 0 6 Inf 5 Inf Inf Inf

Inf Inf 11 Inf Inf Inf Inf 6 0 Inf 3 Inf 6 Inf Inf Inf Inf 7 Inf Inf Inf Inf Inf 0 6 8 Inf 10 Inf Inf Inf Inf Inf Inf 7 5 3 6 0 6 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 8 6 0 10 5 Inf Inf Inf Inf Inf Inf Inf Inf 6 Inf Inf 10 0 11 Inf Inf Inf Inf Inf Inf Inf Inf Inf 10 Inf 5 11 0 Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf Inf

Column 15

Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf Inf 0 d1 =

Columns 1 through 14

0 7 Inf 5 4 Inf Inf Inf Inf Inf Inf Inf Inf Inf 7 0 7 Inf 8 3 Inf Inf Inf Inf Inf Inf Inf Inf Inf 7 0 Inf Inf 6 Inf 7 11 Inf Inf Inf Inf Inf 5 Inf Inf 0 6 Inf 5 Inf Inf 7 Inf Inf Inf Inf 4 8 Inf 6 0 7 4 8 Inf Inf Inf Inf Inf Inf

Inf 3 6 Inf 7 0 Inf 5 Inf Inf Inf Inf Inf Inf

Inf Inf Inf 5 4 Inf 0 4 Inf Inf 7 Inf Inf Inf Inf Inf 7 Inf 8 5 4 0 6 Inf 5 Inf Inf Inf

Inf Inf 11 Inf Inf Inf Inf 6 0 Inf 3 Inf 6 Inf Inf Inf Inf 7 Inf Inf Inf Inf Inf 0 6 8 Inf 10 Inf Inf Inf Inf Inf Inf 7 5 3 6 0 6 Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf Inf 8 6 0 10 5 Inf Inf Inf Inf Inf Inf Inf Inf 6 Inf Inf 10 0 11 Inf Inf Inf Inf Inf Inf Inf Inf Inf 10 Inf 5 11 0 Inf Inf Inf Inf Inf Inf

Column 15

Inf Inf Inf Inf Inf Inf Inf Inf 5 Inf Inf Inf Inf Inf 0 d2 =

Columns 1 through 14

0 7 14 5 4 Inf

7 0 7 12 8 Inf

14 7 0 Inf 13 Inf

5 12 Inf 0 6 17

4 8 13 6 0 Inf

Inf Inf 10 8 3 12 6 11 13 5 7 4 5 Inf Inf Inf Inf Inf 12 Inf 12 Inf Inf Inf 8 18 Inf Inf Inf Inf 7 11 Inf 12 Inf 17 9 Inf 7 12 15 Inf 8 14 13 11 Inf Inf

10 3 6 13 7 0 9 5 11 Inf 10 Inf Inf Inf

8 12 11 5 4 9 0 4 10 12 7 13 Inf Inf

12 8 7 9 8 5 4 0 6 11 5 11 12 Inf

Inf 18 11 Inf 14 11 10 6 0 9 3 9 6 17

12 Inf Inf 7 13 Inf 12 11 9 0 6 8 18 10

Inf Inf 12 12 11 10 7 5 3 11

Inf Inf Inf 15 Inf Inf 13 11 9 5

Inf Inf 17 Inf Inf Inf Inf 12 6 11

Inf Inf Inf 17 Inf Inf Inf Inf 17 0

Inf Inf 16 Inf Inf Inf Inf 11 5 Inf

Column 15

Inf Inf 16 Inf Inf Inf Inf 11 5 Inf 8 Inf 11 Inf 0 d3 =

Columns 1 through 14

0 7 14 5 4 10 8 12 18 6 0 8 6 18 9 10 11 8 Inf 12 15 6 9 0 10 10 0 5 11 11 Inf 20 24

22

7 0 7 12 8 3 12 8 14 19 13 19 20 29

14 7 0 16 13 6 11 7 11 18 12 18 17 23

5 12 16 0 6 13 5 9 15 7 12 15 21 17

4 8 13 6 0 7 4 8 14 13 11 17 20 22

10 3 21

8 12 18

12 8 16

18 14 14

12 19 10

15 13 11

20 19 5

24 20 11

22 29 0

23 19 19

Column 15

23 19 16 20 19 16 15 11 5 14 8 14

6 13 11 5 7 9 11 15 18 7 12 12 18 15 17 21 23 17 16 20 7 0 4 9 8 5 14 11 13 16 11 10 17 16 20 17 22 21 19 16 9 5 0 4 4 0 10 6 12 11 7 5 13 11 16 12 18 16 15 11 21

11 16 10 12 6 11 0 9 9 0 3 6 9 8 6 15 14 10 5 14 10 16 7 13 5 11 3 9 6 8 0 6 6 0 9 10 11 5 8 14 17 16 12 6 15 9 10 0 11 11

11 19 0 d4 =

Columns 1 through 14

0 7 22

7 0 24

14 7 23

5 12 17

4 8 22

10 3 21

8 12 18

12 8 16

18 14 14

12 19 10

15 13 11

20 19 5

24 20 11

22 24 0

23 19 19

Column 15

23 19

14 5 7 12 0 16 16 0 13 6 6 13 11 5 7 9 11 15 18 7 12 12 18 15 17 21 23 17 16 20 4 10 8 3 13 6 6 13 0 7 7 0 4 9 8 5 14 11 13 16 11 10 17 16 20 17 22 21 19 16 8 12 12 8 11 7 5 9 4 8 9 5 0 4 4 0 10 6 12 11 7 5 13 11 16 12 18 16 15 11 22

12 14 19 11 18 7 14 13 11 16 12 6 11 0 9 9 0 3 6 9 8 6 15 14 10 5 14 20 19 18 15 11 17 16 7 13 5 11 3 9 6 8 0 6 6 0 9 10 11 5 8 14 24 20 17 21 20 17 16 12 6 15 9 10 0 11 11 18 15 13 12 15 12 10 10

16 20 19 16 15 11 5 14 8 14 11 19 0

LINGO程序：

min=P+Q; DA1=4; DA2=8; DA3=8; DA4=19; DA5=11; DA6=6; DA7=22; DA8=20; DB1=14; DB2=7; DB3=7; DB4=16; DB5=12; DB6=16; DB7=23; DB8=17; DC1=20; DC2=19; DC3=11; DC4=14; DC5=6; DC6=15; DC7=5; DC8=10;

SA1+SA2+SA3+SA4+SA5+SA6+SA7+SA8=200; SB1+SB2+SB3+SB4+SB5+SB6+SB7+SB8=170; SC1+SC2+SC3+SC4+SC5+SC6+SC7+SC8=160;

23

p=(SA1*DA1+SA2*DA2+SA3*DA3+SA4*DA4+SA5*DA5+SA6*DA6+SA7*DA7+SA8*DA8)+(SB1*DB1+SB2*DB2+SB3*DB3+SB4*DB4+SB5*DB5+SB6*DB6+SB7*DB7+SB8*DB8)+(SC1*DC1+SC2*DC2+SC3*DC3+SC4*DC4+SC5*DC5+SC6*DC6+SC7*DC7+SC8*DC8);

Q=10*(75-(SA1+SB1+SC1))+8*(60-(SA2+SB2+SC2))+5*(80-(SA3+SB3+SC3))+10*(70-(SA4+SB4+SC4))+10*(100-(SA5+SB5+SC5))+8*(55-(SA6+SB6+SC6))+5*(90-(SA7+SB7+SC7))+8*(80-(SA8+SB8+SC8));

10*(75-(SA1+SB1+SC1))>=0; 8*(60-(SA2+SB2+SC2))>=0; 5*(80-(SA3+SB3+SC3))>=0; 10*(70-(SA4+SB4+SC4))>=0; 10*(100-(SA5+SB5+SC5))>=0; 8*(55-(SA6+SB6+SC6))>=0; 5*(90-(SA7+SB7+SC7))>=0; 8*(80-(SA8+SB8+SC8))>=0; SA1+SB1+SC1

运行结果：

Global optimal solution found.

Objective value: Infeasibilities: Total solver iterations:

Model Class:

Total variables: Nonlinear variables: Integer variables:

Total constraints: Nonlinear constraints:

Total nonzeros: Nonlinear nonzeros:

26 0 0 22 0 124 0 Variable 24

4610.000 0.000000 10 LP Value Reduced Cost

P 3890.000 0.000000 Q 720.0000 0.000000 DA1 4.000000 0.000000 DA2 8.000000 0.000000 DA3 8.000000 0.000000 DA4 19.00000 0.000000 DA5 11.00000 0.000000 DA6 6.000000 0.000000 DA7 22.00000 0.000000 DA8 20.00000 DB1 14.00000 DB2 7.000000 DB3 7.000000 DB4 16.00000 DB5 12.00000 DB6 16.00000 DB7 23.00000 DB8 17.00000 DC1 20.00000 DC2 19.00000 DC3 11.00000 DC4 14.00000 DC5 6.000000 DC6 15.00000 DC7 5.000000 DC8 10.00000 SA1 75.00000 SA2 0.000000 SA3 0.000000 SA4 0.000000 SA5 70.00000 SA6 55.00000 SA7 0.000000 SA8 0.000000 SB1 0.000000 SB2 60.00000 SB3 80.00000 SB4 30.00000 SB5 0.000000 SB6 0.000000 SB7 0.000000 SB8 0.000000 SC1 0.000000 SC2 0.000000 25

0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 12.00000 5.000000 11.00000 0.000000 0.000000 0.000000 2.000000 11.00000 14.00000 3.000000 21.00000 16.00000

SC3 0.000000 8.000000 SC4 0.000000 2.000000 SC5 30.00000 0.000000 SC6 0.000000 14.00000 SC7 90.00000 0.000000 SC8 40.00000 0.000000

Row Slack or Surplus Dual Price 1 4610.000 -1.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000 26 0.000000 27 0.000000 28 0.000000 29 0.000000 30 0.000000 31 0.000000 32 0.000000 33 0.000000 34 400.0000 35 0.000000 36 0.000000 26

-75.00000 0.000000 0.000000 0.000000 -70.00000 -55.00000 0.000000 0.000000 0.000000 -60.00000 -80.00000 -30.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -30.00000 0.000000 -90.00000 -40.00000 -7.000000 -6.000000 -2.000000 -1.000000 -1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

37 0.000000 0.000000 38 320.0000 0.000000 39 0.000000 13.00000 40 0.000000 7.000000 41 0.000000 4.000000 42 40.00000 0.000000 43 0.000000 6.000000 44 0.000000 9.000000 45 0.000000 2.000000 46

问题二： LINGO程序

min=P+Q; DA1=4; DA2=8; DA3=8; DA4=19; DA5=11; DA6=6; DA7=22; DA8=20; DB1=14; DB2=7; DB3=7; DB4=16; DB5=12; DB6=16; DB7=23; DB8=17; DC1=20; DC2=19; DC3=11; DC4=14; DC5=6; DC6=15; DC7=5; DC8=10;

SA1+SA2+SA3+SA4+SA5+SA6+SA7+SA8=200; SB1+SB2+SB3+SB4+SB5+SB6+SB7+SB8=170;

27

40.00000 0.000000

SC1+SC2+SC3+SC4+SC5+SC6+SC7+SC8=160;

p=(SA1*DA1+SA2*DA2+SA3*DA3+SA4*DA4+SA5*DA5+SA6*DA6+SA7*DA7+SA8*DA8)+(SB1*DB1+SB2*DB2+SB3*DB3+SB4*DB4+SB5*DB5+SB6*DB6+SB7*DB7+SB8*DB8)+(SC1*DC1+SC2*DC2+SC3*DC3+SC4*DC4+SC5*DC5+SC6*DC6+SC7*DC7+SC8*DC8);

Q=10*(75-(SA1+SB1+SC1))+8*(60-(SA2+SB2+SC2))+5*(80-(SA3+SB3+SC3))+10*(70-(SA4+SB4+SC4))+10*(100-(SA5+SB5+SC5))+8*(55-(SA6+SB6+SC6))+5*(90-(SA7+SB7+SC7))+8*(80-(SA8+SB8+SC8));

10*(75-(SA1+SB1+SC1))>=0; 8*(60-(SA2+SB2+SC2))>=0; 5*(80-(SA3+SB3+SC3))>=0; 10*(70-(SA4+SB4+SC4))>=0; 10*(100-(SA5+SB5+SC5))>=0; 8*(55-(SA6+SB6+SC6))>=0; 5*(90-(SA7+SB7+SC7))>=0; 8*(80-(SA8+SB8+SC8))>=0; SA1+SB1+SC1=60; SA2+SB2+SC2>=48; SA3+SB3+SC3>=64; SA4+SB4+SC4>=56; SA5+SB5+SC5>=80; SA6+SB6+SC6>=44; SA7+SB7+SC7>=72; SA8+SB8+SC8>=64; end

运行结果：

Global optimal solution found.

Objective value: Infeasibilities: Total solver iterations:

Model Class:

Total variables:

4806.000 0.000000 13 LP 26

28

0 0 30 0 148 0 Variable P Q DA1 DA2 DA3 DA4 DA5 DA6 DA7 DA8 DB1 DB2 DB3 DB4 DB5 DB6 DB7 DB8 DC1 DC2 DC3 DC4 DC5 DC6 DC7 DC8 SA1 SA2 SA3 SA4 SA5 SA6 SA7 SA8 29

Value 4208.000 598.0000 4.000000 8.000000 8.000000 19.00000 11.00000 6.000000 22.00000 20.00000 14.00000 7.000000 7.000000 16.00000 12.00000 16.00000 23.00000 17.00000 20.00000 19.00000 11.00000 14.00000 6.000000 15.00000 5.000000 10.00000 75.00000 10.00000 0.000000 0.000000 60.00000 55.00000 0.000000 0.000000 Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 2.000000 0.000000 0.000000 12.00000 5.000000

Nonlinear variables: Integer variables:

Total constraints: Nonlinear constraints:

Total nonzeros: Nonlinear nonzeros:

SB1 0.000000 11.00000 SB2 50.00000 0.000000 SB3 64.00000 0.000000 SB4 56.00000 0.000000 SB5 0.000000 2.000000 SB6 0.000000 11.00000 SB7 0.000000 14.00000 SB8 0.000000 3.000000 SC1 0.000000 21.00000 SC2 0.000000 SC3 0.000000 SC4 0.000000 SC5 24.00000 SC6 0.000000 SC7 72.00000 SC8 64.00000 Row Slack or Surplus 1 4806.000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 19 0.000000 20 0.000000 21 0.000000 22 0.000000 23 0.000000 24 0.000000 25 0.000000 26 0.000000 30

16.00000 8.000000 2.000000 0.000000 14.00000 0.000000 0.000000 Dual Price -1.000000 -75.00000 -10.00000 0.000000 0.000000 -60.00000 -55.00000 0.000000 0.000000 0.000000 -50.00000 -64.00000 -56.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -24.00000 0.000000 -72.00000 -64.00000 -1.000000

27 0.000000 0.000000 28 0.000000 4.000000 29 0.000000 -1.000000 30 0.000000 -1.000000 31 0.000000 0.000000 32 0.000000 0.000000 33 80.00000 0.000000 34 140.0000 0.000000 35 160.0000 0.000000

问题三：

LINGO程序：

min=P+Q; DA1=4; DA2=8; DA3=8; DA4=19; DA5=11; DA6=6; DA7=22; DA8=20; DB1=14;

36 0.000000 37 90.00000 38 128.0000 39 0.000000 40 0.000000 41 16.00000 42 14.00000 43 16.00000 44 0.000000 45 18.00000 46 16.00000 47 15.00000 48 12.00000 49 0.000000 50 0.000000 51 4.000000 52 11.00000 53 0.000000 54 0.000000 31

0.000000 0.000000 0.000000 7.000000 1.000000 0.000000 0.000000 0.000000 3.000000 0.000000 0.000000 0.000000 0.000000 -2.000000 -6.000000 0.000000 0.000000 -4.000000 -6.000000

DB2=7; DB3=7; DB4=16; DB5=12; DB6=16; DB7=23; DB8=17; DC1=20; DC2=19; DC3=11; DC4=14; DC5=6; DC6=15; DC7=5; DC8=10;

SA1+SA2+SA3+SA4+SA5+SA6+SA7+SA8>=200; SB1+SB2+SB3+SB4+SB5+SB6+SB7+SB8>=170; SC1+SC2+SC3+SC4+SC5+SC6+SC7+SC8>=160;

p=(SA1*DA1+SA2*DA2+SA3*DA3+SA4*DA4+SA5*DA5+SA6*DA6+SA7*DA7+SA8*DA8)+(SB1*DB1+SB2*DB2+SB3*DB3+SB4*DB4+SB5*DB5+SB6*DB6+SB7*DB7+SB8*DB8)+(SC1*DC1+SC2*DC2+SC3*DC3+SC4*DC4+SC5*DC5+SC6*DC6+SC7*DC7+SC8*DC8);

Q=10*(75-(SA1+SB1+SC1))+8*(60-(SA2+SB2+SC2))+5*(80-(SA3+SB3+SC3))+10*(70-(SA4+SB4+SC4))+10*(100-(SA5+SB5+SC5))+8*(55-(SA6+SB6+SC6))+5*(90-(SA7+SB7+SC7))+8*(80-(SA8+SB8+SC8));

10*(75-(SA1+SB1+SC1))>=0; 8*(60-(SA2+SB2+SC2))>=0; 5*(80-(SA3+SB3+SC3))>=0; 10*(70-(SA4+SB4+SC4))>=0; 10*(100-(SA5+SB5+SC5))>=0; 8*(55-(SA6+SB6+SC6))>=0; 5*(90-(SA7+SB7+SC7))>=0; 8*(80-(SA8+SB8+SC8))>=0; SA1+SB1+SC1>=75; SA2+SB2+SC2>=60; SA3+SB3+SC3>=80; SA4+SB4+SC4>=70; SA5+SB5+SC5>=100; SA6+SB6+SC6>=55; SA7+SB7+SC7>=90; SA8+SB8+SC8>=80; end

运行结果：

32

Global optimal solution found.

Objective value: 4770.000 Infeasibilities: 0.000000 Total solver iterations: 12

Model Class: LP

Total variables: 26 Nonlinear variables: 0 Integer variables:

Total constraints: Nonlinear constraints:

Total nonzeros: Nonlinear nonzeros:

0 22 0 124 0 Variable P Q DA1 DA2 DA3 DA4 DA5 DA6 DA7 DA8 DB1 DB2 DB3 DB4 DB5 DB6 DB7 DB8 DC1 DC2 DC3 DC4 DC5 DC6 DC7 DC8 33

Value 4770.000 0.000000 4.000000 8.000000 8.000000 19.00000 11.00000 6.000000 22.00000 20.00000 14.00000 7.000000 7.000000 16.00000 12.00000 16.00000 23.00000 17.00000 20.00000 19.00000 11.00000 14.00000 6.000000 15.00000 5.000000 10.00000 Reduced Cost 0.000000 0.6250000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000

SA1 75.00000 0.000000 SA2 40.00000 0.000000 SA3 0.000000 0.000000 SA4 0.000000 2.000000 SA5 30.00000 0.000000 SA6 55.00000 0.000000 SA7 0.000000 12.00000 SA8 0.000000 5.000000 SB1 0.000000 11.00000 SB2 20.00000 SB3 80.00000 SB4 70.00000 SB5 0.000000 SB6 0.000000 SB7 0.000000 SB8 0.000000 SC1 0.000000 SC2 0.000000 SC3 0.000000 SC4 0.000000 SC5 70.00000 SC6 0.000000 SC7 90.00000 SC8 80.00000 Row Slack or Surplus 1 4770.000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10 0.000000 11 0.000000 12 0.000000 13 0.000000 14 0.000000 15 0.000000 16 0.000000 17 0.000000 18 0.000000 34

0.000000 0.000000 0.000000 2.000000 11.00000 14.00000 3.000000 21.00000 16.00000 8.000000 2.000000 0.000000 14.00000 0.000000 0.000000 Dual Price -1.000000 -75.00000 -40.00000 0.000000 0.000000 -30.00000 -55.00000 0.000000 0.000000 0.000000 -20.00000 -80.00000 -70.00000 0.000000 0.000000 0.000000 0.000000 0.000000

19 0.000000 0.000000 20 0.000000 0.000000 21 0.000000 0.000000 22 0.000000 -70.00000 23 0.000000 0.000000 24 0.000000 -90.00000 25 0.000000 -80.00000 26 0.000000 -5.000000 27 0.000000 -4.000000 28 80.00000 29 0.000000 30 0.000000 31 0.000000 32 0.000000 33 0.000000 34 0.000000 35 0.000000 36 0.000000 37 0.000000 38 0.000000 39 0.000000 40 0.000000 41 0.000000 42 0.000000 43 0.000000 44 0.000000 45 0.000000 46 0.000000

35

0.000000 -1.000000 -0.3750000 -0.4750000 0.000000 0.000000 0.000000 0.000000 -0.2500000 0.000000 0.000000 0.000000 0.000000 -1.125000 -8.250000 -2.250000 0.000000 -3.125000 -7.000000