数学建模第二章整数规划2研究报告.ppt

%解：编写Matlab 程序如下： c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5 8 4 2 3 5;9 10 6 9 10]; c=c(:); a=zeros(10,25); for i=1:5 a(i,(i-1)*5+1:5*i)=1; a(5+i,i:5:25)=1; end b=ones(10,1); [x,y]=bintprog(c,[],[],a,b); x=reshape(x,[5,5]),y %求得最优指派方案为 x51 =x44= x32 =x23= x15 = 1 最优值为21。 2.5 分枝定界法 对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系统有哪些信誉好的足球投注网站，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。 分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解 整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。 设有最大化的整数规划问题 A ，与它相应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A的整数条件，那么B的最优目标函数必是A的最优目标函数z*的上界，记作 ,而A的任意可行解的目标函数值将是z*的一个下界 分枝定界法就是将B的可行域分成子区域的方法。逐步减小 和增大 最终求到z*。现用下 例来说明： 解 （i）先不考虑整数限制，即解相应的线性规划B ，得最优解为： 可见它不符合整数条件。这时z 是问题A的最优目标函数值z*的上界，记作 。而x1=0, x2 = 0 显然是问题A的一个整数可行解，这时z = 0，是z*的一个下界，记作 ， 即0 ≤ z* ≤ 356。 （ii）因为 x1, x2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选x1进行分枝，把可行集分成2 个子集： 因为 4 与5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这一步称为分枝。这两个子集的规划及求解如下： 再定界： （iii）对问题B1再进行分枝得问题 B11和B12 ，它们的最优解为 （iv）对问题B2再进行分枝得问题 B12和 B22 ，它们的最优解为 于是可以断定原问题的最优解为： 从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为： 开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问题B 。 （i）解问题B 可能得到以下情况之一： （a） B 没有可行解，这时A 也没有可行解，则停止． （b） B 有最优解，并符合问题A 的整数条件， B 的最优解即为A 的最优解，则停止。 （c） B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为 （ii）用观察法找问题A的一个整数可行解，一般可取 x j =0, j = 1,…. ,n，试探求得其目标函数值，并记作 。以z*表示问题A的最优目标函数值；这时有 进行迭代。 第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量 xj ，其值为 b j ，以[b j] 表示小于bj的最大整数。构造两个约束条件 xj ≤ [b j] 和 xj ≥ [b j] 将这两个约束条件，分别加入问题B ，求两个后继规划问题B 1和 B 2 。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界 。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界 ，若无作用 不变。 第二步：比较与剪枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。若大于 ，且不符合整数条件，则重复第一步骤。一直到最后得到z* = 为止。得最优整数解x * j . j =1.2….n 。 剪枝的条件 1.无可行解的分支；2.得到整数解的分支； 3.目标函数值小于下界的分支 补充 生产与销售计划问题 例9 某公司用两种原油（ A 和B ）混合加工成两种汽油（甲和乙）。甲、乙两种汽