线性规划问题及其数学模型

1、第一章 线性规划问题及其数学模型一、问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。例1 某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。表1-1III该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应如何安排计划设 备原材料A原材料B1402048台时16kg12kg使该工厂获利最多？这问题可以用以下的数学模型来描述，设x1、x2分别表示在计划期内产品I、II的产量。因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品I、II

2、的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：x1+2x28同理，因原材料A、B的限量，可以得到以下不等式4x1164x212该工厂的目标是在不超过所有资源限量的条件下，如何确定产量x1、x2以得到最大的利润。若用z表示利润，这时z=2x1+3x2。综合上述，该计划问题可用数学模型表示为：目标函数 max z=2x1+3x2满足约束条件 x1+2x284x1164x212 x1、x20例2 某铁路制冰厂每年1至4季度必须给冷藏车提供冰各为15，20，25，10kt。已知该厂各季度冰的生产能力及冰的单位成本如表6-26所示。如果生产出来的冰不在当季度使用，每千吨冰存贮一个季度需存贮

3、费4千元。又设该制冰厂每年第3季度末对贮冰库进行清库维修。问应如何安排冰的生产，可使该厂全年生产费用最少？季 度生产能力（kt）单位成本（千元）IIIIIIIV251816155785解：由于每个季度生产出来的冰不一定当季度使用，设xij为第i季度生产的用于第j季度的冰的数量。按照各季度冷藏车对冰的需要量，必须满足： 又每个季度生产的用于当季度和以后各季度的冰的数量不可能超过该季度的生产能力，故又有 第i季度生产用于第j季度的冰的实际成本cij应该是该季度冰的生产成本加上存贮费用。对不可能的用冰方案，例如第一季度生产的冰存贮到第四季度用，其xij=0，cij=M（充分大的正数）。同时注意到这是

4、一个产销不平衡问题，总的生产能力大于总的销量，应该增加一个虚销点，并令cij=0（i=1，2，3，4）。这样就可以把这个问题变成一个产销平衡的运输问题模型，如表6-27所示。表6-27销地产地IIIIIIIV虚销点产量IIIIIIIV5 x11M x21M x319 x410 x120 x220 x320 x420 x130 x230 x330 x43M x14M x24M x245 x440 x150 x250 x850 x4525181615销量152025104从以上两例可以看出，它们都是属于一类优化问题。它们的共同特征：（1）每一个问题都用一组决策变量（x1，x2，xn）表示某一方案；

5、这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。（2）存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。（3）都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划的数学模型。满足约束条件： （1.1）、（1.2）称为约束条件。二、线性规划的数学模型线性规划的数学模型可一般表示为 其中，（1.3.1）为目标函数，（1.3.2）和（1.3.3）为约束条件，（1.3.3）为非负条件。上述数学模型，也可借助于求和符号写成如下的“压缩”形式： 若引用下述记号：C=（c

6、1，c2，cn）=（A1，A2，An）则可将线性规划的数学模型写成矩阵形式如下： 其中，0为n维零向量。在上述各式中，cj（j=1，2，n）称为价值系数，aij（i=1，2，m；j=1，2，n）为约束条件的系数，bi（i=1，2，m）为约束条件的右侧常数，xj（j=1，2，n）为未知数（变量），C为价值系数（行）向量，b为限定向量，X为未知数向量，A为约束条件的系数矩阵，Aj（j=1，2，n）为约束条件的系数列向量。三、线性规划问题的标准型式由前节可知，线性规划问题有各种不同的形式。目标函数有的要求max，有的要求min；约束条件可以是“”，也可以是“”形式的不等式，还可以是等式。决策变量一般

7、是非负约束，但也允许在（）范围内取值，即无约束。将这种多种形式的数学模型统一变换为标准形式。这里规定的标准型式为：max z = c1x1+c2x2+cnxn简写为max z = 在标准型式中规定各约束条件的右端项bi0，否则等式两端乘以“1”。用向量和矩阵符号表述时为：max z =CX 其中：C=（c1,c2cn）； ； ；向量pj对应的决策变量是xi。用矩阵描述时为：max z =CXAX=bX0其中 称A为约束条件的m×n维系数矩阵，一般mn；m，n0；b为资源向量；C为价值向量；X为决策变量向量。实际碰到各种线性规划问题的数学模型都应变换为标准型式后求解。以下讨论如何化标准

8、型的问题。（1）若要求目标函数实现最小化，即min z =CX。这时只需将目标函数数量小化变换求目标函数最大化，即令，于是得到max 。这就同标准型的目标函数的形式一致了。（2）约束方程为不等式。这里有两种情况：一种是约束方程为不等式，则可在不等式的左端加入非负松弛变量，把原不等式变为等式；另一种是约束方程为不等式，则可在不等式的左端减去一个非负剩余变量（也可称松弛变量），把不等式约束条件变为等式约束条件。下面举例说明。例3 将例1的数学模型化为标准型。例1的数学模型为（简称模型M2）模型M2max z =2x1+3x2在各不等式中分别加上一个松弛变量x3，x4，x5，使不等式变为等式。这时得

9、到标准型：max z =2x1+3x2+0x3+0x4+0x5所加松弛变量x3、x4、x5表示没有被利用的资源。当然也没有利润，在目标函数中其系数应为零；即c3，c4，c5=0。（3）若存在取值无约束的变量xk，可令，其中，0。以上讨论说明，任何形式的数学模型都可化为标准型，下面举例说明。例4 将下述线性规划问题化为标准型x1+x2+x37x1x2+x323x1+x2+2x3=5 x1，x20，x3为无约束解：步骤为：1用x1x5替换x3，其中x4，x50；2在第一个约束不等式号的左端加入松弛变量x6；3在第二个约束不等式号的左端减去剩余变量x7；4令，把求min z 改为求max ；即可得到

10、该问题的标准型max = x12x2+3（x4x5）+0x6+0x1x1+x2+(x4x5)+ x6 =7x1x2+(x4x5) x7 =23x1+x2+2（x4x5）=5x1，x2，x4，x5，x6，x7 2四、图解法图解法简单直观，有助于了解线性规划问题求解的基本原理。现对上述例1进行图解。在以x1、x2为坐标轴的直角坐标系中，非负条件x1，x20是指第一象限。例1的每个约束条件都代表一个半平面。如约束条件x1+2x28是代表以直线x1+2x2=8为边界的左下方的半平面，若同时满足x1，x20，x1+2x28，4x116和4x212的约束条件的点，必然落在由这三个半平面交成的区域内。由例1

11、的所有约束条件为半平面交成的区域见图1-2中的阴影部分。阴影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是例1的线性规划问题的解集合，称它为可行域。再分析目标函数z =2x1+3x2，在这坐标平面上，它可表示以z为参数、2/3为斜率的一族平行线：x2=(2/3)x1+z/3位于同一直线上的点，具有相同的目标函数值，因而称它为“等值线”。当z值由小变大时，直线x2=(2/3)x1+z/3沿其法线方向向右上方移动。当移动到Q2点时，使z值在可行域边界上实现最大化（见图1-3），这就得到了例1的最优解Q2，Q2点的坐标为（4，2）。于是可计算出z =14。这说明该厂

12、的最优生产计划方案是：生产产品I 4件，生产产品II 2件，可得最大利润为14元。上例中求解得到2到的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：图1-3（1）无穷多最优解（多重解）。若将例1中的目标函数变为求max z=2x1+4x2，则表示目标函数中以参数z的这族平行直线与约束条件x1+2x28的边界线平行。当z值由小变大时，将与线段Q2Q3重合（见图1-4）。线段Q2Q3上任意一点都使z取得相同的最大值，这个线性规划问题有无穷多最优解（多重解）。（2）无界解。对下述线性规划问题max z = x1+x22x1+x24x1x22x1，x20用图解法求解结果见图1-5，从图中可以看到，该问题可行域无界，目标函数值可以增大到无穷大。称这种情况为无界解或无最优解。0 （3）无可行解。如果在例1的数学模型中增加一个约束条件2x1+x24