[数学]线性规划与单纯形法.doc

第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 x212。对于B、C设备也可列出类似的不等式：4 x116；5 x215。该厂的目标是在各种设备允许的情况下，使总的利润收入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(j1,.,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 x212，可令x3=12-2 x1-2 x2,得2 x1+2 x2+x3=12,显然x30。这样增加的决策变量x3取非负值，加到原约束条件中把“”约束转化为等式约束，故称为松弛变量。类似的，当约束条件为“”时，例如3 x1+8 x224，可令x4=3 x1+8 x2-24,得3 x1+8x2-x4=12,显然x40。这样增加的决策变量x4取非负值，加到原约束条件中把“”约束转化为等式约束，故称为剩余变量（也可称为剩余变量）。松弛变量或剩余变量在实际问题中表示未被利用的资源数或短缺的资源数，均未转化为价值和利润，所以引入到模型后它们在目标函数中的系数均为零。3. 若某个约束条件的右端项bi是负数，则可将此约束两边同时乘以(-1)，从而(-bi)成为正数。4. 变量xp0.应令xp=-xp,代入模型，显然xp0.5. 变量xq取值无约束.应令xq=xq-xq代入模型，显然xq、xq0.例1.7将下列线性规划模型化为标准形式。并引入松弛变量x4, x5,按照上述方法将问题化为如下标准形式：二、 线性规划的基可行解的概念 已知线性规划的标准形式： (1.6)A=(aij)为约束方程组的mn阶系数矩阵(设nm)，其秩为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列出了本例的全部基和基解，其中共有5个基可行解，表中用标注的为最优解即X=(3,3,0,4,0)T。表1-1基基解是基可行解？目标函数值 x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-5否18P3P4P500121615是0三、 线性规划解的性质在介绍线性规划问题解的性质之前，先介绍凸集和顶点。设E是n维向量的集合，X1和X2是E的任意两点，若X1和X2连线段上的点X=aX1+(1-a)X2 (0a1)仍属于集合E，则称E为凸集。直观上讲：凸集是没有凹入部分，其内部没有空洞。 顶点： 凸集E中的点X，若不存在凸集中的点X1,X2,使得X成为X1和X2连线段上的点，或者不存在X1及X2,使得X=aX1+(1-a)X2，(0a1)，则称点X为顶点。定理1 若线性规划问题存在可行域，则其可行域一定是凸集。证明：设 max z=CX st.AX=b X0并设其可行域为C，若X1、X2为其可行解，且X1X2 ，则 X1C，X2 C， 即AX1=b，AX2=b，X10，X20，又 X为X1、X2连线上一点，即 X=aX1+(1-a)X2C， (0a1)， AX=aAX1+ (1-a)AX2 = ab+ (1-a)b =b , (0a1)，且 X 0， X C，即C为凸集。 引理 线性规划问题的可行解X为基可行解的充要条件，X的正分量所对应的系数列向量是线性独立的证明：必要性：X基可行解X的正分量所对应的系数列向量线性独立 可设X=(x1,x2,xk,0,0,0)T，若X为基可行解，显然，由基可行解定义可知x1, x2,xk所对应的系数列向量P1,P2,Pk应该线性独立。充分性： X的正分量所对应的系数列向量线性独立 X为基可行解若A的秩为m，则X的正分量的个数km；当k=m时，则x1,x2,xk的系数列向量P1,P2,Pk恰好构成基， X为基可行解。当k0，得到如下结论：(1) 若对所有jm+1，有sj 0 ，则z（1） z （0） ，即z （0）为最优函数值，X（0）为唯一最优解；(2) 若对所有j m+1 ，有sj 0，且存在某个非基变量的检验数sk=0，则将Pk作为新的基向量得出新的基可行解X（1） ，满足z（1） = z （0） ，故z（1） 也为最优函数值，从而 X（1）也为最优解， X（0） 、X（1） 连线上所有点均为最优解，因此该线性规划模型具有无穷多最优解；(3) 若存在某个sj 0，但对应的第j列系数全非正，即aij0，则q不受限制，可以任意取值，故当 q+时，有z（1） +， 该线性规划模型具有无界解。注意：线性规划问题出现无可行解的情形将在后面进行讨论。3、 单纯形表和单纯形法的基本步骤 为书写规范和便于计算，对单纯形法的计算设计了一种专门的表格，称为单纯形表（见表1-5）。一个含有n个决策变量m个约束条件的标准线性规划问题，对应的单纯形表中第一行称为价值行，用Cj表示，列出每个决策变量在目标函数中的系数；第二行称为变量行，列出n个决策变量；最后一行称为检验数行，列出每个决策变量的检验数（易见基变量的检验数为0）；第一列称为基价值列，用CB表示，列出每个基变量在目标函数中的系数；第二列称为基列（或基变量列），用B或XB表示,列出m个基变量；第三列称为基解列，用b表示，即每个基变量的取值；最后一列称为比值列；而中心位置m行n列的矩阵为约束条件的系数矩阵，注意基变量对应的系数矩阵是m阶的单位矩阵。不难看出从表中可以方便的计算出每个非基变量的检验数，即用变量的价值减去基价值与变量的系数乘积之和，即表1-5CjC1C2CjCn比值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1nq1CB2xB2b2a21a22a2ja2nq2CBnxBnbmam1am2amjamnqm检验数sjs1s2sjsn每一次迭代对应一张单纯形表，含初始基可行解的单纯形表称为初始单纯形表，含最优解的单纯形表称为最终单纯形表。下面介绍用单纯形表计算线性规划问题的步骤。（注意此处考虑的是有可行解的线性规划问题。） 将线性规划问题化成标准型。构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。计算各非基变量xj的检验数sj= Cj -CBPj，若所有sj0，则问题已得到最优解，停止计算，否则转入下一步。注意在有最优解，即所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。在大于0的检验数中，若某个sk所对应的系数列向量Pk0，则此问题是无界解，停止计算，否则转入下一步。根据maxsjsj0=sk原则，确定xk为换入基的变量，简称为换入变量(或进基变量)，再按比值q的选取规则计算：q=minbi/aik| aik0=bl/ aik 确定xBl为换出基的变量，简称换出变量（或出基变量）。建立新的单纯形表，此时基变量中xk取代了xBl的位置。将aik称为主元素或主元，常用方括号 标记，利用主元进行迭代，即通过矩阵的初等行变换，把xk所对应的列向量变为单位列向量，即主元aik变为1，同列中其它元素为0，转第 步。 上述这种利用单纯形表求解线性规划问题的方法称为单纯形法（simplex method）。例1.8用单纯形法求解下列线性规划问题.解：先标准化其约束条件的系数矩阵为A中有3阶单位矩阵，选其为基B=(P3,P4,P5)。令非基变量x1=x2=0,得到基变量x3=12,x4=16,x5=15,从而得到初始基可行解X=(0,0,12,16,15)T，列出初始单纯形表，如表1-7：表1-7cj23000CBBbX1X2X3X4X50X3122210060X41640010-0X515050013j23000注意变量x1,x2的 检验数大于0，选择正检验数中最大的对应变量x2为换入变量；依照比值的计算规则，只有x2的正系数才有对应的比值，即故变量x5为换出变量，从而元素5为主元（用标记），上述计算过程可直接在表中进行。利用初等行变换将5变为1，此列其它系数变为0，得到新的单纯形表（见表1-8）表1-8cj23000CBBbX1X2X3X4X50X362010-2/530X4164001043X2301001/5-j2000-3/5注意表中x1为换入变量；依照比值的计算规则，只有x1的正系数才有对应的比值，即故变量x3为换出变量，从而元素2为主元（用标记），再将2变为1，此列其它系数变为0，得到新的单纯形表（见表1-9）表1-9cj23000CBBbX1X2X3X4X52X13101/20-1/50X4400-214/53X2301001/5j00-10-1/5表1-9中所有检验数均非正，得到最优解X=(3,3,0,4,0)T,zmax=15,进一步由于非基变量的检验数全小于0，该问题是唯一最优解。四、关于单纯形法的补充说明单纯形法在实际应用中非常有效，已被广泛采用，但在理论上不是多项式时间算法，但这并不影响我们使用该方法解决实际中的相关问题。下一节将解决线性规划问题化为标准形时，约束条件的系数矩阵中不存在单位矩阵，应如何构造初始可行基。 第四节 初始可行基的求法-人工变量法在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初始基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为添加的变量称为人工变量，由此构成的可行基称为人工基，这种用人工变量作桥梁的求解方法称为人工变量法。一、大M法 例1.9用单纯形法求解下列线性规划问题。解：先标准化为但是A中没有单位矩阵，在A中人为的增加两列此时A有单位子矩阵，选择该单位矩阵作为基，常称为人工基。于是该问题新增加了两个变量：x4和x5，称为人工变量。对应的约束方程组为：为使两个方程组等价，要求可行解中人工变量的值为0.问题若有最优解，则最优解中人工变量的值也必须为0.为此取人工变量在目标函数中的系数为-M，常称为罚因子（其中M为任意大的正数）。一旦人工变量取值不为0，则目标函数无法极大化。本例引入人工变量后转化为：再用单纯形法继续计算如下：Cj-2-30-M-MCBBbX1X2X3X4X5-MX4311-1103-MX54120012j-2+2M-3+3M-M00-MX411/20-11-1/22-3X221/21001/24j-1/2+M/20-M03/2-3M/2-2X1210-22-1-3X21011-11j00-11-M1-M在最终单纯形表中，检验数全非正，且人工变量取值全为0，因此该问题有唯一最优解：注意： 若表中所有sj 0 ，但存在非0的人工变量 ，则该模型无可行解。采用大M法求解线性规划模型时，当模型中各个系数与M的值非常接近或相差甚远时，若用手工计算，不会出现问题。但是若利用计算机求解，只能用很大的数代替M,则容易使机器判断出错，从而使大M法失效。在这种情况下，可采用下面的两阶段法进行计算。二、两阶段法 两阶段法，顾名思义是将线性规划问题分成两个阶段来处理。第一阶段的作用是判断原线性规划问题是否存在可行解。为此，不考虑原问题是否存在可行解，给原线性规划问题加入人工变量，并构造仅含人工变量的目标函数w（通常人工变量在w中的系数一般取为1）和要求w的最小值，然后用单纯型法求解。若求得wmin=0，则表明已知问题有可行解，进入第二阶段，否则表明已知问题无可行解，计算结束。进入第二阶段后，将第一阶段得到的最终表去掉人工变量，并将目标函数还原为原线性规划问题的目标函数（即修改最终表中的第一行和第一列），以此作为第二阶段的初始表，继续用单纯形法求解。例1.10用两阶段法求解下列线性规划问题。解：引入人工变量，转化为：第一阶段，求解线性规划问题：先标准化：再用单纯形法继续计算如下：Cj000-1-1CBBbX1X2X3X4X5-1X4311-1103-1X54120012j23-100-1X411/20-11-1/220X221/21001/24j1/20-10-3/20X1210-22-10X21011-11j000-1-1在最终单纯形表中，检验数全非正，且人工变量取值全为0，因此第一阶段问题有唯一最优解：结果表明已知问题有可行解，进入第二阶段。先修改第一阶段的最终表，再继续计算：Cj-2-30-2X1210-2-3X21011j00-1因此该问题有唯一最优解：三、关于退化解的说明 在用单纯形法计算时，可能出现以下两种情况：1、 出现若干正检验数大小相同且都是最大。原则上可以任取一个对应的变量为换入变量，但通常会选其中一个下标最小的作为换入变量；2、 出现若干比值大小相同且都是最小。当任取一个对应的变量为换出变量时，则下一张表中有基变量的值等于0，这种现象称为退化。当发生退化现象时，从理论上讲有可能出现计算过程的死循环，始终求不到最优解。为此人们已经提出了三种避免出现死循环的方法，即摄动法、字典序法或最小下标法。然而千千万万例实际应用中从来没遇见过出现死循环的问题，所以在实际计算时一般不必理会此事，可选其中一个下标最小的基变量为换出变量继续计算即可。四、单纯形法小结1、用最终单纯形表判断解的类型例1.11 用单纯形法求解下列问题。解：在图解法中已看到本例有无界解，用单纯形法求解时，先化为标准形式列单纯形表如下Cj230CBBbX1X2X30X316401-j230表中最大的正检验数2=30，但x2的系数为0，使得不能被确定，从而z无限增大。故该问题有无界解。例1.12 用单纯形法求解下列问题。解：在图解法中已看到本例有无穷多最优解，用单纯形法求解时，先化为标准形式列单纯形表如下cj22000CBBbX1X2X3X4X50X3122210060X4164001040X51505001-j220000X34021-1/2012X141001/40-0X515050013j020-1/202X22011/2-1/402X141001/400X5500-5/25/41j00-100表中所有检验数均非正且无人工变量，得到最优解X(1)=(4,2,0,0,5)T,zmax=12,进一步由于非基变量x4的检验数等于0，取x4作为换入变量，继续用单纯形法计算如下：cj22000CBBbX1X2X3X4X52X22011/2-1/40-2X141001/40160X5500-5/25/414j00-1002X2301001/52X13101/20-1/50X4400-214/5j00-100表中所有检验数均非正且无人工变量，得到另一个最优解X(2)=(4,2,0,0,5)T,zmax=12,连接X(1)和X(2)的线段上的点也都是最优解。故此题有无穷多最优解。例1.13 用单纯形法求解下列问题。解：在图解法中已看到本例无可行解，用单纯形法求解时，先化为标准形式列单纯形表如下cj2300-MCBBbX1X2X3X4X50X312221006-MX514120-117j2+M2+2M0-M03X26111/200-MX52-10-1-11j-1-M0-3/2-M-M0表中所有检验数均非正,但人工变量x5不等于0，使得此题无可行解。通过以上各例，我们归纳出利用最终单纯形表判断线性规划问题解的类型的方法如下：解的类型最终表的特征无可行解有非0的人工变量有可行解唯一最优解无非0的人工变量，非基变量的检验数全为负数无穷多最优解无非0的人工变量，非基变量的检验数全非正，且有某个非基变量的检验数为0，同时该变量对应的系数列至少有一个正系数无界解无非0的人工变量，有某个非基变量的检验数为正数，但该变量对应的系数列全为非正数2、能够用单纯形法求解的线性规划问题应首先化为标准形式，并可选择一个单位矩阵作为基，常称之为广义标准形式。针对不同类型的线性规划问题，应如何进行广义标准化，具体方法（以大M法为例）参见表1-，表中xs表示松弛变量，xa表示人工变量：表1-模型决策变量约束条件目标函数特点个 数取 值右 端 项等式或不等式极大或极小新加变量系数两个三个以上xj0xj无约束xj 0 bi 0bi 0计算 最小比值对应的变量xl为换出变量，alk为主元素1xk替换xl2列出新的单纯形表，用矩阵的初等行变换将主元素化为1将主元素列的其它系数化为0第五节 线性规划应用举例学习运筹学的目的在于应用，而应用的第一步就是建立与实际问题对应的数学模型，正如绪论中曾经讲述的。建模时运筹学学习的核心和精髓。将经济管理领域的实际问题抽象为数学模型，这是一项极具创造性和技巧性的工作，既要求能熟练地掌握运用有关的数学知识，又要求对所研究经济对象的本质有深刻的理解，同时还需要相关方面的专业人员的互相配合和通力合作。当然对实际经济问题能给予深刻准确的数学描述以及把数学上的定理算法给予确切合理的经济解释，都不是容易的事情。一般而言，一个经济、管理问题只有满足以下条件时，才能建立对应的线性规划模型。等待求解问题的目标能用某种效益指标度量其大小，即能用数值指标来反映，且为线性函数；.存在着多种可采取的方案；.要求达到的目标是在一定条件下实现的，这些条件可用线性等式或不等式描述。下面举例说明如何将实际问题归结为线性规划问题的数学模型。例1.14（混合配料问题） 某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求、单价和原材料的供应量、单价。该厂应如何安排生产使利润最大？产品名称规格要求单价(元/kg）A原材料C不少于50%原材料H不超过25%50B原材料C不少于25%原材料P不超过50%35D不限25原材料名称每天最多供应量(kg)单价(元/kg)C10065P10025H6035解：用i=1,2,3表示产品A,B,D；用j=1,2,3表示原材料C,P,H；设xij为生产第i种产品中使用的第j种原料的质量(i,j=1,2,3)则该问题的数学模型为：用单纯型法计算得结果:每天生产A产品200kg,分别需要原料:C为100kg;P为50kg;H为50kg. 最大的总利润收入Z=500元/天.例1.15（合理下料问题）现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？解：设变量xj为使用第 j 种方式下料的圆钢根数。下料方式毛坯1234需要根数2.5米32101001.3米0246200余料长度（米）0.50.40.30.2则该问题的数学模型为：用单纯型法计算得结果:注意：若考虑余料最少，则对应模型为：用单纯型法计算得结果:例1.16（投资项目组合问题）兴安公司有一笔30万元的资金，考虑今后三年内用于下列项目的投资：1、三年内每年年初均可投资，每年获利为投资额的20%，其本利可一起用于下一年投资；2、只允许第一年初投入，于第二年末收回，本利合计为投资额的150%,但此类投资限额不超过15万元；3、允许于第二年初投入，于第三年末收回，本利合计为投资额的160%，但限额投资20万元；4、允许于第三年初投入，年末收回，可获利40%，但限额为10万元.试为该公司确立一个使第三年末本利和最大的投资组合方案，请建立这个问题的线性规划模型。解：用xij表示第i年初投放到第j个项目的资金数（注意只有6个决策变量x11,x12,x21,x23,x31,x34），则建立如下线性规划模型：用单纯形法求得：综上投资组合方案如下：方案年初1234116.713.3202031010单位：万元第三年末本利和的最大值=58万元。本章小结本章讨论了线性规划问题的数学模型，介绍了求解含有两个变量的线性规划问题的图解法，详细分析了单纯形法的基本原理及基本步骤，并介绍了单纯形法的进一步讨论，同时对一些实际问题建立了线性规划问题的数学模型。本章的学习重点是单纯形法的步骤，难点是单纯形法的原理及如何就一些简单的实际问题建立线性规划模型。练习题 1.1 把下列线性规划化为标准形式： 1.2求出下列线性规划的所有基解，并指出其中的基可行解和最优解。1.3用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。 1.4判定下列集合是否凸集：（1）R1=(x1,x2)|x12+2x222（2）R2=(x1,x2)|x122x2+30,x20,|x1|1（3）R3=(x1,x2)|x1x21,x11,x201.5用单纯形法求解下列线性规划问题。 1.6用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。 1.7表1-12是一个求极大值线性规划的单纯形表，其中x4，x5，x6是松弛变量。表1-12cj22CBXBbx1x2x3x4x5x62x5x2x12141-12a21-1-1-2-a+8j-1（1）把表中缺少的项目填上适当的数或式子。（2）要使上表成为最优表，