MODEL:
! Target assignment problem in LINGO.
Given a
set of sources
e.g., weapon delivery systems, and
number of units available from each source,
a set of targets,
each with a given value, and
probabilities
Prob(i,j) = probability that one unit from source i
will be NOT be successful at target j,
Decide how many units from each source
to assign to each target
so as to maximize the expected
value of successes;
! Reference: Bracken and McCormick;
! Keywords: Target assignment, Assignment,
Transportation problem, Interdiction;
SETS:
DESTN: VALUE, DEM, LFAILP;
SOURCE: AVAIL;
DXS( DESTN, SOURCE): PROB, VOL;
ENDSETS
DATA:
! Units available at each source;
AVAIL= 200 100 300 150 250;
! Min units required at each destination;
DEM=
30 0 0 0 0 100 0 0 0 40
0 0 0 50 70 35 0 0 0 10;
! Value of satisfying destination J;
VALUE=
60 50 50 75 40 60 35 30 25 150
30 45 125 200 200 130 100 100 100 150;
! Probability that a unit from source J will NOT do the job at destination I;
PROB=
1.00 .84 .96 1.00 .92
.95 .83 .95 1.00 .94
1.00 .85 .96 1.00 .92
1.00 .84 .96 1.00 .95
1.00 .85 .96 1.00 .95
.85 .81 .90 1.00 .98
.90 .81 .92 1.00 .98
.85 .82 .91 1.00 1.00
.80 .80 .92 1.00 1.00
1.00 .86 .95 .96 .90
1.00 1.00 .99 .91 .95
1.00 .98 .98 .92 .96
1.00 1.00 .99 .91 .91
1.00 .88 .98 .92 .98
1.00 .87 .97 .98 .99
1.00 .88 .98 .93 .99
1.00 .85 .95 1.00 1.00
.95 .84 .92 1.00 1.00
1.00 .85 .93 1.00 1.00
1.00 .85 .92 1.00 1.00;
ENDDATA
SUBMODEL TARGASSG:
!Max sum over I:(value of destn I)
*Prob{success at I};
! Exploit the facts:
a) Prob{at least one success in n tries} =
1 - Prob{each of n tries fails},
b) p1*p2*...pn = @EXP(@LOG(p1)+...+@LOG(pn));
MAX = OBJ;
OBJ = @SUM( DESTN( I): VALUE( I) *
( 1 - @EXP( LFAILP( I))));
! The supply constraints;
@FOR( SOURCE( J):
@SUM( DESTN( I): VOL( I, J)) <= AVAIL( J));
@FOR( DESTN( I):
!The demand constraints;
@SUM( SOURCE( J): VOL( I, J)) >= DEM( I);
!Compute log of destination I failure probability;
@FREE( LFAILP( I));
LFAILP( I) =
@SUM(SOURCE(J): @LOG(PROB(I,J)) * VOL(I,J));
);
! Can assign only integer quantities;
@FOR( DXS(i,j): @GIN(VOL(i,j)));
ENDSUBMODEL
CALC:
@SET('GLOBAL',0); ! Do not need to use Global solver;
@SOLVE( TARGASSG);
! Write a little solution report;
@WRITE(' Target assignment Solution Report',@NEWLINE(1));
@WRITE(' Total expected value of successes= ',
@FORMAT(OBJ,"10.2f"), @NEWLINE(2));
@WRITE(' #units Success', @NEWLINE(1));
@WRITE(' Target Source assigned Probability', @NEWLINE(1));
@FOR( DESTN(i):
@FOR( DXS(i,j) | VOL(i,j) #GT# 0.5:
@WRITE( @FORMAT(DESTN(i),"7s"),' ', @FORMAT(SOURCE(j),"7s"),
' ', @FORMAT( VOL(i,j),"4.0f"),
' ', @FORMAT(( 1 - @EXP( LFAILP( I))),"4.2f"), @NEWLINE(1));
);
);
ENDCALC
|
