9299.net
大学生考试网 让学习变简单
当前位置:首页 >> 理学 >>

分支定界法----整数规划matlab

分支定界法----整数规划matlab


分支定界法的思想是:首先确定目标值的上下界
发布人:chengxu0921 发布时间:2008-7-21 18:16:27 新闻类别:分支-界限法

例 1:设有 A,B,C,D,E 5 人从事 j1,j2,j3,j4,j5 5 项工作每人只能从事一项,它们的 效益表如下: j1 j2 j3 j4 j5 A 13 11 10 4 B 13 10 10 8 C 5 9 7 7 7 5 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; Man2Job: TIntArray; JobsDep: Integer; Next: PNode; end; var CurNode: PNode; NewNode: PNode; DelNode: PNode; GoalNode: PNode; // Current node // New branch node // for delete // the goal // Current Man and Job of current Node // Job2Man[n] = m, job-n assign to person-m // Man2Job[n] = m, person-n assign to job-m // jobs decided, as search depth

UpperVal: Integer; // upper value

GoalMaxVal: Integer; // goal max value CurMan, CurJob: Integer; 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; end; 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); // for Job // with ANode^

CalUpperValue := Res;

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) else Insert(NewNode, CurNode); if CurJob < Size then Continue; // all job assigned, update goal if NewNode^.UpperVal > GoalMaxVal then begin GoalNode := NewNode; GoalMaxVal := GoalNode^.UpperVal end; end; // if // for CurMan // for CurMan // discard this branch if smaller than limit

DelNode := CurNode; CurNode := CurNode^.Next;

Dispose(DelNode); until (CurNode^.UpperVal <= GoalMaxVal) or (CurNode = nil); PrintNode(GoalNode); Readln; end. // end of repeat

input.txt: 5 13 13 5 15 10 11 10 9 12 11 7 10 8 10 10 7 8 4 8 4 11 4 5 7 5

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 13 5 15 10 13 13 5 15 10 11 10 9 12 11 11 10 9 12 11 7 10 8 7 10 8 10 10 7 8 10 10 7 8 4 8 4 11 4 4 8 4 11 4 7 5 5 5 10 7 5 5 5 13 13 9 15 11 10 13 13 9 15 11 11 10 7 12 8 11 10 7 12 8 10 10 7 10 8 4 11 4 5 10 10 7 10 8 4 8 4 11 4 7 5 5 4 8 7 5

运行约两分钟。

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


推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com