线性规划实验内容实验一

实验一、线性规划问题建模及其求解

一、实验目的

1、进一步掌握建立线性规划数学模型的方法和步骤；

2、进一步掌握求解线性规划的单纯形法的原理和步骤；

2、熟悉运筹学软件的基本功能并能运用运筹学软件求解线性规划问题。

二、实验的内容

案例1(必做题)

罗伯・利蒙，美洲银行的总裁，疲惫地擦了一下眼睛，斜视着他书房里的钟。已经是凌晨3点

了。在前面的数个小时里，罗伯熟读了美洲银行在前三个季度的财务报表。美洲银行是一家中等规

模的银行，分支机构遍布美国，但现在，它步履艰难，陷入了困境。该银行提供各种的资金交易，

储蓄，投资和信贷服务，在过去的几年里，净收人不断的减少，而且，这种趋势还将继续下去。该

银行的业务正逐渐的被一些非银行性质或国外的竞争者蚕食。

美洲银行并不是惟一亏损的银行，从每天的工业读物中，罗伯知道在美国银行的领域内，来自

非银行性质的机构以及一些外国同行的不断加剧的竞争，使得许多美国银行处于亏损的境地。

这些非银行机构和外国的银行专门从事某一特殊服务业务，通过提供更有效，便利而价格却更

低廉的服务，获取「相应的市场。例如，现在大型的公司都从外国的银行和商业信贷处(paper

offerings)获得贷款，而富有的美国人都向货币市场基金投资。美国的银行正面临着如何才能使自

己与其他非银行性质机构和外国竞争者区别开来，从而使自己有特色的问题。

罗伯认为区别于竞争对手的一个对策是提供竞争对手所没有提供的服务一一交易服务。他确

定，在自动取款机之后又会有一种便利的交易方法，这种方法就是通过网络的电子银行。通过网络,

客户可以直接从家里和办公室里的桌面电脑来进行交易。网络的大发展，已经使得许多人懂得如何

使用万维网。这样，他总结出，如果美洲银行提供网络上的银行交易的话，可能会吸引新的消费者。

在罗伯决定开发网上业务之前，他必须知道网络银行的市场以及美洲银行可以通过网络提供的

服务。例如，客户是否只能通过网络查询账户以及交易信息，还是可以获得存取服务？银行是否需

要实时的提供股价的行情，收取很少的一笔手续费而允许客户在网上下订单，以吸引一部分投资市

场上的客户？

因为美洲银行没有从事调研业务，所以决定将这一调研项目交给一个专业的咨询公司，该项目

收到了好几个咨询公司的投标，罗伯将选择成本最小的一个公司。罗伯为资讯公司列出了一系列的

调研要求，为确保公司能够获得实行该策略的所需要的信息。

因为不同年龄段的人需要不同的服务，美洲银行对四个年龄段的人有兴趣。第一类为18—25

岁，这些人的收入有限，交易量不会很大。第二类为26—40,这些人收入可观，交易量大，需要

大量的住房和汽车贷款，并会在各类证券上投资。第三类为41—50,这类人与第二类的收人与行

为类似，但因为这些人还不适应网络上的电脑大爆炸，因此不大可能使用网络银行。最后，第四类

人是51岁以上，这些人渴望安全，并且对希望获得退休基金的信息。银行相信这些人是绝对不会

使用网络交易的，但银行也希望能够进一步获得这些人的需求信息。美洲银行将会调研2,000名

客户，其中，第一年龄段至少占20%,第二类27.5%,第三类15%,第四类15%。

罗伯知道网络是近期才发展起来的，一些人甚至还不知道什么是万维网。因此他希望能够知道

哪些人使用网络，而哪些人不使用网络。为了保证美洲银行能够获得准确的组合，他要求彼调研的

人中至少15%来自网络普遍使用的硅谷地区，而35%来自大城市，那里网络的使用程度一般，20%

来自很少使用电脑的小城镇。

精致调研公司（SophisticatedSurveys）是投标该项Fl的三家调研公司中的一家，该公司对调

研的成本做了初步的估计，每人的调研费用如下表所示：

地区年龄组

18-2526-4041-5051以上

硅谷$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、运用运筹学软件对所建立的线性规划模型进行求解c

五、实验设备

1、PC机、打印机；

2、运筹学商用软件包一套。

六、实验报告

1、对案例1或案例2进行建模求解，并提交实验报告。

2、实验报告的内容应包括：数学模型：winqsb求解过程（要求有截图）；最终求解结果。

附：WinQSB软件线性规划问题求解基本步骤

1.启动程序，点击开始—程序—>WinQSBfLinearandIntegerProgramming,屏幕显示如图

2-2所示的线性规划和整数规划工作界面。

图2-2线性规划和整数规划，作界面

2.建立新问题或打开磁盘中已有的文件，按图2-2所示操作建立或打开一个LP问题，或点击

File—>NewProblem建立新问题，屏幕上出现如图2-3所示的问题选项输入界面。

图2-3建立新问题

此处共有4种变量类型：

(I)Nonnegativecontinuous非负连续实数

(2)Nonnegativeinteger非负整数

(3)Binary。1)二进制数

(4)Unsigned/unrestricted无符号或无约束变量

在此处可选(1)Nonnegaiivecontinuous(若无约束，可在后面修改)。

3.输入数据。在选择数据输入格式时，选择SpreadsheetMatrixForm则以电子表格形式输入变

量系数矩阵和右端常数矩阵，是固定格式，如图2-5所示。WinQSB默认以XI、X2、X3、X4表示

变量，以Cl、C2、C3、C4、C5表示约束。如果你对默认的不满意，可以通过Edit菜单下的修改

变量名(VariableName)约束名(ConslraintName)来进行修改。在此菜单下还可以修改问题标题

(ProblemTitle)和目标函数准则(ObjectiveCriterion)(max和min)。

数据输入过程中按Tab键或右方向键可输入下一个单元格。此表格中的数据按如下方式修改：

Variable->X1X2DirectionR.H.S.

Maximize23

C14<=16

C24<=12

C312<=8

LowerBound00

UpperBoundMM

VariableTypeContinuousContinuous

图2-5电子表格数据输入格式

5.修改变量名和约束名。系统默认变量名为XI,X2,......Xn,约束名为Cl,C2,

Cm。如果对默认名不满意可以进行修改，点击菜单栏Edit后，下拉菜单有四个修改选项：修改标

题名(ProblemName)、变量名(VariableName)、约束名(ConstraintName)和目标函数准则(max或min)。

WinQSB支持中文,可以输入中文名称，如图2-6所示

I柝LinearandIntegerPrograming

FileFormatSolveandAnalyzeUtilitiesWindowYinQS3Help

图2-6

6.增加或减少变量和约束。

(1)插入变量:Edit菜单下的Inseriavariable,弹出如下的对话框(图2-7)

InsertaVariable凶

Thereare4variablesintheproblem.Thedefaultnameof

thenextvariablewillbeX5.

Insertat

InsertedName:

X5(•Theend

CThebeginning

区UsethedefaultnameCTheselectedlocation

OKCancelHelp

图2-7插入变量对话框

点击0K插入一个新变量

⑵删除变量：Edit菜单下的Deleteavariable,弹出如下的对话框（图2-8）

图2-8删除变鼠对话框

选择要删除的变量，点击0K即可删除。

（3）插入约束：Edit菜单下的Insertaconstraint,弹出如下的对话框（图2-9）

图2-9约束插入对话框

具体意义同插入变量。

（4）删除约束：Edit菜单下的Deleteaconstraint,弹出如下的对话框（图2-10）

图2-10约束删除对话框

具体意义同删除变量。

7.求解模型。

点击菜单栏SolveandAnalyze,卜拉菜单有三个选项：求解不显示迭代过程(Solvethe

Problem)、求解并显示单纯形法迭代步骤(SolveandDisplaySteps)及图解法(GraphicMethod,限两

个决策变量)。

(1)图解法：选择图解法(GraphicMethod)。显示如下对话框2-11

图2-11

用图解法求解，显示可行域，点击菜单栏OptionfChangeXYRangesandColors,改变XI、

X2的取值区域(坐标轴的比例),单击颜色区域改变背景、可行域等8种颜色,满足你的个性选择。

如图2-12所示

图2-12

(2)单纯形法：选择求解并显示单纯形法迭代步骤，系统显示初始单纯形表2-1。下一步点击菜

单栏SimplexIteration选择NextIteration继续迭代，还可以人工选择进基变量，或直接显示最终单

纯形表。

表2-1初始单纯形表

X1IX2Slack_C1Slack_C2Slack_C3

Basisc(i)2.000013.0000000R.H.S.Ratio

Slack_C104.000001.00000016.0000M

Slack_C20°4.000001.0000012.00003.0000

Slack_C301.00002.0000001.00008.00004.0000

C(i)-Z(i)2.00003.00000000

(3)求解最优解。选择SolvetheProblem,系统直接显示求解的综合报告如表2-2所示，表中

的各项含义见常见术语表2-3,LP有最优解或无最优解(无可行解或无界解)，系统自动给出提示。

表2-2最优解综合报告表

18:01:20|Wednesday|March152006

DecisionSolutionUnitCostorTotalReducedBasisAllowableAllowable

VariableValueProfitc(j)ContributionCostStatusMin.c(j)Max.c(j)

TX14.00002.00008.00000basic1.5000M

2X22.00003.00006.00000basic°4.0000

ObjectiveFunction(Max.)=14.0000

LeftHandRightHandSlackShadowAllowableAllowable

ConstraintSideDirectionSideorSurplusPriceMin.RHSMax.RHS

1C116.0000<=16.000000.12508.000032.0000

2C28.0000<=12.00004.000008.0000M

3C38.0000<=8.000001.50004.000010.0000

由表2-2得到例4.4.1的最优解为X=(4,2)，最优解Z=14。

8.结果显示及分析：使