第1章 线性规划模型

第1章线性规划Chapter1LinearProgramming本章内容提要线性规划是运筹学的重要内容。本章介绍线性规划数学模型、线性规划的基本概念以及求解线性规划数学模型的专门软件——Lingo。学习本章要求掌握以下内容：线性规划模型的结构。包括：决策变量，目标函数，约束条件。线性规划的标准形式，非标准形式转化为标准形式线性规划的基本概念。包括：约束直线，可行域，可行解，凸集，极点，目标函数等值线，最优解线性规划的软件求解。包括：lingo软件简介，lingo软件求解规划问题§1.1线性规划1.1.1线性规划线性规划（LinearProgramming，LP）是运筹学中最重要的一种系统优化方法。它的理论和算法已十分成熟，应用领域十分广泛，通常研究资源的最优利用、设备最佳运行等问题。例如，当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标；企业在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大）。还包括生产计划，物资调运，资源优化配置，物料配方，任务分配，经济规划等问题。随着计算机硬件和软件技术的发展，目前用微型计算机就可以求解大规模的规划问题。Lingo软件就是其中的代表软件之一。在本章中，我们将介绍线性规划的基本概念，线性规划在经济分析中的应用。§1.2线性规划问题线性规划问题由目标函数、约束条件以及变量的非负约束三部分组成。根据实际问题的条件和要求，可以建立线性规划问题数学模型。下面列举五种最常见的线性规划问题的类型。1.2.1生产计划问题例1.1某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：表1-1每件产品占用的机时数（小时/件）产品甲产品乙产品丙产品丁设备能力（小时）设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利润（元/件）5.247.308.344.18用线性规划制订使总利润最大的生产计划。设变量xi为第i种产品的生产件数（i=1,2,3,4）,目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：maxz=5.24x1+7.30x2+8.34x3+4.18x4目标函数s.t.1.5x1+1.0x2+2.4x3+1.0x<200041.0x1+5.0x2+1.0x3+3.5x<80004约束条件1.5x1+3.0x2+3.5x3+1.0x<50004xi,x2,x3,x N04变量非负约束这是一个典型的利润最大化的生产计划问题。其中max表示极大化（maximize），s.t.是subjectto的缩写。求解这个线性规划，可以得到最优解为：x1=294.12 x2=1500 x3=0 x4=58.82 （件）最大利润为z=12737.06（元）请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产。说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性。尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果。

1.2.2配料问题例1・2某工厂要用四种合金T1,T2,T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素格（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（％）如下表所示:表1-2TiT2T3T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.30单价（元/公斤）115978276设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T「T2,T3和T4各多少公斤，使成本最小。设选用原料T］，T2，T3和T4分别为X］，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下：minz= 115x1+97x2+82x3+76x4s.t. 0.0321x1+0.0453x2+0.0219xq3+0.0176x,4N3.200.0204x1+0.0112x2+0.0357x3+0.0433x4N2.100.0582x1+0.0306x2+0.0427x3+0.0273x4N4.30x1+x2+x3+x4=100xi,x2,x3,x4N0这是一个典型的成本最小化的问题。其中min表示极小化（minimize）0这个线性规划问题的最优解是x1=26.58 x2=31.57 x3=41.84 x4=0 （公斤）最低成本为z=9550.889（元）1.2.3背包问题例1.3一只背包最大装载重量为50公斤。现有三种物品，每种物品数量无限。每种物品每件的重量、价值如下表所示：

表1-3物品1物品2物品3重量（公斤/件）104120价值（元/件）177235要在背包中装入这三种物品各多少件，使背包中的物品价值最高。设装入物品1，物品2和物品3各为xi，x2，x3件，由于物品的件数必须是整数，因此背包问题的线性规划模型是一个整数规划问题：maxz=17x1+72xo2+35x3s.t.10x1+41x2+20x3W50x1,x2,x3N0,x1，x2,x3是整数这个问题的最优解是：x1=1件,x2=0件,x3=2件，最高价值为：z=87元1.2.4运输问题例1.4设某种物资从两个供应地A「A2运往三个需求地B「B2,B3。各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示。表1-4运价（元/吨）B1B2B3供应量（吨）A123535A247825需求量（吨）103020这个问题也可以用图解表示如下，其中节点A.A2表示发地，节点B］、B2、35吨25吨1035吨25吨10吨30吨20吨B3表示收地，从每一发地到每一收地都有相应的运输路线，共有6条不同的运输路线。设％.为从供应地A】运往需求地Bj的物资数量（i=l,2；j=l,2,3）,z为总运费，则总运费最小的线性规划模型为：minz=2x11+3X12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35⑴x21+x22+x23=25(2)x11+x21=10⑶x12+x22=30⑷x13+x23=20⑸x.20ij以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束。这个问题的最优解为：X]]=0,x12=30,x13=5,x21=10,x22=0,x23=15（吨）；最小运费为：z=275元。1.2.5指派问题例1.5有n项任务由n个人去完成，每项任务交给一个人，每个人都有一项任务。由第i个人去做第j项任务的成本（或效益）为％。求使总成本最小（或效益最大）的分配方案。次 [0第i个人不从事第j项任务设： x..=<ij[1第i个人被指派完成第j项任务得到以下的线性规划模型：min（max）z=8玲.i=1J=1s.t Ex=1J=1,2,...,niji=1Ex=1i=1,2,.,niJj=1X=0,1例如，有张、王、李、赵4位教师被分配教语文、数学、物理、化学4门课程，每位教师教一门课程，每门课程由一位老师教。根据这四位教师以往教课的情况，他们分别教这四门课程的平均成绩如下表：

表1-5语文数学物理化学张92688576王82917763李83907465赵93618375四位教师每人只能教一门课，每一门课只能由一个教师来教。要确定哪一位教师上哪一门课，使四门课的平均成绩之和为最高。设x..（i=1,2,3,4；j=1,2,3,4）为第i个教师是否教第j门课，乂而只能取值0或1，其意义如下：x=[0第i个教师不教第.门课Xij=〔1第i个教师教第.门课变量X.J与教师i以及课程j的关系如下：表1-6X语文数学物理化学张x11x12x13x14王x21x22x23x24李x31x32x33x34赵x41x42x43x44这个指派问题的线性规划模型为:maxz=92x+68x+85xo+76x+82x+91x+77xo+63xOJ11 12 13 14 21 22 23 24+83x+90xmaxz=92x+68x+85xo+76x+82x+91x+77xo+63xOJ11 12 13 14 21 22 23 24+83x+90xo+74xo+65x+93x,+61xo+83xo+75x^<31 32 33 34 41 42 43 44S.t. xn+x12+x13+x14=1x21+x22+x23+x24Tx31+x32+x33+x34=1x41+x42+x43+x44=1x11+x21+x31+x41=1x12+x22+x32+x42=1（1）（2）（3）（4）（5）（6）X13+X23+X33+X43=1X14+X24+X34+X44=1(7)(8)(7)(8)这个问题的最优解为X14=1,X23=1,X32=1,X41=1,maxz=336；即张老师教化学，王老师教物理，李老师教数学，赵老师教语文，如果这样分配教学任务，四门课的平均总分可以达到336分。在线性规划问题中，如果所有的变量都只能取值0或1。这样的线性规划问题称为(纯)0—1整数规划问题。如果一个线性规划问题中，有的变量是连续变量，而另一些变量是0—1变量，这样的问题称为混合0—1规划问题。§1.3线性规划问题的数学模型由以上5个例子，我们可以归纳出线性规划问题的数学模型和一般形式：上述5个例子的3个共同点每个问题都有一组变量 称为决策变量都有一个关于决策变量的函数每个问题都有一组决策变量需满足的约束条件线性规划问题定义：将约束条件及目标函数都是决策变量的线性函数的规划问题称为线性规划问题。建立线性规划问题的数学模型步骤确定问题的决策变量确定问题的目标，并表示为决策变量的线性函数找出问题的所有约束条件，并表示为决策变量的线性方程或不等式线性规划的数学模型假定线性规划问题中含n个变量，分别用xj(j=1,...,n)表示，在目标函数中，xj的系数为cj(通常称为价值系数)。xj的取值受m项资源的限制，用bi(i=1,...,m)表示第i种资源的拥有量，用aij表示变量xj的取值为一个单位时所消耗或含有的第i种资源的数量(通常称为技术系数或工艺系数)。则上述线性规划问题的数学模型可以表示为

max(min)z=cx+cx+・・・+cx+・ +cx1122jj nnst ax+ax+・+ax +—+ax <(=,>)b1111221jj 1nn 1ax+ax+・+ax +—+ax <(=,>)b2112222jj 2nn 2・・.・・・ ・ ・ ・ax+ax+・+ax +—+ax<(=,>)bm11m22mjj mnn mxx・x… x >012jn其中max(min)z=cx+cx+・11 22••+cx+ +cxjj nn称为目标函数，ax +ax+—+ax+—+ax <(=>)b111 1221jj1nn 1ax +ax+—+ax+・+ax <(=>)b211 222•… •…2jj•・・••-2nn 2・ ・ ・ax +ax+—+ax+—+ax<(=>)bm11 m22mjjnmn m称为约束条件，x1，x2,…，xj，…，xn>0称为变量的非负约束。在线性规划问题中，目标函数是变量的线性函数，约束条件是变量的线性不等式。例如以下的问题就不是线性规划问题而是非线性规划问题了：maxz=5x1x2+2x3s.t.2x12+3x2-—<15x3Ix1-x2l+4x3>14x1,x2，x3>0记向量和矩阵C=c1C2，X=「x[1x2，b=bb2，A=a11a21a・12a・22a1na2n:::•・・・・•••・cxbaa・a1-n」n1-m」m1m2mn则线性规划问题可由向量和矩阵表示max(min)z=CTXs.t. AXW(=,3)bX30§1.3线性规划问题的标准形式由于目标函数和约束条件内容和形式上的差别，线性规划问题有多种表达式，为了便于讨论和制定统一的算法，规定标准形式如下：目标函数极大化；约束条件为等式且右端项30；决策变量30。为了今后讨论的方便，我们称以下线性规划的形式为标准形式：minz=CTXs.t.AX=bX30对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。*1.3.1极大化目标函数的问题设目标函数为maxz=cx+cxH Fcx11 22 nn令z’=—z，则以上极大化问题和极小化问题有相同的最优解，即minz=-cx一cx cx11 22 nn但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即max z=—minz’*1.3.2约束条件不是等式的问题设约束条件为a.ixi+a.2x2+ +a.x<b. (.=1,2,...,m)可以引进一个新的变量xn+.，使它等于约束右边与左边之差x=b一(ax+ax+ +ax)n+. . .11 .22 .nn显然xn+i也具有非负约束，即xn+.30，这时新的约束条件成为a.ixi+a.2x2+ +a.x+x.=b.当约束条件为a，ixi+a,2x2H fa.x>b,时，类似地令x.=(a，ixi+a.2x2+ +a.x)一b.则同样有xn+.30，新的约束条件成为

a.]X]+a.2X2+ +aix-x.=bi为了使约束由不等式成为等式而引进的变量 xn+i称为“松弛变量（SlackVariables）"。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。例1.6将以下线性规划问题转化为标准形式maxz=3x1-2X2+X3s.t. X]+2X2-x3W5(1)4x1+3x338(2)xi+X2+x3=6(3)xi，x2，X330将目标函数转换成极小化，并分别对约束（1）、（2）引进松弛变量X4，X5，下标准形式的线性规划问题minz’=-3x1+2X2-x3s.t. X1+2X2-x3+x4=54x1+3X3 -X5=8x1+X2+x3=6x1，x2，X3, X4，X530得到以*1.3.3变量无符号限制的问题在标准形式中，每一个变量都有非负约束。当一个变量Xj没有非负约束时，可以令其中注河，x”30即用两个非负变量之差来表示一个无符号限制的变量，当Xj的符号取决于x《和X”的大小。例1.7将以下线性规划问题转化为标准形式maxz=2x1-3x2+x3s.t. X1-x2+2x3W32x1+3x2-x335X+x+x=4123x1,x3^0,x2无符号限制令z’=-z,引进松弛变量x4,X530,并令

X2=X2-X2其中x2'30,x；30得到以下等价的标准形式minz’=-2x1+3x；-3X2”-X3s.t. X]-X2'+X；'+2X3+X4=32x1+3x；-3X2”-X3-X5=5x1+X2'-X2''+X3=4X1，x；，X2''，X3,X4，X5对*1.3.4变量小于等于零的问题在一些实际问题中，变量不允许为正数，这样的问题也需要转化为标准问题。例如：minz=3xi-5X2+X3s.t.2xi+4X2+X3W]5-xi-3X2+2x336X]30X2<0x330令X2=-X'2，x'230,原问题成为:minz=3xi+5x'2+X3s.t.2xi-4x'2+X3W]5-xi+3x'2+2x336x]30x'230x330然后引进松弛变量X4,X5,成为标准问题：minz=3x +5x'1 2+X3s.t. 2x-4x'1 2+X3+X4 T5-X1 +3x'2+2x3 -X5 =6xi x'2X3 X4 X5 30这样，我们就能够将任何非标准形式的线性规划问题转化为等价的标准形式问题。*§1.4线性规划问题的几何解释对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。例1・8maxz=x1+3x2TOC\o"1-5"\h\z\o"CurrentDocument"s.t.x1 +x2W6 (1)\o"CurrentDocument"-x.+2x2W8 (2)x], x230 「x1 ...其中满足约束(1)的点X=1位于坐标平面上直线x+x=6靠近原点的一%」 1'侧。同样，满足约束(2)的点位于坐标平面上直线-x.+2x2=8的靠近原点的一侧。而变量x.,x2的非负约束表明满足约束条件的点同时应位于第一象限内。这样，以上几个区域的交集就是满足以上所有约束条件的点的全体。我们称满足线性规划问题所有约束条件(包括变量非负约束)的向量X=(X],x2，…，X/T为线性规划的可行解(FeasibleSolution)，称可行解的集合为可行域(FeasibleRegion)。例1.8的线性规划问题的可行域如图1.2中阴影部分所示。为了在图上表示目标函数，令z=z0为某一确定的目标函数值，取一组不同的z0值，在图上得到一组相应的平行线，称为目标函数等值线。在同一条等值线上的点，

相应的可行解的目标函数值相等。在图1.2中，给出了z=0,z=3,z=6,…，z=15.3等一组目标函数等值线，对于目标函数极大化问题，这一组目标函数等值线沿目标函数增大而平行移动的方向（即目标函数梯度方向）就是目标函数的系数向量C=（C］,c2，…，…,cn）T；对于极小化问题，目标函数则沿-C方向平行移动。在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线X1+X2=6-X1+2x2=8的交点求得143'最优解的目标函数值为z=Xz=X]+3x2=4+3X14=3346为了将以上概念推广到一般情况，我们给出以下定义:定义1・1在n维空间中，满足条件a.,x+aXc+“・+a.x=b.111 122 inni的点集X=（X］，x2，...，xn）T称为一个超平面。定义1.2满足条件a.,x+ax+.+ax《（或＞）b.111 122inn i的点集X=（X］，x2，...，xn）T称为n维空间中的一个半空间。定义1.3有限个半空间的交集，即同时满足以下条件的非空点集a,x+ax+.+aX《（或》）b,TOC\o"1-5"\h\z111122 1nn 1a孵x+a”x+“・+a。x《（或＞）b0211222 2nn 2a,x+ax+.+ax《（或＞）bm11m22 mnn m称为n维空间中的一个多面体。运用矩阵记号，n维空间中的多面体也可记为AXW（或3）b

每一个变量非负约束xi^0(i=1,2,…，n)也都是半空间，其相应的超平面就是相应的坐标平面x=0。i在图1.2中，我们看到，线性规划问题的可行域是一个凸多边形。容易想象，在一般的n维空间中，n个变量，m个约束的线性规划问题的可行域也应具备这一性质。为此我们引进如下的定义。定义1.4设S是n维空间中的一个点集。若对任意n维向量XU，X2GS，且X/X2,以及任意实数入(0<!<1)，有X=XX1+(1-X)X2gS则称S为n维空间中的一个凸集(ConvexSet)。点X称为点X]和X2的凸组合。以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点(包括这两个端点)，都位于凸集S之中。(a)凸集(d)非凸集(b)凸集(c)凸集(f)非凸集(e)非凸集(a)凸集(d)非凸集(b)凸集(c)凸集(f)非凸集(e)非凸集图1.3从图1.2还可以看出，线性规划如果有最优解，其最优解必定位于可行域边界的某些点上。在平面多边形中，这些点就是多边形的顶点。在n维空间中，我们称这样的点为极点(ExtremePoint)0在凸集中，不能表为不同点的凸组合的点称为凸集的极点。定义1.5设S为一凸集，且XgS，X1GS，X2gS。对于0<入<1，若X=XX1+(1-X)X2则必定有X=X]=X2，则称X为s的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：1、 若线性规划的可行域非空，则可行域必定为一凸集。2、 若线性规划有最优解，则最优解至少位于一个极点上。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。最后，来讨论线性规划的可行域和最优解的几种可能的情况。1、 可行域为封闭的有界区域有唯一的最优解；有一个以上的最优解；2、 可行域为非封闭的无界区域有唯一的最优解；有一个以上的最优解；目标函数无界(即虽有可行解，但在可行域中，目标函数可以无限增大或无限减小)，因而没有最优解。3、 可行域为空集，因而没有可行解。

§1.5线性规划的基、基础可行解由于图解法无法解决三个变量以上的线性规划问题，我们必须用代数方法来求得可行域的极点。先从以下的例子来看。例1・9maxz=x1+2x2s.t.x1+x2W3(1)x2W1(2)x1,x2对这个问题的图解如图1.5所示。引进松弛变量x3,x4>0，问题变成为标准形式maxz=x1+2x2s.t.x1+x2+x3=3(1)x2+x4=1(2)x1x2x3 x4>0由上图可以看出，直线AD对应于约束条件(1)，位于AD左下侧半平面上的点满足约束条件x1+x2<3，即该半平面上的点，满足x3>0。直线AD右上侧半平面上的点满足约束条件x1+x2>3，即该半平面上的点，满足x3<0，而直线AD上的点，相应的x3=0。同样，直线BC上的点满足x4=0，BC以下半平面中的点，满足x4>0。BC以上半平面中的点，满足x4<0。另外，OA上的点满足x2=0，OD上的点满足x1=0o由此可见，上图中约束直线的交点O,A,B,C和D可以由以下方法得到：在标准化的等式约束中，令其中某两个变量为零，得到其他变量的唯一解，这个解就是相应交点的坐标，如果某一交点的坐标（x1，x2,x3,x4）全为非负，则该交点就对应于线性规划可行域的一个极点（如点A，B，C和O）；如果某一交点的坐标中至少有一个分量为负值（如点D），则该交点不是可行域的极点。由图1.5可知，O点对应于x1=0，x2=0，在等式约束中令乂］=0，x2=0，得到Ux3=3,x4=1。即O点对应于极点X=（xi，x2,x3,x4）T=（0，0，3，1）T。由于所有分量都为非负，因此O点是一可行域的极点。同样，A点对应于x=0,x=0,x=3,x=1；B点对应于x=0,x=0,x=2,x=1；乙 J _L J _L 乙C点对应于x1=0,x4=0,x2=1,x3=20以上都是极点。而D点对应于x1=0,x3=0,x2=3,x4=-2,乂4的值小于0,因而不是极点。同时，我们也注意到，如在等式约束中令x2=0,x4=0,由于线性方程组的系数行列式等于0,因而土、x3无解。这在图1.5中也容易得到解释，这是由于对应的直线x2=0和x4=0平行，没有交点的缘故。对于一般的问题，获得线性规划可行域极点的方法可描述如下：设线性规划的约束条件为AX=bXN0其中A为mXn的矩阵，n>m,^A=m,b为mX1向量。在约束等式中，令n维空间的解向量X=（x1，x2,„,xn）T中n-m个变量为零，如果剩下的m个变量在线性方程组中有唯一解，则这n个变量的值组成的向量X就对应于n维空间中若干个超平面的一个交点。当这n个变量的值都是非负时，这个交点就是线性规划可行域的一个极点。根据以上分析，自然可以得到以下定义：定义1・6线性规划的基（Basis）对于线性规划的约束条件AX=bX>0^B是A矩阵中的一个非奇异的mxm子矩阵，则称B为线性规划的一个基。设B是线性规划的一个基，则A可以表示为A=[B,N]X也可相应地分成

其中XB^mXl向量，称为基变量，其分量与基B的列向量对应；XN^(n-m)X1向量，称为非基变量，其分量与非基矩阵N的列对应。这时约束等式AX=b可表示为M,n]：b=bXN或BXB+NXN=b若XN取确定的值，则XB有唯一的值与之对应X=B-Ib-B-1NX”BN特别，取XN=0，这时有XB=B-ib。对于这样一个特别的解，我们有以下定义：定义1・7线性规划问题的基础解(BasicSolution,BS)、基础可行解(BasicFeasibleSolution,BFS)和可行基(FeasibleBasis,FB)线性规划的解「X[「B-1b-B=XLN」0称为线性规划与基B对应的基础解。若其中基变量的值X=B-1b>0，则称以上的基础解为一基础可行解，相应的基BB称为可行基。根据以上的分析，我们不加证明地给出以下定理：定理1.1线性规划的基础可行解就是可行域的极点。这个定理是线性规划的基本定理，它的重要性在于把可行域的极点这一几何概念与基础可行解这一代数概念联系起来，因而可以通过求基础可行解的线性代数的方法来得到可行域的一切极点，从而有可能进一步获得最优极点。例1.10求例1.9中线性规划可行域的所有极点。这个线性规划问题的标准形式的约束条件为：X1+X2+X3=3X2+X4=1xX1+X2+X3=3X2+X4=1x1，X2,X3,X4A=k,a2,a3,a4L11A矩阵包含以下六个2A矩阵包含以下六个2X2的子矩阵：B1=[a1，%] 与=虬，财B4=[a2，财 鸟=虬，％]B3=[a1，a4]B6=[a3，a4]其中B2=^其中B2=^a]=

a3-■=其行列式detB2=0,因而82不是线性规划的一个基。其余均为非奇异方阵，因此该问题共有5个基。对于基B1=[a对于基B1=[a1，x3xL4」a2]，2「0=0令非基变量等于0得到基变量的值为非负，因而B为非负，因而B1是可行基。「x11「2「XB——=x2—=1XN」x一30xL4」0-x一「1-1320X=1=BTb==>Bx2l_01」110为对应于基B1的一个基础解。由于X的各分量均为非负，故X是一个基础可行解，因而对应于一个极点。事实上，这个极点就是图1.5中的极点B。用同样的方法，可以验证b3、b4、b6都是可行基，因而相应的基础解都是可行解，各对应于一个极点。但B5不是可行基，这是因为b5对应的基础解X=（X]，x2，x3，x4）T=（0，3，0，-2）T有小于零的分量，因而对应的点D不是极点。定理1.1指出了一种求解线性规划问题的可能途径，这就是先确定线性规划问题的基，如果是可行基，则计算相应的基础可行解以及相应解的目标函数值。由于基的个数是有限的（最多Cm个），因此必定可以从有限个基础可行解中找到使目n标函数为最优（极大或极小）的解。不幸的是线性规划的基的个数是随着问题规模的增大而很快增加，以至实际上成为不可穷尽的。举例来说，一个有50个变量，20个约束等式的线性规划问题。其最多可能有C20=_50_=4.7x10135020!30!个基。

为了说明计算所有基础可行解的计算量有多大，我们假定计算一个基础可行解(即求解一个20X20的线性方程组！)只需要一秒钟，那么计算以上所有的基础可行解需要4.7x4.7x10133600x24x365=1.5x106（年）即约150万年。很显然，借助于定理1.1来求解线性规划问题，那怕是规模不大的问题，也是不可能的。而线性规划的一种算法一一单纯形法，可以极为有效地解决大规模的线性规划问题。§1.6lingo软件简介及使用LINGO是LinearInteractiveandGeneralOptimizer的缩写，即—交互式的线性和通用优化求解器”，由美国LINDO系统公司(LindoSystemInc.)推出的，可以用于求解非线性规划，也可以用于一些线性和非线性方程组的求解等，功能十分强大，是求解优化模型的最佳选择。其特色在于内置建模语言，提供十几个内部函数，可以允许决策变量是整数(即整数规划，包括0-1整数规划)，方便灵活，而且执行速度非常快。能方便与EXCEL，数据库等其他软件交换数据。一般地，使用LINGO求解运筹学问题可以分为以下两个步骤来完成：根据实际问题，建立数学模型，即使用数学建模的方法建立优化模型；根据优化模型，利用LINGO来求解模型。主要是根据LINGO软件，把数学模型转译成计算机语言，借助于计算机来求解。§1.6.1LINGO快速入门LINGO求解线性规划的过程采用单纯形法，一般是首先寻求一个可行解，在有可行解情况下再寻求最优解。用LINGO求解一个LP问题会得到如下的几种结果：不可行(Nofeasible)或可行(Feasible)；可行时又可分为：有最优解(OptimalSolution)和解无界(UnboundedSolution)两种情况。当你在windows下开始运行LINGO系统时，会得到类似下面的一个窗口：外层是主框架窗口，包含了所有菜单命令和工具条，其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGOModel-LINGO1的窗口是LINGO的默认模型窗口，建立的模型都都要在该窗口内编码实现。让我们来解如下的LP问题：例].10max七=2尤+3》[4x+3y<10<3x+5y<12、x,y>0由于LINGO中已假设所有的变量是非负的，所以非负约束不必再输入到计算机中，LINGO也不区分变量中的大小写字符（任何小写字符将被转换为大写字符）；约束条件中的”<=”及”>=”可用”<”及”>”代替。上面的问题编写程序如下：Model:MAX=2*X+3*Y;4*X+3*Y<10;3*X+5*Y<12;ENDLINGO中一般称上面这种问题（PROBLEM）的实例（INSTANCE）的输入为模型（MODEL），简称为“问题模型”。要LINGO编程中输入模型时应注意如下事项：（1） 以“model:”开头，以“end”结束。（2） 目标函数求最大时用“max=”，求最小时用“min=”。（3） 目标函数及约束条件各语句之间要用分号“；”，如果两个语句之间没有分号，LINGO把此两个语句看成是一个语句。（重要！）

运算符号“+,一,*,/,"”按要求书写，不可省略。(重要！)注释语句在前面注有“!”符号，例如：！Thisisacomment。LINGO将目标函数所在行作为第一行，从第二行起为约束条件，行号自动产生。按工具栏上的Solve按钮◎就可求得该问题的解。计算结果表明：“Globaloptimalsolutionfound."表示全局最优解已经找至U。“Objectivevalue:7.454545"表示最优目标值为7.4545450。“Infeasibilities:0.000000”表示初始值为0。“Totalsolveriterations:2”表示用单纯形算法，迭代次数为2次。“Variable”给出最优解中各变量的值(Value)：X=1.272727，Y=1.636364。“ReducedCost”给出最优单纯形表中第1行中变量的系数(max型问题)。其中基变量的reducedcost值应为0，对于非基变量，相应的reducedcost值表示当该非基变量增加一个单位时(其他变量保持不变)目标函数减少量。本例中此值均为0。“SlackorSurplus”给出松弛变量的值：第2，3行松弛变量均为0,说明对最优解来讲，两个约束(第2,3行)均取等号。这样的约束也称为紧约束，即表示约束的右端资源要全部用完。“DualPrice”给出对偶价格的值：第2,3行对偶价格分别为0.090909,0.545455。例1.11DAKOTA家具公司制造书桌(DESK),桌子(TABLE)和椅子(CHAIR),所有的资源有三种：木料，木工和漆工，生产数据如下表所示：每个DESK每个TABLE每个CHAIR现有资源总数

木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木2单1.5单0.5单8单位工位位位利60单30单20单润位位位若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大?编写程序如下：Model:MAX=60*DESKS+30*TABLES+20*CHAIRS;8*DESKS+6*TABLES+CHAIRS<48;4*DESKS+2*TABLES+1.5*CHAIRS<20;2*DESKS+1.5*TABLES+0.5*CHAIRS<8;TABLES<5;END计算结果为:Globaloptimalsolutionfound.Objectivevalue:280.0000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000RowSlackorSurplusDualPrice1280.00001.000000224.000000.00000030.00000010.0000040.00000010.0000055.0000000.000000即生产书桌（DESK）2件，桌子（TABLE）0件和椅子（CHAIR）