数学规划课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数学规划课件,数学规划模型的,一般表达式,：,为目标函数，为约束函数，为可控变量，为已知参数，为随机参数。,数学规划,分为线性规划、非线性规划、动态规划、,随机规划、整数规划、分式规划、几何规划、目标规划、平衡规划、参数规划、多目标规划等十几种。当然这么多规划其中亦有交叉。又可经过组产生新的规划，每一种规划有专著问世。,第一节 线性规划模型,线性规划模型,是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科。1947年美国数学家,丹齐格,G.B.Dantzig及其同事提出的求解线性规划的,单纯形法,及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。随着1979年前苏联数学家,哈奇扬,的,椭球算法,和1984年美籍印度数学家,卡玛卡尔H.Karmarkar算法,的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。线性规划研究的实际问题多种多样，如,生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。,就模型而言，线形规划模型类似于高等数学中的,条件极值问题,，只是其,目标函数和约束条件都限定为线性函数,。,线性规划模型的求解方法目前仍以,单纯形法,为主要方法。本节将介绍的,主要内容：线性规划模型的建立及标准形式；线性规划模型的解和单纯形法；整数线性规划模型及建模案例等。,例2.1,生产组织与计划问题,。,某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg、专用设备能力3000台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示，问如何安排生产，才能使该厂所获利润最大（只需建立数学模型）。,产品,单位产品消,耗定额,材料与设备,甲（件）,乙（件,）,现有材料与,设备能力,钢材,（kg）,铜材,（kg）,设备能力（台时）,单位产品的利润（元）,9 4 3600,4 5 2000,3 10 3000,70 120,建模过程,：,设甲、乙两种产品计划生产量分别为 和 （件），总的利润为 （元）。那么我们的任务就是：求变量的值为多少时，才能使总利润,最大，由已知条件，要受下列限制：,(1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即,(2)生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即,(3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即,(4),甲、乙两种产品的计划生产量不能为负数，即,于是问题转化为求解如下的条件极值问题（,数学模型,）：,例2.2,设有m种物质，第 种物资的库存量为 ，每种物资都可以生产n种产品,第 种物资生产第,种产品时，每生产单位产品所需物资量为,，每种物资生产第 种产品时，每单位产品可获利润 （表22）问如何组织生产才能使利润最大？,表22,产品,种类,生产单位产,品所需物资量,物资种类,库存量,单位产品利润,用 表示生产第 种产品计划数，则问题归结为如下数学问题（,数学模型,）：,约束条件的意义是：每种原料生产n种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。,例2.3,运输问题,设某类物资有 个产地，个销售地.第 个产地的产量为 ,第 个销售地的需要量为 .从产地 到销售地 运输单位物资的运价（单价）为 .今考虑在产销平衡（即 )的条件下，应如何,组织运输，才能使得即满足各地的需要，又使,总运费最小,。,表2,销地,单位物 资运价,产地,产量,需求量,建模过程,:,用 表示产地 供给销地 的物资数量，则问题变成在产销平衡条件下，求解以下数学问题（模型）：,考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变量的线性函数，故称这类数学问题为线性规划问题。,类似的问题很多，诸如,下料问题、配料问题、分配问题、工厂选址问题,等等。它们的解决都是归结上述的线性规划问题，只是约束条件有的是等式，有的是不等式。,通过以上两例可以看出：尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征：,（1）目标函数是决策变量的线性函数。,（2）约束条件都是决策变量的线性等式或不等式。,二、线性规划的解法概述、解的性质及单纯形法,我们称如下的,条件极值问题,为,标准的线性规划问题,。,若引进记号,则（LP）可简单地表示为,进一步，若令,，,则（LP）可表示为：,对于非标准形式的线性规划，可通过下列办法化成标准形式。,若求 ,可化为求 .,若约束条件中含有不等式 或 则可引进新变量 （称为,松弛变量,），化为等式约束：,或,今后总假定 ，否则在等式两边乘以-1即可。,若变量 无非负限制，则引入两个非负变量 与 令 ，便可化为标准形式。,解法概述,（,1,）,单纯形法,：,1947,年由美国数学家,Dantzig,提出，虽然在特殊情况下可能出现循环，但这种方法仍是目前求解线性规划问题最常用的方法。事实上在大量的实际问题计算中看出，循环情况从未出现过（仅在特意构造下才能出现）。它是一种,迭代方法,。,（,2,）,椭球法,：,1977,年由前苏联数学家,khachiyan,提出的,多项式时间算法,，它在理论上保证了多项式时间算法的存在性。但大量数值研究发现，对于大多数实际问题，椭球法在计算上不如单纯形方法。,（3）,Karmarkar内点法,：1983年由美籍印度数学家Karmarkar提出的。也是一种,多项式时间算法,，在大多数情况下比单纯形算法的,计算速度要快,。,（4）,图上作业与表上作业法：,前一种是50年代由我国数学工作者提出的，后者是1950年Dantzing提出的，这二种方法主要是解决,运输问题,（特殊的线性规划）而设计的。据统计在用线性规划解决的实际问题中，70%以上属于运输问题类型。,线性规划问题的软件解法,求解线性规划的常用方法是1947年G.B.Dantzig,提出的单纯形法。这种方法是以寻找最优解的迭代过,程为主线。基本思路是：给出一个基可行解（一个顶,点）后，判断其是否为最优解；若它不是最优解，可,用迭代的方法转换到另一个基可行解（顶点），最终,找到使目标函数值更优的基可行解。经过有限次迭代,后，这一迭代过程以找到最优解或判定问题无最优解,为目标。另外，求解线性规划的方法还有Karmarkar,算法和椭球算法。求解线性规划的软件很多，下面介,绍,Mathematica,和,MATLAB软件,。,Mathematica和MATLAB求解,Mathematica命令,可用于求解各种形式的线性规划问题的命令。命令的输入格式：,c=c,1,x,1,+c,2,x,2,+,+,c,n,x,n,；,m=a,11,x,1,+a,12,x,2,+,+a,1n,x,n,=b,1,，,a,m1,x,1,+a,m2,x,2,+,+,a,mn,x,n,=,b,m,；,用于求极小值的命令：,ConstrainedMinc,，,m,，,x,1,x,2,x,n,用于求极大值的命令：,ConstrainedMaxc,，,m,，,x,1,x,2,x,n,专用来求解极小值的线性规划命令,矩阵形式的线性规划命令的输入格式是：,c=c,1,c,2,c,n,；,m=-a,11,-a,12,-a,1n,，,-a,m1,-a,m2,-,a,mn,b=-b,1,-b,2,-,b,m,LinearProgrammingc,m,b,MATLAB命令命令输入格式及线性规划模型如下：,其中：x0是算法迭代的初始点；nEq表示等式约束的个数。,三、建模举例,例2.4,营养配餐问题,。每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-3中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20,kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜，为了使,费用最小,又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？,表2-3,问题分析与模型建立,设 分别表示下一周内应当供应的青,豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：,约束条件：,铁的需求量至少6个单位数：,磷的需求量至少25个单位数：,维生素A的需求量至少17500个单位：,维生素C的需求量至少245个单位：,烟酸的需求量至少5个单位数：,每周需供应140千克蔬菜，即,0,x,1,40 0,x,2,40 0,x,3,40 0,x,4,20 0,x,5,40 0,x,6,40,问题是满足营养素要求的条件下，所需费用最小，,是一个线性规划模型。,利用Matlab软件编程序：,%营养配餐ch61%文件名：ch61.mc=5;5;8;2;6;3;A=(-1)*1,1,1,1,1,1;,0.45,0.45,1.05,0.40,0.50,0.50;,10,28,59,25,22,75;,415,9065,2550,75,15,235;,8,3,53,27,5,8;,0.30,0.35,0.60,0.15,0.25,0.80;,b=(-1)*140;6;25;17500;245;5;,xLB=zeros(6,1);,xUB=40;40;40;20;40;40;,nEq=1;,x0=0*ones(6,1);,x=lp(c,A,b,xLB,xUB,x0,nEq);,disp(,青豆需要的份数,),x(1),disp(,胡罗卜需要的份数,),x(2),disp(,菜花需要的份数,),x(3),disp(,白菜需要的份数,),x(4),disp(,甜菜需要的份数,),x(5),disp(土豆需要的份数),x(6),执行后输出,青豆需要的份数,ans=40,胡罗卜需要的份数,ans=40.0000,菜花需要的份数,ans=0,白菜需要的份数,ans=20.0000,甜菜需要的份数,ans=0,土豆需要的份数,ans=40,最小费用,ans=560.0000,四、整数线性规划,在许多线性规划模型中，变量取,整数,时才有意义。例如，不可分解产品的数目，如汽车、房屋、飞机等，或只能用整数来记数的对象。这样的线性规划称为整数线性规划，简称整数规划，记为IP。,整数规划分为两类：一类为纯整数规划，记为PIP，它要求问题中全部变量都取整数；另一类是混合整数规划，记之为MIP，它的某些变量只能取整数，而其他变量则为连续变量。整数规划的特殊情况是0-1规划，其变量只取0或者1；图论中的一些问题（如,背包问题,等）也可用0-1规划来描述。,在整数规划模型中，若每一变量只取0或1，即为,0-1规划模型,。0-1规划模型因其特殊性，又不同于整数规划的解法。如一般0-1规划的隐枚举法，指派问题中的匈牙利法，背包问题则可以用动态规划的方法求解。,下面的几个例子说明了0-1规划在实际问题中的使用。,例5.2,背包问题,有n件物品，编号为,1，2，n。第 件重为 kg，价值为 元。今一装包者欲将这些物品装入一包，其质量不能超过 kg，问应装入哪几件价值最大？,解 引入变量,将 物品装包,不将 物品装包,于是得问题的模型为,取0或1，i=1，2，n,背包问题看似简单，但应用很广，例如某些,投资问题,即可归入背包问题模型。此类问题可以,描述为：设有总额为 元的资金，投资几项事业，第 项副业需投资 元，利润为 元问应选择哪些项总利润为最大？,例2.6,某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小。若10个井位的代号为 ，相应的钻探费用为 ，并且井位选择要满足下列限制条件：,（1）或选 和 ，或选 ；,（2）选择了 或 就不能选 ，反之亦然；,（3）在 中最多只能选两个。,试建立其数学模型：,解 引入变量,选择,不选择,于是以上问题的数学模型为：,例2.7,指派问题。,有 项任务，由 个人来完成，每人只能干一件，第 个人完成第 项任务需要的时间为 小时，问怎样安排能使总用时最少？,解 引入0-1型变量,人完成 任务,人不去完成 任务,于是该问题的数学模型为,整数规划的解法较复杂,，,主要有分枝定界法、割 平面法，隐枚举法及解指派问题的匈牙利法等。,分配甲、乙、丙、丁去完成A、B、C、D四项任务，每人完成一项，每项任务只能由一个人去完成，试做出任务分配使总时间最少。（个人完成各项任务如下表）,个人完成各项任务如下表,任务,人员,A,B,C,D,甲,8,6,10,9,乙,9,12,7,11,丙,7,4,3,5,丁,9,5,8,11,编写Lingo程序如下,model:,sets:,worker/w1.w4/;,job/j1.j4/;,links(worker,job):c,x;,endsets,data:,c=8,6,10,9,9,12,7,11,7,4,3,5,9,5,8,11;,enddata,min=sum(links:c*x);,for(worker(i):sum(job(j):x(i,j)=1);,for(job(j):sum(worker(i):x(i,j)=1);,for(links:bin(x);,end,Lingo的语法规定：,1.Lingo,模型语句以”model:”开头，以”end”结束，对于简单的模型，这两句可以省略；,2.,求目标函数的最大值或最小值分别用Max=或Min=标示；,3.,每个语句必须以“；”结束，每行可以有多个语句，语句可以跨行；,4.,以！开头，以“；”号结束的语句是注释语句；,5.,如果对变量的取值范围无特殊说明，则默认所有决策变量为非负。,讨论题,1、某市场研究小组考虑下一步如何选择广告竞争计划，在进行大量的调查研究后，制定了各种可供选择的方案，方案的特征数字如下：,广告计划的目的是,使受影响的顾客数为最大,。上表所给出的资源限制（资金、设计员和推销员）外，还有如下约束条件：（1）如果决定发起推销运动，那么必须同时用电台或流行杂志配合；（2）公司不能同时在商业杂志和流行杂志上作广告。假定各种广告手段所影响的顾客不同，不重复（即每一顾客只受一种广告手段影响），问如何开展广告宣传？,