管理运筹学第02章线性规划简介.ppt

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,CONTENTS,管理运筹学,第,2,章 线性规划简介,线性规划是运筹学中研究最早，理论和算法比较成熟的一个重要分支，其应用十分广泛。早在,1939,年，前苏联的数学家康托洛维奇（,1975,年诺贝尔经济学获得者）就提出了生产组织和管理中的线性规划模型。,20,世纪,40,年代末，美国的,Dantzig,提出了求解一般线性规划的单纯形方法。,Charnes,对于线性规划的理论和应用也作出了突出的贡献。目前可供计算大规模线性规划问题的计算机软件也较为成熟。因此，线性规划在工农业生产、商业活动、军事行动和科学研究的各个方面都得到了重要的应用。,2.1,线性规划模型,在了解线性规划的理论和应用前，必须先对线性规划模型有一个形象的映像。这一节将继续绪论中的讨论，首先介绍如何将真实问题转化为数学模型。下面通过两个示例（最优投资组合问题和投资决策问题）来介绍这一问题。,【,例,2-1】,一个投资者希望用一定数量的资金进行投资。他对,10,种不同的股票进行投资，并估计在,1,年内投资的收益。表,2-1,给出了每种股票的国别、风险类别（,R,为高风险，,N,为低风险）和期望投资收益率（,ROI,）。投资者确定了某些约束条件。为了分摊风险，他希望对每种股票的投资最多占总资金的,30,。进一步，他希望资金的一半能够投资在北美的股票和最多 是高风险投资。这些资金应该怎样在各种股票中进行分配才能达到最大化的收益的目的呢？,2.1,线性规划模型,编号,描述,国别,风险类型,期望收益率,1,国库券,加拿大,N,5,2,硬件,美国,R,17,3,剧院,美国,R,26,4,电信,美国,R,12,5,酿酒,英国,N,8,6,高速公路,法国,N,9,7,汽车,德国,N,7,8,银行,卢森堡,N,6,9,软件,印度,R,31,10,电子,日本,R,21,表,2-1,股票的国别和估计投资收益列表,2.1,线性规划模型,解：为了构建数学模型，首先要确定问题的解中包含的决策变量：在当前的案例中，希望知道整个投资中每种股票的投资数量。因此，定义决策变量 表示股票 在投资资金中所占的比例。这也就意味着所有变量都必须是一个在,0,和,1,之间的分数（其中,1,代表整个资金的,100,）。事实上，每个变量都有一个最大值约束，即投资者期望的投资每种股票最多占整个资金的,30,。以下约束条件建立了所有变量的边界：,将 作为股票 的期望,ROI,，在这里表示：,2.1,线性规划模型,投资者希望将所有的资金都进行投资，也就是说不同股票的分数之和必须为,100,。这可以表达为以下等式约束：,现在仍然需要两个约束条件来表达投资者的特殊要求。至多,1/3,的资金是高风险股票，即投资到这个类型股票的资金之和不能超过整个资金的,1/3,：,投资者同样坚持对北美的股票的投资最少,50,：,这两个约束条件为不等式约束。,2.1,线性规划模型,投资者的目标是最大化所有股票投资的收益，也就是说最大化下面的表达式：,这就是数学模型的目标函数。,总结以上不同部分，可以得到以下整个数学模型的表达式：,2.1,线性规划模型,通过对这个问题的解读，已经将以上的模型建立起来了。其中，,“,maximize,”,表示最大化。,S.t.,是英文,“,subject to,”,的缩写，,“,使得,”,的意思。下面来回忆一下整个建模过程和线性规划的一些特点：,（,1,）全面了解问题。,（,2,）描述目标。,（,3,）描述约束条件。,（,4,）定义决策变量。,（,5,）用决策变量写出目标和约束条件。,2.1,线性规划模型,以上问题就是线性规划模型或者线性规划。正如前面所述，该问题有目标和约束条件，这是所有线性规划所共有的特点。并且它的目标函数和约束条件都是关于决策变量的线性函数。线性函数是指函数中的每个变量都是分离的并且幂次为,1,。在刚才的模型中，目标函数是线性函数，因为所有的决策变量都是分离的，并且都是一次幂。约束条件的左边都是线性函数，因此称此问题为线性规划。,线性规划有,3,个基本的假设：比例性、可加性和可分性。比例性是指目标函数值和约束条件所对应的资源值与决策变量值成比例。可加性是指目标函数的值和使用资源总量分别可以通过汇总所有的决策变量对目标函数的贡献和各个决策变量使用资源数量而得到。可分性是指决策变量是连续的。非负条件和可分性假设意味着决策变量可以是大于或者等于零的一切数值。,2.1,线性规划模型,【,例,2-2】,某公司有,100,万的资金可供投资。该公司有六个可选的投资项目，其各自的数据如表,2-2,所示：,表,2-2,六个可选投资项目的有关数据,投资项目,风险（）,红利（）,增长率（）,信用度,1,18,4,22,4,2,6,5,7,10,3,10,9,12,2,4,4,7,8,10,5,12,6,15,4,6,8,8,8,6,2.1,线性规划模型,该公司想达到的目标为：投资风险最小，每年的红利至少为,6.5,万元，最低平均增长率为,12,，最低平均信用度为,7,。,解：首先面对这一问题，要抓住决策变量、目标以及约束条件。,(1),决策变量：本问题的决策变量是在每种投资项目上的投资额。设,X,i,为项目,i,的投资额,(),。,(2),目标函数：本问题要求总投资最小，即：,2.1,线性规划模型,(3),约束条件：本问题共有,5,个约束条件。这些约束可以表示为：,A.,各项目投资总额为,100,万；,B.,每年的红利至少为,6.5,万：,C.,最低平均增长率为,12,：,D.,最低平均信用度为,7,：,E.,非负约束：,2.1,线性规划模型,于是得到以下的线性规划模型：,这是一个典型的成本（或者风险）最小化问题。模型的意义是在给定的限制条件下，求使得目标函数达到最小时的每个项目投资额。可以看到，以上问题是线性规划模型。该问题有目标和约束条件，其目标函数和约束条件都是决策变量的线性函数，也满足线性规划的,3,个基本假设。,2.2,线性规划图解法,对模型中只含有,2,个变量的线性规划问题，可以通过在平面上作图的方法求解。通过图解法，可以对线性规划问题及其求解过程有一个直观的认识，便于建立,N,维空间中线性规划问题的概念，同时帮助读者更好地理解求解一般线性规划问题的单纯形法的思路。,2.2,线性规划图解法,2.2.1,线性规划问题图解法的步骤,为了便于理解，下面将通过抽象出来的数学规划模型来具体说明线性规划问题图解法的步骤，以便理解。,【,例,2-3】,考虑只有两个变量的线性规划问题，用图解法解答：,max z=x,1,+3x,2,2.2,线性规划图解法,1.,在平面上建立直角坐标系,2.,根据图示约束条件，找出可行域,3.,图示目标函数,4.,寻找最优解,最优解的目标函数值为：,2.2,线性规划图解法,例,2-3,的线性规划问题的可行域如图,2-1,中阴影部分所示。,2.2,线性规划图解法,2.2.1,线性规划问题图解法的步骤,1.,有唯一的最优解,2.,有无穷多最优解,3.,无界解,4.,无解，或无可行解,2.2,线性规划图解法,以上几种情况的图示见图,2-2,：,2.3,线性规划的基本概念,2.3.1,线性规划问题的标准形式,由于目标函数和约束条件在内容与形式上的差别，导致线性规划问题表达多种多样，为了便于讨论线性规划问题的求解方法和解的性质，需要规定线性规划问题的标准形式。如果一个线性规划问题满足以下条件，就称为标准形式的线性规划问题：,(1),求目标函数的最大值,;,(2),所有变量均要求取非负值,;,(3),所有的约束条件（变量非负约束除外）必须为等式,;,(4),约束条件右端常数项,b,i,全为非负值。,2.2,线性规划图解法,具有,n,个变量的线性规划问题的标准形式如下：,2.2,线性规划图解法,标准形式的矩阵表达式如下：,max z,C,T,X,AX,b,X0,其中，,，,s.t.,2.3,线性规划的基本概念,对于各种非标准形式的线性规划问题，总可以通过以下的变换，将其转化为标准形式。,（,1,）极小化目标函数的问题：,（,2,）约束条件不为等式的问题：,（,3,）变量无符号限制的问题：,（,4,）变量小于等于零的问题：,2.3,线性规划的基本概念,2.3.2,线性规划问题的解,在图解法中，已经比较直观地讨论了线性规划问题的可行解和最优解等概念，但图解法无法解决三个及其三个变量以上的线性规划问题，为了用代数方法求得可行域的极点，还需要引入以下一些有关线性规划可行域和解的概念。,定义,2.1,在,n,维空间中，满足条件：,a,i1,x1+a,i2,x2+,+,a,in,x,n,=b,i,的点集,X=(x,1,，,x,2,，,，,x,n,),T,称为一个超平面。,定义,2.2,满足条件,a,i1,x1+a,i2,x2+,+,a,in,x,n,（或）,b,i,的点集,X=(x,1,，,x,2,，,，,x,n,),T,称为,n,维空间中的一个半空间。,2.3,线性规划的基本概念,定义,2.3,有限个半空间的交集，即同时满足以下条件的非空点集：,a,11,x1+a,12,x2+,+a,1n,x,n,（或）,b,1,a,21,x1+a,22,x2+,+a,2n,x,n,（或）,b,2,a,m1,x1+a,m2,x2+,+,a,mn,x,n,（或）,b,m,称为,n,维空间中的一个多面体。,2.3,线性规划的基本概念,定义,2.4,线性规划的基：,对于线性规划的约束条件,AX=b,X0,其中,A,为,m,n,的矩阵，,nm,，秩,A=m,，,b,为,m,1,向量。设,B,是,A,矩阵中的一个非奇异的,m,m,子矩阵，则称,B,为线性规划的一个基。,定义,2.5,线性规划问题的基解、基可行解和可行基：,线性规划的解,:,称为线性规划与基,B,对应的基解。,2.4,线性规划的计算机求解,2.4.1,用,Excel“,规划求解”功能求解线性规划,1.,在,Excel,电子表格中建立线性规划模型,2.,利用,Excel,“,规划求解,”,功能求解线性规划问题,（,1,）,“,Set Target,”,（设置目标单元格）：在这一栏中，输入表示目标函数值的单元格地址,“,B10,”,(,也可以直接单击,B10,单元格,),。,（,2,）,“,Equal to,”,（等于）：选中,“,min,”,;,（,3,）在,“,By changing cells:,”,中输入：,B4:G4,表示决策变量的位置。,（,4,）在,“,subject to the constraints,”,一栏中通过,“,Add,”,添加约束条件。,2.4,线性规划的计算机求解,（,5,）单击,“,Options,”,按钮，在弹出的,“,Solver Options,”,对话框中，设置求解运算中的有关参数。本问题需要选择,“,Assume Linear Model,”,和,“,Assume Non-Negative,”,。这是采用线性模型和假定非负的复选框，单击确定，如图,2,6,所示：,（,6,）单击左上角的,“,Solve,”,按钮，则开始进行规划求解。,（,7,）在弹出的,“,Solver Results,”,对话框中（注意：当模型没有可行解或者目标值为无穷的时候，规划求解结果的内容将不同），选中,“,keep Solver Solution,”,保存结果，单击,“,OK,”,，如图,2-7,所示。,2.4,线性规划的计算机求解,2.4.2,用,LINDO/LINGO,求解线性规划问题,1.LINDO,软件求解线性规划,安装好,LINDO,软件包以后，点击执行文件。此时会弹出,LINDO,软件的空白对话框。在空白对话框中就可以直接书写命令了。,下面给出其结果的一般解释（划线的部分表示需要的求解结果）：,“,LP OPTIMUM FOUND AT STEP 3,”,表示,LINDO,在（用单纯形法）,3,次迭代或旋转后得到最优解。,“,OBJECTIVE FUNCTION VALUE 1)8.25,”,表示最优目标值为,8.25,。,“,VALUE,”,给出最优解中各变量的值。,2.4,线性规划的计算机求解,要得到以上结果，必须遵循以下简单的软件规则：,（）目标函数及各约束条件之间一定要有,“,Subject to(ST),”,分开。,（）变量名不能超过个字符。,（）变量与其系数间可以有空格，单不能有任何运算符号（如乘号,“,”,等）。,（）要输入,=,约束，相应以,代替即可。,（）一般,LINDO,中不能接受括号,“,（）,“,和逗号,“,，,“,，例：,400(X1+X2),需写成,400X1+400X2,；,10,000,需写成,10000,。,（）表达式应当已经简化过。不能出现,2 X1+3 X2-4 X1,，而应写成,-,X1+3 X2,。,2.4,线性规划的计算机求解,2.LINGO,软件求解线性规划,LINGO,是求解优化问题的一个专业工具软件，它包含了内置的建模语言，容许用户以简单直观的方式描述较大规模的优化模型，对于模型中所需要的数据可以以一定的形式保存在独立的文件中，读取也很方便快捷。,一般来说，在,LINGO,中建立优化模型都是由四个部分组成，也即是：集合段，数据段，初始段以及目标与约束段。每个模型都是由,model,语句开始，由,end,语句结束。,