《运筹学》实验教学指导书

内容发布更新时间 : 2024/6/16 8:01:00星期一 下面是文章的全部内容请认真阅读。

《运筹学》实验教学指导书

实验类别:课内实验 所属课程名称:运筹学 实验学时:8 所属课程编码:N02081307 实验室名称:大学数学实验中心 实验室类别:基础实验教学中心

参考书目:《运筹学》(胡运权等编著,高等教育出版社)、《运筹学模型与方法教程》(程理民编,清华大学出版社)、《运筹学》(牛映武编,西安交通大学出版社)、MATLABR2012a完全自学一本通(刘浩 韩晶编著,电子工业出版社)

适用专业:信息与计算科学 数学与应用数学

序号 实验一 实验二 实验三 实验四 实验名称 利用单纯形法求解线性规划 利用对偶单纯形法求解线性规划 灵敏度分析 整数线性规划 学时 2 2 2 2 页码 2 13 23 35

- 1 -

实验一 利用单纯形法求解线性规划

一、实验目的

使学生了解lindo系统,熟练掌握利用lindo软件,利用单纯形法求解线性规划问题。 二、实验内容及要求

1. 安装Lindo6.1软件, 启动lindo6.1, 熟悉lindo6.1求解线性规划的过程和步骤。 2. 对教材《运筹学基础及应用》上第一章线性规划及单纯形法的几个例子(有唯一解,有无穷多解,有无界解,无可行解)编写简单的LINDO程序,会利用lindo软件求解。

3.根据实际问题建立线性规划数学模型,利用lindo软件求解。 4. 对于给出的线性规划模型,利用lindo软件求解。 三、实验的重点和难点

1. 实验的重点:单纯形法。

2. 实验的难点:线性规划模型的正确建立。 四、实验准备

实验室电脑需要安装lindo软件。lindo软件在线性规划中的使用说明: 1. 安装Lindo软件

安装过程中,用户只需要按照程序给出的提示,一步一步走下去,直到安装成功为止。 第一次运行刚安装的LINDO软件时,系统会弹出一个对话框,要求你输入密码(Password)。如果你买的是正版软件,请在密码框中输入LINDO公司给你提供的密码,然后按“OK” 按钮即可。否则,你只能使用演示版(即试用版),按下“Demo Version(演示版)” 按钮即可。 进入lindo软件的输入界面:

2.会编写一个简单的LINDO程序 例如,一个线性规划(LP)问题:

Max

在空白的模型窗口中输入这个LP模型:

max 2x+3y

st 4x+3y<=10 3x+5y<=12 end

如图:

- 2 -

s..tz?2x?3y4x?3y?103x?5y?12x,y?0

LINDO程序有以下特点:

1)程序以“MAX”(或“MIN”)开始,表示目标最大化(或最小化)问题,后面直接写出目标函数表达式和约束表达式;

2)目标函数和约束之间用“ST”分开或用“s.t.”,“sunject to” ; 3)程序以“END”结束( “END” 也可以省略); 4)系数与变量之间的乘号必须省略;

5)系统对目标函数所在行自动生成行名“1)”,对约束默认的行名分别是“2)” “3)”…,用户也可以自己输入行名;行名放在对应的约束之前;

6)书写相当灵活,不必对齐,不区分字符的大小写; 7)默认所有的变量都是非负的, 所以不必输入非负约束; 8)约束条件中的“<=” 及“>=”可分别用“<” 及“>”代替;

9)一行中感叹号“!”后面的文字为是注释语句,可增强程序的可读性,不参与模型的建立。 3. 会模型求解

用鼠标点击工具栏中的图标,或从菜单中选择Solve|Solve(Ctrl+S)命令, LINDO首先开始编译这个模型,编译没有错误则开始求解;求解时会首先显示如右图所示的LINDO“求解器运行状态窗口 ”:

求解器运行状态窗口显示的相应信息及含义: 名称 Status (当前状态) Iterations(迭代次数) 含义 显示当前求解状态:“Optimal”表示已经达到最优解;其他可能的显示还有三个:Feasible(可行解), Infeasible(不可行), Unbounded(最优值无界)。 显示迭代次数:“2”表示经过了2次迭代。 - 3 -

Infeasibility (不可行性) 约束不满足的量(即各个约束条件不满足的“数量”的和;特别注意不是“不满足的约束个数”):“0”表示这个解是可行的。 Objective(当前的目标值) 显示目标函数当前的值:7.45455。 Best IP(整数规划当前的最佳目标值) 显示整数规划当前的最佳目标值:“N/A” (No Answer或Not Applicable)表示无答案或无意义,因为这个模型中没有整数变量,不是整数规划(IP)。 IP Bound(整数规划的界) 显示整数规划的界(对最大化问题显示上界;对最小化问题,显示下界):“N/A”含义同上。 Branches(分枝数) Elapsed Time (所用时间) Update Interval (刷新本界面的时间间隔) Interrupt Solver (中断求解程序) Close(关闭) 显示分枝定界算法已经计算的分枝数: “N/A”含义同上。 显示计算所用时间(秒):“0.00”说明计算太快了,用时还不到0.005秒。 显示和控制刷新本界面的时间间隔:“1”表示1秒;用户可以直接在界面上修改这个时间间隔。 当模型规模比较大时(尤其对整数规划),可能求解时间会很长,如果不想再等待下去时,可以在程序运行过程中用鼠标点击该按钮终止计算。求解结束后这个按钮变成了灰色,再点击就不起作用了。 该按钮只是关闭状态窗口,并不终止计算。如果你关闭了状态窗口,将来随时可以选择WINDOW | OPEN STATUS WINDOW 菜单命令来再次打开这个窗口。 紧接着弹出一对话框,询问你是否需要做灵敏性分析(DO RANGE (SENSITIVITY) ANALYSIS? )先选择“否(N)”按钮,这个窗口就会关闭。然后,再把状态窗口也关闭。

4.通过报告窗口得到线性规划的解

用鼠标选择“Reports”(报告窗口)下拉菜单选项“solution”,就可以查看该窗口的内容

从报告窗口的下方显示该线性规划问题的目标函数值、变量值、迭代次数等:

- 4 -

LP OPTIMUM FOUND AT STEP 2 OBJECTIVE FUNCTION VALUE 1) 7.454545

VARIABLE VALUE REDUCED COST X 1.272727 0.000000 Y 1.636364 0.000000 ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 0.090909 3) 0.000000 0.545455

NO. ITERATIONS= 2 输出结果表示的意思是:

“LP OPTIMUM FOUND AT STEP 2”:表示单纯形法在两次迭代(旋转)后得到最优解;

OBJECTIVE FUNCTION VALUE 1) 7.4545450 ”表示最优目标值为7.4545450.(注意:在LINDO中目标函数所在的行总是被认为是第1行,这就是这里“1)”的含义);

“VALUE”给出最优解中各变量(VARIABLE)的值: X =1.272727, Y =1.636364;

“REDUCED COST” 给出最优的单纯形表中目标函数行(第1行)中变量对应的系数(即各个变量的检验数(也称为判别数)). 其中基变量的reduced cost值一定为0;对于非基变量(注意:非基变量本身取值一定为0), 相应的 reduced cost值表示当该非基变量增加一个单位(其他非基变量保持不变)时目标函数减少的量( 对max型问题)。本例最优解中两个变量都是基变量,所以对应的REDUCED COST的值均为0。

“SLACK OR SURPLUS(松驰或剩余)” 给出约束对应的松驰变量的值: 第2、3行松驰变量均为0, 说明对于最优解来讲,两个约束(第2、3行)均取等号,即都是紧约束。

“DUAL PRICES” 给出对偶价格的值: 第2、3行对偶价格分别为 .090909,.545455。 “NO. ITERATIONS= 2” 表示用单纯形法进行了两次迭代(旋转)。 5. 保存文件

选择File|Save(F5)命令把“结果报告”保存在一个文件中(缺省的后缀名为LTX,即LINDO文本文件)。类似地,回到模型窗口,可以把输入的模型保存在一个文件中。保存的文件将来可以用File | Open(F3)和File | View(F4)重新打开,用前者打开的程序可以进行修改,而后者只能浏览。

如果模型有错误,运行时会弹出出错信息报告窗口(LINDO Error Message),则需要修改模型。 6. LINDO模型的一些注意事项

1)变量名由字母和数字组成,但必须以字母开头,且长度不能超过8个字符,不区分大小写字母,包括关键字(如MAX、MIN等)也不区分大小写字母。

2)对目标函数和约束用行号(行名)进行标识,这些标识会在将来的求解结果报告中用到。行名可以和变量名一样命名,也可以只用数字命名,还可以含有中文字符,但长度同样不能超过8个字符。为了方便将来阅读求解结果报告,建议用户总是自觉地对每个约束进行命名。行名结束标志符号、即右

- 5 -

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi