第一章_线性规划

《第一章_线性规划》由会员分享，可在线阅读，更多相关《第一章_线性规划（80页珍藏版）》请在金锄头文库上搜索。

1、党耀国 ,运筹学,第一章 线性规划 线性规划是运筹学的一个重要分枝。自1947年美国数学家丹捷格（G.B.Dantzig）提出了求解线性规划问题的方法单纯形法之后，线性规划在理论上趋于成熟，在实际中的应用日益广泛与深入。特别是在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更加广泛。从解决技术问题中的最优化设计到工业、农业、商业、交通运输业、军事、经济计划与管理、决策等各个领域均可发挥重要作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛、计算技术比较简单的特点，是现代管理科学

2、的重要基础和手段之一。,第 一 节 线性规划问题及其数学模型一、线性规划问题的数学模型线性规划问题主要解决以下两类问题： 1、任务确定后，如何统筹安排，做到应用尽量少的人力和物力资源来完成任务； 2、在一定量的人力、物力资源的条件下，如何安排、使用他们，使完成的任务最多。在生产管理和经济活动中，经常会遇到线性规划问题，如何利用线性规划的方法来进行分析，下面举例来加以说明。,例11：（计划安排问题）某工厂在计划期内安排生产、两种产品，已知生产单位产品所占用的设备A、B的台时、原材料的消耗及两种产品每件可获利润见表所示：,问如何安排计划使该工厂获利最多？,解: 假设 x1、x2分别表示在计划期内生

3、产 产品I、II的件数，因为设备A的有效台 时是15，所以在确定产品I、II的产量时，可用不等式表示为：同理，因设备B的限制，有不等式：原材料的限制，有不等式： 若用Z表示利润，则该工厂的利润值：Z = 2x1 +3x2（元）,综上所述，该工厂的计划问题可用如下 数学模型表示为：目标函数： Max Z = 2x1 +3x2约束条件：,例12 (成本问题)某炼油厂根据每季度需供应给合同单位汽油15万吨、煤油12万吨、重油12万吨。该厂计划从A，B两处运回原油提炼，已知两处的原油成分含量见表12；又已知从A处采购的原油价格为每吨（包括运费）200元，B处采购的原油价格为每吨（包括运费）290元,

4、问：该炼油厂该如何从A，B两处采购原油，在满足供应合同的条件下，使购买成本最小。表12,产品来源,成分,分析：很明显，该厂可以有多种不同的方案从A，B两处采购原油，但最优方案应是使购买成本最小的一个，即在满足供应合同单位的前提下，使成本最小的一个采购方案。 解：设分别表示从A，B两处采购的原油量（单位：万吨），建立的数学模型为：,以上两个例子，从数学上来讲，我们会发现此数学模型具有如下特点： (1)有一组非负的决策变量(decision or control variable)； (2)有一组约束条件：含有决策变量的线性不等式(或等式)组(linear function constraints

5、)；(3)有一个含有决策变量的线性目标函数(objective linear function)，按研究问题的不同，要求目标函数实现最大化或最小化。 我们把满足上述三个条件的数学模型称为线性规划的数学模型。其一般形式如下：,在该数学模型中，方程(1.1)称为目标函数；(1.2)称为约束条件；(1.3)称为变量的非负约束条件。,二、线性规划问题的标准型由前面所举的例子可知，线性规划问题可能有各种不同的形式。目标函数有实现最大化也有实现最小化的；约束条件可以是“”形式、“”形式的不等式，也可以是等式。决策变量有时有非负限制，有时没有。这种多样性给讨论问题带来了不便。为了便于今后讨论，我们规定线性规

6、划问题的标准型为：,这里我们假设bi 0 ( i = 1,2,m)，否则两端同时乘以“1”。用矩阵向量描述就是：,其中：C = ( c1, c2, , cn )，X = ( x1, x2, , xn ) ，b = ( b1, b2, , bm ), A = ( P1, P2, , Pn ) ，Pj = ( a1j, a2j, , amj ) ，0 = ( 0, 0, , 0 ) , ( j = 1, 2, , n ) 。我们称 A 为约束方程组的系数矩阵( mn阶)，一般情况下 m n , m , n 为正整数，分别表示约束条件的个数和决策变量的个数，C 为价值向量，X 为决策向量，通常aij

7、 , bi , cj ( i = 1, 2, , m ，j = 1, 2, , n ) 为已知常数。,T,T,T,T,T,T,实际上，具体问题的线性规划数学模型是各式各样的，需要把它们化成标准型，并借助于标准型的求解方法进行求解。以下就具体讨论如何把一般的线性规划模型化成标准型。1. 若要求目标函数实现最小化时，即此时的目标函数是：min Z=C X，这时只需要将目标函数的最小值变换为求目标函数的最大值，即 MinZ=Max (-Z) 。令Z= -Z，于是就得到： Max Z= - C X 。,2. 若约束方程组为不等式。这时有两种情况：一是约束条件为“ ”形式的不等式，则在“ ”号的左边加入

8、非负的松弛变量，把原“ ” 形的不等式变为等式；另一种是约束条件为“ ”形式的不等式，则可在“ ”号的左端减去一个非负的剩余变量。相应的松弛变量或剩余变量在目标函数中的价值系数取值为0。3. 若存在无非负要求的变量。即有某一个变量 xj 取正值或负值都可以。这时为了满足标准型对变量的非负要求，可令 xj = xj- xj, 其中： xj、 xj 0 ，由于xj可能大于也可能小于xj，故 xj 可以为正也可以为负。,上述的标准型具有如下特点：（1）目标函数求最大值；（2）所求的变量都要求是非负的；（3）所有的约束条件都是等式；（4）常数项非负。综合以上的讨论可以说明任何形式的线性规划问题都可以通

9、过上述手段把非标准型的线性规划问题化成标准型。现举例如下：,例13 将例11的数学模型化为标准型。 解：引进3个新的非负变量x3，x4，x5使不等式变为等式，标准型为：Max Z=2x1+3x2+0x3+0x4+0x5 3x2+x3=154x1+x4 =122x1+2x2+x5=14 x1，x2，x3，x4，x50,例14 试将如下线性规划问题化成标准型,解：令 x3 = x4 - x5 , x4 , x5 0 , (1)式左端加上非负松弛变量 x6 ；(2)式左端减去非负剩余变量 x7 , 则可将上述线性规划问题化成如下的标准型：,第二节 线性规划问题的图解法及几何意义,一、线性规划问题的解

10、的概念在讨论线性规划问题的求解之前，先要了解线性规划问题的解的概念。由前面讨论可知线性规划问题的标准型为 (1.6)、(1.7)、(1.8)式所示：,1. 可行解: 满足约束条件(1.7)，(1.8)的解 X = ( x1, x2, , xn) 称为线性规划问题的可行解；所有可行解的集合称为可行解集或可行域。2. 最优解: 满足约束条件及目标函数(1.6)的可行解称为线性规划问题的最优解。 3. 基: 假设 A 是约束方程组的系数矩阵，其秩数为 m ，B是矩阵 A 中由 m 列构成的非奇异子矩阵(B的行列式的值不为0)，则称 B 是线性规划问题的一个基。这就是说，矩阵 B 是由 m 个线性无关

11、的列向量组成，不失一般性，可假设:称 Pj ( j = 1,2,m )为基向量，与基向量 Pj 相对应的变量xj ( j = 1,2,m )称为基变量，否则称为非基变量。,T,为了进一步讨论线性规划问题的解，下面研究约束方程组(1.7)的求解问题。假设该方程组系数矩阵 A 的秩为 m，因 m n，所以它有无穷多个解。假设前 m 个变量的系数列向量是线性无关的，这时(1.7)式可改写为：方程组(1.9)的一个基是B=(P1, P2, ,Pm), Pj=(a1j, ,amj), (j = 1,2, , m )，设 XB 是对应于这个基的基变量，即：XB = ( x1, x2, , xm ) 现若令

12、(1.9)式中的非基变量xm+1= =xn=0，并用高斯消去法求出一个解X=(x1,x2, ,xm,0, , 0 ) ，这个解的非0分量的数目不大于方程的个数m，这时称X为基本解。,T,T,T,4. 基本可行解 : 满足非负条件(1.8)的基本解称为基本可行解。由此可见，基本可行解的非0分量的数目不大于m，并且都是非负的。5. 可行基: 对应于基本可行解的基称为可行基。由此可见，满足约束方程组(1.7)的基本解的数目至多是 Cnm 个。一般地讲，基本可行解的数目要小于基本解的数目，至多相等。以上提到的几种解的概念，可用图14来表示：,二、线性规划问题的图解法对于简单的线性规划问题(只有两个决策

13、变量的线性规划问题)，我们可以通过图解法对它进行求解。我们以例11具体给出求解的方法。例15 用图解法求解线性规划问题max Z = 2x1 +3x2,解：对于上述具有两个变量的线性规划问题，图1-2中的OABCD部分描述了满足约束条件的区域；虚线为目标函数Z=2x1+3x2的等值线。沿箭头方向移动目标函数的等值线，平移等值线直至与可行域OABCD相切或融合为一条直线，此时就得到最优解为B点，其坐标可通过解方程组得到：2x1+2x2=143x2=15 解得：x1=2x2=5 这就是本线性规划问题的最优解。 此时相应的目标函数的最大值为：Z=22+35=19,例16 用图解法求解线性规划问题ma

14、xZ=40x1+ 80x2 s.t. x1+2x2 303x1+2x2 602x2 24x1 , x2 0解：如图13所示： 求解最优解：BC线段 B点 X(1)= (6,12)；C点 X(2)= (15,7.5)X= X(1)+(1-) X(2) (0 1)maxZ=1200 即 x1 =6 +(1- )15x2=12+(1- )7.5 整理得：x1 =15-9x2 =7.5+4.5 (0 1),例17 maxZ=2x1+ 4x2 s.t. 2x1+x2 8-2 x1+ x2 2x1，x2 0 解：由于可行域无界，作目标函数等值线，如图14中虚线所示，并用箭头标出其函数值增加的方向，由此可以

15、看出，该问题无有限最优解。 若目标函数由 max Z = 2x1 + 4x2 改为 min Z =2 x1 +4 x2 , 则可行解所在的范围虽然无界，但有最优解 x1 = 4，x2 = 0 ，即 (4,0)点。,通过以上各题图解法所得结论可以看出：（1）线性规划的所有可行解构成的可行域一般是凸多边形，有些可行域可能是无界的；（2）若存在最优解，则一定在可行域的某顶点得到；（3）若在两个顶点上同时得到最优解，则在这两点的连线内的任一点都是最优解。（4）若可行域无界，则可能发生最优解无界的情况；（5）若可行域是空集，此时无最优解。上述理论具有普遍意义，对于两个以上变量的线性规划问题都是成立。图解

16、法虽然具有直观、简便等优点，但在变量多的情况下，即在多维的情况下，它就无能为力了。因此，需要介绍一种代数方法单纯型法，为了以后介绍方便，需要研究一下线性规划问题解的基本定理。,三、基本定理1. 凸集：假设K是n维欧氏空间的一个点集，若对于K中的任意两点X1、X2，其连线上的所有点X1+(1-)X2，( 0 1)都在集合K中，即：X1+(1-)X2 K ( 0 1) 则称K为凸集。 从直观上讲，凸集无凹入部分，其内部没有洞。 如实心圆、实心球、实心立方体等都是凸集。两个凸集的交集仍是凸集。2. 凸组合：设X1，X2，Xk是n维欧氏空间En中的k个点，若存在1，2，k，且0 i 1，i = 1,2, , k， i = 1，使X = 1X1 + 2X2 + + kXk，则称X为由X1，X2，Xk所构成的凸组合。 按照定义，凡是由x，y的凸组合表示的点都在x，y的连线上，而且反之亦然。3. 顶点： 假设K是凸集，X K；X若不能用不同的两个点X1、X2 K的线性组合表示为：X = X1+(1-)X2 ， ( 0 1) 则称X为凸集K的一个顶点（或称为极点）。顶点不位于凸集K中的任意不同两点的连线内。,