1、-1-第二章 线性规划线性规划（linear programming，简称 LP）是运筹学的一个重要分支，研究得比较早，尤其自 1947年丹捷格（G.B.Dantzig ）提出了单纯形法之后，线性规划在理论上趋向成熟线性规划研究的对象大体可分为两大类：一类是在现有的人、财、物等资源的条件下，研究如何合理地计划、安排，可使得某一目标达到最大，如产量、利润目标等；另一类是在任务确定后，如何计划、安排，使用最低限度的人、财等资源，去实现该任务，如使生产成本、费用最小等这两类问题从本质上说是相同的，即都在一组约束条件下，去实现某一个目标的最优（最大或最小） 线性规划研究的问题要求目标与约束条件函数均是
2、线性的，而目标函数只能是一个在经济管理问题中，大量的问题是线性的，有的可以转化为线性的，从而使线性规划有极大的应用价值据美国财富杂志对全美 500家大公司的调查，线性规划的应用名列前茅，有 85%左右的公司频繁地使用线性规划线性规划问题及其数学模型一、线性规划问题的数学模型在生产实践和日常生活中，经常会遇到如何合理地使用有限资源（如资金、劳力、材料、机器、仪器设备、时间等） ，以获得最大效益的问题例 2-1 某制药厂在计划期内要安排生产、两种药品，这些药品分别需要在 四种不同的设备上加工按工艺规定，每千克药品和DCBA、在各台设备上所需要的加工台时数如表 2-1已知各设备在计划期内有效台时数（
3、1 台设备工作 1小时称为 1台时）分别是 12、8、16 和 12该制药厂每生产 1千克药品可得利润 200元，每生产 1千克药品可得利润 300元问应如何安排生产计划，才能使制药厂利润最大？表 2-1 两种药品每千克在各台设备上所需的加工台时数BA、药品 CD-2- 2 1 4 0 2 2 0 4这是一个资源有限，但需利润最大的线性规划问题解 设 ， 分别表示在计划期内药品和的产量（千克） ， 表示这1x2 Z个期间的制药厂利润则计划期内生产、两种药品的利润总额为（元） 但是生产、两种药品在 设备上的加工台时数必21302Z A须满足 ；在 设备上的加工台时数必须满足 ；在 设xB821x
4、C备上的加工台时数必须满足 ；在 设备上的加工台时数必须满足164xD；生产、两种药品的数量应是非负的数，即 于是上述124x 0,21x的问题归结为：目标函数 21302Max xZ182x约束条件 641 2x0,1同样，在经济生活和生产活动中也遇到另一类问题，即为了达到一定的目标，应如何组织生产，或合理安排工艺流程，或调整产品的成分等，以使消耗（人力、设备台时、资金、原材料等）为最少例 2-2 用 3种原料 配制某种食品，要求该食品中蛋白质、脂321B、肪、糖、维生素的含量不低于 15、20、25、30 单位以上 3种原料的单价及每单位原料所含各种成分的数量，如下表 2-2所示问应如何配
5、制该食品，使所需成本最低？表 2-2 3 种原料所含成分营养成分原料食品中营养成分的最低需要量（单位）-3-1B23B蛋白质（单位/千克） 5 6 8 15脂肪（单位/千克） 3 4 6 20糖（单位/千克） 8 5 4 25维生素（单位/千克） 10 12 8 30原料单价（元/千克） 20 25 30这个问题是在食品的营养要求得到满足的前提下，如何通过适当的原料配比，使食品的成本最低解 设 分别表示原料 的用量（千克） ， 表示食品的321x、 321B、 Z成本（元） ，则这一食品配制问题变为：目标函数 321050Min xxZ86 43321xx约束条件 55 080321xx,3例
6、 2-3 某医院每天至少需要下列数量的护士（见表 2-3） 表 2-3 某医院每天至少需要的护士数班次 时间 护士数1 上午 6时上午 10时 602 上午 10时下午 2时 703 下午 2时下午 6时 604 下午 6时晚 10时 505 晚 10时凌晨 2时 20-4-6 凌晨 2时上午 6时 30每班的护士在值班开始时向病房报到，连续工作 8小时试问：为满足每班所需要的护士数，医院最少应雇用多少护士？请列出线性规划问题的数学模型解 设 表示第 1班次向病房报到的护士数；1x表示第 2班次向病房报到的护士数；2表示第 3班次向病房报到的护士数；3x表示第 4班次向病房报到的护士数；4表示
7、第 5班次向病房报到的护士数；5x表示第 6班次向病房报到的护士数6则有目标函数 61Min Zjx06721x3约束条件 504x2365x且为整数 0j 6,21j例 2-4 某一卫生所配有 1名医生和 1名护士医生每天工作 8小时，护士每天工作 9小时服务的项目是接生和做小手术一次接生，医生要花 0.5小时，护士同样要花 0.5小时；一次小手术，医生要花 1小时，护士要花 1.5小时这是一所小规模的卫生所，每天容纳的手术数和接生数合计不能超过 12-5-次假定一次手术的收入为 200元，一次接生的收入为 80元问怎样合理安排接生和手术的数量，使医生和护士一天工作能收入最多？解 设每天手术
8、数为 ，每天接生数为 ，则1x2x目标函数 1802Ma Zx9213x 且为整数0,21x二、线性规划问题的结构特征从上面 4个例子可见，线性规划的数学模型（model of LP）有如下特征：1都有一组未知变量（ ）代表某一方案，它们取不同的非负nx,21值，代表不同的具体方案；2都有一个目标要求，实现极大或极小目标函数要用未知变量的线性函数表示；3未知变量受到一组约束条件的限制，这些约束条件用一组线性等式或不等式表示正是由于目标函数和约束条件都是未知变量的线性函数，所以我们把这类问题称为线性规划问题线性规划问题的一般形式：目标函数 nxcxcZ21 (Min)ax121),(ban22,
9、xx约束条件 mnmmbaxa),(21 0,nx约束条件-6-这里， 称为目标函数，记为 ，其中， （nxcxc21 Zjc）称为成本或利润系数； （ ； ）称为约nj,2ijam,21nj,21束条件中未知变量的系数； （ ）称为限定系数ib,三、线性规划问题的标准形式建立线性规划的标准形式有助于我们研究它的求解方法，至于其他各种形式的线性规划问题，我们可以先将非标准形式变成标准形式，然后再用标准形式的求解方法求解（一）线性规划问题的标准形式线性规划的标准形式（standard form of LP）为：目标函数 nxcxcZ21Ma 121 ban2221xxnmnmbxaxa210,2
10、1nx( )i mi,式中， （ ）称为成本或利润系数； （ ；jcn,2ijam,21）称为未知变量的系数； （ ）称为限定系数nj,21ib,21标准形式的主要特点是：目标函数最大化；所有的约束条件由等式表示；所有的变量和每一约束条件右端的常数项均为非负值（二）书写形式为书写简便，我们可以将上述线性规划问题的标准形式写成如下两种形式，其中 代表约束条件.ts1简缩形式约束条件-7-njjxcZ1Manjijib1 mi,21.ts0jxnj,ibi212矩阵形式 CXZMax bA.ts0其中， ),(21ncCmnmnaaA 21211 nxX 2mb 210 这里 为成本或利润向量，
11、为决策向量， 为系数矩阵（或称约束矩阵）CXA， 为限定向量（或称右端向量） ，条件 称为非负约束b （三）标准形式的转化当给出的线性规划为非标准形式时，可以按照下述的方法化为标准形式1目标函数的转换 若给出的线性规划要求目标函数极小化，即 ，因 ，所以只须令 ，即有njjxcZ1Mi )(Max in ZZjnjcZ 1)( )(a 这就是标准形式的目标函数了-8-2约束条件的转换 由于标准形式要求所有的约束条件是等式，必须把不等式的约束条件化为等式须引入新的变量，代表每个不等式左右端之间的差额这些新的变量称为松弛变量或剩余变量这里有 2种情况：一种是约束条件为“ ”形式的不等式，则可在“
12、”的左端加入非负的松弛变量，把原“ ”形式的不等式变为等式；另一种是约束条件为“ ”形式的不等式，则可在“ ”号的左端减去一个非负的剩余变量（也可称松弛变量） ，把不等式改为等式例如前面例 2-1中线性规划问题的标准形式可写为：目标函数 21302Max xZ1 1 、842xx.ts 6 451 、122xx0,61式中 为松弛变量6543xx、例 2-2中线性规划的标准形式可写成：321050MaxZ15 86 54321 x2 35x.ts 6321x30 807x0,721x式中 ， 为剩余变量（也可称松弛变量） Z4要注意的是松弛变量或剩余变量都是非负值，它们的实际意义是未被利用-9
13、-的资源或额外的提供量由于松弛变量或剩余变量都不会影响目标函数的增加或减少，所以在目标函数中它们的系数都应当为零3变量的非负转换 若存在无非负要求的变量，即变量 取正值或负值kx都可以，在物理、经济意义上都是合理的，这时为了满足标准形式对变量的非负要求，可令 ，其中， ， 由于 可能大于 ，kxk 0kxkk k也可能小于 ，故 可为正值也可为负值kx 以上讨论说明，任何形式的线性规划问题都可化成标准形式线性规划问题的图解法讨论两变量的线性规划问题的图解法（graphical solution of LP problems） ，是为了更直观地了解线性规划问题及其解的基本概念，从而了解求解线性规
14、划问题的一般方法单纯形法的基本原理一、线性规划问题解的基本概念设线性规划问题的标准形式为： mibnjxiatsxcZijnijinjj ,210,.11 M 1可行解 满足约束条件的解 ，称为线性规划问题的TnxX),(21可行解所有可行解的集合称为可行域2最优解 满足目标函数式的可行解，称为线性规划问题的最优解3最优值 对应于最优解的目标函数之值，称为最优值二、两个变量的线性规划问题的图解法例 2-5 以上一节例 2-1为例:-10-0,12468.302121xxtsZMa 由于此问题是两变量的线性规划问题，因而可用图解法求解求解过程是先求出满足约束条件的可行解区域；然后从可行解区域中找
15、出最优解具体步骤如下：第 1步 建立平面直角坐标系，取 为横轴， 为纵轴1x2x第 2步 求满足约束条件的可行解区域本例中作直线： ,第一个约束不等式的解由直线21x及其左下方半平面表示；作直线： ，第二个约束不121x 821x等式的解由直线 及其左下方半平面表示；作直线： ，第82x 164三个约束不等式的解由直线 及其左方半平面表示；作直线164： ，第四个约束不等式的解由直线 及其下方半平面表示；142x 124x和 变量非负条件的区域为第 1象限满足所有约束条件的可行解区域（也1称可行域）是由上述 5个区域的公共部分表示，即图 2-1中 的区域OABCD（包括边界） 在这个区域里的每一点(包括边界上的点)都是可行解从图上我们可以看到这个可行域是一个凸多边形，我们把它称为凸集（如果在形体中任意取两点连接一根直线，若线段上所有的点都在这个形体中，则称该形体为凸集） 第 3步 作目标函数的等值线簇，确定目标函数值增加方向本例中，由目标函数 可知，当 Z值取不同的数值时，在2130 xZ图上可得到一簇以 Z为参数的平行线位于同一直线上的点，具有相同的目标函数值，因而称每条直线为“等值线” 图 2-1 图解法求解例 2-1
