合肥工业大学系统工程导论数学规划基础.doc

第3章 数学规划基础系统工程的主要目标是改造或建立系统，使系统的整体功能达到最优。而作为系统科学的技术基础之一的运筹学，就是从系统总体的角度寻求系统最优解的数学工具，它包括数学规划（第3章）、图与网络（第4章）、决策分析（第6章）等。本章着重介绍数学规划的基本概念以及相关算法。所谓数学规划，是指系统在一定约束条件下使某一评价目标达到最优（极值）的一种决策方法。数学规划的关键是从系统思想出发，在定性分析的基础上建立其数学模型。数学规划模型的一般形式为：系统在满足条件 （1）的情况下，使评价目标达到最优（最大或最小值），即 （2）其中，式（1）是系统必须满足的限制条件的数学描述，通常由等式或不等式组成，称为约束条件，简记为s.t.（subject to，意为“受的限制”）；式（2）是系统评价目标的数学描述，称为目标函数。由于不同系统的目标函数和约束条件存在差异，则数学规划可以分为线性规划、非线性规划和动态规划等。下面我们主要介绍各数学规划模型的建立、求解及其结果分析方法。一、 线性规划所谓线性规划，是指约束条件和目标函数均为线性的数学规划方法。根据系统评价目标是单个还是多个，可将线性规划分为单目标线性规划和多目标线性规划。（一）单目标线性规划1. 问题的提出在生产管理和经营活动中经常提出一类问题，即如何充分合理地利用有限的人力、物力、财力等资源，以便获得最佳的经济效益。例1（生产管理问题） 某工厂计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问如何安排生产计划才能使工厂获利最多？产品产品限制设备（台时/件）128台时原材料A（kg /件）4016kg原材料B（kg /件）0412kg利润（元/件）23解 上述所谓的“安排生产计划”问题，其实质就是要寻求一个满足设备和原材料资源约束的可行的生产方案，以确保工厂能获得最大的利润值。假设产品、的产量分别为x1、x2，则该工厂的获利值f = 2 x1 + 3 x2。由于可行的生产方案需要考虑不能超出设备的有效台时数限制，即x1+2 x28；同时，还要考虑满足A、B原材料资源的约束条件，即4x116，4x212。因此，工厂的目标是在满足设备和原材料资源限制的条件下，如何确定两种产品的产量x1、x2，使工厂的获利最大。综上所述，上述安排生产计划问题的数学模型为目标 满足约束条件（s.t.）由此可见，将这类实际问题转换为数学模型的基本步骤可归纳如下：（1） 确定决策变量；决策变量必须是可控制的且常用x1, x2, , xn表示，如例1中产品、的产量。（2） 确定所要追求的目标（目的）；目标通常用决策变量的函数来表达，称为目标函数。目标可以是单一或多个的，这里着重讨论目标单一的情形，如例1中工厂的最大获利。（3） 确定约束条件；将现实中的各种限制用含有决策变量的数学关系式（等式或不等式）来表达，称为约束条件，如例1中设备和原材料资源的限制。例2（环保问题） 靠近某河流有两个化工厂，流经工厂1的河水流量是5106m3/天，在两个工厂之间有一条流量为2106m3/天的支流，如图所示。工厂1每天排放工业污水2104m3，工厂2每天排放工业污水1.4104m3。从工厂1排出的污水流到工厂2之前，有20%可自然净化。根据环保要求，河流中工业污水的含量不应超过0.2%。若这两个工厂都各自处理一部分污水，工厂1处理污水的成本是1000元/104m3，工厂2处理污水的成本是800元/104m3，试问在满足环保要求的条件下，各工厂应分别处理多少污水，才能使两个工厂处理污水的总费用最小？解 假设工厂1和工厂2每天处理污水量分别为x1104m3、x2104m3，则两个工厂处理污水的总费用f = 1000x1 + 800 x2。根据环保要求，从工厂1到工厂2之间的河流中污水含量不超过0.2%，则可得由于从工厂1排出的污水流到工厂2之前有20%会自然净化，且流经工厂2后河流中污水含量仍要不超过0.2%，故有此外，各工厂每天的污水处理量不应超过其污水排放量，则有x12，x21.4。因此，问题的目标是要求两个工厂处理污水的总费用最小。综上所述，上述环保问题的数学模型为目标 满足约束条件（s.t.）2. 数学模型的建立通过上述例题可知，应用单目标线性规划来解决实际的最优化问题时，必须符合以下特征（参见P34）： （1） 所求问题都有一个目标要求，且相应的目标函数可以用最大或最小值的形式来表达；（2） 要达到最优目标，必须有多种方案可供选择；注意：每一组决策变量（x1, x2, , xn）的取值就是一个具体方案。（3） 所寻求的目标必然有条件约束；（4） 目标函数和约束条件都是线性方程式，且决策变量具有非负性。因此，单目标线性规划问题的数学模型可归纳如下：目标函数 满足约束条件（s.t.） 其中，aij, bi, cj为已知常数。3. 数学模型的标准化由于在单目标线性规划问题中，其目标函数的实现可能要求最大化或最小化，约束条件又可能是等式或“/”形式的不等式，这种多样性给问题的研究带来很大的不便。为此，我们将单目标线性规划的数学模型规定为以下标准形式：（1） 目标函数是求最大值当目标函数是求最小值时，即由于令f = - f，可得（2） 约束条件均用线性等式方程来表示，且右边常数项均为非负值显然，实际的约束条件不可能都是等式关系。当表达式中含“”时，可在约束条件左边加上一个非负的变量松弛变量，使原来的“”变为“=”；当表达式中含“”时，可在约束条件左边减去一个非负的变量剩余变量，使原来的“”变为“=”。另外，在标准型中要求约束条件右边的常数项bi0，若存在bi0，则目前的基本可行解不是最优解。特别要指出的是，若存在某个m+k = 0，而其它任何j0，且A的列向量Pm+k中的所有元素均不大于0，则线性规划问题无最优解。（2） 基本思路单纯形法的基本思路是：根据线性规划问题的标准型，从可行域中的一个顶点（基可行解）开始，转换到另一个顶点（基可行解），并且使目标函数的值逐步增大。当目标函数达到最大值时，就得到了问题的最优解。下面以例1的生产管理问题为例，说明单纯形法逐步迭代寻优的原理和思路。该问题的数学标准型为 （1）第一轮：约束方程系数矩阵显然是线性独立的，这些列向量构成一个初始可行基B对应于初始可行基B，x3、x4和x5为初始基变量，x1和x2为非基变量。由方程组（1）可得 （2）令非基变量x1、x2为零，得到初始的基可行解为将方程组（2）代入目标函数，得 （3）将初始的基本可行解代入式（3），得f (0) =0。这个基本可行解表示：工厂没有安排生产产品、；设备的有效台时和原材料A、B没有被利用，所以工厂的利润指标f (0) =0。从式（3）目标函数可以看到，x1、x2（即没有安排生产的产品，）的系数都是正数，显然将非基变量换成基变量，目标函数的值就可能增大。从经济意义上讲，安排生产产品或就可以使工厂的利润指标增加，所以只要式（3）目标函数中还存在有正系数的非基变量，则目标函数值（利润）还有增加的可能，就需要将非基变量与基变量进行对换。一般选择正系数最大的那个非基变量x2为换入变量（即引入变量），将它换入到基变量中去，同时还要确定基变量中有一个要换出来成为非基变量。可按下列方法来确定换出变量（即退出变量）。现在分析方程组（2），当将x2定为换入变量后，必须要从x3、x4和x5中换出一个，并要保证其余的都是非负，即x3，x4，x50。当x1=0时，由方程组（2）可得 （4）从方程组（4）可见，只有选择x2 = min8/2，-，12/4=3时，才能使式（4）成立。当x2=3时，x5=0，这就决定了x5为换出变量，用x2去替换x5。以上数学描述说明：每生产一件产品，需要用掉设备台时及原材料为（2，0，4）。这些资源能力中的薄弱环节就确定了产品的产量，也就是由原料B的生产能力，确定了产品的产量x2=12/4=3件。第二轮：x2与x5互换，即x2为基变量，x5为非基变量。则互换后，x3、x4和x2为基变量，x1和x5为非基变量。为了求得新的基可行解，并将目标函数f用非基变量x1、x5表示，以判别所求的基可行解是否为最优解，则需要用高斯消元法，将方程组（2）中第一个方程的x2消去，将第三个方程的x2移至左边，并将系数化为1，于是有 （5）令非基变量x1、x5为零，得基可行解为将方程组（5）代入目标函数中，得 （6）将x1=0，x5=0代入方程组（6），可得目前基可行解的目标值为9。由式（6）可知，非基变量x1的系数大于0，则目前的基可行解不是最优解，x1应为换入变量。在方程组（5）中，用各方程负的x1的系数（如果x1在方程的左边，则用正的x1系数）去除对应的常数项，选最小者，即x1 = min2/1，16/4，-=2于是，方程组（5）中的第一个方程对应的原基变量x3为换出变量。第三轮：x1与x3互换，则互换后，x1、x4和x2为基变量，x3和x5为非基变量。将方程组（5）进行初等变换，使得由基变量x1、x4和x2所构成的基为单位矩阵，即 （7）令非基变量x3、x5为零，得基可行解将方程组（7）代入目标函数中，得 （8）由式（8）可知，非基变量x5的系数大于0，则目前的基可行解不是最优解，x5为换入变量，因为min-，8/2，3/(1/4)=4，故取x4为换出变量。第四轮：x5与x4互换，则互换后，x1、x5和x2为基变量，x3和x4为非基变量。用高斯消元法对方程组（7）进行初等变换，使得每个约束方程中只含有一个基变量且基变量的系数为1，即 （9）令非基变量x3、x4为零，得基可行解为将方程组（9）代入目标函数中，得 （10）由式（10）可见，x3与x4的系数均为负数，说明若想使用剩余的设备台时和原材料A，就必须支付附加费用。所以当x3 = x4 =0时，即不再利用这些设备能力和原材料时，目标函数达到最大fmax =14，于是基可行解为最优解。（3） 单纯形表 为了便于以单纯形法求解线性规划问题，人们在上述讨论的基础上，专门设计了一种计算表格单纯形表，用单纯形表的变换来代替约束方程组中系数矩阵的变换过程，并使单纯形法的计算步骤规范化，从而有利于求解更复杂的线性规划问题。对于标准化的线性规划模型式中，x1，x2，xm为基变量，且对应的基为B = I（mm阶单位阵）。所设计的初始单纯形表如表1所示。表1 初始单纯形表Cc1cmcm+1cniCBXBbx1xmxm+1xnc1x1b110a1, m+1a1n1c2x2b200a2, m+1a2n2cmxmbm01am, m+1amnm00j表中，XB列中填入基变量，这里是x1，x2，xm；CB列中填入基变量的价值系数，这里是c1，c2，cm，它们随基变量改变而改变，并与基变量相对应；b列中填入约束方程组右端的常数；X行填入决策变量名；在X行上面的C行，相应填入各决策变量的价值系数；最后一行是检验数行，对应各非基变量xj的检验数是i列的数字是在确定换入变量后，按规则计算后填入表中的。单纯形表要求初始可行基B=I，这时可以从表上直接得到基可行解，即且该基可行解的目标值为。单纯形法就是以上述形式的初始单纯形表为起点进行迭代，每迭代一次后，得到使新的基B=I的另一个单纯形表；从表上得到新的基可行解和目标值，并进行最优判别，直到找到最优解为止。（4） 单纯形法小结下面将单纯形法的计算步骤归纳如下：第一步，建立线性规划的数学模型，并使其标准化。标准化的要求为： 目标函数化成求最大值问题； 约束条件均表达为等式关系（必要时引入松弛变量和剩余变量）； 模型存在一个初始可行基单位矩阵（必要时引入人工变量）。第二步，建立初始单纯形表，如表1所示。第三步，检验各非基变量xj的检验数若所有j0（j = m+1，n），则已得到最优解，可停止计算，否则转入下一步。第四步，在j 0，j = m+1，n中，若有某个k 0对应的xk的系数列向量Pk 0，则此问题无最优解，停止计算，否则转入下一步。第五步，根据maxj 0=k ，在单纯形表中k所在的列为主元列（即关键列），主元列所对应的变量xk为换入变量（入基变量）。再根据规则计算，有i = bi /aik（aik 0，i =1，2，m），l = min(i) = bl /alk，确定l所在的行为主元行（即关键行），主元行在单纯形表中所对应的基变量xl为换出变量（出基变量）。主元行与主元列相交的元素alk为主元素（即关键元素），用方括号 标明，转入下一步。第六步，以alk为主元素，用高斯消元法进行约束方程组的初等变换，将主元列中主元素alk变为1，其它元素变为0，即把xk所对应的列向量将XB列中的xl转换为xk，CB列中的cl换成ck ，得到新的单纯形表。重复第三步第六步，直到算法终止。例6 用单纯形法计算例1（生产管理问题）的最优解。解 第一步，将模型标准化后，即为模型中已存在一个初始可行基，对应的基变量为x3、x4和x5，则令非基变量x1、x2为零，可得初始基可行解为且相应的目标函数值f (0) =0。第二步，将有关内容填入表中，得到如表2所示的初始单纯形表。表2 初始单纯形表cj23000iCBXBbx1x2x3x4x50x381210040x416400100x512040013j23000第三步，计算各非基变量的检验数，1 =2，2 =3，故存在j 0，目前的解不是最优解，转入下一步。第四步，P1，P2均有正分量存在，转入下一步。第五步，经比较maxj 0=2，确定x2为换入变量，x2所在列为主元列；计算1 =8/2=4，3=12/4=3，取最小值者为3，于是3所在的行为主元行，主元行所对应的基变量x5为换出变量，主元行与主元列相交的元素4为主元素。第六步，以4为主元素，用高斯消元法进行初等行变换，使对应主元列的列向量P2变换为0 0 1T，在XB列中将x5替换为x2，于是得到表3。表3 x5替换为x2后的单纯形表cj23000iCBXBbx1x2x3x4x50x321010-1/220x4164001043x2301001/4j2000-3/4这样，得到新的基本可行解且相应的目标函数值f (1) =9。第七步，重复第三步第六步的计算步骤，由于表3中检验数1 =20，则目前的解不是最优解。同理可以确定x1为换入变量，x3为换出变量，于是得到表4。表4 x3替换为x1后的单纯形表cj23000iCBXBbx1x2x3x4x52x121010-1/20x4800-41243x2301001/412j00-201/4则其新的基本可行解且相应的目标函数值f (2) =13。第八步，再次重复第三步第六步的计算步骤，由于表4中检验数5 =1/40，则目前的解还不是最优解。同理可以确定x5为换入变量，x4为换出变量，于是得到表5。表5 x4替换为x5后的单纯形表（最优单纯形表）cj23000iCBXBbx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80j00-3/2-1/80第九步，表5最后一行的所有检验数j都已为负或零，这表示目标函数值已不可能再增大，于是得到最优解且相应的最优值（即工厂的最大获利）f *= f (3) =14。6. 对偶问题在线性规划问题中，任何一个求最大值的规划问题必有一个求最小值的规划问题与之相对应，二者含有相同的数据，且它们的解也有密切联系，反之亦然。若两个问题中，其中一个称为原问题，则另一个就称为对偶问题。（1） 对偶问题的关系已知下列两个线性规划问题、是互为对偶的，其中问题： 问题： 不难发现，互为对偶的两个问题之间具有以下关系： 一个问题目标函数的系数是另一个问题约束条件右端的常数； 一个问题第i个约束条件的各系数是另一个问题第i个变量的约束条件系数； 一个问题是求目标函数的最大值，其约束条件均为“”形式，而另一个问题则是求目标函数的最小值，其约束条件均为“”形式； 两个问题的变量均是非负的。（2） 对偶问题的转化已知一个线性规划问题，在实际应用中通常可以根据具体情况将原问题转化为对偶问题，其具体方法如下：如果目标函数是求最大值，首先应将约束条件全部转化为“”形式，即 原约束条件为“”形式时，则可在该不等式两边同乘以-1，使其变为“”形式； 原约束条件为等式时，则可将该式再将“”形式转化为“”形式； 原问题中有自由变量时，则可用两个非负变量相减来代替，如xi为自由变量，令xi = xi - xi且xi 、xi0。然后，再根据对偶问题的关系进行转化。同理，如果目标函数是求最小值，则应先将约束条件全部转化为“”形式，然后再转化为相应的对偶问题。例7 试写出下列线性规划问题的对偶问题解 令x1 = x1 - x1且x1 、x1 0，并将第四个约束条件转化为两个不等式，则原问题可改写为由原问题与对偶问题的关系可得，相应的对偶问题为（3） 对偶问题最优解的关系互为对偶的两个问题最优解之间的关系为： 求最小问题的任意可行解对应的目标函数值都不小于求最大问题的最优目标函数值，而求最大问题的任意可行解的目标函数值都不大于求最小问题的最优目标函数值； 如果一个线性规划问题有最优解，则其对偶问题也一定有最优解，且两个问题的最优目标函数值相等； 最大值问题的原变量xj的值等于最小值对偶问题的第j个剩余变量的检验数。（参见P44例3.6）由上述关系可知，如果一个线性规划问题比较复杂，而其对偶问题比较简单时，则可通过求解对偶问题而得到原问题的最优解，这样就为求解线性规划问题提供了方便。（二）多目标线性规划通常，在实际情况下，希望得到的某个行动方案并不像前面介绍的单目标规划那样，只是使一个目标函数达到最优值，而是希望该方案尽可能同时接近几个预定的目标值，这种数学方法就称为多目标规划法，简称目标规划。目标规划是由Charnes和Cooper于1961年首次提出的。这里，着重介绍线性目标规划的有关问题。1. 问题的提出在实际问题中，常需要研究在某些限制条件下，同时考虑多个目标的最优化问题。例如，人们在购买一件衣服时，往往需要考虑质量、颜色、式样、大小、价格这五个目标；又如在选择一个新厂址时，除了要考虑运费、造价、燃料供应费等经济指标以外，还要考虑对环境影响等社会因素；再如在设计货船时，通常要考虑选取使船舶的试航速率最大，年货运量最多和运输成本最低等多个目标都尽可能好的方案。例8（投资决策问题） 某投资开发公司拥有总资金A万元，今有n（n2）个投资项目可供选择。设投资第i（i = 1, 2, , n）个项目需用资金ai万元，预计可获利bi万元，试问应如何决策投资方案？解 一个好的投资方案应该是投资少，收益大的方案。设投资决策变量由题意可知，投资第i（i = 1, 2, , n）个项目需用资金aixi万元，则为了使总投资金额尽可能地少，即有同时，投资第i（i = 1, 2, , n）个项目预计可获利bixi万元，则为了使获得的收益最大，又应要求此外，由于该公司的总资金为A万元，故有限制条件而投资决策变量xi只能取1或0，即满足综上所述，所考虑的投资决策问题可归纳为以下具有两个目标的最优化问题：通过上例可见，目标规划与前面介绍的单目标规划类似，由实际问题建立目标规划的数学模型时，同样也需要确定决策变量、目标函数以及约束条件，只是这里的目标有多个。2. 数学模型的建立由于决策者对不同目标的偏爱程度不同，导致对不同目标逼近其目标值的要求程度也不同，所以为了体现决策者的这一偏爱关系，在建立目标规划数学模型的过程中，应根据具体情况引入不同的优先级因子。因此，建立目标规划模型的基本思路是：（参见P45）（1） 确定决策定量xj，选择约束条件和各个目标函数，构造出多目标的线性规划；（2） 根据决策者的意图，对各个目标函数确定相应的目标值，并在这些目标函数方程中加入偏离系数di- 、di+，组成一组新的约束条件；（3） 用这些偏离系数产生目标规划的目标函数F，再根据各目标的轻重缓急赋予不同优先级别的权因子i，使目标规划的目标函数达到最小。目标规划数学模型的一般形式为：式中，i为决策者根据具体情况选定的各目标优先级的权因子；di- 、di+分别表示未达到目标或超过目标的偏离系数，且对于任何目标都只能取二者之一，故有di- di+=0条件成立。例9（生产管理问题） 某工厂生产甲、乙两种产品，已知产品生产的有关数据如表所示，试求获利最大的生产方案。数据甲乙拥有量原材料（kg/件）2111 kg设备（台时/件）1210台时利润f（元/件）810解 这是个单目标线性规划问题，设甲、乙产品的产量分别为x1、x2，则其数学模型为用单纯形法求得最优决策方案为：x1*= 4，x2*= 3， f *= 62元。但实际上工厂在作决策时，还要考虑市场等一系列其它条件，譬如 严格限制原材料供应； 产品乙的产量不低于产品甲的产量； 充分利用设备的有效台时，但不希望加班； 利润额不小于56元。同时希望将作为第一优先目标，将作为第二优先目标，将作为第三优先目标。先对条件，可引入偏离系数变量d1+、d1-，建立目标约束x2-x1-d1+d1-=0，并使1d1-min；再对条件，可引入偏离系数变量d2+、d2-，建立目标约束x1+2x2-d2+d2-=10，并使2(d2+d2-)min；最后对条件，可引入偏离系数变量d3+、d3-，建立目标约束8x1+10x2-d3+d3-=56，并使3d3-min。因此，建立相应的目标规划数学模型为由此可见，在建立目标规划数学模型时，需要确定目标值、优先次序以及相应的权系数等，它们都具有一定的主观性和模糊性，可以通过组织专家进行评估给以量化。3. 图解法对于只具有两个决策变量的目标规划数学模型，可以用图解法来分析求解。用例9来说明具体的求解过程。例10 用图解法求解例9的生产管理问题。解 （1）在平面直角坐标系中，做出约束条件所确定的区域，如图所示 先画出绝对约束条件1（画法同线性规划图解法），即三角形区域OAB； 再画出目标约束条件24。先令di-=di+ =0，做出相应直线；然后在直线旁标上di-、di+，表明目标约束可沿着di-、di+所示方向平移（平移方向是使di+或di- 增加的方向）。（2）根据目标函数中的优先因子来分析求解 先考虑第一优先因子1，即要求实现min d1-。由图可见，可以满足d1-=0，这时，x1、x2的取值范围只能在三角形OBC上； 再考虑第二优先因子2，即要求实现min(d2+d2-)。当d2+= d2-=0时，x1、x2可在线段ED上取值； 最后考虑第三优先因子3，即要求实现mind3-。从图中可以看到，要使d3-=0，x1、x2只能在多边形BCJF取值；因此，线段GD上的点即为该目标规划的最优解（有效解）。4. （分层）单纯形法目标规划与线性规划的数学模型没有本质区别，因而也可以用单纯形法求解，但考虑到目标规划的某些特点，做出以下规定：（1）由于目标规划问题的目标函数均为求最小值，故以检验数j0（j = 1, 2, , n）为最优准则；（2）由于目标规划的检验系数矩阵=1 2 n=C-CBA，所以各检验数j中含有不同优先级的权因子k ，即当权因子12M时，从各检验数的整体来看，各检验数的正负首先决定于1的系数1 j的正负；若1 j =0，则检验数的正负就取决于2的系数2 j的正负；以此类推。注意：在目标规划的（分层）单纯形法中，其基变量的检验数同样为零向量。求解目标规划问题的（分层）单纯形法计算步骤为：（1）建立初始单纯形表，在表中将检验数行按优先因子个数分别列成M行，令k=1；（2）检查该检验数行中是否存在负数，且对应的前k-1行的系数是零。若有负数，则取其中最小者对应的变量为换入变量，并转至（3）；若无负数，则转至（5）；（3）按线性规划单纯形法确定主元行、主元素和换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高优先层次的基变量为换出变量；（4）按单纯形法进行基变换运算，建立新的计算表，并返回（2）；（5）当k = M时，计算结束，表中的解即为最优解，否则令k = k+1，并返回（2）。例11 某电视机厂装配黑白和彩色电视机，每装配一台电视机需占用装配线1h，装配线每周计划开动40h。预计市场每周彩色电视机的销量为24台，每台可获利80元，黑白电视机的销量为30台，每台可获利40元，该厂确定的目标是：（1）首先，充分利用装配线每周计划开动的40h；（2）其次，允许装配线加班，但加班时间每周尽量不超过10h；（3）再次，装配电视机的数量尽量满足市场需求。因彩电的利润高，取其权系数为2。试建立该问题目标规划的数学模型，并求解彩色电视机和黑白电视机每周的产量。解 设彩色电视机和黑白电视机每周的产量分别为x1、x2，则该问题目标规划的数学模型为方法一：（思考题）用图解法求解，如图所示 由图可见，在考虑具有1、2的目标实现后，x1、x2的取值范围为ABCD。考虑具有3的目标要求时，因d3-的权系数大于d4-，故先取d3-=0，这时x1、x2的取值范围为ABEF。在ABEF区域中只有E点使d4-取值最小，因此，E点即为最优解，其坐标为（24，26），即该厂每周应装配彩色电视机24台，黑白电视机26台。方法二：用单纯形法求解（1）取d1-、d2-、d3- 和d4- 为初始基变量，列出初始单纯形表，如表1所示表1 初始单纯形表cj00100223030iCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+1d1-40111-1000000400d2-5011001-100005023d3-241000001-100243d4-30010000001-1j1-1-101000000200000100003-2-100000201（2）检查检验数j的1行，有两个同为-1的负数，则取变量x1为换入变量；（3）在表1中计算1 = min(bi /ai1) | ai1 0= min40/1, 50/1, 24/1=24，将该最小比值对应的基变量d3- 作为换出变量；（4）进行基变换运算，可得表2，并返回（2）。依此类推，直至得到最优单纯形表为止，如表4所示；表2 第一次迭代后单纯形表cj00100223030iCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+1d1-16011-100-1100160d2-2601001-1-1100260x1241000001-1003d4-30010000001-130j10-101001-1002000001000030-100002001表3 第二次迭代后单纯形表cj00100223030iCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x216011-100-11000d2-1000-111-10000100x1241000001-1003d4-1400-11001-11-114j10010000000200000100003001-1001101注意：如果检验数j的某行中存在有一个负数，便要看同列中优先级高的权因子的检验数j是否为正数，若是正数，即可得最优解；否则就不是最优解。表4 最优单纯形表cj00100223030iCBXBbx1x2d1-d1+d2-d2+d3-d3+d4-d4+0x22601001-1-11000d1+1000-111-100000x1241000001-1003d4-40000-111-11-1j1001000000020000010000300001-11101表4所示的解x1*= 24，x2*= 26即为该目标规划问题的最优解。（三）整数规划1. 问题的提出在前面讨论的线性规划问题中，决策变量的取值可能是非负的整数或小数。但在某些实际问题中，决策变量只有取整数才有意义，如生产或配备的机器台数、完成工作需要的人数等。此时，若得到的解为小数，就不符合要求。表面上看，似乎只要把所得到的小数解经过“四舍五入”，就可得到问题的整数解。但这往往是行不通的，因为化整后的解不一定是可行解，或者即使是可行解，也不一定是最优解。因此，对于这类问题有必要另行研究。通常，把有决策变量限制为整数的规划问题称为整数规划。在整数规划中，若所有变量都限制为整数，则称为纯整数规划；若仅有一部分变量限制为整数，则称为混合整数规划。在纯整数规划中，若所有变量的取值都仅限于0或1，则称为0-1规划。例12（生产计划问题） 某工厂生产A1、A2两种产品，产品分别由B1、B2两种部件组装而成，每件产品所用部件的数量和部件的最大限额，以及产品的利润如表所示。试问如何安排产品A1、A2的产量，工厂才能获得最大利润？部件产品B1B2利润A16115A24320部件最大限额2510解 设产品A1和A2的产量分别为x1、x2。由题意可建立数学模型如下：可见，这是一个纯整数规划问题。2. 分枝定界法在求解整数规划时，首先容易想到的方法就是穷举列出变量的所有可行的整数组合，然后比较它们的目标函数值以确定最优解。对于小规模问题，该方法是可行且有效的；而对于大规模问题，由于可行的整数组合数很大，不可能采用穷举法。因此，一般采取的方法是仅检查一部分可行的整数组合，以确定其最优的整数解。分枝定界法就是这样的一种方法。分枝定界法是以求相应的线性规划问题的最优解为出发点，如果这个解不符合整数条件，就将原问题分为几个部分，每部分都增加了决策变量为整数的约束条件，这样就缩小了原线性规划问题的可行域。考虑到整数规划的最优解不会更优于线性规划的最优解，对于求最大值问题来说，相应的线性规划目标函数的最大值就成为整数规划目标函数值的上界。分枝定界法就是利用这种性质来进行求解。分枝定界法的计算步骤为：（1）求解整数规划对应的线性规划问题，若线性规划问题无可行解，则相应的整数规划也无可行解；若线性规划问题有最优解，且满足整数约束条件，则此最优解就是整数规划的最优解，否则转至（2）；（2）在线性规划问题的求解中，任选一个不符合整数条件的变量x j，如x j = b j作两个后继分枝，它们是对线性规划问题分别增加约束条件：（其中，INT(b j)表示对b j取整） x j INT(b j) 或 x j INT(b j) + 1（3）对各个后继分枝再采用步骤（1）和（2），直到求出原整数规划的最优解为止。例13 用分枝定界法求解例12的生产计划问题。解