分支定界法的思想是:首先确定目标值的上下界,边搜索边减掉搜索树的某些支,提高搜索效率。
原文见:
http://it.pjschool.com.cn/Article/ArticleShow.asp?ArticleID=231
例1:设有A,B,C,D,E 5人从事j1,j2,j3,j4,j5 5项工作每人只能从事一项,它们的
效益表如下:
|
j1 |
j2 |
j3 |
j4 |
j5 |
A |
13 |
11 |
10 |
4 |
7 |
B |
13 |
10 |
10 |
8 |
5 |
C |
5 |
9 |
7 |
7 |
4 |
D |
15 |
12 |
10 |
11 |
5 |
E |
10 |
11 |
8 |
8 |
4 |
求最佳安排,使效益最高?
原文代码重写如下,希望增加点可读性。
program PlanJob;
const MAX_SIZE = 20;
type
TIntArray = array[1..MAX_SIZE] of Integer;
PNode = ^Node;
Node = record
Job2Man: TIntArray; // Job2Man[n] = m, job-n assign to person-m
Man2Job: TIntArray; // Man2Job[n] = m, person-n assign to job-m
UpperVal: Integer; // upper value
JobsDep: Integer; // jobs decided, as search depth
Next: PNode;
end;
var
CurNode: PNode; // Current node
NewNode: PNode; // New branch node
DelNode: PNode; // for delete
GoalNode: PNode; // the goal
GoalMaxVal: Integer; // goal max value
CurMan, CurJob: Integer; // Current Man and Job of current Node
Size: Integer; // Person number, also task number
Values: array[1..MAX_SIZE, 1..MAX_SIZE] of Integer;
function CalUpperValue(ANode: PNode): Integer;
var
Res: Integer;
Man, Job: Integer;
JobMaxVal: Integer;
begin
Res := 0;
with ANode^ do
begin
for Job := 1 to Size do
begin
if Job <= JobsDep then
begin
Man := Job2Man[Job];
Res := Res + Values[Man, Job];
Continue;
end;
// else find the max value for Job
JobMaxVal := 0;
for Man := 1 to Size do
begin
if (JobMaxVal < Values[Man,Job]) and (Man2Job[Man] = 0) then
JobMaxVal := Values[Man,Job];
end;
Res := Res + JobMaxVal;
end; // for Job
end; // with ANode^
CalUpperValue := Res;
end;
function InitNode(): PNode;
var
Man, Job: Integer;
FInput: Text;
Res: PNode;
begin
Assign(FInput, 'input.txt');
Reset(FInput);
Read(FInput, Size);
Readln(FInput);
for Man := 1 to Size do
begin
for Job := 1 to Size do
Read(FInput, Values[Man,Job]);
Readln(FInput);
end;
New(Res);
with Res^ do
begin
for Man := 1 to Size do
begin
Man2Job[Man] := 0;
Job2Man[Man] := 0;
end;
JobsDep := 0;
UpperVal := CalUpperValue(Res);
Next := nil;
end;
InitNode := Res;
end;
procedure Insert(ANode: PNode; From: PNode);
var
PrevNode, NextNode: PNode;
begin
NextNode := From;
repeat
PrevNode := NextNode;
NextNode := PrevNode^.Next;
until (NextNode = nil) or (ANode^.UpperVal >= NextNode^.UpperVal);
PrevNode^.Next := ANode;
ANode^.Next := NextNode;
end;
procedure PrintNode(ANode: PNode);
var
Man, Job: Integer;
AllJobAssigned: Boolean;
begin
AllJobAssigned := true;
for Job := 1 to Size do
begin
Man := ANode^.Job2Man[Job];
if 0 <> Man then
Writeln('Job ', Job, ' assign to man ',
Man, ', value ', Values[Man, Job])
else
AllJobAssigned := false;
end;
Writeln;
if AllJobAssigned then
Writeln('Value = ', ANode^.UpperVal)
else
Writeln('UpperVal = ', ANode^.UpperVal);
end;
begin
CurNode := InitNode();
GoalMaxVal := 0;
repeat
CurJob := CurNode^.JobsDep + 1;
for CurMan := 1 to Size do
begin
if CurNode^.Man2Job[CurMan] <> 0 then
Continue;
// New search branch
New(NewNode);
NewNode^ := CurNode^;
NewNode^.JobsDep := CurJob;
NewNode^.Man2Job[CurMan] := CurJob;
NewNode^.Job2Man[CurJob] := CurMan;
NewNode^.UpperVal := CalUpperValue(NewNode);
if NewNode^.UpperVal < GoalMaxVal then
Dispose(NewNode) // discard this branch if smaller than limit
else
Insert(NewNode, CurNode);
if CurJob < Size then Continue; // for CurMan
// all job assigned, update goal
if NewNode^.UpperVal > GoalMaxVal then
begin
GoalNode := NewNode;
GoalMaxVal := GoalNode^.UpperVal
end; // if
end; // for CurMan
DelNode := CurNode;
CurNode := CurNode^.Next;
Dispose(DelNode);
until (CurNode^.UpperVal <= GoalMaxVal)
or (CurNode = nil); // end of repeat
PrintNode(GoalNode);
Readln;
end.
input.txt:
5
13 11 10 4 7
13 10 10 8 5
5 9 7 7 4
15 12 10 11 5
10 11 8 8 4
output:
Job 1 assign to man 4, value 15
Job 2 assign to man 5, value 11
Job 3 assign to man 2, value 10
Job 4 assign to man 3, value 7
Job 5 assign to man 1, value 7
Value = 50
如果扩展为10*10,
input.txt:
10
13 11 10 4 7 13 11 10 4 7
13 10 10 8 5 13 10 10 8 5
5 9 7 7 4 5 9 7 7 4
15 12 10 11 5 15 12 10 11 5
10 11 8 8 4 10 11 8 8 4
13 11 10 4 7 13 11 10 4 7
13 10 10 8 5 13 10 10 8 5
5 9 7 7 4 5 9 7 7 4
15 12 10 11 5 15 12 10 11 5
10 11 8 8 4 10 11 8 8 4
运行约两分钟。
output :
Job 1 assign to man 9, value 15
Job 2 assign to man 5, value 11
Job 3 assign to man 2, value 10
Job 4 assign to man 8, value 7
Job 5 assign to man 6, value 7
Job 6 assign to man 4, value 15
Job 7 assign to man 10, value 11
Job 8 assign to man 7, value 10
Job 9 assign to man 3, value 7
Job 10 assign to man 1, value 7
Value = 100
分享到:
相关推荐
分支定界法是一种搜索与迭代的方法,选择不同的分支变量和子问题进行分支。对于两个变量的整数规划问题,使用网格的方法有时更为简单。 [1] 通常,把全部可行解空间反复地分割为越来越小的子集,称为分支;并且对每...
分支定界法例题
最优化方法的整数规划的分支定界方法 整数线性规划的求解 求解整数规划的割平面法 整数规划的分支定界法
该.m文件使用分支定界法来求解TSP问题
pythonpython解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法解决TSP问题并对比python解决TSP问题以及采用分支定界法...
分支定界法的matlab程序,有详细注释
分支定界伪代码.txt
整数线性规划分支定界法,可求解纯整数规划和混合整数规划
分支定界法python实现,一个例子,可以供研究学习用
分支定界法、割平面法、隐式枚举法的整数规划matlab源代码.zip
该rar包中包含了个人设计出的分支定界法-旅行商(TSP)问题算法开发,其中开发语言为JAVA,请各位小伙伴下载下来后不要随便传发,谢谢支持!
用Matlab实现求解混合整数规划的分支定界法。还不是很完善,可以在上面修改。
运用matlab软件,使用分支定界法编程,求解整数规划问题。
用分支定界算法求以下问题: 某公司于乙城市的销售点急需一批成品,该公司成品生产基地在甲城市。甲城市与乙城市之间共有 n 座城市,互相以公路连通。甲城市、乙城市以及其它各城市之间的公路连通情况及每段公路的...
分支定界法MATLAB程序及详细过程,老师让做的作业,有需要的可以看看
0-1整数 分支定界 matlab 采用分支定界方法和matlab自带优化工具求解
数学建模-整数规划-分支定界法的MATLAB实现。对于数学建模很有帮助,祝大家在建模中取得好成绩。程序已经经过调试,可以运行
利用MATLAB实现了分支定界法,内有三个.m文件,含有中文注释。
运筹学上机实验,用Matlab实现分支定界法求解整数线性规划问题。
分支定界算法实现