Lingo与线性规划.docx
《Lingo与线性规划.docx》由会员分享，可在线阅读，更多相关《Lingo与线性规划.docx（20页珍藏版）》请在冰点文库上搜索。
Lingo与线性规划
Lingo与线性规划
线性规划的标准形式是
（1）
其中
称为目标函数，自变量
称为决策变量,不等式组
（1）称为约束条件.
满足不等式组
（1）的所有
的集合称为可行域，在可行域里面使得z取最小值的
称为最优解，最优解对应的函数值称为最优值。
求解优化模型的主要软件有Lingo、Matlab、Excel等。
其中Lingo是一款专业求解优化模型的软件，有其他软件不可替代的方便功能。
本文将简要介绍其在线性规划领域的应用。
一、基本规定
1、目标函数输入格式
max=函数解析式；或者min=函数解析式；
2、约束条件输入格式
利用：
>、<、>=、<=等符号。
但是>与>=没有区别。
Lingo软件默认所以自变量都大于等于0.
3、运算
加（+）,减（-）,乘（*）,除（/）,乘方（x^a），要注意乘号（*）不能省略。
4、变量名
不区分大小写字母，不超过32个字符，必须以字母开头。
5、标点符号
每个语句以分号“；”结束，感叹号“！
”开始的是说明语句（说明语句也需要以分号“;”结束）。
但是，model，sets，data以“：
”结尾。
endsets，enddata，end尾部不加任何符号。
6、命令不考虑先后次序
7、MODEL语句
一般程序必须先输入MODEL：
表示开始输入模型，以“END”结束。
对简单的模型，这两个语句也可以省略。
8、改变变量的取值范围
@bin（变量名）；限制该变量为0或1.
@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求目标函数
的最小值，约束条件为
输入Lingo程序：
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.
第二步：
菜单lingo-->range
2、灵敏度报告中常见的词汇
Currentcoefficient：
当前目标函数系数
Allowableincrease：
允许增加量
Allowabledecrease：
允许减少量
CurrentRHS：
当前右边常数项
INFINITY：
表示正无穷。
例1求解下列模型：
max=72*x1+64*x2;
x1+x2<=50;
12*x1+8*x2<=480;
3*x1<=100;
并做灵敏度分析。
求解报告：
灵敏度分析报告：
灵敏度分析报告的解读：
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）/：
矩阵名称
例如：
sets：
set1/1..3/:
x;
set2/1..4/:
a;
link（set1,set2）:
A;
endsets
表示建立了一个矩阵类link，其矩阵的阶数为
，A是具体的矩阵名。
有两个命令是比较常见的：
求和语句:
@sum（集合名（i）:
含集合名（i）的语句）;
循环语句:
@for（集合名（i）:
循环的语句）;
例3：
求目标函数
的最小值，约束条件为
输入Lingo程序：
model:
sets:
set1/1..2/:
c,x;
set2/1..3/:
b;
link（set2,set1）:
A;
endsets
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
6
3
3
如果从各蔬菜生产基地到各地市的每吨蔬菜的运价表（单位：
万元/吨）为:
地市
生产基地
甲
乙
丙
丁
A
5
8
7
9
B
4
9
10
7
C
8
4
2
9
为了降低运输费，需要合理调拨资源.
（1）根据以上资料表制订一个使总的运费为最少的蔬菜调拨方案．
（2）如果有机会增加生产基地的产量1吨，问应当优先增加那个基地的产量？
（3）如果将A到乙市的运价减少为5万元/吨，问这会影响最优的调拨方案吗？
设
：
第i个蔬菜生产基地，
，分别对应生产基地A，B，C；
：
第i个蔬菜需求地，
，分别对应蔬菜需求地市甲、乙、丙、丁；
：
总运输费用；
：
表示的是从第i个生产基地向第j个地市运输的蔬菜数量；
：
表示的是从第i个生产基地向第j个地市运输蔬菜的运价；
：
第i个蔬菜生产基地的蔬菜产量；
：
第j个地市的蔬菜需求量；
那么有优化模型：
输入Lingo程序求解模型：
model:
sets:
set1/1..3/:
b;
set2/1..4/:
q;
link（set1,set2）:
c,x;
endsets
min=@sum（link（i,j）:
c（i,j）*x（i,j））;
@for（set1（i）:
@sum（link（i,j）:
x（i,j））<=b（i））;
@for（set2（j）:
@sum（link（i,j）:
x（i,j））=q（j））;
data:
c=5,8,7,9
4,9,10,7
8,4,2,9;
b=7,8,3;
q=6,6,3,3;
enddata
end
运行结果如下：
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、最优的调拨方案为：
地市
生产基地
甲
乙
丙
丁
A
1
6
0
0
B
5
0
0
3
C
0
0
3
0
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、运价在下面的范围内最优的调拨方案不变:
地市
生产基地
甲
乙
丙
丁
A
[4,6]
[4,9]
[6,+∞]
[8,+∞]
B
[3,5]
[7,+∞]
[5,+∞]
[0,8]
C
[1,+∞]
[3,8]
[0,3]
[4,+∞]
2、生产基地的产量在下面的范围内最优基不变:
生产基地
A
B
C
蔬菜生产量（吨）
[7,+∞]
[8,9]
[6,9]
3、四个地市的需求量在下面的范围内最优基不变:
地区
甲
乙
丙
丁
蔬菜生产量（吨）
[5,6]
[0,6]
[0,3]
[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.
0
140
100
90
225
DETROIT
145
0
111
110
119
ATLANTA
105
115
0
113
78
HOUSTON
89
109
121
0
-
TAMPA
210
117
82
-
0
如何确定运输和生产方案,才能满足Houston和Tempa的需求且费用最低.
2、设有三个化肥厂供应四个地区的农用化肥.假定等量的化肥在这些地区使用效果相同.各化肥厂年产量,各地区年需要量及从各化肥厂到各地区运送单位化肥的运价（万元/万吨）如下表所示.试求出总的运费最省的化肥调拨方案.
需求地区
化肥厂
I
II
III
IV
产量（万吨）
A
16
13
22
17
50
B
14
13
19
15
60
C
19
20
23
禁止
50
最低需求（万吨）
30
70
0
10
最高需求（万吨）
50
70
30
不限
3、某航运公司承担6个港口城市A,B,C,D,E,F的四条固定航线的物资运输任务.已知各条航线的起点,终点城市及每天航班数见下表:
航线
起点城市
终点城市
每天航班数
1
E
D
3
2
B
C
2
3
A
F
1
4
D
B
1
假定各条航线使用相同型号的船只,由各城市间的航程天数见下表:
到
从
A
B
C
D
E
F
A
0
1
2
14
7
7
B
1
0
3
13
8
8
C
2
3
0
15
5
5
D
14
13
15
0
17
20
E
7
8
5
17
0
3
F
7
8
5
20
3
0
又知每条船只每次装卸货物的时间各需1天,则该航运公司至少应配备多少条船,才能满足所有航线的运货要求.
4、如下图所示，节点间的线段表示某小区的弄堂，线段旁的数字表示弄堂的长度。
邮局在其中某个节点，请设计邮递员投递路线。
5、如下图所示，节点间的线段表示某区的街道，街道都是单行道，线段旁的数字表示街道的长度。
邮局在其中某个节点，请设计邮递员投递路线。
5
6、伦敦一家大公司计划将公司的一些部门搬出伦敦，以节约诸如房租人事等方面的费用，当然部门间的通信费用必将增加。
公司由五个部门组成，A,B,C,D,和E,考虑搬迁的地址为Bristol和Brighton。
每个城市至多安置3个部门。
各部门搬迁后每年能节约的费用（千镑）如下表：
A
B
C
D
E
Bristol
10
15
10
20
5
Brighton
10
20
15
15
15
各部门间每年的通信量（千单位）如下表：
A
B
C
D
E
A
1.0
1.5
B
1.4
1.2
C
2.0
D
0.7
各部门间的通信单价（镑每年每单位）
Bristol
Brighton
London
Bristol
5
14
13
Brighton
14
5
9
London
13
9
10
升级会员 