第四章-運輸問題.ppt

1、運籌學(xué) Operations Research,北京理工大學(xué)珠海學(xué)院 吳浩然,運輸問題模型,第四章 運輸問題,1,表上作業(yè)法,2,運輸問題的應(yīng)用,3,1.運輸問題模型-問題提出,某企業(yè)從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示：,請問，應(yīng)如何調(diào)運可使總運輸費用最小？,產(chǎn)地,銷地,元素等于0或1； 每列只有兩個元素為1，其余為0； 對于每個變量，前m個約束方程只出現(xiàn)一次，后n個約束方程也只出現(xiàn)一次；,運輸問題約束條件系數(shù)矩陣的特點,是否最優(yōu)解？,尋找新的基本可行解,2.表上作業(yè)法步驟,西北角法：從 x11開始分配，

2、從西北向東南方向逐個分配； 最小元素法：采用最小費用優(yōu)先分配的原則；,步驟1：初始基本可行解的確定,檢驗數(shù)的公式為：,其中 分別稱為行位勢、列位勢。,結(jié)論： （1）基變量所對應(yīng)的檢驗數(shù)：,步驟2：最優(yōu)解的檢驗-位勢法,（2）若非基變量所對應(yīng)的檢驗數(shù) 當(dāng)前解即為最優(yōu)解；,閉回路： 從進(jìn)基變量的空格出發(fā)，沿水平或垂直方向前進(jìn)，每碰到數(shù)字格轉(zhuǎn)90o（有些情況也可以不改變方向）繼續(xù)前進(jìn)，直到回到出發(fā)的空格為止，由此形成的封閉的折線稱為閉回路。,步驟3：尋找新的基本可行解-閉回路法,某企業(yè)從兩個產(chǎn)地A1、A2將物品運往三個銷地B1、B2、B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如

3、下表所示：,請問，應(yīng)如何調(diào)運可使總運輸費用最小？,產(chǎn)地,銷地,某公司有從三個產(chǎn)地A1，A2，A3，將物品運送到四個銷地B1，B2，B3，B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示： 請問，應(yīng)如何調(diào)運產(chǎn)品，使得總運費最少？,課堂練習(xí),從每一個非基變量的空格出發(fā)，構(gòu)造閉回路。若非基變量所對應(yīng)的檢驗數(shù) ，則當(dāng)前解即為最優(yōu)解。 其中： 閉回路奇數(shù)頂點運費之和 -閉回路偶數(shù)頂點運費之和,閉回路法檢驗解的最優(yōu)性,某公司有從三個產(chǎn)地A1，A2，A3，將物品運送到四個銷地B1，B2，B3，B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示： 請用最小元素法確定初始基

4、本可行解，并用閉回路法檢驗初始基本可行解是否為最優(yōu)解。,課堂練習(xí),總產(chǎn)量總銷量,2.表上作業(yè)法（產(chǎn)銷不平衡的運輸問題）,某公司有從三個產(chǎn)地A1，A2，A3，將物品運送到三個銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示：,請問，應(yīng)如何調(diào)運產(chǎn)品，使得總運費最少？,某公司有從三個產(chǎn)地A1，A2，A3，將物品運送到四個銷地B1，B2，B3，B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示： 請問，應(yīng)如何調(diào)運產(chǎn)品，使得總運費最少？,課堂練習(xí),總銷量總產(chǎn)量,某公司有從三個產(chǎn)地A1，A2，A3，將物品運送到五個銷地B1，B2，B3，B4， B5，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示： 請問，應(yīng)如何調(diào)運產(chǎn)品，使得總運費最少？,1.判別下表中的調(diào)運方案能否作為表上作業(yè)法的初始解。,2.請用最小元素法確定下述運輸問題的初始基本可行解。,3.某公司有從兩個產(chǎn)地A1，A2，將物品運送到三個銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量、各銷地的銷量、各產(chǎn)地到各銷地的單位運價如下表所示： 其中， B3的銷量必須得到滿足。請問，應(yīng)如何調(diào)運產(chǎn)品，使得總運費最少？,4.某公司有從三個產(chǎn)地A1，A2， A3 ，將物品運送到三個銷地B1，B2，B3，各產(chǎn)地的產(chǎn)量