数学建模-第五章-数学规划模型

数学建模（MathematicalModeling)黑龙江科技学院理学院工程数学教研室第五章数学规划模型黑龙江科技学院数学建模理学院第五章数学规划模型数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。黑龙江科技学院数学建模理学院动态规划模型数学规划模型第五章非线性规划模型重点:数学规划模型的建立和求解难点:数学规划模型的基本原理及数值计算线性规划模型黑龙江科技学院数学建模理学院建模举例多目标规划模型整数规划模型1、例1：某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A，B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A，B，C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？黑龙江科技学院数学建模理学院设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:目标函数:约束条件:2134maxxxz0,781022122121xxxxxxx黑龙江科技学院数学建模理学院1minnjjjzcx1s.t.1,2,,nijjijaxbim112211112211211222221122min.0(1,2,,)nnnnnnmmmnnmifcxcxcxaxaxaxbaxaxaxbstaxaxaxbxin一般线性规划问题的标准型为线性规划的Matlab标准形式黑龙江科技学院数学建模理学院•线性规划模型矩阵的形式：•例如线性规划•Matlab标准型为bAxxcxTthatsuchminbAxxcxTthatsuchmaxbAxxcxTthatsuchmin黑龙江科技学院数学建模理学院0246810012345678910x2=72x1+x2=10x1+x2=8z=12(2,6)Tx)6,2(*26*z4、线性规划的图解法本例的最优解为最优目标值黑龙江科技学院数学建模理学院•5、求解线性规划的Matlab解法•单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。黑龙江科技学院数学建模理学院Matlab2008b中线性规划的标准型为：基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式（在Matlab指令窗运行helplinprog可以看到所有的函数调用形式），如：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)这里fval返回目标函数的值，Aeq和beq对应等式约束，LB和UB分别是变量的下界和上界，是的初始值，OPTIONS是控制参数。bAxxcTxsuchthatmin黑龙江科技学院数学建模理学院例5.1.2求解下列线性规划问题•解（i）编写M文件•c=[2;3;-5];a=[-2,5,-1];b=-10;aeq=[1,1,1];•beq=7;•x=linprog(-c,a,b,aeq,beq,zeros(3,1))•value=c'*x•（ii）将M文件存盘，并命名为example1.m。•（iii）在Matlab指令窗运行example1即可得所•求结果。321532maxxxxz0,,10527321321321xxxxxxxxx黑龙江科技学院数学建模理学院•例5.1.3求解线性规划问题32132minxxxz0,,62382432121321xxxxxxxx解编写Matlab程序如下：c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))黑龙江科技学院数学建模理学院例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？•引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为:11minnnijijijcxn,1,2,ji,,10,,2,1,1,,2,1,111或ijniijnjijxnjxnix指派问题黑龙江科技学院数学建模理学院•可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,…,n中的一个置换表示。•求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。黑龙江科技学院数学建模理学院可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。黑龙江科技学院数学建模理学院例5.1.6求解指派问题，其系数矩阵为•将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得16221917171822241819211722191516C06310157124074011B黑龙江科技学院数学建模理学院•再将第3列元素各减去1，得•以B2为系数矩阵的指派问题有最优指派****20531005711407301B431243210100100000100001X即黑龙江科技学院数学建模理学院•例5.1.7求解系数矩阵C的指派问题解先作等价变换如下61071041066141512141217766698979712C2636040*08957510*00*0032202*056107104106614151214121776669897971246767黑龙江科技学院数学建模理学院•容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n=5，最优指派还无法看出。此时等价变换还可进行下去。步骤如下：（1）对未选出0元素的行打；（2）对行中0元素所在列打；（3）对列中选中的0元素所在行打；重复（2）、（3）直到无法再打为止。可以证明，若用直线划没有打的行与打的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令行元素减去此数，列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。黑龙江科技学院数学建模理学院•上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5.1.7变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得•最优指派为041404008113538000034202075314254321黑龙江科技学院数学建模理学院建模举例：营养配餐问题每种蔬菜含有的营养素成份是不同的，从医学上知道，每人每周对每种营养成分的最低需求量。某医院营养室在制定下一周菜单时，需要确定表2-4中所列六种蔬菜的供应量，以便使费用最小而又能满足营养素等其它方面的要求。规定白菜的供应一周内不多于20千克，其它蔬菜的供应在一周内不多于40千克，每周共需供应140千克蔬菜，为了使费用最小又满足营养素等其它方面的要求，问在下一周内应当供应每种蔬菜各多少千克？黑龙江科技学院数学建模理学院每份所含营养素单位数每千克费用序号蔬菜铁磷维生素A维生素C烟酸1青豆0.451041580.3052胡萝卜0.4528906530.3553菜花1.05592550530.6084白菜0.402575270.1525甜菜0.50221550.2566土豆0.507523580.803要求蔬菜提供的营养6.0025175002455.00表5-4黑龙江科技学院数学建模理学院问题分析设分别表示下一周内应当供应的青豆、胡萝卜、菜花、白菜、甜菜及土豆的量，费用目标函数为：(1~6)ixi123456558263fxxxxxx1234560.450.451.050.400.500.506xxxxxx约束条件：铁的需求量至少6个单位数：磷的需求量至少25个单位数：12345610285925227525xxxxxx黑龙江科技学院数学建模理学院12345641590652550751523517500xxxxxx12345683532758245xxxxxx问题分析维生素A的需求量至少17500个单位：维生素C的需求量至少245个单位：烟酸的需求量至少5个单位数：1234560.300.350.600.150.250.805xxxxxx每周需供应140千克蔬菜，即123456140xxxxxx黑龙江科技学院数学建模理学院模型的建立123456123456123456123456123456123456min5582631400.450.451.050.400.500.50610285925227525.41590652550751523517500835327582450.3fxxxxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxx12345600.350.600.150.250.805xxxxxx0≤x1≤400≤x2≤400≤x3≤400≤x4≤200≤x5≤400≤x6≤40黑龙江科技学院数学建模理学院模型求解利用Matlab软件编程序：%营养配餐ch21%文件名：ch21mc=[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('白菜需要