2.2 理論基礎

2.2.1 運輸調配問題的提法

運輸調配問題是一種線性規劃(包含整數線性規劃和0-1規劃)，可以較為容易地用代數形式建模。一般運輸調配問題的提法如下：

設m個供給地Si(i =1，2，…，m)，n個需求地Dj(j =1，2，…，n)，供給地Si的供給量為si，需求地Dj的產量為dj，供給地Si到需求地Dj的單位運輸成本為cij，運輸調配方案如表2-3所示。

如果運輸調配問題的總供給量等于總需求量，即當時，稱為供需平衡的運輸調配問題，這是基本的運輸調配問題(也稱為簡單的運輸調配問題)；否則，稱為供需不平衡的運輸問題，屬于變形的運輸調配問題。

2.2.2 基本的運輸調配問題

若用xij表示從供給地Si到需求地Dj的運輸調配量，則基本的運輸調配問題的數學模型可以表示為

模型中包含mn個決策變量，有m+n個資源(供需)約束和mn個非負約束(含整數約束、0-1約束)。

基本的運輸調配問題需要滿足如下條件。

(1) 目標明確：明確供給地(廠家、產地、發出地)，需求地(客戶、銷地、接收地)，供給量(產量、生產能力)，需求量(銷量、接收能力)和單位成本。

(2) 需求假設：每一個供給地都有一個固定的供應量，所有的供給量都必須配送到需求地。同樣，每一個需求地都有一個固定的需求量，所有的需求量都必須由供給地滿足。即達成供需平衡——“總供給=總需求”。

(3) 成本假設：從任何一個供給地到達需求地的物品配送成本與所配送的數量呈線性比例關系，因此，配送成本等于配送的單位成本乘以所配送的數量。

2.2.3 運輸調配問題的變形

實際運作中，完全供需平衡的情況較少，多數情況下供需是不平衡的，從而引起運輸調配問題的變形。

(1) 供過于求的運輸調配問題：當時，即總供給量大于總需求量的情況，每個供給量表示了從其供給地能調配出去的最大量，應以滿足需求為主，所有需求均可以得到滿足，供過于求的運輸調配問題的數學模型為

(2) 供不應求的運輸調配問題：當時，即總供給量小于總需求量的情況，每個需求量表示了其需求地所能接收到的最大量，應以滿足供給為主，只能滿足部分需求，供不應求的運輸調配問題的數學模型為

除此之外，還有如下的一些可能變形方式：

一個需求地同時存在著最小需求和最大需求，于是，所有在這兩個數值之間的數量均是可以接受的；目標函數不是求最小值(總成本)，而是求最大值(總利潤)；在運輸調配中不能使用特定的“供給—需求”組合。這些變形問題的模型，需要根據具體問題在上述模型的基礎上修改目標函數和約束條件。

案例3屬于供過于求的運輸調配變形問題，但是又不能使用特定的“供給—需求”組合；案例4屬于一個需求地同時存在著最小需求和最大需求的運輸調配變形問題，且目標是使總利潤最大而不是總成本最小。

2.2.4 運輸調配問題的MATLAB求解

對于運輸調配問題，在決策變量沒有取整數的要求時，自然可用線性規劃求解，但是，在決策變量必須要求取整數時(比如機器設備的臺數、物品的件數、動物的數量等)，則線性規劃不可用，需要用整數線性規劃求解。關于線性規劃與整數線性規劃的MATLAB實現，已經在第1章中給予了介紹，于此不復贅述。