单纯形法的矩阵计算例题

1、在使用单纯形法求解线性规划问题时，初始基本可行解通常通过以下哪种方法获得？

A. 两阶段法

B. 高斯消元法

C. 矩阵求逆

D. 逐次逼近法

（答案）A

2、在单纯形表的迭代过程中，当所有检验数均非负时，说明当前解是？

A. 无界解

B. 无解

C. 最优解

D. 可行解但非最优

（答案）C

3、单纯形法中，选择进入基的变量时，通常选择检验数最小的变量，这是？

A. 错误的做法

B. 正确的做法，但仅当目标函数求最大值时

C. 正确的做法，但仅当目标函数求最小值时

D. 无论目标函数求最大还是最小，都是正确的做法

（答案）B（假设题目中指的是选择绝对值最大的负检验数对应的变量进入基，若求最小值则选择正检验数）

4、在单纯形迭代过程中，若出现某个基变量的值为零，而该变量在目标函数中的系数（即检验数）为正，则？

A. 该问题无界

B. 应立即停止迭代，因为当前解不可行

C. 应将该变量从基中换出

D. 这种情况不可能发生

（答案）C

5、单纯形法中，退出基的变量选择通常基于？

A. 检验数的大小

B. 基变量在约束条件中的系数比值（即比值检验）

C. 目标函数中的系数

D. 变量的下界或上界

（答案）B

6、在单纯形迭代过程中，若所有基变量的检验数均为零，则？

A. 达到了最优解，且可能存在多个最优解

B. 达到了最优解，且唯一

C. 问题无解

D. 需要进行人工变量调整

（答案）A

7、单纯形法中，若某个迭代步骤中发现无法找到符合条件的进入基变量（即所有检验数均非负），则？

A. 当前解即为最优解

B. 问题无解

C. 需要引入人工变量继续迭代

D. 应检查初始基本可行解的正确性

（答案）A

8、在构建初始单纯形表时，若目标函数为求最小化，则检验数应如何计算？

A. 检验数 = 目标函数系数 - 约束条件右侧常数与基变量系数的乘积之和

B. 检验数 = 目标函数系数 + 约束条件右侧常数与基变量系数的乘积之和的相反数

单纯形法例题

单纯形法例题

1、 例1、目标函数 max z=2𝒙𝟏+3𝒙𝟐

约束条件：{ 𝒙𝟏+𝟐𝒙𝟐≤𝟖𝟒𝒙𝟏≤𝟏𝟔𝟒𝒙𝟐≤𝟏𝟐𝒙𝟏，𝒙𝟏≥𝟎}

解：首先要将约束条件化为标准形：由此可以看出我们需要加上三个松弛变量，𝒙𝟑，𝒙𝟒，𝒙𝟓，并且它们都大于等于𝟎.得到的标准形式为：

max z=2𝒙𝟏+3𝒙𝟐+

0𝒙𝟑+0𝒙𝟒+0𝒙𝟓

{ 𝒙𝟏+𝟐𝒙𝟐+𝒙𝟑＝𝟖𝟒𝒙𝟏+𝒙𝟒=𝟏𝟔𝟒𝒙𝟐+𝒙𝟓＝𝟏𝟐𝒙𝟏，𝒙𝟐，𝒙𝟑，𝒙𝟒，𝒙𝟓≥𝟎}

然后要将其初始的单纯形表画出来：

𝒄𝒋 2 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓

0 𝒙𝟑 8 1 2 1 0 0 4

0 𝒙𝟒 16 4 0 0 1 0 -

0 𝒙𝟓 12 0 [𝟒] 0 0 1 3

𝒄𝒋−𝒛𝒋 2 3 0 0 0

由初始单纯形表可以看出，𝒙𝟐为换入变量， 𝒄𝒋−𝒛𝒋 2 0 0 0 -3/4

由于在检验数中仍然存在大于等于0的数，而且P1，P5的坐标中有正分量存在，所以需要继续进行迭代运算。通过观察可以看出主元素为1，换入变量为𝒙𝟏，换出变量为𝒙𝟑，故得到的单纯形表如下：

𝒄𝒋 2 3 0 0 0 𝜽𝒊 𝑪𝑩 𝑿𝑩 b 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓

2 𝒙𝟏 2 1 0 1 0 -1/2 -

0 𝒙𝟒 8 0 0 -4 1 [𝟐] 4

3 𝒙𝟐 3 0 1 0 0 1/4

12

𝒄𝒋−𝒛𝒋 0 0 -2 0 1/4

由于检验数中存在正数，且P5和P3中有正分量存在，所以需要继续迭代(换入变量为𝒙𝟓，换出变量为𝒙𝟒：得到单纯形表如下：

第２９卷第３期　２０１３年６月　大　学　数　学　

ＣＯＬＬＥＧＥ　ＭＡＴＨＥＭＡＴＩＣＳ　Ｖｏ１．２９，№．３　Ｊｕｎ．２０１３　

对于单纯形法矩阵描述的认识　

贺素香　，　

（１．武汉理工大学理学院，湖北武汉４３００７０；　郑　杰　

２．武汉理工大学经济学院，湖北武汉４３００７Ｏ）　

［摘　要］从修正单纯形法的提出、对偶单纯形法的出现、对偶问题最优解的确定以及灵敏度分析的基本　依据等四个方面阐述了对单纯形法矩阵描述的认识，充分显示出单纯形法矩阵描述在线性规划发展中的重　要性．　［关键词］（对偶）单纯形法；矩阵描述；修正单纯法；对偶问题；灵敏度分析　［中图分类号］０２２１　［文献标识码］Ｃ　［文章编粤］１６７２—１４５４（２０１３）０３—００７６—０５　

１　引　言　

线性规划是运筹学中一个基础而又相对比较成熟的重要分支．１９４７年Ｄａｎｔｚｉｇ［１　提出了易于在计　算机上实现的单纯形法．由于单纯形法的有效性以及电子计算机软硬件技术的迅速发展，近六十年多　来一直在几乎所有领域得到广泛应用［２　］．对于大规模的线性规划问题，尽管它受到内点算法Ｌ３　的挑　

战，但单纯形法以其简单有效性仍受到广大用户的青睐．　单纯形法的矩阵描述可谓对单纯形法研究的一个升华，不仅促进了修正单纯形法与对偶单纯形法　

的诞生，同时在线性规划基本性质的基础上，为由线性规划原问题最优单纯形表直接确定其对偶问题　最优解提供了一种途径，也为线性规划的灵敏度分析提供了基本依据．本文将从上述这四个方面详细　

阐明单纯形法矩阵描述在线性规划发展中所起的重要作用，可让广大运筹学学习者对单纯形法矩阵描　述具有充分的理解，也可丰富某些运筹学教材在这一方面的内容．　

２单纯形法的矩阵描述　

考虑线性规划问题的标准型Ⅲ　

ｍａｘ　ｚ—ＣＸ。　Ｓ．ｔ．ＡＸ—ｂ，　（２．１）　Ｘ≥０　，　其中ｃ　，Ｘ∈　”，Ａ∈　，ｂ∈　，且Ｒ（Ａ）－－－ｍ．根据单纯形法的基本思想，假设第ｋ次迭代中基可　行解为ｘｃ　，其中基变量为ｘ‰，非基变量为ＸＮ　，相应的基矩阵为Ｂ　ｃ　，非基矩阵为Ｎｃ　，对应　的目标函数系数为　和　，则由基可行解的定义与分块矩阵的乘法，约束方程组ＡＮ—ｂ可　表示为　

单纯形法的计算步骤例题

单纯形法是一种用于线性规划问题的求解方法，它通过不断地移动解空间中的顶点，逐步逼近最优解。下面我将通过一个简单的例题来说明单纯形法的计算步骤。

考虑以下线性规划问题：

最大化目标函数 Z = 3x1 + 4x2

约束条件：

2x1 + x2 <= 10

x1 + 2x2 <= 8

x1, x2 >= 0

首先，我们将这个线性规划问题转化为标准型，引入松弛变量将不等式约束转化为等式约束。得到如下形式：

最大化目标函数 Z = 3x1 + 4x2

约束条件：

2x1 + x2 + x3 = 10

x1 + 2x2 + x4 = 8

x1, x2, x3, x4 >= 0

然后，我们构建初始的单纯形表格，包括目标函数系数矩阵、系数矩阵、单位矩阵和右端常数向量。

初始单纯形表格如下：

基变量 x1 x2 x3 x4 常数

x3 2 1 1 0 10

x4 1 2 0 1 8

Z -3 -4 0 0 0

接下来，我们通过单纯形法进行迭代计算，每次迭代都要找到一个入基变量和一个出基变量，然后更新单纯形表格，直到满足最优解的条件。

在这个例子中，我们不再继续举例，因为单纯形法的计算步骤较为复杂，需要逐步进行迭代计算。希望这个简单的介绍对你有所帮助。