type
Post
Created date
Oct 30, 2022 11:22 PM
category
Business
tags
Decision Making
status
Published
Language
From
School
summary
slug
password
Author
Priority
Featured
Featured
Cover
Origin
Type
URL
Youtube
Youtube
icon
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.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F9ddb5b38-8733-40ed-b221-fe5013c27f0c%2FUntitled.png%3Ftable%3Dblock%26id%3D3552159f-169b-4e1c-9c40-abfc13028020%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DS6FXH4nVyuJQ7alN4smjqNqSalzBC6Ym5c_TZEGbL2Y?table=block&id=3552159f-169b-4e1c-9c40-abfc13028020&cache=v2)
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.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ff218fed7-fc88-41be-b245-35d061d17228%2FUntitled.png%3Ftable%3Dblock%26id%3D620e1d5f-ef22-4136-879f-6375b855711d%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D53UIfn8kjW7HpKiukZ9KSa2Wf-01Fmy3ZYcscd9SE2w?table=block&id=620e1d5f-ef22-4136-879f-6375b855711d&cache=v2)
Example: The Bavarian Motor Company
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F88468fba-a95d-4d0f-8ec8-5956184404b3%2FUntitled.png%3Ftable%3Dblock%26id%3Dcf05c987-7e0d-4e76-ba85-211946cfdf1b%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DNrna6mKKz8wd6OI5_xkjUWrqXSzFpuM_dEl44x6DToI?table=block&id=cf05c987-7e0d-4e76-ba85-211946cfdf1b&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F4e570fb8-0db2-4e8c-a3a0-0e772a510f4b%2FUntitled.png%3Ftable%3Dblock%26id%3D6952aea9-5a00-4ec6-b599-720f742ba095%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DVkUx36_SgA0TwoZ-N8BEFHkKMbwNoruXjsslrIKXNEw?table=block&id=6952aea9-5a00-4ec6-b599-720f742ba095&cache=v2)
- Understand the problem.
- Identify the decision variables.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F5c8edf25-43fb-4776-ae87-bd0fdfcfe93a%2FUntitled.png%3Ftable%3Dblock%26id%3D4ebcd2be-41fd-420f-920a-ef3aa0ea192f%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DYBMggANoUbTiBxvi-xu2mpmSQPiowsF7ksG-GLvLHGo?table=block&id=4ebcd2be-41fd-420f-920a-ef3aa0ea192f&cache=v2)
- State the objective function as a linear combination of the decision variables.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F04043510-22ee-47d2-af64-327cb3860f22%2FUntitled.png%3Ftable%3Dblock%26id%3D0ece6f5c-8705-40e6-91f2-27d449707b4e%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DQ_9iS1rcqInq8mdrc0PNYSH0CTM3CUyQx4l8NkrFbYg?table=block&id=0ece6f5c-8705-40e6-91f2-27d449707b4e&cache=v2)
- State the constraints as linear combinations of the decision variables
using The Balance-of-Flow Rules.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F33928d21-f8f5-4a8f-8067-bb66c8deffc4%2FUntitled.png%3Ftable%3Dblock%26id%3D754a4b35-89de-4baa-aa4a-3875009391c4%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DqN_adw6Nu8nYJ-Oj6mktu9UGePvyC-Onr8ObjaVBxq8?table=block&id=754a4b35-89de-4baa-aa4a-3875009391c4&cache=v2)
One example
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F57d42a5b-060d-4a1d-a467-31ae43252688%2FUntitled.png%3Ftable%3Dblock%26id%3Decddd208-0b31-4fce-805b-b5cb695f30b8%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3Dsi5EE9_uJuzMtXoVJD5cNNg1nvzChyT7mTHODvhDROA?table=block&id=ecddd208-0b31-4fce-805b-b5cb695f30b8&cache=v2)
All in one
Outflow 就減,Inflow 就加 (出減入加)
例如: Note 1 outflow 去 , 所以係
相反, Node 4, 有inflow, 所以係
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ff86d984b-284a-41ce-ab0e-ca52edcfd5ec%2FUntitled.png%3Ftable%3Dblock%26id%3D54971b5d-066b-4b1c-9025-dcdb4314aac4%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D71iNHlWU6SgxKkCDBxf2_Hmhax9okullZRDJyZII3gU?table=block&id=54971b5d-066b-4b1c-9025-dcdb4314aac4&cache=v2)
- Identify any upper or lower bounds on the decision variables.
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F2f92c5e5-6e0c-407d-84df-4088584a59c4%2FUntitled.png%3Ftable%3Dblock%26id%3D0cf2243b-d52e-4273-b4a3-9042bd3e81bf%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DpaZfrr2i9UqzyqYLSmRlw8Amym4M4laht65zih9kHu4?table=block&id=0cf2243b-d52e-4273-b4a3-9042bd3e81bf&cache=v2)
- Result
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F155dc402-c693-442a-8646-3f3aa90e140f%2FUntitled.png%3Ftable%3Dblock%26id%3D0f1b359c-dbdf-4a21-af31-515338de4256%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DiEjiZhRO0NjHAiJ07dlqrk-LH_91vmj2EuwnTL4F6rM?table=block&id=0f1b359c-dbdf-4a21-af31-515338de4256&cache=v2)
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
Minimal spanning tree problem
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F16dcb4e1-c7c9-4828-bd3e-4b46603d5c1c%2FUntitled.png%3Ftable%3Dblock%26id%3Df4b84bde-d418-4296-885b-aa5c250b285d%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DQQ-PQN_vIuvhTUNH800V_ZmbvtJRnmILiWihqjPhF_0?table=block&id=f4b84bde-d418-4296-885b-aa5c250b285d&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F4270d8de-9772-48e7-98fc-937771231453%2FUntitled.png%3Ftable%3Dblock%26id%3D37a7dca8-0210-42d6-bdb0-2a07d36dc465%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3Da8hg8ffOV5m_64vr_4YkS5nnCKFAUISNlqQ7f0E3BmU?table=block&id=37a7dca8-0210-42d6-bdb0-2a07d36dc465&cache=v2)
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)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ff10d5d72-e895-4056-b72f-8effe6ce51e9%2FUntitled.png%3Ftable%3Dblock%26id%3Db50f773a-8d47-4f57-87ad-c31f4aeaa0ac%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DzsowGZbFescubfY8jsagrPm6FwGBWvav1eXAEhDOXXk?table=block&id=b50f773a-8d47-4f57-87ad-c31f4aeaa0ac&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ffb08387d-3d4c-4540-a7eb-1bec935425c6%2FUntitled.png%3Ftable%3Dblock%26id%3Ddfec6c0f-a798-4fc0-89c1-fb4cb603c243%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D9yHeJ8rkLjwqTHN9m2NMzrAlBCjpQsX-TFsm8H-7WZM?table=block&id=dfec6c0f-a798-4fc0-89c1-fb4cb603c243&cache=v2)
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?
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fd01c93a9-7d6b-4d11-abb8-6243b37eb0b8%2FUntitled.png%3Ftable%3Dblock%26id%3Dceeeb7e4-95d6-4983-a601-5be3d04b3d44%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DVderWYnj7RZKlIa8ToL9Lv9vQaT3HUQq_paQRiebYX4?table=block&id=ceeeb7e4-95d6-4983-a601-5be3d04b3d44&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F00610436-de90-44d6-80f5-605ab93c1b4d%2FUntitled.png%3Ftable%3Dblock%26id%3De8ef2cd1-0bf3-4f20-ac82-ffb42a3ddf15%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D5SdN5krrELXZX_dlSzXdU7-_AsnW9INJjAUgPRvPa4k?table=block&id=e8ef2cd1-0bf3-4f20-ac82-ffb42a3ddf15&cache=v2)
Set all nodes = 0.
Another Similar example is easier to understand from (63) Maximum Flow Problem - YouTube
Video
Instruction
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F3b40dfad-be60-42a1-8032-902c107d9b52%2FUntitled.png%3Ftable%3Dblock%26id%3D878ea64c-b8e7-4646-9e76-5d834fd89555%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DhgfFh_9fbOm9T2fWCm0tnf-GJx3KonvGkeTUkFK3VdA?table=block&id=878ea64c-b8e7-4646-9e76-5d834fd89555&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F10121521-aab1-49d3-bb47-d16bbc205f8a%2FUntitled.png%3Ftable%3Dblock%26id%3Dcc7305f3-dadc-47e7-801a-982b22c4b6d0%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D-nC5J54JylXfvsybJYkBy7ztdAP-U790dXLcXi-EJi4?table=block&id=cc7305f3-dadc-47e7-801a-982b22c4b6d0&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F8dfb3541-51c6-4d35-8012-99da0880d0ac%2FUntitled.png%3Ftable%3Dblock%26id%3D6a91bb2f-33c2-4042-9af6-bca3a4f5d2ae%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DpjU9Hu8vLq5nw5gEPikGlA-HDp3LPkBekTf_qWbfOK0?table=block&id=6a91bb2f-33c2-4042-9af6-bca3a4f5d2ae&cache=v2)
Transportation Problem
![Video preview](https://i.ytimg.com/vi/WZIyL6pcItY/hqdefault.jpg)
Example: Lecture Review Q11
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F006eb689-d988-4baf-98d4-fac1348751c2%2FUntitled.png%3Ftable%3Dblock%26id%3Def3cefe3-09ef-4043-8cb8-c9ab7087a0dd%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DUkPo0mHzmh5rVRzxoafPtlIHRna1hOCfN1x6uYsyf20?table=block&id=ef3cefe3-09ef-4043-8cb8-c9ab7087a0dd&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F88a756bb-db99-4bec-a28d-62fb9f1b0adf%2FUntitled.png%3Ftable%3Dblock%26id%3Dd4c48016-e607-4231-bde5-9fab1e3eaa80%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DA-6q_bvGR_ZsnxWk3nAD0BTp-B-05dvuTAza-XLBKBk?table=block&id=d4c48016-e607-4231-bde5-9fab1e3eaa80&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2F2ec1e6be-793b-4c69-8752-cac96668d544%2FUntitled.png%3Ftable%3Dblock%26id%3D8def0780-5b11-4527-9dd4-512a13473dbc%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3Drl36oBADJuwoRJ7ezcjKVVaG_0yTueVln2kYgrkJq_k?table=block&id=8def0780-5b11-4527-9dd4-512a13473dbc&cache=v2)
Our task is to formulate this solution:
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ff125888a-3cdf-46af-b096-25aaf0323273%2FUntitled.png%3Ftable%3Dblock%26id%3Dfd50ac65-c20a-4be0-9672-f7181e3a4fb8%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DnVFfX2MkqqqiMvko2nVtZocZU2A52YnwTfkZoy_PfSI?table=block&id=fd50ac65-c20a-4be0-9672-f7181e3a4fb8&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Ff74d24c0-101e-49d3-a874-ebcc4885f766%2FUntitled.png%3Ftable%3Dblock%26id%3Dc0525584-cb5e-4bc4-b745-be29ca6fd236%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3D2f4j5e5T6HqkcrHWKcuPtQyKsy2VQ_bEhIhm3XdXmUg?table=block&id=c0525584-cb5e-4bc4-b745-be29ca6fd236&cache=v2)
![notion image](https://www.notion.so/image/https%3A%2F%2Ffile.notion.so%2Ff%2Ff%2Fe1c5ba0e-562a-49b0-8505-ce5e38fc061b%2Fac756211-01a8-4b00-829e-9ffec68a7041%2FUntitled.png%3Ftable%3Dblock%26id%3D0dd39d8b-0f1c-44b8-84b9-e46340bf3809%26spaceId%3De1c5ba0e-562a-49b0-8505-ce5e38fc061b%26expirationTimestamp%3D1725789600000%26signature%3DEk-ThTDBq3nnhK4aZxfOq7s0jCKuWVtO5SHPXWglte8?table=block&id=0dd39d8b-0f1c-44b8-84b9-e46340bf3809&cache=v2)
Note: You can ONLY write in this LAZY / Math way, when there are no arrows between nodes.
- Author:Jason Siu
- URL:https://jason-siu.com/article/a4680eaf-50ed-4701-b16e-a380a285eee7
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!
Relate Posts
Values alignment - Ray Dalio & Naval Ravikant
The AAA Framework - Ali Abdaal
Bouncing Back with Gain Recovery Calculator: The Art of Recouping Financial Losses in Leveraged Investments
Zero to One Extract: Questions that every business must answer
Life - Principles
I'm a master of analysis, coding is just a bonus!