当前课程知识点:运筹学 > 线性规划 > 2.13线性规划实验 > 线性规划实验内容
实验一、线性规划问题建模及其求解
一、实验目的
1、进一步掌握建立线性规划数学模型的方法和步骤;
2、进一步掌握求解线性规划的单纯形法的原理和步骤;
2、熟悉运筹学软件的基本功能并能运用运筹学软件求解线性规划问题。
二、实验的内容
案例 1(必做题)
罗伯· 利蒙,美洲银行的总裁,疲惫地擦了一下眼睛,斜视着他书房里的钟。已经是凌晨3 点了。在前面的数个小时里,罗伯熟读了美洲银行在前三个季度的财务报表。美洲银行是一家中等规模的银行,分支机构遍布美国,但现在,它步履艰难,陷人了困境。该银行提供各种的资金交易,储蓄,投资和信贷服务,在过去的几年里,净收人不断的减少,而且,这种趋势还将继续下去。该银行的业务正逐渐的被一些非银行性质或国外的竞争者蚕食。
美洲银行并不是惟一亏损的银行,从每天的工业读物中,罗伯知道在美国银行的领域内,来自非银行性质的机构以及一些外国同行的不断加剧的竞争,使得许多美国银行处于亏损的境地。
这些非银行机构和外国的银行专门从事某一特殊服务业务,通过提供更有效,便利而价格却更低廉的服务,获取了相应的市场。例如,现在大型的公司都从外国的银行和商业信贷处(paper offerings)获得贷款,而富有的美国人都向货币市场基金投资。美国的银行正面临着如何才能使自己与其他非银行性质机构和外国竞争者区别开来,从而使自己有特色的问题。
罗伯认为区别于竞争对手的一个对策是提供竞争对手所没有提供的服务――交易服务。他确定,在自动取款机之后又会有一种便利的交易方法,这种方法就是通过网络的电子银行。通过网络,客户可以直接从家里和办公室里的桌面电脑来进行交易。网络的大发展,已经使得许多人懂得如何使用万维网。这样,他总结出,如果美洲银行提供网络上的银行交易的话,可能会吸引新的消费者。
在罗伯决定开发网上业务之前,他必须知道网络银行的市场以及美洲银行可以通过网络提供的服务。例如,客户是否只能通过网络查询账户以及交易信息,还是可以获得存取服务?银行是否需要实时的提供股价的行情,收取很少的一笔手续费而允许客户在网上下订单,以吸引一部分投资市场上的客户?
因为美洲银行没有从事调研业务,所以决定将这一调研项目交给一个专业的咨询公司。该项目收到了好几个咨询公司的投标,罗伯将选择成本最小的一个公司。罗伯为资讯公司列出了一系列的调研要求,为确保公司能够获得实行该策略的所需要的信息。
因为不同年龄段的人需要不同的服务,美洲银行对四个年龄段的人有兴趣。第一类为18-25 岁,这些人的收人有限,交易量不会很大。第二类为26-40 ,这些人收人可观,交易量大,需要大量的住房和汽车贷款,并会在各类证券上投资。第三类为41-50 ,这类人与第二类的收人与行为类似,但因为这些人还不适应网络上的电脑大爆炸,因此不大可能使用网络银行。最后,第四类人是51 岁以上,这些人渴望安全,并且对希望获得退休基金的信息。银行相信这些人是绝对不会使用网络交易的,但银行也希望能够进一步获得这些人的需求信息。美洲银行将会调研2,000名客户,其中,第一年龄段至少占20 % ,第二类27 . 5 % ,第三类15%,第四类15%。
罗伯知道网络是近期才发展起来的,一些人甚至还不知道什么是万维网。因此他希望能够知道哪些人使用网络,而哪些人不使用网络。为了保证美洲银行能够获得准确的组合,他要求被调研的人中至少15%来自网络普遍使用的硅谷地区,而35%来自大城市,那里网络的使用程度一般,20%来自很少使用电脑的小城镇。
精致调研公司(Sophisticated Surveys )是投标该项目的三家调研公司中的一家,该公司对调研的成本做了初步的估计,每人的调研费用如下表所示:
地区 | 年龄组 | |||
18-25 | 26-40 | 41-50 | 51以上 | |
硅谷 | $4.75 | $6.50 | $6.50 | $5.00 |
大城市 | $5.25 | $5.75 | $6.25 | $6.25 |
小城市 | $6.50 | $7.50 | $7.50 | $7.25 |
精致调研公司对下面问题进行了探讨。
建立线性规划模型,在满足美洲银行的调研要求的基础上使成本最小。
案例2(选做题)
某公司受人委托,准备用120万元投资A和B两种基金,其中A基金的单位投资额为50元,年回报率为10%,B基金的单位投资额为100元,年回报率为4%。委托人要求在每年的年回报金额至少达到6万元的基础上要求投资风险最小。据测定,每单位A基金的投资风险指数为8,每单位基金B的投资风险指数为3,风险指数越大表示投资风险越大。委托人要求在基金B的投资额不少于30万元。
请回答:
(1) 为了使总的投资风险指数最小,该公司应该在基金A和基金B中各投资多少单位?这时每年的回报金额是多少
(2) 为了使总的投资回报金额最大,应该如何投资?这时的投资风险指数是多少?
三、实验要求
1、能正确建立线性规划问题的数学模型;
2、熟悉单纯形法的原理和求解步骤;
3、熟练运用运筹学商用软件包求解线性规划模型。
四、实验步骤
1、建立数学模型;
2、运用运筹学软件对所建立的线性规划模型进行求解。
五、实验设备
1、PC机、打印机;
2、运筹学商用软件包一套。
六、实验报告
1、 对案例1 或案例2 进行建模求解,并提交实验报告。
2、 实验报告的内容应包括:数学模型;winqsb求解过程(要求有截图);最终求解结果。
附:WinQSB软件线性规划问题求解基本步骤
1. 启动程序,点击开始程序WinQSBLinear and Integer Programming,屏幕显示如图2-2所示的线性规划和整数规划工作界面。
图2-2 线性规划和整数规划工作界面
2. 建立新问题或打开磁盘中已有的文件,按图2-2所示操作建立或打开一个LP问题,或点击FileNew Problem建立新问题,屏幕上出现如图2-3所示的问题选项输入界面。
图2-3 建立新问题
此处共有4种变量类型:
(1) Nonnegative continuous非负连续实数
(2) Nonnegative integer非负整数
(3) Binary(0,1)二进制数
(4) Unsigned/unrestricted无符号或无约束变量
在此处可选(1) Nonnegative continuous(若无约束,可在后面修改)。
3. 输入数据。在选择数据输入格式时,选择Spreadsheet Matrix Form则以电子表格形式输入变量系数矩阵和右端常数矩阵,是固定格式,如图2-5所示。WinQSB默认以X1、X2、X3、X4表示变量,以C1、C2、C3、C4、C5表示约束。如果你对默认的不满意,可以通过Edit菜单下的修改变量名(Variable Name)约束名(Constraint Name)来进行修改。在此菜单下还可以修改问题标题(Problem Title)和目标函数准则(Objective Criterion)(max和min)。
数据输入过程中按Tab键或右方向键可输入下一个单元格。此表格中的数据按如下方式修改:
(1) 如需修改变量,只需用鼠标单击此单元格输入所需数据即可。
(2) 在Direction列双击可在<=、=和>=之间切换。
(3)上界(LowerBound)和下界(UpperBound)的修改可单击单元格直接输入数据,M表示无穷。
(4)双击VariableType行的单元格可使变量类型在Continuous、Integer、Binary和Unrestricted之间切换。若某变量无约束,所以应改为Unrestricted。
选择Normal Model Form则以自由格式输入标准模型,如图2-4所示。两种输入格式可以通过Format菜单下的Switch to Normal Model Form或Switch to Matrix Form来进行切换。
图2-4 标准模型输入格式
4. 修改变量类型。图2-3中给出了非负连续、非负整数、0-1型和无符号限制或无约束4种变量类型选项,当选择了某种类型后系统默认所有变量都属该种类型。M是一个任意大的正数,如图2-5所示。
图2-5 电子表格数据输入格式
5. 修改变量名和约束名。系统默认变量名为X1,X2,……,Xn,约束名为C1,C2,……,Cm。如果对默认名不满意可以进行修改,点击菜单栏Edit后,下拉菜单有四个修改选项:修改标题名(Problem Name)、变量名(Variable Name)、约束名(Constraint Name)和目标函数准则(max或min)。WinQSB支持中文,可以输入中文名称, 如图2-6所示
图2-6
6. 增加或减少变量和约束。
(1) 插入变量:Edit菜单下的Insert a variable,弹出如下的对话框(图2-7)
图2-7插入变量对话框
点击OK插入一个新变量
(2) 删除变量:Edit菜单下的Delete a variable,弹出如下的对话框(图2-8)
图2-8删除变量对话框
选择要删除的变量,点击OK即可删除。
(3) 插入约束:Edit菜单下的Insert a constraint,弹出如下的对话框(图2-9)
图2-9约束插入对话框
具体意义同插入变量。
(4) 删除约束:Edit菜单下的Delete a constraint,弹出如下的对话框(图2-10)
图2-10约束删除对话框
具体意义同删除变量。
7. 求解模型。
点击菜单栏Solve and Analyze,下拉菜单有三个选项:求解不显示迭代过程(Solve the Problem)、求解并显示单纯形法迭代步骤(Solve and Display Steps )及图解法(Graphic Method,限两个决策变量)。
(1)图解法:选择图解法(Graphic Method)。显示如下对话框2-11
图 2-11
用图解法求解,显示可行域,点击菜单栏OptionChange XY Ranges and Colors,改变X1、X2的取值区域(坐标轴的比例),单击颜色区域改变背景、可行域等8种颜色,满足你的个性选择。如图2-12所示
图2-12
(2)单纯形法:选择求解并显示单纯形法迭代步骤,系统显示初始单纯形表2-1。下一步点击菜单栏Simplex Iteration选择Next Iteration继续迭代,还可以人工选择进基变量,或直接显示最终单纯形表。
表2-1 初始单纯形表
(3)求解最优解。选择Solve the Problem,系统直接显示求解的综合报告如表2-2所示,表中的各项含义见常见术语表2-3,LP有最优解或无最优解(无可行解或无界解),系统自动给出提示。
表2-2 最优解综合报告表
由表2-2得到该题的最优解为X=(4,2),最优解Z=14。
-运筹学概述
--什么是运筹学
-绪论章节作业
-2.1 什么是线性规划
--课程视频
-2.2 线性规划的图解法
--课程视频
--图解法作业
-2.3 线性规划的标准型
--课程视频
-2.4 线性规划问题的解
--课程视频
-2.5 线性规划问题的基本可行解
--课程视频
--几个解之间的关系
-2.6 从图解法到单纯形法的几个定理
--课程视频
-2.7 用一个例子了解单纯形法的原理
--课程视频
-2.8 单纯形法原理与单纯形法
--课程视频
--单纯形法的原理作业
-2.9 单纯形法例题详解
--课程视频
-2.10 大M法
--课程视频
--大M法讨论
-2.11 两阶段法
--课程视频
-2.12 线性规划中的特殊解
--课程视频
--工商2018级3.17日作业
-线性规划章节作业
-2.13线性规划实验
--线性规划实验内容
--实验一 实验报告电子版提交处
-3.1 什么是对偶问题
--课程视频
-3.2 写出对偶问题的规划与口诀
--课程视频
-3.3 弱对偶定理与对偶定理
--课程视频
--对偶性质作业一
-3.4 奇怪又好用的互补松弛定理
--课程视频
--互补松驰定理作业
-3.5 从对偶性质到对偶单纯形法
--课程视频
--反过来想想
-3.6 对偶单纯形法的计算步骤
--课程视频
-3.7 影子价格
--课程视频
--影子价格(周三作业)
-3.8 什么是灵敏度分析
--课程视频
--对运筹学的感受
-3.9 价值系数的灵敏度分析
--课程视频
-3.10 资源限量的灵敏度分析
--课程视频
-3.11 工艺系数的灵敏度分析
--课程视频
--灵敏度分析作业
-对偶规划与灵敏度分析作业
-3.12对偶问题与灵敏度分析实验
--实验内容
--对偶规划与灵敏度分析实验报告
-4.1 什么是运输问题
--课程视频
-4.2 运输问题的模型特点
--课程视频
--运输问题的数学模型与特点
-4.3 初始运输方案-最小元素法
--课程视频
--运输问题的运价表
-4.4 初始运输方案-Vogel法
--课程视频
-4.5 检验数计算-闭合回路法
--课程视频
-4.6 检验数计算-位势法
--课程视频
-4.7 表上作业法-解的改进
--课程视频
-4.8 产销不平衡的运输问题与退化解
--课程视频
--退化解的添零技巧
-4.9 有转运运输问题的数学模型
--课程视频
--特殊的运输问题作业(工商)
-运输问题作业
-4.10 运输问题实验
--实验内容
--运输问题实验报告提交处
-5.1 什么是目标规划
--课程视频
-5.2 目标规划的变量和模型
--课程视频
--目标规模模型作业(工商)
-5.3 目标规划建模例题
--课程视频
-5.4 目标规划求解
--课程视频
--满意解与最优解
--目标规划建模与求解(工商)
-目标规划作业
-目标规划实验
--目标规划实验内容
--目标规划实验报告提交处
-6.1 用一个游戏了解多阶段决策问题
--课程视频
--小圆片游戏
-6.2 动态规划的数学模型
--课程视频
-6.3 动态规划的求解思路
--课程视频
-6.4 投资决策问题
--课程视频
-6.5 背包问题
--课程视频
--问题的拆分
--背包问题作业
-动态规划作业
-动态规划实验
--动态规划实验内容
--动态规划实验报告提交处