第1章 线性规划与单纯形法 .生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划论要解决的问题规划论作为运筹学的一大分支，常分成线性规划、非线性规划和动态规划三个部分线性规划是运筹学创立初期人们重点研究的内容，是生产、科研和企业管理中一种有效的优化技术，其理论完善，方法简便，应用广泛，成为规划问题乃至运筹学最基本的内容第一节 线性规划的基本概念1、 线性规划的数学模型 线性规划问题通常有两大类型：一类是在一定的资源条件限制下，如何组织安排生产获得最大的经济效益（如产量最多或利润最大等）；另一类是当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源 （如资金、设备、原材料、人工或时间等）去完成给定的任务或目标现各举一例如下：例1.1产计划问题常山机器厂生产 I、II 两型产品这两型产品都分别要在A、B、C三种不同设备上加工按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如表1-1所示：表1-1 单位产品消耗设备工时III设备工时限量（小时）设备A2212设备B4016设备C0515单位利润（元）23如何安排生产才能使总的利润最大？解 设计划期内两种产品的产量分别为x1和x2，由于设备A在计划期内的有效时间为12h，不允许超过，于是有2 x1+2 x2≤12。
对于B、C设备也可列出类似的不等式：4 x1≤16；5 x2≤15该厂的目标是在各种设备允许的情况下，使总的利润收入z=2 x1+3 x2为最大因此例1可以归结为如下的数学模型例1.2配料问题 一饲养场饲养某种动物用于出售，该动物每天至少需要700克蛋白质， 30克矿物质，100毫克维生素现有四种饲料可供选用，各种饲料每千克营养成分含量及单价如表1-2所示：表1-2 每千克饲料中各营养成分的含量IIIIIIIV需要量蛋白质（克）3215700矿物质（克）10.50.2230维生素（毫克）0.510.32.5100单价（元/千克）0.81.20.62四种饲料各采购多少，才能使总费用最小？解 设四种饲料分别采购x1,x2,x3,x4千克.根据该动物每天对蛋白质的需求，有 同理得到类似的不等式；该饲料厂的目标是在满足动物生长需求的情况下，使总的费用为最小因此例2可以归结为如下的数学模型 从上面的例子可以看出，所谓规划问题，就是求规划目标在若干限制条件下的极值问题规划问题的数学模型包含三个组成要素：（1）决策变量或变量，即决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量通常用x1，x2，…，xn表示；（2）目标函数，即问题要达到的目标要求，表示为决策变量的函数。
通常用 z=f(x1，x2，…，xn)表示，按优化目标分别在这个函数前面加上max或min；（3）约束条件，即决策变量取值时受到各种可用资源的限制，通常表示为含决策变量的等式或不等式若在规划问题的数学模型中，决策变量是可控的连续变量，目标函数和约束条件都是线性的，则此类模型称为线性规划问题或线性规划（Linear Programming）实际问题中线性的含义：一是严格的比例性，如生产某产品可获取的利润和产品的数量严格成比例；二是可叠加性，如生产多种产品时对某项资源的消耗量应等于各产品对该项资源的消耗量之和一般地，假设线性规划数学模型有n个决策变量，分别用xj（j=1,2…,n）表示目标函数中变量系数用cj表示, 通常cj称为价值系数有m个约束条件，第i个约束条件中变量xj的系数用aij表示，aij常称为工艺系数或技术系数约束条件右端的常数用bi表示，通常bi称为资源限量或资源拥有量于是线性规划数学模型的一般表达式可写成(1.1)一个线性规划问题有解，是指能找出一组xj(j＝1,...,n)的值既满足(1.1)中的约束条件，又满足决策变量的取值要求，此时称X=(x1,x2,...,xn)T为该问题的可行解。
全部可行解的集合称为可行域．特别的，能使目标函数达到最优的可行解称为最优解研究线性规划的根本目的在于求出它的最优解，这个过程称为求解线性规划问题式(1.1)也可简写为(1.2)若各个约束条件左右两端的连接符号都相同（都是“≤”，或都是“=”，或都是“≥”），则可利用向量把线性规划问题写成(1.3)在式(1.3)中式(1.3)还可用矩阵形式表示为 (1.4)式(1.4)中A称为约束条件中变量的系数矩阵，或简称为约束变量的系数矩阵注意在实际意义中决策变量的取值一般为非负实数在单纯数学意义下也可以有决策变量取非正实数另外若某个决策变量xj表示第j种产品本期产量相对于前期产量的变化量，则xj的取值范围可以是全体实数2、 图解法对于仅含有两个决策变量的线性规划问题有一种简单直观的几何方法——图解法图解法的步骤是：先在平面直角坐标系中画出约束条件所确定的可行域；再对任意确定的z，画出目标函数所代表的一族直线（常称为目标函数等值线）；最后沿优化方向平移目标函数等值线，确定最优解（如果有的话）例1.3 用图解法求例1的最优解解：由该问题所确定的可行域为图1-1所示的凸五边形目标函数z=2 x1+3 x2表示一族直线，向右上方平移目标函数等值线将使目标函数值增大，依此方向平移到与可行域相切为止。
此时唯一切点即为最优解，这个切点是凸五边形的一个顶点，如图1-2所示此问题有唯一最优解当 x1=x2=3 时，Zmax = 15即常山机器厂生产的最佳方案为I、II型产品各生产3件，可获得最大利润15元例3有唯一一个最优解，而任意一个线性规划问题的解还可能有其它情形例1.4 用图解法求解下列线性规划问题 解 用图解法求解，如图1-3所示，沿优化方向平移时目标函数等值线与可行域在整个线段上相切，即该问题的最优解为此线段上的所有点故该问题有无穷多个最优解，它们使目标函数都达到同一个最大值例1.5 用图解法求解下列线性规划问题解 用图解法求解，如图1-4所示，该问题的可行域上方无边界，目标函数等值线沿着优化方向可以无限延伸，使得目标函数值无限增大此时问题有可行解但目标函数值无界，故无最优解，常称之为无界解这种情形的出现往往是由于在建立数学模型时遗漏了某些必要的资源约束条件注意：可行域无界仅是线性规划问题出现无界解的必要条件，而不是充分条件例1.6 用图解法求解下列线性规划问题解 用图解法求解时该问题的可行域是空集，如图1-5所示表明此问题无可行解（自然是最优解的其原因是模型本身有错误，出现了矛盾约束。
尽管图解法只能解决含有两个决策变量的线性规划问题，但从它的解题思路和几何直观上得到了线性规划问题的若干规律，对之后介绍求解一般线性规划问题的代数方法——单纯形法很有启示：(1) 求解线性规划问题时，解有四种情况：唯一最优解、无穷多最优解（也称为多重最优解）、无界解（也称为有可行解但无最优解）和无可行解2) 若线性规划问题的可行域不是空集，则可行域为凸集 (3) 若线性规划问题有最优解，则最优解一定可以在可行域的某个顶点达到若在两个顶点同时达到最优解，则它们连线上的所有点都是最优解，此时对应问题有无穷多最优解4) 解题思路：先找出凸集的任一顶点，计算其目标函数值再与周围相邻顶点的目标函数值比较是否比这个值更优若否，则该顶点就是最优解的点或最优解的点之一；若是，则转到比该顶点的目标函数值更优的另一顶点重复上述过程，直到找到使目标函数值达到最优的顶点为止（如果有的话）第2节 线性规划的标准形式和解的性质1、 线性规划的标准形式\在不同情况下，归结出来的线性规划问题可能多种多样，在目标函数和约束条件上也可能各有不同为了讨论问题的方便，规定线性规划问题的标准形式如下：（1.5）标准形式的线性规划问题中，目标函数为求极大值（有些书上规定是求极小值），约束条件全为等式，约束条件右端常数全为非负值，决策变量的取值必须非负。
对于不符合标准形式的线性规划问题（或称为非标准形式），都可以分别通过下述方法转化为标准形式1.目标函数为求极小值，即为因为在满足相同约束条件的前提下使z达到极小值的那组决策变量必定使(-z)达到极大值，反之亦然，故令新目标函数z'=-z，即转化为2. 约束条件为不等式当约束条件为“≤”时，例如2 x1+2 x2≤12，可令x3=12-2 x1-2 x2,得2 x1+2 x2+x3=12,显然x3≥0这样增加的决策变量x3取非负值，加到原约束条件中把“≤”约束转化为等式约束，故称为松弛变量类似的，当约束条件为“≥”时，例如3 x1+8 x2≥24，可令x4=3 x1+8 x2-24,得3 x1+8x2-x4=12,显然x4≥0这样增加的决策变量x4取非负值，加到原约束条件中把“≥”约束转化为等式约束，故称为剩余变量（也可称为剩余变量）松弛变量或剩余变量在实际问题中表示未被利用的资源数或短缺的资源数，均未转化为价值和利润，所以引入到模型后它们在目标函数中的系数均为零3. 若某个约束条件的右端项bi是负数，则可将此约束两边同时乘以(-1)，从而(-bi)成为正数4. 变量xp≤0.应令xp'=-xp,代入模型，显然xp'≥0.5. 变量xq取值无约束.应令xq=xq'-xq''代入模型，显然xq'、xq''≥0.例1.7将下列线性规划模型化为标准形式。
并引入松弛变量x4, x5,按照上述方法将问题化为如下标准形式：二、 线性规划的基可行解的概念 已知线性规划的标准形式： (1.6)A=(aij)为约束方程组的m×n阶系数矩阵(设n>m)，其秩为m.若B是矩阵A中一个m阶可逆子矩阵，则称B是线性规划问题的一个基矩阵（简称为基）不失一般性，设基为将B中每个列向量即P1,P2,… ,Pm称为基向量，与基向量Pj对应的变量xj称为基变量(常记为XB)，除基本量以外的其它变量称为非基变量(常记为XN)可见只有先确定一个基，才有随之确定的基变量和非基变量，且基变量有m个，非基变量有n-m 个基解 在式（1.6）的约束方程组中令所有非基变量xm+1=xm+2=…=xn =0 后，因为B是可逆矩阵，根据克拉默法则，解出m个基变量的唯一值XB=(x1,x2,...,xm)T，再加上非基变量取0值得到的解 X=(x1,x2,...,xm,0,...,0)T 称为相应于基B的基解(或基本解)显然，基解的总数不会超过 个，在每个基解中取值非0的变量个数不会大于m基可行解 满足变量非负取值的基解称为基可行解(或基本可行解)可行基 对应于基可行解的基称为可行基。
基最优解 使目标函数达到最大值的基可行解称为基最优解最优基 对应于基最优解的基称为最优基例1.8在下述线性规划问题中，列出全部基、基解、基可行解，并指出最优解解 先写出系数矩阵因为 秩(A)≤3，所以只要找出3个列向量组成可逆矩阵就成为线性规划问题的一个基，再求出对应的基解表1-1列出了本例的全。