Q:

Optimal solution to a table of numbers

I want to maximise the score of the following table, choosing one item from each column/row, so no two items are on the same row or column.  Score to maximise is just adding all the choices together. 
$$*\quad A\quad B\quad C\quad D\quad E$$
$$\alpha\quad 16\quad 16\quad 18\quad 18\quad 18$$
$$\beta\quad 20\quad 18\quad 16\quad 12\quad 10$$
$$\gamma\quad 20\quad 18\quad 18\quad 16\quad 16$$
$$\delta\quad 18\quad 18\quad 16\quad 16\quad 8$$
$$\epsilon\quad 10\quad 12\quad 14\quad 14\quad 14$$
Example: ($^{C}$ means chosen)
$$*\quad A\quad B\quad C\quad D\quad E$$
$$\alpha\quad 16^{C}\quad 16\quad 18\quad 18\quad 18$$
$$\beta\quad 20\quad 18\quad 16\quad 12\quad 10^{C}$$
$$\gamma\quad 20\quad 18^{C}\quad 18\quad 16\quad 16$$
$$\delta\quad 18\quad 18\quad 16^{C}\quad 16\quad 8$$
$$\epsilon\quad 10\quad 12\quad 14\quad 14^{C}\quad 14$$
Gives a score of $16+10+18+16+14=74$
Now there are a few ways to do this, but can firstly, someone actually tell me if $88$ really is the best result and how can this be done computational.  Note: I am a Mathematics student and would normally approach such a problem with graph theory, but would like to see computation methods. 

A:

This is called an assignment problem.  The most common algorithm to solve it is known as the Hungarian algorithm, and runs in $O(n^3)$ time. 
Another interesting observation is that it corresponds to computing the permanent of a matrix in the tropical (max-plus) semiring.  Unfortunately, though, a Google search for "tropical permanent" is complicated by the non-mathematical meanings of these words. 

A:

This can be formulated as a linear programming problem.  Since you want to choose the right positions on each line and column, you may formulate this as finding a matrix $X$ with entries zero and $1$ such that the sum on each line and column is equal to $1$ and the dot product between $A$ and $X$ is maximized.  
Since we want to maximize a linear functional with linear constraints and we expect the variables to take values in $\{0,1\}$ we may relax this to allow variables to belong to $[0,1]$. This is because linear functions always attain their extremal values at the vertices of the computational domain.  That's why the simplex algorithm works in this case. 
The complexity of the simplex algorithm is not polynomial, apparently, but for small examples it works really well.  
Here's a Matlab implementation using linprog and the simplex algorithm:
function sci_comp1_mat

A = [16 16 18 18 18; 
     20 18 16 12 10;
     20 18 18 16 16;
     18 18 16 16 8;
     10 12 14 14 14];

n = size(A,1);
f = double(A(:)); % coeffs matrix
% constraints
% sum on lines

C = zeros(2*n,n^2);
for i=1:n
   C(i,linspace((i-1)*n+1,i*n,n))=1;
   C(n+i,linspace(i,n^2-n+i,n))=1;
end
b = ones(2*n,1);

lb = zeros(size(f));
ub = ones(size(f));

options. Algorithm = 'simplex';
x = linprog(-f,C,b,[],[],lb,ub,[],options);
dot(x,f)
x = reshape(x,n,n);
round(x)

Res = A.*x

Res(Res==0) = '';
Res(:)

