Algorithm to determine the best team and formation?

If we model your problem by graph and noticing that the number of different formations is small, the problem is maximum weighted bipartite matching, which is solvable by Hungarian Algorithm, ....

To model the problem with bipartite graphs, put players in one part, and positions to the other part (e.g. in soccer), to form a pool of players and 11 positions for them, connect all players to all positions, and set the corresponding edge weights as a corresponding player rating in the position.

Now all you should do is to find a maximum (weighted) matching in this complete bipartite graph. (codes are available in wiki link).

I supposed we have a limited number of formations, for each formation we can find the corresponding matching graph, and its maximum weight matching, finally take maximum value over all possible formations (in all graphs).

The simples heuristic that can be applied to your problem is the greedy algorithm, whose explanation can be found at http://en.wikipedia.org/wiki/Greedy_algorithm.

Another solution is to create two dummy nodes (begin and end) and consider your pool of players as an ordered graph (first comes the goalkeeper, then the right wing defender, and so on). The edges will consist of the players rating for the position under consideration. In this scenarion, you will have a scenario where you can apply the A* algorithm, whose description you will find at http://en.wikipedia.org/wiki/A*_search_algorithm (just remember that a maximization problem is only a minimization of the inverse function).

You could try a heuristical approach using existing AI tools for optimizations, such as Genetic Algorithms or Hill Climbing.
I'll give more details on hill climbing, since it is my favorite.

Represent your problem as states graph G = (V,E) such that V = {all possible states } and E = {(u,v) | swapping one player you can move from u to v }.
Also, let u:V->R be a utility function for a formation.
Since we do not want to generate the graph, let next:V->2^V be a function such that next(v) = {all possible formation that you can get by changing one player }

The idea of hill climbing is to start from a random formation, and greedily make the best change possible, when you are stuck - restart the algorithm from a new random formation.

1. best<- -INFINITY
2. while there is more time
3. choose a random matching
4. NEXT <- next(s)
5. if max{ u(v) | for each v in NEXT} < u(s): //s is a local maximum
   5.1. if u(s) > best: best <- u(s) //if s is better then the previous result - store it.
   5.2. go to 2. //restart the hill climbing from a different random point.
6. else:
   6.1. s <- max { NEXT }
   6.2. goto 4.
7. return best //when out of time, return the best solution found so far.

Note that this variation of hill climbing (hill climbing with random restarts) is an any time algorithm - meaning it will become better when more time is given, and when infinite time is given - it founds the global maximum.