Available online
Description
The programme examines two algorithms which optimise the problem of finding lowest transportation costs from factories to customers for a given product.
The programme examines two algorithms which optimise the problem of finding lowest transportation costs from factories to customers for a given product.
| Module code and title: | TM361, "Graphs, networks and design" |
|---|---|
| Item code: | TM361; 11 |
| First transmission date: | 05-08-1981 |
| Published: | 1981 |
| Rights Statement: | |
| Restrictions on use: | |
| Duration: | 00:23:50 |
| + Show more... | |
| Producer: | Ted Smith |
| Contributors: | Norman Biggs; Roy Nelson |
| Publisher: | BBC Open University |
| Keyword(s): | Algorithm; Flow chart; Hungarian algorithm; Shadow costs; Transportation |
| Footage description: | Shots of an oil well and of an oil refinery. Roy Nelson introduces the programme by pointing out the importance of transportation cost for some commodities. Nelson goes on to examine a simple problem; how to determine the cheapest method for transporting a commodity from three factories to two customers. He works out a solution based on common sense. Norman Biggs explains a simple mathematical method for finding a feasible solution to the problem. He goes on to improve on this method and finds a better solution. Roy Nelson introduces the concept of shadow costs to begin to work out an algorithm which will improve the transportation costs further. The shadow costs are taken by Norman Biggs to develop the algorithm further and he arrives at a solution which is the best one yet. Roy Nelson summarizes what has been done so far and asks whether or not it is possible to arrive at an even better solution. He goes on to show that none better is possible and that the algorithm developed above does find the optimal solution. Norman Biggs, using animated captions and a drawing board, gives a geometrical interpretation of why the above algorithm works. He also constructs a model and interprets the algorithm in terms of this model. Roy Nelson compares the algorithm developed in this programme with the Hungarian Algorithm found in the study text. He briefly states the merits of each. |
| Production number: | FOUT087F |
| Videofinder number: | 1532 |
| Available to public: | no |
