一、实验目的：

1. 掌握分支定界法原理。整数规划求解的分枝定界法，首先确定目标函数的一个初始上下界，然后通过逐步分支使上界减小，下界增大，直到两者相等时，就求出了最优值和最优解。

2. 掌握用数学软件求解整数规划的方法；

3. 实验从算法思想、实验步骤与程序、运行结果、结果分析与讨论等几方面完成；

4. 预习整数规划的求解方法原理分枝定界法的基本思想。

二、实验内容

1. 题目：求解下列0-1整形规划问题

数学模型：

程序代码：

MODEL:

MAX=3*X1-2*X2+5*X3;

X1+2*X2-X3<2;

X1+4*X2+X3<4;

X1+X2<3;

4*X2+X3<5;

@BIN(X1);

@BIN(X2);

@BIN(X3);
END

程序执行结果：

结果解释：

该模型为PILP（纯整数线性规划）。当x1取1,x2取0,x3取1时,z取得最大值8.

变量x1对应的Reduced cost值为-3，表示当前非基变量x1的值增加一个单位时，目标函数减少-3，即最优目标函数值为8+3=11；变量x2对应的Reduced cost值为0，即x2为基变量；变量x3对应的Reduced cost值为-5，表示当前非基变量x1的值增加一个单位时，目标函数减少-5，即最优目标函数值为8+5=13；

1. 题目：有四个工人，要指派他们分别完成4项工作，每人做各项工作所

消耗的时间如下表：

问指派哪个人去完成哪项工作，可使总的消耗时间为最小？

数学模型：

程序代码：

MODEL:

sets:

worker/1..4/;

job/1..4/;

link(worker,job):c,t;

endsets

data:

t=15 18 21 24

  19 23 22 18

   26 17 16 19

   19 21 23 17;

enddata

min=@sum(link:c*t);

@for(job(j):@sum(worker(i):c(i,j))=1); @for(worker(i):@sum(job(j):c(i,j))=1);

@for(link:@bin(c));

end

程序执行结果：

结果解释：

该模型为纯整数线性规划（PILP）。派遣甲完成工作2，乙完成工作1，丙完成工作3，丁完成工作4，可使总的消耗时间最短为70。变量c12对应的Reduced cost值为18，表示当前非基变量c12的值增加一个单位时，目标函数减少18，即最优目标函数值为70-18=52；变量c21对应的Reduced cost值为19，表示当前非基变量c21的值增加一个单位时，目标函数减少19，即最优目标函数值为70-19=51；变量c33对应的Reduced cost值为16，表示当前非基变量c33的值增加一个单位时，目标函数减少16，即最优目标函数值为70-16=54；变量c44对应的Reduced cost值为17，表示当前非基变量c44的值增加一个单位时，目标函数减少17，即最优目标函数值为70-17=53。

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

数学模型：

程序代码：

model:

sets:

worker/1..4/;

job/1..4/;

link(worker,job):c,t;

endsets

data:

t=6 7 11 2

  4 5 9 8

  3 1 10 4

  5 9 8 2;

enddata

min=@sum(link:c*t);

@for(job(j):@sum(worker(i):c(i,j))=1);

@for(worker(i):@sum(job(j):c(i,j))=1);

@for(link:@bin(c));

end

程序执行结果：

结果解释：

该模型为纯整数线性规划（PILP）。派遣甲将中文说明书译为俄语，乙将中文说明书译为英语，丙将中文说明书译为日语，丁将中文说明书译为德语，可使总的消耗时间最短为15。

变量c14对应的Reduced cost值为2，表示当前非基变量c14的值增加一个单位时，目标函数减少2，即最优目标函数值为15-2=13；变量c21对应的Reduced cost值为4，表示当前非基变量c21的值增加一个单位时，目标函数减少4，即最优目标函数值为15-4=11；变量c32对应的Reduced cost值为1，表示当前非基变量c32的值增加一个单位时，目标函数减少1，即最优目标函数值为15-1=14；变量c43对应的Reduced cost值为8，表示当前非基变量c43的值增加一个单位时，目标函数减少8，即最优目标函数值为15-8=7。

1. 题目：某钻井队要从10个可供选择的井位中确定5个钻井探油，使总

的钻探费用为最小。若10个井位的代号为s1,s2,…,s10,相应的钻探费用c1,c2,…,c10为5,8,10,6,9,5,7,6,10,8.并且井位选择上要满足下列限制条件：
（1） 或选择s1和s7,或选择钻探s9；
（2） 选择了s3或s4就不能选s5，或反过来也一样；
（3） 在s5,s6,s7,s8中最多只能选两个.

试建立这个问题的整数规划模型,确定选择的井位。

数学模型：

取0-1变量s1，若si=1,则表示选取第i个井，若si=0,则表示不选取第i个井。建立数学模型如下：

程序代码：

MODEL:

SETS:

HANG/1..10/:S,C;

ENDSETS

DATA:C=5,8,10,6,9,5,7,6,10,8;

ENDDATA

MIN=@SUM(HANG(I):S(I)*C(I));

(S(1)+S(7)-2)*(S(9)-1)=0;

S(3)*S(5)+S(4)*S(5)=0;

S(5)+S(6)+S(7)+S(8)<=2;

@SUM(HANG(I):S(I))=5;

@FOR(HANG(I):@BIN(S));

END

结果解释：

根据程序运行结果：

该模型为PILP（纯整数线性规划）。确定钻井为s1,s4,s6,s7,s10。其费用分别为5，6，5，7，8，使总费用z最少为31

当前非基变量s1的值增加一个单位时，目标函数减少5，即最优目标函数值为33-5=28；非基变量s3的值增加一个单位时，目标函数减少10，即最优目标函数值为33-10=23；非基变量s4的值增加一个单位时，目标函数减少6，即最优目标函数值为33-6=27；当前非基变量s6的值增加一个单位时，目标函数减少5，即最优目标函数值为33-5=28;当前非基变量s7的值增加一个单位时，目标函数减少7，即最优目标函数值为33-7=26。

分析与讨论：
1.描述分枝定界法的过程。

• 先求出线性规划的解。
• 确定整数规划的最优目标函数值z*初始上界和下界z。
• 将一个线性规划问题分为两枝，并求解。
• 修改最优目标函数上、下界。
• 比较与剪枝：各分枝的目标函数值中，若有小于。Z者，则剪掉此枝，表明此子问题已经探清。
• 不必再分枝了；否则继续分枝。
• 如此反复进行，直到得到Z＝Z*为止，即得最优解X*。

2.描述割平面法的过程。

在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。其构造步骤如下：

(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。

(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。