第一章-线性规划与单纯形法

1第一章线性规划与单纯形法第一节线性规划问题及其数学模型第二节线性规划问题的几何意义第三节单纯形法第四节单纯形法的计算步骤第五节单纯形法的进一步讨论第六节应用举例2第一节线性规划问题及其数学模型一、问题的提出二、图解法三、线性规划问题的标准形式四、线性规划问题的解的概念3线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。4一、问题的提出例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表所示。资源产品ⅠⅡ拥有量设备128台时原材料A4016kg原材料B0412kg每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?5称它们为决策变量。产品的数量，分别表示计划生产设III,,21xx124;164;82,,212121xxxxxx这是约束条件。即有量的限制的数量多少，受资源拥生产021x,x,即生产的产品不能是负值使利润最大目标：如何安排生产，利润z=2x1+3x260124164823221212121x,xxxxx:xxzmax约束条件目标函数本问题的数学模型为:这就是一个最简单的线性规划模型。7例2建立LP数学模型某家电厂家利用现有资源生产两种产品，有关数据如下表：设备A设备B调试工序利润（元）0612521115时24时5时产品Ⅰ产品ⅡD如何安排生产，使获利最多？8如何安排生产，使获利最多？厂家设Ⅰ产量–––––Ⅱ产量–––––1x2x0,524261552max212121221xxxxxxxs.t.xxz9每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。nx,x,x21上述两个问题具有的共同特征：10)3.1(0,,,),()2.1(),(),()1.1(max(min)21221122222121112121112211nmnmmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz线性规划模型的一般形式目标函数满足约束条件价值系数技术（工艺）系数限额系数（资源）非负约束条件11二、图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。0,1241648232max21212121xxxxxxxxz124x1=164x2=12x1+2x2=8x1x2484300,1241648232max21212121xxxxxxxxz134x1=164x2=12x1+2x2=8x1x248430Q1可行域0,1241648232max21212121xxxxxxxxz1433212zxx目标值在（4，2）点，达到最大值144x1=164x2=12x1+2x2=8x1x248430Q2(4,2)Q1可行域0,1241648232max21212121xxxxxxxxzx1+2x2=84x1=1615图解法求解步骤由全部约束条件作图求出可行域；作目标函数等值线，确定使目标函数最优的移动方向；平移目标函数的等值线，找出最优点，算出最优值。16练习：用图解法求解目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x20179—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+x25目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2245x215图解法12—11—10—189—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+x25目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2245x215图解法12—11—10—可行域199—8—7—6—5—4—3—2—1—0|||||||||123456789x1x2x1+x25目标函数MaxZ=2x1+x2约束条件5x2156x1+2x224x1+x25x1、x206x1+2x2245x21512—11—10—x2=-2x16x1+2x2=24x1+x2=5最优解(3.5,1.5)目标值在（3.5，1.5）点，达到最大值8.520（1）无穷多最优解(多重最优解)（2）无界解（3）无可行解•上例中求解得到问题的最优解是惟一的•通过图解法，可观察到一般线性规划的解还可能出现一下几种情况：21无穷多最优解（多重最优解）4x1=164x2=12x1+2x2=8x1x248430可行域0,12416482:212121xxxxxx约束条件目标函数Q2Q3MaxZ=2x1+4x222表示一簇平行线33212zxx4x1=16x1x240无界解（a）0,16432max21121xxxxxz可行域230,242max2121121xxxxxxxxz无界解（b）24当存在相互矛盾的约束条件时，线性规划问题的可行域为空集，即无可行解，也不存在最优解。85.121xx无可行解4x1=164x2=12x1+2x2=8x1x230原可行域8121.58xx12121212max2328416:412,0zxxxxxxxx目标函数约束条件增加一个新的约束条件25可行域和解有以下几种情况(a)可行域有界有唯一最优解(b)可行域有界有无穷多最优解26(c)可行域无界有唯一最优解(d)可行域无界有无穷多最优解(e)可行域无界无最优解(无界解)27(f)可行域为空集无可行解28LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界,无界解）无可行解（无解，可行域为空集）若LP问题有最优解，则要么最优解唯一，要么有无穷多最优解29图解法的几点结论:（由图解法得到的启示）可行域是有界或无界的凸多边形，凸多边形的顶点个数是有限的。若线性规划问题存在最优解，它一定可以在可行域的顶点得到。若两个顶点同时得到最优解，则其连线上的所有点都是最优解。解题思路：找出凸集的顶点，计算其目标函数值，比较即得。30三、线性规划问题的标准形式111221111221121122222112212:maxzca,,,0nnnnnnmmmnnmnMxcxcxxaxaxbaxaxaxbaxaxaxbxxx目标函数：约束条件：在标准形式中规定约束条件的右端项bi031njxmibxxMjnjijnjj,,2,1,0,,2,1,aczmax:1ij1j'1约束条件：目标函数：32n,,j;bbbb;aaaP;xxxX;c,,c,cCn,,,j,xbxPCXzmax:Mmmjjjjnnjnjjj''212102121212111约束条件：目标函数：用向量形式表示的标准形式线性规划线性规划问题的几种表示形式33用矩阵形式表示的标准形式线性规划''111112112121m:max0,,;,,,;,,,0b0b0bnnmmnTnnMzCXAXbXaaAPPPaaCcccXxxx目标函数：约束条件：系数矩阵：价值向量：决策变量向量：零向量：；资源向量：34'kkkxxx(1)若要求目标函数实现最小化，即minz=CX，则只需将目标函数最小化变换求目标函数最大化，即令z′=−z，于是得到maxz′=−CX。(2)约束条件为不等式。分两种情况讨论：若约束条件为“≤”型不等式，则可在不等式左端加入非负松弛变量，把原“≤”型不等式变为等式约束；若约束条件为“≥”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。(3)若存在取值无约束的变量xk,可令0,'kkxx如何将一般线性规划转化为标准形式的线性规划35例3将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为0,1241648232max21212121xxxxxxxxz0,,,,1241648243215241321xxxxxxxxxxxx5432100032maxxxxxxz36例4将下述线性规划问题化为标准形式线性规划为无约束3213213213213210533732x;x,xxxxxxxxxxxxxzmin(1)用x4−x5替换x3，其中x4，x5≥0；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z′=−z，将求minz改为求maxz′37例4的标准型0,,,,,5)(232)(7)(00)(32max76542154217542165421765421'xxxxxxxxxxxxxxxxxxxxxxxxxxz38补充：•当某个变量xj≤0时,令x′j=－xj.•当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束将其化为两个不等式再加入松驰变量化为等式。974321xxx974974321321xxxxxx39四、线性规划问题解的概念1.可行解2.基3.基可行解4.可行基40njxmibxxjnjijnjj,,2,1,0,,2,1,aczmax1ij1j约束条件：目标函数：（1-4）（1-5）（1-6）一般线性规划问题的标准型：41定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解；其中使目标函数（1-4）达到最大值的可行解称为最优解。)61(,,2,1,0)51(,2,1,)41(max11njxmibxaxczjnjijijnjjj1、可行解422、基nmnmnPPPaaaaA,,211111A是约束方程组的m×n维系数矩阵，其秩为m43–B是矩阵A中m×m阶非奇异子矩阵（|B|0），则称B是线性规划问题的一个基。令B==(P1,P2,…,Pm)–Pj(j=1,2,…,m)为基向量。–与基向量Pj对应的变量xj称为基变量–记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xn)T。mmm12m1m1211aaaaaa44–令非基变量xm+1=x