数学建模第五章数学规划模型.ppt

《数学建模第五章数学规划模型.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学建模（MathematicalModeling)黑龙江科技学院理学院工程数学教研室第五章数学规划模型黑龙江科技学院数学建模理学院第五章数学规划模型数学规划论起始20世纪30年代末，50年代与60年代发展成为一个完整的分支并受到数学界和社会各界的重视。七八十年代是数学规划飞速发展时期，无论是从理论上还是算法方面都得到了进一步完善。时至今日数学规划仍然是运筹学领域中热点研究问题。从国内外的数学建模竞赛的试题中看，有近1/4的问题可用数学规划进行求解。黑龙江科技学院数学建模理学院动态规划模型数学规划模型第五章非线性规划模型重点:数学规划模型的建立和求解难点:数学规

2、划模型的基本原理及数值计算线性规划模型黑龙江科技学院数学建模理学院建模举例多目标规划模型整数规划模型1、例1：某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用A，B机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用A，B，C三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A机器10小时、B机器8小时和C机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？黑龙江科技学院数学建模理学院设该厂生产x1台甲机床和x2台乙机床时总利润最大，则x1,x2应满足:目标函数:约束条件:黑龙江科技学院数

3、学建模理学院一般线性规划问题的标准型为线性规划的Matlab标准形式黑龙江科技学院数学建模理学院线性规划模型矩阵的形式：例如线性规划Matlab标准型为黑龙江科技学院数学建模理学院4、线性规划的图解法本例的最优解为最优目标值黑龙江科技学院数学建模理学院5、求解线性规划的Matlab解法单纯形法是首先由GeorgeDantzig于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先找出可行域的一个极点，据一定规则判断其是否

4、最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到找到某一最优解为止。黑龙江科技学院数学建模理学院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是控制参数。黑

5、龙江科技学院数学建模理学院例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即可得所求结果。黑龙江科技学院数学建模理学院例5.1.3求解线性规划问题解编写Matlab程序如下：c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a

6、,-b,[],[],zeros(3,1))黑龙江科技学院数学建模理学院例5.15拟分配n人去干n项工作，每人干且仅干一项工作，若分配第i人去干第j项工作，需花费cij单位时间，问应如何分配工作才能使工人花费的总时间最少？引入变量xij，若分配i干j工作，则取xij=1，否则取xij=0。上述指派问题的数学模型为:指派问题黑龙江科技学院数学建模理学院可行解既可以用一个矩阵(称为解矩阵)表示，其每行每列均有且只有一个元素为1，其余元素均为0，也可以用1,…,n中的一个置换表示。求解指派问题的匈牙利算法由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更

7、为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C=cij一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B=bij，则以C或B为系数矩阵的指派问题具有相同的最优指派。黑龙江科技学院数学建模理学院可将原系数阵C变换为含零元素较多的新系数阵B，而最优解不变。若能在B中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为0，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。黑龙

8、江科技学院数学建模理学院