《系统工程》课件第03章 线性规划

第3章

线性规划3.1线性规划问题及其数学模型3.2

线性规划问题解的性质3.3单纯形法3.4二阶段法（人工变量法）3.5单纯形法小结3.6改进单纯形法3.7对偶线性规划问题3.8运输问题3.9指派问题3.10整数规划

本章主要介绍线性规划分析法的基本原理，使学生掌握图解法和单纯形解法的程序及运算，并借助现代化教学，能够初步应用线性规划法解决最低成本的农业生产资源最优配合方式和最大收益的生产结构问题。知识点聚焦第3章

线性规划

系统工程的主要目标是改造或建立系统，使系统的整体功能达到最优。线性规划是系统优化的重要方法之一。它包括线性规划、非线划、整数规划和动态规划等。20世纪30年代初出现的线性规划，到1947年丹茨基(G·B·Dantzig)发明单纯形法之后，理论上才得到完善，应用上也得到了迅速发展和推广。随着电子计算机的发展，成千上万个约束条件和变量的大型线性规划问题都可以求解。因此，无论从理论的成熟性看，还是从应用的广泛性看，线性规划都是运筹学的一个重要分支。它在工业、农业、交通运输、军事和计划管理等各方面都越来越得到广泛地应用。第3章

线性规划3.1线性规划问题及其数学模型

线性规划(LinearProgramming，简称LP)是在第二次世界大战前后逐渐发展和完善起来的运筹学的一个重要分支。它的应用范畴已渗透到工业、农业、商业、交通运输及经济管理等诸多领域。小到一个小组的日常工作和计划的安排，大至整个部门以至国民经济的计划的最优化方案的提出，都有它用武之地。正是由于它的适应性强、应用面广、计算技术比较简便等特点，使其成为现代管理科学的重要基础和手段之一。

现实中什么样的问题可以用线性规划问题去求解?在解决实际问题的过程中，需将实际问题归结为数学模型。什么是线性规划的数学模型，它具有哪些特点，标准形式如何，等等，则是这节需要讨论的问题。第3章

线性规划3.1.1问题提出

在生产过程中，要想提高工作效率和经济效益，一般有两种途径：一是进行技术改造，改进生产手段和条件。比如增添设备、改进工艺、挖掘潜力等等。另一条途径是在生产手段和条件都不变的情况下，改善生产的组织和计划管理，作出最优安排，使生产手段和条件得到充分的利用。线性规划方法就是解决后一类问题的工具。而这一类问题又分为两个方面，一是在一定限制条件下，使得工作成果可能大；二是为完成既定任务，使资源消耗尽可能少。下面几个问题可以说明这类问题。第3章

线性规划【例3-1】某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A、B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A、B、C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？上述问题的数学模型：设该厂生产x1台甲机床和x2乙机床时总利润最大，则x1，x2应满足（目标函数）(3-1)（约束条件）(3-2)3.1.1问题提出第3章

线性规划这里变量x1，x2称之为决策变量，(3-1)式被称为问题的目标函数，(3-2)中的几个不等式是问题的约束条件，记为s.t.(即subjectto)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。

总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。

在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。3.1.1问题提出第3章

线性规划【例3-2】某工厂计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A，B两种原材料的消耗，如表3-1所示。该工厂生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问如何安排计划使工厂获利最多?

所谓“如何安排生产计划”，意指产品Ⅰ，Ⅱ各生产多少，每指定一次两种产品的产量，就决定了一个生产方案，而一个生产方案决定一个获利值。上述问题的实质是寻找一个可行的生产方案(满足资源和设备约束)，使得工厂的获利值达到最大。3.1.1问题提出第3章

线性规划

解：这个问题可以用以下的数学语言来描述。

假设x1，x2分别表示产品Ⅰ，Ⅱ的产量。可行的生产方案要考虑不能超出设备的有效台时数，即可用不等式表示为：x1+2x2≤8，同时，还要考虑满足原材料A，B的资源约束条件，即用不等式表示为4x1≤16，4x2≤12。

对于产量x1，x2，该工厂的获利值f可表示为f=2x1+3x2。工厂的目标是在满足设备能力和原材料限制的条件下，如何确定产量x1和x2，使工厂的获利最大。

综上所述，安排生产计划问题可归纳为进行求解。3.1.1问题提出第3章

线性规划由此，把这类实际问题转换为数学模型可归结为三个基本步骤。

(1)确定决策变量，如【例3-2】中产品Ⅰ，Ⅱ的产量确定。决策变量必须是可控制的，通常用x1，x2，⋯，xn来表达。

(2)恰当地表达所要追求的目标(目的)，如【例3-1】中工厂追求的最大获利。目标通常用决策变量的函数来表达，称为目标函数。目标可以是单一的，也可以是多个的，但线性规划问题中一般只讨论目标单一的情形。

(3)把现实中的各种限制用含有决策变量x1，x2，⋯，xn的数学关系式来表达，称为约束条件，诸如资源限制、能力限制等。3.1.1问题提出第3章

线性规划【例3-3】(下料问题)。某工厂制造一种机床，每台机床需A，B，C三种不同长度的轴各一根，其毛坯长度：A为2.9m，B为2.1m，C为1.5m，它们用同一种圆钢来下料，每根圆钢长为7.4m。要造100台机床，问如何下料最好?试建立其数学模型(不考虑下料截口损耗）。解

将各种可能的下料方案排列程表3.2，设圆钢总数为f根，则由题意有(3-3)下料方案其中：3.1.1问题提出第3章

线性规划上述模型即为所求模型。通过分析表3-2，发现其中的方案3、5、7、8的料头过长，不经济，如果把它们舍弃，对剩下的4种方案进行搭配，仍然可以满足题意。为此可以将上述模型简化为下列模型(保持变量下标不变)。即(3-4)3.1.1问题提出第3章

线性规划【例3-4】(运输问题)。设有甲、乙、丙3个仓库，存有某种货物分别为7t、4t和9t。现在要把这些货物分别送A，B、C、D这4个商店，其需要量分别为3t、6t、5t和6t，各仓库到各商店的每吨运费以及收、发总量见表3-3。

现在要确定一个运输方案：从哪一个仓库运多少货到哪一个商店，使得各个商店都能得到货物需要量，各个仓库都能发完存货，而且总的运输费用最低?试建立其数学模型。3.1.1问题提出第3章

线性规划

解

记总运费为z设xij为i仓库到j商店的货物量，其中i=1，2，3分别代表甲、乙、丙仓库，j=1，2，3，4分别代表A，B，C，D商店，则根据题意

上述各例，都是要求一组非负变量，在满足一组线性等式或线性不等式的前提下，使一线性函数取得最大值或最小值，这一类问题就称为线性规划问题。(3-5)3.1.1问题提出第3章

线性规划将上述问题得出的数学表达式加以概括和抽象，就可得到线性规划问题的数学模型为求一组变量xj，j=1，2，...，n，满足条件使函数取得最大值或最小值。如果简写，则线性规划问题的数学模型可以表示为(3-6)(3-7)(3-8)3.1.1问题提出第3章

线性规划式(3-8)称为目标函数，式(3-9)称为约束条件。式中max(min)f：目标函数f取最大（最小）值；xj：决策变量，又称为生产活动或活动方式；cj：决策变量在目标函数中的系数，又称为利益系数、价值或效果系数；aij：决策变量在约束条件中的系数，又称为投入产出系数或技术系数bi：资源限制量；n：决策变量的个数；m：约束条件(不包括非负约束条件)的个数。

把满足约束条件式(3-2)的任意一组解称为线性规划间题的可行解，使得目标函数f取得最优值的可行解称为线性规划问题的最优解。如何求得线性规划问题的最优解，就是本章索要讨论的中心问题。(3-9)3.1.1问题提出第3章

线性规划3.1.2线性规划问题数学模型的一般形式从例【3-1】~【3-4】的线性规划可以看出，它们具有以下共同特征。(1)每一个问题都用一组未知数(x1，x2，⋯，xn)表示某一方案，这组未知数的一组定值就代表一个具体方案。通常要求这些未知数取值是非负的。(2)存在一定的限制条件(称为约束条件，也可用缩写s.t.表示)，这些限制条件都可以用一组线性等式或线性不等式来表达。(3)都有一个目标要求，并且这个目标可表示为一组未知数的线性函数(称为目标函数)。按研究的问题不同，要求目标函数实现最大化或者最小化。一般来讲，这类问题可用数学语言描述如下

(3-10)s.t.(3-11)第3章

线性规划

这就是线性规划的数学模型。式(3-10)方程称为目标函数，式(3-11)与式(3-12)称为约束条件，其中，式(3-12)也称为非负条件。也是线性规划问题的一般形式。可简写为：(3-12)(3-13)(3-14)3.1.2线性规划问题数学模型的一般形式第3章

线性规划3.1.3线性规划问题数学模型的标准形式由例【3-1】~【3-4】可知，线性规划问题可能有各种不同的形式。目标函数，有的要求实现最大化，有的要求最小化；约束条件可以是“≤”形式的不等式，也可以是“≥”形式的不等式，还可以是等式。这种多样性给求解问题的讨论和求解程序的标准化带来不便。在所有bi≥0，i=1，2，…，n的前提下，有必要化成规范形式。又称标准形式。为了求解的方便，就需要把线性规划问题的一般数学形式化成如下标准形式。即：(3-15)s.t.(3-16)(3-17)第3章

线性规划(3-18)(3-19)进一步可用矩阵型式表示：(3-20)s.t.(3-21)3.1.3线性规划问题数学模型的标准形式第3章

线性规划标准型的特征：目标函数最大化；约束条件为等式；右端相为非负值；决策变量非负值。目标函数转化：1)目标函数为求最小值若原问题的目标函数为minf，则令，于是有约束条件的转化：2)含有不等式约束条件这类型式往往有两种情形：若原问题的第i个约束条件为则可在不等式的左边加上一个新的变量使其变为等式约束，即称为松弛变量。如：(3-23)(3-22)3.1.3线性规划问题数学模型的标准形式第3章

线性规划则可以通过引进非负变量xn+1使两边相等，即这里xn+1称为松弛变量。若原问题的第i个约束条件为则可在不等式的左边减去一个新的变量使其变为等式约束，即称为剩余变量，也称为松弛变量。如：这里xn+1称为剩余变量。

应该指出，引入松弛变量和剩余变量后，对目标函数无任何影响，因为它们在目标函数中的系数全为零。(3-24)(3-25)则(3-26)3.1.3线性规划问题数学模型的标准形式第3章

线性规划3)所有变量要求非负还需要提到一点的是，在标准型中要求bi≥0(i=1，2，⋯m)，如果存在bi<0的情形，则可在约束方程式两边各乘上“-1”号，使所有bi≥0得到满足。如：4)含有自由变量，及非负约束的变量若原问题中第j个变量xj没有非负约束，则xj叫自由变量。自由变量可用两个非负变量之差代换，即令

，并代入约束条件和目标函数中，便可消去自由变量。这也是现实中，有些变量可能从物理意义或经济意义上讲没有非负要求。为了满足标准型对变量非负的要求所做的变换。(3-27)3.1.3线性规划问题数学模型的标准形式第3章

线性规划【例3-5】将以下线性规划问题转化为标准形式解：目标函数属于求极小值，约束中有大于、小于等情况。按前述标准化方法进

行转换。(1)令

，或者下成

。(2)在第一个约束条件中引入松弛变量x6，第2个约束条件中引入剩余变量x7。S.t.(3)对第三个约束条件两边同乘以-1。(4)将引入的变量代入目标函数和约束条件，并令

，把求最小变成求最大。3.1.3线性规划问题数学模型的标准形式第3章

线性规划于是有：解此规划问题，得到

和

的值，则

，

，从而可得到原问题的解。3.1.3线性规划问题数学模型的标准形式第3章

线性规划3.1.4. 线性规划问题解的概念

前一节介绍了线性规划的数学模型，建立数学模型的目的自然是为了求解，而要找到好的求解方法，首先必须对模型的解及其基本性质有一个清楚的了解。

对于一般线性规划问题(3-28)(3-29)称满足式(3-29)的点(或向量)X为该问题的解(solution)；而同时又满足式(3-29)的第二式，则称点X为可行解(feasiblesolution)；所有可行解组成的集合称为可行域(feasibleregion)或可行解集。可行域上满足式(3-28)的点称为最优解(optimalsolution)，最优解对应的目标函数值称为最优值。第3章

线性规划

在讨论线性规划问题的解法之前，先来介绍一下标准形式线性规划问题解的概念。对于标准形式的线性规划问题，其约束条件(3-29)为下列线性方程组：(3-30)

在此约束条件中，前m个等式构成线性方程组，对此方程组，若m=n，且系数行列式不为零，则方程组有唯一一组解，故不存在优化问题。若m≠n，一般来说m<n，如果方程组的系统矩阵的秩为m，则该方程组有无穷多个解。假设前m个变量的系数列向量是线性独立的，构成的系数矩阵3.1.4. 线性规划问题解的概念第3章

线性规划

称为线性问题的一个基，称为基向量，称与基向量对应的变量为基变量，其他变量称为非基变量。若令非基变量等于零，则可求得一个解为这样的解称为基本解，它的非零变量的个数不大于秩m。基本解不一定都是可行的。若基本解同时满足非负条件，就称为基本可行解，对应于基本可行解的基称为可行基。若基本可行解中的非零变量的个数小于m，即基变量出现零值时，则此基本可行解称为退化的基本可行解。当其非零变量的个数等于m，即基变量均为正值时，则此基本可行解称为非退化的基本可行解。3.1.4. 线性规划问题解的概念第3章

线性规划显然，如果基矩阵B为m阶单位阵，则问题的一个基本可行解为

线性规划问题的一个基本可行解，对应于可行域上的一个顶点。若线性规划问题有最优解，则必定在某个顶点处得到。虽然顶点数目是有限的，它不超过

，采用枚举法找出所有基本可行解，然后一一比较，最终可以找到最优解。但当m，n相当大时，这种办法是行不通的。所以，需用另一种更好的方法-----单纯形法。3.1.4. 线性规划问题解的概念第3章

线性规划3.2

线性规划问题解的性质3.2.1

几何意义上的几个基本概念

对一个线性规划问题，建立数学模型之后，面临着如何求解的问题。这里先介绍含有两个未知变量的线性规划问题的图解法，它简单直观。这里通过图像法来直观的了解线性规划问题的最优解。图解法的步骤：步骤1：确定可行域。Step1：绘制约束等式直线，确定由约束等式直线决定的两个区域中哪个区域对应着由约束条件所定义的正确的不等式。通过画出指向正确区域的箭头，来说明这个正确区域。Step2：确定可行域。步骤2：画出目标函数的等值线，标出目标值改进的方向。步骤3：确定最优解。用图示的方式朝着不断改进的目标函数值的方向，移动目标函数的等值线，直到等值线正好接触到可行域的边界。等值线正好接触到可行城边界的接触点对应着线性优化模型的最优解。第3章

线性规划【例3-6】求解线性规划s.t.解：在二维平面坐标中，每个线性不等式约束的点集是一个半平面（由一条直线分界），通常一个二维线性规划问题的可行域如果是有界的，则是一个多边形围成的区域。Step1．先在平面直角坐标系

里画出上述线性规划的可行域Ｒ。事实上在约束条件中，每个线性等式代表平面上一条直线，这直线将坐标平面分成两部分，于是每个线性不等式代表一个半平面。本例中五个线性不等式代表的五个半平面的交，就是可行域Ｒ，显然它是一个凸多边形，这个凸多边形有五个顶点，它们分是Ｏ（０，０），Ａ（０，７），Ｂ（５，７），Ｃ（８，４），Ｄ（８，０），如图3-1。3.2.1

几何意义上的几个基本概念第3章

线性规划图3-1【例3-6】题解的图示Step2．求解线性规划，就是要在上述凸多边形Ｒ中找一点

，使目标函数取最大值。对任意固定的常数Ｃ，直线上的每点都有相同的目标函数值Ｃ，故该直线也称为“等值线”。当Ｃ变化时，得出一族相互平行的等值线，这些等值线中有一部分与可行域相交。要在凸多边形即可行域Ｒ中找这样的点，使它所在的等值线具有最大值Ｃ。当Ｃ<０时，直线

与Ｒ不相交；当Ｃ＝０时，直线

与Ｒ有唯一交点，即顶点（０，０）；当Ｃ由０增大时，等值线平行向右上方移动，与Ｒ相交于一线段；当Ｃ增至一定程度时，等值线与可行域Ｒ只有唯一交点，即顶点（5，7），这时Ｃ＝9.8；若Ｃ继续增大，等值线与Ｒ将不再有交点。由此可见，顶点（5，7）是使Ｒ中目标函数达到最大值的点，于是线性规划有唯一3.2.1

几何意义上的几个基本概念第3章

线性规划解

，这时，f*＝maxf＝9.8。若将例3中求目标函数的最大值改为求最小值，即求

约束条件不变。这时，令直线族

中的C不断减小，等值线将向左下方平行移动。当C＝0时，等值线与可行域只有唯一交点即顶点(0，0)，若C继续减小，等值线与Ｒ将不再有交点，于是线性规划有最优解：

，这时，f*＝minf＝0。从上面的图解法中可以看出：两变量线性规划的可行域一定是一个凸多边形，线性规划如果有解，则该解一定可以在凸多边形的顶点上达到。

有时线性规划的最优解不是唯一的。例如我们将【例3-6】中线性规划的目标函数改为,而约束条件不变，这时，对直线族

，令C不断增大，当C增至10.8时，等值线与Ｒ相交于线段BC，该线段的两个端点是Ｒ的顶点，当C继续增大时，等值线与R不再相交，故这时线段BC上的点都是线性规划的最优解，最优值

由此可见：若有两个顶点是最优解，则这两个顶点连线上所有的点都是最优解。线性规划的可行域可能是空集，这意味着约束条件互相矛盾，线性规划无可行解。3.2.1

几何意义上的几个基本概念第3章

线性规划【例3-7】

求解线性规划(无可行解)解：因约束条件中前两个不等式相互矛盾，线性规划无可行解（见图3-2）。图3-2【例3-7】解的图示

注意：有时线性规划的可行域无界，这时线性规划的解可能存在，也可能没有有界的最优解。3.2.1

几何意义上的几个基本概念第3章

线性规划【例3-8】

求解线性规划(无界解)解：该线性规划的可行域Ｒ无界（图3-3），用图解法可以看出，该线性规划无有界最优解。图3-3【例3-8】解的图示3.2.1

几何意义上的几个基本概念第3章

线性规划注意：本例中，若改求目标函数的最小值，则它仍有最优解：,这时，f*＝minf＝0。通过图解法看到，线性规划问题的所有可行解构成的可行域，一般是凸多边形的(有时可行域是无界的)。若存在最优解，则一定在可行域的某顶点上得到；若在两个顶点上同时得到最优解，则这两顶点连线上的任一点都是最优解。若可行解无界，则可能发生无最优解的情况；若无可行域，自然也就既无可行解也无最优解。因此有如下结论：（1）线性规划问题的所有可行解组成的可行域是一凸集，即可行域上任意两点之间的连线都可在可行域内。（2）若一个线性规划问题存在最优解，则至少有一个最优解在可行域的顶点上达到；若在两个顶点上同时达到最优，则这两顶点连线上的任一点都是最优解，这时称有无穷多个最优解。（3）若可行域呈现无界区域，则可能有最优解，也可能出现最优解无界的情形，这时称最优解不存在或无最优解。（4）若可行域为空集，这时无可行解，当然也就无最优解。上述结论对于含有两个以上变量的线性规划问题同样适用。图解法虽然直观、简便，但只能用于两个，最多3个变量的线性规划问题，当变量个数超过3个时，用图解法就很难处理了。因此在后面将要介绍线性规划问题的一般解法单纯形法。3.2.1

几何意义上的几个基本概念第3章

线性规划推广到线性规划问题的基本性质：(1)线性规划问题的可行域如果非空，则是一个凸集-凸多面体。(2)如果线性规划问题有最优解，那么最优解可在可行域的顶点中确定。(3)如果可行域有界，且可行域只有有限个顶点，则问题的最优解必存在，并在这有限个顶点中确定。(4)最优解可由最优顶点处的有效约束形成的方程组的解确定。3.2.1

几何意义上的几个基本概念第3章

线性规划3.2.2线性规划问题的基本定理

下面将解两变量线规划问题时用图解法得出的结论推广到一般的情形。为此，先介绍凸集的概念。

【凸集定义】设Ｋ是ｎ维欧氏空间的一个点集，对Ｋ中任意两点Ｘ1，Ｘ2∈Ｋ，和任意实数

，若都有

，则称Ｋ为凸集。设Ｘ1，Ｘ2是ｎ维欧氏空间中的两个点，Ｘ是它们连线上的任意一点，且有向线段之比

，显然由

，可推出：

，故

时，

是Ｘ1，Ｘ2连线上的一点，称为Ｘ1，Ｘ2的凸组合。于是Ｋ是凸集的几何意义是，若Ｘ1，Ｘ2是Ｋ中任意两点，那么Ｘ1，Ｘ2连线上的点也是Ｋ中的点。图3-4几种凸集概念的示例

实心圆、实心球体、实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。例如三角形、凸多边形、四面体、凸多面体、园、球等都是凸集。如下图所示。第3章

线性规划其中，(a)、(b)是凸集，(c)不是凸集，(d)是两个图集的交集，也是凸集。

【顶点定义】设Ｋ是凸集，Ｘ∈Ｋ，且Ｘ不能用Ｋ中不同的两点Ｘ1，Ｘ2∈Ｋ表示成

的线性组合，故

的形式，则称Ｘ为Ｋ的一个顶点(或极点)。例如：三角形的顶点，四面体的顶点，园周和球面上任意一点，都是凸集的顶点。可以将两变量线性规划图解法中得到的结果推广到一般线性规划中去：（1）线性规划的可行域Ｒ是凸集；（2）线性规划若有最优解，则最优解一定可以在顶点上达到；（3）若有两个或两个以上的顶点都是线性规划的最优解，则这些点组成的凸组合也是最优解；（4）线性规划可行域顶点的个数是有限的，因此线性规划如果有最优解的话，总可以在有限个顶点中找到最优解。

3.2.2线性规划问题的基本定理

丹茨格的著名的单纯形法，就是根据上述原理，从一个初始的顶点开始，通过有限步，就能找到线性规划的最优顶点。几个基本定理（这里不作证明，有兴趣可参考相关资料）：【定理1】若线性规划问题存在可行解，则问题的可行域是凸集。（即连接线性规划问题任意两个可行解的线段上的点仍然是可行解。)【定理2】线性规划问题的基可行解x对应线性规划问题可行域的顶点。【定理3】线性规划问题有最优解，一定存在一个基可行解是最优解。第3章

线性规划3.2.2线性规划问题的基本定理第3章

线性规划3.3单纯形法

求解线性规划问题的单纯形方法(SimplexMethod)，是由美国数学家G.B.Dantzig于1947年首先提出来，至今这一数学方法仍然是解线性规划问题的行之有效的方法。它是从可行域的一个基本可行解(极点)出发，判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题无界为止。3.3.1单纯形法思路

单纯形法求解线性规划的思路：一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。这就是迭代，直到目标函数实现最大值或最小值为止。注意：单纯形是指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章

线性规划【例3-9】对例3.2线性规划模型进行求解。

解：第一步：将一般形式的线性规划问题化成标准型。在约束条件中，引入松弛变量

，有(3-31)第二步：确定初始基本可行解

为确定初始基本可行解，首先要找出初始可行基。由3.1.4节可知，如果在约束方程的系数矩阵中能找到m个线性无关的单位向量，就能很容易地得到问题的一个初始基本可行解。若原问题的约束条件（不包括非负约束条件，下同）为一组“≦”不等式，标准化后，第3章

线性规划可以松弛变量作为基变量，其余的变量为非基变量，令非基变量等于零，便可立即得到一个初始基本可行解。对于本例，

为基变量，

为非基变量，x1=x2=0。则问题的一个初始可行解为X=(0081612)T。此时的目标函数值

，这意味着工厂没有进行生产，对应的利润为零。这也正是生产规划的开始。

若原问题的约束条件为一组“≧”不等式或一组等式或3种约束组合，标准化后，如果约束方程的系数矩阵中不存在m个线性无关的单位向量，就要设法构成m个不同的单位列向量，有关这个问题将在后面进行讨论。

为明显起见，把基变量放在等式左边，非基变量放在等式右边，由式(3-31)得

(3-32)相应的目标函数用非基变量表示为：

从目标函数表达式可以看出，非基变量x1,x2的系数都是正数，因此增加x1或x2均可是目标函数f增加，所以只要在目标函数的表达式中还存在有正系数的非基变量，就表明目标函数还有增加可能，就需要将非基变量进行对换。单纯形法的实质上就是进行基变量和非基变量的代换过程。新进入左边的变量叫换入变量，被代换到右边的变量叫换出第3章

线性规划变量。每完成一次代换，就是一次迭代，而对应的目标函数值就相应地有所增加，至少也与代换前相同。第三步：确定换入换出变量，进行第一次迭代。

在进行单纯形发法迭代时，每次只能代换一个变量。一般选择正系数最大的那个非基变量为换入变量，并成为新的基变量，本例中，x2为换入变量。同时，还要从原来的基变量中确定出一个为换出变量，成为新的非基变量。换出变量的确定要经过计算换人变量的最大步长。x2作为换入变量，由于受到有关资源的限制，是不能随意安排调整的，把资源允许的最大调整量叫最大步长。故当x1=0时，要保证x3，x4

，x5>=0由(3-32)有即

显然，为同时满足以上3个条件，x2的调整量只能是，即x2=3为调整的最大步长。因此，x5为换出变量。

第3章

线性规划

这样一来就得到了新的基变量x3，x4，x2，新的非基变量为x1，x5。此时，需要把式(3-32)中x1，x5的位置对换，即由(3-32)中第3式得将上式代入(3-32)中，消去x2，有(3-33)

也将目标函数中的基变量用非基变量代换，得到调整后的目标函数为：

这样，f中，x1为正系数表明：还有潜力可挖，没有达到最大值；x5为负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当x5=0时，即不再利用这些资源。

此时，当非基变量x1=x5=0时，得到另一个基本可行解为X1=(032160)T

目标函数值为f=9，由此可见，调整x2后，目标函数值增加了9。从目标函数的表达式可看出，非基变量x1的系数为正，说明调整x1将会使目标函数继续增加，X1不是规划问题的最优解。第3章

线性规划第四步：确定新的换入换出变量，进行第二次迭代。

由于非基变量x5在目标函数中的系数为-3/4，调整x5将使目标函数值减少，又因目标函数中只有x1的系数为正，于是便知x1是新的换入变量，而新的换出变量还要通过计算最大的调整步长来确定。故当x5

=0，要保证

x3，x4

，x5>=0，有→x1的调整最大步长为x1=min{24-}=2x1的最大步长是由式(3-33)中的第1个方程确定的，对应的基变量x3为新的换出变量，由(3-33)中的第1式得

，将其带入(3-33)中的第2、第3式，消去x1，有

(3-34)调整后的目标函数为第3章

线性规划

当x3=x5=0时，可得到一个新的基本可行解为X2=(23080)T

对应的目标函数值为13。由于目标函数中非基变量x5的系数大于0，所以，即目前的基可行解不是最优解，x5为换入变量，同样用步长确定换出变量。故当x3=0，要保证

x1，x4

，x2>=0，有→(3-35)X5的调整最大步长为x5=min{-412}=4X5的最大步长是由式(3-33)中的第2个方程确定的，对应的基变量x4为新的换出变量，由(3-34)中的第2式得代入上式得令x3，x4为零，最优解为：X3=（4，2，0，0，4）T第3章

线性规划可以看出，目标函数中的系数均为负，故f=14为最优解。3.3.2单纯形表解法

上面的引例说明了用单纯形法解线性规划问题的基本思路和理论依据。但在实际求解中，用上述方法比较麻烦，而且容易出错，故多采用单纯形表解法，下面仍以上面的例子来说明表上求解的步骤和方法，并引出一般线性规划问题的解法。第一步：标准化(见前解法第1步)。第二步：找出初始基变量，并将目标函数中的基变量用非基变量代替。1)检查约束方程的系数矩阵是否含有机阶单位阵。若没有，则设法构造。m阶单位阵对应的变量为基变量，其余变量为非基变量。上面的问题3阶单位矩阵对应的变量x3，x4，x5为基变量，x1，x2为非基变量。2)检查目标函数申是否含有基变量，如果有，则用非基变量加以代换。上面问题的目标函数中不含有基变量，故不需代换。第三步：作初始单纯形表。

初始单纯形表就是把线性规划模型中的变量和相关的系数规则地排成一种表格，它和线性规划模型具有一一对应的关系。第3章

线性规划

对于上面的问题，可将目标函数写成类似于约束方程的形式，即

为了便于理解计算关系，现设计一种计算表，称为单纯形表，其功能与增广矩阵相似，下面来建立这种计算表。

将标准式约束条件与目标函数组成n+1个变量，m+1个方程的方程组。(3-36)为了便于迭代，可将上式方程组下称增广矩阵形式：

(3-37)

若将f看作不参与基变换的基变量，它与x1，x2，⋯，xm的系数构成一个基，这时可采用行初等变换将c1，c2，⋯，cm变换为零，使其对应的系数矩阵为单位矩阵。得到第3章

线性规划(3-38)依据增广矩阵，设计单纯形表如下：表(3-4)单纯形法XB

列中填入基变量，这里是x1，x2，⋯，xm；CB

列中填入基变量的价值系数，这里是c1，c2，⋯，cm；它们是与基变量相对应的；第3章

线性规划b列中填入约束方程组右端的常数；cj行中填入基变量的价值系数c1，c2，⋯，cn；θi列的数字是在确定换入变量后，按θ规则计算后填入；最后一行称为检验数行，对应各非基变量xj的检验数是表1-2称为初始单纯形表，没迭代一步构造一个新单纯形表。第3章

线性规划3.3.3单纯形表解步骤第一步：建立线性规划的数学模型，并使其标准化。标准化的要求为：(1)目标函数化成求最大值问题；(2)约束条件均表达为等式关系(必要时引入松弛变量和剩余变量)；(3)模型存在一个初始可行基———单位矩阵(必要时引入人工变量)。第二步：找出初始可行基，确定初始基可行解，建立初始单纯形表。第三步：检验各非基变量xj的检验数是则已得到最优解，可停止计算。否则转入下一步。第四步：在σj>0，j=m+1，⋯，n中，若有某个σk对应xk的系数列向量Pk≤0，则此问题是无界，停止计算。否则，转入下一步。第五步：根据

，在单纯形表中，

所在的列为主元列，主元列所对应的变量xk为换入变量（入基变量），按θ规则计算

，确定

所在的行为主元行，主元行在单纯形表中s对的基变量为换出变量（出基变量）。主元行与主元列相交的元素为主元素

，转入下一步。第3章

线性规划

第六步：以alk为主元素进行迭代，即用高斯消去法或称为旋转运算，将主元列中主元素变

为1，其他元素变为0，即把xk所对应的列向量变换为

第

l行

将XB列中的xl转换为xk，CB列中的cl换成ck，得到新的单纯形表。重复第三步～第六步，直到算法终止。

【例3-10】用【例3-2】的标准型来说明上述计算步骤。第3章

线性规划第一步：将模型标准化。取松弛变量x3，x4，x5为基变量，它对应的单位矩阵为基。(3-39)模型中已存在一个初始可行基，对应的基变量为x3，x4，x5，这就得到初始基可行解X(0)=(0，0，8，16，12)T将有关数字填入表中，得到初始单纯形表，见表3-5。表(3-5)第3章

线性规划

表(3-5)中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数，它们都为零，各非基变量的检验数为σ1=c1-z1=2-(0×1+0×4+0×0)=2σ2=c2-z2=3-(0×2+0×0+0×4)=3第二步：因检验数都大于零，且P1，P2有正分量存在，转入下一步；第三步：max(σ1，σ2)=max(2，3)=3，对应的变量x2为换入变量，计算θ(3-40)

它所在行对应的x5为换出变量。x2所在列和x5所在行的交叉处[4]称为主元素或枢元素(pivotelement)。第四步：以[4]为主元素进行旋转运算，即初等行变换，使P2变换为(0，0，1)T，在xB列中将x2替换x5，于是得到新表(3-6)。表(3-6)第3章

线性规划b列的数字是x3=2，x4=16，x2=3于是得到新的基可行解X(1)=(0，3，2，16，0)T目标函数的取值z=9第五步：检查表(3-6)的所有cj-zj，这时有c1-z1=2；说明x1应为换入变量。重复(2)～(4)的计算步骤，得表(3-7)。表(3-7)第3章

线性规划

第六步：表(3-7)最后一行的所有检验数都已为负或零。这表示目标函数值已不可能在增大，于是得到最优解目标函数值

z*=143.4二阶段法（人工变量法）

线性规划问题的单纯形法，若标准化后找不到m阶单位阵，为了得到问题的一组初始基变量，通常采用人造基，即给方程加入一个非负的虚拟变量，称这个虚拟变量为人工变量（剩余变量系数为-1，不能构成初始基变量）。

人工变量是虚拟变量，存在于初始基本可行解中，需要将它们从基变量中替换出来。若人工变量可以从基变量中替换出来，即基变量中不含有非零的人工变量，表示原问题有解；若人工变量不可以从基变量中替换出来，则表示原问题无可行解。

对于一个标准化的线性规划问题，其约束方程为(3-41)第3章

线性规划给第i个约束方程中加入一个人工变量

，得到(3-42)如果以为基变量

，，非基变量，便可得到问题的一个初始基本可行解X0=(00......0b1b2......bm)T。因为人工变量是加入到原约束方程组中的虚拟变量，为了不改变原来问题的性质，就应将它们从基变量中逐渐替换掉，即使人工变量为零。处理人工变量的方法有两阶段发和大M法，下面分别介绍。3.4.1二阶段法

两阶段法是将加入人工变量后的线性规划问题分两阶段来求解。第3章

线性规划第一阶段：在原线性规划问题中加入人工变量，构造模型。构造模型的目标函数为：

(3-43)(3-44)

用单纯形法对(3-44)模型求解。若w=0，即所有的人工变量都为零，说明原问题存在一个基本可行解，可以进行第二个阶段；若w<0，即不是所有人工变量都为零，这说明原问题无可行解，停止运算。

第二阶段：从第一阶段得到的基本可行解开始，继续用单纯形法进行迭代，直到找出原问题的最优解或判断无最优解。

说明：以上介绍的方法是对每个约束方程中都加入人工变量。如果原问题约束方程的系数矩阵中存在有一些单位向量，为减少计算工作量，可以只在部分约束方程中加入人工变量。

下面举例说明。第3章

线性规划【例3-11】用两阶段法求下列线性规划问题(3-45)解

第一步：标准化

在第1个约束条件中引入松弛变量x4，第2个约束条件中引入剩余变量x5，得到原问题的标准形式为(3-46)第3章

线性规划

第二步：确定初始变量，并将目标函数中的基变量用非基变量代替。

上一步中，约束方程只有x4的系数为单位向量，为形成3阶单位矩阵，在第2、第3个约束方程中分别引入人工变量x6和x7，得第一阶段的规划问题为(3-47)x4，x6，x7为基变量，将目标函数w中的基变量用非基变量代替，有

注：如果原问题的目标函数中也含有基变量时，也必须用非基变量代替。

第三步：作初始单纯形表

作初始单纯形表的基本要求与前面介绍的完全一样，唯一的区别是增加了第1阶段问题的目标函数w行，见下面表(3-8)表格。第3章

线性规划表(3-8)第3章

线性规划

第四步：确定主元

第1阶段问题以w为目标函数，主元的确定方法与前面相同。

第五步：进行第1阶段迭代

与前述方法相同，即换出变量退出基底，换入变量进入基底，化主元为1，主元列其它元素（包括f行元素）为零，完成一次迭代。若检验数行的检验数不全非正，则继续迭代。

该问题经过二次迭代后，w行的检验数全部非正，且有maxw=0，故得到了原问题的一组基变量x4，x2，x3，至此第1阶段迭代结束。

第六步：进行第2阶段迭代

从第1阶段的最终单纯形表中去掉人工变量x6，x7所对应的列及w行，得到第2阶段的单纯形表，见表3-9。第3章

线性规划经过一次迭代后，检验数全部非正，得到原问题的最优解为X=（41900）T相应的目标函数值f=2。第3章

线性规划3.4.2大M法

在一个线性规划问题的约束条件中加入人工变量后，目标函数应如何处理?由于希望人工变量对目标函数取值不受影响，因此，只有在迭代过程中把人工变量从基变量换出去，让它成为非基变量。为此，这就必须假定人工变量在目标函数中的价值系数为(-M)(M为很大的正数)，这样对于要求实现目标函数最大化的问题来讲，只要在基变量中还存在人工变量，目标函数就不可能实现最大化(取正值)。若对目标函数要求实现最小化时，在目标函数中给人工变量规定一个很大的正系数(+M)，其理由与前述相同。这就是大M法。下面用例子来说明计算方法。

大M法的基本思路是对标准型线性规划问题，引入人工变量后将其改造为：(3-48)s.t.(3-49)第3章

线性规划其中，M为充分大的整数，记为M>>1，下面举例说明大M法的具体迭代过程。【例3-12】试用大M法求解下面线性规划问题解：在上述问题的约束条件中加入松弛变量、剩余变量和人工变量，得到第3章

线性规划目标函数中，M是一个很大的正数。下面用单纯形法进行计算，见表3.10。第3章

线性规划由表(3-10)的最终计算表，得最优解，

由此可见，凡约束条件为大于或等于型不等式时，均需引入人工变量，在目标函数中，人工变量前面均应乘上系数M，M>>1，而且，在极大值问题中，M前面为负号。这样，可以保证在获得最优解时消去人工变量，如果人工变量不能通过迭代消去，则说明该问题无最优解。到此为止，对于任何形式的线性规划问题，总可以利用单纯形法，两阶段单纯形法或大M法对其求解。第3章

线性规划3.5单纯形法小结根据实际问题给出数学模型，列出初始单纯形表。进行标准化，见表(3-11)。分别以每个约束条件中的松弛变量或人工变量为基变量，列出初始单纯形表。第3章

线性规划(2)对目标函数求max的线性规划问题，用单纯形法计算步骤的框图见图3-5。图3-5单纯形法计算步骤的框图第3章

线性规划3.6改进单纯形法

对于较简单的线性规划问题，可以用单纯形表法求解，但当线性规划问题的规模较大时，用单纯形表求解会非常困难，甚至变得不可能。为此就出现了一种新的算法----改进的单纯形法。其实是通过矩阵求逆来实现规划问题解的方法。这种方法有助于计算机求解线性规划问题。

对标准形式的线性规划问题(3-50)第3章

线性规划令：则上式可用矩阵型式表示若用列向量Pj，j=1，2，...，n代表矩阵A的第j列，则有第3章

线性规划可设其前m个列向量是线性独立的，则

为线性规划问题的基矩阵。其余列向量构成的矩阵称为非基子矩阵。此时有A=(BN)。其中基矩阵B对应的变量为基变量，用XB表示，，非基子矩阵N对应的变量为非基变量，用XB表示，

，则有X=(XBXN)T。同样地，C可以表示为C=(CBCN)T，于是式（3-15）可改写为

(3-52)由上式得：(3-53)将其代入目标函数整理得(3-54)其中，称为单纯形算子。第3章

线性规划注意到，则表示了检验数行的所有元素。而λ又可以表示为(3-55)此时，单纯形表如下如果检验数，则为问题的最优基可行解，相应的目标函数值，否则，应确定新的基矩阵B1继续迭代。第3章

线性规划实际上，单纯形迭代过程是由一个基矩阵到另一个基矩阵转移，而且每一次迭代只能是一个变量换入，一个变量换出，即基阵中只有一个列向量发生变化。设为初始基矩阵。若对应的检验数行向量不全非正。即基矩阵B0不是最优基，根据前述的方法确定的换入变量为xk，则以列向量PK代换Pl得到新的基矩阵为由前面的推导可知，如果求得了，那么就可以求出一组新的基本可行解、相应的目标函数值和检验数等。由此可见，在改进单纯形法计算中，关键是每次迭代时基矩阵的逆阵B-1。下面讨论其求法。与单纯形表解法类似，改进单纯形法通常也是用m个单位向量构成的单位矩阵作为初始矩阵，即第3章

线性规划以列向量Pk代换Pl后，得到的新基矩阵为因此，基矩阵求逆实际上就是计算机形如上式这种矩阵的逆，根据线性代数理论，不难求得B1的逆为改进单纯形法的计算步骤与单纯形法类似，举例说明如下。第3章

线性规划【例3-13】用改进单纯形法求下列线性规划问题解：第1步：标准化，引入松弛变量x3，x4，x5得第3章

线性规划第2步：确定初始可行解，考虑矩阵表示，由上式得取x3，x4，x5为初始基变量，初始基变量为则有，可得非基变量的列向量为第3章

线性规划初始基本可行解为相应的目标函数为非基变量检验数为可将上述结果列表3-13，实际上是按3-10表列出。第3章

线性规划因，故B0不是最优基。第3章

线性规划第3步：确定新基，进行第一次迭代。由，x1为换入变量，P10为换入列向量。则由可知，6为主元，x5为换出变量，新的基变量为x3，x4，x1，故得新基B1为此时有由此得第3章

线性规划上式中，，，故x2为换入变量，P21为换入列向量。第3章

线性规划

同样的，按照第2步的方法可知，x3为换出变量，P31为换出列向量，新的基变量为x2，x4，x1，故得新基B2为此时有由此可得第3章

线性规划因检验数，所以，迭代终止，得到问题的最优解为相应的目标函数f2=31/4，上述结果可用如下表给出。第3章

线性规划

小结：从以上运算过程可以看出，对于手算来说，采用改进单纯形法并不方便，而且很容易出错，但对于计算机而言，却是得心应手的事情。既节约了内存，也减小了运算量。

第3章

线性规划3.7对偶线性规划问题3.7.1对偶规划先看看下面的例子在【例3-2】中，已建立的规划问题模型LP1为进行求解。第3章

线性规划现从另一角度来讨论这个问题。假设该厂的决策者决定不生产产品Ⅰ、Ⅱ，而将其所有资源出租或外售。这时工厂的决策者就要考虑给每种资源如何定价的问题。设用y1，y2，y3分别表示出租单位设备台时的租金和出让单位原材料A，B的附加额。他在做定价决策时，做如下比较：若用1个单位设备台时和4个单位原材料A可以生产一件产品Ⅰ，可获利2元，那么生产每件产品Ⅰ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅰ的利润，这就有。同理将生产每件产品Ⅱ的设备台时和原材料出租或出让的所有收入应不低于生产一件产品Ⅱ的利润，这就有

。把工厂所有设备台时和资源都出租或出让，其收入为

从工厂的决策者来看当然ω愈大愈好，但从接受者来看他的支付愈少愈好，所以工厂的决策者只能在满足大于等于所有产品的利润条件下，提出一个尽可能低的出租或出让价格，才能实现其原意，为此需解如下的线性规划问题LP2

(3-56)第3章

线性规划显然，当

时，工厂决策者认为这两种考虑具有相同的结果，都是最优方案。比较LP1和LP2，可知它们之间有着密切的联系，两者包含有相同的数据，只是位置不同而已。如果称前者为原问题，则后者就叫前者的对偶问题，反过来也是如此，即两者互为对偶问题。更一般地，若原问题为(3-57)则对偶问题为(3-58)第3章

线性规划其中，yi叫做对偶变量。若表示成矩阵形式，则有(3-59)上式为对偶关系的非对称形式。其中，A是矩阵；C是n维向量；b是m维列向量；X是n维列向量，为原问题的变量；Y是m为行向量，为对偶问题的变量。上式称为对偶关系的对称形式（或叫对偶标准形式），一般情况下，原问题与对偶问题的变换关系可归纳如下表3-16示。第3章

线性规划若原规划问题的约束条件中含有≧约束，可在其两边同乘以-1，统一为≦约束。这里，右边项没有符号限制。根据表3-16，可以写出下列一对线性规划问题：

(3-60)式(3-25)称为对偶关系的非对称形式。【例3-14】写出下列线性规划问题的对偶问题：第3章

线性规划解：用-1乘第2个约束条件的两端，把它变成≦约束，根据3-16表即可写出其对偶问题为【例3-15】写出下列线性规划问题的对偶问题：解：设对应于约束条件的对偶变量一次分别为y1，y2，y3，则由表3-15的对偶关系，可直接给出上述问题的对偶问题，即第3章

线性规划3.7.2

对偶问题的基本性质下面介绍对偶问题的几条重要性质，以揭示原问题的解与对偶问题的解之间的一些重要关系，并为后续讨论对偶问题的单纯形法奠定基础。若X和Y分别是原问题和对偶问题的任一可行解，则必有CX≦Yb，即f≦g。若X*和Y*分别为原问题和对偶问题的可行解，且可行解对应的原问题和对偶问题的目标函数值相等，即CX*≦Y*b，X*和Y*分别为原问题和对偶问题的最优解。若原问题和对偶问题之一的最优解无界，则另一个无可行解；若之一无可行解，则另一个的最优解无界或无可行解。也就是说，原问题和对偶问题之一无最优解，则另一个也无最优解。第3章

线性规划4)若原问题和对偶问题之一有最优解，则另一个也有最优解，且两者的最优目标函数值相等。5)原问题的最优解为XB=B-1b，则对偶问题的最优解为Y=CBB-1。6)根据原问题最优单纯形表中的检验数可以读出对偶问题的最优解。对于第6个性质下面作一说明。设原问题和对偶问题为式(3-60)，(3-61)

在原问题和对偶问题的约束条件中分别引入松弛变量Xs和剩余变量Ys，其中Xs为m维列向量，Ys为n维列向量，有设B为原问题的一个最优基，则原问题可改写为第3章

线性规划相应的对偶问题为这里，取是对应于原问题中基变量XB的剩余变量，是对应于原问题中非基变量XN的剩余变量。原问题的最优解为XB=B-1b，相应的基变量XB的检验数为0，非基变量XN的检验数为CN--CBB-1N，松弛变量XS的检验数为-CBB-1，把对偶问题的最优解Y=CBB-1代入上式得第3章

线性规划由此可见，原问题的最优单纯形表中的检验数对应于对偶问题的最优解的负值。它们的关系见表(3-17)。同样地若原问题和对偶问题为式(3-25)所示的非对称形式，则可得到表(3-18)所示的结果。第3章

线性规划根据表(3-18)可知，原问题最优表中的检验数对应于对偶问题最优解中剩余变量的负值，而对偶决策变量的值Y=CBB-1看起来还不能直接从表(3-18)中读出。当然，如果知道了B-1和CB就可以直接计算出Y来，下面讨论如何从表(3-18)中直接读出对偶变量的值。假定在原间题的约束条件的系数矩阵中有一个m阶单位阵，以此为初始可行基进行迭代得到最优基B，则在最优表中，原来为单位阵的地方就变成了B-1，而在初始表中和B-1相对应的基矩阵B正好位于和最优表中的单位阵相对应的位置，若用CI表示和初始表中单位阵相对应变量的价值系数向量，则在最优表中B-1下的检验数将是CI-CBB-1。因而若由最优表中B-1下的检验数减去相应的价值系数，则正好得到其对偶问题最优解的负值，即-Y=-CBB-1，特别地，当初始表中的单位阵是由引人松弛变量后而形成的，则有CI=0。在这种情况下，最优表(3-17)中B-1下面的检验数就正好等于其对偶问题的最优解的负值。举例说明。第3章

线性规划【例3-16】对偶问题如下：(3-62)对偶问题为

(3-63)第3章

线性规划

在原问题的约束条件中引入松弛变量x1，x2，x3，按单纯形法得原问题的初始表和最优表分别为表3-18和表3-19。第3章

线性规划

由表3-19可知，原问题的最优解为X=(35102500)T，最优目标函数值为maxf=215.

在表3-18申，松弛变量x1，x2，x3的系数矩阵构成单位阵，故在最优表3-19中对应的系数矩阵为最优基的逆阵

且对应的检验数等于它在对偶问题式（3-21）中的最优解的负值。即Y=(y1，y2，y3)T=(013)，相应的目标函数值为ming=maxf=215。

另一方面，Y也可按式Y=CBB-1计算，由于最优表中的单位阵对应于基变量x3，x1，x2，所以它们在初始表3-18中的系数列向量构成最优基B，故，CB=(c3c1c2)T=(054)，则有：第3章

线性规划相应的目标函数值为为了验证按上述方法确定的对偶问题的最优解的正确性，按单纯形法对对偶问题式(3-21)进行迭代，得对偶问题的最优表，见表(3-21)。表中y6，y7为人工变量，g’=-g。第3章

线性规划

由表3-20可知，对偶问题式(3-21)的最优解和最优目标函数值与上述方法求得的完。由此可见从表3-20的检验数中也可以直接读出原问题的最优解，这说明在求解线性规划问题时，可在原问题和对偶间题中，选择容易求解一方进行。然后，应用对偶问题性质可求出对应解。一般来说，线性规划问题求解的工作量在很大程度上取决于约束条件数目的多少，约束越多，基矩阵阶次就高，计算量自然就大。因此，对于约束条件多，变量少的规划问题，其对偶规划的约束条件少，变量多，若对对偶规划求解，就可减少计算工作量。第3章

线性规划3.7.3对偶单纯形法

在用单纯形进行迭代时，在bi列申得到问题的基本可行解，而在检验数行得到的是对偶问题的非可行解。这是因为在达到最优解之前，检验数λ=C--CBB-1A=C-YA≧0，即YA≦C，显然Y=CBB-1不满足对偶问题的约束条件YA≧C。通过逐步迭代，当检验数行得到的对偶问题的解也是可行解时，即C-YA≦C或YA≧C时，CBXB=Yb，由对偶问题的性质2知，此时原问题和对偶问题同时达到了最优解。

根据对偶问题的对称性也可以这样来考虑：若保持对偶问题的解是可行解，即C-YA≦0，而原问题在非可行解的基础上，即B-1b中至少有一个负分量，通过迭代逐步达到基本可行解，这样也得到了原问题和对偶问题的最优解。因为这种方法是从对偶问题的可行性出发来求解原问题的最优解，故它称做对偶单纯形法。这种方法的优点是原问题的初始解不一定是基本可行解，即可以从非可行解开始迭代。下面通过一个例题来介绍对偶单纯形法的计算机步骤。第3章

线性规划【例3-17】用对偶单纯形法求解下列线性规划问题：(3-64)解

第1步：标准化引入剩余变量x3，x4，x5，并令f’=-f，则有(3-65)第3章

线性规划显然，如果要用单纯形法求解，则需引人3个人工变量，再用两阶段法或大M法进行求解，若用下面介绍的对偶单纯形法就简单多了。第2步：找初始基变量，并将目标函数中的基变量用非基变量代替。为了找出基变量，先在约束方程的系数矩阵中形成m阶单位阵，为此用-1乘式(3-65)约束方程两端，得(3-66)

显然，x3，x4，x5为初始基变量，但对应的初始解不是可行解。目标函数中不含基变量。故不需代换。第3章

线性规划第3步：作初始单纯形表。由式(3-28)得初始单纯形表。由表3-21可知，初始解是非可行的，但检验数全部非正，在对偶单纯形法中，把这种对应检验数全部非正的基本解称为正则解。对偶单纯形法是以正则解出发开始迭代，在迭代过程中最终保持bi列所有元素全部非负，即得到原问题的最优解。第4步：确定主元对偶单纯形算法是以原问题的右端列bi作为检验数。若min{bi|bi<0}=bl则bl所在的行为主元行，bl所对应的基变量为换出变量。此例中x4为换出变量。当主元行确定后，就可按下