线性规划问题及灵敏度分析Word文档下载推荐.doc

线性规划问题及灵敏度分析Word文档下载推荐.doc

《线性规划问题及灵敏度分析Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《线性规划问题及灵敏度分析Word文档下载推荐.doc（9页珍藏版）》请在冰点文库上搜索。

用WinQSB软件求解下列线性规划问题：

s.t.

解：

应用WinQSB软件求解线性规划问题不必化为标准型，如果是可以线性化的模型则先线性化，对于有界变量及无约束变量可以不用转化，只需要修改系统的变量类型即可，对于不等式约束可以在输入数据时直接输入不等式符号。

（1）启动线性规划（LP）和整数规划（ILP）程序

点击开始→程序→WinQSB→LinearandIntegerProgramming，显示线性规划和整数规划工作界面（注意菜单栏、工具栏和格式栏随主窗口内容变化而变化）。

这一程序解决线性规划（LP）以及整数线性规划（ILP）问题。

IP-ILP的特殊性能包括：

LP的单纯形法与图形法

ILP的分枝定界法

显示单纯形表

显示分枝定界法解决方案

执行灵敏性或参数分析

寻求可选择的解决

对不可行问题进行不可行分析

用电子表格矩阵式输入问题

用普通模型形式输入问题

定制变量边界与类型

图1-1LP-ILP模块的主要功能

自动生成对偶问题

（2）建立新问题或者打开磁盘中已有的文件

点击File→NewProblem建立一个新问题。

输入本问题的文件名称lp1（读者可以任意取名），决策变量个数4和约束条件个数5，由于本问题是一个最大化问题，所以选择Maximization，同时可以确定数据的输入形式，一种为表单形式，一种为模型形式。

如果我们选择了表单形式，如图2-1所示。

（3）输入数据

按照例1以表格或模型形式输入变量系数和右端常数数据。

决策变量个数

目标函数取极大还是极小进行选择

数据输入方式选择：

表单式、一般模型形式

数据类型定义

约束条件个数

图1-2LP-ILP模型基础设定

（4）修改变量类型

图1-3种给出了非负连续、非负整数、0-1型和无符号限制或者无约束4种变量类型选项，当选择了某一种类型后系统默认所有变量都属于该种类型。

在例1中，，直接将中的下界（LowerBound）改为10，上界（UpperBound）改为20。

把设定为无约束（Unrestricted），M是一个任意大的正数。

得到如表1-1所示的表格。

表1-1初始单纯型表

（5）修改变量名和约束名。

系统默认变量名为X1，X2，…，Xn，约束名为C1，C2，…，Cm。

默认名可以修改，点击菜单栏Edit后，下拉菜单有四个修改选项：

修改标题名（ProblemName）、变量名（VariableName）、约束名（ConstraintName）和目标函数准则（max或min）。

由于WinQSB软件支持中文，读者可以输入中文名称。

（6）求解

点击菜单栏SolveandAnalyze，下拉菜单有三个选项：

求解不显示迭代过程（SolvetheProblem）、求解并显示单纯形法迭代步骤（SolveandDisplaySteps）及图解法（GraphicMethod，限两个决策变量）。

如选择SolvetheProblem，系统直接显示求解的综合报告如表1-2所示，表中的各项含义见表1-5。

线性规划问题有最优解或无最优解（无可行解或无界解），系统会给出提示。

表1-2winqsb线性规划求解的综合报告

由表1-2得到例1的最优解为，最优值。

同时由表2的第6行提示AlternateSolutionExists!

!

知原线性规划问题有多重解。

（7）显示结果分析

点击菜单栏result或者点击快捷方式图标，存在最优解时，下拉菜单有9个选项（如下1）~9）），无最优解时有两个选项（如下10）~11））。

只显示最优解（SolutionSummary）。

约束条件摘要（ConstraintSummary），比较约束条件两端的值。

对目标函数进行灵敏度分析（SensitivityAnalysisofOBJ）。

对约束条件右端常数进行灵敏度分析（SensitivityAnalysisofRHS）。

求解结果组合报告（CombinedReport），显示详细综合分析报告。

进行参数分析（PerformParametricAnalysis），某个目标函数系数或约束条件右端常数带有参数，计算出参数的变化区间及其对应的最优解，属于参数规划内容。

显示最后一张单纯性表（FinalSimplexTableau）。

显示另一个基本最优解（ObtainAlternateOptimal），存在多重解时，系统显示另一个基本最优解，然后考虑对基本最优解进行组合可以得到最优解的通解。

显示系统运算时间和迭代次数（ShowRunTimeandItration）。

不可行性分析（InfeasibilityAnalysis），线性规划问题无可行解时，系统指出存在无可行解的原因，如将例1的第5个约束改为，系统显示无可行解并且给出这样的显示报告：

表1-3winqsb线性规划求解不可行性分析表

这说明第5个约束不可能小于等于零，右端常数至少等于117.1429才可行。

（11）无界性分析（UnboundednessAnalysis），线性规划问题存在无界解时，系统指出存在无界解的可能原因。

如将目标函数系数改为，系统显示无界并且显示：

表1-4winqsb线性规划求解无界性分析表

系统提示要使线性规划问题有解，应该改变第二个约束条件。

（12）保存结果。

求解后将结果显示在顶层窗口，点击File→SaveAs，系统以文本格式存储计算结果。

（13）将计算表格转换成Excel表格。

在计算结果界面中点击File→CopytoClipboard，系统将计算结果复制到剪贴板，再粘贴到Excel表格中即可。

（8）单纯形表

选择求解并显示单纯形法迭代步骤，系统显示初始单纯性表如表1-1所示可以发现，系统将X4无约束改写成X4－Neg_X4，即两个非负变量之差；

系统将改写成约束C6：

，令，则有，将代入约束条件并整理，在表中的实际上是，如约束C1：

X1+2X2+6（X3+10）+9X4－Neg_X4+Slack_C1=260

整理后得到表1-5第一行（Slack_C1）。

约束C1，C4，C5，C6加入4个松弛变量Slack_C1，Slack_C4，Slack_C5以及Slack_UB_X3，约束C2减去剩余变量Surplus_C2，然后C2与C3加入2个人工变量Artificial_C2和Artificial_C3，共6个约束12个变量。

表2最后两行为检验数，如X1的检验数C

（1）－Z

（1）*BigM=6－15M。

选X1进基，表2-1最后一列为比值，变量Artificial_C3出基，主元素A（3,1）=7。

下一步点击菜单栏SimplexIteration选择NextIteration继续迭代，还可以人工选择进基变量，或直接显示最终单纯形表。

（9）模型形式转换

点击菜单栏Format→SwitchtoNormalModelForm，将表1-5电子表格转换成表1-6的模型形式，再点击一次转换成表1-5的电子表格。

（10）写出对偶模型

点击菜单栏Format→SwitchtoDualForm，系统自动给出线性规划的对偶模型，再点击一次给出原问题模型。

表1-5初始单纯形表

图1-3标准模型输入形式

附录：

线性规划常用术词汇及其含义

常用术语

含义

AlternativeSolutionExists

BasicandNonbasicVariable

Basis

BasisStatus

Branch-and-BoundMrthod

Cj-Zj

CombinedReport

ConstraintSummary

Constraint

ConstraintDirection

ConstraintStatus

DecisionVariable

DualProblem

EnteringVariable

FeasibleArea

FeasibleSolution

Infeasible

InfeasibilityAnalysis

LeavingVariable

Left-handside

LowerorUpperBound

MinimumandMaximumAllowableCj

有多重解

基变量和非基变量

基

基变量状态

分支定界法

检验数

组合报告

约束条件摘要

约束条件

约束方向

约束状态

决策变量

对偶问题

入基变量

可行域

可行解

不可行

不可行分析

出基变量

左端

上界或下界

最优解不变时，价值系数允许变化范围

MinimumandMaximumAllowable

RHS

ObjectiveFunction

OptimalSolution

ParametricAnalysis

RangeandSlopeofParametricAnalysis

ReducedCost

RangeofFeasibility

RangeofOptimality

RelaxedProblem

RelaxedOptimum

Right-handSide

SensitivityAnalysisofOBJCoefficients

SensitivityAnalysisofRight-Hand-sides

ShadowPrice

SimplexMethod

Slack,SurplusorArtificialVariable

SolutionSummary

Subtract（Add）MoreThanThisFromA（i,j）

TotalContribution

UnboundedSolution

最优基不变时，资源限量允许变化范围；

右端系数

目标函数

最优解

参数分析

参数分析的区间和斜率

约简成本（价值）

可行区间

最优区间

松弛问题

松弛最优

右端常数

目标函数的灵敏度分析

右端常数的灵敏度分析

影子价格

单纯形法

松弛变量、剩余变量或人工变量

最优解摘要

减少（增加）约束系数

总体贡献

无界解

二、对偶线性规划的WinQSB应用

例2：

已知线性规划

s.t.

写出对偶线性规划，变量用表示；

求原问题及对偶问题的最优解；

分别写出价值系数及右端常数的最大允许变化范围；

目标函数系数改为，同时常数改为，求最优解；

删除第四个约束同时删除第三个变量，求最优解；

增加一个变量，系数为，求最优解。

启动线性规划与整数规划（LinearandIntegerProgramming），建立新问题，取名为dual1（可任意取名），输入数据得到表2-1，存盘。

表2-1

（1）点击Format→SwitchtoDualForm，得到对偶问题的数据表，点击Format→SwitchtoNormalModelForm，得到对偶模型，点击Edit→VariableName，分别修改变量名，得到以为变量名的对偶模型，如图2-1所示。

图2-1

（2）再求一次对偶返回到原问题，求解显示结果如表2-2，此时最优解为，最优值。

表中影子价格（ShadowPrice）对应列的数据就是对偶问题的最优解为。

表2-2最优解详细综合分析报告

（3）由表2-2最后两列可知：

价值系数（）最大允许变化范围分别是[0.8333,4.1667]，[1.333,5.7778]，[1.1667,4.5]，（,3.4917]；

右端常数的最大允许变化范围分别是[5,27.4719]，[16.6667,50]，[0，33.3333]，[30.75,）。

（4）直接修改表2-1的数据，求解后得到最优解为，最优值。

（5）将数据修改回原问题，点击Edit→DeleteaConstraint，选择要删除的约束C4，ok。

点击Edit→DeleteaVariable，选择要删除的变量X3，ok。

得到如表2-3的模型，求解得到最优解为，最优值。

表2-3

（6）调用原问题数据表，点击Edit→InsertaVariable，选择变量名和变量插入的位置，如图2-2，在显示的电子表格中输入数据（6,5,4,2,3），得到最优解为，最优值。

图2-2

三、实验内容：

用winQSB软件完成下列问题

1．写出对偶线性规划，变量用y表示。

2．求原问题及对偶问题的最优解。

3．分别写出价值系数cj及右端常数的最大允许变化范围。

4．目标函数系数改为C＝（5，3，6）同时常数改为b=（120，140，100），求最优解。

5．增加一个设备约束和一个变量x4，系数为（c4,a14,a24,a34,a44）=（7，5，4，1，2），求最优解。

6．在第5问的模型中删除材料2的约束，求最优解。

（三）操作步骤

1．启动线性规划与整数规划程序（LinearandIntegerProgramming），建立新问题，输入数据并存盘。

2．点击Format→SwitchtoDualForm，点击Format→SwitchtoNormalModelForm，点击Edit→VariableName，分别修改变量名为yi。

3．再求一次对偶返回到原问题，求解模型显示最优解。

查看最优表中影子价格（ShadowPrice）对应列的数据写出对偶问题的最优解。

4．在综合分析报告表中查找Allowablemin（max）对应列，写出价值系数及右端常数的允许变化范围。

5．修改模型数据并求解。

6．点击Edit→InsertaContraint插入一个约束，点击Edit→InsertaVariable插入一个变量，求解。

7．点击Edit→DeleteaContraint，选择要删除的约束C2，求解。