运筹学(第四版)清华大学出版社《运筹学》教材编写组-第2章

清华大学出版社1二、线性规划与目标规划第2章线性规划与单纯形法第3章对偶理论与灵敏度分析第4章运输问题第5章线性目标规划清华大学出版社2第2章线性规划与单纯形法第1节线性规划问题及其数学模型第2节线性规划问题的几何意义第3节单纯形法第4节单纯形法的计算步骤第5节单纯形法的进一步讨论第6节应用举例清华大学出版社3第1节线性规划问题及其数学模型2.1.1问题的提出2.1.2图解法2.1.3线性规划问题的标准形式2.1.4线性规划问题的解的概念清华大学出版社4第1节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介绍单纯形法。清华大学出版社52.1.1问题的提出2.1.1问题的提出例1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。资源产品ⅠⅡ拥有量设备128台时原材料A4016kg原材料B0412kg每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排计划使该工厂获利最多?清华大学出版社62.1.1问题的提出称它们为决策变量。产品的数量，分别表示计划生产设III,,21xx12416482212121x;x;xx,x,x这是约束条件。即有量的限制的数量多少，受资源拥生产021x,x,即生产的产品不能是负值这是目标。最大如何安排生产，使利润,用数学关系式描述这个问题清华大学出版社72.1.1问题的提出0124164823221212121x,xxxxx:xxzmax约束条件目标函数得到本问题的数学模型为:这就是一个最简单的线性规划模型。清华大学出版社82.1.1问题的提出例2靠近某河流有两个化工厂(见图1-1)，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。图1-1化工厂1每天排放含有某种有害物质的工业污水2万立方米，化工厂2每天排放的工业污水为1.4万立方米。从化工厂1排出的污水流到化工厂2前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%。因此两个工厂都需处理一部分工业污水。化工厂1处理污水的成本是1000元/万立方米,化工厂2处理污水的成本是800元/万立方米。问:在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。清华大学出版社92.1.1问题的提出设：化工厂1每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为x2万立方米100027004128021000250022211)]x.()x(.[)x(工厂后的水质要求：经第工厂前的水质要求：经第建模型之前的分析和计算清华大学出版社102.1.1问题的提出0,4.126.18.018001000min212121121xxxxxxxxxz约束条件目标函数得到本问题的数学模型为：清华大学出版社112.1.1问题的提出每一个线性规划问题都用一组决策变量表示某一方案，这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的；都有关于各种资源和资源使用情况的技术数据，创造新价值的数据；存在可以量化的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示;都有一个达到某一目标的要求，可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同，要求目标函数实现最大化或最小化。nx,x,x21)n,j;m,i(c;ajij11上述两个问题具有的共同特征：清华大学出版社122.1.1问题的提出nmmnmmnnnccbbbaaaaaaaaamxxx212121222211121121c21价值系数动活资源决策变量决策变量及各类系数之间的对应关系清华大学出版社132.1.1问题的提出).(x,,x,xb),(xaxaxa).(b),(xaxaxab),(xaxaxa).(xcxcxczmax(min)nmnmmmnnnnnn310211121221122222121112121112211约束条件目标函数线性规划模型的一般形式清华大学出版社142.1.2图解法1.2图解法例1是一个二维线性规划问题，因而可用作图法直观地进行求解。12121212max2328416412,0zxxxxxxxx清华大学出版社152.1.2图解法表示一簇平行线33212zxx2132xxzmax目标值在（4，2）点，达到最大值14清华大学出版社162.1.2图解法（1）无穷多最优解(多重最优解)，见图1-4。（2）无界解，见图1-5-1。（3）无可行解，见图1-5-2。通过图解法，可观察到线性规划的解可能出现的几种情况：清华大学出版社172.1.2图解法目标函数maxz=2x1+4x2图1-4无穷多最优解（多重最优解）清华大学出版社182.1.2图解法ox,xxxxxxxzmax2121121242图1-5-1无界解清华大学出版社19当存在相互矛盾的约束条件时，线性规划问题的可行域为空集。例如，如果在例1的数学模型中增加一个约束条件:则该问题的可行域即为空集，即无可行解，85.121xx无可行解的情形2.1.2图解法清华大学出版社2085.121xx增加的约束条件图1-5-2不存在可行域2.1.2图解法清华大学出版社212.1.3线性规划问题的标准型式111221111221121122222112212:maxzca,,,0nnnnnnmmmnnmnMxcxcxxaxaxbaxaxaxbaxaxaxbxxx目标函数：约束条件：2.1.3线性规划问题的标准型式清华大学出版社222.1.3线性规划问题的标准型式n,,j;bbbb;aaaP;xxxX;c,,c,cCn,,,j,xbxPCXzmax:Mmmjjjjnnjnjjj''212102121212111约束条件：目标函数：用向量形式表示的标准形式线性规划线性规划问题的几种表示形式清华大学出版社232.1.3线性规划问题的标准型式用矩阵形式表示的标准形式线性规划Tnnmnmn''x,,x,xX;P,P,PaaaaAXbAXCXzmax:M21m12111111bbb0000决策变量向量：；资源向量：零向量：系数矩阵：约束条件：目标函数：清华大学出版社242.1.3线性规划问题的标准型式'kkkxxx(1)若要求目标函数实现最小化，即minz=CX，则只需将目标函数最小化变换求目标函数最大化，即令z′=−z，于是得到maxz′=−CX。(2)约束条件为不等式。分两种情况讨论：若约束条件为“≤”型不等式，则可在不等式左端加入非负松弛变量，把原“≤”型不等式变为等式约束；若约束条件为“≥”型不等式，则可在不等式左端减去一个非负剩余变量(也称松弛变量)，把不等式约束条件变为等式约束。(3)若存在取值无约束的变量xk,可令0,'kkxx如何将一般线性规划转化为标准形式的线性规划清华大学出版社252.1.3线性规划问题的标准型式例3将例1的数学模型化为标准形式的线性规划。例1的数学模型在加入了松驰变量后变为1212345123121412521212345max23max230002828416416412412,0,,,,0zxxzxxxxxxxxxxxxxxxxxxxxxxx清华大学出版社262.1.3线性规划问题的标准型式例4将下述线性规划问题化为标准形式线性规划为无约束3213213213213210533732x;x,xxxxxxxxxxxxxzmin(1)用x4−x5替换x3，其中x4，x5≥0；(2)在第一个约束不等式左端加入松弛变量x6；(3)在第二个约束不等式左端减去剩余变量x7；(4)令z′=−z，将求minz改为求maxz′即可得到该问题的标准型。清华大学出版社272.1.3线性规划问题的标准型式例4例4的标准型'12456712456124571245124567max23()00()7()232()5,,,,,0zxxxxxxxxxxxxxxxxxxxxxxxxxx清华大学出版社282.1.4线性规划问题的解概念1.可行解2.基3.基可行解4.可行基清华大学出版社292.1.4线性规划问题的解的概念定义满足约束条件(1-5)、(1-6)式的解X=(x1,x2，…，xn)T，称为线性规划问题的可行解，其中使目标函数达到最大值的可行解称为最优解。)(n,,,j,x)(m,,i,bxa)(xczmaxjnjijijnjjj61210512141111.可行解清华大学出版社302.1.4线性规划问题的解的概念为基变量。为基向量，为线性规划问题的基。称阶非奇异子矩阵中的是系数矩阵),2,1(x),2,1(P,,B0BAjj21212222111211mjmjPPPaaaaaaaaaBmmBmmmmmmm2.基，基向量，基变量清华大学出版社312.1.4线性规划问题的解的概念是基可行解43210Q,Q,Q,Q,满足非负条件（1-6）的基解，称为基可行解.基可行解的非零分量的数目不大于m，并且都是非负的。3基可行解清华大学出版社322.1.4线性规划问题的解的概念对应于基可行解的基，称为可行基。约束方程组(1-5)具有的基解的数目最多是个，一般基可行解的数目要小于基解的数目。以上提到了几种解的概念，它们之间的关系可用图1-6表明。说明：当基解中的非零分量的个数小于m时，该基解是退化解。在以下讨论时，假设不出现退化的情况。mnC4可行基清华大学出版社332.1.4线性规划问题的解的概念mnC不同解之间的关系P552.1（1），2.2（1）(无需列初始单纯形表）作业清华大学出版社35第2节线性规划问题的几何意义2.2.1基本概念2.2.2几个定理清华大学出版社362.2.1基本概念1.凸集2.凸组合3.顶点清华大学出版社372.2.1基本概念定义设K是n维欧氏空间的一点集，若任意两点X(1)∈K，X(2)∈K的连线上的所有点αX(1)+(1−α)X(2)∈K，(0≤α≤1)，则称K为凸集。图1-71.凸集清华大学出版社382.2.1基本概念实心圆，实心球体，实心立方体等都是凸集，圆环不是凸集。从直观上讲，凸集没有凹入部分，其内部没有空洞。图1-7中的(a)(b)是凸集，(c)不是凸集。图1-2中的阴影部分是凸集。任何两个凸集的交集是凸集，见图1-7(d)清华大学出版社392.2.1基本概念设X(1)，X(2)，…，X(k)是n维欧氏空间En中的k个点。若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k使X=μ1X(1)+μ2X(2)+…+μkX(k)则称X为X(1)，X(2)，…，X(k)的