-单纯形法计算中的几个问题
- 格式：ppt
- 大小：601.52 KB
- 文档页数：17
下载文档原格式
合集下载
单纯形法的矩阵计算例题
1、在使用单纯形法求解线性规划问题时，初始基本可行解通常通过以下哪种方法获得？A. 两阶段法B. 高斯消元法C. 矩阵求逆D. 逐次逼近法（答案）A2、在单纯形表的迭代过程中，当所有检验数均非负时，说明当前解是？A. 无界解B. 无解C. 最优解D. 可行解但非最优（答案）C3、单纯形法中，选择进入基的变量时，通常选择检验数最小的变量，这是？A. 错误的做法B. 正确的做法，但仅当目标函数求最大值时C. 正确的做法，但仅当目标函数求最小值时D. 无论目标函数求最大还是最小，都是正确的做法（答案）B（假设题目中指的是选择绝对值最大的负检验数对应的变量进入基，若求最小值则选择正检验数）4、在单纯形迭代过程中，若出现某个基变量的值为零，而该变量在目标函数中的系数（即检验数）为正，则？A. 该问题无界B. 应立即停止迭代，因为当前解不可行C. 应将该变量从基中换出D. 这种情况不可能发生（答案）C5、单纯形法中，退出基的变量选择通常基于？A. 检验数的大小B. 基变量在约束条件中的系数比值（即比值检验）C. 目标函数中的系数D. 变量的下界或上界（答案）B6、在单纯形迭代过程中，若所有基变量的检验数均为零，则？A. 达到了最优解，且可能存在多个最优解B. 达到了最优解，且唯一C. 问题无解D. 需要进行人工变量调整（答案）A7、单纯形法中，若某个迭代步骤中发现无法找到符合条件的进入基变量（即所有检验数均非负），则？A. 当前解即为最优解B. 问题无解C. 需要引入人工变量继续迭代D. 应检查初始基本可行解的正确性（答案）A8、在构建初始单纯形表时，若目标函数为求最小化，则检验数应如何计算？A. 检验数= 目标函数系数- 约束条件右侧常数与基变量系数的乘积之和B. 检验数= 目标函数系数+ 约束条件右侧常数与基变量系数的乘积之和的相反数C. 检验数= 目标函数系数直接作为检验数D. 检验数= 约束条件左侧系数与目标函数系数的比值（答案）B（简化描述，实际计算中需考虑基变量的当前值和目标函数系数）9、单纯形法中，当某个基变量的值为负时，说明？A. 当前解不可行B. 当前解可能是最优解，但需进一步验证C. 应立即将该变量从基中换出D. 这种情况在正确执行单纯形法时不可能发生（答案）D（在正确执行时，基变量应始终非负）10、在单纯形迭代过程中，若发现某个非基变量的检验数为正，且该变量对应的约束条件为“≤”类型，则？A. 该变量应被选为进入基的变量B. 该变量不能进入基，因为其检验数为正C. 需要检查该变量的上界是否满足约束D. 该问题可能无解（答案）A（在求最大化问题时，正检验数对应的非基变量是潜在的进入基候选）。
运筹学单纯形法的例题
可行域在x1+3x2=7与4x1+2x2=9之下__
3
.
05.07.2020
练习㈠用图解法
5
4 4x1+x2=9
3
2
1 (2.25,0)
0
1
2
3
4
5
6
7
4
.
05.07.2020
练习㈠. 单纯形表
1 31 0 7 4 20 1 9
填入第一个约束的数据.
填入第二个约束的数据.
5
.
05.07.2020
❖至少有一个非基变量的检验数为正,但它的系 数全为非正,则无有限最优解；
❖所有非基变量的检验数全为非正，已有最优解， 但若其中至少有一个的检验数为0，且它的系 数中有2正4 的，则可能有. 无穷多个最优0解5.07.。2020
基变量列中_x_5_换为_x_1_,
改CB列,_-_M__换为_4__.
Excel
17
.
05.07.2020
练习㈢用图解法和单纯形法求 如下线性规划问题的最优解：
Max z =4 x1 + x2 x1 + 3x2 ≥ 7
s.t. 4x1 + 2x2 ≥ 9 x1 , x2 ≥ 0
可行域在直线 x1+3x2=7之上__
s.t. 4x1 + 2x2 -x4+x6=9
基引是进谁两?个这 理x“1里?,x人“2 ,工x-”3 如变,x4何量,x5处”,x6≥0
x5 ,x620
.
05.07.2020
练习㈢.用单纯形法
Max z=4x1+x2+0x3+0x4 -Mx5 –Mx6
单纯形法的计算题
单纯形法的计算题
单纯形法是一种求解线性规划问题的数学方法。
下面是一道使用单纯形法求解的线性规划问题的例子：
求最大化目标函数z = -2x1 + 3x2，
约束条件：
1. x1 + x2 <= 4
2. 3x1 + 4x2 <= 12
3. x1, x2 >= 0
用单纯形法求解此问题，需要进行以下步骤：
1. 建立初始单纯形表格：根据约束条件，我们可以确定初始单纯形表格的基变量和非基变量。
2. 计算目标函数的系数和：根据目标函数的系数，我们可以计算出目标函数的系数和。
3. 检查退出条件：如果目标函数的系数和大于零，则无法找到可行解；如果目标函数的系数和小于等于零，则已经找到最优解。
4. 迭代计算：如果未达到最优解，需要继续迭代计算，更新单纯形表格，直到找到最优解为止。
5. 输出结果：最终的单纯形表格中，最优解对应的基变量和非基变量的值即为所求的最优解。
具体到这个例子中，可以使用线性规划软件包或编程语言实现单纯形法来求解。
通过输入约束条件和目标函数，可以得到最优解。
第四节 单纯形法的计算步骤
上表中由于所有σ 上表中由于所有 j>0 ，表明已求得最优解 x1=4， x2=2， x3=0， x4=0， x5=0， x6=4， ， ， ， ， ， ， Z=14。 。 当确定x 为换入变量计算θ值时 值时， ◆当确定 6为换入变量计算 值时，有两个相 同的最小值： 同的最小值：2/0.5=4，8/2=4。任选其中一 ， 。 个作为换出变量时， 个作为换出变量时，则下面表中另一基变 量的值将等于0，这种现象称为退化 退化。 量的值将等于 ，这种现象称为退化。含有 一个或多个基变量为0的基可行解称为 的基可行解称为退化 一个或多个基变量为 的基可行解称为退化 的基可行解。 的基可行解。
18
迭代
xB
次数
cB
x1
x2
x3
x4
x5 bi
θi
50
x1
100
0
0
0
50 0 100
1 0 0
0
0 0 1
0
1 -2 0
- 50
0 1 0
0
-1 1 1
- 50
50 50 250 -27500
2
x4 x2
σj
2010年8月
管理工程学院
18
《运筹学》 运筹学》
19
所有的检验数 σ j ≤ 0, 此基本可行解： 此基本可行解：
2010年8月
管理工程学院
5
《运筹学》 运筹学》
6
c1 … cl b b1´
⋮
c j→ cB c1
⋮
… cm … xm …0 …⋮ 0 …1 …
⋮
…cj …xj …a1j´ …⋮ a2j´ …⋮ amj´
… ck … cn … xk …xn …0 …⋮ 1 …0
单纯形法选择题
当然，我可以为您提供关于单纯形法选择题的解答。
为了给您提供最全面的答案，我会按照题目类型和可能的解答方式进行说明。
请注意，以下回答基于一些假设和简化，实际情况可能会有所不同。
问题类型：单纯形法基础概念选择题问题：1. 在单纯形法中，以下哪个选项描述正确地描述了基本可行解的概念？A. 基本可行解是线性规划问题的唯一解。
B. 基本可行解是线性规划问题的初始解。
C. 基本可行解是最优解的一种可能状态。
D. 基本可行解是在最优解不存在时的解。
解答：基本可行解是线性规划问题的初始解，即在单纯形法中，初始时选择的基向量，对应的非基变量值被设置为零，其他变量在可行域内选择最优值。
基本可行解是线性规划问题的初始状态，但不是唯一解，因为可能存在多种不同的基向量选择。
2. 当使用单纯形法求解线性规划问题时，以下哪个选项描述正确地描述了最优解的存在性？A. 在任何情况下，最优解都是存在的。
B. 在大多数情况下，最优解都是存在的。
C. 在某些情况下，最优解不存在。
D. 在某些情况下，最优解存在但不可计算。
解答：最优解的存在性取决于线性规划问题的具体约束条件和目标函数。
一般来说，当线性规划问题有可行解时，最优解是存在的。
然而，在某些特殊情况下，最优解可能不存在或不可计算。
因此，正确答案是C. 在某些情况下，最优解不存在。
3. 当使用单纯形法时，以下哪个选项描述正确地描述了基本调优步骤的作用？A. 基本调优步骤是为了找到基本可行解。
B. 基本调优步骤是为了使基本可行解更接近最优解。
C. 基本调优步骤是为了找到一个基向量，使得目标函数值最小化。
D. 基本调优步骤是为了确保问题能够被成功求解。
解答：基本调优步骤是为了确保问题能够被成功求解。
通过选择一个更好的基向量（通常是使目标函数值更小的基向量），可以确保问题有更好的初始状态，从而增加了找到最优解的可能性。
因此，正确答案是D. 基本调优步骤是为了确保问题能够被成功求解。
总结：以上是对单纯形法基础概念的一些选择题解答。
运筹学单纯形法
单纯形表
max z=x1+2x2 s.t. x1+x23 x2 1 x1, x2 0
Cj CB XB b 0 0 Z X3 3 X4 1 0 1 2 0 0
标准化
max z=x1+2x2 s.t. x1+x2+ x3 =3 x2 +x4=1 x1, x2 ,x3, x40
X1 X2 X3 X4 1 0 1 1 1 2 1 0 0 0 1 0
Z=x1+2x2 x1+x2+ x3 =3 x2 +x4=1 单纯形表
Cj
1
2
0
0
单纯形法原理 单纯形表 CB XB b
z=x1+2x2 x3 =3-x1-x2 x4=1 -x2
x2进基，x4离基
X1 X2 X3 X4
3/1 11
0
1 0
1 1
1 1
2 2 0 1 0 2 0 1 0 0 1 0 -1 0
max z=x1+2x2 s.t. x1+x2+x3 =3 x2 +x4=1 x1, x2, x3, x40
x1=0
(x1,x2,x3,x4)= (0,1,2,0), z=2 C (x1,x2,x3,x4)= (2,1,0,0), z=4,最优解
B
x4=0 x3=0
(x1,x2,x3,x4)= (0,0,3,1), z=0
1 0
0 0
0 1
0
CB XB b 0 2 Z Cj CB XB b 1 2 Z X1 2 X2 1 4 X3 2 X2 1 2 1 1 0 0
X1 X2 X3 X4 1 0 1 1 0 0 0 -1 1 -1
-单纯形法计算中的几个问题
(1-37)
将（1-36）逐个代入(1-37)并整理得到
1 2
Ac
1 2
Ap
1 2
AH
0
1 4
Ac
3 4
Ap
1 4
AH
0
3 4
Bc
1 4
Bp
1 4
BH
0
1 2
Bc
1 2
Bc
1 2
BH
0
表1-15表明这些原材料供应数量的限额,加入到产品A、B、D的 原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不 超过60kg。由此
§1-7.单纯形法计算中的几个问题
一、单纯形法计算中的几个问题 1.目标函数极小化时解的最优性判别
对于目标函数值极小化的线性规划问题，这时只需以 所有检验数作为判别表中解是否最优的标志。 2.退化
按最小比值来确定换出基的变量时，有时出现存在 两个以上相同的最小比值，从而使下一个表的基可行解 中出现一个或多个基变量等于零的退化解。退化解的出 现原因是模型中存在多余的约束，使多个基可行解对应 同一顶点。当存在退化解时，就有可能出现迭代计算的 循环，尽管可能性极其微小。为避免出现计算的循环， 1974年勃兰特（Bland）提出了一个简便有效的规则：
单价(元/kg) 50
35
D
不限
25
原材料名称
C P H
每天最多供应量(kg) 单价(元/kg)
100
65
100
25
60
35
解 如以 A表c 示产品A中C的成分，Ap 表示产品A中P的成分，依次
类推。有(1-36)
Ac
1 2
A, Ap
1 4
单纯形法计算方法存在的问题
204 2011.112011年11月科教纵横按照单纯形法的计算方法，有些数学模型在求解时会存在一些不必要的转换，使计算量相对增加。
下面通过两个例子的计算说明。
例1数学模型的计算，用单纯形法计算其标准形式为：单纯形法计算表如表1。
表1例1计算表表中a＝－2M－3，b＝6M－3，c＝－M－3/2，d＝－M+1/2，e＝－M+3/4，f＝－M－1/4。
例1有惟一最优解为：X*＝（0 2.5 1.5）T，Z*＝1.5，其中第二次转换是用x1换x7，第三次转换是用x3换x1，相当于第二次转换是多余的计算。
表1有207个字。
类似这样的例子，在计算时完全可以避免，这就是对单纯形法计算时的方法做适当的改变。
在确定换入变量时不一定把最大的检验数对应的非基变量做为换入变量，而应该看哪种变量对应的费效比高。
例1计算中若第二次转换是用x3换x7比用x1换x7更有利，一是单位产品对第一种资源消耗量少（4和6），二是x3是赚的而x1是赔的（1和－3）。
因此例1的计算可按表3进行。
表3有162个字，比表1少45个字，计算量少了25%。
因此我们在学习中只要灵活掌握知识，而不是死学书本，才能学到知识的真谛。
表3例1简化计算表作者单位：郑州大学西亚斯国际学院商学院作者简介：李小林（1964.06— ），男，陕西周至，郑州大学西亚斯国际学院商学院教师，副教授，硕士研究生，主要从事统计学和运筹学的教学和研究工作。
单纯形法计算方法存在的问题文/李小林摘 要：通过举例说明单纯形法计算方法存在的问题，供相关学习者在使用中借鉴。
关键词：单纯形；计算方法；存在问题；改进方法中图分类号：O1-0 文献标识码：A 文章编号：1006-4117（2011）11-0204-01。
1-5 单纯形法的进一步讨论
B 1b B 1NX N
令非基变量XN=0，XB=B—1b，由 B是 可行基的假设，则得到
基本可行解
X=(B－1b，0)T
将目标函数写成
Z
(CB
,
CN
)
X X
B N
CB X B
CN X N
CB (B1b B1NX N ) CN X N
CBB1b (CN CBB1N )) X N
MaxZ=-3x1+x3 x1+ x2+ x3≤4
-2x1+ x2- x3≥1 3x2+x3=9
xi ≥0,j=1,2,3
求解辅助问题，得到辅助 问题的最优解
引进人工变量x6，x7，构造辅助 问题，辅助问题的目标函数为
所有人工变量之和的极小化
MaxW=-x6-x7
x1+ x2+ x3+x4
=4
-2x1+ x2-x3 -x5+x6 =1
z zσ
XB … 0T …
xj cj - zj
… RHS … z0
XB xB I …
Yj
…b
基变量在目标函数中的系数等于0， 基变量在约束条件中的系数是一个单位矩阵
单纯形表的结构
注意： Z行中有m 个0，它们与基变量相对应。一般情况下，这m 个0分散在Z行的各列中，并与基变量相对应。
其余m行中有一个m阶单位矩阵I，其各列与基变量相对应。 一般情况下，组成I的各列分散在表的各列中，它们与基变 量相对应。
X1 1
0
a1
0
a2 a6
X2 0
1
1
0
-2
最优化--单纯形法解例
例1 用单纯形法解下列问题：解：将原问题化成标准形：x 4与添加的松弛变量x 5，x 6在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为X =（0, 0, 0,10, 8, 4）T列出初始单纯形表，见表1。
22x 2的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。
242)24,110(m in ===θ 因此确定2为主元素（表1中以防括号[]括起），意味着将以非基变量x 2去置换基变量x 6，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将x 2的系数列(1, -1, 2)T 变换成x 6的系数列(0, 0, 1)T ，变换之后重新计算检验数。
变换结果见表2。
1231234123123min 2..210,248,244,0,1,,4.j x x x s t x x x x x x x x x x x j -++-+=-+≤-+-≤≥=123123412351236max 2..210,248,244,0,1,,6.j x x x s t x x x x x x x x x x x x x j -+-+-+=-++=-+-+=≥=检验数σ3=3>0，当前基可行解仍然不是最优解。
继续“换基”，确定2为主元素，即以非基变量x 3置换基变量x 5。
变换结果见表3。
此时，3个非基变量的检验数都小于0，σ1= -9/4，σ5= -3/2，σ5= -7/4，表明已求得最优解：T)0,0,8,5,12,0(=*X 。
去除添加的松弛变量，原问题的最优解为：T )8,5,12,0(=*X ,最小值为-19例2 用大M 法求解下列问题：12312312313min 3..211,243,21,0,1,,3.j x x x s t x x x x x x x x x j +--+≤+-≥-=≥=解 引进松弛变量x 4、、剩余变量x 5和人工变量x 6、x 7，解下列问题：1234567123412356137min 300()..211243210,1,2,,7j x x x x x M x x s t x x x x x x x x x x x x x j +-++++-++=+--+=-+=≥=用单纯形法计算如下：由于σ1<σ2< 0，说明表中基可行解不是最优解，所以确定x 1为换入非基变量；以x 1的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（1）当存在多个 j 0 时，始终选取下标值为最小 的变量作为换入变量；（2）当计算值出现两个 以上相同的最小比值时，始终选取下标值为最小 的变量作为换出变量。
3.无可行解的判别
本章第四节单纯形法迭代原理中，讲述了用 单纯形法求解时如何判别问题结局属唯一最优解、 无穷多最优解和无界解。当线性规划问题中添加 人工变量后，无论用大M法或两阶段法，初始单 纯形表中的解因含非零人工变量，故实质上是非 可行解。当求解结果出现所有时，如基变量中仍 含有非零的人工变量（两阶段法求解时第一阶段 目标函数值不等于零），表明问题无可行解。
的逆阵，将J中的第L个数改为k ，转入 （2）。
§1-9.单纯形法应用实例
例1-12 合理利用线材问题
现要做100套钢架，每套用长为2.9m，2.1m和1.5m的 元钢各一根，已知原料长7.4m，问应如何下料，使用 的原材料最省。
解 最简单做法是，在每一根原材料上截取2.9m， 2.1m和1.5m的元钢各一根组成一套，每根原材料 省下料头0.9m。为了做100套钢架，需用原材料 100根，有90米料头,若改为用套裁，这可以节约 原材料。下面有几种套裁方案，都可以考虑采用， 见表1-13。
0,
得到最优解，停止；否则，记为k主元列，
转入（4）。
（4）计算 B1 pk ,若B1 pk 0， 得无界解，停 止：否则转入（5）。
（5）求
min i
{((BB11pbk))
|
(B 1
pk
)i
0}
(B 1b)l (B 1 pk )l
并记l为主元行。 （6）构造矩阵 Elk用 Elk 左乘B 1 得到新基
2 6Biblioteka 11 0以 表x31,-x115。为表基中变当量所列有c出j 初 z始j 单0纯形表时，，进基行变迭量代中计仍算含有，非过零程的见
人工变量x，5 2 故例1-12的线性规划问题无可行解。
cj
2
1 0 0 -M
CB 基 b
0 -M
xx53
2 6
cj zj
2 -M
x1
x5
2 2
cj zj
min z 0x1 0.1x2 0.2x3 0.3x4 0.8x5
x1 2x2
x4
100
s.t.
3x1
2x3 x2 2x3
2x4 x5 3x5
100 100
x1, x2 , x3 , x4 , x5 0
计算得到最优下料方案是：按Ⅰ 方案下料30根；Ⅱ方案 下料10根；Ⅳ方案下料50根。即需90根原材料才能制造 100套钢架。
§1-7.单纯形法计算中的几个问题
一、单纯形法计算中的几个问题 1.目标函数极小化时解的最优性判别
对于目标函数值极小化的线性规划问题，这时只需以 所有检验数作为判别表中解是否最优的标志。 2.退化
按最小比值来确定换出基的变量时，有时出现存在 两个以上相同的最小比值，从而使下一个表的基可行解 中出现一个或多个基变量等于零的退化解。退化解的出 现原因是模型中存在多余的约束，使多个基可行解对应 同一顶点。当存在退化解时，就有可能出现迭代计算的 循环，尽管可能性极其微小。为避免出现计算的循环， 1974年勃兰特（Bland）提出了一个简便有效的规则：
2 . 单纯形法计算步骤的框图见page35图1-
§1-8修正单纯形法
一、修正单纯形法的基本思想
运用单纯形法时，如果知道可行基的逆 B 就
能利用 B 原始数据计算基变量的取值及检验
数，从而能够确定一个基本可行解，并判断它
是否为最优解。因此在整个计算过程中，只要
保存原始数据和现行的逆即可。修正单纯刑法
(1-37)
将（1-36）逐个代入(1-37)并整理得到
1 2
例1-13 配料问题
某工厂要用三种原材料C、P、H混合调配出三种 不同规格的产品A、B、C。已知产品的规格要 求，产品单价，每天能供应的原材料数量及原材 料单价，分别见表1-14和表1-15，该厂应如何安 排生产，使利润收入为最大？
产品名称 A
B
规格要求
原材料C不少于50% 原材料P不少于25% 原材料C不少于25% 原材料P不少于50%
x1 x2 x3 x4 x5
[1] 1 1 0 0
2
2 0 -1 1
2+2M 1+2M 0 -M 0
1 1 100 0 0 -2 -1 1
0 -1 -2-2M -M 0
二、单纯形法小结
1. 对给定的线性规划问题应首先化为标准形式， 选取或构造一个单位矩阵作为基，求出初始基 可行解并列出初始单纯形表。对各种类型线性 规划问题如何化为标准形式及如何选取初始基 变量可参见page35表1-14。
例1-11 用单纯形法求解线性规划问题
max z 2x1 x2
s.t.
2
x1 x1
x2 2 2x2 6
x1 , x 0
解 用图解法可看出本例无可行解。现用单纯形法求解，在添加松
驰变量和人工变量后，模型可写成
max z 2x1 x2 0x3 0x4 Mx5
s.t. 2x1x1 x22x2x3 x4 x5
单价(元/kg) 50
35
D
不限
25
原材料名称
C P H
每天最多供应量(kg) 单价(元/kg)
100
65
100
25
60
35
解 如以 A表c 示产品A中C的成分，Ap 表示产品A中P的成分，依次
类推。有(1-36)
Ac
1 2
A, Ap
1 4
A, Bc
1 4 B, Bp
1 B(1-36)
2
这里
Ac Ap AH A Bc B p BH B
为了得到100套钢架，需要混合使用各种下料方案。设 按Ⅰ方案下料的原材料要数为，Ⅱ方案为，Ⅲ方案为， Ⅳ方案为，Ⅴ方案为。根据表1-13的方案，可列出以下 数学模型：
方案 下料数(根) Ⅰ Ⅱ Ⅲ Ⅲ Ⅴ 长度m
2.9
12
1
2.1
2 21
1.5
31
2
3
合计 7.4 7.3 7.2 7.1 6.6 料头 0 0.1 0.2 0.3 0.8
的基本思想就是给定初始基本可行基后，通过
修改新基的逆
B
进而完成其他运算。在整个
计算过程中，始终保持先行基的逆B 。
二、修正单纯形发的步骤
（1）求一个初始基B并求出它的逆B ， 写出基底描述J。
（2）求单纯形乘子Y (CBT B )T 。
（3）求 j c j Y T p j
及max{ jJ
j } k ,若 k