数学建模--整数规划.pptVIP

;第三局部整数规划;例1整数规划问题;设设应购进甲、乙机床台数分别为x1和x2，工厂的收益为z。;formatshort

c=[-3;-2];

a=[2,3;4,2];

b=[14;18];

lb=[0;0];

[x,Fval]=linprog(c,a,b,[],[],lb);1〕不考虑解的整数限制，问题B的最优解：x1=3.25，x2=2.5，最优值：z=14.75;?;2.模型求解;4〕对问题B1在进行分枝，得问题B11和B12;求解问题B11和B12得到：;整数规划;整数规划;整数规划;分枝定界法

〔1〕分枝：通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；

〔2〕定界：并且对每个子集内的解集计算一个目标下界〔对于最小值问题〕，这称为定界。

〔3〕剪枝：在每次分枝后，但凡界限超出可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。

求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题。;分枝定界法步骤

〔1〕求解整数规划问题A对应的线性规划问题B〔松弛问题〕；

〔2〕分枝，在松弛问题B的最优解中任选一个不符合整数条件的变量xj，其值为bj，以[bj]表示小于bj的最大整数，构造两个约束条件

将这两个约束条件，分别参加问题B，求两个后继规划问题B1和B2。;?;·········;x1≤3;;

某公司拟在市东、西、南三区建立门市部，拟议中有7个位置Ai(i=1,2,…,7)可供选择。规定

在东区，由A1，A2，A3三个点中至多项选择两个；

在西区，由A4，A5两个点中至少选一个；

在南区，由A6，A7两个点中至少选一个。

如选用Ai点，设备投资估计为bi元，每年可获利润估计为ci元，但投资总额不能超过B元。问应选择哪些点可使年利润最大？

;s.t.;0-1型整数规划;某厂拟用集装箱托运甲乙两种货物，每箱的体积、重量、可获利润以及托运所受限制如表格所示。问两种货物各托运多少箱，可使获得利润为最大?;0-1型整数规划;0-1型整数规划;相互排斥的约束条件;有三种自然资源被用于生产三种产品，资源量、产品单件可变费用及售价、资源单位消耗量及组织三种产品生产的固定费用如下表。要求制订一个生产方案，使总收益最大。;;0-1型整数规划解法;0-1型整数规划解???;0-1型整数规划解法;解法二〔优化〕：重新排列xj的顺序(系数递减);0-1型整数规划计算表;;⑵如约束条件为≤，两边同乘(-1)；如约束条件为等式，

可令变量，代入目标函数和其它约束条件中，将xn消掉。;调整后的0-1规划问题变为：;步骤3：分支和定界。依次令各变量分别取0或1，将问题划分为两个子问题，分别检查解是否可行，如不可行继续对边界值较小的子问题分支，直到找出一个可行解为止，这时得到值的一个上界。;步骤4：考察所有子问题，有以下四种情况：;分支③边界值=-6＜-4，但相应的解不可行，需继续分支。过程如上图所示。;上述求解过程也可用表格表示：;所以，最优解：;

;二、指派问题的数学模型;某单位现在Ａ、Ｂ、Ｃ、Ｄ四项工作需完成，现在甲、乙、丙、丁四个人均可完成这四项任务。每人完成各项任务所用的时间如右表所示，问应指派何人去完成何项任务，使所需时间最少？;指派问题数学模型的性质：;三、指派问题的解法〔匈牙利法〕;经第一步变换后，系数矩阵中每行每列都已有了0元素；只需找出n个独立的0元素，假设能找出，就以这些独立的0元素对应解矩阵中的元素为1，其它作为0，这就得到最优解。找独立0元素的步骤如下：;

;min;第三步：作最少的直线覆盖所有0元素，以确定该系数矩阵中能找到最多的独立0元素数。;第四步：对第三步所得矩阵进行变换，目的是增加0元素。;第五步：系数矩阵(bij)中找出n个独立的0元素；那么令解矩阵(xij)中对应这n个独立的0元素取值为1，其它元素取值为0。;练习：有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：;解：用匈牙利法求解过程如下：;四、非标准形式的指派问题〔选学〕;1、求最大化的指派问题;2、人数和任务数不等的指派问题;3、一个人可做几件事的指派问题;例9：分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。;1、m约束条件中只有k个起作用;2、约束条件的右端项可能是