运筹学实验报告
整数线性规划
专 业: 数学与应用数学专业
班 级: 0941班
姓 名: 张国钢 丁雪晴 赵海迪
郑权水 程龙 闫杰
学 号: 25 02 08 22 23 14
指导教师: 王忠文
应用理学院数学与应用数学专业
20##-12-6
实 验 目 录
一、实验目的... 3
二、实验要求... 3
三、实验类型... 3
四、需用仪器设备... 3
五、实验步骤... 3
实验一 LINGO软件包的使用方法... 4
实验二 MATLAB优化工具箱使用方法... 4
实验三 线性规划问题实例... 4
实验四 整数线性规划问题实例... 4
实验五 非线性规划问题实例... 4
六、实验总结………………………………………………………………………………………5
一、实验目的
掌握建立线性规划、整数规划问题、非线性规划问题数学模型的方法;
熟练地使用LINDO软件包及MATLAB求规划问题。
二、实验要求
1.利用LINGO软件求解简单的线性规划、整数规划、非线性规划模型。
2.利用MATLAB求解简单的线性规划、整数规划、非线性规划模型。
三、实验类型
综合性实验
四、需用仪器设备
pc 486微机、 windows环境、LINGO软件、MATLAB软件。
五、实验步骤
1.通过教材所附光盘的使用说明文件的第二章、第三章、第四章的实例,学习LINGO软件或MATLAB软件基本操作。
2.建立教材80页第2题数学模型,并利用LINGO软件或MATLAB软件求解。
3.建立教材100页第2题数学模型,并利用LINGO软件或MATLAB软件求解。
4.建立教材155页第2题数学模型,并利用LINGO软件或MATLAB软件求解。
本章, 我们介绍三种解决整数线性规划问题的软件:
第一种: MATLAB中的optimization toolbox 中的若干程序;
第二种: LINDO软件;
第二种: LINGO软件.
实验二 整数线性规划问题实例
1. MATLAB程序说明
程序名: intprogram, L01p_e, L01p_ie, transdetobi, biprogram
intprogram 是利用分支定界法解决整数规划问题, 是全部的整数规划问题;
L01p_e 是利用枚举法解决0-1规划问题, 变量要求全部为0或者1;
L01p_ie 是利用隐枚举法解决0-1规划问题, 变量要求全部为0或者1;
Transdetobi 是枚举法和隐枚举法中利用到的将十进制数转化为二进制数的函数;
Biprogram 是MATLAB6.5以上版本中有的求解0-1规划的函数的程序.
intprogram执行实例1:
在命令窗口的程序执行过程和结果如下:
>> c=[-20,-10]; %将最大转化为最小;
>> a=[5,4;2,5];
>> b=[24;13];
>> [x,f]=intprogram(c,a,b,[0;0],[inf;inf],[],0,0.0001) % c,a,b之后[0;0] is the value of low bound;[inf;inf] is the value of up bound;[] is the initialization;0 is the number of the equation constraints; 0.0001 is the concise rate.
x =
4.0000
1.0000
f =
-90
2.LINDO程序说明
LINDO也提供了解决全整数规划、混合整数规划以及0-1规划的方法.
2.1 解决全整数规划问题
程序名: intlpall
intlpall执行实例:
在命令窗口键入以下内容:
max 11x+10y
st
2x+y<12
x-3y>1
end
gin x ! the general integer statement – GIN 将变量约束为整数
gin y ! the general integer statement – GIN 将变量约束为整数
按solve键在reports window出现:
LP OPTIMUM FOUND AT STEP 7
OBJECTIVE VALUE = 72.4285736
NEW INTEGER SOLUTION OF 66.0000000 AT BRANCH 0 PIVOT 12
BOUND ON OPTIMUM: 66.00000
ENUMERATION COMPLETE. BRANCHES= 0 PIVOTS= 12
LAST INTEGER SOLUTION IS THE BEST FOUND
RE-INSTALLING BEST SOLUTION...
OBJECTIVE FUNCTION VALUE
1) 66.00000
VARIABLE VALUE REDUCED COST
X 6.000000 -11.000000
Y 0.000000 -10.000000
ROW SLACK OR SURPLUS DUAL PRICES
2) 0.000000 0.000000
3) 5.000000 0.000000
NO. ITERATIONS= 12
BRANCHES= 0 DETERM.= 1.000E 0]
3. LINGO程序说明
除了特别说明, LINGO默认变量是非负的以及连续的, 但是可用以下命令使得变量满足要求:
@GIN restricts a variable to being an integer value,
@BIN makes a variable binary (i.e., 0 or 1),
@FREE allows a variable to assume any real value, positive or negative
@BND limits a variable to fall within a finite range等.
程序名: intlp (该程序主要是解决整数线性规划问题的, 用上述命令赋予变量属性.)
intlp执行实例:
在模型命令窗口键入以下内容:
max=100*x+150*y;
x<=100;
y<=120;
x+2*y<=160;
@gin(x);@gin(y);!若要只限制x,只要限制x即可.
按运行按钮在solution report 窗口得到以下结果:
Global optimal solution found at iteration: 2
Objective value: 14500.00
Variable Value Reduced Cost
X 100.0000 -100.0000
Y 30.00000 -150.0000
Row Slack or Surplus Dual Price
1 14500.00 1.000000
2 0.000000 0.000000
3 90.00000 0.000000
4 0.000000 0.000000
第二篇:运筹学 线性规划实验报告
实验报告
一、实验名称:线性规划问题
二、实验目的:通过本实验,能掌握Spreadsheet方法,会熟练应用Spreedsheet建模与求解方法。在Excel(或其他)背景下就所需解决的问题进行描述与展平,然后建立线性规划模型,并用Excel的命令与功能进行运算与分析。
三、实验设备
计算机、Excel
四、实验内容
1、线性规划
其中,目标函数为求总利润的最大值。
B11=SUMPRODUCT(B6:C6,B9:C9);
B14=SUMPRODUCT(B3:C3,$B$9:$C$9);
B15=SUMPRODUCT(B4:C4,$B$9:$C$9);
B16=SUMPRODUCT(B5:C5,$B$9:$C$9);
D14=D3; D15=D4; D16=D5;
用规划求解工具求解:目标单元格为B11,求最大值,可变单元格为$B$9:$C$9,约束条件为B14:B16<=D14:D16。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果,即确定产品A的产量为20,产品B的产量为24,可实现最大总利润为428。
2、灵敏度分析
在【可变单元格】表中:
“终值”表示最优解,即产品A产量为20,产品B产量为24。
“递减成本”表示产品的边际收入与按影子价格折算的边际成本的差,当递减成本小于0时,表示不应该安排该产品的生产,在表中的情况反映了产品A产品、B都进行生产,因为在产品A与产品B产量增加的同时利润也是在增加的。
“目标式系数”是在目标函数中变量的系数,也是产品A与产品B的单位利润。
“允许的增量”和“允许的减量”表示在不改变最优解结构的前提下,单个目标系数可变的上下限。也就是说,在目标函数中,产品A的价值系数在(3.6,9.6】内,产品B的价值系数不变,或者产品A的价值不变,产品B的价值系数在【23.3,8.75】内,最有的生产方案依旧为产品A产量为20,产品B产量为24,以达到最大利润。
在【约束】表中:
“阴影价格”表示影子价格。
“允许的增量”与“允许的减量”表示仅当资源增幅在允许的范围内才能利用影子价格进行分析。
3、运输问题
产销不平衡的情况(供给>需求):
其中,E8=SUM(B8:D8);E9=SUM(B9:D9); E10=SUM(B10:D10);
B11=SUM(B8:B10);C11=SUM(C8:C10);D11=SUM(D8:D10);
G8=E2;G9=E3;G10=E4;B13=B5;C13=C5;D13=D5;
E11=SUMPRODUCT(B2:D4,B8:D10)
用规划求解工具求解:目标单元格为E11,求最小值,可变单元格为$B$8:$D$10,约束条件为B11:D11=B13:E13; E8:E10<=G8:G10。在【选项】菜单中选择“采用线性模型”“假定非负”。即可进行求解得结果,即确定最佳运输方案,可实现总运输费最小,为13。
五、实验体会
通过这次实验,我学会了在Excel背景下就所需解决的问题进行描述与展平,然后建立线性规划模型,并用Excel的命令与功能进行运算与分析。通过实际的操作,用Excel来解题方便极了。通过对所需解决的问题进行描述与展平,对原问题的变量、目标值、约束条件理解得更明晰,才能更顺利地建立线性规划模型。然后通过用Excel的命令与功能进行运算与分析,省去了中间繁杂的计算过程,既方便又快速迅捷。