第二章 单纯形法

第二章单纯形法

第二章单纯形法

单纯形法的一般原理

表格单纯形法

借助人工变量求初始的基本可行解

单纯形表与线性规划问题的讨论

改进单纯形法

考虑到如下线性规划问题

其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。

根据线性规划基本定理：

如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界，

则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。

这个重要的定理启发了Dantzig的单纯形法，

即将寻优的目标集中在D的各个顶点上。

单纯形法的一般原理

Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。

其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下：

（1）寻找一个初始的基本可行解。

（2）检查现行的基本可行解是否最优，如果为最优，

则停止迭代，已找到最优解，否则转一步。

（3）移至目标函数值有所改善的另一个基本可行解，

然后转会到步骤（2）。

确定初始的基本可行解

确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定

为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即

Ａ=（ＢＮ），其中

Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量

构成的可行基，

Ｎ=(Ｐm+1，Pm+2，…Pn)为非基变量xm+1，xm+2，…xn的

系数列向量构成的矩阵。

所以约束方程就可以表示为

用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：

若令所有非基变量, 则基变量

由此可得初始的基本可行解

问题：

要判断m个系数列向量是否恰好构成一个基并不是一件容易的事。

基由系数矩阵Ａ中m个线性无关的系数列向量构成。

但是要判断m个系数列向量是否线性无关并非易事。

即使系数矩阵Ａ中找到了一个基B，也不能保证该基恰好是可行基。

因为不能保证基变量ＸB=Ｂ-1b≥0。

为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。

但是求逆阵Ｂ-1也是一件麻烦的事。

结论：在线性规划标准化过程中设法得到一个m阶单位矩阵I作为初始可行基Ｂ，

若在化标准形式前，约束方程中有“≥”不等式，

那么在化标准形时除了在方程式左端减去剩余变量使不等式变

成等式以外，还必须在左端再加上一个非负新变量，称为

人工变量．

若在化标准形式前，约束方程中有等式方程，那么可以直接在

等式左端添加人工变量。

为了设法得到一个m阶单位矩阵I作为初始可行基Ｂ，可在性规划标准化过程中作如下处理：

若在化标准形式前，m个约束方程都是“≤”的形式，

那么在化标准形时只需在一个约束不等式左端都加上一个松弛变

量xn+i (i=12…m)。

判断现行的基本可行解是否最优

假如已求得一个基本可行解

将这一基本可行解代入目标函数，可求得相应的目标函数值

其中分别表示基变量和

非基变量所对应的价值系数子向量。

要判定是否已经达到最大值，只需将

代入目标函数，使目标函数用非基变量表示，即：

其中称为非基变量ＸN的检验向量，它的各个分量称为检验数。若σN的每一个检验数均小于等于0，即σN ≤0，那么现在的基本可行解就是最优解。

定理1：最优解判别定理

对于线性规划问题

若某个基本可行解所对应的检验向量，则这个基本可行解就是最优解。

定理2：无穷多最优解判别定理

若是一个基本可行解，所对应的检验向量

，其中存在一个检验数σm+k=0，

则线性规划问题有无穷多最优解。

基本可行解的改进

如果现行的基本可行解Ｘ不是最优解，即在检验向量

中存在正的检验数，则需在原基本可行解Ｘ的基础上寻找一个新的基本可行解，并使目标函数值有所改善。具体做法是：

先从检验数为正的非基变量中确定一个换入变量，使它从非基变量变成基变量（将它的值从零增至正值），

再从原来的基变量中确定一个换出变量，使它从基变量变成非基变量（将它的值从正值减至零）。

由此可得一个新的基本可行解，由

可知，这样的变换一定能使目标函数值有所增加。

换入变量和换出变量的确定：

换入变量的确定—最大增加原则

假设检验向量，

若其中有两个以上的检验数为正，那么为了使目标函数值增加得快些，通常要用“最大增加原则”，即选取最大正检验数所对应的非基变量为换入变量，即若

则选取对应的为换入变量，

由于且为最大，

因此当由零增至正值，

可使目标函数值

最大限度的增加。

换出变量的确定—最小比值原则

如果确定为换入变量，方程

其中为Ａ中与对应的系数列向量。

现在需在中确定一个基变量为换出变量。

当由零慢慢增加到某个值时，的非负性可能被打破。

为保持解的可行性，可以按最小比值原则确定换出变量：

若

则选取对应的基变量为换出变量。

定理3：无最优解判别定理

若是一个基本可行解，有一个检验数，

但是，则该线性规划问题无最优解。

证：令，则得新的可行解

将上式代入

因为 , 故当λ→+∞时，Z→+∞。

用初等变换求改进了的基本可行解

假设Ｂ是线性规划的可行基，则令非基变量，则基变量。

可得基本可行解。

用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等“行变换”。变换的结果是将系数矩阵Ａ中的可行基Ｂ变换成单位矩阵I，把非基变量系数列向量构成的矩阵Ｎ变换成，把资源向量b变换成。

且改进了的基本可行解只是在Ｘ的基变量的基础上用一个换入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵I中的单位向量。为了求得改进的基本可行解，只需对增广矩阵

施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。

由于行初等变换后的方程组

与原约束方程组或同解

例1

解：

(１)确定初始的基本可行解。

，基变量，非基变量。

(2) 检验是否最优。

检验向量

因为σ1=3，σ3=4 均大于零，

所以不是最优解。

（3）基本可行解的改进

①??? 选取换入变量

因为max{3，4}=4，取x3为换入变量。

②??? 选取换出变量

且，

选取x4为换出变量.

（4）求改进了的基本可行解

对约束方程组的增广矩阵施以初等行变换，使换入变量x3所对应的系数列向量变换成换出变量x4所对应的单位向量 , 注意保持基变量x5的系数列向量为单位向量不变。

第一行除以２

第二行减去第一行——————————————————————————

可得改进的基本可行解。

，基变量，非基变量。

基本可行解

目标函数值

易见目标函数值比原来的Z=-1增加了，再转向步骤(2)

（2）检验是否最优。

检验向量

因为，

所以仍不是最优解。

（3）基本可行解的改进

①??? 选取换入变量

因为，取为换入变量。

②??? 选取换出变量

且，

选取为换出变量.

（4）求改进了的基本可行解

对约束方程组的增广矩阵施以初等行变换，使换入变量所对应

的系数列向量变换成换出变量所对应的单位向量 ,

第二行乘以２/５

第一行减以第二行的１/２倍

——————————————————————————

可得改进的基本可行解。

，基变量，非基变量

基本可行解

目标函数值比Z=15增加了，再转向步骤(2)

（2）检验是否最优。

检验向量

因为所有检验数均小于零，

所以是最优解，

表格单纯形法

通过例１我们发现，在单纯形法的求解过程中，有下列重要指标：每一个基本可行解的检验向量

根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。

每一个基本可行解所对应的目标函数值

通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。

在单纯形法求解过程中，每一个基本可行解Ｘ都以某个经过初等行变换的约束方程组中的单位矩阵Ι为可行基。

当Ｂ=Ｉ时，Ｂ-1=Ｉ，易知：

可将这些重要结论的计算设计成如下一个简单的表格，

即单纯形表来完成：

CN- CBN 0

CBb

Z

θ1

θ2

.

.

θm

N

I

b1

b2

.

.

bm

X1

X2

?

Xm

C1

C2

.

.

Cm

X m+1 Xm+2 ··· Xn

X1 X2 ··· Xm

b

XB

CB

θ

CN

C

例2、试利用单纯形表求例1中的最优解解：

得初始的单纯形表：

初始基本可行解，Z= -1，

1 2 2 1 0 8

x4

-1

3 0

4 0 0 -1

Z

3 4 1 0 1 7

x5

1

x1 x2 x3 x4 x5 b

XB

CB

Θ

5 2 3 -1 1 C

换入变量，换出变量，２为主元进行旋转变换

基本可行解，Z= 15，

1/2 1 1 1/2 0

4

x3

3

1 -4 0 -

2 0 15

Z

5/2 3 0 -1/2 1

3

x5

1

x1 x2 x3 x4 x5

b

XB

CB

Θ

5 2 3 -1 1 C

1 2 2 1 0

8

x4

-1

3 0

4 0 0 -1

Z

3 4 1 0 1 7

x5

1

x1 x2 x3 x4 x5 b

XB

CB

Θ

5 2 3 -1 1 C

8/2

7/1

最优解最优值

换入变量，换出变量，５/２为主元进行旋转变换

4/1/2

1/2 1 1 1/2 0

4

x3

3

1 -4 0 -

2 0 15

Z

3/5/2

5/2 3 0 -1/2 1

3

x5

1

x1 x2 x3 x4 x5

b

XB

CB

Θ

5 2 3 -1 1 C

0 2/5 1 3/5 -1/5

17/5

x3

3

0 -26/5 0 -9/5 -2/5

81/5

Z

1 6/5 0 -1/5 2/5

6/5

x1

5

x1 x2 x3 x4 x5 b

XB

CB

Θ

5 2 3 -1 1 C

例3、用单纯形方法求解线性规划问题

第二章 单纯形法

第二章单纯形法 第二章单纯形法 单纯形法的一般原理 表格单纯形法 借助人工变量求初始的基本可行解 单纯形表与线性规划问题的讨论 改进单纯形法 考虑到如下线性规划问题 其中Ａ一个m×n矩阵，且秩为m，ｂ总可以被调整为一个m维非负列向量，Ｃ为n维行向量，Ｘ为n维列向量。 根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。 这个重要的定理启发了Dantzig的单纯形法， 即将寻优的目标集中在D的各个顶点上。 单纯形法的一般原理 Dantzig的单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。

其基本思路是从一个初始的基本可行解出发，寻找一条达到最优基本可行解的最佳途径。单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。 确定初始的基本可行解 确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m个系数列向量恰好构成一个可行基，即 Ａ=（ＢＮ），其中 Ｂ=（Ｐ1，Ｐ2，…Ｐm）为基变量x1，x2，…xm的系数列向量 构成的可行基， Ｎ=(Ｐm+1，Pm+2，…Pn)为非基变量xm+1，xm+2，…xn的 系数列向量构成的矩阵。 所以约束方程就可以表示为 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得：

单纯形法的计算方法

第4章 单纯形法的计算方法单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代,直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z = 从Pj ( j = 1 , 2 , ? , n)中一般能直接观察到存在一个初始可行基 （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 及 ( i = 1 , 2 , ? , m; j = 1 , 2 , ? , n)进行编号, 则可得下列方程组 显然得到一个m×m单位矩阵 以B 作为可行基。将上面方程组的每个等式移项得 令由上式得 又因 ≥0, 所以得到一个初始基可行解 （3）第三种情况：对所有约束条件是“ ≥”形式的不等式及等式约

束情况, 若不存在单位矩阵时, 就采用人造基方法。即对不等式约束减去一个非负的剩余变量后, 再加上一个非负的人工变量; 对于等式约束再加上一个非负的人工变量, 总能得到一个单位矩阵。 4.2 最优性检验和解的判别 对线性规划问题的求解结果可能出现唯一最优解、无穷多最优解、无界解和无可行解四种情况, 为此需要建立对解的判别准则。一般情况下, 经过迭代后可以得到： 将上代入目标函数，整理后得 令 于是 再令 则 (1) 最优解的判别定理 若为对应于基B的一个基可行解，且对于一切 且有则 为最优解。称为检验数。 (2) 无穷多最优解的判别定理 若为一个基可行解， 且对于一切 且有 又存在某个非基变量的检验数，则线性规划问题有无穷多最优解。 (3) 无界解判别定理 若为一个基可行解，有一个> 0 ,并且对i = 1 , 2 , ?, m,有≤0 , 那么该线性规划问题具有无界解(或称无最优解)。 4.3 基变换

《管理运筹学》第四版 第5章 单纯形法 课后习题解析

《管理运筹学》第四版课后习题解析 第5章单纯形法 1．解： 表中a 、c 、e 、f 是可行解，f 是基本解，f 是基本可行解。 2．解： （1）该线性规划的标准型如下。 max 5x 1＋9x 2＋0s 1+0s 2+0s 3 s.t. 0.5x 1＋x 2＋s 1＝8 x 1＋x 2－s 2＝10 0.25x 1＋0.5x 2－s 3＝6 x 1，x 2，s 1，s 2，s 3≥0 （2）至少有两个变量的值取零，因为有三个基变量、两个非基变量，非基变量取零。 （3）（4，6，0，0，-2）T （4）（0，10，-2，0，-1）T （5）不是。因为基本可行解要求基变量的值全部非负。 （6）略 3.解： 令33 3x x x ''-'=，z f -=改为求f max ；将约束条件中的第一个方程左右两边同时乘以-1，并在第二和第三个方程中分别引入松弛变量5x 和剩余变量6x ，将原线性规划问题化为如下标准型： j x '、j x ''不可能在基变量中同时出现，因为单纯性表里面j x '、j x ''相应的列向 量是相同的，只有符号想法而已，这时候选取基向量的时候，同时包含两列会使 选取的基矩阵各列线性相关，不满足条件。 4．解： （1） 表5-1 0,,,,,, 24423 1863 1334 7234max 65433 21633 21543321433 214 321≥'''=-''+'--=++''+'-+-=+''+'---++-=x x x x x x x x x x x x x x x x x x x x x x x x x x x f 约束条件：

单纯形法求解线性规划的步骤

单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都就是非负的(否则无解),接下来的m 列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都就是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题就是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量与主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格与新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0)、把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行与列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化与处理(本程序所用的实例用的就是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组、用于很难预先估计矩阵的行与列,所以在程序中才了动态的内存分配、需要重载析构函数bool Is_objectLine_All_Positive(); //判断目标行就是否全部为非负数,最后一列不作考虑 这个函数用来判断就是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列就是否全部为负数或零 这个函数用来判断线性规划就是否就是无解的 bool Is_column_all_Positive(int col); //判断col列中就是否全部为正(不包括目标行)

单纯形法求解线性规划的步骤

单纯形法求解线性规划的步骤

单纯形法求解线性规划的步骤 1>初始化 将给定的线性规划问题化成标准形式,并建立一个初始表格,它最右边的单元格都是非负的(否则无解),接下来的m列组成一个m*m的单元矩阵(目标行的单元格则不必满足这一条件),这m列确定了初始的基本可行解的基本变量,而表格中行用基本变量来表示 2>最优化测试 如果目标行的所有单元格都是非负的(除了最右列中代表目标函数值的那个单元格),就可以停止了,该表格代表了一个最优解,它的基本变量的值在最右列中,而剩下的非基本变量都为0 3>确定输入变量 从目标行的前n个单元格中选择一个负的单元格(选择绝对值最大的那个)该单元格所在的列确定的输入变量及主元列 4>确定分离变量 对于主元列的每个正单元格,求出θ比率(如果主元格的单元格为负或为0,说明该问题是无解的,算法终止),找出θ比率最小的列,改行确定了分离变量和主元行 5>建立下一张表格 将主元行的所有单元格除以主元得到新的主元行,包括主元行在内的每一行,要减去改行主元列单元格和新主元行的成绩(除主元行为1外,这一步将主元列的所有单元格变成0).把主元列的变量名进行代换,得到新的单纯形表,返回第一步 为求简单 在本程序中,需要自己建立标准矩阵(比如加入松弛变量等工作需要用户自己完成),程序的输入有两种方式: 1:指定行和列,由用户自行输入每一个元素SimpleMatrix(introw=0,int col=0); 2:直接在主程序中初始化一个二维数组,然后利用构造函数SimpleMatrix(introw,int col,double **M) 来初始化和处理(本程序所用的实例用的是这种方法) 程序中主要的函数以及说明 ~SimpleMatrix(); 销毁动态分配的数组.用于很难预先估计矩阵的行和列,所以在程序中才了动态的内存分配.需要重载析构函数 bool Is_objectLine_All_Positive(); //判断目标行是否全部为非负数,最后一列不作考虑 这个函数用来判断是否已经存在最优解 bool Is_MainCol_All_Negative(int col);//判断主元列是否全部为负数或零 这个函数用来判断线性规划是否是无解的 bool Is_column_all_Positive(int col); //判断col列中是否全部为正(不包括目标行)

单纯形法求解原理过程

单纯形法 需要解决的问题： 如何确定初始基本可行解； 如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降； 如何判断一个基本可行解是否为最优解。 min f(X)=-60x1-120x2 s.t. 9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 x i≥0 (i=1,2,3,4,5) (1) 初始基本可行解的求法。当用添加松弛变量的方法把不等式约 束换成等式约束时，我们往往会发现这些松弛变量就可以作为 初始基本可行解中的一部分基本变量。 例如：x1-x2+x3≤5 x1+2x2+x3≤10 x i≥0 引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10 x i≥0 (i=1,2,3,4,5) 令x1=x2=x3=0，则可立即得到一组基本可行解 x1=x2=x3=0，x4=5，x5=10 同理在该实例中，从约束方程式的系数矩阵 中可以看出其中有个标准基，即 与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成 X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x2 若令非基变量x1=x2=0，则可得到一个初始基本可行解X0 X0=[0,0,360,300,200] T 判别初始基本可行解是否是最优解。此时可将上式代入到目标函数中，得：

F(X)=-60x1-120x2 对应的函数值为f(X0)=0。 由于上式中x1,x2系数为负，因而f(X0)=0不是最小值。因此所得的解不是最优解。 (2) 从初始基本可行解X0迭代出另一个基本可行解X1，并判断X1是否 为最优解。从一个基本可行解迭代出另一个基本可行解可分为 两步进行： 第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量； 第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。 选择进基和离基变量的原则是使目标函数值得到最快的下降和使所有的基本变量值必须是非负。 在目标函数表达式中，非基变量x1,x2的系数是负值可知，若x1,x2不取零而取正值时，则目标函数还可以下降。因此，只要目标函数式中还存在负系数的非基变量，就表明目标函数还有下降的可能。也就还需要将非基本变量和基本变量进行对换。一般选择目标函数式中系数最小的（即绝对值最大的负系数）非基变量x2换入基本变量，然后从x3，x4，x5中换出一个基本变量，并保证经变换后得到的基本变量均为非负。 当x1=0，约束表达式为： X3=360-4x2≥0 x4=300-10x2≥0 x5=200-5x2≥0 从上式中可以看出，只有选择 x2=min{}=30 才能使上式成立。由于当x2=30时，原基本变量x4=0，其余x3和x5都满足非负要求。因此，可以将x2，x4互换。于是原约束方程式可得到：4x2+x3=360-9x1 10x2 =300-3x1-x4 5x2+x5=200-4x1 用消元法将上式中x2的系数列向量变[4,10,5]T换成标准基向量[0,1,0]T。其具体运算过程如下： -*4/10 : x3=240-78x1/10+4 x4/10 /10 : x2 =30-3x1/10-x4/10

图解法和单纯形法求解线性规划问题

图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式

单纯形法的计算方法

第4章 单纯形法的计算方法 单纯形法求解线性规划的思路: 一般线性规划问题具有线性方程组的变量数大于方程个数, 这时有不定的解。但可以从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步选择的单纯形。这就是迭代, 直到目标函数实现最大值或最小值为止。 4.1 初始基可行解的确定 为了确定初始基可行解, 要首先找出初始可行基, 其方法如下。 （1）第一种情况：若线性规划问题 max z =n j j j=1c x ∑ 1,1,2,...,0,1,2,...n ij j i j j a x b i m x j n =?==???≥=?∑ 从Pj ( j = 1 , 2 , ? , n )中一般能直接观察到存在一个初始可行基 121(,,...,)n B P P P 0 0?? ?0 1 0 ?== ? ?0 0 1?? （2）第二种情况：对所有约束条件是“ ≤”形式的不等式, 可以利用化为标准型的方法, 在每个约束条件的左端加上一个松弛变量。经过整理, 重新对 j x 及ij a ( i = 1 , 2 , ? , m ; j = 1 , 2 , ? , n )进行编号, 则可得下列方 程组 11,1111 22,1122,1112.........,,...,0 m m n n m m n n m m m m nn n n n x a x a x b x a x a x b x a x a x b x x x +++++++++=?? +++=?? ??+++=??≥? 显然得到一个m ×m 单位矩阵

运筹学作业2(清华版第二章部分习题)答案

运筹学作业2(清华版第二章部分习题)答案 -标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

运筹学作业2（第二章部分习题）答案 2．1 题 （P. 77） 写出下列线性规划问题的对偶问题： （1）123123123123123max 224..34223343500,z x x x s t x x x x x x x x x x x x =++??++≥??++≤??++≤? ≥≥?? 无约束，； 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 123123123123123max 235..22342 4334,0,0w y y y s t y y y y y y y y y y y y =++??++≤?? ++≤??++=? ≥≤≤??0 （2）11 11 min ,1,,,1,,0,1,,;1,,m n ij ij i j n ij ij i j n ij ij j j ij z c x c x a i m c x b j n x i m j n ====? =? ??==????==??≥==??∑∑∑∑ 解：根据原—对偶关系表，可得原问题的对偶规划问题为： 11 max 1,,;1,,m n i i j j i j i j ij i w a u b v u v c i m j n u ==? =+??? +≤? ?==???∑∑j 无约束，v 无约束 2．2判断下列说法是否正确，为什么？ （1） 如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； 答：错。

因为：若线性规划的原问题存在可行解，且其对偶问题有可行解，则 原问题和可行问题都将有最优解。但，现实中肯定有一些问题是无最优解的，故本题说法不对。 例如原问题 12 1221 2max 31.. 30,0 z x x x x s t x x x =++≥?? ≤? ?≥≥?有可行解，但其对偶问题 121 121 2min 33.. 10,0 w y y y s t y y y y =+≥?? +≥??≤≥?无可行解。 （2） 如果线性规划的对偶问题无可行解，则原问题也一定无可行解； 答：错，如（1）中的例子。 （3） 在互为对偶的一对原问题与对偶问题中，不管原问题是求极大或求极 小，原问题可行解的目标函数值一定不超过其对偶问题可行解的目标函数值。 答：错。正确说法是：在互为对偶的一对原问题与对偶问题中，求极大的问题可行解的目标函数值一定不超过求极小的问题可行解的目标函数值。 （4） 任何线性规划问题具有唯一的对偶问题。 答：正确。 2．5给出线性规划问题 123 123123123123max 221 .. 220,0,0 z x x x x x x x x x s t x x x x x x =+++-≤??-+=?? ++≥??≥≥≥? 写出其对偶问题；（2）利用对偶问题性质证明原问题目标函数值1z ≤

单纯形法的解题步骤

单纯形法的解题步骤

三、单纯形法的解题步骤 第一步：作单纯形表. （1）（1）把原线性规划问题化为标准形式； （2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； （3）（3）目标函数非基化； （4）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即 ，则此时线性规划问题已取得最优解. (2) 若存在某个检验数是正数，即，而 所对应的列向量无正分量，则线性规划问题无最 优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. （1）找到最大正检验数，设为，并确定

（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）. 表 6.8 x1 x2x3x4x5常数 x 3 x 4 x 51 0 1 0 0 1 2 0 1 0 0 （1）0 0 1 5 10 4 S′ 1 3 0 0 0 0 x 3 x 4 x2 1 0 1 0 0 （1）0 0 1 -2 0 1 0 0 1 5 2 4 S′ 1 0 0 0 -3 -12 x 3 x 1 x 20 0 1 -1 2 1 0 0 1 -2 0 1 0 0 1 3 2 4 S′0 0 0 -1 -1 -14

（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出