数学建模-数学规划.

陈旺虎[e-mail]内容安排•数学规划•线性规划•线性规划的软件解法•整数规划•目标规划1.数学规划•数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。•七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。•时至今日数学规划仍然是运筹学领域中热点研究问题。•从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。数学规划模型的一般表达式：为目标函数，为约束函数，为可控变量，为已知参数，为随机参数。minmax,,fx..,,0stgxfgx数学规划模型2.线性规划•线性规划模型是运筹学的重要分支，是20世纪三四十年代初兴起的一门学科。•1947年美国数学家丹齐格G.B.Dantzig及其同事提出的求解线性规划的单纯形法及有关理论具有划时代的意义。他们的工作为线性规划这一学科的建立奠定了理论基础。•随着1979年前苏联数学家哈奇扬的椭球算法和1984年美籍印度数学家卡玛卡尔H.Karmarkar算法的相继问世，线性规划的理论更加完备成熟，实用领域更加宽广。•线性规划研究的实际问题多种多样，如生产计划问题、物资运输问题、合理下料问题、库存问题、劳动力问题、最优设计问题等。•就模型而言，线形规划模型类似于高等数学中的条件极值问题，只是其目标函数和约束条件都限定为线性函数。•线性规划模型的求解方法目前仍以单纯形法为主要方法。•本节将介绍的主要内容–线性规划模型的建立及标准形式；–线性规划模型的解和单纯形法；–整数线性规划模型及建模案例等。例2.1生产组织与计划问题某工厂计划生产甲、乙两种产品，主要材料有钢材3600kg、专用设备能力3000台时。材料与设备能力的消耗定额以及单位产品所获利润如下表所示问如何安排生产，才能使该厂所获利润最大？产品单位产品消耗定额材料与设备甲（件）乙（件）现有材料与设备能力钢材（kg）铜材（kg）设备能力（台时）单位产品的利润（元）943600452000310300070120•设甲、乙两种产品计划生产量分别为x1和x2件，总的利润为Z元•那么,我们的任务就是：求变量的值为多少时，才能使总利润最大?•由已知条件，x1和x2要受下列限制：–(1)生产甲、乙两种产品所用钢材的总数不能超过现有钢材数，即––(2)生产甲、乙两种产品所用铜材的总数不能超过现有铜材数，即––(3)生产两种产品所用的设备能力的总数不能超过现有设备能力的台时数，即1270120zxx12943600xx12452000xx123103000xx建模过程–(4)甲、乙两种产品的计划生产量不能为负数，即问题转化为求解如下的条件极值（数学模型）：120,0xx12max70120zxx12121212943600452000..31030000,0xxxxstxxxx建模过程•设有m种物质，第i种物资的库存量为bi•每种物资都可以生产n种产品,第i种物资生产第j种产品时，每生产单位产品所需物资量为aij•每种物资生产第j种产品时，每单位产品可获利润Cj（如下表）•问如何组织生产才能使利润最大？例2.2最大利润问题•用xj表示生产第j种产品计划数，则问题归结为如下数学问题：•约束条件的意义是：每种原料生产n种产品所需要的资源总量不能超过该种资源的库存量；每种产品的生产计划数不能为负。njjjnxcxxxf1,21)...,,(maxmibxaxxgtsinjjijni,...,1,),...,(..11njxj,...,1,0建模过程•设某类物资有m个产地，有n个销售地.•第i个产地的产量为ai,第j个销售地的需要量为bj.•从产地i到销售地j运输单位物资的运价（单价）为Cij.•今考虑在产销平衡的条件下，即•应如何组织运输，才能使得即满足各地的需要，又使总运费最小。11mnijijab例2.3运输问题•用xij表示产地i供给销地j的物资数量，则问题变成在产销平衡条件下，求解以下数学问题：考察上述几个问题的数学模型，他们的目标函数及约束函数都是自变量的线性函数，故称这类数学问题为线性规划问题。1..1,2,,mijjistxbjn11,2,,nijijxaim0ijx11minmnijijijzcx建模过程•类似的问题很多–诸如下料问题、配料问题、分配问题、工厂选址问题等等。–解决方法都归结为上述的线性规划问题，只是约束条件有的是等式，有的是不等式。•通过以上例子可以看出–尽管所提问题的内容不同，但从构成数学问题的结构来看，却属于同一类优化问题，其结构具有如下特征：（1）目标函数是决策变量的线性函数。（2）约束条件都是决策变量的线性等式或不等式。总结•称如下的条件极值问题为标准的线性规划问题。njxmibxaxxgtsxcxxfLPjnjijijnnjjjn,...,1,0,...,1,),...,(..),...,(min1111线性规划的解法概述若引进记号则（LP）可简单地表示为进一步，若令则（LP）可表示为：11,,,,,,TTnncccbbbminTfxcx..stAxb0x,0nDxRAxbxxCxfTDx)(minnmijTnaAxxx)(,),...,(对于非标准形式的线性规划，可通过下列办法化成标准形式。①若求,可化为求.②若约束条件中含有不等式或则可引进新变量（称为松弛变量），化为等式约束：或③今后总假定，否则在等式两边乘以-1即可。④若变量无非负限制，则引入两个非负变量与令，便可化为标准形式。maxfxAxbAxb1nx1nAxxb1nAxxb0bjx))(min(xfjxjxjjjxxx（1）单纯形法1947年由美国数学家Dantzig提出；虽然在特殊情况下可能出现循环，但这种方法仍是目前求解线性规划问题最常用的方法；事实上在大量的实际问题计算中看出，循环情况从未出现过（仅在特意构造下才能出现）；是一种迭代方法。（2）椭球法1977年由前苏联数学家khachiyan提出的多项式时间算法；它在理论上保证了多项式时间算法的存在性；但大量数值研究发现，对于大多数实际问题，椭球法在计算上不如单纯形方法。解法概述（3）Karmarkar内点法1983年由美籍印度数学家Karmarkar提出的；也是一种多项式时间算法，在大多数情况下比单纯形算法的计算速度要快。（4）图上作业与表上作业法前一种是50年代由我国数学工作者提出的，后者是1950年Dantzing提出的；这二种方法主要是为解决运输问题（特殊的线性规划）而设计的。据统计在用线性规划解决的实际问题中，70%以上属于运输问题类型。3.线性规划问题的软件解法求解线性规划的常用方法是1947年G.B.Dantzig提出的单纯形法。这种方法是以寻找最优解的迭代过程为主线。基本思路是给出一个基可行解（一个顶点）后，判断其是否为最优解；若它不是最优解，可用迭代的方法转换到另一个基可行解（顶点），最终找到使目标函数值更优的基可行解。经过有限次迭代后，这一迭代过程以找到最优解或判定问题无最优解为目标。求解线性规划的软件很多，下面介绍Mathematica和MATLAB软件。Mathematica和MATLAB求解•Mathematica命令1.可用于求解各种形式的线性规划问题的命令，输入格式：c=c1x1+c2x2+…+cnxn；m={a11x1+a12x2+…+a1nxn=b1，…am1x1+am2x2+…+amnxn=bm}；•用于求极小值的命令：ConstrainedMin[c，m，{x1,x2,…,xn}]•用于求极大值的命令：ConstrainedMax[c，m，{x1,x2,…,xn}]2.专用来求解极小值的线性规划命令矩阵形式的线性规划命令的输入格式是：c={c1,c2,…,cn}；m={{-a11,-a12,…,-a1n}，…{-am1,-am2,…-amn}}b={-b1,-b2,…,-bm}LinearProgramming[c,m,b]0.minXbAXtsXCfT•MATLAB命令命令输入格式及线性规划模型如下：1.其中：x0是算法迭代的初始点；nEq表示等式约束的个数。2211.'minbxAbxAtsxcfxUBxxLB2121,bbbAAA建模举例•例2.4营养配餐问题。–每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。–某医院营养室在制定下一周菜单时，需要确定表中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。–规定白菜的供应一周内不多于20kg，其它蔬菜的供应在一周内不多于40kg，每周共需供应140kg蔬菜–为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少kg？每份所含营养素单位数每千克费用序号蔬菜铁磷维生素A维生素C烟酸1青豆0.451041580.3052胡萝卜0.4528906530.3553菜花1.05592550530.6084白菜0.402575270.1525甜菜0.50221550.2566土豆0.507523580.803要求蔬菜提供的营养6.0025175002455.00问题分析与模型建立设分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：约束条件：（1）铁的需求量至少6个单位数：（2）磷的需求量至少25个单位数：(1~6)ixi123456558263fxxxxxx1234560.450.451.050.400.500.506xxxxxx12345610285925227525xxxxxx（3）维生素A的需求量至少17500个单位：（4）维生素C的需求量至少245个单位：（5）烟酸的需求量至少5个单位数：（6）每周需供应140千克蔬菜，即12345641590652550751523517500xxxxxx12345683532758245xxxxxx1234560.300.350.600.150.250.805xxxxxx123456140xxxxxx0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40123456123456123456123456123456123456min558263.1400.450.451.050.400.500.5061028592522752541590652550751523517500835327582450.3fxxxxxxstxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx12345600.350.600.150.250.805xxxxxx问题是满足营养素要求的条件下，所需费用最小，是一个线性规划模型。利用Matlab软件编程序：%营养配餐%文件名：plan.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;%nEq表示等式约束的个数x0=