Degenerate Solutions to the Transportation Problem

If a feasible solution to a transportation problem with n rows and m colums exists, but the solution uses less thancells, then the solution is said to be degenerate. This cann happen when the demand of a single destination depot can be supplied by a single source depot. A B C Supply 1 25 20 […]

Continue Reading

Dominating Strategies in Two Player Games

Players obviously want to maximising their winnings – or minimize their losses – when playing a game. If player 1 has a choice of strategies, but the winnings from strategy A, which depend on the strategy adopted by the player 2, are at least as great as the winnings of strategy B, which also depend […]

Continue Reading

Formulating a Problem for the Simplex Algorithm

The simplex algorithm is used to find optimal combinations of certain quantities, subject to constraints on those quantities. Before the algorithm can be used the problem must be suitably expressed, which involves defining the constraint conditions and the objective function which is to be maximised. Each constrain, and the objective function, is a linear combination […]

Continue Reading

Proof of the Stable Solution Theorem

For a two player, zero sum game, a stable solution is one such that each player always plays the same, unchanging strategy. The Stable Solution Theorem states that there will only be a stable solution when the row maximum of the matrix representing the playoffs for one player equals the column minimum. If the matrix […]

Continue Reading

Vertex Testing

Solving a linear programming problem using the simplex algorithm may give non integer solutions. Such solutions may not be practical, and we must look for integer solutions for each variable. The process of looking for integer solutions is called vertex testing. Suppose we have solved the linear programming problem: Maximisesubject to the constraintsand The simplex […]

Continue Reading

Bellman’s Principle of Optimality

Bellman’s Principle of Optimality is a principle used in directed networks, where arcs can only be traversed in a certain direction.. Suppose we have the network below: The longest route from A to Z is AHDCEZ. The longest route from A to H is AH. The longest route A to D is AHD. The longest […]

Continue Reading

Changing Zero Sum Games Into Linear Programming Problems

Given a zero sum game with two players, each with a choice of strategies, and a payoff matrix representing the winnings or losses of one player for every possible combination of strategies, we can find the optimal strategy that player should produce to maximise their winnings (or minimise therir losses) by expressing the game as […]

Continue Reading

Flow Augmentation

An initial flow through a network can be found by inspection, and a maximum flow through the network can be found by flow augmentation once this initial flow has been found. We do this by labelling the arcs of a network with their corresponding flows and capacities as shown below. Each arc is now labelled […]

Continue Reading

The Maximum Flow Minimum Cut Theorem

Given a network, as shown below, with each number on an arc indicating a capacity, we can cut the network into two in so many different ways. Each cut will return a maximum flow through the network, equal to the sum of the capacities on the arcs passing from left to right, but not all […]

Continue Reading