COSC 6367 (Dr. Eick) - Spring 2007

Project 1

Due Date: | February 27, 2007 |

Last Updated: | January 29, 2007, 5:40pm |

Write a system that is capable of solving 5 source / 6 destination real-valued balanced transportation problems with respect to four given cost functions. Write an interactive EC-style system that

For example, let us assume that the following source and destination
capacities are given:

source[1]=5 source[2]=5 source[3]=20 source[4]=15 source[5]=15 |
destination[1]=8 destination[2]=8 destination[3]=8 destination[4]=8 destination[5]=8 destination[6]=20 |

Moreover, four different cost functions f1, f2, f3, and f4 will be used for the project:

Let i the source index (i=1,...,5) j be the destination index(j=1,...,6) u the number of units to be transported (>=0)

f1(i,j,u) := (|i-j|+1)^2 * u f2(i,j,u) := (|i-j|+1)^2 * u^2 f3(i,j,u) := |i*j - 11|*sqrt(u) + sqrt(u) f4(i,j,u) := |i*j - 11|*u^2 + u^4 |
"linear transportation problem" "quadratic transportation problem" "general transportation problem1" "general transportation problem2" |

The transportation cost of the above solution matrix, assuming that function f1 is used, would be:

f1(1,1,5) + f1(2,1,3) + f1(2,2,2) + f1(3,2,6) + f1(3,3,8) + f1(3,4,6) + f1(4,4,2) + f1(4,5,8) + f1(4,6,5) + f1(5,6,15)In general, the elements of the solution matrix are floating point numbers; however, if you print the elements of the matrix, round those to two numbers after the decimal point(e.g. 27.14334344343434 is printed as 27.14 and 3.45500111232332 is printed as 3.46).

Write a program that displays the inputs, the evolution process, and the final results obtained by a program run in a nice and understandable form. Test and enhance your program assuming each of the 4 classes of supported cost-functions. Be prepared to demo your program!

Write a report (approx. 9 to 13 single spaced pages) that describes the evolution of the project, gives a clear description of the explored and employed search strategies, and summarizes the results of running your program using the four cost functions for:

source[1]=5 source[2]=5 source[3]=20 source[4]=15 source[5}=15 |
destination[1]=8 destination[2]=8 destination[3]=8 destination[4]=8 destination[5]=8 destination[6]=20 |

source[1]=12 source[2]=12 source[3]=12 source[4]=12 source[5]=12 |
destination[1]=10 destination[2]=10 destination[3]=10 destination[4]=10 destination[5]=10 destination[6]=10 |