Flows model situations where fluids of some sort – though they may in fact be traffic flows or currents for example – are transported from point to point. The simplest situations involve a single point where fluid flows into the network, called a source, and a single point where fluid exits from the network, called […]

# Archive | D2

## Introduction to Dynamic Programming

Dynamic programming is similar to linear programming. Both seek to solve the problem of optimising some quantity – often profit must be maximised. It involves identifying stages and all possible stages and actions within a project. Decisions are made at each stage that optimise the desired quantity, with calculations being carried out that follow from […]

## Using The Hungarian Algorithm to Find the Least Cost Allocation

The Hungarian algorithm provides a method of allocating workers to tasks, with each worker doing one tak, so that the total cost of doing all the tasks is minimized. The steps in the algorithm are: Find the reduced cost matrix. Determine the minimum number of straight lines – horizontal or vertical – which will cover […]

## Formulating an Allocation Problem as a Linear Programming Problem

An allocation problem can be formulated as a linear programming problem with the introduction of decision variables. Suppose for example we have the following cost matrix for workers doing specific tasks: Task 1 Task 2 Task 3 Andrew 9 25 17 Boris 11 10 49 Charles 27 24 13 We can define decision variables x-{ij} […]

## The Allocation Problem – Finding the Reduced Cost Matrix

Given a matrix representing the costs of a having each worker performing a task, we can find the minimum total cost of having each worker perform just one of the tasks so that the total cost of performing all the tasks is minimized by first finding the reduced cost matrix. To reduce the cost matrix: […]

## The Allocation (Assignment) Problem

The allocation or assignment problem is to distribute tasks between workers in such a way that the total cost, time, waste (or some other measure) involved in doing a job which involves completing a range of tasks is minimized. In general, people are better at some things than others. In general a person more effective […]

## The Transportation Problem – The North West Corner Method

The transportation problem describes a situation where the total cost of transporting identical goods over several routes between various sources of supply and points of demand is to be minimized. A starting solution – one that meets all the demand and uses all the supply, can be found using the ‘north west corner method’. The […]

## The Transportation Problem – Shadow Costs

The transportation problem describes a situation where the total cost of transporting identical goods over several routes between various sources of supply and points of demand is to be minimized. A starting solution – one that meets all the demand and uses all the supply, can be found using the ‘north west corner method’. The […]

## The Transportation Problem

The transportation problem describes a situation where identical goods are to be transported from several supply points to several destination points via several routes. Each route from an individual supply point to an individual destination point has an associated cost, and the problem is to minimize the overall cost while meeting all the demand. We […]

## The Prisoner’s Dilemma

Cooperation is usually analysed in game theory by means of a non-zero-sum game called the “Prisoner’s Dilemma”. The game has two players who can choose between two moves, either “cooperate” or “defect”. The idea is that each player gains when both cooperate, but if only one of them cooperates, the other one, who defects, will […]