The graphical method of solving linear programming problems is only suitable for problems with two variables, because the constraints, written in terms of the two variables, can be plotted on a set of axes on a piece of paper. If there are more than two variables, the constraints cannot be so plotted. In this case, […]

## The Travelling Salesman Problem – Finding a Lower Bound

The ‘travelling salesman problem’ is, for a given network of vertices connected by arcs of given lengths, to find the minimum distance that visits each vertex once and returns to the starting vertex. For a small network, it is possible to find the minimum distance by examining every possible route, but as the size of […]

## The Travelling Salesman Problem – Finding an Upper Bound Using the Nearest Neighbour Algorithm

The ‘travelling salesman problem’ is, for a given network of vertices connected by arcs of given lengths, to find the minimum distance that visits each vertex once and returns to the starting vertex. For a small network, it is possible to find the minimum distance by examining every possible route, but as the size of […]

## The Travelling Salesman Problem – Finding an Upper Bound

The ‘travelling salesman problem’ is, for a given network of vertices connected by arcs of given lengths, to find the minimum distance that visits each vertex once and returns to the starting vertex. For a small network, it is possible to find the minimum distance by examining every possible route, but as the size of […]

## The Travelling Salesman Problem

The travelling salesman problem’ is actually two problems – the classical and practical problems. In the classical problem, each vertex must be visited exactly once before returning to the start vertex. In the practical problem, each vertex must be visited at least once before returning to the start vertex. In both problems we seek to […]

## Converting a Network into a Network of Least Distances

Given a network, it is desirable to construct a table showing the minimum distance between any two vertices in the network – this includes the case where vertices are not directly connected. We find the least distance even for indirectly connected verticesFor example given the network below, We can go direct from A to C […]

## Solving Linear Programming Problems Graphically

Clive has decided that as a fund-raising activity he will make and sell candles. He has decided to make two types of candle, a plain one, and a scented one. Each candle requires 200g of wax and Clive has bought enough ingredients to make a total of 1.6kg of wax. His idea is to make […]

## Stable Solutions in a Zero Sum Game

Suppose we have the following payoff matrix. 5 -2 3 3 5 6 5 4 2 3 -1 2 We find the play safe strategies. Row Minimum 5 -2 3 3 -2 5 6 5 4 4 2 3 -1 2 -1 Column Maximum 5 6 5 4 The row maximin is 4, so A […]

## Game Theory – Play Safe Strategies

In game theory, a player adopts a ‘play safe’ strategy if he looks for the worst possible outcome that could result from the choices he makes. He then picks the choice that results in the least worst option. We can determine the play safe strategy from a payoff matrix. The matrix below shows the outcomes […]

## Zero Sum Games

A zero sum game is one in which the total pay-offs are the same for all possible combinations of players’ strategies. Each player can only gain at the expense of the other players so any player’s loss is balanced by an equal gain made by other players. It does not actually matter much whether the […]