《運(yùn)籌學(xué)（第3版）》 課件全套 葉向 第1-8章 線(xiàn)性規(guī)劃 -線(xiàn)性目標(biāo)規(guī)劃

實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）第1章線(xiàn)性規(guī)劃LinearProgramming本章內(nèi)容要點(diǎn)線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型線(xiàn)性規(guī)劃的圖解法線(xiàn)性規(guī)劃的電子表格建模和求解線(xiàn)性規(guī)劃的多解分析建立規(guī)劃模型的流程本章主要內(nèi)容框架圖線(xiàn)性規(guī)劃線(xiàn)性規(guī)劃（linearprogramming，LP）是運(yùn)籌學(xué)（operationsresearch，OR）中研究較早、理論和算法比較成熟的一個(gè)重要分支，主要研究在一定的線(xiàn)性約束條件下，使得某個(gè)線(xiàn)性指標(biāo)最優(yōu)的問(wèn)題。自1947年美國(guó)的丹齊格（G.B.Dantzig）提出求解線(xiàn)性規(guī)劃的單純形法（LPsimplexmethod），線(xiàn)性規(guī)劃的理論體系和計(jì)算方法日趨系統(tǒng)和完善。隨著計(jì)算機(jī)的發(fā)展，線(xiàn)性規(guī)劃已經(jīng)廣泛應(yīng)用于工農(nóng)業(yè)生產(chǎn)、交通運(yùn)輸、軍事等各領(lǐng)域，例如生產(chǎn)計(jì)劃、運(yùn)輸、人力資源規(guī)劃、選址、庫(kù)存管理和營(yíng)銷(xiāo)決策等。因此，線(xiàn)性規(guī)劃也是運(yùn)籌學(xué)中應(yīng)用最廣的分支之一。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-1生產(chǎn)計(jì)劃問(wèn)題。某工廠(chǎng)要生產(chǎn)兩種新產(chǎn)品：門(mén)和窗。經(jīng)測(cè)算，每生產(chǎn)一扇門(mén)需要在車(chē)間1加工1小時(shí)、在車(chē)間3加工3小時(shí)；每生產(chǎn)一扇窗需要在車(chē)間2和車(chē)間3各加工2小時(shí)。而車(chē)間1、車(chē)間2、車(chē)間3每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間分別是4小時(shí)、12小時(shí)、18小時(shí)。已知門(mén)的單位利潤(rùn)為300元，窗的單位利潤(rùn)為500元。而且根據(jù)市場(chǎng)調(diào)查得到的這兩種新產(chǎn)品的市場(chǎng)需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷(xiāo)售出去。問(wèn)該工廠(chǎng)應(yīng)如何制訂這兩種新產(chǎn)品的生產(chǎn)計(jì)劃，才能使總利潤(rùn)最大？1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型【分析】在該問(wèn)題中，目標(biāo)是兩種新產(chǎn)品的總利潤(rùn)最大化，所要決策的（變量）是兩種新產(chǎn)品（門(mén)和窗）的每周產(chǎn)量，而新產(chǎn)品的每周產(chǎn)量要受到三個(gè)車(chē)間每周可用于生產(chǎn)新產(chǎn)品的時(shí)間的限制。因此，該問(wèn)題可以用“目標(biāo)函數(shù)”“決策變量”“約束條件”三個(gè)因素加以描述。實(shí)際上，所有線(xiàn)性規(guī)劃問(wèn)題都包含這三個(gè)因素：（1）決策變量是指問(wèn)題中有待確定的未知因素。例如決定企業(yè)經(jīng)營(yíng)目標(biāo)的各產(chǎn)品的產(chǎn)量等。（2）目標(biāo)函數(shù)是指對(duì)問(wèn)題所追求目標(biāo)的數(shù)學(xué)描述。例如總利潤(rùn)最大、總成本最小等。（3）約束條件是指實(shí)現(xiàn)問(wèn)題目標(biāo)的限制因素。如原材料供應(yīng)量、生產(chǎn)能力、市場(chǎng)需求等，它們限制了目標(biāo)值所能實(shí)現(xiàn)的程度。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型【解】例1-1可用表1-1表示。每個(gè)產(chǎn)品所需工時(shí)（小時(shí)）每周可用工時(shí)（小時(shí)）門(mén)窗車(chē)間1104車(chē)間20212車(chē)間33218單位利潤(rùn)（元）3005001.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型（1）決策變量本問(wèn)題的決策變量是兩種新產(chǎn)品（門(mén)和窗）的每周產(chǎn)量?？稍O(shè)：x1表示門(mén)的每周產(chǎn)量（扇）；

x2表示窗的每周產(chǎn)量（扇）。（2）目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是兩種新產(chǎn)品的總利潤(rùn)最大。由于門(mén)和窗的單位利潤(rùn)分別為300元和500元，而其每周產(chǎn)量分別為x1和x2

，所以每周總利潤(rùn)z可表示為：

z=300x1＋500x2

1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型（3）約束條件本問(wèn)題的約束條件共有四個(gè)。車(chē)間1每周可用工時(shí)限制：x1

4車(chē)間2每周可用工時(shí)限制：2x212車(chē)間3每周可用工時(shí)限制：3x1

+2x218非負(fù)約束：x10,x201.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-1的線(xiàn)性規(guī)劃（數(shù)學(xué)）模型:這是一個(gè)典型的總利潤(rùn)最大化的生產(chǎn)計(jì)劃問(wèn)題。其中，“max”是英文單詞“maximize”的縮寫(xiě)，含義為“最大化”；“s.t.”是“subjectto”的縮寫(xiě)，意思是“受約束于……”。因此，上述模型的含義是：在給定的條件限制（約束）下，求目標(biāo)函數(shù)z

達(dá)到最大時(shí)x1，x2

的取值。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型

本章討論的問(wèn)題均為線(xiàn)性規(guī)劃問(wèn)題。

如果目標(biāo)函數(shù)是關(guān)于決策變量的線(xiàn)性函數(shù)，而且約束條件也都是關(guān)于決策變量的線(xiàn)性等式或線(xiàn)性不等式，則相應(yīng)的規(guī)劃問(wèn)題就稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-2

營(yíng)養(yǎng)配餐問(wèn)題。某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，兩種原料包含的營(yíng)養(yǎng)成分和采購(gòu)成本都不相同，公司管理層希望能夠確定混合飼料中兩種原料的數(shù)量，使得飼料能夠以最小的成本達(dá)到一定的營(yíng)養(yǎng)要求。研究者根據(jù)這一目標(biāo)收集到的有關(guān)數(shù)據(jù)如表1-2所示。營(yíng)養(yǎng)成分每千克玉米每千克紅薯營(yíng)養(yǎng)要求碳水化合物8420蛋白質(zhì)3618維生素1516采購(gòu)成本（元）1.81.6

1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型【解】（1）決策變量本問(wèn)題要決策（確定）的是混合飼料中兩種原料的數(shù)量（原料采購(gòu)量）?？稍O(shè)：

x1

為玉米采購(gòu)量；x2

為紅薯采購(gòu)量。（2）目標(biāo)函數(shù)本問(wèn)題的目標(biāo)是混合飼料的總成本最小，即：1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型（3）約束條件本問(wèn)題共有四個(gè)約束條件。①滿(mǎn)足三種營(yíng)養(yǎng)要求

碳水化合物的營(yíng)養(yǎng)要求：8x1

+4x220

蛋白質(zhì)的營(yíng)養(yǎng)要求：3x1

+6x218

維生素的營(yíng)養(yǎng)要求：x1

+5x216

②非負(fù)約束：x10,x201.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-2的線(xiàn)性規(guī)劃模型：這是一個(gè)典型的總成本最小化問(wèn)題。其中，“min”是英文單詞“minimize”的縮寫(xiě)，含義為“最小化”。因此，上述模型的含義是：在給定的條件限制（約束）下，求目標(biāo)函數(shù)z

達(dá)到最小時(shí)x1，x2的取值。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問(wèn)題。某物流公司需將三個(gè)工廠(chǎng)（工廠(chǎng)1、工廠(chǎng)2、工廠(chǎng)3）生產(chǎn)的一種新產(chǎn)品運(yùn)送到A、B兩個(gè)倉(cāng)庫(kù)，工廠(chǎng)1和工廠(chǎng)2的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)A，數(shù)量不限；工廠(chǎng)3的產(chǎn)品可以通過(guò)鐵路運(yùn)送到倉(cāng)庫(kù)B，同樣，數(shù)量不限。由于鐵路運(yùn)輸成本較高，公司同時(shí)考慮用卡車(chē)來(lái)運(yùn)送，但每個(gè)工廠(chǎng)要用卡車(chē)先將產(chǎn)品運(yùn)送到配送中心（每個(gè)工廠(chǎng)用卡車(chē)最多運(yùn)送60單位），再?gòu)呐渌椭行挠每ㄜ?chē)運(yùn)送到各個(gè)倉(cāng)庫(kù)（每個(gè)倉(cāng)庫(kù)最多收到用卡車(chē)運(yùn)送來(lái)的貨物90單位）。公司管理層希望以最小的成本來(lái)運(yùn)送所需的貨物。1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問(wèn)題（續(xù)）。每條線(xiàn)路上的單位運(yùn)輸成本和各工廠(chǎng)產(chǎn)品的產(chǎn)量以及各倉(cāng)庫(kù)分配量（需求量）等數(shù)據(jù)，如表1-3所示。配送中心倉(cāng)庫(kù)A倉(cāng)庫(kù)B產(chǎn)量工廠(chǎng)13.07.5－100工廠(chǎng)23.58.2－80工廠(chǎng)33.4－9.270配送中心－2.32.3

需求量－120130

1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型【解】例1-3物流網(wǎng)絡(luò)配送問(wèn)題--配送網(wǎng)絡(luò)圖9.22.390902.38.23.43.53.06060607.513TBA28070120130配送中心100產(chǎn)量工廠(chǎng)單位運(yùn)輸成本倉(cāng)庫(kù)需求量1.1線(xiàn)性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問(wèn)題--線(xiàn)性規(guī)劃模型1.1.2線(xiàn)性規(guī)劃的模型結(jié)構(gòu)線(xiàn)性規(guī)劃的一般形式為:

對(duì)于一組決策變量x1，x2，，xn，取1.1.2線(xiàn)性規(guī)劃的模型結(jié)構(gòu)在線(xiàn)性規(guī)劃模型中，也直接稱(chēng)z為“目標(biāo)函數(shù)”；稱(chēng)xj(j=1,2,

,n)為“決策變量”；稱(chēng)cj(j=1,2,

,n)

為“目標(biāo)函數(shù)系數(shù)”、“價(jià)值系數(shù)”或“費(fèi)用系數(shù)”；稱(chēng)bi(i=1,2,

,m)為“約束條件的右邊項(xiàng)”或簡(jiǎn)稱(chēng)“右邊項(xiàng)”，也稱(chēng)“資源常數(shù)”；稱(chēng)aij(i=1,2,

,m;j=1,2,

,n)為“技術(shù)系數(shù)”或“工藝系數(shù)”。這里，cj，bi，aij均為常數(shù)（稱(chēng)為模型參數(shù)）。線(xiàn)性規(guī)劃的數(shù)學(xué)模型可以表示為下列簡(jiǎn)潔的形式：1.2線(xiàn)性規(guī)劃的圖解法對(duì)于只有兩個(gè)變量的線(xiàn)性規(guī)劃問(wèn)題，可以在二維直角坐標(biāo)平面上作圖求解（圖1-2）可行域與最優(yōu)解線(xiàn)性規(guī)劃的圖解法1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題在Excel中建立線(xiàn)性規(guī)劃模型利用Excel求解線(xiàn)性規(guī)劃問(wèn)題應(yīng)用名稱(chēng)建好電子表格模型的幾個(gè)原則1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題在用Excel電子表格建立數(shù)學(xué)模型（這里是一個(gè)線(xiàn)性規(guī)劃模型）的過(guò)程中，有三個(gè)問(wèn)題需要回答：（1）要做出的決策是什么？（決策變量）（2）做出這些決策時(shí)，有哪些約束條件？

（約束條件）（3）這些決策的目標(biāo)是什么？（目標(biāo)函數(shù)）1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題圖1-5例1-1完整的電子表格模型（求解前）數(shù)據(jù)單元格、可變單元格、輸出單元格、目標(biāo)單元格在Excel中加載“規(guī)劃求解”功能第一步：?jiǎn)螕簟拔募边x項(xiàng)卡，在彈出的列表中單擊“選項(xiàng)”，這時(shí)將出現(xiàn)“Excel選項(xiàng)”對(duì)話(huà)框。第二步：在“Excel選項(xiàng)”對(duì)話(huà)框中，單擊左側(cè)的“加載項(xiàng)”，在右下方“管理”下拉列表中選擇“Exce1加載項(xiàng)”，然后單擊“轉(zhuǎn)到”按鈕，打開(kāi)“加載項(xiàng)”對(duì)話(huà)框。第三步：在“加載項(xiàng)”對(duì)話(huà)框中，勾選“規(guī)劃求解加載項(xiàng)”，單擊“確定”按鈕。這樣，Excel工作窗口的“數(shù)據(jù)”選項(xiàng)卡的“分析”組中將出現(xiàn)“規(guī)劃求解”。1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題圖1-6利用Excel“規(guī)劃求解”功能求解例1-1（“規(guī)劃求解參數(shù)”對(duì)話(huà)框）1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題圖1-9規(guī)劃求解后例1-1的電子表格模型（沒(méi)有給單元格命名）1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題

應(yīng)用名稱(chēng)利用Excel的“規(guī)劃求解”功能求解規(guī)劃問(wèn)題，應(yīng)用名稱(chēng)能使規(guī)劃問(wèn)題的電子表格模型更容易理解。主要表現(xiàn)在以下兩個(gè)方面：（1）在公式中應(yīng)用名稱(chēng)，人們更容易理解公式的含義；（2）在“規(guī)劃求解參數(shù)”對(duì)話(huà)框中應(yīng)用名稱(chēng)，人們更容易理解規(guī)劃模型的含義。因此，一般會(huì)為與公式和規(guī)劃模型有關(guān)的四類(lèi)單元格命名。例如，在例1-1的電子表格模型中，分別為下列單元格命名：（1）數(shù)據(jù)單元格：?jiǎn)挝焕麧?rùn)（C4:D4）、可用工時(shí)（G7:G9）；（2）可變單元格：每周產(chǎn)量（C12:D12）；（3）輸出單元格：實(shí)際使用（E7:E9）；（4）目標(biāo)單元格：總利潤(rùn)（G12）。1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題應(yīng)用名稱(chēng)圖1-19規(guī)劃求解后例1-1的電子表格模型（應(yīng)用名稱(chēng)）1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題電子表格建模是一門(mén)藝術(shù)，建立一個(gè)好的電子表格模型應(yīng)遵循以下幾個(gè)原則：（1）首先輸入數(shù)據(jù)；（2）清楚地標(biāo)識(shí)數(shù)據(jù)；（3）每個(gè)數(shù)據(jù)輸入到唯一的單元格中；（4）將數(shù)據(jù)與公式分離；（5）保持簡(jiǎn)單化（使用SUMPRODUCT函數(shù)、SUM函數(shù)、中間結(jié)果等）；（6）應(yīng)用名稱(chēng)；（7）使用相對(duì)引用和絕對(duì)引用，以便簡(jiǎn)化公式的復(fù)制；（8）使用邊框、背景色（填充顏色）來(lái)區(qū)分單元格類(lèi)型（四類(lèi)單元格）；（9）在電子表格中顯示整個(gè)模型（包括符號(hào)和數(shù)據(jù)）。Excel提供了許多有效的工具來(lái)幫助用戶(hù)進(jìn)行規(guī)劃模型調(diào)試，其中一個(gè)工具是將電子表格的輸出單元格在數(shù)值（運(yùn)算結(jié)果）和公式之間切換:“公式”選項(xiàng)卡－>“公式審核”組－>“顯示公式”

1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題圖1-21例1-2的電子表格模型1.3利用Excel求解線(xiàn)性規(guī)劃問(wèn)題圖1-22例1-3的電子表格模型1.4線(xiàn)性規(guī)劃問(wèn)題求解的幾種可能結(jié)果唯一解無(wú)窮多解無(wú)解可行域無(wú)界（目標(biāo)值不收斂）1.4線(xiàn)性規(guī)劃問(wèn)題求解的幾種可能結(jié)果唯一解線(xiàn)性規(guī)劃問(wèn)題具有唯一解是指該線(xiàn)性規(guī)劃問(wèn)題有且僅有一個(gè)既在可行域內(nèi)又使目標(biāo)值達(dá)到最優(yōu)的解例1-1就是一個(gè)具有唯一解的線(xiàn)性規(guī)劃問(wèn)題（圖1-2）1.4線(xiàn)性規(guī)劃問(wèn)題求解的幾種可能結(jié)果無(wú)窮多解線(xiàn)性規(guī)劃問(wèn)題具有無(wú)窮多解是指該線(xiàn)性規(guī)劃問(wèn)題有無(wú)窮多個(gè)既在可行域內(nèi)又使目標(biāo)值達(dá)到最優(yōu)的解在例1-1中，假設(shè)門(mén)的單位利潤(rùn)從300元增加至750元，這時(shí)該問(wèn)題的解將發(fā)生變化（圖1-23）1.4線(xiàn)性規(guī)劃問(wèn)題求解的幾種可能結(jié)果無(wú)解當(dāng)線(xiàn)性規(guī)劃問(wèn)題中的約束條件不能同時(shí)滿(mǎn)足時(shí)，無(wú)可行域的情況將會(huì)出現(xiàn)，這時(shí)不存在可行解，即該線(xiàn)性規(guī)劃問(wèn)題無(wú)解在例1-1中，若要求門(mén)的每周產(chǎn)量不得少于6，則需再加上一個(gè)約束條件：x16（圖1-24）1.4線(xiàn)性規(guī)劃問(wèn)題求解的幾種可能結(jié)果可行域無(wú)界（目標(biāo)值不收斂）線(xiàn)性規(guī)劃問(wèn)題的可行域無(wú)界，是指最大化問(wèn)題中的目標(biāo)函數(shù)值可以無(wú)限增大，或最小化問(wèn)題中的目標(biāo)函數(shù)值可以無(wú)限減少在例1-1中，如果沒(méi)有車(chē)間可用工時(shí)的約束，但要求門(mén)與窗的總產(chǎn)量不得少于4（圖1-26）1.5建立規(guī)劃模型的流程建立規(guī)劃模型的工作既是一門(mén)科學(xué)，又是一門(mén)藝術(shù)。否是否是實(shí)際問(wèn)題向規(guī)劃問(wèn)題的提煉確定決策變量確定目標(biāo)函數(shù)確定約束條件是否有無(wú)法定量表述的成分輔助決策實(shí)際應(yīng)用模型分析和檢驗(yàn)，提交定量報(bào)告解讀軟件運(yùn)行結(jié)果開(kāi)展人機(jī)對(duì)話(huà)，把數(shù)學(xué)模型軟件化上機(jī)調(diào)試是否通過(guò)報(bào)告補(bǔ)充：WPS表格WPS表格，也有“規(guī)劃求解”，在“數(shù)據(jù)”->“模擬分析”->“規(guī)劃求解”。WPS的“規(guī)劃求解”功能，可以完成：線(xiàn)性規(guī)劃的求解方法：?jiǎn)渭兙€(xiàn)性規(guī)劃，與Excel的“規(guī)劃求解”相同；非線(xiàn)性規(guī)劃的求解方法：非線(xiàn)性?xún)?nèi)點(diǎn)法，與Excel的“規(guī)劃求解”求解方法（非線(xiàn)性GRG）不同。不同點(diǎn)：在“公式”中應(yīng)用名稱(chēng)，操作不同(Excel自動(dòng)引用名稱(chēng)，WPS表格需要手動(dòng)“粘貼”名稱(chēng)或手動(dòng)輸入名稱(chēng)）；在“規(guī)劃求解參數(shù)”對(duì)話(huà)框中應(yīng)用名稱(chēng)，操作相同（Excel自動(dòng)引用名稱(chēng)，但WPS表格第一次求解時(shí)目標(biāo)和可變單元格沒(méi)有自動(dòng)引用名稱(chēng)，第二次求解時(shí)才自動(dòng)引用名稱(chēng)）。Excel的“規(guī)劃求解”有“演化”求解方法，但WPS表格沒(méi)有。本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>

在Excel中加載“規(guī)劃求解”功能，利用Excel求解線(xiàn)性規(guī)劃問(wèn)題。2．內(nèi)容和要求

（1）在Excel中，加載“規(guī)劃求解”功能；

（2）在Excel中，建立新問(wèn)題，輸入模型，求解模型，對(duì)結(jié)果進(jìn)行簡(jiǎn)單分析。3．操作步驟

利用Excel求解習(xí)題1.1、習(xí)題1.2（或其他習(xí)題）。

（1）在Excel中建立電子表格模型：輸入數(shù)據(jù)、給單元格或區(qū)域命名、輸入公式等；

（2）利用Excel中的“規(guī)劃求解”功能求解線(xiàn)性規(guī)劃問(wèn)題；

（3）結(jié)果分析：如每月生產(chǎn)四種產(chǎn)品各多少?lài)?？總利?rùn)是多少？哪些原料有剩余？并對(duì)結(jié)果提出自己的看法；

（4）在Word文檔（或PowerPoint演示文稿）中撰寫(xiě)實(shí)驗(yàn)報(bào)告，包括線(xiàn)性規(guī)劃模型、電子表格模型和結(jié)果分析等。第2章線(xiàn)性規(guī)劃的敏感性分析SensitivityAnalysisforLinearProgramming實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）本章內(nèi)容要點(diǎn)線(xiàn)性規(guī)劃的敏感性分析利用Excel進(jìn)行敏感性分析本章主要內(nèi)容框架圖2.1線(xiàn)性規(guī)劃的敏感性分析在第1章的討論中，假定線(xiàn)性規(guī)劃模型中的所有系數(shù)（包括目標(biāo)函數(shù)系數(shù)cj、工藝系數(shù)aij、約束條件的右邊項(xiàng)bi）都是確定的常數(shù)，并根據(jù)這些數(shù)據(jù)，求得最優(yōu)解。2.1線(xiàn)性規(guī)劃的敏感性分析但事實(shí)上，系數(shù)cj、aij、bi都有可能變化，因此，要再對(duì)這些系數(shù)進(jìn)行進(jìn)一步的分析，以決定是否需要調(diào)整決策。敏感性分析研究的另一類(lèi)問(wèn)題是探討在原線(xiàn)性規(guī)劃模型的基礎(chǔ)上增加一個(gè)變量或者一個(gè)約束條件對(duì)最優(yōu)解的影響。2.1線(xiàn)性規(guī)劃的敏感性分析對(duì)例1-1進(jìn)行敏感性分析最優(yōu)解為（2，6），最優(yōu)值為36002.1線(xiàn)性規(guī)劃的敏感性分析問(wèn)題1：如果門(mén)的單位利潤(rùn)由原來(lái)的300元增加到500元，最優(yōu)解是否會(huì)發(fā)生變化？對(duì)總利潤(rùn)又會(huì)產(chǎn)生怎樣的影響?問(wèn)題2：如果門(mén)和窗的單位利潤(rùn)都發(fā)生變化，最優(yōu)解會(huì)不會(huì)發(fā)生變化？對(duì)總利潤(rùn)又會(huì)產(chǎn)生怎樣的影響?問(wèn)題3：如果車(chē)間2的可用工時(shí)增加1小時(shí)，總利潤(rùn)是否會(huì)發(fā)生變化？如何改變?最優(yōu)解是否會(huì)發(fā)生變化?問(wèn)題4：如果同時(shí)改變多個(gè)車(chē)間的可用工時(shí)，總利潤(rùn)是否會(huì)發(fā)生變化？如何改變?最優(yōu)解是否會(huì)發(fā)生變化?問(wèn)題5：如果車(chē)間2更新生產(chǎn)工藝，生產(chǎn)一扇窗由原來(lái)的2小時(shí)縮短為1.5小時(shí),最優(yōu)解是否會(huì)發(fā)生變化？總利潤(rùn)是否會(huì)發(fā)生變化？問(wèn)題6：工廠(chǎng)考慮增加一種新產(chǎn)品（防盜門(mén)），總利潤(rùn)是否會(huì)發(fā)生變化？問(wèn)題7：如果工廠(chǎng)新增用電限制，是否會(huì)改變?cè)瓉?lái)的最優(yōu)方案？2.2單個(gè)目標(biāo)函數(shù)系數(shù)變化的敏感性分析下面討論在假定只有一個(gè)系數(shù)cj發(fā)生變化，模型中的其他參數(shù)保持不變的情況下，單個(gè)目標(biāo)函數(shù)系數(shù)的變化對(duì)最優(yōu)解的影響。例1-1的問(wèn)題1：如果當(dāng)初對(duì)門(mén)的單位利潤(rùn)估計(jì)不準(zhǔn)確，如把它改成500元，是否會(huì)影響求得的最優(yōu)解呢？方法1：利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能）；方法2：利用“敏感性報(bào)告”尋找單個(gè)目標(biāo)函數(shù)系數(shù)的允許變化范圍。2.2單個(gè)目標(biāo)函數(shù)系數(shù)變化的敏感性分析方法1：利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能）。可以借助電子表格互動(dòng)地展開(kāi)敏感性分析。當(dāng)模型參數(shù)發(fā)生改變時(shí)，只要修改電子表格模型中相應(yīng)的參數(shù)，再重新運(yùn)行Excel“規(guī)劃求解”功能，就可以看出改變參數(shù)對(duì)最優(yōu)解和最優(yōu)值的影響。需要逐個(gè)嘗試，效率略顯低下。求解結(jié)果為：最優(yōu)解沒(méi)有發(fā)生改變，仍然是（2，6）。由于門(mén)的單位利潤(rùn)增加了500－300＝200（元），因此總利潤(rùn)增加了200×2＝400（元）2.2單個(gè)目標(biāo)函數(shù)系數(shù)變化的敏感性分析方法2：利用“敏感性報(bào)告”尋找單個(gè)目標(biāo)函數(shù)系數(shù)的允許變化范圍。生成“敏感性報(bào)告”工作表；讀懂相應(yīng)的信息。當(dāng)門(mén)的單位利潤(rùn)從300元增加到500元時(shí)，還是在c1允許的變化范圍內(nèi)，最優(yōu)解不會(huì)發(fā)生變化，仍然是（2，6）。c1允許的變化范圍：[300-300，300+450]

即[0,750]

2.2單個(gè)目標(biāo)函數(shù)系數(shù)變化的敏感性分析結(jié)果：最優(yōu)解沒(méi)有發(fā)生變化，仍然是（2，6）；由于門(mén)的單位利潤(rùn)增加了500－300＝200（元），因此總利潤(rùn)增加了200×2＝400（元）。2.2單個(gè)目標(biāo)函數(shù)系數(shù)變化的敏感性分析圖解法：直觀可以看到

最優(yōu)解（2，6）

保持不變

。2.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的敏感性分析多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化對(duì)最優(yōu)解的影響。例1-1的問(wèn)題2：假如原先門(mén)的單位利潤(rùn)（300元）低估了，現(xiàn)在升為450元；同時(shí)，以前窗的單位利潤(rùn)（500元）高估了，現(xiàn)在降為400元。這樣的變化是否會(huì)導(dǎo)致最優(yōu)解發(fā)生變化呢？方法1：利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能）；方法2：利用“敏感性報(bào)告”進(jìn)行分析（目標(biāo)函數(shù)系數(shù)同時(shí)變化的百分之百法則）。2.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的敏感性分析方法1：利用電子表格進(jìn)行互動(dòng)分析，重新運(yùn)行Excel“規(guī)劃求解”功能?？梢钥闯觯顑?yōu)解并沒(méi)有發(fā)生變化，總利潤(rùn)由于門(mén)和窗的單位利潤(rùn)的改變相應(yīng)地改變了(450－300)×2＋(400－500)×6＝－3002.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的敏感性分析方法2：利用“敏感性報(bào)告”進(jìn)行分析。目標(biāo)函數(shù)系數(shù)同時(shí)變化的百分之百法則：如果目標(biāo)函數(shù)系數(shù)同時(shí)變化，計(jì)算出每一系數(shù)變化量占該系數(shù)允許變化量（允許的增量或允許的減量）的百分比，然后將各個(gè)系數(shù)變化的百分比相加。如果所得的變化的百分比總和不超過(guò)100%，則最優(yōu)解不會(huì)改變；如果超過(guò)了100%，則不能確定最優(yōu)解是否改變（可能改變，也可能不變），可通過(guò)重新運(yùn)行Excel“規(guī)劃求解”功能來(lái)判斷。由于變化的百分比總和不超過(guò)100%，因而可以確定最優(yōu)解仍為（2，6）。2.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的敏感性分析但是變化的百分比總和超過(guò)了100%，并不表示最優(yōu)解一定會(huì)改變。例如，門(mén)和窗的單位利潤(rùn)都減半變化的百分比總和超過(guò)了100%，但從右圖看最優(yōu)解還是（2，6），沒(méi)有發(fā)生改變。這是由于這兩個(gè)單位利潤(rùn)同比例變化，等利潤(rùn)直線(xiàn)的斜率不變，因此最優(yōu)解就保持不變。2.4單個(gè)約束右邊項(xiàng)變化的敏感性分析單個(gè)約束右邊項(xiàng)變化對(duì)目標(biāo)值的影響。例1-1的問(wèn)題3：如果車(chē)間2的可用工時(shí)增加1小時(shí)，總利潤(rùn)是否會(huì)發(fā)生變化？如何改變?最優(yōu)解是否會(huì)發(fā)生變化?方法1：利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能）；方法2：從“敏感性報(bào)告”中獲得關(guān)鍵信息（影子價(jià)格，shadowprice）。2.4單個(gè)約束右邊項(xiàng)變化的敏感性分析方法1：利用電子表格進(jìn)行互動(dòng)分析，重新運(yùn)行Excel“規(guī)劃求解”功能?？偫麧?rùn)為3750元，增加了3750－3600＝150（元）。由于總利潤(rùn)增加了，而目標(biāo)函數(shù)系數(shù)不變，因此最優(yōu)解一定會(huì)發(fā)生改變，從圖中可以看出，最優(yōu)解由原來(lái)的（2，6）變?yōu)椋?.667，6.5）。2.4單個(gè)約束右邊項(xiàng)變化的敏感性分析方法2：從“敏感性報(bào)告”中獲得關(guān)鍵信息。影子價(jià)格（shadowprice）：是指線(xiàn)性規(guī)劃模型在保持其他參數(shù)不變的前提下，某個(gè)約束的右邊項(xiàng)在一個(gè)微小的范圍內(nèi)變動(dòng)一單位時(shí)，導(dǎo)致的最優(yōu)目標(biāo)函數(shù)值的變動(dòng)量。第二個(gè)約束條件（車(chē)間2的工時(shí)約束）的影子價(jià)格是150，說(shuō)明在允許變化范圍[6，18]（即[12-6，12+6]）內(nèi)，再增加（或減少）1小時(shí)的可用工時(shí)，總利潤(rùn)將增加（或減少）150（元）。2.4單個(gè)約束右邊項(xiàng)變化的敏感性分析圖解法：直觀可以看到

在這個(gè)范圍內(nèi)，車(chē)間2的約束右邊項(xiàng)每增加（或減少）1個(gè)單位，交點(diǎn)的移動(dòng)就使利潤(rùn)增長(zhǎng)（或減少）1個(gè)影子價(jià)格的數(shù)量（150元）。2.5多個(gè)約束右邊項(xiàng)同時(shí)變化的敏感性分析多個(gè)約束右邊項(xiàng)同時(shí)變化對(duì)目標(biāo)值的影響。例1-1的問(wèn)題4：將1小時(shí)的工時(shí)從車(chē)間3移到車(chē)間2，對(duì)總利潤(rùn)所產(chǎn)生的影響。方法1：利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能）；方法2：利用“敏感性報(bào)告”進(jìn)行分析（約束右邊項(xiàng)同時(shí)變化的百分之百法則）。2.5多個(gè)約束右邊項(xiàng)同時(shí)變化的敏感性分析方法1：利用電子表格進(jìn)行互動(dòng)分析，重新運(yùn)行Excel“規(guī)劃求解”功能?？偫麧?rùn)增加了3650-3600=50（元），影子價(jià)格有效。2.5多個(gè)約束右邊項(xiàng)同時(shí)變化的敏感性分析方法2：利用“敏感性報(bào)告”進(jìn)行分析。約束右邊項(xiàng)同時(shí)變化的百分之百法則：如果約束右邊項(xiàng)同時(shí)變化，計(jì)算每一右邊項(xiàng)變化量占該約束右邊項(xiàng)允許變化量（允許的增量或允許的減量）的百分比，然后將各個(gè)約束右邊項(xiàng)的變化的百分比相加。如果所得的變化的百分比總和不超過(guò)100%，那么影子價(jià)格依然有效；如果超過(guò)了100％，就無(wú)法確定影子價(jià)格是否依然有效（可能有效，也可能無(wú)效），可通過(guò)重新運(yùn)行Excel“規(guī)劃求解”功能來(lái)判斷。由于變化的百分比總和不超過(guò)100%，因此用影子價(jià)格來(lái)預(yù)測(cè)這些變化的影響是有效的?？偫麧?rùn)的變化量為：（13－12）×150－（18－17）×100＝50（元）2.5多個(gè)約束右邊項(xiàng)同時(shí)變化的敏感性分析在影子價(jià)格的有效范圍內(nèi)，總利潤(rùn)的變化量可以直接通過(guò)影子價(jià)格來(lái)計(jì)算。比如將車(chē)間3的3個(gè)工時(shí)轉(zhuǎn)移給車(chē)間2，由于所以，總利潤(rùn)的變化量為2.6約束條件系數(shù)變化的敏感性分析例1-1的問(wèn)題5：車(chē)間2更新生產(chǎn)工藝，生產(chǎn)一扇窗由原來(lái)的2小時(shí)縮短為1.5小時(shí),此時(shí)最優(yōu)解是否會(huì)發(fā)生變化？總利潤(rùn)是否會(huì)發(fā)生變化？利用電子表格進(jìn)行互動(dòng)分析(重新運(yùn)行Excel“規(guī)劃求解”功能)重新運(yùn)行Excel“規(guī)劃求解”功能后，最優(yōu)解發(fā)生了改變，變?yōu)椋?/3，8），總利潤(rùn)也由原來(lái)的3600元增加到4200元。可見(jiàn)，車(chē)間2更新生產(chǎn)工藝后，為工廠(chǎng)增加了利潤(rùn)。2.7增加一個(gè)新變量例1-1的問(wèn)題6：例2-1工廠(chǎng)考慮增加一種新產(chǎn)品---防盜門(mén)，假設(shè)其單位利潤(rùn)為400元。生產(chǎn)一扇防盜門(mén)占用車(chē)間1、車(chē)間2、車(chē)間3的時(shí)間分別為2小時(shí)、1小時(shí)、1小時(shí)。請(qǐng)問(wèn)新產(chǎn)品是否能為工廠(chǎng)帶來(lái)利潤(rùn)？利用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”功能)最優(yōu)解為(2,5.5,1）,總利潤(rùn)為3750元?？梢?jiàn)新產(chǎn)品為工廠(chǎng)增加了利潤(rùn)。2.8增加一個(gè)約束條件例1-1的問(wèn)題7：增加電量供應(yīng)限制。例2-2

在例1-1中，假定生產(chǎn)一扇門(mén)和窗需要消耗的電量分別為20kW·h和10kW·h，工廠(chǎng)可供電量最多為90kW·h，請(qǐng)問(wèn)在此情況下工廠(chǎng)的利潤(rùn)會(huì)發(fā)生何種變化?利用電子表格進(jìn)行互動(dòng)分析(重新運(yùn)行Excel“規(guī)劃求解”功能)可見(jiàn)，電量約束的確限制了門(mén)的每周產(chǎn)量（而窗的每周產(chǎn)量不變），最優(yōu)解變成(1.5,6),總利潤(rùn)也相應(yīng)地下降為3450元。2.9敏感性分析的應(yīng)用舉例例2-3力浦公司是一家生產(chǎn)外墻涂料的建材企業(yè)。目前生產(chǎn)甲、乙兩種規(guī)格的產(chǎn)品，這兩種產(chǎn)品在市場(chǎng)上的單位利潤(rùn)分別是4萬(wàn)元和5萬(wàn)元。甲、乙兩種產(chǎn)品均需要同時(shí)消耗A、B、C三種化工材料，生產(chǎn)1單位產(chǎn)品甲需要消耗三種材料（資源）的情況是：1單位材料A、2單位材料B和1單位材料C；而生產(chǎn)1單位的產(chǎn)品乙需要1單位材料A、1單位材料B和3單位材料C。當(dāng)前市場(chǎng)上甲、乙兩種產(chǎn)品供不應(yīng)求，但是在每個(gè)生產(chǎn)周期（假設(shè)一年）內(nèi)，公司的A、B、C三種原材料的儲(chǔ)備量分別是45單位、80單位和90單位，年終剩余的資源必須無(wú)償調(diào)回，而且近期也沒(méi)有能籌集到額外資源的渠道。面對(duì)這種局面，力浦公司應(yīng)如何制訂生產(chǎn)計(jì)劃，才能獲得最大的市場(chǎng)利潤(rùn)？2.9敏感性分析的應(yīng)用舉例該公司在運(yùn)營(yíng)了一年后，管理層對(duì)第二年的運(yùn)營(yíng)進(jìn)行了如下預(yù)想（假設(shè)以下問(wèn)題均單獨(dú)出現(xiàn)）：?jiǎn)栴}1：由于資源市場(chǎng)受到其他競(jìng)爭(zhēng)者活動(dòng)的影響，公司市場(chǎng)營(yíng)銷(xiāo)部門(mén)預(yù)測(cè)當(dāng)年的產(chǎn)品甲的價(jià)格將會(huì)產(chǎn)生變化，導(dǎo)致產(chǎn)品甲的單位利潤(rùn)在3.8萬(wàn)元～5.2萬(wàn)元之間波動(dòng)。應(yīng)對(duì)這種情況，公司該如何提前對(duì)生產(chǎn)格局做好調(diào)整預(yù)案？問(wèn)題2：由于供應(yīng)鏈上游的化工原料價(jià)格不斷上漲，給力浦公司帶來(lái)資源購(gòu)置上的壓力。公司采購(gòu)部門(mén)預(yù)測(cè)現(xiàn)有45單位限額的材料A將會(huì)出現(xiàn)3單位的資源缺口，但是也不排除通過(guò)其他渠道籌措來(lái)1單位材料A的可能。對(duì)于材料A的資源上限的增加或減少，力浦公司應(yīng)如何進(jìn)行新的規(guī)劃？問(wèn)題3：經(jīng)過(guò)規(guī)劃分析已經(jīng)知道，材料B在最優(yōu)生產(chǎn)格局中出現(xiàn)了12.5單位的剩余，那么公司應(yīng)如何重新制訂限額，做好節(jié)約工作？2.9敏感性分析的應(yīng)用舉例【解】例2-3力浦公司的線(xiàn)性規(guī)劃模型和電子表格模型。2.9敏感性分析的應(yīng)用舉例力浦公司的敏感性分析（問(wèn)題1、問(wèn)題2和問(wèn)題3）力浦公司的“敏感性報(bào)告”2.9敏感性分析的應(yīng)用舉例問(wèn)題1：當(dāng)產(chǎn)品甲的單位利潤(rùn)在3.8萬(wàn)元～5.2萬(wàn)元之間變化時(shí)對(duì)規(guī)劃（最優(yōu)解和最優(yōu)值）的影響根據(jù)“敏感性報(bào)告”，分段分析。針對(duì)產(chǎn)品甲的單位利潤(rùn)將會(huì)在3.8萬(wàn)元～5.2萬(wàn)元（[3.8,5.2]）之間波動(dòng)的預(yù)測(cè)，力浦公司應(yīng)制訂兩套預(yù)案：當(dāng)單位利潤(rùn)在3.8萬(wàn)元～5萬(wàn)元（[3.8,5]）之間時(shí)，甲、乙兩種產(chǎn)品的產(chǎn)量均為22.5單位；而單位利潤(rùn)在5萬(wàn)元～5.2萬(wàn)元（[5,5.2]）之間時(shí)，甲、乙兩種產(chǎn)品分別生產(chǎn)35單位和10單位?？梢钥闯?，當(dāng)產(chǎn)品甲的單位利潤(rùn)逐漸增加時(shí)，力浦公司一定會(huì)理性地將資源配置向產(chǎn)品甲傾斜。2.9敏感性分析的應(yīng)用舉例問(wèn)題2：當(dāng)資源A的限額（儲(chǔ)備量）在42～46單位變化時(shí)對(duì)規(guī)劃（最優(yōu)值和最優(yōu)解）的影響從“敏感性報(bào)告”可知：當(dāng)資源A的儲(chǔ)備量在[30,50]范圍內(nèi)變化時(shí)，影子價(jià)格有效。如果資源A的儲(chǔ)備量從45減少到42（出現(xiàn)3單位的資源缺口），則可以方便地計(jì)算出最優(yōu)值（總利潤(rùn)）為202.5－3×3.5＝192（萬(wàn)元）。重新規(guī)劃求解后，可知新的最優(yōu)解是（18，24）。同理，如果資源A的儲(chǔ)備量從45增加到46，則最優(yōu)值（總利潤(rùn)）為202.5＋1×3.5＝206（萬(wàn)元），重新規(guī)劃求解后，可知新的最優(yōu)解是（24，22）。2.9敏感性分析的應(yīng)用舉例問(wèn)題3：對(duì)資源B的限額（儲(chǔ)備量）的考察資源B是力浦公司尋求市場(chǎng)收益活動(dòng)中的一個(gè)有趣的約束。實(shí)質(zhì)上，該約束在當(dāng)前的最優(yōu)規(guī)劃的生產(chǎn)格局下，并沒(méi)有真正起到約束的作用。正如實(shí)際的規(guī)劃結(jié)果表明，資源B在取得最優(yōu)值后，尚有12.5單位的剩余。從“敏感性報(bào)告”中可知，資源B的儲(chǔ)備量的允許變化范圍是：資源B的最小合理儲(chǔ)備量是67.5單位。本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>

掌握利用Excel進(jìn)行敏感性分析的操作方法。2．內(nèi)容和要求

利用Excel求解習(xí)題2.1、習(xí)題2.3（或其他習(xí)題）。3．操作步驟

（1）在Excel中建立電子表格模型；（2）利用Excel中的“規(guī)劃求解”功能求解線(xiàn)性規(guī)劃問(wèn)題并生成“敏感性報(bào)告”；（3）結(jié)果分析：哪些問(wèn)題可以直接利用“敏感性報(bào)告”中的信息求解，哪些問(wèn)題需要重新運(yùn)行Excel“規(guī)劃求解”功能，并對(duì)結(jié)果提出自己的看法；（4）在Word文檔（或PowerPoint演示文稿）中撰寫(xiě)實(shí)驗(yàn)報(bào)告，包括線(xiàn)性規(guī)劃模型、電子表格模型、敏感性報(bào)告和結(jié)果分析等。實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）第3章運(yùn)輸問(wèn)題和指派問(wèn)題TheTransportationandAssignmentProblems本章內(nèi)容要點(diǎn)運(yùn)輸問(wèn)題的基本概念運(yùn)輸問(wèn)題的數(shù)學(xué)模型運(yùn)輸問(wèn)題的變形轉(zhuǎn)運(yùn)問(wèn)題指派問(wèn)題的基本概念指派問(wèn)題的變形本章主要內(nèi)容框架圖3.1運(yùn)輸問(wèn)題的基本概念運(yùn)輸問(wèn)題源于在日常生活中人們把某些物品或人們自身從一些地方轉(zhuǎn)移到另一些地方，要求所采用的運(yùn)輸路線(xiàn)或運(yùn)輸方案是最經(jīng)濟(jì)或成本最小的，這就成為一個(gè)運(yùn)籌學(xué)問(wèn)題。隨著經(jīng)濟(jì)水平的不斷提升，現(xiàn)代物流業(yè)蓬勃發(fā)展，如何充分利用時(shí)間、信息、倉(cāng)儲(chǔ)、配送和聯(lián)運(yùn)體系創(chuàng)造更多的價(jià)值，向運(yùn)籌學(xué)提出了更高的挑戰(zhàn)。這要求科學(xué)地組織貨源、運(yùn)輸和配送，使運(yùn)輸問(wèn)題變得日益復(fù)雜，但其基本思想仍然是實(shí)現(xiàn)現(xiàn)有資源的最優(yōu)化配置。3.1運(yùn)輸問(wèn)題的基本概念一般的運(yùn)輸問(wèn)題就是解決如何把某種產(chǎn)品從若干個(gè)產(chǎn)地調(diào)運(yùn)到若干個(gè)銷(xiāo)地的問(wèn)題，在每個(gè)產(chǎn)地的供應(yīng)量和每個(gè)銷(xiāo)地的需求量以及各地之間的運(yùn)輸單價(jià)已知的前提下，確定一個(gè)使得總運(yùn)輸成本最小的方案。平衡運(yùn)輸問(wèn)題的條件如下：（1）明確出發(fā)地（產(chǎn)地）、目的地（銷(xiāo)地）、供應(yīng)量（產(chǎn)量）、需求量（銷(xiāo)量）和單位運(yùn)輸成本。（2）需求假設(shè)：每一個(gè)出發(fā)地（產(chǎn)地）都有一個(gè)固定的供應(yīng)量，所有的供應(yīng)量都必須配送到目的地（銷(xiāo)地）。與之類(lèi)似，每一個(gè)目的地（銷(xiāo)地）都有一個(gè)固定的需求量，所有的需求量都必須由出發(fā)地（產(chǎn)地）滿(mǎn)足。即“總供應(yīng)量＝總需求量”。（3）成本假設(shè)：從任何一個(gè)出發(fā)地（產(chǎn)地）到任何一個(gè)目的地（銷(xiāo)地）的貨物運(yùn)輸成本與所運(yùn)送的貨物數(shù)量呈線(xiàn)性關(guān)系，因此，貨物運(yùn)輸成本就等于單位運(yùn)輸成本乘以所運(yùn)送的貨物數(shù)量（目標(biāo)函數(shù)是線(xiàn)性的）。3.2運(yùn)輸問(wèn)題的數(shù)學(xué)模型產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的數(shù)學(xué)模型設(shè)從產(chǎn)地Ai運(yùn)往銷(xiāo)地Bj的物資數(shù)量為xij（i=1,2,?,m;j=1,2,?,n)

3.2.1產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題例3-1

某公司有三個(gè)加工廠(chǎng)（A1、A2和A3）生產(chǎn)某種產(chǎn)品，每日的產(chǎn)量分別為7噸、4噸、9噸。該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷(xiāo)售點(diǎn)（B1、B2、B3和B4），四個(gè)銷(xiāo)售點(diǎn)每日的銷(xiāo)量分別為3噸、6噸、5噸、6噸。從三個(gè)加工廠(chǎng)（產(chǎn)地）到四個(gè)銷(xiāo)售點(diǎn)（銷(xiāo)地）的單位產(chǎn)品運(yùn)價(jià)如表3-2所示。問(wèn)該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，才能在滿(mǎn)足四個(gè)銷(xiāo)售點(diǎn)的銷(xiāo)量的前提下，使總運(yùn)費(fèi)最?。夸N(xiāo)售點(diǎn)B1銷(xiāo)售點(diǎn)B2銷(xiāo)售點(diǎn)B3銷(xiāo)售點(diǎn)B4加工廠(chǎng)A1311310加工廠(chǎng)A21928加工廠(chǎng)A3741053.2.1產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題【解】首先，三個(gè)加工廠(chǎng)A1、A2、A3的總產(chǎn)量為7＋4＋9＝20（噸）；四個(gè)銷(xiāo)售點(diǎn)B1、B2、B3、B4的總銷(xiāo)量為3＋6＋5＋6＝20（噸）。也就是說(shuō)，總產(chǎn)量等于總銷(xiāo)量，故該運(yùn)輸問(wèn)題是一個(gè)產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題。（1）決策變量

設(shè)xij為從加工廠(chǎng)Ai（i＝1,2,3）運(yùn)往銷(xiāo)售點(diǎn)Bj（j=1,2,3,4）的運(yùn)輸量。（2）目標(biāo)函數(shù)

本問(wèn)題的目標(biāo)是使公司的總運(yùn)費(fèi)最小。3.2.1產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題（3）約束條件①三個(gè)加工廠(chǎng)的產(chǎn)品全部都要運(yùn)送出去（產(chǎn)量約束）②四個(gè)銷(xiāo)售點(diǎn)的產(chǎn)品全部都要得到滿(mǎn)足（銷(xiāo)量約束）③非負(fù)3.2.1產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題是一種特殊的線(xiàn)性規(guī)劃問(wèn)題，一般采用“表上作業(yè)法”求解，但Excel的“規(guī)劃求解”功能還是采用“單純形法”來(lái)求解。例3-1的電子表格模型（1）設(shè)置條件格式的操作請(qǐng)參見(jiàn)本章附錄。（2）將單元格的字體和背景顏色設(shè)置為相同顏色以實(shí)現(xiàn)“渾然一體”的效果，可以起到隱藏單元格內(nèi)容的作用。當(dāng)單元格被選中時(shí)，編輯欄中仍然會(huì)顯示單元格的真實(shí)數(shù)據(jù)。（3）本章所有例題的最優(yōu)解（運(yùn)輸方案或指派方案）有一個(gè)共同特點(diǎn)，即“0”值較多，所以都使用了Excel的“條件格式”功能。3.2.1產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題例3-1的最優(yōu)調(diào)運(yùn)方案網(wǎng)絡(luò)圖A2A3A1B2B3B1B47365649231635產(chǎn)量

加工廠(chǎng)

運(yùn)輸量

銷(xiāo)售點(diǎn)

銷(xiāo)量運(yùn)輸問(wèn)題的整數(shù)解性質(zhì)需要注意的是：運(yùn)輸問(wèn)題有這樣一個(gè)性質(zhì)（整數(shù)解性質(zhì)），即只要它的產(chǎn)量（供應(yīng)量）和銷(xiāo)量（需求量）都是整數(shù)，任何存在可行解的運(yùn)輸問(wèn)題就必然存在所有決策變量都是整數(shù)的最優(yōu)解。因此，沒(méi)有必要加上所有決策變量都是整數(shù)的約束條件。由于運(yùn)輸量經(jīng)常以卡車(chē)、集裝箱等為單位，如果卡車(chē)不能裝滿(mǎn)，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)避免了運(yùn)輸量（運(yùn)輸方案）為小數(shù)的麻煩。3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題實(shí)際問(wèn)題中，產(chǎn)銷(xiāo)往往是不平衡的。（1）銷(xiāo)大于產(chǎn)（供不應(yīng)求）運(yùn)輸問(wèn)題的數(shù)學(xué)模型（以滿(mǎn)足小的產(chǎn)量為準(zhǔn)）3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題（2）產(chǎn)大于銷(xiāo)（供過(guò)于求）運(yùn)輸問(wèn)題的數(shù)學(xué)模型（以滿(mǎn)足小的銷(xiāo)量為準(zhǔn)）3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2自來(lái)水輸送問(wèn)題。某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A、B、C三個(gè)水庫(kù)供應(yīng)。四個(gè)居民區(qū)每天的基本生活用水量分別為3萬(wàn)噸、7萬(wàn)噸、1萬(wàn)噸、1萬(wàn)噸，但由于水源緊張，三個(gè)水庫(kù)每天最多只能分別供應(yīng)5萬(wàn)噸、6萬(wàn)噸、5萬(wàn)噸自來(lái)水。由于地理位置的差別，自來(lái)水公司從各水庫(kù)向各居民區(qū)供水所需支付的引水管理費(fèi)不同（見(jiàn)表3?4，其中水庫(kù)C與丁區(qū)之間沒(méi)有輸水管道），其他管理費(fèi)用都是4500元／萬(wàn)噸。根據(jù)公司規(guī)定，各居民區(qū)用戶(hù)按照統(tǒng)一標(biāo)準(zhǔn)9000元／萬(wàn)噸收費(fèi)。此外，四個(gè)居民區(qū)都向公司申請(qǐng)了額外用水量，分別為每天5萬(wàn)噸、7萬(wàn)噸、2萬(wàn)噸、4萬(wàn)噸。問(wèn)：（1）該公司應(yīng)如何分配供水量，才能獲利最大？（2）為了增加供水量，自來(lái)水公司正在考慮進(jìn)行水庫(kù)改造，使三個(gè)水庫(kù)每天的最大供水量都增加一倍，那時(shí)供水方案應(yīng)如何改變？公司利潤(rùn)可增加到多少？3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題【解】可以把“自來(lái)水輸送問(wèn)題”看作“運(yùn)輸問(wèn)題”，也就是用“運(yùn)輸問(wèn)題”的方法求解“自來(lái)水輸送問(wèn)題”。設(shè)xij為水庫(kù)i向居民區(qū)j的日供水量（11個(gè)變量）

3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（1）的線(xiàn)性規(guī)劃模型目標(biāo)：從獲利最大轉(zhuǎn)化為引水管理費(fèi)最小由于A、B、C三個(gè)水庫(kù)的總供水量5＋6＋5＝16，超過(guò)四個(gè)居民區(qū)的基本生活用水量之和3＋7＋1＋1＝12（供過(guò)于求），但又少于四個(gè)居民區(qū)的基本生活用水量與額外用水量之和（3＋7＋1＋1）＋（5＋7＋2＋4）＝30（供不應(yīng)求），所以本問(wèn)題既是“供過(guò)于求”又是“供不應(yīng)求”的不平衡運(yùn)輸問(wèn)題。

3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（1）的電子表格模型電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過(guò)增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒(méi)有輸水管道”。3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（1）的最優(yōu)供水方案網(wǎng)絡(luò)圖BCA乙丙甲丁5814356551541水庫(kù)供水量居民區(qū)最大供水量最大用水量3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（2）方法1的線(xiàn)性規(guī)劃模型目標(biāo)：將獲利最大轉(zhuǎn)化為引水管理費(fèi)最小由于A、B、C三個(gè)水庫(kù)每天的最大供水量都提高一倍，則公司總供水能力增加到16×2＝32萬(wàn)噸，大于總需求量30萬(wàn)噸，為“供過(guò)于求”的不平衡運(yùn)輸問(wèn)題。

3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（2）方法1

的電子表格模型電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過(guò)增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒(méi)有輸水管道”。3.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（2）的最優(yōu)供水方案網(wǎng)絡(luò)圖BCA乙丙甲丁10814351210105353水庫(kù)供水量居民區(qū)最大供水量最大用水量43.2.2產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題例3-2問(wèn)題（2）方法2：目標(biāo)為獲利最大電子表格模型中有12個(gè)變量（供水量，C9:F11區(qū)域），通過(guò)增加約束條件“$F$11＝0”，實(shí)現(xiàn)“水庫(kù)C與居民區(qū)丁之間沒(méi)有輸水管道”。

3.3運(yùn)輸問(wèn)題的變形現(xiàn)實(shí)生活中符合產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題的每個(gè)條件的情況很少。一個(gè)特征近似但其他一個(gè)或者幾個(gè)特征不符合產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題條件的運(yùn)輸問(wèn)題卻經(jīng)常出現(xiàn)。下面是要討論的一些特征：特征1：總供應(yīng)量大于總需求量。每個(gè)供應(yīng)量（產(chǎn)量）代表了從其出發(fā)地（產(chǎn)地）運(yùn)送出去的最大數(shù)量（而不是一個(gè)固定的數(shù)值，≤）特征2：總供應(yīng)量小于總需求量。每個(gè)需求量（銷(xiāo)量）代表了在其目的地（銷(xiāo)地）接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值，≤）特征3：一個(gè)目的地（銷(xiāo)地）同時(shí)存在最小需求量和最大需求量，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（需求量可在一定范圍內(nèi)變化，≥、≤）特征4：在運(yùn)輸中不能利用特定的出發(fā)地（產(chǎn)地）--目的地（銷(xiāo)地）組合（xij=0）特征5：目標(biāo)是使與運(yùn)輸量有關(guān)的總利潤(rùn)最大而不是使總成本最?。∕in－>

Max）3.3運(yùn)輸問(wèn)題的變形例3-3

某公司決定使用三個(gè)有生產(chǎn)余力的工廠(chǎng)進(jìn)行四種產(chǎn)品的生產(chǎn)。生產(chǎn)每單位產(chǎn)品需要等量的工作，所以工廠(chǎng)的有效生產(chǎn)能力以每天生產(chǎn)的任意種產(chǎn)品的數(shù)量來(lái)衡量（見(jiàn)表3-7的最右列）。而每種產(chǎn)品每天有一定的需求量（見(jiàn)表3-7的最后一行）。除了工廠(chǎng)2不能生產(chǎn)產(chǎn)品3以外，每個(gè)工廠(chǎng)都可以生產(chǎn)這些產(chǎn)品。然而，每種產(chǎn)品在不同工廠(chǎng)中的單位成本（元）是有差異的（如表3-7所示）?，F(xiàn)在需要決定的是在哪個(gè)工廠(chǎng)生產(chǎn)哪種產(chǎn)品，可使總成本最小。單位成本生產(chǎn)能力產(chǎn)品1產(chǎn)品2產(chǎn)品3產(chǎn)品4工廠(chǎng)24029一2375工廠(chǎng)33730272145需求量203030403.3運(yùn)輸問(wèn)題的變形【解】把“指定工廠(chǎng)生產(chǎn)產(chǎn)品問(wèn)題”看作“運(yùn)輸問(wèn)題”。本問(wèn)題中，工廠(chǎng)2不能生產(chǎn)產(chǎn)品3，這樣可以增加約束條件x23＝0

；并且總供應(yīng)量（75+75+45=195）>總需求量（20+30+30+40=120），是供大于求的運(yùn)輸問(wèn)題。其數(shù)學(xué)模型：設(shè)xij為工廠(chǎng)i生產(chǎn)產(chǎn)品j

的數(shù)量3.3運(yùn)輸問(wèn)題的變形例3-3的電子表格模型產(chǎn)品4分在2個(gè)工廠(chǎng)（工廠(chǎng)2和工廠(chǎng)3）生產(chǎn)3.3運(yùn)輸問(wèn)題的變形例3-4

需求量存在最小需求量和最大需求量（需求量可在一定范圍內(nèi)變化）的問(wèn)題。某公司在三個(gè)工廠(chǎng)中專(zhuān)門(mén)生產(chǎn)一種產(chǎn)品。在未來(lái)的四個(gè)月中，四個(gè)處于國(guó)內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能有大量訂購(gòu)該產(chǎn)品。顧客1是公司最重要的顧客，所以他的訂單要全部滿(mǎn)足；顧客2和顧客3也是公司很重要的顧客，所以營(yíng)銷(xiāo)經(jīng)理認(rèn)為至少要滿(mǎn)足他們訂單的1/3；對(duì)于顧客4，營(yíng)銷(xiāo)經(jīng)理認(rèn)為并不需要特殊考慮。由于運(yùn)輸成本的差異，單位利潤(rùn)也不同，利潤(rùn)很大程度上取決于哪個(gè)工廠(chǎng)供應(yīng)哪個(gè)顧客（見(jiàn)表3-8）。問(wèn)應(yīng)向每個(gè)顧客供應(yīng)多少產(chǎn)品，才能使公司的總利潤(rùn)最大？單位利潤(rùn)（元）產(chǎn)量（件）顧客1顧客2顧客3顧客4工廠(chǎng)1554246538000工廠(chǎng)2371832485000工廠(chǎng)3295951357000最少供應(yīng)量（件）7000300020000要求訂購(gòu)量（件）70009000600080003.3運(yùn)輸問(wèn)題的變形【解】該問(wèn)題要求滿(mǎn)足不同顧客的需求（訂購(gòu)量），解決辦法：實(shí)際供應(yīng)量

最少供應(yīng)量實(shí)際供應(yīng)量

要求訂購(gòu)量

目標(biāo)是總利潤(rùn)最大，而不是總成本最小。其數(shù)學(xué)模型：設(shè)xij為工廠(chǎng)i供應(yīng)顧客j的產(chǎn)品數(shù)量3.3運(yùn)輸問(wèn)題的變形例3-4的電子表格模型3.4轉(zhuǎn)運(yùn)問(wèn)題在實(shí)際工作中，有一類(lèi)問(wèn)題是需要先將物品由產(chǎn)地運(yùn)到某個(gè)中間轉(zhuǎn)運(yùn)地，這個(gè)轉(zhuǎn)運(yùn)地可以是產(chǎn)地、銷(xiāo)地或中間轉(zhuǎn)運(yùn)倉(cāng)庫(kù)，然后再運(yùn)到銷(xiāo)售目的地，這類(lèi)問(wèn)題稱(chēng)為轉(zhuǎn)運(yùn)問(wèn)題，可以通過(guò)建模轉(zhuǎn)化為運(yùn)輸問(wèn)題模型。例3-5

例3-1是一個(gè)普通的產(chǎn)銷(xiāo)平衡運(yùn)輸問(wèn)題，如果假定：（1）每個(gè)加工廠(chǎng)（產(chǎn)地）的產(chǎn)品不一定直接運(yùn)到銷(xiāo)售點(diǎn)（銷(xiāo)地），可以將其中幾個(gè)加工廠(chǎng)的產(chǎn)品集中一起運(yùn)；（2）運(yùn)往各銷(xiāo)售點(diǎn)的產(chǎn)品可以先運(yùn)給其中幾個(gè)銷(xiāo)售點(diǎn)，再轉(zhuǎn)運(yùn)給其他銷(xiāo)售點(diǎn)；（3）除產(chǎn)地、銷(xiāo)地之外，中間還可以有幾個(gè)轉(zhuǎn)運(yùn)站，在產(chǎn)地之間、銷(xiāo)地之間或產(chǎn)地與銷(xiāo)地之間轉(zhuǎn)運(yùn)。3.4轉(zhuǎn)運(yùn)問(wèn)題例3-5轉(zhuǎn)運(yùn)問(wèn)題（續(xù)）已知各產(chǎn)地、銷(xiāo)地、中間轉(zhuǎn)運(yùn)站及相互之間的單位產(chǎn)品運(yùn)價(jià)如表3-9所示，問(wèn)在考慮產(chǎn)銷(xiāo)地之間非直接運(yùn)輸?shù)那闆r下，如何將三個(gè)加工廠(chǎng)生產(chǎn)的產(chǎn)品運(yùn)往銷(xiāo)售點(diǎn)，才能使總運(yùn)費(fèi)最??？單位運(yùn)價(jià)加工廠(chǎng)（產(chǎn)地）中間轉(zhuǎn)運(yùn)站銷(xiāo)售點(diǎn)（銷(xiāo)地）A1A2A3T1T2T3T4B1B2B3B4加工廠(chǎng)（產(chǎn)地）A1

132143311310A21

一35一21928A33一

1一2374105中間轉(zhuǎn)運(yùn)站T1231

1322846T215一1

114527T34一231

21824T4323212

1一26銷(xiāo)售點(diǎn)（銷(xiāo)地）B13172411

142B21194858一1

21B33210422242

3B410856746213

3.4轉(zhuǎn)運(yùn)問(wèn)題【解】現(xiàn)在把該轉(zhuǎn)運(yùn)問(wèn)題轉(zhuǎn)化成一般運(yùn)輸問(wèn)題，要做如下處理：（1）由于問(wèn)題中的所有加工廠(chǎng)、中間轉(zhuǎn)運(yùn)站、銷(xiāo)售點(diǎn)都可以看作產(chǎn)地，也可以看作銷(xiāo)地，因此把整個(gè)問(wèn)題當(dāng)作有11個(gè)產(chǎn)地和11個(gè)銷(xiāo)地的擴(kuò)大的運(yùn)輸問(wèn)題。（2）對(duì)擴(kuò)大的運(yùn)輸問(wèn)題建立單位運(yùn)價(jià)表。方法是將不可能的運(yùn)輸方案的運(yùn)價(jià)用任意大的正數(shù)（相對(duì)極大值）M代替，其余運(yùn)價(jià)cij不變。（3）所有中間轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷(xiāo)量，即流入量等于流出量。（4）擴(kuò)大的運(yùn)輸問(wèn)題中原來(lái)的產(chǎn)地（加工廠(chǎng)）與銷(xiāo)地（銷(xiāo)售點(diǎn)），因?yàn)橐灿兄虚g轉(zhuǎn)運(yùn)站的作用，所以同樣在原來(lái)的產(chǎn)量與銷(xiāo)量上加t＝20噸。即三個(gè)加工廠(chǎng)的每日產(chǎn)量分別改為27噸、24噸和29噸，銷(xiāo)量均為20噸；四個(gè)銷(xiāo)售點(diǎn)的每日銷(xiāo)量分別改為23噸、26噸、25噸和26噸，產(chǎn)量均為20噸。同時(shí)引進(jìn)xii為輔助變量（虛擬運(yùn)量）。3.4轉(zhuǎn)運(yùn)問(wèn)題【解】表3-10為擴(kuò)大的運(yùn)輸問(wèn)題產(chǎn)銷(xiāo)平衡表與單位運(yùn)價(jià)表。單位運(yùn)價(jià)A1A2A3T1T2T3T4B1B2B3B4產(chǎn)量A1013214331131027A210M35M2192824A33M01M237410529T12310132284620T215M1011452720T34M23102182420T432321201M2620B13172411014220B21194858M102120B332104222420320B410856746213020銷(xiāo)量20202020202020232625262403.4轉(zhuǎn)運(yùn)問(wèn)題例3-5的電子表格模型例3-5（轉(zhuǎn)運(yùn)問(wèn)題）有多組最優(yōu)解。（1）最優(yōu)調(diào)運(yùn)方案1：無(wú)需中間轉(zhuǎn)運(yùn)站，如表3-11和圖3-12所示；（2）最優(yōu)調(diào)運(yùn)方案2：需中間轉(zhuǎn)運(yùn)站T1，如表3-12和圖3-13所示；（3）最優(yōu)調(diào)運(yùn)方案3：需中間轉(zhuǎn)運(yùn)站T3，如表3-13和圖3-14所示。3.5指派問(wèn)題的基本概念在生活中經(jīng)常會(huì)遇到這樣的問(wèn)題：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可以承擔(dān)這些任務(wù)。由于每個(gè)人的專(zhuān)長(zhǎng)不同，各人完成的任務(wù)不同，所需的時(shí)間（或效率）也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)所需的總時(shí)間最短（或總效率最高）。這類(lèi)問(wèn)題稱(chēng)為指派問(wèn)題或分派問(wèn)題。平衡指派問(wèn)題的假設(shè)如下：（1）人的數(shù)量和任務(wù)的數(shù)量相等；（2）每個(gè)人只能完成一項(xiàng)任務(wù)；（3）每項(xiàng)任務(wù)只能由一個(gè)人完成；（4）每個(gè)人和每項(xiàng)任務(wù)的組合都會(huì)有一個(gè)相關(guān)的成本（單位成本）；（5）目標(biāo)是要確定如何指派才能使總成本最小。3.5指派問(wèn)題的基本概念設(shè)xij為是否指派第i個(gè)人去完成第j項(xiàng)任務(wù)，目標(biāo)函數(shù)系數(shù)cij為第i個(gè)人完成第j項(xiàng)任務(wù)所需要的單位成本。平衡指派問(wèn)題的線(xiàn)性規(guī)劃模型如下：3.5指派問(wèn)題的基本概念需要說(shuō)明的是：指派問(wèn)題實(shí)際上是一種特殊的運(yùn)輸問(wèn)題。其中出發(fā)地是“人”，目的地是“任務(wù)”。只不過(guò)，每個(gè)出發(fā)地的供應(yīng)量都為1（因?yàn)槊總€(gè)人都要完成一項(xiàng)任務(wù)），每個(gè)目的地的需求量也都為1（因?yàn)槊宽?xiàng)任務(wù)都要完成）。由于運(yùn)輸問(wèn)題有整數(shù)解性質(zhì)，因此，指派問(wèn)題沒(méi)有必要加上所有決策變量都是0-1變量的約束條件。指派問(wèn)題是一種特殊的線(xiàn)性規(guī)劃問(wèn)題，有一種簡(jiǎn)便的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”功能還是采用單純形法來(lái)求解。3.5指派問(wèn)題的基本概念例3-6

某公司的營(yíng)銷(xiāo)經(jīng)理將要主持召開(kāi)一年一度的由營(yíng)銷(xiāo)區(qū)域經(jīng)理以及營(yíng)銷(xiāo)人員參加的銷(xiāo)售協(xié)商會(huì)議。為了更好地召開(kāi)這次會(huì)議，他安排小張、小王、小李、小劉四個(gè)人，每個(gè)人負(fù)責(zé)完成一項(xiàng)任務(wù)：A、B、C和D。由于每個(gè)人完成每項(xiàng)任務(wù)的時(shí)間和工資不同。問(wèn)公司應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使總成本最小？完成每項(xiàng)任務(wù)的時(shí)間（小時(shí)）每小時(shí)工資（元）任務(wù)A任務(wù)B任務(wù)C任務(wù)D小張3541274014小王4745325112小李3956364313小劉32512546153.5指派問(wèn)題的基本概念【解】

該問(wèn)題是一個(gè)典型的平衡指派問(wèn)題。單位成本為每個(gè)人完成每項(xiàng)任務(wù)的總工資；目標(biāo)是要確定哪個(gè)人去完成哪項(xiàng)任務(wù)，才能使總成本最?。还?yīng)量為1表示每個(gè)人都只能完成一項(xiàng)任務(wù)；需求量為1表示每項(xiàng)任務(wù)也只能由一個(gè)人完成；總?cè)藬?shù)（4人）和總?cè)蝿?wù)數(shù)（4項(xiàng)）相等。3.5指派問(wèn)題的基本概念例3-6的線(xiàn)性規(guī)劃模型設(shè)xij為是否指派人員i去完成任務(wù)j

3.5指派問(wèn)題的基本概念例3-6的電子表格模型3.5指派問(wèn)題的基本概念例3-6的最優(yōu)指派方案網(wǎng)絡(luò)圖小李小劉小張BCAD人指派任務(wù)小王3.6指派問(wèn)題的變形經(jīng)常會(huì)遇到指派問(wèn)題的變形，之所以稱(chēng)它們?yōu)樽冃危且驗(yàn)樗鼈兌疾粷M(mǎn)足平衡指派問(wèn)題所有假設(shè)中的一個(gè)或者多個(gè)。一般考慮下面的一些特征：特征1：某人不能完成某項(xiàng)任務(wù)（相應(yīng)的xij＝0）；特征2：每個(gè)人只能完成一項(xiàng)任務(wù)，但是任務(wù)數(shù)比人數(shù)多(人少事多)；特征3：每項(xiàng)任務(wù)只由一個(gè)人完成，但是人數(shù)比任務(wù)數(shù)多（人多事少）；特征4：某人可以同時(shí)被指派多項(xiàng)任務(wù)（一人可做多事）；特征5：某事需要由多人共同完成（一事需多人做）；特征6：目標(biāo)是與指派有關(guān)的總利潤(rùn)最大而不是總成本最??；特征7：實(shí)際能夠完成的任務(wù)數(shù)小于總?cè)藬?shù)，也小于總?cè)蝿?wù)數(shù)。3.6指派問(wèn)題的變形例3-7指派工廠(chǎng)生產(chǎn)產(chǎn)品問(wèn)題。題目見(jiàn)例3-3，即某公司需要安排三個(gè)工廠(chǎng)來(lái)生產(chǎn)四種產(chǎn)品，相關(guān)的數(shù)據(jù)見(jiàn)表3-7。在例3-3中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生的情況下對(duì)問(wèn)題進(jìn)行分析。新問(wèn)題描述為：已知如表3-7所示的數(shù)據(jù)，問(wèn)如何把每個(gè)工廠(chǎng)指派給至少一種產(chǎn)品（每種產(chǎn)品只能在一個(gè)工廠(chǎng)生產(chǎn)），才能使總成本最小？3.6指派問(wèn)題的變形【解】該問(wèn)題可視為指派工廠(chǎng)生產(chǎn)產(chǎn)品問(wèn)題，工廠(chǎng)可以看作指派問(wèn)題中的人，產(chǎn)品則可以看作需要完成的任務(wù)。

由于有三個(gè)工廠(chǎng)和四種產(chǎn)品，所以就需要有一個(gè)工廠(chǎng)生產(chǎn)兩種新產(chǎn)品，只有工廠(chǎng)1和工廠(chǎng)2有生產(chǎn)兩種產(chǎn)品的能力，這是因?yàn)楣S(chǎng)1和工廠(chǎng)2的生產(chǎn)能力都是75，而工廠(chǎng)3的生產(chǎn)能力是45。這里涉及如何把運(yùn)輸問(wèn)題轉(zhuǎn)化為指派問(wèn)題，關(guān)鍵之處在于數(shù)據(jù)轉(zhuǎn)化。3.6指派問(wèn)題的變形如何把運(yùn)輸問(wèn)題轉(zhuǎn)化為指派問(wèn)題，關(guān)鍵之處在于數(shù)據(jù)轉(zhuǎn)化：（1）單位指派成本:原來(lái)的單位成本轉(zhuǎn)化成整批成本（整批成本＝單位成本×需求量），即單位指派成本為每個(gè)工廠(chǎng)生產(chǎn)每種產(chǎn)品的成本。（2）供應(yīng)量和需求量：三個(gè)工廠(chǎng)生產(chǎn)四種產(chǎn)品，但一種產(chǎn)品只能在一個(gè)工廠(chǎng)生產(chǎn)。根據(jù)生產(chǎn)能力，工廠(chǎng)3只能生產(chǎn)一種產(chǎn)品（供應(yīng)量為1），而工廠(chǎng)1和工廠(chǎng)2可以生產(chǎn)兩種產(chǎn)品（供應(yīng)量為2），而四種產(chǎn)品的需求量都為1。還有“總供應(yīng)量”（2+2+1=5）>“總需求量”（1+1+1+1=4）,即“人多事少”的指派問(wèn)題。3.6指派問(wèn)題的變形例3-7的線(xiàn)性規(guī)劃模型

設(shè)xij為指派工廠(chǎng)i（i=1,2,3）生產(chǎn)產(chǎn)品j（j=1,2,3,4)3.6指派問(wèn)題的變形例3-7的電子表格模型、最優(yōu)指派生產(chǎn)方案網(wǎng)絡(luò)圖2312314工廠(chǎng)

指派生產(chǎn)

產(chǎn)品

本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>

掌握利用Excel求解運(yùn)輸問(wèn)題和指派問(wèn)題的操作方法。2．內(nèi)容和要求

利用Excel求解運(yùn)輸問(wèn)題、轉(zhuǎn)運(yùn)問(wèn)題、指派問(wèn)題等，題目自選。3．操作步驟（1）在Excel中建立運(yùn)輸問(wèn)題（或指派問(wèn)題）的電子表格模型；（2）利用Excel中的“規(guī)劃求解”功能求解運(yùn)輸問(wèn)題或指派問(wèn)題；（3）結(jié)果分析；（4）在Word文檔（或PowerPoint演示文稿）中撰寫(xiě)實(shí)驗(yàn)報(bào)告，包括線(xiàn)性規(guī)劃模型、電子表格模型和結(jié)果分析等。實(shí)用運(yùn)籌學(xué)

－－運(yùn)用Excel建模和求解（第3版）第4章網(wǎng)絡(luò)最優(yōu)化問(wèn)題NetworkOptimizationProblems本章內(nèi)容要點(diǎn)網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念最小費(fèi)用流問(wèn)題最大流問(wèn)題最小費(fèi)用最大流問(wèn)題最短路問(wèn)題最小支撐樹(shù)問(wèn)題貨郎擔(dān)問(wèn)題和中國(guó)郵路問(wèn)題本章主要內(nèi)容框架圖4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念網(wǎng)絡(luò)在各種實(shí)際背景問(wèn)題中以各種各樣的形式存在。交通、電子和通信網(wǎng)絡(luò)遍及人們?nèi)粘Ｉ畹母鱾€(gè)方面，網(wǎng)絡(luò)規(guī)劃也廣泛應(yīng)用于不同領(lǐng)域來(lái)解決各種問(wèn)題，如生產(chǎn)、分派（指派）、項(xiàng)目計(jì)劃、廠(chǎng)址選擇、資源管理和財(cái)務(wù)策劃等。網(wǎng)絡(luò)規(guī)劃為描述系統(tǒng)各組成部分之間的關(guān)系提供了非常有效的直觀和概念上的幫助，廣泛應(yīng)用于科學(xué)、社會(huì)和經(jīng)濟(jì)活動(dòng)的各個(gè)領(lǐng)域。近些年來(lái)，運(yùn)籌學(xué)（管理科學(xué)）中一個(gè)振奮人心的、不同尋常的發(fā)展體現(xiàn)在解決網(wǎng)絡(luò)最優(yōu)化問(wèn)題的方法論及其應(yīng)用方面。4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念許多研究對(duì)象往往可以用一個(gè)圖來(lái)表示，研究的目的歸結(jié)為圖的極值問(wèn)題。運(yùn)籌學(xué)中研究的圖具有下列特征：

(1)用點(diǎn)（圓圈）表示研究對(duì)象，用連線(xiàn)（不帶箭頭的邊或帶箭頭的弧）表示對(duì)象之間的某種關(guān)系。

(2)強(qiáng)調(diào)點(diǎn)與點(diǎn)之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀。

(3)每條邊（或弧）都賦有一個(gè)權(quán)，其圖稱(chēng)為賦權(quán)圖。實(shí)際應(yīng)用中，權(quán)可以表示兩點(diǎn)之間的距離、費(fèi)用、利潤(rùn)、時(shí)間、容量等不同的含義；

(4)建立一個(gè)網(wǎng)絡(luò)模型，求最大值或最小值。4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念V1V3V5V2V4V68736548521對(duì)于該網(wǎng)絡(luò)圖，可以提出許多極值問(wèn)題。4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念（1）將某個(gè)點(diǎn)Vi的物資或信息送到另一個(gè)點(diǎn)Vj，使得運(yùn)送總費(fèi)用最小。這屬于最小費(fèi)用流問(wèn)題。（2）將某個(gè)點(diǎn)Vi的物資或信息送到另一個(gè)點(diǎn)Vj，使得總流量最大。這屬于最大流問(wèn)題。（3）從某個(gè)點(diǎn)Vi出發(fā)，到達(dá)另一個(gè)點(diǎn)Vj，如何安排路線(xiàn)，使得總距離最短或總費(fèi)用最小。這屬于最短路問(wèn)題。4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念（4）點(diǎn)Vi表示自來(lái)水廠(chǎng)及用戶(hù)，Vi與Vj間的邊表示兩點(diǎn)間可以鋪設(shè)管道，權(quán)為Vi與Vj間鋪設(shè)管道的距離或費(fèi)用，如何鋪設(shè)管道，使得將自來(lái)水送到其他5個(gè)用戶(hù)家中的總費(fèi)用最小。這屬于最小支撐樹(shù)問(wèn)題。（5）售貨員從某個(gè)點(diǎn)Vi出發(fā)，經(jīng)過(guò)其他所有點(diǎn)，最后回到原點(diǎn)Vi，如何安排路線(xiàn)，使他行走的總路程最短。這屬于貨郎擔(dān)問(wèn)題（旅行售貨員問(wèn)題）。（6）郵遞員從郵局Vi出發(fā)，經(jīng)過(guò)每一條邊（街道），將郵件送到客戶(hù)手中，最后回到郵局Vi，如何安排路線(xiàn)，使他行走的總路程最短。這屬于中國(guó)郵路問(wèn)題。4.1網(wǎng)絡(luò)最優(yōu)化問(wèn)題的基本概念網(wǎng)絡(luò)最優(yōu)化問(wèn)題的類(lèi)型主要包括：（1）最小費(fèi)用流問(wèn)題；（2）最大流問(wèn)題；（3）最短路問(wèn)題；（4）最小支撐樹(shù)問(wèn)題；（5）貨郎擔(dān)問(wèn)題；（6）中國(guó)郵路問(wèn)題。4.2最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題在網(wǎng)絡(luò)最優(yōu)化問(wèn)題中扮演著重要的角色，原因是它的適用性很廣，并且求解方法簡(jiǎn)單。通常最小費(fèi)用流問(wèn)題用于最優(yōu)化貨物從供應(yīng)點(diǎn)到需求點(diǎn)的網(wǎng)絡(luò)。目標(biāo)是在通過(guò)網(wǎng)絡(luò)配送貨物時(shí)，以最小的成本滿(mǎn)足需求。一種典型的應(yīng)用就是使配送網(wǎng)絡(luò)的運(yùn)營(yíng)最優(yōu)。4.2最小費(fèi)用流問(wèn)題例4-1

某公司有兩個(gè)工廠(chǎng)生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運(yùn)送到兩個(gè)倉(cāng)庫(kù)中。其配送網(wǎng)絡(luò)圖如圖4-2所示。目標(biāo)是確定一個(gè)運(yùn)輸方案（即在每條線(xiàn)路上運(yùn)送多少單位產(chǎn)品），使得通過(guò)配送網(wǎng)絡(luò)的總運(yùn)輸成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（無(wú)限制，700）（無(wú)限制，900）4.2最小費(fèi)用流問(wèn)題最小費(fèi)用流問(wèn)題的三個(gè)基本概念如下：（1）最小費(fèi)用流問(wèn)題的構(gòu)成（網(wǎng)絡(luò)表示）①節(jié)點(diǎn)：包括供應(yīng)點(diǎn)、需求點(diǎn)和轉(zhuǎn)運(yùn)點(diǎn)。②?。嚎尚械倪\(yùn)輸線(xiàn)路（節(jié)點(diǎn)i->節(jié)點(diǎn)j），經(jīng)常有最大運(yùn)輸能力（容量）的限制。4.2最小費(fèi)用流問(wèn)題（2）最小費(fèi)用流問(wèn)題的假設(shè)

①至少有一個(gè)供應(yīng)點(diǎn)。②至少有一個(gè)需求點(diǎn)。③可以有轉(zhuǎn)運(yùn)點(diǎn)。④通過(guò)弧的流，只允許沿著箭頭方向流動(dòng)，通過(guò)弧的最大流量取決于該弧的容量。⑤網(wǎng)絡(luò)中有足夠的弧提供足夠的容量，使得所有在供應(yīng)點(diǎn)中產(chǎn)生的流都能夠到達(dá)需求點(diǎn)（有可行解）。⑥在流的單位成本已知的前提下，通過(guò)每條弧的流的成本與流量成正比（目標(biāo)函數(shù)是線(xiàn)性的）。

⑦最小費(fèi)用流問(wèn)題的目標(biāo)是在滿(mǎn)足給定需求的條件下，使得通過(guò)配送網(wǎng)絡(luò)的總成本最?。ɑ蚩偫麧?rùn)最大）。4.2最小費(fèi)用流問(wèn)題（3）最小費(fèi)用流問(wèn)題的解的特征①具有可行解的特征：在以上假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點(diǎn)所提供的供應(yīng)