规划模型.ppt

线性规划问题线性规划问题n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 nMatlabMatlab计算线性规划问题计算线性规划问题一、一、线性规划问题及其数学模型线性规划问题及其数学模型 线性规划在经营管理中，常常用来解决线性规划在经营管理中，常常用来解决有限资源（人、财、物）的合理分配问题。有限资源（人、财、物）的合理分配问题。在经营管理中，几乎一切问题都与有限资源在经营管理中，几乎一切问题都与有限资源的合理分配利用有关。线性规划为解决有限的合理分配利用有关。线性规划为解决有限资源的合理分配利用提供了一个有效的数学资源的合理分配利用提供了一个有效的数学工具。工具。建立线性规划数学模型是解决线性规划问题的建立线性规划数学模型是解决线性规划问题的一个重要步骤。一个重要步骤。建立的线性规划数学模型是否真正的反映客观建立的线性规划数学模型是否真正的反映客观实际，数学模型本身是否正确，都直接影响求解结实际，数学模型本身是否正确，都直接影响求解结果，从而影响决策结果，所以，建立正确的线性规果，从而影响决策结果，所以，建立正确的线性规划模型尤为重要。下面举例说明线性规划数学模型划模型尤为重要。下面举例说明线性规划数学模型的建立。的建立。一、线性规划数学模型的建立一、线性规划数学模型的建立某厂利用某厂利用A A、B B两种原料，生产甲、乙两种产品，有关数据如下：两种原料，生产甲、乙两种产品，有关数据如下：例例1 1：（产品组合问题）：（产品组合问题）产品名称产品名称甲甲 乙乙单位产品单位产品消耗原料消耗原料原料名称原料名称可供利用的原料可供利用的原料数量（数量（T/T/日）日）6 68 81 21 22 12 1A AB B产品售价产品售价 （千元（千元/T T）3 2 3 2根据市场调查，有如下资料：根据市场调查，有如下资料：1.1.乙产品的需求量至多乙产品的需求量至多 2 2 T/T/日日;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产品的需求量至多大 1 1 T/T/日。日。求该厂产值最大的求该厂产值最大的生产方案生产方案。提出三个问题大家考虑：提出三个问题大家考虑：1.1.问题的未知数是什么？问题的未知数是什么？设未知数设未知数2.2.以什么准则进行决策？以什么准则进行决策？目标函数目标函数3.3.约束条件是什么？约束条件是什么？约束方程约束方程 这这里里生生产产方方案案指指的的是是如如何何安安排排甲甲、乙乙产产品品的的产产量量。显显然然，产产量量是是未未知数。知数。设：甲产品的产量为设：甲产品的产量为 x x1 1 T/T/日日 乙产品的产量为乙产品的产量为 x x2 2 T/T/日日 决策准则是产值最大，用决策准则是产值最大，用 Z Z 代表产值，则有：代表产值，则有：Z=3xZ=3x1 1+2x+2x2 2 Z Z 是是x x1 1、x x2 2 的函数，称为目标函数，目标是求极大值，的函数，称为目标函数，目标是求极大值，即：即：max Z=3xmax Z=3x1 1+2x+2x2 2 约束条件（分三部分：资源限制、市场限制、非负限制）约束条件（分三部分：资源限制、市场限制、非负限制）x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2-x-x1 111 x x1 1，x x2 200约束条件资源限制资源限制市场限制市场限制非负限制非负限制2万m31.4万m32万m31.4万m3整理得数学模型：整理得数学模型：目标函数：目标函数：min min z z=1000 =1000 x1+800+800 x2约束条件：约束条件：s.t.s.t.x1 1 1 0.8 0.8 x1+x2 1 1.6.6 x1 2 2 x2 1 1.4.4 x1 0 0，x2 0 0例例3、配料问题（、配料问题（min,)设设 x1,x2分别代表每粒胶丸分别代表每粒胶丸中甲、乙两种原料的用量中甲、乙两种原料的用量 某厂生产一种胶丸，某厂生产一种胶丸，已知如下资料：已知如下资料：例例4、合理下料问题、合理下料问题 用用7.4m长的钢筋，分别截取长的钢筋，分别截取2.9m、2.1m、1.5m各各至少至少100根，要求用料最少。根，要求用料最少。设设 xj 分别代表采用切割方案分别代表采用切割方案18所需所需7.4米的钢米的钢筋的数量。筋的数量。二、线性规划问题的共同特征二、线性规划问题的共同特征（模型的三要素）（模型的三要素）每一个问题都用一组决策变量每一个问题都用一组决策变量(x x1 1，x x2 2，x xn n)表示某表示某一方案；这组决策变量的值就代表一个具体方案。一般一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负的。这些变量取值都是非负的。存在一定的约束条件，这些约束条件可以用一组线性存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。等式或线性不等式来表示。都有一个要求达到的目标，它可用决策变量的线性函都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示。按问题的不同，要求目标数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化函数实现最大化或最小化。三、线性规划数学模型的一般表示方式三、线性规划数学模型的一般表示方式 求解线性规划问题的任务是：在满求解线性规划问题的任务是：在满足约束条件的所有足约束条件的所有(x x1 1，x x2 2，x xn n)（可可行解）中求出使目标函数达到最大行解）中求出使目标函数达到最大(小小)z z 值的决策变量值值的决策变量值(x x1 1*，x x2 2*，x xn n*)（最最优解）。优解）。1.和式和式2.向量式向量式3.矩阵式矩阵式练习题：建立练习题：建立线性规划模型线性规划模型 某城市在一昼夜间，市内交通需要车辆数如图，对车辆某城市在一昼夜间，市内交通需要车辆数如图，对车辆的需求在昼夜间是变化的，车辆的工作制度是一天连续工作的需求在昼夜间是变化的，车辆的工作制度是一天连续工作8 8小时，派车时间在各时间间隔的端点，一旦派出，就连续工小时，派车时间在各时间间隔的端点，一旦派出，就连续工作作8 8小时。求保证需要的最小车辆数。小时。求保证需要的最小车辆数。车辆数时间04712162024481248121084 派车时间在各时间间隔的端点，一旦派出，就连续工派车时间在各时间间隔的端点，一旦派出，就连续工作作8小时。小时。设：各时间间隔所派车辆数为设：各时间间隔所派车辆数为xj j=1，2，6则有：则有：min Z=x1+x2+x3+x4+x5+x6 x1+x64 x1+x28 x2+x3 10 x3+x47 x4+x512 x5+x6 4 x1，x2，x3，x4，x5，x6 0二、二、线性规划问题及图解法线性规划问题及图解法n线性规划问题及其数学模型线性规划问题及其数学模型 n图解法图解法 nMatlab计算线性规划问题计算线性规划问题二、二、图图解法解法 对模型中只含对模型中只含2 2个变量个变量的线性的线性规划问题，可以通过在平面上作规划问题，可以通过在平面上作图的方法求解。图的方法求解。一、图解法的步骤一、图解法的步骤 1.1.等直线法等直线法 x1x204Q2(4,2)Q1Q3Q44x1=164x2=12 x1+2x2=82x1+3x2=03Q21.1.建立平面直角坐标系；建立平面直角坐标系；4 4向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后向着目标函数的优化方向平移等值线，直至得到等值线与可行域的最后交点，这种点就对应最优解。交点，这种点就对应最优解。2.2.找出表示每个约束的找出表示每个约束的半平面半平面，所有半平面的交集是可行域（全体可行，所有半平面的交集是可行域（全体可行解的集合）；解的集合）；3.3.画出目标函数的画出目标函数的等值线等值线 ；2.2.试算法试算法x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2最优解在顶点达到：最优解在顶点达到：O点：点：X1=0,X2=0,Z=0Q1:X1=4,X2=0,Z=8Q2:X1=4,X2=2,Z=14Q3:X1=2,X2=3,Z=10Q4:X1=0,X2=3,Z=6二、线性规划问题解的存在情况二、线性规划问题解的存在情况1.1.存在唯一最优解存在唯一最优解x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+3x2=03Q2如例如例12.2.有无穷多最优解有无穷多最优解 若将例若将例1 1目标函数变为目标函数变为 max max z z=2=2x x1 1+4+4x x2 2，则问题则问题变为存在无穷多最优解。如图变为存在无穷多最优解。如图:x1x204Q2(4,2)Q1Q3Q44x1=164x2=12x1+2x2=82x1+4x2=03Q2 3.有无界解有无界解z 可可行行域域可可伸伸展展到到无无穷穷，由由此此目目标标函函数数值值也也可可增增大大至至无无穷穷。这这种种情情况况下下问问题题的的最最优优解解无无界界。产产生生无无界界解解的的原原因因是是由由于于在在建建立立实实际际问问题题的的数数学学模模型型时时遗遗漏漏了了某某些必要的资源约束条件些必要的资源约束条件。例如：例如：max Z=2x1+2x2 s.t.-2x1+x24 x1-x2 2 x1，x2 00 x x1 1x x2 2例如：例如：min Z=60 x1+50 x2 2x1+4x2 80 3x1+2x2 60 x1，x2 00 x x1 1x x2 2无界不一定无最优解无界不一定无最优解X X1 1=10,x=10,x2 2=15 Z=1350=15 Z=1350模型的约束条件之间存在矛盾，建模时有错误。模型的约束条件之间存在矛盾，建模时有错误。4.无可行解（无可行解（可行域为空集可行域为空集）例如：例如：max Z=x1+2x2 -x-x1 1-x-x2 22 2 2x 2x1 1+x+x2 24 4 x x1 1，x x2 2 000 x x1 1x x2 2 三、由图解法得到的启示三、由图解法得到的启示 图图解解法法虽虽只只能能用用来来求求解解只只具具有有两两个个变变量量的的线线性性规规划划问问题题，但但它它的的解解题题思思路和几何上直观得到的一些概念判断，对下面要讲的单纯形法有很大启示：路和几何上直观得到的一些概念判断，对下面要讲的单纯形法有很大启示：1 1求求解解线线性性规规划划问问题题时时，解解的的情情况况有有：唯唯一一最最优优解解；无无穷穷多多最最优优解解；无界解无界解；无可行解无可行解。（见下页图示所示）（见下页图示所示）2 2若线性规划问题的可行域存在，则可行域是一个若线性规划问题的可行域存在，则可行域是一个凸集凸集。3 3若若线线性性规规划划问问题题的的最最优优解解存存在在，则则最最优优解解或或最最优优解解之之一一(如如果果有有无无穷穷多的话多的话)一定是可行域的凸集的某个一定是可行域的凸集的某个顶点顶点。4 4解解题题思思路路是是，先先找找出出凸凸集集的的任任一一顶顶点点，计计算算在在顶顶点点处处的的目目标标函函数数值值。比比较较周周围围相相邻邻点点的的目目标标函函数数值值是是否否比比这这个个值值大大，如如果果为为否否，则则该该顶顶点点就就是是最最优优解解的的点点或或最最优优解解的的点点之之一一，否否则则转转到到比比这这个个点点的的目目标标函函数数值值更更大大的的另另一一顶顶点，重复上述过程，一直到找出点，重复上述过程，一直到找出使目标函数值达到最大的顶点使目标函数值达到最大的顶点为止。为止。(d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解 多个最优解多个最优解 唯一最优解唯一最优解四、线性规划问题的标准形式四、线性规划问题的标准形式 （一）线性规划问题标准形式（一）线性规划问题标准形式 为了使线性规划问题的解法标准，就要把为了使线性规划问题的解法标准，就要把一般形式化一般形式化为为标准形式标准形式。其。其一般形式一般形式如下所示：如下所示：某厂利用某厂利用A A、B B两种原料，生产甲、乙两种产品，有关数据如下：两种原料，生产甲、乙两种产品，有关数据如下：练习题：用图解法求解下列问题练习题：用图解法求解下列问题产品名称产品名称甲甲 乙乙单位产品单位产品消耗原料消耗原料原料名称原料名称可供利用的原料数可供利用的原料数量（量（T/日）日）681 22 1AB产品售价产品售价（千元（千元/T）3 2根据市场调查，有如下资料：根据市场调查，有如下资料：1.1.乙产品的需求量至多乙产品的需求量至多 2 2 T/T/日日;2.2.乙产品的需求量比甲产品的需求量至多大乙产品的需求量比甲产品的需求量至多大 1 1 T/T/日。日。求该厂产值最大的生产方案。求该厂产值最大的生产方案。max Z=3xmax Z=3x1 1+2x+2x2 2 x x1 1+2x+2x2 266 2x 2x1 1+x+x2 288 x x2 222 x x2 2-x-x1 111 x x1 1，x x2 2000 x x1 1x x2 2X X1 1=10/3,x=10/3,x2 2=4/3=4/3Z=12.67Z=12.67用用MATLAB优化工具箱解线性规划优化工具箱解线性规划minz=cX 1、模型：命令：x=linprog（c，A，b）2、模型：minz=cX 命令：x=linprog（c，A，b，Aeq,beq）注意：若没有不等式：存在，则令A=，b=.3、模型：minz=cX VLBXVUB命令：1x=linprog（c，A，b，Aeq,beq,VLB，VUB）2x=linprog（c，A，b，Aeq,beq,VLB，VUB,X0）注意：1若没有等式约束:,则令Aeq=,beq=.2其中X0表示初始点4、命令：x,fval=linprog()返回最优解及处的目标函数值fval.解解 编写编写M文件文件xxgh1.m如下：如下：c=-0.4-0.28-0.32-0.72-0.64-0.6;A=0.01 0.01 0.01 0.03 0.03 0.03;0.02 0 0 0.05 0 0;0 0.02 0 0 0.05 0;0 0 0.03 0 0 0.08;b=850;700;100;900;Aeq=;beq=;vlb=0;0;0;0;0;0;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh1)解解:编写编写M文件文件xxgh2.m如下：如下：c=6 3 4;A=0 1 0;b=50;Aeq=1 1 1;beq=120;vlb=30,0,20;vub=;x,fval=linprog(c,A,b,Aeq,beq,vlb,vub)ToMatlab(xxgh2)整数规划的模型整数规划的模型分支定界法分支定界法割平面法割平面法0 01 1 整数规划整数规划蒙特卡洛方法蒙特卡洛方法例一、合理下料问题例一、合理下料问题设用某型号的圆钢下零件设用某型号的圆钢下零件A A1 1,A A2 2,A,Am m 的毛坯。在一根的毛坯。在一根圆钢上下料的方式有圆钢上下料的方式有B B1 1,B,B2 2,B Bn n 种，每种下料方式可以得种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。怎到各种零件的毛坯数以及每种零件的需要量，如表所示。怎样安排下料方式，使得即满足需要，所用的原材料又最少？样安排下料方式，使得即满足需要，所用的原材料又最少？设：设：xj 表示用表示用Bj(j=1.2n)种方式下料根数种方式下料根数 模型：模型：整数规划一般形式整数规划一般形式依依照照决决策策变变量量取取整整要要求求的的不不同同，整整数数规规划划可可分分为为纯纯整整数数规规划划、全全整整数数规规划划、混混合合整整数数规规划划、01整整数数规划。规划。部分或者全部为整数部分或者全部为整数纯纯整整数数规规划划：所所有有决决策策变变量量要要求求取取非非负负整整数数（这这时时引引进进的的松松弛弛变变量量和和剩剩余余变变量量可可以以不不要要求求取整数）。取整数）。全全整整数数规规划划：除除所所有有决决策策变变量量要要求求取取非非负负整整数数外外，系系数数aij和和常常数数bi也也要要求求取取整整数数（这这时时引引进进的松弛变量和剩余变量也必须是整数）。的松弛变量和剩余变量也必须是整数）。混混合合整整数数规规划划：只只有有一一部部分分的的决决策策变变量量要要求求取取非负整数，另一部分可以取非负实数。非负整数，另一部分可以取非负实数。01整整数数规规划划：所所有有决决策策变变量量只只能能取取 0 或或 1 两两个整数。个整数。从从数数学学模模型型上上看看整整数数规规划划似似乎乎是是线线性性规规划划的的一一种种特特殊殊形形式式，求求解解只只需需在在线线性性规规划划的的基基础础上上，通通过过舍舍入入取取整整，寻寻求求满满足足整整数数要要求求的的解解即即可可。但但实实际际上上两两者者却却有有很很大大的的不不同同，通通过过舍舍入入得得到到的的解解（整整数数）也也不不一一定定就就是是最最优优解解，有有时时甚至不能保证所得到的解是整数可行解。甚至不能保证所得到的解是整数可行解。例：设整数规划问题如下例：设整数规划问题如下 首先不考虑整数约束，得到线性规划问题（一般首先不考虑整数约束，得到线性规划问题（一般称为松弛问题）。称为松弛问题）。且为整数 用图解法求出最优解用图解法求出最优解x x1 13/2,3/2,x x2 2=10/3=10/3且有且有Z=29/6Z=29/6x1x233(3/2,10/3)现现求求整整数数解解（最最优优解解）：如如用用“舍舍入入取取整整法法”可可得得到到4个个点点即即(1，3),(2，3),(1，4),(2，4)。显显然然，它它们们都都不不可可能能是是整整数数规规划划的的最优解。最优解。按按整整数数规规划划约约束束条条件件，其其可可行行解解肯肯定定在在线线性性规规划划问问题题的的可可行行域域内内且且为为整整数数点点。故故整整数数规规划划问问题题的的可可行行解解集集是是一一个个有有限限集集，如图所示。如图所示。因因此此，可可将将集集合合内内的的整整数数点点一一一一找找出出，其其最最大目标函数的值为最优解，此法为完全枚举法。大目标函数的值为最优解，此法为完全枚举法。如如上上例例：其其中中（2 2，2 2）（3 3，1 1）点点为为最最大大值值，Z=4Z=4。目前，常用的求解整数规划的方法有：目前，常用的求解整数规划的方法有：分支定界法和割平面法；分支定界法和割平面法；对于特别的对于特别的0 01 1规划问题采用隐枚举法。规划问题采用隐枚举法。0-1型整数规划1.0-1变量及其应用：0-1变量可表示逻辑关系：x=1:采取方案。x=0:不采取方案。若需要从p个约束条件中，恰好选择q个，则可引入p个0-1变量：yi=0:选择i个约束条件。yi=1:不选择i个约束条件那么，约束条件组为：Mi是充分大的数2.0-1型整数规划的解法n个变量有2n种组合，采用隐枚举法。列出2n种组合，先求出一个可行解，计算目标函数值，作为当前的最优解。对于其它组合，先计算目标函数值，若不如当前的最优解，就不必检验它的可行性否则，如果是可行解，则把更新为当前的最优解。采用分支定界法，搜索更快。蒙特卡洛方法蒙特卡洛方法 在在前前面面介介绍绍的的分分枝枝定定界界方方法法，算算法法的的每每一一个个计计算算步步骤骤都都是是固固定定的的，而而且且可可以以保保证证求求得得最最优优解解。但但是是，当当整整数数线线性性规规划划的的决决策策变变量量数数目目很很大大时时，分分枝枝定定界界法法的的代代价价可可能能是是巨巨大大的的；特特别别是是当当整整数数规规划划本本身身是是非非线线性性的的时时候候，尚尚未未有有一一种种成成熟熟而而有有效效的的求解方法，因为非线性规划本身的通用有效解法尚未找到。求解方法，因为非线性规划本身的通用有效解法尚未找到。然然而而，由由于于整整数数规规划划解解的的数数目目是是有有限限的的，于于是是为为枚枚举举法法提提供供了了方方便便。当当然然，当当决决策策变变量量数数目目很很大大、取取值值范范围围很很宽宽情情况况下下，企企图图用用完完全全搜搜索索（即即穷穷举举法法）计计算算出出最最优优值值是是不不现现实实的的，但但是是应应用用蒙蒙特卡洛算法，在一定的计算量下，完全可以得出一个满意解。特卡洛算法，在一定的计算量下，完全可以得出一个满意解。例例 已知非线性整数规划为：已知非线性整数规划为：对对该该问问题题，目目前前尚尚无无有有效效方方法法求求出出准准确确的的最最优优解解。如如果果用用穷穷举举法法（完完全全搜搜索索）试试探探，共共需需计计算算1005=1010 个个点点，计计算算量量非非常常大大。然然而而概概率率理理论论能能够够保保证证，应应用用蒙蒙特特卡卡洛洛方方法法随随机机计计算算106个个点，便可找到问题的满意解。点，便可找到问题的满意解。解：用蒙特卡洛方法求解这个问题必须借助计算机来实现。解：用蒙特卡洛方法求解这个问题必须借助计算机来实现。运行程序运行程序 5 次，可得如下表次，可得如下表 所示的结果：所示的结果：注注：蒙蒙特特卡卡洛洛（Monte Carlo）算算法法是是一一种种随随机机搜搜索索算算法法，它它允允许许算算法法在在执执行行的的过过程程中中随随机机选选择择下下一一个个计计算算步步骤骤。许许多多情情况况下下，当当算算法法在在执执行行过过程程中中面面临临一一个个选选择择时时，随随机机性性选选择择常常比比最最优优选选择择省省时时，因因此此蒙蒙特特卡卡洛洛算算法法可可在在很很大大程程度度上上降降低低算算法法的的复复杂杂度度。但但另另一一方方面面，同同一一实实例例用用蒙蒙特特卡卡洛洛算算法法求求解解两两次次可可能能得得到到完完全全不不同同的的结结果果，也也就就是是说说，用用蒙蒙特特卡卡洛洛算算法法能能够够求求得得问问题题的的一一个个解解，但但无无法法判判断断这这个个解解是是否否正正确确，求求得得正正确确解解的的概概率率依依赖赖于于算算法法所所用用的时间，算法所用的时间越多，得到正确解的概率就越高。的时间，算法所用的时间越多，得到正确解的概率就越高。此课件下载可自行编辑修改，供参考！感谢您的支持，我们努力做得更好！