第1章线性规划与单纯形法第3节单纯形法3.1举例3.2初始基可行解的确定3.3最优性检验与解的判断3.4基变换3.5迭代（旋转运算）单纯形法求解线性规划的思路：•一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。•但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。这样问题就得到了最优解单纯形：•是指0维中的点，一维中的线段，二维中的三角形，三维中的四面体，n维空间中的有n+1个顶点的多面体。•例如在三维空间中的四面体，其顶点分别为(0，0，0)，(1，0，0)，(0，1，0)，(0，0，1)•具有单位截距的单纯形的方程是∑xi≤1，并且xi≥0，i=1,2,…,m。3.1举例例6试以例1来讨论如何用单纯形法求解。例1的标准型为：maxz2x=13+x2+0x3+0+4x05x−(111)x1+2x2+x3=84x+1+x416=(1−12)4x2+x5=12x0≥j1j=,2",,5约束方程(1-12)式的系数矩阵1⎛2100⎞⎜⎟APPPPP1=(),,,,234=45⎜0010⎟⎜⎟0⎝4001⎠从(1-12)式中可以看到x3,x4,x5的系数列向量⎛1⎞⎛0⎞⎛0⎞1⎛0⎞0⎜⎟⎜⎟⎜⎟⎜⎟PPP=0,=1,=03⎜⎟4⎜⎟5⎜BPPP⎟=()3,,45=0⎜1⎟0⎜⎟⎜⎟⎜⎟⎜⎟⎝0⎠⎝0⎠⎝1⎠0⎝0⎠1是线性独立的，这些向量构成一个基x⎧=38−x1−22x从(1-12)式可得到:⎪⎨x4=16−14x(1−13)⎪⎩x5=12−x42将(1-13)式代入目标函数(1-11)maxz2x=13+x2+0x3+0+4x05x−(111)得到z0=+2x1+3x2(1−14)•当令非基变量x1=x20。这时得到一=0，便得到z=个基可行解:X(0)=(0,0,8,16,12)T•这个基可行解表示：工厂没有安排生产产品Ⅰ、Ⅱ；资源都没有被利用，所以工厂的利润指标z=0。从分析目标函数的表达式(1-14)可以看到•非基变量x1,x2(即没有安排生产产品Ⅰ，Ⅱ)的系数都是正数，因此将非基变量变换为基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品Ⅰ或Ⅱ，就可以使工厂的利润指标增加。所以只要在目标函数(1-14)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与基变量进行对换。如何确定换入、换出变量•一般选择正系数最大的那个非基变量x2为换入变量，将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。•现分析(1-13)式，当将x2定为换入变量后，必须从x3,x4,x5中确定一个换出变量，并保证其余的都是非负，即x3,x4,x5≥0。非负限制（可行性）当x1=0,由(1-13)式得到⎧x3=8−2x2≥0⎪⎨x4=16≥0(1−15)⎪⎩x=512−4x2≥0•x只有选择时，才能3=)4/21,-,2/8(nim=2使(1-15)式成立。•因当x2=3时，基变量x5=0，这就决定用x2去替换x5。实际意义•每生产一件产品Ⅱ，需要用掉各种资源数为(2，0，4)。•由这些资源中的薄弱环节，就确定了产品Ⅱ的产量。•这里就是由原材料B的数量确定了产品Ⅱ的产量x2=12/4=3件。位置对换为了求得以x3,x4,x2为基变量的一个基可行解和进一步分析问题，需将(1-13)中x2的位置与x5的位置对换。得到x⎧=38−x1−22x⎪⎨x4=16−x41(1−13)⎪⎩x5=12−x42⎧x3+2x2=8−x1()1⎪⎨x4=16−x14()(21−16)⎪4x=12−x3⎩⎪25()高斯消去法•)式中x61-1将(2。的系数列向量变换为单位列向量其运算步骤是：•③′=③/4；①′=①-2×③′;②′=②,•并将结果仍按原顺序排列有：⎧1x=2−x+x()1'⎪3125⎪⎪'⎨x4=16−x41()21()−17⎪1'⎪x2=3−x5()3⎩⎪4再将(1-17)式代入目标函数(1-11)式得到3z=9+x2−x1()−18145(1)令非基变量x1=x5到得=0，z=9，并得到另一个基可行解XX(1)=(0,3,2,16,0)T迭代•从目标函数的表达式(1