单纯形法原理推导过程

第二章单纯形法第二章单纯形法单纯形法的一般原理表格单纯形法借助人工变量求初始的基本可行解单纯形表与线性规划问题的讨论改进单纯形法考虑到如下线性规划问题其中Ａ一个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。

单纯形法原理及步骤单纯形法，求解线性规划问题的通用方法。

单纯形是美国数学家G.B.丹齐克于1947年首先提出来的。

它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。

顶点所对应的可行解称为基本可行解。

单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别；若仍不是，则再转换,按此重复进行。

因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。

如果问题无最优解也可用此法判别。

单纯形法是从某一基可行解出发，连续地寻找相邻的基可行解，直到达到最优的迭代过程，其实质是解线性方程组。

概述：根据单纯形法的原理，在线性规划问题中，决策变量（控制变量）x1，x2，…x n的值称为一个解,满足所有的约束条件的解称为可行解。

使目标函数达到最大值（或最小值）的可行解称为最优解。

这样，一个最优解能在整个由约束条件所确定的可行区域内使目标函数达到最大值（或最小值）。

求解线性规划问题的目的就是要找出最优解。

最优解可能出现下列情况之一：①存在着一个最优解；②存在着无穷多个最优解；③不存在最优解，这只在两种情况下发生，即没有可行解或各项约束条件不阻止目标函数的值无限增大（或向负的方向无限增大）。

单纯形法的一般解题步骤可归纳如下：①把线性规划问题的约束方程组表达成典范型方程组，找出基本可行解作为初始基本可行解。

②若基本可行解不存在，即约束条件有矛盾，则问题无解。

③若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。

④按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。

⑤若迭代过程中发现问题的目标函数值无界，则终止迭代。

用单纯形法求解线性规划问题所需的迭代次数主要取决于约束条件的个数。

单纯形法一、单纯形法的原理线性方程组的解：⎩⎨⎧=----=+-+-4322425432154321x x x x x x x x x x （1） 5个未知数，两个方程组。

方程的解多于1个。

两种初等变换：51）方程组的任一方程乘上一个不为零的数。

2）方程组的任一方程两边同乘上一个常数，分别加到另一个方程的两边。

式（1）做变换得到：（①×-1）⎩⎨⎧=-+-=+-+-2322242543254321x x x x x x x x x （2） 式（2）做变换得到：（②×2）⎩⎨⎧=-+-=---232642354325431x x x x x x x x （3）方程组（1）、（2）、（3）同解，可令0543===x x x 。

得到：61=x ，22=x 。

选择3x ，4x ，5x 不同的值，相应地有不同的1x 和2x 的值，因此方程组有多组解。

基本变量：如果变量i x 的系数在某一个方程为1，而在其它所有方程为0，则称i x 为该方程组中的基本变量。

非基本变量：凡不是基本变量的变量都叫做非基本变量。

1x ，2x 为基本变量；3x ，4x ，5x 为非基本变量。

旋转运算：运用初等变换，可使一给定变量化为基本变量，这一运算，成为旋转运算。

基本变量的个数，与方程的个数相同。

基本解：设非基本变量为0，求得相应的基本变量的值，得到一组解，这组解称为基本解。

基本可行解：基变量的值为非负时的基本解称为基本可行解。

单纯形法的思路；1）先不考虑目标函数，从满足约束条件开始，寻求一个初始基本可行解； 2）求具有较佳目标函数值的另一个基本可行解，以改进初始解；3）对目标函数做有限次的改善。

当某一个基本可行解不能再得到改善时，即求得最优解，单纯形法结束。

二、单纯形算法例：54321325max x x x x x Z +-++= 约束条件为：⎪⎩⎪⎨⎧≥≥≥≥≥=+++=+++0,0,0,0,0743********53214321x x x x x x x x x x x x x （5） 以上线性规划问题中，具有： 1）全部变量非负；2）全部约束条件都是等式；5 3）右端常数都是正的。

单纯形法求解原理过程第一篇：单纯形法求解原理过程单纯形法需要解决的问题：如何确定初始基本可行解；如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降；如何判断一个基本可行解是否为最优解。

min f(X)=-60x1-120x2 s.t.9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 xi≥0(i=1,2,3,4,5)(1)初始基本可行解的求法。

当用添加松弛变量的方法把不等式约束换成等式约束时，我们往往会发现这些松弛变量就可以作为初始基本可行解中的一部分基本变量。

例如：x1-x2+x3≤5 x1+2x2+x3≤10xi≥0 引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10xi≥0(i=1,2,3,4,5)令x1=x2=x3=0，则可立即得到一组基本可行解x1=x2=x3=0，x4=5，x5=10 同理在该实例中，从约束方程式的系数矩阵⎡94100⎤⎥A=[P1,P2,P3,P4,P5]=⎢310010⎢⎥⎢⎣45001⎥⎦中可以看出其中有个标准基，即⎡100⎤⎥B=⎢010⎢⎥⎢⎣001⎥⎦与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x20 若令非基变量x1=x2=0，则可得到一个初始基本可行解X0 TX=[0,0,360,300,200]判别初始基本可行解是否是最优解。

此时可将上式代入到目标函数中，得： F(X)=-60x1-120x20对应的函数值为f(X)=0。

0由于上式中x1,x2系数为负，因而f(X)=0不是最小值。

因此所得的解不是最优解。

011(2)从初始基本可行解X迭代出另一个基本可行解X，并判断X 是否为最优解。

从一个基本可行解迭代出另一个基本可行解可分为两步进行：第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量；第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。

第三章 单纯形法在线性规划的计算求解中，应用最多且最著名的就是单纯形法。

这种方法是美国运筹学家G .B.Dantzig 丹捷格在1947年提出的。

后来经过人们多次改进，形成了许多变种。

实践证明单纯形法是一种使用方便、行之有效的算法。

§3.1 单纯形法的原理基本可行解的存在定理已经表明，若线性规划有最优解，则一定存在最优基本可行解，因此求线性规划问题就归结为寻找最优基本可行解。

单纯形法的基本思想就是从一个基本可行解出发，检查该基本可行解是否为最优解；若不是，则再设法求另一个未检查过的基本可行解，如此继续，直到查询到最优解为止。

按照以上的思路，需要解决三个难题： 1、 如何求出第一个基本可行解？2、 如何判断这个基本可行解就是最优解？3、 若不是最优解，如何从一个基本可行解过渡到另一个未检查过的基本可行解？ 第一个问题的彻底解决尚需留待今后，但是我们知道，求基本可行解就是解线性方程组=A x B ，由于且()r m =A ，故可以解出m 个变量，称之为基本变量，剩下的n-m 个变量称之为自由变量。

于是，最简单的方法就是令所有的自由变量的值为零相应得到的解就是基本解。

例3.1 考虑线性规划1234134123m in 324..246350,1,2,3,4j z x x x x s t x x x x x x x j =-++-+=-++=≥= （3.1）把约束方程写成表格的形式，如表3-1：20 -4 1 6 -1 1 3 0 5从上述表格的左端可以看出，由第二、四列构成一个单位子矩阵，或曰子块，即对角元为1，其余为0，因此把2x 和4x 解出，即把2x 和4x 作为基本变量，余下1x 和3x 作为自由变量。

41321362453x x x x x x =-+=+- （3.2）令所有的自由变量130x x ==，而426,5x x ==，从而得到一个基本解(0,5,0,6)T 。

若需要判断该基本解是否基本可行解？只需看左端有单位子矩阵时，右列的元素是否都是非负，若是，则为基本可行解。

单纯形算法的一般原理单纯形法的基本思路是有选择地取基本可行解，即是从可行域的一个极点出发，沿着可行域的边界移到另一个相邻的极点，要求新极点的目标函数值不比原目标函数值差。

考虑到如下线性规划问题：其中Ａ一个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 →→→● 问题：➢ 要判断m 个系数列向量是否恰好构成一个基并不是一件容易的事。