Lingo与线性规划文档格式.docx

Lingo与线性规划文档格式.docx

《Lingo与线性规划文档格式.docx》由会员分享，可在线阅读，更多相关《Lingo与线性规划文档格式.docx（20页珍藏版）》请在冰点文库上搜索。

@bnd（a,变量名,b）；

限制该变量介于a,b之间.

@free（变量名）；

允许该变量为负数.

@gin（变量名）；

限制该变量为整数.

例1求目标函数

的最小值，约束条件为

输入Lingo程序：

min=2*x1+3*x2;

x1+x2>

=350;

x1>

=100;

2*x1+x2<

=600;

有两种运行方式：

1、点击工具条上的按钮即可。

2、点击菜单：

LINGO→Solve

运行结果如下：

下面对其各个部分进行说明：

Globaloptimalsolutionfound：

表示已找到全局最优解。

Objectivevalue：

表示最优值的大小。

可见本题函数最小值

800。

Infeasibilities：

矛盾约束的数目。

Totalsolveriterations:

迭代次数。

Variable：

变量。

本题有两个变量。

Value：

变量对应的最优解，即

。

ReducedCost：

变量

在最优解的基础上增加一个单位，目标函数值的改变量。

例如，一个变量的ReducedCost值为8，那么当该变量增加一个单位，在最大化（最小化）问题中目标函数值将减少（增大）8个单位。

SlackorSurplus：

表示接近等于的程度，即约束离相等还差多少。

在约束条件是<

=中，表示松弛程度，在约束条件是>

=中，不是过剩程度。

如果约束条件是=，则SlackorSurplus为0，该约束是个紧约束（或有效约束）。

如果一个约束是矛盾的，即模型无可行解则Slackorsurplus的值是负数。

知道SlackorSurplus的值，可以帮助我们发现优化模型中错误的约束条件。

在上例中第2和第4行松弛变量均为0,说明对于最优解来讲,两个约束（第2和4行）均取等号,即都是紧约束，第3行为150，即最优解使得第3行过剩150.

DualPrice：

对偶价格的值，它表示约束条件中的常数，每增加一个单位，目标函数值改变的数量（在最大化问题中目标函数值是增加，在最小化问题中目标函数值是减少）。

比如，在上一个Min模型中第四行的1，表示2*x1+x2<

=600增加一个单位到2*x1+x2<

=601，可以使目标值增加-1（因为第一行是目标函数的DualPrice是-1），即Objectivevalue=799;

如果增加-1个单位到599会使目标值增加到801。

例2求目标函数

min=4*x1^2-x2^2+2*x3^2+12;

3*x1+2*x2+x3=9;

x1+x2+x3=-1;

@free（x1）;

@free（x2）;

@free（x3）;

运行结果：

即当

时，

二、灵敏度分析

灵敏度分析是指：

找出模型变量系数的一个变化范围，使得最优基（即最优解）保持不变。

一般只对线性规划模型做灵敏度分析。

1、灵敏度分析操作步骤

第一步：

菜单lingo-->

options-->

generalsolver-->

dualcomputations:

prices&

ranges-->

ok.

第二步：

range

2、灵敏度报告中常见的词汇

Currentcoefficient：

当前目标函数系数

Allowableincrease：

允许增加量

Allowabledecrease：

允许减少量

CurrentRHS：

当前右边常数项

INFINITY：

表示正无穷。

例1求解下列模型：

max=72*x1+64*x2;

x1+x2<

=50;

12*x1+8*x2<

=480;

3*x1<

并做灵敏度分析。

求解报告：

灵敏度分析报告：

灵敏度分析报告的解读：

x1的系数变化范围是（72-8，72+24）=（64，96）；

x2的系数变化范围是（64-16，64+8）=（48，72）。

注意：

x1系数的允许范围需要x2系数64不变，反之亦然。

由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。

右边常数项中，第2行原来为50，当它在[50-6.67，50+10]=[43.33，60]范围变化时，最优基保持不变。

第3行可以类似解释。

对第4行，原来为100，当它在[100-40，100+∞]=[60，+∞]范围变化时，最优基保持不变。

不过由于此时约束发生变化，最优基即使不变，最优解、最优值也会发生变化。

三、数据输入

对于大型的优化问题，即自变量比较多的时候，还像上两节那样输入目标函数和约束条件就比较麻烦了。

一般输入数据的方法有两种：

一、建立向量、矩阵输入；

二、调用外部数据。

这里仅介绍第一种方法。

1、建立向量

命令格式：

集合名称/集合维数/：

向量名称

例如：

sets：

set1/1..9/:

x;

set2/1..5/:

a,b;

endsets

表示建立了两类集合。

第一类集合set1，维数为9，x和y是向量名。

向量x=（x

（1）,…,x（9））,其中x（i）是x的元素。

第二类集合set2，维数为5，a和b都是向量名。

向量a=（a

（1）,…,a（5））,其中a（i）是a的元素。

向量b=（b

（1）,…,b（5））,其中b（i）是b的元素。

2、建立矩阵

集合名称（集合1，集合2）/：

矩阵名称

set1/1..3/:

set2/1..4/:

a;

link（set1,set2）:

A;

表示建立了一个矩阵类link，其矩阵的阶数为

，A是具体的矩阵名。

有两个命令是比较常见的：

求和语句:

@sum（集合名（i）:

含集合名（i）的语句）;

循环语句:

@for（集合名（i）:

循环的语句）;

例3：

求目标函数

model:

sets:

set1/1..2/:

c,x;

set2/1..3/:

b;

link（set2,set1）:

max=@sum（set1（i）:

c（i）*x（i））;

@for（set2（i）:

@sum（link（i,j）:

A（i,j）*x（j））<

=b（i））;

data:

c=1115;

A=2030

3025

3025;

b=3602000300;

enddata

end

运行结果报告：

例4、某地区有三个蔬菜生产基地，估计每年可供应本地区的蔬菜量表为：

生产基地

A

B

C

蔬菜生产量（吨）

7

8

3

有四个地市需要该类蔬菜，需求表为：

地区

甲

乙

丙

丁

6

如果从各蔬菜生产基地到各地市的每吨蔬菜的运价表（单位：

万元/吨）为:

地市

5

9

4

10

2

为了降低运输费，需要合理调拨资源.

（1）根据以上资料表制订一个使总的运费为最少的蔬菜调拨方案．

（2）如果有机会增加生产基地的产量1吨，问应当优先增加那个基地的产量？

（3）如果将A到乙市的运价减少为5万元/吨，问这会影响最优的调拨方案吗？

设

：

第i个蔬菜生产基地，

，分别对应生产基地A，B，C；

第i个蔬菜需求地，

，分别对应蔬菜需求地市甲、乙、丙、丁；

总运输费用；

表示的是从第i个生产基地向第j个地市运输的蔬菜数量；

表示的是从第i个生产基地向第j个地市运输蔬菜的运价；

第i个蔬菜生产基地的蔬菜产量；

第j个地市的蔬菜需求量；

那么有优化模型：

输入Lingo程序求解模型：

q;

link（set1,set2）:

min=@sum（link（i,j）:

c（i,j）*x（i,j））;

@for（set1（i）:

x（i,j））<

@for（set2（j）:

x（i,j））=q（j））;

c=5,8,7,9

4,9,10,7

8,4,2,9;

b=7,8,3;

q=6,6,3,3;

Globaloptimalsolutionfound.

Objectivevalue:

100.0000

Infeasibilities:

0.000000

Totalsolveriterations:

6

VariableValueReducedCost

B

（1）7.0000000.000000

B

（2）8.0000000.000000

B（3）3.0000000.000000

Q

（1）6.0000000.000000

Q

（2）6.0000000.000000

Q（3）3.0000000.000000

Q（4）3.0000000.000000

C（1,1）5.0000000.000000

C（1,2）8.0000000.000000

C（1,3）7.0000000.000000

C（1,4）9.0000000.000000

C（2,1）4.0000000.000000

C（2,2）9.0000000.000000

C（2,3）10.000000.000000

C（2,4）7.0000000.000000

C（3,1）8.0000000.000000

C（3,2）4.0000000.000000

C（3,3）2.0000000.000000

C（3,4）9.0000000.000000

X（1,1）1.0000000.000000

X（1,2）6.0000000.000000

X（1,3）0.0000001.000000

X（1,4）0.0000001.000000

X（2,1）5.0000000.000000

X（2,2）0.0000002.000000

X（2,3）0.0000005.000000

X（2,4）3.0000000.000000

X（3,1）0.0000007.000000

X（3,2）0.0000000.000000

X（3,3）3.0000000.000000

X（3,4）0.0000005.000000

RowSlackorSurplusDualPrice

1100.0000-1.000000

20.0000000.000000

30.0000001.000000

40.0000004.000000

50.000000-5.000000

60.000000-8.000000

70.000000-6.000000

80.000000-8.000000

从该报告可以得到：

1、最优的调拨方案为：

1

2、从DualPrice来看

生产基地A的供应量增加1个单位，费用不变；

生产基地B的供应量增加1个单位，费用减少1；

生产基地C的供应量增加1个单位，费用减少4；

城市甲的需求量增加1个单位，费用减少-5，即增加5；

城市乙的需求量增加1个单位，费用减少-8，即增加8；

城市丙的需求量增加1个单位，费用减少-6，即增加6；

城市丁的需求量增加1个单位，费用减少-8，即增加8；

3、从SlackorSurplus来看，所有的约束都是紧约束。

可见每个生产基地的蔬菜都全部运完。

然后做灵敏度分析：

Rangesinwhichthebasisisunchanged:

ObjectiveCoefficientRanges

CurrentAllowableAllowable

VariableCoefficientIncreaseDecrease

X（1,1）5.0000001.0000001.000000

X（1,2）8.0000001.0000004.000000

X（1,3）7.000000INFINITY1.000000

X（1,4）9.000000INFINITY1.000000

X（2,1）4.0000001.0000001.000000

X（2,2）9.000000INFINITY2.000000

X（2,3）10.00000INFINITY5.000000

X（2,4）7.0000001.000000INFINITY

X（3,1）8.000000INFINITY7.000000

X（3,2）4.0000004.0000001.000000

X（3,3）2.0000001.000000INFINITY

X（3,4）9.000000INFINITY5.000000

RighthandSideRanges

RowCurrentAllowableAllowable

RHSIncreaseDecrease

27.000000INFINITY0.0

38.0000001.0000000.0

43.0000006.0000000.0

56.0000000.01.000000

66.0000000.06.000000

73.0000000.03.000000

83.0000000.01.000000

可以得到以下信息：

1、运价在下面的范围内最优的调拨方案不变:

[4,6]

[4,9]

[6,+∞]

[8,+∞]

[3,5]

[7,+∞]

[5,+∞]

[0,8]

[1,+∞]

[3,8]

[0,3]

[4,+∞]

2、生产基地的产量在下面的范围内最优基不变:

[8,9]

[6,9]

3、四个地市的需求量在下面的范围内最优基不变:

[5,6]

[0,6]

[2,3]

四、收集的一些问题

1、福特在L.A.和Detroit生产汽车,在Atlanta有一仓库,供应点为Houston和Tampa;

城市间每辆汽车运输费用见下表.L.A.的生产能力为1100辆,Detroit的生产能力为2900辆.Houston汽车需求量为2400辆,Tampa汽车需求量为1500辆,

L.A

DETROIT

ATLANTA

HOUSTON

TAMPA

L.A.

140

100

90

225

145

111

110

119

105

115

113

78

89

109

121

-

210

117

82

如何确定运输和生产方案,才能满足Houston和Tempa的需求且费用最低.

2、设有三个化肥厂供应四个地区的农用化肥.假定等量的化肥在这些地区使用效果相同.各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价（万元/万吨）如下表所示.试求出总的运费最省的化肥调拨方案.

需求地区

化肥厂

I

II

III

IV

产量（万吨）

16

13

22

17

50

14

19

15

60

20

23

禁止

最低需求（万吨）

30

70

最高需求（万吨）

不限

3、某航运公司承担6个港口城市A,B,C,D,E,F的四条固定航线的物资运输任务.已知各条航线的起点,终点城市及每天航班数见下表:

航线

起点城市

终点城市

每天航班数

E

D

F

假定各条航线使用相同型号的船只,由各城市间的航程天数见下表:

到

从

又知每条船只每次装卸货物的时间各需1天,则该航运公司至少应配备多少条船,才能满足所有航线的运货要求.

4、如下图所示，节点间的线段表示某小区的弄堂，线段旁的数字表示弄堂的长度。

邮局在其中某个节点，请设计邮递员投递路线。

5、如下图所示，节点间的线段表示某区的街道，街道都是单行道，线段旁的数字表示街道的长度。

6、伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。

公司由五个部门组成，A,B,C,D,和E,考虑搬迁的地址为Bristol和Brighton。

每个城市至多安置3个部门。

各部门搬迁后每年能节约的费用（千镑）如下表：

Bristol

Brighton

各部门间每年的通信量（千单位）如下表：

1.0

1.5

1.4

1.2

2.0

0.7

各部门间的通信单价（镑每年每单位）

London