FIT3158 Note - W5 Network Modelling

type

Post

Created date

Oct 30, 2022 11:22 PM

Introduction

Network flow problems can be represented as a collection of nodes connected by arcs.

Three types of nodes are: 1) Supply; 2) Demand; and 3) Transshipment.

We use negative numbers to represent supplies and positive numbers to represent demand.

Five types of problems are: 1) Transshipment problem; 2) The Shortest Path Problem; 3) Minimal spanning tree problem; 4) Maximal Flow Problem; and 5) Transportation Problem.

Rule of thumb

To formulate the constraints, all these methods are of different ways:

For Maximal Flow Problem, all constraints, nodes = 0.

For The Shortest Path Problem, set the supply node = -1 and terminal note = 1.

All rules of the modeling are

1. Outflow 就減，Inflow 就加 (出減入加)

例如: Note 1 outflow 去 , 所以係

相反, Node 4, 有inflow, 所以係

2. The balance of rules applied.

Transshipment problem

A problem in which a shipment may move through intermediate nodes (transshipment nodes) before reaching a particular destination node.

The network representation for a transshipment problem with two sources, three intermediate nodes, and two destinations.

Example: The Bavarian Motor Company

Understand the problem.

Identify the decision variables.

State the objective function as a linear combination of the decision variables.

State the constraints as linear combinations of the decision variables

using The Balance-of-Flow Rules.

One example

All in one

Outflow 就減，Inflow 就加 (出減入加)

例如: Note 1 outflow 去 , 所以係

相反, Node 4, 有inflow, 所以係

Identify any upper or lower bounds on the decision variables.

Result

The Shortest Path Problem

A special case of a transshipment problem where

There is one supply node with a supply of - ()

There is one demand node with a demand of + ()

All other nodes have supply/demand of +0

Problem from (62) Transportation & Network Models (Pt. 2) - Shortest Path/Minimal Span Tree - YouTube

Procedure

Set the supply node = -1 and terminal note = 1

Result

Minimal spanning tree problem

Generalised Network Flow Problems

In some problems, a gain or loss occurs in flows over arcs.

Applications are

Oil or gas shipped through a leaky pipeline
Imperfections in raw materials entering a production process
Spoilage of food items during transit
Theft during transit
Interest or dividends on investments

Examples: Coal Bank Hollow Recycling (Explanations on YouTube is here, using Excel)

Optimal Result

How others formulate (Here)

Maximal Flow Problem

In some network problems, the objective is to determine the maximum amount of flow that can occur through a network. The arcs in these problems have upper and lower flow limits.

Examples

How much water can flow through a network of pipes?

How many cars can travel through a network of streets?

Set all nodes = 0.

Another Similar example is easier to understand from (63) Maximum Flow Problem - YouTube

Video

Instruction

Transportation Problem

Example: Lecture Review Q11

Our task is to formulate this solution:

Note: You can ONLY write in this LAZY / Math way, when there are no arrows between nodes.