运筹学-1-线性规划1

1、线 性 规 划 (Linear Programming),线性规划问题及其数学模型,线性规划问题的求解方法,图解法,单纯形法,单纯形法的进一步讨论,线性规划模型的应用,线性规划研究的主要问题： 线性约束条件下的线性函数极致问题 在一定的人力、财力、资源条件下，如何合理安排使用，使效益最高? 某项任务确定后，如何安排人力、财力、物力，使之花费最省?,线性规划介绍,历史悠久，理论成熟，应用广泛 运筹学的最基本的方法之一，网络规划、整数规划、目标规划和多目标规划都是以线性规划为基础的。 解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。,线性规划问题的发展 1939年，前苏联数学家康

2、托洛维奇用线性模型研究提高组织和生产效率问题 1947年，Dantzig提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法 1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。 1963年Dantzing写成“Linear Programming and Extension” 1979年，苏联的Khachiyan提出“椭球法” ，1984年，印度的Karmarkaa提出“投影梯度法”研究成功线性规划的多项式算法。 线性规划是研究线性不等式组的理论，或者说是研究（高维空间中）凸多面体的理论

3、，是线性代数的应用和发展。,一、线性规划问题及其数学模型,1、问题的提出,例1 某工厂用A,B,C,D四种设备生产I,II两种产品，已知生产单位产品所需各种设备的数量、在计划期内各种设备的拥有量以及每单位产品I,II的利润见下表所示，问应如何安排生产才能使总利润最大？,建立该问题的数学模型 解(1)决策变量:设生产产品I x1个单位，产品II x2个单位； (2)目标：总利润最大，于是记成max z=2x1+3x2, z 称为目标函数； (3)限制条件 (约束条件) a:各种设备的数量有限，无论如何安排生产，x1,x2均应满足如下条件：,b:产量x1,x2不能为负，即,数学模型,即线性规划模型

4、。,目标函数,约束条件,例2 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下：,班次 时间 所需人数 1 6:00-10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 20 5 22:00-2:00 20 6 2:00-6:00 30,设司乘人员在各时间段一开始时上班，并连续工作8小时，问该公司线路至少应配备多少司乘人员。列出该问题的数学模型,设x1,x2,x6为各班新上班人数，考虑到在每个时间段工作的人数既包括该时间段新上班的人又包括上一个时间段上班的人员，按所需人员最少的要求可列出本例的数学模型：,目标函数：,约束

5、条件：,上面两优化模型，都具有下述特征：,(1)每个问题都用一组未知量x1,x2,.,xn表示所求方案，通常这些变量都是非负的，称为决策变量。,(2)都存在一组约束条件，这些约束条件都可以用一组线性等式或不等式表示。,(3)都有一个要实现的目标，并且这个目标可表示为一组决策变量的线性函数称为目标函数。目标函数可以是求最大也可以是求最小。,具有上述特征的数学模型就称为线性规划模型。,比例性：决策变量变化引起目标的改变量与决策变量改变量成正比； 可加性：每个决策变量对目标和约束的影响独立于其它变量； 连续性：每个决策变量取连续值； 确定性：线性规划中的参数ai , bi , ci为确定值。,线性规

6、划数学模型中隐含的假设,线性规划问题应用 市场营销(广告预算和媒介选择，竞争性定价，新产品开发，制定销售计划) 生产计划制定(合理下料，配料，“生产计划、库存、劳力综合”) 库存管理(合理物资库存量，停车场大小，设备容量) 运输问题 财政、会计(预算，贷款，成本分析，投资，证券管理) 人事(人员分配，人才评价，工资和奖金的确定) 设备管理(维修计划，设备更新) 城市管理(供水，污水管理，服务系统设计、运用),线性规划数学模型,线性规划的适用情况 要解决的问题的目标可以用数值指标反映 对于要实现的目标有多种方案可选择 有影响决策的若干约束条件,目标函数：,约束条件：,2、线性规划数学模型的形式,

7、c1,c2,cn称为价值系数，b1,b2,bm称为资源系数或右端项常数,aij称为技术系数或约束系数,一般形式,紧缩形式,目标函数：,约束条件：,向 量 形 式：,矩阵形式：,一 般 有 两种方法,图 解 法 单纯形法,两个变量、直角坐标 三个变量、空间直角坐标,适用于任意变量、但需将 一般形式变成标准形式,二、线性规划问题的求解方法,例1、,(一)图 解 法,步骤：(1)建立平面直角坐标系； (2)画出可行域; (3)作目标函数等值线； (4)寻找最优解.,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,作 图, 最 优 解：x1 = 4 x2 = 2,有唯一最优解，Z = 14

8、,x2,x1,(4 2),可行域,最优解,目标函数等值线,x2=-2/3x1+z/3,例2、,例3、,无穷多最优解,无有限最优解,x1,x1,x2,x2,x1,x2,无可行解,例5、,例4、,唯一解,x1,x2,线性规划问题的解的情况： 有可行解 有唯一最优解 有无穷多个最优解 无有限最优解 无可行解,图解法的启示 (1)具有两个变量的线性规划问题的可行域是凸多边形。 (2)若线性规划存在最优解，它一定在可行域的某个顶点得到。 虽然图解法只能求解包含2个或3个变量的问题，作为算法，没有太大价值，但是上述结论却非常有意义。它将搜索最优解的范围从可行域的无穷多个点缩小到有限几个顶点。从而开启了人们

9、的思路。而后面我们要介绍的求解多维线性规划的单纯形法就是在此结论的基础上推广得到的。,(二)线性规划模型的标准形式,1、标准形式,2、特征： (1)目标函数为求极大值； (2)所有约束条件（非负条件除外）都是等式; (3)右端常数项均为非负; (4)所有决策变量均为非负。,矩阵形式：,向 量 形 式：,3、转换方式：,(1) 目标函数的转换,(3)约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,(4)变量的变换,若存在取非正值的变量xj,可令xj=-xj,其中xj 0.,例 1、将下列线性规划问题化为标准形式,例2、将线性规划问题化为标准型,解：,1、解的概念, 可行解：满足

10、约束条件(2)、(3)的解为可行解。所有可行解的集合称为可行域。, 最优解：使目标函数(1)达到最大值的可行解。,(三)线性规划问题的解,(1),(2),(3), 基可行解：满足变量非负约束条件(3)的基解。, 可行基：对应于基可行解的基称为可行基。,基与解的对应关系：,非可行解,可 行 基 解 可行解,基解,解与解之间的关系为：,基解,基,可行基,基可行解,最优基,基最优解,例1 求出下面线性规划的所有基解，并指出哪些是基可行解。,化为标准型：,秩A=2,得基可行解,得基可行解,得基解,得基解,得基可行解,得基可行解,需待解决的理论问题,什么条件下LP的可行域非空？可行域D有何特性？ 可行域

11、D是否有顶点？顶点有多少个？顶点的数学含义？ 是否一定能保证最优解在顶点（D内）上达到？ 顶点是什么概念？ 基本可行解是否存在？如何判断？ 基本可行解是否唯一对应D的一个顶点？ 如何求基本可行解？,凸集：设K是n维欧氏空间的一个点集，若任意两点,的连线上的一切点,则称K为凸集。,凸集的特征是：连接集合中任意两点的线段也在集合之中。,凸组合：设X(1),X(2),X(k)是n维欧氏空间的K个点，若存在满足,则称,为X(1),X(2),X(k)的凸组合。,2.线性规划问题解的几何意义,顶点：设K是凸集,定理3.1线性规划问题的可行域D=x|Ax=b,x0是一个凸集。,若X不能表示成任何,两点连线的

12、内点，则称X为K的一个顶点(或极点),关于线性规划问题解的性质，介绍以下几个定理：,证明：设,因此，根据凸集的定义，D为凸集。,定理3.2 X是可行域D=x|Ax=b,x0的顶点的充要条件是：X是该线性规划问题的基可行解。,证明：必要性 设X是D的顶点。若X不是基可行解，不妨设,由引理1知,P1,P2,Pk必线性相关，于是存在不全为0的一组数,满足,易于验证,此与X是D的顶点矛盾，因而X是基可行解。,充分性：设X是问题的基可行解，不妨设,于是P1,P2,Pk必线性无关。若X不是D的顶点，则存在,于是，对j=k+1,k+2,n,有,因此，对于j=k+1,k+2,n,应有,故P1,P2,Pk必线性

13、相关，这与已知矛盾.,因此，X必为顶点.,定理3.3若可行域非空有界，则线性规划问题一定可以在可行域的某个顶点上找到最优解。,证明：不妨设可行域的顶点为,域D的任意一点。由引理2,有,由x(0)的任意性，知线性规划在顶点x(m）处达到最优。,说明1：若可行解集D无界，则线性规划问题可能有最优解，也可能无最优解。若有最优解，也必在顶点上达到。,说明2：有时目标函数也可能在多个顶点上达到最优值。这些顶点的凸组合也是最优值。（有无穷多最优解）,重要结论,线性规划问题的可行域是凸集；凸集的每个顶点对应一个基可行解，基可行解个数是有限的，当然凸集的顶点也是有限的；若线性规划有最优解，必在可行域某顶点上达

14、到，亦即在有限个基可行解中存在最优解。因此，可以在有限个基可行解中去找最优解。这就是下节将介绍的单纯形法的理论依据，该方法是一种在基可行解中搜索最优解的算法。,单纯形法的基本思想是：首先从可行域的一个基可行解(一个顶点)出发，然后判断它是否为最优解，若是则停止计算;否则就找一个更好的基可行解，再进行检验,如此反复经过有限次迭代,直至找到最优解,或者判定它无界(即无有限最优解)为止。,(四)单纯形法,找出一个初始可行解,是否最优,转移到另一个使目标函数 更优的基可行解,最优解,是,否,循 环,结束,例1求解下列线性规划问题,变成标准型,约束方程组的系数矩阵,为基变量,为非基变量,将基变量用非基变

15、量表示,目标函数变为：,令：,则：, 基本可行解为X(0)=（0, 0, 12, 8, 16, 12）此时，Z = 0，它表明该厂未安排产品I,II的生产，资源未被利用，故利润为0.,（2）,（1）,从目标函数(2)可见，x1,x2的系数均为正，故若使这两个非基变量 中的一个变成基变量，均可能使目标函数值增加，为使变换后目 标函数值增加的幅度最大，选正系数最大的那个非基变量x2进基。 (进基原则),确定出基变量的原则是使得到的基解满足非负约束条件。于是有,当x1=x6=0时，z=9,X(1)=(0,3,6,2,16,0),由于(4)中x1的系数为正，可选x1为进基变量，则x4为出基变量，于是新

16、的基变量为x1,x2,x3,x5,非基变量为x4,x6,最优解为:X=(4，2，0，0，0，4） Z=14,1.确定初始基可行解,对标准型的线性规划问题,若在约束条件(1)的系数矩阵中存在一个单位矩阵,作为初始基，则可以求出基解，若基解非负,则为基可行解.,2.从一个基可行解转换为相邻的基可行解,设初始基可行解中的前m个为基变量，即,代入约束条件(1)有,写出(3)系数矩阵的增广矩阵,因,是一个基，其他向量,可用这个基的线性组合来表示，有,或,将(4)式乘上一个正的数,得,(3)式+(5)式并经过整理后有,由(6)式找到满足约束方程组,的另一个点,，有,其中,是,的第j个坐标的值，要使,是一个

17、基可行解，,因规定,故应对所有i=1,m,存在,令这m个不等式中至少有一个等号成立。因为当,时,(7)式显然成立，故可令,由式(8),故,是一个可行解。又因与变量,对应的向量，经重新排列后加上b列有如下形式矩阵和增广矩阵,因,故由上述矩阵元素组成的行列式不为零，,是一个基。,在上述增广矩阵中进行行的初等变换，将第l行乘上1/alj,再分别乘以(-aij)(i=1,l-1,l+1,m)加到各行上去，则增广矩阵左半部变成为单位矩阵，又因,由此X(1)是同X(0)相邻的基可行解，且由基向量组成的矩阵仍为单位矩阵。,(3)最优性检验和解的判别,将基可行解X(0)和X(1)分别代入目标函数得,令,(1)

18、当所有的,时，可以判定现有顶点对应的基可行解即为最优解。,(2)当所有的,又对某个非基变量xj有,这表明可以找到另一个顶点的目标函数值也达到最大。,此时线性规划问题有无穷多个最优解。,反之，当所有非基变量的,时，线性规划问题具有唯一解。,(3)如果存在某个,又,由式(7)知对任意,均有,因而,的取值可以无限增大不受限制。,由式(9)可见,可无限增大，表明线性规划有无界解,（三）、单纯形表,若给定问题标准化后,线性无关的单位列向量，则以这m个单位列向量构,求解约束方程组即可得基可行解。,系数矩阵A中存在m个,1.确定初始基可行解,对于线性规划问题,我们首先介绍求初始基可行解的方法,（一）单纯形法

19、的一般描述,成的单位子矩阵作为初始基B,则令非基变量取零值,求下列问题的初始基可行解,标准化后,为初始基B,即初始基可行解为X=(0,0,100,120)T,2.最优性检验,最优性判别准则：设X(0)=(0,0,b1,bm)T为对应于基B的基可行解，则：,无最优解判别准则,最小比值原则,3.基变换,主元列与主元行交叉处的元素称为主元素。,按主元素进行迭代运算,（二）单纯形算法步骤：,步骤1 将线性规划问题标准化，确定初始可行基和初始基可行解，建立初始单纯形表;,步骤2 检查非基变量的检验数，若所有,则已得最优解，计算结束；否则转下一步;,确定xk为换入变量。,步骤3 若对于,单纯形表中xs 对

20、应的列向量非正,，则该问题无有限最优解，计算结束；否则转下一步;,步骤4 据,确定xl 为换出变量。称alk 为主元素，同时转入下一步;,步骤5以alk为主元进行迭代运算，得新的单纯形表，重复以上步骤，直到得到最优解。,1. 唯一最优解,2 3 0 0 0 0,12/2,8/2,12/4,3,x2,3,0,1,0,0,0,1/4,2,6,2,0,1,0,0,-1/2,1,0,0,1,0,0,-1/2,2 0 0 0 0 -3/4,6/2,2,16/4,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2

21、0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,2. 无穷多个最优解,引入松弛变量x3,x4,x5化为标准形,CB,XB,b,x1 x2 x3 x4 x5,3 2 0 0

22、0,i,x3 x4 x5,0 0 0,4 14 3,-1 3 1,2 2 -1,1 0 0,0 1 0,0 0 1,-z,0,3 2 0 0 0,14/3,3/1,x3 x4 x1,0 0 3,3,1 -1 0 0 1,5,0 5 0 1 -3,7,0 1 1 0 1,-z,-9,0 5 0 0 -3,7,1,x3 x2 x1,0 2 3,1,0 1 0 1/5 -3/5,6,0 0 1 -1/5 8/5,4,1 0 0 1/5 2/5,-z,-14,0 0 0 -1 0,由表III知最优解为X1*=(4,1,6,0,0)T,由于5=0,可选x5进基，再求最优解,CB,XB,b,x3 x2 x

23、1,6 1 4,0 2 3,x1 x2 x3 x4 x5,3 2 0 0 0,i,0 0 1 -1/5 8/5 0 1 0 1/5 -3/5 1 0 0 1/5 2/5,-z,-14,0 0 0 -1 0,15/4,10,x5 x2 x1,0 2 3,15/4,0 0 5/8 -1/8 1,13/4,0 1 3/8 1/8 0,5/2,1 0 -1/4 1/4 0,-z,-14,0 0 0 -1 0,X2*=(5/2,13/4,0,0,15/4)T也为最优解，且X1*,X2*的凸组合也为最优解。,3. 无有限最优解,CB,XB,b,x1 x2 x3 x4 x5,x3 x4 x5,0 0 0,2

24、 1 2,1 2 0 0 0,-2 1 1,1 -3 -1,1 0 0,0 1 0,0 0 1,-z,0,1 2 0 0 0,i,2,x2 x4 x5,2 0 0,2,-2 1 1 0 0,7,-5 0 3 1 0,4,-1 0 1 0 1,-z,-4,5 0 -2 0 0,例：求解下列线性规划问题,化为标准型后,三、单纯形法的进一步讨论,求初始可行基和基可行解的方法,1. 试算法,(1)在系数矩阵A中，任取m个线性无关的列向量，(假设A的秩为m）作为基B,相应的变量为基变量，,缺点(1)从A的n列中选出m个线性无关的列向量，即要判断m个列向量线性无关要花一定的计算工作量；(2)即使选出了m个

25、线性无关的列向量作为基B，但并不一定能保证最后算出的B-1b0,即基B不一定是可行基；(3)矩阵的初等变换的计算量也很大。,(2) 利用矩阵的初等行变换对约束方程组的增广矩阵(A b)进行变换，目的是将B变为单位矩阵，即将AX=b化为,2. 人工变量法,为了在约束方程组的系数矩阵中凑成一个mm阶的单位矩阵，以便形成一个初始可行基，可以根据需要在相应的约束方程中人为地加上一个变量，称为人工变量。,由于引进了人工变量，如果仍以原问题的目标函数为新问题的目标函数，得到的线性规划问题就不可能与原问题等价，(因为人工变量的引入已经改变了原问题的约束条件)。为了求解原问题，要设法排除人工变量。,排除人工变

26、量的方法,1. 大M法,因为人工变量是后加入到原约束方程组中的虚拟变量，要将它从基变量中逐渐被置换出来。对于求极大值而言，假定人工变量在目标函数中的系数为-M, 只要在基可行解中，还有人工变量是基变量，且取值不为零，则目标函数就不可能达到最大值。,大M法,列单纯形表求解即可,两条原则,(1),(2),cj的大小，进而确定进基变量。,最优解为（4 1 9 0 0 0 0），Z = 2,大M法的优缺点：,优点：程序实现比较简单，基本上就是原来的单纯形法，只须将目标函数稍加处理,就可按照原单纯形法的步骤进行迭代， 缺点：在利用计算机编程计算时应给M赋予一个适当大的定值，但究竟应该取多大，事先很难预计

27、，而且大M过大容易引起计算误差。,2. 两阶段法,对于前面介绍的大M法，如果用计算机求解时，只能用很大的正数代替M,这就可能造成计算上的错误。为了解决这一问题，我们介绍两阶段法。,第一阶段，判断原问题是否存在初始基可行解：具体求解一个辅助线性规划问题，约束条件是引入人工变量后的约束条件，目标函数是最小化所有人工变量的和，若目标函数的最优值为零，则原问题存在基可行解，进入第二阶段，否则原问题无可行解，结束计算。,第二阶段，求原问题的最优解：在第一阶段得到的最终单纯形表中除去人工变量列，恢复原来的目标函数，并以第一阶段的最优解为初始基可行解，重新计算检验数，然后用单纯形法继续求解。,第一阶段： 在

28、原线性规划问题中加入人工变量，构造如下模型：,第二阶段：在第一阶段的最终表中，去掉人工变量列，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。,例1：,第一阶段,第二阶段,最优解为（4 1 9 0 0），目标函数 Z = -2,例2 用两阶段法求解下列线性规划问题,引入人工变量x5,x6,x7得辅助问题,4,2,1,1,在x6所在行中，有原变量x3的系数为-5/4非零，因此以它为主元进行迭代运算,例3,用两阶段法求解下列线性规划问题,引入人工变量x5,x6,x7， 得辅助问题,4,2,0,1,1,可见w*=0,但基变量中还有人工变量x6（取值为0），且x6

29、所在行中，原变量xj(j=1,2,3,4)下所有的元素均为零，这表明原问题的约束方程组中第2个方程是多余的。将它去掉，即可转入第二阶段，继续迭代求原问题的最优解。,4,4,0,例4 用两阶段法证明该线性规划问题无可行解。,证,引入松弛变量x3,x4及人工变量x5,x6,得辅助问题,辅助问题的最优值g*=-4,故原问题无可行解。,1,需要注意的几个问题 若存在两个以上相同的最小比值，就会出现退化解。理论上讲，退化解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。,当计算中出现最小比值相同的情况时，可按Bland规则 来计算。 Bland 规则： 在j0中，选下标小的非基变

30、量入基； 对相同的最小比值，选下标小的基变量出基。,j与i的计算同max问题。,根据上表列出初始单纯形表 A,（二）、线性规划小结,A,练习1,练习2,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,四、线性规划模型的应用,.存在着多种方案；,.要求达到的目标是在一定条件下实现的，这些约束条件可用线性等式或不等式描述。,.要求解问题的目标函数能用数值指标来反映，且为线性函数；,（一）、资源的合理利用,一般提法： 某厂计划在下一生产周期内生产B1,B2, Bn种产品，要消耗A1,A2, Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表

31、所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？,（二）、合理下料问题,一般提法 设用某种原材料截取零件A1,A2, Am的毛坯。根据以往的经验，在一种原材料上可以有B1,B2, Bn种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问应如何下料才能既满足需要又使原材料消耗最少？,现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,100 200,3 2 1 0 0 2 4 6,2.5米 1.3米,需要 根数,一 二 三 四,下料 下料 件数 方式 毛坯型号,例

32、1：,（三）、合理配料问题,一般提法 某饲养场用n种饲料B1,B2, Bn配置成含有m种营养成分A1,A2, Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？,例2：,某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下： 问两种食物各食用多少， 才能既满足需要、又使 总费用最省？,设：Xj 表示Bj 种食物的食用量,（四）、运 输 问 题,已知资料如表所示：,问应如何制定调运方案，使得总运费最省?,某运输问题的资料如下：,例3：,（五）、作物布局问题,(六）分派问题,解：设 为Bj分派给人Ai情况： Bj分派给Ai时， ； 不分派给Ai时， 。 那

33、末这一问题的数学模型为：,求一组变量 的值， 使目标函数 的值最小。,(完成全部工作的总工时最少）,(六）分派问题,约束条件,每件工作只分派一人去做,每人只做一件工作,每人对每件工作只有 做与不做两种情况,分派问题的模型,目标函数,(七）生产组织与计划问题,(七）生产组织与计划问题,设某车间用机床 生产由 这n个不同零件 构成的机器。如果每架机器需要各 种零件的数目成比例 ; 机床 生产零件 的效率(每日 生产零件数)为 。,() 生产的机器最多,应如何分配机床负荷，才使生产的机器最多?,求一组变 的值,解：设 为一天机床 生产零件 的时 间（单位：日） 这一问题的数学模型为：,生产的机器台数

34、,(七）生产组织与计划问题,() 生产的机器最多,约束条件,各机床一天生产 各种零件总数， 应成已定比例,生产零件时间不能为负数,(七）生产组织与计划问题,各机床生产各种零件 时间总和应等于1,特别地，当 （即每架机器需要各种零件数目相同）时，它的数学模型为：,求一组变量 的值,使它满足,(七）生产组织与计划问题,() 生产的机器最多,目标函数,() 生产的机器最多的模型,(七）生产组织与计划问题,某工厂用机床 加工 种零件。在一个生产周期， 各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间（单位：机时个）和加工每个零件的成本（单位：元个）如表1及表2所示。 问：在这个

35、生产周期，怎样安排各机床的生产任务，才能既完成加工任务，又使总的加工成本最低。,() 总的加工成本最低,(七）生产组织与计划问题,表1 ：加工每个零件的时间,(七）生产组织与计划问题,() 总的加工成本最低,(七）生产组织与计划问题,() 总的加工成本最低,求一组变量 的值,使它满足,(七）生产组织与计划问题,() 总的加工成本最低,约束条件,(加工零件个数不能为负数、分数）,(机床 加工各零件总机时不能超过 能工作机时）,(各机床加工零件 的总数不能少于 需要数）,(七）生产组织与计划问题,总的加工成本最低的模型,(七）生产组织与计划问题,总的加工成本最低的模型,目标函数,某厂签订了5种产品

36、 上半年的交货合同。已知各产品在第 月 的合同交货量 ，该月售价 成本价 及生产1件时所需工时 。该厂第 月的正常生产工时为 ，但必要时可加班生产，第 月允许的最多加班工时不超过 ，并且加班时间内生产出来的产品每件成本增加额外费用 元。若生产出来的产品当月不交货，每件库存1个月交存贮费 元。试为该厂设计一个保证完成合同交货，又使上半年预期盈利总额为最大的生产计划安排。,（）生产存储问题,(七）生产组织与计划问题,解： 设 为 种产品 月份在正常时间内 生产的数量， 为第 种产品 月份 在加班时间内生产的数量。该厂盈利总 额为生产的 5 种产品销售价减去成本和 库存费用。问题的限制条件有两项：,

37、（）生产存储问题,(七）生产组织与计划问题,一是各个月的正常和加班的允许工时； 二是满足交货要求。,该生产存储问题的线性规划模型为,(七）生产组织与计划问题,目标函数,盈利总额=生产的 5 种产品销售价 成本和库存费用,约束条件,一是各个月的正常和加班的允许工时； 二是满足交货要求。,宏达公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款;2003年-100万,2004年-150万,2005年-120万,2006年-110万.以上贷款资金均须于2002年底前筹集齐.但为了充分发挥这笔资金的作用,在满足每年贷款额情况下,可将多余资金分别用于下列投资项目:,(1)于2003年初购

38、买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； (2)于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，但限购90万元； (3)于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元； (4)于每年年初将任意数额的资金存放于银行，年息4%，于每年年底取出。,问宏达公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额为最少。,1、用矩阵形式表示线性规划标准型,(1) (2) (3),五、单纯形法的矩阵描述(已知初始可行基求最优解),2、用矩阵形式表示基可行解、目标函数值及检验数,(4),将(4)代入(1

39、)中,(5),3、用矩阵形式表示 规则,4、用矩阵形式表示单纯形表,(6) (7),(6)(7)可写成表格形式,六、改进单纯形法,从经济管理或其他实际问题中归纳出来的线性规划问题，其变量的个数和约束方程的个数，一般都大大超过我们所遇到的例题和习题。因而都是用计算机来计算的。当问题的规模较大时，如何节省存贮单元和减少计算时间就成为人们必须加以考虑的问题。改进单纯形法正是基于这种考虑出发设计出来的一种适合于计算机计算的方法。,改进单纯形法的基本原理,在单纯形法的迭代过程中，有两个关键步骤：选择进基变量和确定出基变量。为了实现这两步，在每次迭代中，只需计算检验数j 和用最小比值原则计算即,可见这些数据的获得都依赖于基B的逆矩阵B-1.另外，从矩阵形式的单纯形表亦可见。,定理 在单纯形法的相邻两次迭代中，设迭代前的可行基为,经过换基运算后，得到另一个可行基,其中,(1),