数学建模专题

数学建模专题

——柏庆国中国古代马鞍数学建模马克思说：任何一门学科只有运用了数学才能称为科学。数学建模对于现实世界的一个特定对象，为了一个特定目的，根据特有的内在规律，做出一些必要的简化假设，运用恰当的数学工具，得到一个数学结构。模型分类

占绝对优势的模型可以归为三类：最优化模型动态模型概率模型数学建模例1常山机器厂生产1、2两种产品，这两种产品都要分别在A、B、C三种不同的设备上加工，按工艺资料规定，生产每件产品1需要占用设备分别为2h、4h、0h；生产每件产品2，需要占用设备分别为2h、0h、5h。已知各设备计划期内用于生产这两种产品的能力分别为12h、16h、15h；又知每生产一件产品1企业能获得2元利润，每产一件产品2企业能获得3元利润。问：该企业应安排生产两种产品个多少件使总的利润最大？模型求解例２：货物打折的存贮模型某生产商为销售产品，对于前来采购的商店采取打折优惠活动试对此商店的库存与销售情况，建立数学模型模型分析：商店首先要采购一定数量的此种物品，将其放在仓库中，而具体一段时间内采购多少，主要取决于这时期内销售多少。因此我们可对某种物品的需求量划分若干个时期，在同一时期内需求是常数，但在不同时期内需求是变化的。另外商家到生产上订货时，还需考虑不同时期生产上给出的优惠是不同的。因此建立数学模型的目的就是制定最有存贮策略，即多长时间订一次货，每次订多少货，使总的费用最少。什么方法才是好的？很强的理论结果，漂亮的证明?

不管白猫黑猫，抓住老鼠就是好猫！模型求解提出问题选择建模方法推导模型的数学表达式求解模型回答问题演示文稿

后

等我们所讲的模型离散模型1.整数规划模型2.图优化模型3.不规则离散优化模型4.离散概率模型所属学科：计算机、运筹学与控制论、概率的交叉学科一、整数规划1、整数规划的数学模型2、整数规划解法3、0-1整数规划4、指派问题及解法1.整数规划数学模型

在许多经济管理的实际问题中，决策变量只有非负整数才有实际意义。对求整数最优解的问题，称为整数规划。又称约束条件和函数均为线性的IP为整数线性规划。根据变量取整数的情况,将整数规划分为：（1）纯整数规划，所有变量都取整数.（2）混合整数规划，一部分取整数,一部分取实数。（3）0-1整数规划,所有变量均取0或11.整数规划数学模型例3.某厂拟用集装箱托运甲、乙两种货物，每箱的体积、重量、可获的利润以及托运所受限制如下。问：两种货物各托运多少箱，使利润最大？货物体积重量利润甲乙54252010托运限制24131.整数规划数学模型2.整数规划的解法枚举法分支定界法割平面法智能算法2.整数规划的解法分支定界法例：2.整数规划的解法分支定界法步骤：1.寻找替代问题说明(1)若替代问题无可行解，则原问题无可界，停止；（2）若替代问题有最优解，且符合原问题的整数条件，则替代问题的最优解就是原问题的最优解；（3）若替代问题有最优解，且不符合原问题的条件，则分支。2.分支3.定界4.剪支2.整数规划的解法割平面法思路：不考虑某个变量的整数约束这一条件，但增加线性约束条件（割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解。如此进行使得切割最终的得到这样的可行域，它的一个整数坐标的极点恰好是问题的最优解。3.0-1整数规划问题特征：包含的变量取0或1.构造0-1整数规划模型所利用的条件m个约束条件中只有k起作用。约束条件的右端项可能是r个值中的某一个，即3.两组条件中满足其中一组。例4

某城市消防总部将全市划分为11个防火区，设有4个消防站，下图中表示了各防火区域与消防站的位置，其中①，②，③，④表示消防站，1，2，3，……，11表示消防区域。根据历史资料证实，各消防站可在事先规定的允许时间内对所负责的地区火灾予以消灭，图中虚线即表示各地区由哪个消防站负责（没有虚线连接就表示不负责），现在总部提出，在同样负责全市消防的前提下，是否可以减少消防站的数目？如果可以，应当关闭哪个？①②③④1287345611910解：令对各防火区域可分别列出以下约束条件：防火区1：防火区2：防火区3：防火区4：防火区5：防火区6：防火区7：防火区8：防火区9：防火区10：防火区11：由上述约束条件知：必须x1,x3,x4为1，x2可为0，也可为1，由此，消防站②可以关闭而不影响任务的执行

在实际中经常会遇到这样的问题，有n项不同的任务，需要n个人分别完成其中的一项，使完成n项任务的总效率最高（或所需时间最少），这类问题称为指派问题或分派问题。

（一）指派问题的数学模型设n个人被分配去做n件工作，规定每个人只做一件工作，每件工作只有一个人去做。已知第i个人去做第j件工作的的效率（时间或费用）为Cij。问应如何分配才能使总效率（时间或费用）最高？4.指派问题例：

任务人员ABCD甲21097乙154148丙13141611丁415139设决策变量1分配第i个人去做第j件工作

xij=0相反(i,j=1.2.…n)其数学模型为：理论结果定理1.从系数矩阵中一行（列）各元素分别减去该行（列）的最小元素得到新的矩阵，则以新的矩阵为系数矩阵求得到最优解和原系数矩阵求得最优解相同。定理2.若矩阵A的元素可分成0与非0两部分，则覆盖0元素的最少直线数等于位于不同行不同列的0元素的个数。定理3.在系数矩阵中若能找到n个不同行不同列的0元素，则令解矩阵中对应的这个n个不同行不同列0元素的值为1，其他元素的值为0，则该解即为最优。解题步骤

指派问题是0-1规划的特例，也是运输问题的特例，当然可用整数规划，0-1规划或运输问题的解法去求解，这就如同用单纯型法求解运输问题一样是不合算的。利用指派问题的特点可有更简便的解法，这就是匈牙利法。

第一步：变换系数矩阵。

(1)从（cij）的每行元素都减去该行的最小元素；

(2)再从所得新系数矩阵的每列元素中减去该列的最小元素。

保证每行、每列至少一个0元素。第二步：寻找独立零元素。

(1)从只有一个0元素的行(列)开始，给这个0元素加圈，记作◎，然后划去◎所在列和行的其它0元素，记作Ø

。

(2)如果所在行（列）中有多个0元素，任选一个加圈，记作◎

，同时，划去◎所在列和行的其它0元素。

(3)反复进行上述几步，直到所有0元素都被圈出和划掉为止。

(4)

若◎元素的数目m等于矩阵的阶数n，那么这指派问题的最优解已得到。若m<n,则转入第三步。

第三步：作最少的直线覆盖所有0元素。

(1)对没有◎的行打√号；

(2)对已打√号的行中所有含Ø元素的列打√号；

(3)再对打有√号的列中含◎元素的行打√号；(4)重复(2)，(3)直到得不出新的打√号的行、列为止；

(5)对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数

第四步：变换矩阵，增加0元素。在没有被直线覆盖的所有元素中找出最小元素，未被覆盖的各行（或列）都减去这最小元素，如果出现负元素，则在该列（或行）都加上这最小元素（以保证系数矩阵中不出现负元素）。转回第二步。例：

任务人员ABCD甲215134乙1041415丙9141613丁78119249742◎Ø◎ØØ◎◎有一份中文说明书，需译成英、日、德、俄四种文字，分别记作A、B、C、D。现有甲、乙、丙、丁四人，他们将中文说明书译成不同语种的说明书所需时间如下表所示，问如何分派任务，可使总时间最少？

任务人员ABCD甲67112乙4598丙31104丁5982例：求解过程如下：第一步，变换系数矩阵：－5第二步，独立0元素：◎◎◎ØØ找到3个独立零元素但m=3<n=

4第三步，作最少的直线覆盖所有0元素：

◎◎◎ØØ√√√独立零元素的个数m=3<n=4；第四步，变换矩阵(bij)以增加0元素：没有被直线覆盖的所有元素中的最小元素为1，然后打√各行都减去1；打√各列都加上1，得如下矩阵，并转第二步进行试指派：000

0

00得到4个独立零元素，所以最优解矩阵为：

◎◎◎ØØ√√√-1◎◎Ø-115◎◎◎ØØ◎特殊的指派问题1．最大化指派问题构造系数矩阵（max-Cij）2．人、事不对等指派问题添上虚拟的人或者事，回忆运输问题？3．一人做几事的指派问题将此人看作N个相同的人。4．某人一定不做某事的指派问题

其费用无穷大或者利润无穷小。

从甲、乙、丙、丁、戊五人中挑选四人去完成四项工作。已知每人完成各项工作的时间如表所示。规定每项工作只能由一个人去单独完成，每个人最多承担一项任务。又假定对甲必须保证分配一项任务，丁因某种原因决定不同意承担第4项任务。在满足上述条件下，如何分配工作，使完成四项工作总的花费时间为最少。甲乙丙丁戊1234105152021051531514131527694158

分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。

ABCDE甲乙丙丁2539342429382742312628364220402337333245其他应用举例某大学计算机实验室聘用4名大学生（代号1，2，3，4）和2名研究生（代号5，6）值班答疑。已知每人从周一至周五最多可安排的值班时间及每人每小时值班的报酬如下表。问：该实验室安排一张人员的值班表使总支付的报酬最少？每天最多可安排的值班时间学生报酬（元/h）周一周二周三周四周五12345610109.99.810.811.360607060604830