第五章 单纯形法（1基本思路和原理）

第五章 单纯形法Singlex Method第五章 单纯形法由美国数学家丹捷格(G.B.Dantzig)提出的，得到最广泛应用的线性规划的代数算法单纯形法，这恐怕是在运筹学发展史上最辉煌的一笔。对于只有 两个决策变量 的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解 . 我们在第三章所介绍的线性规划问题的计算机解法就是基于单纯形法编程来解决可以含有上千个决策变量的及上千个约束条件的复杂的线性规划问题。第五章 单纯形法 5.1 单纯形法的基本思路和原理5.1 单纯形法的基本思路和原理线性规划问题 ( )( )( )(i=1, ， m)(j=1, ， n)可行解：满足上述约束条件（），（）的解 ， 称为线性规划问题的可行解全部可行解的集合称为可行域5.1 单纯形法的基本思路和原理线性规划问题 ( )( )( )(i=1, ， m)(j=1, ， n)最优解：使目标函数（）达到最大值的可行解称为最优解5.1 单纯形法的基本思路和原理基：设为约束方程组（）的 mn 阶 系数矩阵 ，（设 n m），其 秩 为 m，是矩阵中的一个 mm 的 满秩子矩阵 ，称是线性规划问题的一个 基 不失一般性，设中的每一个列向量 j（ j， ， m）称为 基向量 ，与基向量 j对应的变量 xj称为 基变量 。线性规划中除了基变量以外的变量称为 非基变量 。5.1 单纯形法的基本思路和原理标准形式为 :目标函数： max z = 50x1+100x2+0s1+0s2+0s3约束条件： x1 + x2 +s1 = 3002x1 + x2 +s2 = 400x2 +s3 = 250x1, x2, s1, s2, s30 。这是由三个五元线性方程组成的方程组，它的系数矩阵为 :中的每一个列向量 p3, p4, p5 是 基向量 ，与其对应的变量 s1, s2, s3是 基变量 。除了基变量以外的变量 x1, x2是非基变量。5.1 单纯形法的基本思路和原理可以看到 s1, s2, s3的系数列向量这是由三个五元线性方程组成的方程组，它的系数矩阵为 :是线性独立的 ,这些向量构成一个基5.1 单纯形法的基本思路和原理基：设为约束方程组（）的 mn 阶 系数矩阵 ，（设 n m），其 秩 为 m，是矩阵中的一个 mm 的 满秩子矩阵 ，称是线性规划问题的一个 基 不失一般性，设中的每一个列向量 j（ j， ， m）称为 基向量 ，与基向量 j对应的变量 xj称为 基变量 。线性规划中除了基变量以外的变量称为非基变量。在此例题中：都是该线性规划的一个 基 。这些 基 都是由 3个线性无关的系数列向量组成的 ,对应的 基变量分别为 x1 , x2 , s1 ; s1, s2, s3; x2 ,s1,s2。 5.1 单纯形法的基本思路和原理基解：在约束方程组（ E）中，令所有的非基变量：又因为有 ，根据克莱姆法则，由 m个约束方程可以解出 m个基变量的唯一解 。将这个解加上非基变量取 0的值有 ，称 X为线性规划问题的基解。我们找到 A 的一个基 :令这个基的非基变量 x1, s2 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b即 :求解 ,即可得到基变量的唯一一组解 : x2= 400 , s1= -100 , s3= -150加上非基变量 : x1= 0, s2 = 0, 得到此线性规划的一个基解 .x1=0,x2=400s1=-100s2=0s3=-150我们找到 A 的一个基 :令这个基的非基变量 x1, x2 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b即 :求解 ,即可得到基变量的唯一一组解 : s1=300 , s2=-400 , s3=250加上非基变量 : x1= 0, x2 = 0, 得到此线性规划的一个基解 .x1=0,x2=0,s1=300s2=400s3=2505.1 单纯形法的基本思路和原理基解：在约束方程组（ E）中，令所有的非基变量：又因为有 ，根据克莱姆法则，由 m个约束方程可以解出 m个基变量的唯一解 。将这个解加上非基变量取 0的值有 ，称 X为线性规划问题的基解。5.1 单纯形法的基本思路和原理线性规划问题 ( )( )( )(i=1, ， m)(j=1, ， n)基可行解：满足变量非负约束条件 ( G ) 的基解称为基可行解。可行基：对应于基可行解的基称为可行基。我们找到 A 的一个基 :令这个基的非基变量 x1, x2 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b即 :求解 ,即可得到基变量的唯一一组解 : x2= 400 , s1= -100 , s3= -150加上非基变量 : x1= 0, s2 = 0, 得到此线性规划的一个基解 .x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,我们找到 A 的一个基 :令这个基的非基变量 x1, x2 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b即 :求解 ,即可得到基变量的唯一一组解 : s1=300 , s2=-400 , s3=250加上非基变量 : x1= 0, x2 = 0, 得到此线性规划的一个基解 .x1=0,x2=0,s1=300s2=400s3=250x1=0,x2=0,s1=300s2=400s3=250均为基解x1= 0,x2= 400,s1= -100,s2= 0,s3= -150,基可行解 不是基可行解均为基可行基 不是可行基由于在这个基解中 s1 100， s3 150，不满足该线性规划最后一个 变量非负的约束条件 ，显然不是此线性规划的 可行解 ，一个 基解可以是可行解 ， 也可以是非可行解 ，它们之间的主要区别在于其 所有变量 的解是否满足 非负的条件。5.1 单纯形法的基本思路和原理5.1 单纯形法的基本思路和原理定理 :线性规划问题的基可行解 X 对应线性规划问题可行域的顶点 .在这里，可行域的顶点已不再像图解法中那样直接可见了。在单纯形法中的可行域的顶点叫做 基可行解 ，第一个找到的可行域的顶点叫做 初始基可行解 。5.1 单纯形法的基本思路和原理例：找出下述线性规划问题的全部基解，指出其中的基可行解，并确定最优解：max z = 2 x1 + 3 x2 + x3 x1 + x3 = 5x1 +2x2 +x4 =10 x2 +x5=4x1-5 0矩阵方程 :我们找到 A 的一个基 :令这个基的非基变量 x1, x2 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b得到基解 : x1=0,x2=0,x3=5x4=10x5=4代入目标方程式 : max z = 2 x1 + 3 x2 + x3, 得到 Z = 55.1 单纯形法的基本思路和原理x1 x2 x3 x4 x5 z 是否基可行解 0 0 5 10 4 5 0 4 5 2 0 17 5 0 0 5 4 10 0 5 5 0 -1 20 10 0 -5 0 4 15 5 2.5 0 0 1.5 17.5 5 4 0 -3 0 22 2 4 3 0 0 19 我们找到 A 的一个基 :令这个基的非基变量 x1, x5 为零 , 这时约束方程就变为基变量的约束方程 :矩阵方程 AX = b得到基解 :x1=0,x2=4,x3=5x4=2x5=0代入目标方程式 : max z = 2 x1 + 3 x2 + x3, 得到 Z = 17即 :5.1 单纯形法的基本思路和原理x1 x2 x3 x4 x5 z 是否基可行解 0 0 5 10 4 5 0 4 5 2 0 17 5 0 0 5 4 10 0 5 5 0 -1 20 10 0 -5 0 4 15 5 2.5 0 0 1.5 17.5 5 4 0 -3 0 22 2 4 3 0 0 19 5.1 单纯形法的基本思路和原理单纯形法的基本思路： 从可行域中某一个顶点开始，判断此顶点是否是最优解， 如不是则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。 直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。5.1 单纯形法的基本思路和原理定理 :线性规划问题的基可行解 X 对应线性规划问题可行域的顶点 .找顶点就是找基可行解 5.1 单纯形法的基本思路和原理一、找出一个初始基可行解在第二章的例 1中我们得到以下数学模型：例 1.目标函数 ： max z = 50 x1 + 100 x2 约束条件 ：s.t. x1 + x2 3002x1 +x2 400x2 250x1 ， x2 05.1 单纯形法的基本思路和原理标准形式为 :目标函数： max z = 50x1+100x2+0s1+0s2+0s3约束条件： x1