单纯形法求解线性规划的思路及重要参数
的推导
在求解线性规划问题的算法中，单纯形法是一种成熟、简便、有效的算法，在目前应用最为广泛。因此，我们组通过查阅资料以及小组讨论的形式，分工合作，共同探讨出单纯形法求解线性规划的思路。
一般线性规划问题有时具有线性方程组的变量数大于方程个数
的情况, 这时就使得方程有不定的解。这时就可以使用单纯形法来求解，从线性方程组中找出一个个的单纯形, 每一个单纯形可以求得一组解, 然后再判断该解使目标函数值是增大还是变小, 决定下一步
选择的单纯形。在这其中每一个单纯形所对应的解其实都相当于n维空间图形中的一个顶点，我们就是要一个顶点，一个顶点的找到使目标函数值更好的顶点, 直到目标函数实现最大值或最小值为止。这样问题就得到了最优解。
具体的求解步骤来说有6步：1：建立基本可行解。2：计算变量的检验数。3：判断是否最优。4：若不是最优解，则换基。5：计算新的基本可行解。6：迭代计算直到求的最优解或者可判断无最优解为止。
接下来，我们通过具体的事例来详细介绍具体的求解步骤，并列出重要参数以及定理的推导过程。
某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品, 已知生产单位产品所需的设备台时及A、B 两种原材料的消耗, 如下表所示。
该工厂每生产一件产品Ⅰ可获利2 元, 每生产一件产品Ⅱ可获利3元, 问应如何安排计划使该工厂获利最多?
解：根据题意建立其标准型：
max z = 2x1 + 3x2 + 0x3 + 0x4 + 0x5 (1)
x1 +2x2 +x3 = 8
4x1 + x4 = 16 (2)
4x2 +x5 = 12
x j ≥0 , j = 1 , 2 , ? , 5 一、建立基本可行解
在标准型中x3 , x4 , x5为转化为标准型时加入的松弛变量，从(2)式中可以看到x3, x4 , x5的系数列向量
1 0 0
P3 = 0 , P4 = 1 , P5 = 0
0 0 1
而这些列向量就可以看做一个初始可行基
1 0 0
B = ( P3 , P4 , P5 ) = 0 1 0
0 0 1
B 的变量
x 3 , x 4 , x 5 为基变量, 从(2)式中可以得到 x 3 = 8 -x 1 - 2x 2
x 4= 16 - 4x 1 (3) x 5= 12 - 4x 2
二、计算变量的检验数
将(3)式代入目标函数(1)式得到
z = 0 + 2
x 1 + 3x 2 (4)
当令非基变量x 1 = x 2 = 0 , 便得到z = 0。这时得到一个基可行解
X (0)，X (0)= ( 0 , 0 , 8 , 16 , 12) T
这个基可行解表示: 工厂没有安排生产产品Ⅰ、Ⅱ ; 资源都没有被利用, 所以工厂的利润指标z = 0。
三、判断是否最优（最优解的检验和解的判别）
线性规划问题的求解结果可能出现唯一最优解，无穷多最优解，无界解和无可行解四种情况，为此需要建立对解的判别准则。下面我们来讨论怎样判别解属于那一种情况。
''1
n
i i ij j j m x b a x =+=-
∑
（i=1,2,…,m ） (1-1)
将（1-1）式代入目标函数 目标函数式为（1-2）
''111m n
m
i i j i ij j i j m i z c b c c a x ==+=??=+-????
∑∑∑ （1-3）
令
'
'01
1
,,1,...,m m
i i j i ij i i z c b z c a j m n =====+∑∑
于是
01
()n
j
j j j m z z c
z x =+=+
-∑ （1-4）
再令
j j j c z σ=- （j=m+1,…,n ）
则
01
n
j
j j m z z x σ
=+=+
∑ （1-5）
1. 最优解的判别定理
若(0)'''12(,,...,,0,...,0)T m X b b b =为对应基B 的一个基可行解，且对于一切J=m+1,…,n,有0j σ≤，则为(0)
X 最优解。称j σ为检验数。 2. 无穷多最优解判别定理 若
(0)'''12(,,...,,0,...,0)T
m X b b b =为一个基可行解, 对于一切j = m+ 1 ,
?, n, 有σj ≤0 ,又存在某个非基变量的检验数σm + k = 0 ,则线性规划问题有无穷多最优解。
证只需将非基变量m k x +换入基变量中, 找到一个新基可行解。因σm + k = 0, 由(1 -2 )知, 0z z = 故(0)X 也是最优解。由前面提到的定理，即，若可行域有界，线性规划问题的目标函数一定可以在其可行域的
顶点上达到最优，可知, (0)X ，(1)X 连线上所有点都是最优解 3. 无界解判别定理
若
(0)'''12(,,...,,0,...,0)T
m X b b b =为一基可行解, 有一个σm + k > 0 ,
并且对i = 1 , 2 , ?, m ，有,0i m k a +≤, 那么该线性规划问题具有无界解(或称无最优解)。
证构造一个新的解(1)X ，它的分量为
(1)'',(0)i i i m k x b a λλ+=->
(1)m k x λ+=
(1)0,j x =
j = 0 , j = m + 1 , ? , n , 且j ≠m + k
因,0i m k a +≤ , 所以对任意的λ> 0 都是可行解, 把x ( 1 ) 代入目标函数内得
0m k z z λσ+=+
因σm + k > 0 , 故当λ→ + ∞ , 则z → + ∞ , 故该问题目标函数无界。
以上讨论都是针对标准型，即求目标函数极大化时的情况。当求目标函数极小化时，一种情况如前所述, 将其化为标准型。如果不化为标准型, 只需在上述1 , 2 点中把σj ≤0改为σj ≥0 , 第3 点中将m k σ+>0改写为σm + k < 0 即可。
对于本例来说，由（4）得到非基变量
x 1 , x 2的检验数为正数,
因此X(0)还不是目标函数的最优解，将非基变量x1 , x2变换为基变量,则目标函数的值就可能增大。工厂只有生产了产品后才有可能收益，所以只要在目标函数(4)的表达式中还存在有非负的检验数,就表示目标函数值还有增加的可能。
四、换基（入基、出基）
对某些情况来说，通过检验，初始可行解可能不是最优解。这是，我们需要通过基变换得到一个新的可行基。具体做法是从可行基中换一个列向量，得到一个新的可行基，使得求解得到新的基本可行解，使目标函数值更优。为了换基就要确定换入变量与换出变量。
（1）入基变量的确定
δ>时，非基变量j x不取零值从最优解判别定理知道，当某个0
j
可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去。若有两个以上的，则为了是目标函数增加的更大一些，一般选jδ最大者的非基变量为入变量。
（2）出变量的确定
确定出基变量的方法如下。把已确定的入基变量在各约束方程中的系数除其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。
下面再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。
p p p是一组线性独立的向量组，它们对应的基可行解是设1,2,....m
(0)X 。将它代入约束方程组中1
n
j j
j p x b
==∑，
0,1,2,...,j x j n ≥=中
得到
(0)1m
i i i x P b ==∑ (1)
其他的向量12,,...,...,m m m t n P P P P +++都可以用12,,...,m P P P 线性表示，若确定非基变量m t p +为换入变量，必然可以找到一组不全为0的数（1,2,...,i m =）使得
,1
m
m t i m t i
i P P β++==∑或
,1
m
m t i m t i i P P β+-+==∑ (2)
在（2）式两边同乘一个正数θ，然后将它加到（1）式上，得到
(0),11m
m
i i m t i m t i i i x P P P b θβ+-+==??
+= ???
∑∑或
(0),1
()m
i i i m t m t i x P P b θβθ++=-+=∑ （3）
当θ取适当值时，就能得到满足约束条件的一个可行解（即非零分量的数目不大于m 个）。就应使
(0),()(1,2,...,)
m t i i x i m θβ+-=中的某一个为零，
并保证其余的分量为非负。这个要求可以用以下的办法达到：比较各
比值
(0)
,(1,2,...,)
i
i m t
x
i m β+
=。又因θ必须是正数，所以只选择
(0),0(1,2,...,)i i m t x i m β+??
>= ? ?
??中比值最小的等于θ。以上描述用数学使表述
为：
(0)(0)
,,,min |0i i i m t i i m t i m t x x θβββ+++??=>=
? ???
这时i x 为换出变量。按最小比值确定θ值，称为最小比值规则。将
(0)
,i i m t
x θβ+=
带入X 中，便得到新的基可行解。
(0)
(0)
(0)
(0)(0)(0)
111,,,,,(,...,0,...,,0,...,
,0...,)
i i i m t m m m t l m t
l m t
l m t
x x x X x x βββββ+++++=-
-
↑ ↑ 第l 个分量 第m+t 分量 由此得到由(0)
X 转换到(1)
X 的各分量的转换公式
()
(0)
0,(0)
1,,(1)
,l i i m t l
m t
x x i l i
x i l
X
ββ++-≠=??=???
这里
(0)
i x 是原基可行解 (0)X 的各分量；(1)
i X 是新基可行解 (1)X 的各分量；
,
i m t β+
是换入向量m t P +的对应原来一组基向量的坐标。现在的问题是，
这个新解(1)
X 的m 个非零分量对应的列向量是否线性独立？事实上，因(0)
X 的第l 个分量对应于(1)
X 的相应分量是零，即
(0),0
l l m t X θβ+-=
其中
(0)
l X ，θ均不为零，根据θ规则（最小比值），,0
l m t β+≠。(1)
X 中的m
个非零分量对应的m 个列向量是
(1,2,...,,)
j P j m j l =≠和m t P +。若这组向量
不是线性独立，则一定可以找到不全为零的数
j
α，使
1
,m
m t j j j P P j l
α+==≠∑ （4）
成立。又因
,1
m
m t j m t j
j P P β++==∑ （5）
将（5）式减（1）式得到
,,1,1
()0
m
j m t j j l m t l j j P P βαβ++=≠-+=∑
由于上式中至少有
,0
l m t β+≠，所以上式表明12,,...,m P P P 是线性相关，这
与假设相矛盾。由此可见，(1)
X 的m 个非零分量对应的列向量
(1,2,...,)
j P j m =与m t P +是线性独立的，即经过基变换得到的解是基可行
解。实际上，从一个基到另一个基可行解的变换, 就是进行一次基变换。从几何意义上讲, 就是从可行域的一个顶点转向另一个顶点。 对于本例，当判断不是最优解时，将非基变量与基变量进行对换，当存在多个检验数为非负的时候，一般选择正系数最大的那个非基变量为换入变量,因此x 2换入到基变量中去,同时还要确定基变量中有
一个要换出来成为非基变量,当将
x 2定为换入变量后,必须从x 3 , x 4 , x 5中确定一个换出变量,并保证其余的都是非负,即x 3 , x 4 , x 5≥0。
当x 1 = 0 , 由(3)式得到
x 3 = 8 - 2x 2≥0
x 4 = 16≥
0 (5)
x5 = 12 - 4x2≥0
从(5)式中可以看出, 只有选择x2 = 3时, 才能使(5)式成立。
当x2 = 3 时, 基变量x5 = 0 , 这就决定了用x2去替换x5。
五、计算新的基本可行解：
此时以x3, x4 ,x2为基变量求出其一个基可行解和进一步分析问题, 将(3)中x2的位置与x5的位置对换。得到
x2 = 8 -x1①
x
x4 = 16 - 4x1② (6)
4x2= 12 -x5③
变形的到
x1 +1/2x5①′
x
x4 = 16 - 4x1②′ (7)
x2= 3 - 1/4x5③′
再将(7)式代入目标函数(1)式得到
z = 9 + 2x1 -3/4x5 (8)
令非基变量x1 = x5 = 0 , 得到z = 9 , 并得到另一个基可行解X(1) X(1) = (0 , 3 , 2 , 16 , 0)T
六、迭代计算直到求的最优解或者可判断无最优解为止：
从目标函数的表达式(8) 中可以看到, 非基变量x1的检验数是正的, 说明目标函数值还可以增大, X(1)不一定是最优解。于是再用上述方法, 确定换入、换出变量, 继续迭代, 再得到另一个基可行解
X(2)，X(2) = (2 , 3 , 0 , 8 , 0 )T再经过一次迭代, 再得到一个基可行解X(3)，X(3) = (4 , 2 , 0 , 0 , 4 )T
而这时得到目标函数的表达式是:
z = 14 - 1.5x3 - 0.125x4 (9)
再检查(9)式, 可见到所有非基变量x3, x4的系数都是负数。此时变量的检验数都为负数，所以X(3)是最优解。即当产品Ⅰ生产4 件, 产品Ⅱ生产2 件, 工厂才能得到最大利润。
综上所述，我们可以了解利用单纯形法求解线性规划问题的思路。通俗地讲，单纯形方法的主要思路就是先找一个基本可行解，判别它是否为最优解，如不是，就找一个更好的基本可行解，在进行判别，如此迭代进行，直至找到最优解，或者判定该问题无界。
单纯形法演算 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 无穷 0 4x 24 6 2 0 1 0 4 0 5x 5 1 1 0 0 1 5 j j z c -（检验数） 2 1 首先列出表格，先确定正检验数最大值所在列为主列，然后用b 除以主列上对应的同行数字。除出来所得值最小的那一行为主行，根据主行和主列可以确定主元（交点）。接着把主元化为1并把X4换成X1. ??? ??? ?≥=++=++=+++++=0,,524261550002max 5152 14213 25 4321x x x x x x x x x x x x x x x z ??????? ≥≤+≤+≤+=0 ,5 24261552max 21212122 1x x x x x x x x x z
j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5 1 1 0 0 1 j j z c - 2 1 这时进行初等行列变换，把主列换单位向量，主元为1。也就是X5所在行减去X1所在行。并且重新计算检验数。 j c 2 1 B C X B b 1x 2x 3x 4x 5x 0 3x 15 0 5 1 0 0 2 1x 4 1 2/6 0 1/6 0 0 5x 5-4 1-1=0 1-2/6 =4/6 0-1/6=-1/6 1 j j z c - 2-2*1-0*0-0*1=0 1-0*5-2*2/6-0*4/6=1/3 0-0*0-2*1/6-0*-1/6=-1/3 再次确定主元。为4/6。然后把X5换成X2。并且把主元化成1。
工程优化设计中单纯形法的基本原理 张云龙 （大连海洋大学土木工程学院辽宁大连116023) 摘要：从实例出发提出线性规划的数学模型，给出图解法的基本原理，进而重点讲述它的标准解法——单纯形法。在此基础上进一步讨论单纯形法的推广，即大M法和两相法。 关键词：线性规划图解法单纯形法大M法 THE BASIC PRINCIPLES OF SIMPLEX METHOD TO THE ENGINEERING OPTIMIZE DESIGN ZHANG Y un-long (Dalian Ocean University, College of Civil Engineering, Liaoning, Dalian 16023) Abstract: From the instance of the starting linear programming mathematical model of the basic principles of the graphic method, and then focus on the standard solution - simplex method. To promote further discussion on this basis, the simplex method, that is, the big M method and two-phase method. Key W ords: Linear programming；Graphic method；Simplex Method; Big M Method 1引言 在工程优化设计问题中，当约束集由一组线性函数所确定时，其最优化问题的求解已有比较系统的技巧。如果连目标函数也是线性的，也即线性规划问题，则是目前对规划问题研究最透彻最完善的一类问题，而且有比较成熟的解法。线性规划在工程实例中的应用已相当广泛。 虽然大多数设计问题是非线性的，但对线性规划的研究仍然占据突出地位。其原因是：有一部分实际问题，诸如运输问题，分配问题等，确实可以用线性规划问题来求解。尤为重要的是，对于几乎所有规划问题的讨论都与线性规划有关，有时用线性逼近法去直接求解非线性问题；有时则利用线性规划，作为求解在最优化过程中所提出的那些子问题的一个工具，例如，可用来求解可行方向法中的方向寻求问题等错误！未找到引用源。。 因此，深刻理解线性规划问题及其标准解法——单纯形法，显得尤为关键。 2线性规划问题 2.1数学模型 线性规划主要解决：如何利用现有的资源，使得预期目标达到最优。例如，美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-1所示。问该公司应制造两种家电各多少件，使获取的利润最大？ 表1-1 工时及利润简表
三、单纯形法的解题步骤 第一步：作单纯形表. ）（1）把原线性规划问题化为标准形式； ）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵； ）（3）目标函数非基化； ）（4）作初始单纯形表. 第二步：最优解的判定. (1) 若所有检验数都是非正数，即，则此时线性规划问题已取 得最优解. (2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划 问题无最优解. 如果以上两条都不满足，则进行下一步. 第三步：换基迭代. ，并确定所在列的非基变量为进基变量. （1）找到最大正检验数，设为 （2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号. 主元是最大正检验数 所在列，用常数项与进基变量所对应的列向 量中正分量的比值最小者； 替换出基变量，从而得到新的基变量.也就是主元所在 （3）换基：用进基变量 （4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表； （5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止. 例3 求.
解（1）化标准型：令 ，引进松弛变量 ，其标准型为 求 （2）作单纯形表：在约束方程组系数矩阵中 的系数构成单位矩阵，故取 为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8
（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为 目标函数取得最优值. 原线性规划问题的最优解为：.目标函数的最优值为14，即. 例4 用单纯形方法解线性规划问题. 求. 解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出 ，, 代入目标函数 , 经整理后，目标函数非基化了. 作单纯形表，并进行换基迭代（见表6.9）. 最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变出基，非基变量进基. 换，基变量
单纯形法求最优解问题 题目（老师布置的那道作业题）：2153m ax x x f +=，其中 ??? ??? ?=≥=++=+=+5,4,3,2,1,0182312245214 231j x x x x x x x x j ，求2153m ax x x f +=的最大值。 这张表是根据题目画的，Cj （行向量）为5432100053m ax x x x x x f ++++=中各个变量的系数，Ci （列向量）为与X B （列向量）相对应的各项的系数，X B 称为基变量（3列，由题目中的方程个数决定），起初的基变量由构造的变量x3、x4、x5组成，b 为对应三个方程等式右边的常数，z j 为Ci 各列与xj 各列乘积的和，如z1=0*1+0*0+0*3=0。i θ为判别将哪个基变量换出的依据，根据c j -z j 为正，要先将x2换入XB 中，关键是判断x3、x4、x5哪个跟x2换，这就要根据各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，如上表可知x2跟x4换，换完之后注意原来x4所对应的列向量为[0 1 0]T ,故要将x2所对应的列向量变换为为[0 1 0]T ，注意b 也要跟着变化，于是得下表.
由上表知c 1-z 1=3>0，故仍需将x1换入XB 中，用各列各列除以2x B i X =θ，与所得的最小的i θ对应的XB 换，结合i θ可知，x1跟x5换，于是得下表。 由上表可知c j -z j 均非正，故5432100053m ax x x x x x f ++++=取最大值时，????? ?? ?????????=00662x ， 对应的最大值36max =f . 系统工程导论知识点整理： 系统是由相互作用和相互依赖的若干组成部分(要素)结合的具有特定功能的有机整体。 系统的特征：整体性、相关性、目的性、环境适应性。 系统的功能是指系统与外部环境相互作用所反映的能力。 结构是功能的内在根据，功能是结构的外在表现。 系统功能的特性：易变性、相关性。 系统工程就是用科学的方法规划和组织人力、物力、财力，通过最优途径的选择，使人们的工作在一定期限内收到最合理、最经济、最有效的效果。 科学的方法：从整体观念出发，通盘筹划，合理安排整体中的每一个局部，以求得整体的最优规划、最优管理和最优控制，使每个局部都服从一个整体目标，力求避免资源的损失和浪费。
单纯形法表的解题步骤 单纯形法表结构如下： j c → 对应变量的价值系数 i θ B C b X b 1x 2x 3x " j x 基变量的价值系数 基变量 资源列 θ规则 求的值 j σ 检验数 ①一般形式 若线性规划问题标准形式如下： 123451231425max 23000284164120,1,2,5 j z x x x x x x x x x x x x x j =++++++=??+=?? +=??≥=?" 取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。这样就得到初始可 行基解：()()0 0,0,8,16,12T X =。将有关数字填入表中，得到初始单纯形表，如表 1-1所示： 表 1-1 ()()00,0,8,16,12T X = j c → 2 3 0 0 0 i θ B C b X b 1x 2x 3x 4x 5x 0 3x 8 1 2 1 0 0 4 0 4x 16 4 0 0 1 0 -
5x 12 0 [4] 0 0 1 3 j σ 2 3 0 0 0 若检验数均未达到小于等于0，则对上表进行调整。选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的 θ值，选出其中最小的一行，该行对应的基变量为出基变量。修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。修改后的单纯形表如表 1-2所示： 表 1-2 ()()10,3,2,16,0T X = 检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示： 表 1-3 ()()22,3,0,8,0T X =
单纯形法求解线性规划的步骤
单纯形法求解线性规划的步骤 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 max z=2x1+3x2 （标准形式即所有的变量均为负、所有约束条件为等式、所有的右端项系数非负） a=(2,3) b1=(80,160,120) A2=NULL b2=NULL A3=NULL b3=NULL n.iter=n+2*m maxi=TRUE ● simplex(a=a,A1=A1,b1=b1,maxi=TRUE)： m1=3,m2=0,m3=0 m=3,n=2 a.o=a=(2,3) if(maxi) a=-a(-2,-3) if(m2+m3==0) a=(-2,-3,0,0,0) b=(80,160,120) init=(0,0,0,80,160,120) basic=(3,4,5) eps=1e -10 out1<-simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps) ? simplex1(a=a,A=A,b=b,init=init,basic=basic,eps=eps): N=5,M=3 nonbasic=(1,2) if(stage==2) obfun=(-2,-3) it=1 ◆ while(!all(obfun > -eps) && (it <= n.iter))循环 pcol=3 if(stage==2) neg=(1,3) x1+2x2<=80 4x1<=160 4x2<=120 x1，x2>=0 A1= 1 2 4 0 0 4 A= 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1 tableau= 80 -1 -2 160 -4 0 120 0 -4 tableau= 80 -1 -2 160 -4 0 120 0 -4 0 -2 -3 转化为标准形式 x1+2x2+x3=80 4x1+x4=160 4x2+x5=120 x1,x2,x3,x4,x5>=0
图解法和单纯形法求解以下线性规划问题 1.1 图解法解线性规划问题 只含两个变量的线性规划问题，可以通过在平面上作图的方法求解，步骤如下： (1)以变量x1为横坐标轴，x2为纵坐标轴，适当选取单位坐标长度建立平面坐标直 角坐标系。由变量的非负性约束性可知，满足该约束条件的解均在第一象限内。 (2)图示约束条件，找出可行域（所有约束条件共同构成的图形）。 (3)画出目标函数等值线，并确定函数增大（或减小）的方向。 (4)可行域中使目标函数达到最优的点即为最优解。 然而，由于图解法不适用于求解大规模的线性规划问题，其实用意义不大。 1.2 单纯形法解线性规划问题 它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。 单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 1.3 线性规划问题的标准化 使用单纯形法求解线性规划时，首先要化问题为标准形式
《吉林建筑工程学院城建学院人文素质课线性规划单纯形法例题》 ??? ??≥=++=+++++=?? ? ??≥≤+≤++=0,,,24 261553).(002max ,,0,24 261553).(2max 14.1843214213 214 321432121212 1x x x x x x x x x x t s x x x x z x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【为初始基变量，选择43,x x )1000(00)0010(01 )2050(12)6030(24321=?+?-==?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择41x x
3 /1)6/122/10(00 )0210(03 /1)3/1240(10)1200(24321-=?+-?-== ?+?-==?+?-==?+?-=σσσσ 为出基变量。为进基变量，所以选择32x x 24 /724/528/11012/112/124/1100 021110120124321-=?+-?-=-=-?+?-==?+?-==?+?-=）（）（）（）（σσσσ 433 4341522max ,)4 3,415( ),(2112= +?=+===x x z x x X T T 故有：所以，最优解为
??? ??? ?≥=+ +=+=+ ++++=?????? ?≥≤+≤≤+=0,,,,18232424).(0002max ,,,0 ,182312212 ).(52max 24.185432152142315 43215432121212 1x x x x x x x x x x x x t s x x x x x z x x x x x x x x x t s x x z 标准型得到该线性规划问题的，分别加入松驰变量在上述线性规划问题中法求解线性规划问题。分别用图解法和单纯形）】 （页【 )000010(00001000000000100520200052300010254321=?+?+?-==?+?+?-==?+?+?-==?+?+?-==?+?+?-=σσσσσ）（）（）（）（ 为出基变量。为进基变量，所以选择42x x
单纯形法求解线性规划的步骤 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();其中row2为主元所在的行,col为主元所在的列,row1为要处理的行 void PrintAnswer();数不合法"< 单纯形法原理及步骤 单纯形法，求解线性规划问题的通用方法。单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。它的理论根据是：线性规划问题的可行域是 n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。 单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。 概述： 根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。使目标函数达到最大值（或最小值）的可行解称为最优解。这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。求解线性规划问题的目的就是要找出最优解。最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止 目标函数的值无限增大（或向负的方向无限增大）。 单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。②若基本可行解不存在，即约束条件有矛盾，则问题无解。③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。 用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。现在一般的线性规划问题都是应用单纯形法标准软件在计算机上求解，对于具有106个决策变量和104个约束条件的线性规划问题已能在计算机上解得。 求解步骤： （1）确定初始基可行解 ①从线性规划标准形的系数矩阵中能直接找出m个线性独立的单位向量； ②对约束条件全为“<=”连接的LP，化为标准形，左端添加松弛变量后即形成一个单位子矩阵； ③约束条件中含有“<=”或“=”连接的方程，在插入剩余变量后找不到单位矩阵，则必须采用 第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 单位矩阵 单纯形法的解题步骤 三、单纯形法的解题步骤 第一步：作单纯形表. （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列构成），取为基变量，而目标函数没有非基化.从约束方程找出 单纯形算法的一般原理 单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。 考虑到如下线性规划问题： 其中Ａ一个m ×n 矩阵，且秩为m ，ｂ总可以被调整为一个m 维非负列向量，Ｃ为n 维行向量，Ｘ为n 维列向量。 根据线性规划基本定理： 如果可行域Ｄ={ Ｘ∈Ｒn / ＡＸ=ｂ，Ｘ≥0}非空有界， 则Ｄ上的最优目标函数值Ｚ=ＣＸ一定可以在Ｄ的一个顶点上达到。 这个重要的定理启发了Dantzig 的单纯形法， 即将寻优的目标集中在D 的各个顶点上。 Dantzig 的单纯形法把寻优的目标集中在所有基本可行解 （即可行域顶点）中。 其基本思路是从一个初始的基本可行解出发，寻找一条达到 最优基本可行解的最佳途径。 单纯形法的一般步骤如下： （1）寻找一个初始的基本可行解。 （2）检查现行的基本可行解是否最优，如果为最优， 则停止迭代，已找到最优解，否则转一步。 （3）移至目标函数值有所改善的另一个基本可行解， 然后转会到步骤（2）。 求解思想如下图所示： maxZ=CX AX=b X 0??≥? 确定初始的基本可行解等价于确定初始的可行基，一旦初始的可行基确定了，那么对应的初始基本可行解也就唯一确定 为了讨论方便，不妨假设在标准型线性规划中，系数矩阵Ａ中前m 个系数列向量恰好构成一个可行基，即 Ａ=（ＢＮ），其中 Ｂ=（Ｐ1，Ｐ2，…Ｐm ）为基变量x1，x2，…xm 的系数列向量 构成的可行基， Ｎ=(Ｐm+1，Pm+2， …Pn)为非基变量xm+1，xm+2， …xn 的 系数列向量构成的矩阵。 那么约束方程AX=b 就可表示为： 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量 ，则基变量 由此可得初始的基本可行解 B B N N X AX=(BN)=BX +NX =b X ?? ???-1-1B N X =B b-B NX N X =0-1B X =B b 1B b X=0-?? ???-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b →→→ 单纯形法例题讲解 基可行解 单纯形法是针对标准形式的线性规划问题进行演算的，任何线性规划问题都可以化为标准形式。 min cx f = （1） s.t b Ax = （2） 0≥x （3） 其中 T m mn m m n n T n n b b b b a a a a a a a a a A x x x x c c c c )...,(,............ ... ..., ),...,,(),,...,(212 1 22221112 112121=??? ???????????=== 假设1≥≥m n ，并设系数矩阵A 的秩为m ，即 设约束方程（2）中没有多余的方程，用j p 表示A 的第j 列，于是（2可写成 b p x m k j j =∑=1 （4） 矩阵A 的任意一个m 阶非奇异子方阵为LP 的一个基（或基阵），若 ),...,(21jm j j p p p B = （5） 是一个基，则对应变量jm j j x x x ,...,,21，称关于B 的基变量，其余变量成为关于B 的非基变量，若令非基变量都取零值，则（4）变为 b p x m k jk jk =∑=1 （6） 由于此方程组的系数矩阵B 是满秩方阵，故知（6）有唯一解，记为T jn j j x x x ) ,...,,()0() 0(2) 0(1于是按分量 {}{}),...,,\,...2,1(0) ,....3,2,1(21) 0(m j jk jk j j j n j x m k x x ∈=== 所构成的向量) 0(x 是约束方程组b Ax =的一个 解，称此)0(x 为LP 的对应于基B 的基解 （或基本解），也可称为方程组b Ax =的一个基解，如果) 0(x 为一基解，且满足 0)0(≥x 即它的所有分量都非负，则称此) 0(x 是LP 的一个基可行解，基可行解对应的基 称为可行基。单纯形法原理
单纯形法的计算方法
单纯形法的解题步骤
单纯形算法一般原理
最新单纯形法例题讲解
相关主题
文本预览