《运筹学》实验报告.doc

学 生 实 验 报 告

实验课程名称 《运筹学》

开课实验室 四机房

学 院 2013 年级 国工管 专业 二 班
学 生 姓 名 学 号 6313
开 课 时 间 2014 至 2015 学年第 1 学期

总 成 绩

教师签名

实验一 线性规划模型的求解

一、实验目的
了解Lingo软件的基本功能和简单线性规划模型的求解的输入和输出结果。
二、实验内容
1．在Lingo中求解教材P44习题1.6(2)的线性规划数学模型;
2．建立教材P46习题1.14（1）的线性规划数学模型，并在Lingo中求解。
三、实验步骤
P44 1.6(1) ：
min=2*x1+3*x2+x3;
x1+4*x2+2*x3>=8;
3*x1+2*x2>=6;
P46 1.14（1）：
min=x1+x2+x3+x4+x5+x6+x7;
x1+x4+x5+x6+x7>=17;
x2+x5+x6+x7+x1>=13;
x3+x6+x7+x1+x2>=15;
x4+x7+x1+x2+x3>=19;
x5+x1+x2+x3+x4>=14;
x6+x2+x3+x4+x5>=16;
x7+x3+x4+x5+x6>=11;
@gin(x1);
@gin(x2);
@gin(x3);
@gin(x4);
@gin(x5);
@gin(x6);
@gin(x7);

四、实验结果
P44 1.6(1) ：
Global optimal solution found.
Objective value: 7.000000（最优解）
Total solver iterations: 2

Variable Value Reduced Cost
X1 0.8000000 0.000000
X2 1.800000 0.000000
X3 0.000000 0.000000

Row Slack or Surplus Dual Price
1 7.000000 -1.000000
2 0.000000 -0.5000000
3 0.000000 -0.5000000

P46 1.14（1）：
Global optimal solution found.
Objective value: 23.00000（最优解）
Extended solver steps: 0
Total solver iterations: 6

Variable Value Reduced Cost
X1 7.000000 1.000000
X2 5.000000 1.000000
X3 0.000000 1.000000
X4 7.000000 1.000000
X5 0.000000 1.000000
X6 4.000000 1.000000
X7 0.000000 1.000000

Row Slack or Surplus Dual Price
1 23.00000 -1.000000
2 1.000000 0.000000
3 3.000000 0.000000
4 1.000000 0.000000
5 0.000000 0.000000
6 5.000000 0.000000
7 0.000000 0.000000
8 0.000000 0.000000
五、实验小结
了解了Lingo软件的基本功能和简单线性规划模型的求解的输入和输出

实验二 线性规划模型的灵敏度分析
一、实验目的
掌握在Lingo中对线性规划模型进行灵敏度分析的方法。
二、实验内容
在Lingo中求解教材P77习题2.12的线性规划问题，并针对价值系数和资源向量进行灵敏分析。
三、实验步骤
P77，2.12
min=60*x1+40*x2+80*x3;
3*x1+2*x2+x*3>=2;
4*x1+2*x2+2*x3>=3;
4*x1+x*2+3*x3>=4;
四、实验结果
写出Solution Report的内容，指出最优解和最优值。写出Range Report的内容并解释其含义。 Global optimal solution found.
Objective value: 45.00000（最优解）
Total solver iterations: 0

Variable Value Reduced Cost
X1 0.7500000 0.000000
X2 0.000000 10.00000
X3 0.000000 50.00000
X 0.5000000 0.000000

Row Slack or Surplus Dual Price
1 45.00000 -1.000000
2 1.750000 0.000000
3 0.000000 -15.00000
4 0.000000 0.000000

（灵敏度分析） Ranges in which the basis is unchanged:

Objective Coefficient Ranges
Current Allowable Allowable
Variable Coefficient Increase Decrease
X1 60.00000 20.00000 60.00000
X2 40.00000 INFINITY 10.00000
X3 80.00000 INFINITY 50.00000
X 0.0 30.00000 0.0

Righthand Side Ranges
Row Current Allowable Allowable
RHS Increase Decrease
2 2.000000 1.750000 INFINITY
3 3.000000 1.000000 3.000000
4 4.000000 INFINITY 1.000000

五、 实验小结
掌握了Lingo中对线性规划模型进行灵敏度分析的方法。

实验三 在Lingo中求解最大流问题
一、实验目的
掌握在Lingo中求解最大流问题的方法。
二、实验内容
在Lingo中求解教材P259习题8.17的最大流问题。
三、实验步骤
P259，8.17
max=x1+X2+X3;
X4+X5=x1;
x2=x6;
x6=x7;
X8+X9=x3;
X10+X4=x11;
x5+x7+x8=x12;
x9+x12=x13;
x1<=10;
x2<=15;
x3<=40;
x4<=10;
x5<=35;
x6<=15;
x7<=10;
x8<=30;
x9<=20;
x10<=40;
x11<=10;
x12<=10;
x13<=45;
四、实验结果
写出Solution Report的内容，指出最大流的流量和最小割集。
Global optimal solution found.
Objective value: 40.00000
Total solver iterations: 0

Variable Value Reduced Cost
X1 10.00000 0.000000
X2 10.00000 0.000000
X3 20.00000 0.000000
X4 10.00000 0.000000
X5 0.000000 1.000000
X6 10.00000 0.000000
X7 10.00000 0.000000
X8 0.000000 0.000000
X9 20.00000 0.000000
X10 0.000000 0.000000
X11 10.00000 0.000000
X12 10.00000 0.000000
X13 30.00000 0.000000

Row Slack or Surplus Dual Price
1 40.00000 1.000000
2 0.000000 0.000000
3 0.000000 1.000000
4 0.000000 1.000000
5 0.000000 -1.000000
6 0.000000 0.000000
7 0.000000 1.000000
8 0.000000 0.000000
9 0.000000 1.000000
10 5.000000 0.000000
11 20.00000 0.000000
12 0.000000 0.000000
13 35.00000 0.000000
14 5.000000 0.000000
15 0.000000 0.000000
16 30.00000 0.000000
17 0.000000 1.000000
18 40.00000 0.000000
19 0.000000 0.000000
20 0.000000 1.000000
21 15.00000 0.000000
最大流W=f02+f01+f03=f58+f78=40
最小割集S=（v0-v2，v4-v6，v3-v7）
五、实验小结
掌握了Lingo中求解最大流问题的方法。

实验四 在Lingo中求解最短路径问题
一、实验目的
掌握在Lingo中求解最短路径问题的方法。
二、实验内容
在Lingo中求解下图中v1到v7的最短路径。
2
5
4
4
2
7
2
6
3
6
1
V1
V3
V2
V6
V4
V5
V7
1

提示：将最短路径问题转换为最小费用最大流问题。将各边的距离视为费用值，求总费用最少的运输方案。设定各边的容量为1，每边的流量要么取1要么取0。起点的净流出量为1，终点的净流入量为1，其余点总流入等于总流出。
三、实验步骤
min=5*x12+4*x25+2*x13+x23+4*x36+2*x24+2*x46+7*x34+6*x45+x56+3*x57+6*x67;
x12+x13=1;
x67+x57=1;
x12+x25+x24+x23=y1*2;
x13+x36+x34+x23=y2*2;
x45+x24+x34+x46=y3*2;
x57+x25+x45+x56=y4*2;
x67+x36+x46+x56=y5*2;
@bin(x12);
@bin(x13);
@bin(x25);
@bin(x23);
@bin(x36);
@bin(x24);
@bin(x46);
@bin(x34);
@bin(x45);
@bin(x56);
@bin(x57);
@bin(x67);
@bin(y1);
@bin(y2);
@bin(y3);
@bin(y4);
@bin(y5);

四、实验结果
写出Solution Report的内容，在图中标出最短路径
Global optimal solution found.
Objective value: 10.00000
Extended solver steps: 0
Total solver iterations: 0

Variable Value Reduced Cost
X12 0.000000 5.000000
X25 1.000000 4.000000
X13 1.000000 2.000000
X23 1.000000 1.000000
X36 0.000000 4.000000
X24 0.000000 2.000000
X46 0.000000 2.000000
X34 0.000000 7.000000
X45 0.000000 6.000000
X56 0.000000 1.000000
X57 1.000000 3.000000
X67 0.000000 6.000000
Y1 1.000000 0.000000
Y2 1.000000 0.000000
Y3 0.000000 0.000000
Y4 1.000000 0.000000
Y5 0.000000 0.000000

Row Slack or Surplus Dual Price
1 10.00000 -1.000000
2 0.000000 0.000000
3 0.000000 0.000000
4 0.000000 0.000000
5 0.000000 0.000000
6 0.000000 0.000000
7 0.000000 0.000000
8 0.000000 0.000000

最短路径：v1-v3 v3-v2 v2-v5 v5-v7
五、 实验小结
掌握了Lingo中求解最短路径问题的方法。

实验五 在Lingo中求解运输问题
一、实验目的
掌握在Lingo中求解运输问题问题的方法。
二、实验内容
在Lingo中求解教材P104表3-28及表3-29中运输问题。
三、实验步骤
P104，3-28
min=4*x11+x12+4*x13+6*x14+x21+2*x22+5*x23+3*x31+7*x32+5*x33+x34;
x11+x12+x13+x14=8;
x21+x22+x23+x24=8;
x31+x32+x33+x34=4;
x11+x21+x31=6;
x12+x22+x32=5;
x13+x23+x33=6;
x14+x24+x34=3;

3-29 min=3*x11+7*x12+6*x13+4*x14+2*x21+4*x22+3*x23+2*x24+4*x31+3*x32+8*x33+5*x34;
x11+x12+x13+x14<=5;
x21+x22+x23+x24<=2;
x31+x32+x33+x34<=6;
x11+x21+x31=3;
x12+x22+x32=3;
x13+x23+x33=2;
x14+x24+x34=2;

四、实验结果
写出Solution Report的内容，指出运输问题的解和目标函数值。
（3-28） Global optimal solution found.
Objective value: 39.00000
Total solver iterations: 4

Variable Value Reduced Cost
X11 0.000000 3.000000
X12 5.000000 0.000000
X13 3.000000 0.000000
X14 0.000000 6.000000
X21 6.000000 0.000000
X22 0.000000 1.000000
X23 0.000000 1.000000
X31 0.000000 1.000000
X32 0.000000 5.000000
X33 3.000000 0.000000
X34 1.000000 0.000000
X24 2.000000 0.000000

Row Slack or Surplus Dual Price
1 39.00000 -1.000000
2 0.000000 0.000000
3 0.000000 0.000000
4 0.000000 -1.000000
5 0.000000 -1.000000
6 0.000000 -1.000000
7 0.000000 -4.000000
8 0.000000 0.000000

（3-29） Global optimal solution found.
Objective value: 32.00000
Total solver iterations: 5

Variable Value Reduced Cost
X11 3.000000 0.000000
X12 0.000000 5.000000
X13 0.000000 0.000000
X14 2.000000 0.000000
X21 0.000000 2.000000
X22 0.000000 5.000000
X23 2.000000 0.000000
X24 0.000000 1.000000
X31 0.000000 0.000000
X32 3.000000 0.000000
X33 0.000000 1.000000
X34 0.000000 0.000000

Row Slack or Surplus Dual Price
1 32.00000 -1.000000
2 0.000000 1.000000
3 0.000000 4.000000
4 3.000000 0.000000
5 0.000000 -4.000000
6 0.000000 -3.000000