#!/usr/local/bin/perl -w
@d=(2, 6, 9, 12, 17, 20, 23, 25);
@s=(0, 1, 0,  1,  0,  1,  0,  1);

$min=9e99;
for (;;){
    for (0..7) { $a[$_]=0; } 
    $am=0;
    $str="";	
    for (;;){
	$i = int rand(8);
	$j = int rand(8);
	next if ($i == $j || $s[$i] == $s[$j] || $a[$i]==1 || $a[$j]==1);
	$a[$i]=$a[$j]=1;
	if ($i > $j ) { ($i,$j) = ($j,$i); }
        $str .= "$d[$i]-$d[$j] ";
	$Z=abs($d[$i]-$d[$j]);
	if ($Z<=7) { $am += 750*(1-0.25); }
        elsif ($Z>=10 && $Z <20) { $am += 750*(1-0.35); }
        elsif ($Z>=20) { $am += 750*(1-0.45); }
	else { $am += 750; }
        $sum=0;
        for $i (@a){
	    $sum += $i;
	}	
  	if ($sum == 8) {
	    if ($am < $min){
		$min = $am;
		print "$str \t $am\n"
	    }
	    last;
	}
    }
}

__END__
From gamo@rocketmail.com Sat Dec 18 15:00:04 2004
Date: 18 Dec 2004 06:00:04 -0800
From: gamo@rocketmail.com
Newsgroups: sci.op-research
Subject: Flight Problem. Can anybody help?

A consultant lives in Dallas but has a client in San Diego. So she has
to travel there often. Here is her flight schedule
Leave Dallas          Leave San Diego
March 2               March 6
March 9               March 12
March 17              March 20
March 23              March 25

The round-trip ticket costs $750 and if the ticket covers 7 nights or
less the airline offers 25% discount. A 35% discount for ticket
covering 10 or more night and 45% discount for ticket covering 20 or
more nights. The consultant needs to purchase 4 round-trip for the
least amount of money.
Can anyone help formulte the LP model for me?

Thanks,
Gamo.