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

線性規(guī)劃LinearProgramming1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1.1生產(chǎn)計(jì)劃問題。某工廠要生產(chǎn)兩種新產(chǎn)品：門和窗。經(jīng)測算，每生產(chǎn)一扇門需要在車間1加工1小時(shí)、在車間3加工3小時(shí)；每生產(chǎn)一扇窗需要在車間2和車間3各加工2小時(shí)。而車間1、車間2、車間3每周可用于生產(chǎn)這兩種新產(chǎn)品的時(shí)間分別是4小時(shí)、12小時(shí)、18小時(shí)。已知每扇門的利潤為300元，每扇窗的利潤為500元。而且根據(jù)經(jīng)市場調(diào)查得到的這兩種新產(chǎn)品的市場需求狀況可以確定，按當(dāng)前的定價(jià)可確保所有新產(chǎn)品均能銷售出去。問該工廠應(yīng)如何安排這兩種新產(chǎn)品的生產(chǎn)計(jì)劃，才能使總利潤最大？1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型在該問題中，目標(biāo)是兩種新產(chǎn)品的總利潤最大化，所要決策的（變量）是兩種新產(chǎn)品（門和窗）的每周產(chǎn)量，而新產(chǎn)品的每周產(chǎn)量要受到三個(gè)車間每周可用于生產(chǎn)新產(chǎn)品的時(shí)間的限制。因此，該問題可以用“目標(biāo)函數(shù)”、“決策變量”和“約束條件”三個(gè)因素加以描述。實(shí)際上，所有的線性規(guī)劃問題都包含這三個(gè)因素：（1）決策變量是問題中有待確定的未知因素。例如決定企業(yè)經(jīng)營目標(biāo)的各產(chǎn)品的產(chǎn)量等。（2）目標(biāo)函數(shù)是指對問題所追求目標(biāo)的數(shù)學(xué)描述。例如總利潤最大、總成本最小等。（3）約束條件是指實(shí)現(xiàn)問題目標(biāo)的限制因素。如原材料供應(yīng)量、生產(chǎn)能力、市場需求等，它們限制了目標(biāo)值所能實(shí)現(xiàn)的程度。1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型解：例1.1可用表1-1表示。每個(gè)產(chǎn)品所需時(shí)間每周可用工時(shí)（小時(shí)）門窗車間1104車間20212車間33218單位利潤（元）3005001.1線性規(guī)劃的基本概念和數(shù)學(xué)模型（1）決策變量本問題的決策變量是兩種新產(chǎn)品（門和窗）的每周產(chǎn)量。可設(shè)：x1為門的每周產(chǎn)量（扇）；

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

z=300x1＋500x2

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

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

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

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

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

本章討論的問題均為線性規(guī)劃問題。所謂“線性”規(guī)劃，是指如果目標(biāo)函數(shù)是關(guān)于決策變量的線性函數(shù)，而且約束條件也都是關(guān)于決策變量的線性等式或線性不等式，則相應(yīng)的規(guī)劃問題就稱為線性規(guī)劃問題。1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1.2

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

1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型解：（1）決策變量本問題要決策（確定）的是混合飼料中兩種原料的數(shù)量（原料采購量）?？稍O(shè)：x1為玉米采購量；x2

為紅薯采購量。（2）目標(biāo)函數(shù)本問題的目標(biāo)是混合飼料的總成本最低，即：1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型（3）約束條件本問題共有四個(gè)約束條件：①滿足營養(yǎng)要求碳水化合物的營養(yǎng)要求蛋白質(zhì)的營養(yǎng)要求維他命的營養(yǎng)要求②非負(fù)約束1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1.2的線性規(guī)劃模型為：這是一個(gè)典型的總成本最小化問題。其中，“min”是英文單詞“minimize”的縮寫，含義為“最小化”。因此，上述模型的含義是：在給定的條件限制（約束）下，求目標(biāo)函數(shù)z

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

需求量－120130

1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1.3物流網(wǎng)絡(luò)配送問題--配送網(wǎng)絡(luò)圖9.22.390902.38.23.43.53.06060607.513TBA28070120130配送中心100產(chǎn)量工廠單位運(yùn)輸成本倉庫需求量1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1.3物流網(wǎng)絡(luò)配送問題的線性規(guī)劃模型為：1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型線性規(guī)劃的一般形式為:對于一組決策變量x1，x2，，xn，取1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型在線性規(guī)劃模型中，也直接稱z為目標(biāo)函數(shù)；稱xj(j=1,2,

,n)為決策變量；稱cj(j=1,2,

,n)

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

,m)為函數(shù)約束右端常數(shù)或簡稱右端值，也稱資源常數(shù)；稱aij(i=1,2,

,m;j=1,2,

,n)為約束系數(shù)、技術(shù)系數(shù)或工藝系數(shù)。這里，cj，bi，aij均為常數(shù)（稱為模型參數(shù)）。線性規(guī)劃的數(shù)學(xué)模型可以表示為下列簡潔的形式：1.2線性規(guī)劃的圖解法對于只有兩個(gè)變量的線性規(guī)劃問題，可以在二維直角坐標(biāo)平面上作圖求解。可行域與最優(yōu)解線性規(guī)劃的圖解法1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題在Excel電子表格中建立線性規(guī)劃模型使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題使用名稱建好電子表格模型的幾個(gè)原則1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題在用電子表格建立數(shù)學(xué)模型（這里是一個(gè)線性規(guī)劃模型）的過程中，有三個(gè)問題需要得到回答：（1）要做出的決策是什么？（決策變量）（2）在做出這些決策時(shí)，有哪些約束條件？（約束條件）（3）這些決策的目標(biāo)是什么？（目標(biāo)函數(shù)）1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題在Excel2010中加載“規(guī)劃求解”工具第一步：單擊“文件”選項(xiàng)卡，在彈出的列表中單擊“選項(xiàng)”命令，這時(shí)將出現(xiàn)“Excel選項(xiàng)”對話框。第二步：在“Excel選項(xiàng)”對話框中，單擊“加載項(xiàng)”，在右側(cè)“管理”下拉列表中選擇“Exce1加載項(xiàng)”，然后單擊“轉(zhuǎn)到”按鈕，打開“加載宏”對話框。第三步：在“加載宏”對話框中，勾選“規(guī)劃求解加載項(xiàng)”，單擊“確定”按鈕。這樣，Excel工作窗口的“數(shù)據(jù)”選項(xiàng)卡的“分析”組中將出現(xiàn)“規(guī)劃求解”命令。1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題P15，圖1-9規(guī)劃求解后例1.1的電子表格模型（沒有給單元格命名）1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題—使用名稱在使用Excel的“規(guī)劃求解”命令求解規(guī)劃問題，使用名稱能使規(guī)劃問題的電子表格模型更容易理解。主要表現(xiàn)在以下兩個(gè)方面：（1）在“公式”中使用名稱，使人們更容易理解公式的含義；（2）在“規(guī)劃求解參數(shù)”對話框中使用名稱，使人們更容易理解規(guī)劃模型的含義。因此，一般會(huì)為與公式和規(guī)劃模型有關(guān)的四類單元格命名。例如，在例1.1的電子表格模型中，分別為下列單元格命名：（1）數(shù)據(jù)單元格：單位利潤（C4:D4）、可用工時(shí)（G7:G9）；（2）可變單元格：每周產(chǎn)量（C12:D12）；（3）輸出單元格：實(shí)際使用（E7:E9）；（4）目標(biāo)單元格：總利潤（G12）。1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題P21，圖1-19規(guī)劃求解后例1.1的電子表格模型（使用名稱）1.3使用Excel2010“規(guī)劃求解”工具求解線性規(guī)劃問題電子表格建模是一門藝術(shù)，建立一個(gè)好的電子表格模型應(yīng)遵循以下幾個(gè)原則：（1）首先輸入數(shù)據(jù)；（2）清楚地標(biāo)識(shí)數(shù)據(jù)；（3）每個(gè)數(shù)據(jù)輸入到唯一的單元格中；（4）將數(shù)據(jù)與公式分離；（5）保持簡單化（使用SUMPRODUCT函數(shù)、SUM函數(shù)、中間結(jié)果等）；（6）使用名稱；（7）使用相對引用和絕對引用，以便簡化公式的復(fù)制；（8）使用邊框、背景色（填充顏色）來區(qū)分單元格類型（四類單元格）；（9）在電子表格中顯示整個(gè)模型（包括符號和數(shù)據(jù)）。Excel提供許多有效的工具來幫助用戶進(jìn)行規(guī)劃模型調(diào)試，其中一個(gè)工具是將電子表格的輸出單元格在數(shù)值（運(yùn)算結(jié)果）和公式之間進(jìn)行切換（“公式”選項(xiàng)卡－>“公式審核”組－>“顯示公式”）。1.3使用Excel2010

“規(guī)劃求解”工具求解線性規(guī)劃問題P22，圖1-21例1.2的電子表格模型1.3使用Excel2010

“規(guī)劃求解”工具求解線性規(guī)劃問題P23，圖1-22例1.3的電子表格模型1.4線性規(guī)劃問題求解的幾種可能結(jié)果唯一解無窮多解無解可行域無界（目標(biāo)值不收斂）1.4線性規(guī)劃問題求解的幾種可能結(jié)果唯一解線性規(guī)劃問題具有唯一解是指該線性規(guī)劃問題有且僅有一個(gè)既在可行域內(nèi)、又使目標(biāo)值達(dá)到最優(yōu)的解。例1.1就是一個(gè)具有唯一解的線性規(guī)劃問題。1.4線性規(guī)劃問題求解的幾種可能結(jié)果無窮多解線性規(guī)劃問題具有無窮多解是指該線性規(guī)劃問題有無窮多個(gè)既在可行域內(nèi)、又能使目標(biāo)值達(dá)到最優(yōu)的解。在例1.1中，假設(shè)門的單位利潤從300元增加至750元，這時(shí)該問題的解將發(fā)生變化。1.4線性規(guī)劃問題求解的幾種可能結(jié)果無解當(dāng)線性規(guī)劃問題中的約束條件不能同時(shí)滿足時(shí)，無可行域的情況將會(huì)出現(xiàn)，這時(shí)不存在可行解，即該線性規(guī)劃問題無解。在例1.1中，若要求門的每周產(chǎn)量不得少于6，則需再加上一個(gè)約束條件：x161.4線性規(guī)劃問題求解的幾種可能結(jié)果可行域無界（目標(biāo)值不收斂）線性規(guī)劃問題的可行域無界，是指最大化問題中的目標(biāo)函數(shù)值可以無限增大，或最小化問題中的目標(biāo)函數(shù)值可以無限減少。在例1.1中，如果沒有車間可用工時(shí)的約束，但要求門與窗的總產(chǎn)量不得少于4。1.5建立規(guī)劃模型的流程建立規(guī)劃模型的工作既是一門科學(xué)，又是一門藝術(shù)。NYNY實(shí)際問題向規(guī)劃問題的提煉確定決策變量確定目標(biāo)函數(shù)確定約束條件有無法定量表述的成分輔助決策實(shí)際應(yīng)用模型分析和檢驗(yàn)，提交定量報(bào)告解讀軟件運(yùn)行結(jié)果開展人機(jī)對話，把數(shù)學(xué)模型軟件化上機(jī)調(diào)試通過報(bào)告本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>

在Excel2010軟件中加載“規(guī)劃求解”工具，使用Excel2010軟件求解線性規(guī)劃問題。2．內(nèi)容和要求

（1）在Excel2010軟件中，加載“規(guī)劃求解”工具；

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

使用Excel2010軟件求解習(xí)題1.1、案例1.1（或其他例子、習(xí)題、案例等）。

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

（2）使用Excel2010軟件中的“規(guī)劃求解”工具求解線性規(guī)劃問題。

（3）結(jié)果分析：如每月生產(chǎn)四種產(chǎn)品各多少噸？總利潤是多少？哪些原料有剩余？并對結(jié)果提出自己的看法。

（4）在Excel文件或Word文檔中撰寫實(shí)驗(yàn)報(bào)告，包括線性規(guī)劃模型、電子表格模型和結(jié)果分析等。

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

最優(yōu)解（2，6）保持不變

2.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的靈敏度分析假如，原先門的單位利潤（300元）估計(jì)低了，現(xiàn)在升為450元；同時(shí)，以前窗的單位利潤（500元）估計(jì)高了，現(xiàn)在降為400元。這樣的變化，是否會(huì)導(dǎo)致最優(yōu)解發(fā)生變化呢？方法1：使用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行Excel“規(guī)劃求解”命令）方法2：運(yùn)用“敏感性報(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)解并沒有發(fā)生變化，總利潤由于門和窗的單位利潤的改變相應(yīng)地改變了(450－300)×2＋(400－500)×6＝－3002.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的靈敏度分析方法2：運(yùn)用“敏感性報(bào)告”進(jìn)行分析目標(biāo)函數(shù)系數(shù)同時(shí)變化的百分之百法則:如果目標(biāo)函數(shù)系數(shù)同時(shí)變化，計(jì)算出每一系數(shù)變化量占該系數(shù)允許變化量（允許的增量或允許的減量）的百分比，然后將各個(gè)系數(shù)變化的百分比相加。如果所得的變化的百分比總和不超過100%，則最優(yōu)解不會(huì)變化；如果超過了100%，則不能確定最優(yōu)解是否改變（可能改變，也可能不變），可通過重新運(yùn)行“規(guī)劃求解”命令來判斷。2.3多個(gè)目標(biāo)函數(shù)系數(shù)同時(shí)變化的靈敏度分析但是變化的百分比總和超過100%，并不表示最優(yōu)解一定會(huì)改變。例如，門和窗的單位利潤都減半變化的百分比總和超過了100%，但從右圖看最優(yōu)解還是（2，6），沒有發(fā)生改變。這是由于這兩個(gè)單位利潤同比例變化，等利潤直線的斜率不變，因此最優(yōu)解就保持不變。2.4單個(gè)約束右端值變化的靈敏度分析單個(gè)約束右端值變化對目標(biāo)值的影響如果車間2的可用工時(shí)增加1小時(shí)，總利潤是否會(huì)發(fā)生變化？如何改變?最優(yōu)解是否會(huì)發(fā)生變化?方法1：使用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行“規(guī)劃求解”命令）方法2：從“敏感性報(bào)告”中獲得關(guān)鍵信息（影子價(jià)格，shadowprice）2.4單個(gè)約束右端值變化的靈敏度分析方法1：使用電子表格進(jìn)行互動(dòng)分析，重新運(yùn)行“規(guī)劃求解”命令總利潤為3750元，增加了3750－3600＝150（元）。由于總利潤增加了，而目標(biāo)函數(shù)系數(shù)不變，所以最優(yōu)解一定會(huì)發(fā)生改變，從圖中可以看出，最優(yōu)解由原來的（2，6）變?yōu)椋?.667，6.5）

2.4單個(gè)約束右端值變化的靈敏度分析方法2：從“敏感性報(bào)告”中獲得關(guān)鍵信息在給定線性規(guī)劃模型的最優(yōu)解和目標(biāo)函數(shù)值（最優(yōu)值）的條件下，影子價(jià)格（shadowprice）就是約束右端值每增加（或減少）1個(gè)單位，目標(biāo)函數(shù)值（最優(yōu)值）增加（或減少）的數(shù)量第二個(gè)約束條件（車間2的工時(shí)約束）的影子價(jià)格是150，說明在允許的范圍[6，18]（即[12-6，12+6]）內(nèi)，再增加（或減少）1小時(shí)的可用工時(shí)，總利潤將增加（或減少）150（元）。2.4單個(gè)約束右端值變化的靈敏度分析圖解法（直觀）可以看到，

在這個(gè)范圍內(nèi)，車間2的約束右端值每增加（或減少）1個(gè)單位，交點(diǎn)的移動(dòng)就使利潤增長（或減少）1個(gè)影子價(jià)格的數(shù)量（150元）2.5多個(gè)約束右端值同時(shí)變化的靈敏度分析多個(gè)約束右端值同時(shí)變化對目標(biāo)值的影響將1小時(shí)的工時(shí)從車間3移到車間2，對總利潤所產(chǎn)生的影響方法1：使用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行“規(guī)劃求解”命令）方法2：運(yùn)用“敏感性報(bào)告”進(jìn)行分析（約束右端值同時(shí)變化的百分之百法則）2.5多個(gè)約束右端值同時(shí)變化的靈敏度分析方法1：使用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行“規(guī)劃求解”命令）總利潤增加了3650-3600=50（元），影子價(jià)格有效。2.5多個(gè)約束右端值同時(shí)變化的靈敏度分析方法2：運(yùn)用“敏感性報(bào)告”進(jìn)行分析約束右端值同時(shí)變化的百分之百法則：如果約束右端值同時(shí)變化，計(jì)算每一右端值變化量占該約束右端值允許變化量（允許的增量或允許的減量）的百分比，然后將各個(gè)右端值變化的百分比相加。如果所得的變化的百分比總和不超過100%，那么影子價(jià)格依然有效；如果超過了100％，那就無法確定影子價(jià)格是否依然有效（可能有效，也可能無效），可通過重新運(yùn)行“規(guī)劃求解”命令來判斷。2.5多個(gè)約束右端值同時(shí)變化的靈敏度分析在影子價(jià)格的有效范圍內(nèi)，總利潤的變化量可以直接通過影子價(jià)格來計(jì)算。比如將車間3的3個(gè)工時(shí)轉(zhuǎn)移給車間2，由于所以，總利潤的變化量為2.6約束條件系數(shù)變化的靈敏度分析車間2更新生產(chǎn)工藝，生產(chǎn)一扇窗由原來的2小時(shí)下降為1.5小時(shí),此時(shí)最優(yōu)解是否會(huì)發(fā)生改變？總利潤是否會(huì)發(fā)生變化？使用電子表格進(jìn)行互動(dòng)分析(重新運(yùn)行“規(guī)劃求解”命令)重新運(yùn)行“規(guī)劃求解”命令后，最優(yōu)解發(fā)生了改變，變?yōu)椋?/3，8），總利潤也由原來的3600元增加到4200元?？梢姡囬g2更新生產(chǎn)工藝后，為工廠增加了利潤。2.7增加一個(gè)新變量例2.1工廠考慮增加一種新產(chǎn)品：防盜門，假設(shè)其單位利潤為400元。生產(chǎn)一扇防盜門會(huì)占用車間1、車間2、車間3各2、1、1小時(shí)，總利潤是否會(huì)發(fā)生變化？使用電子表格進(jìn)行互動(dòng)分析（重新運(yùn)行“規(guī)劃求解”命令)最優(yōu)解為(2,5.5,1）,總利潤為3750元?？梢娦庐a(chǎn)品為工廠增加了利潤。2.8增加一個(gè)約束條件增加電力供應(yīng)限制(例2.2假定生產(chǎn)一扇門和窗需要消耗電力分別為20kw和10kw，工廠可供電量最多為90kw),最優(yōu)解是否會(huì)發(fā)生變化?使用電子表格進(jìn)行互動(dòng)分析(重新運(yùn)行“規(guī)劃求解”命令)可見電力約束的確限制了門的每周產(chǎn)量（而窗的每周產(chǎn)量不變），最優(yōu)解變成(1.5,6),總利潤也相應(yīng)地下降為3450元。2.9靈敏度分析的應(yīng)用舉例例2.3力浦公司是一家生產(chǎn)外墻涂料的建材公司，目前生產(chǎn)甲、乙兩種規(guī)格的產(chǎn)品，這兩種產(chǎn)品在市場上的單位利潤分別是4萬元和5萬元。甲、乙兩種產(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ǎn)品供不應(yīng)求，但是在每個(gè)生產(chǎn)周期（假設(shè)一年）內(nèi)，公司的A、B、C三種原材料資源的儲(chǔ)備量分別是45單位、80單位和90單位，年終剩余的資源必須無償調(diào)回，而且近期也沒有籌集到額外資源的渠道。面對這種局面，力浦公司應(yīng)如何安排生產(chǎn)計(jì)劃，以獲得最大的市場利潤？2.9靈敏度分析的應(yīng)用舉例該公司在運(yùn)營了一年后，管理層為第二年的運(yùn)營進(jìn)行了以下的預(yù)想（假設(shè)以下問題均單獨(dú)出現(xiàn)）：問題1：由于建材市場受到其他競爭者的影響，公司市場營銷部門預(yù)測當(dāng)年的產(chǎn)品甲的價(jià)格會(huì)產(chǎn)生變化：產(chǎn)品甲的單位利潤將會(huì)在3.8萬元～5.2萬元之間波動(dòng)。公司該如何應(yīng)對這種情況，提前對生產(chǎn)格局做好調(diào)整預(yù)案？問題2：由于供應(yīng)鏈上游的化工原料價(jià)格不斷上漲，給力浦公司帶來資源購置上的壓力。公司采購部門預(yù)測現(xiàn)有45單位限額的材料A將會(huì)出現(xiàn)3單位的資源缺口，但是也不排除通過其他渠道籌措來1單位材料A的可能。對于材料A的資源上限的增加或減少，力浦公司應(yīng)如何進(jìn)行新的規(guī)劃？問題3：經(jīng)過規(guī)劃分析已經(jīng)知道，材料B在最優(yōu)生產(chǎn)格局中出現(xiàn)了12.5單位的剩余，那么應(yīng)如何重新制訂限額，做好節(jié)約工作？問題4：最壞的可能是公司停止生產(chǎn)，把各種原材料清倉變賣。但是應(yīng)如何在原材料市場上對A、B和C三種資源進(jìn)行報(bào)價(jià)，以使得公司在直接出售原材料的清算業(yè)務(wù)中損失最?。繂栴}5：如果企業(yè)打算通過增加原材料投入擴(kuò)大生產(chǎn)規(guī)模，面對資源市場上的A、B和C三種材料的市價(jià)，力浦公司應(yīng)如何做出經(jīng)濟(jì)合理的決策？2.9靈敏度分析的應(yīng)用舉例例2.3力浦公司的線性規(guī)劃模型和電子表格模型。2.9靈敏度分析的應(yīng)用舉例力浦公司的靈敏度分析（問題1、問題2和問題3）力浦公司的“敏感性報(bào)告”2.9靈敏度分析的應(yīng)用舉例問題1：產(chǎn)品甲的單位利潤變化對最優(yōu)解和最優(yōu)值的影響產(chǎn)品甲的單位利潤將會(huì)在3.8～5.2萬元之間波動(dòng)。根據(jù)“敏感性報(bào)告”，分段分析。針對產(chǎn)品甲的單位利潤將會(huì)在3.8～5.2萬元之間波動(dòng)的預(yù)測，力浦公司應(yīng)制訂兩套預(yù)案：當(dāng)單位利潤在3.8～5.0萬元之間時(shí)，甲、乙兩種產(chǎn)品的產(chǎn)量均為22.5單位；而單位利潤在5.0～5.2萬元之間時(shí)，甲、乙兩種產(chǎn)品分別生產(chǎn)35單位和10單位?？梢钥闯?，當(dāng)產(chǎn)品甲的單位利潤逐漸增加時(shí)，力浦公司一定會(huì)理性地將資源配置向產(chǎn)品甲傾斜。2.9靈敏度分析的應(yīng)用舉例問題2：當(dāng)資源A的限額（儲(chǔ)備量）在42～46單位變化時(shí)對規(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)值（總利潤）為202.5－3×3.5＝192（萬元）。重新規(guī)劃求解后，可知新的最優(yōu)解是（18，24）。同理，如果資源A的限額（儲(chǔ)備量）從45增加到46，則最優(yōu)值（總利潤）為202.5＋1×3.5＝206（萬元），重新規(guī)劃求解后，可知新的最優(yōu)解是（24，22）。2.9靈敏度分析的應(yīng)用舉例問題3：對資源B的限額（儲(chǔ)備量）的考察資源B是力浦公司尋求市場收益活動(dòng)中的一個(gè)有趣的“約束”。實(shí)質(zhì)上，該“約束”在當(dāng)前的最優(yōu)規(guī)劃的生產(chǎn)格局下，并沒有真正起到“約束”的作用。正如實(shí)際的規(guī)劃結(jié)果所表明的，資源B在取得最優(yōu)值后，尚有12.5單位的剩余。從“敏感性報(bào)告”中可知，資源B的限額（儲(chǔ)備量）允許的變化范圍是：資源B的最小合理儲(chǔ)備量是67.5單位。2.9靈敏度分析的應(yīng)用舉例問題4和問題5：影子價(jià)格與線性規(guī)劃的對偶問題了解即可2.9靈敏度分析的應(yīng)用舉例問題4和問題5：影子價(jià)格與線性規(guī)劃的對偶問題方法1：對偶問題的電子表格模型了解即可方法2：“敏感性報(bào)告”中的影子價(jià)格資源A的影子價(jià)格是3.5萬元，資源B的影子價(jià)格是0萬元，資源C的影子價(jià)格是0.5萬元。本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康恼莆帐褂肊xcel軟件進(jìn)行靈敏度分析的操作方法。2．內(nèi)容和要求使用Excel軟件求解習(xí)題2.3、案例2.1（或其他例子、習(xí)題、案例等）。3．操作步驟（1）在Excel中建立電子表格模型；（2）使用Excel軟件中的“規(guī)劃求解”命令求解線性規(guī)劃問題并生成“敏感性報(bào)告”；（3）結(jié)果分析：哪些問題可以直接利用“敏感性報(bào)告”中的信息求解，哪些問題需要重新運(yùn)行“規(guī)劃求解”命令，并對結(jié)果提出自己的看法；（4）在Excel文件或Word文檔中撰寫實(shí)驗(yàn)報(bào)告，包括線性規(guī)劃模型、電子表格模型、敏感性報(bào)告和結(jié)果分析等。

第3章線性規(guī)劃的建模與應(yīng)用LinearProgrammingFormulationandApplications3.1資源分配問題資源分配問題是將有限的資源分配到各種活動(dòng)（決策）中去的線性規(guī)劃問題。這一類問題的共性是：在線性規(guī)劃模型中，每一個(gè)函數(shù)約束均為資源約束，并且每一種資源都可以表現(xiàn)為如下形式：使用的資源數(shù)量

可用的資源數(shù)量對于資源分配問題，有三種數(shù)據(jù)必須收集：（1）每種資源的可供量（可用的資源數(shù)量）；（2）每一種活動(dòng)所需要的各種資源的數(shù)量，對于每一種資源與活動(dòng)的組合,必須首先估計(jì)出單位活動(dòng)所消耗的資源量；（3）每一種活動(dòng)對總的績效測度（如總利潤）的單位貢獻(xiàn)（如單位利潤）。3.1資源分配問題例3.1

某公司是商務(wù)房地產(chǎn)開發(fā)項(xiàng)目的主要投資商。目前，該公司有機(jī)會(huì)在三個(gè)建設(shè)項(xiàng)目中投資： 項(xiàng)目1：建造高層辦公樓； 項(xiàng)目2：建造賓館； 項(xiàng)目3：建造購物中心。三個(gè)項(xiàng)目都要求投資者在四個(gè)不同的時(shí)期投資：在當(dāng)前預(yù)付定金，以及一年、二年、三年后分別追加投資。表3-1顯示了四個(gè)時(shí)期三個(gè)項(xiàng)目所需資金。投資者可以按一定的比例進(jìn)行投資和獲得相應(yīng)比例的收益。辦公樓項(xiàng)目賓館項(xiàng)目購物中心項(xiàng)目現(xiàn)在408090一年后608050兩年后908020三年后108070收益500780600公司目前有2500萬元資金可供投資，預(yù)計(jì)一年后，又可獲得2000萬元，兩年后獲得另外的2000萬元，三年后還有1500萬元可供投資。那么，該公司要在三個(gè)項(xiàng)目中投資多少比例，才能使其投資組合所獲得的總收益最大？3.1資源分配問題解：本問題是一個(gè)資源分配問題。（1）決策變量設(shè)：x1，x2，x3分別為公司在辦公樓項(xiàng)目、賓館項(xiàng)目、購物中心項(xiàng)目中的投資比例（2）目標(biāo)函數(shù)本問題的目標(biāo)是公司所獲得的總收益最大3.1資源分配問題（3）約束條件本問題的約束條件是公司在各個(gè)時(shí)期可獲得的資金限制（資源約束）。但需要注意的是：前一時(shí)期尚未使用的資金，可以在下一時(shí)期使用（為了簡化問題，不考慮資金可獲得的利息）。因此，每一時(shí)期的資金限制就表現(xiàn)為累計(jì)資金。表3-2顯示了四個(gè)時(shí)期三個(gè)項(xiàng)目所需累計(jì)資金和公司累計(jì)可用資金。辦公樓項(xiàng)目賓館項(xiàng)目購物中心項(xiàng)目可用資金現(xiàn)在40809025一年后10016014045兩年后19024016065三年后20032023080收益500780600

3.1資源分配問題例3.1的線性規(guī)劃模型3.1資源分配問題例3.1的電子表格模型3.2成本收益平衡問題成本收益平衡問題與資源分配問題的形式完全不同，這種差異主要是由兩種問題的管理目標(biāo)不同造成的。在資源分配問題中，各種資源是受限制的因素（包括財(cái)務(wù)資源），問題的目標(biāo)是最有效地利用各種資源，使獲利最大。而對于成本收益平衡問題，管理層采取更為主動(dòng)的姿態(tài)，他們指明哪些收益必須實(shí)現(xiàn)（不管如何使用資源），并且要以最低的成本實(shí)現(xiàn)所指明的收益。這樣，通過指明每種收益的最低可接受水平，以及實(shí)現(xiàn)這些收益的最小成本，管理層期望獲得成本和收益之間的適度平衡。因此，成本收益平衡問題代表了一類線性規(guī)劃問題。在這類問題中，通過選擇各種活動(dòng)水平的組合，從而以最小的成本來實(shí)現(xiàn)最低的可接受的各種收益水平。3.2成本收益平衡問題成本收益平衡問題的共性是：所有的函數(shù)約束均為收益約束，并具有如下形式：

完成的水平

最低的可接受水平如果將收益的含義擴(kuò)大，可稱以“

”表示的函數(shù)約束為“收益約束”。在多數(shù)情況下，最低的可接受水平是作為一項(xiàng)政策由管理層制訂的，但有時(shí)這一數(shù)據(jù)也可能是由其他條件決定。成本收益平衡問題需要收集的三種數(shù)據(jù)：（1）每種收益最低的可接受水平（管理決策）；（2）每種活動(dòng)對每種收益的貢獻(xiàn)（單位活動(dòng)的貢獻(xiàn)）；（3）每種活動(dòng)的單位成本。3.2成本收益平衡問題排班問題是成本收益平衡問題研究的最重要的應(yīng)用領(lǐng)域之一。在這一領(lǐng)域中，管理層意識(shí)到在向顧客提供令人滿意的服務(wù)水平的同時(shí)必須進(jìn)行成本控制，因此，必須尋找成本和收益之間的平衡。于是，研究如何規(guī)劃每個(gè)輪班人員的排班才能以最小的成本提供令人滿意的服務(wù)。3.2成本收益平衡問題例3.2某航空公司正準(zhǔn)備增加其中心機(jī)場的往來航班，因此需要雇用更多的服務(wù)人員。不同時(shí)段有最少需求人數(shù)，有5種排班方式（連續(xù)工作8個(gè)小時(shí)）。時(shí)段排班1排班2排班3排班4排班5最少需求人數(shù)06:00～08:00√4808:00～10:00√√7910:00～12:00√√6512:00～14:00√√√8714:00～16:00√√6416:00～18:00√√7318:00～20:00√√8220:00～22:00√4322:00～24:00√√5200:00～6:00√15每人每天工資（元）1701601751801953.2成本收益平衡問題解：本問題是排班問題，是典型的成本收益平衡問題。（1）決策變量確定不同排班的上班人數(shù)。設(shè)：xi為排班i的上班人數(shù)(i＝1,2,

,5)（2）目標(biāo)函數(shù)每天的總成本（工資）最少。（3）約束條件①每個(gè)時(shí)段的在崗人數(shù)必須不少于最低的可接受水平（最少需求人數(shù)）②非負(fù)3.2成本收益平衡問題例3.2的線性規(guī)劃模型3.2成本收益平衡問題例3.2的電子表格模型3.3網(wǎng)絡(luò)配送問題通過配送網(wǎng)絡(luò)，以最小的成本完成貨物的配送，所以稱之為網(wǎng)絡(luò)配送問題。網(wǎng)絡(luò)配送問題將在第4章和第5章中重點(diǎn)介紹。與確定資源和收益一樣，在網(wǎng)絡(luò)配送問題中，必須確定需求并相應(yīng)地確定需求的約束條件。確定需求約束的形式如下：提供的數(shù)量＝需求的數(shù)量3.3網(wǎng)絡(luò)配送問題例3.3

某公司網(wǎng)絡(luò)配送問題。某公司在兩個(gè)工廠生產(chǎn)某種產(chǎn)品?，F(xiàn)在收到三個(gè)顧客下個(gè)月要購買這種產(chǎn)品的訂單。這些產(chǎn)品將被單獨(dú)運(yùn)送，表3-5顯示了工廠運(yùn)送一個(gè)產(chǎn)品給顧客的成本。該表還給出了每個(gè)顧客的訂貨量和每個(gè)工廠的產(chǎn)量。現(xiàn)在公司的物流經(jīng)理要確定每個(gè)工廠需運(yùn)送多少個(gè)產(chǎn)品給每個(gè)顧客，才能使公司的總運(yùn)輸成本最??？

單位運(yùn)輸成本（元/個(gè)）產(chǎn)量（個(gè)）顧客1顧客2顧客3工廠170090080012工廠280090070015訂貨量(個(gè))108927(產(chǎn)銷平衡)3.3網(wǎng)絡(luò)配送問題解：本問題是運(yùn)輸問題，是典型的網(wǎng)絡(luò)配送問題。由于“總產(chǎn)量（27）＝總訂貨量（27）”，故該問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。（1）決策變量本問題要做的決策是每個(gè)工廠運(yùn)送多少個(gè)產(chǎn)品給每個(gè)顧客。設(shè)：xij為從工廠i運(yùn)送給顧客j的產(chǎn)品數(shù)量（i＝1,2;j=1,2,3)（2）目標(biāo)函數(shù)公司的總運(yùn)輸成本最低（3）約束條件①工廠運(yùn)送出去的產(chǎn)品數(shù)量等于其產(chǎn)量②顧客收到的產(chǎn)品數(shù)量等于其訂貨量③非負(fù)3.3網(wǎng)絡(luò)配送問題例3.3的線性規(guī)劃模型3.3網(wǎng)絡(luò)配送問題例3.3的電子表格模型3.4混合問題前面討論了線性規(guī)劃問題的三種類型：資源分配問題、成本收益平衡問題和網(wǎng)絡(luò)配送問題。如表3-8所總結(jié)的，每一類問題都是以一類約束條件為特色的。實(shí)際上，純資源分配問題的共性是它所有的函數(shù)約束均為資源約束（≤）純成本收益平衡問題的共性是它所有的函數(shù)約束均為收益約束（）網(wǎng)絡(luò)配送問題中，主要的函數(shù)約束為確定需求約束（＝）3.4混合問題但許多線性規(guī)劃問題并不能直接歸入三類中的某一類，一些問題因其主要的函數(shù)約束與表3-8中的相應(yīng)函數(shù)約束大致相同而勉強(qiáng)可以歸入某一類。而另一些問題卻沒有一類占主導(dǎo)地位的函數(shù)約束從而不能歸入前三類中的某一類。因此，混合問題是第四類線性規(guī)劃問題，這一類型將包括所有未歸入前述三類中的線性規(guī)劃問題。一些混合問題僅包含兩類函數(shù)約束，而更多的是包含三類函數(shù)約束。3.4混合問題表3-8各類函數(shù)約束類型形式解釋主要用于資源約束LHS

RHS對于特定的資源使用的數(shù)量

可用的數(shù)量資源分配問題混合問題收益約束LHS

RHS對于特定的收益實(shí)現(xiàn)的水平

最低的可接受水平成本收益平衡問題混合問題確定需求約束LHS=RHS對于特定的數(shù)量提供的數(shù)量=需求的數(shù)量網(wǎng)絡(luò)配送問題混合問題注：LHS=左式（一個(gè)SUMPRODUCT函數(shù)）

RHS=右式（一般為常數(shù)）3.4.2混合問題的應(yīng)用舉例一：配料問題配料問題的一般提法是：生產(chǎn)某類由各種原料混合而成的產(chǎn)品，如何在滿足規(guī)定的質(zhì)量標(biāo)準(zhǔn)的條件下，使所用原料的總成本最低。例3.4某公司計(jì)劃要用Ａ、Ｂ、C三種原料混合調(diào)制出三種不同規(guī)格的產(chǎn)品甲、乙、丙，產(chǎn)品的規(guī)格要求和單價(jià)、原料供應(yīng)量和單價(jià)等數(shù)據(jù)如表3-9所示。問該公司應(yīng)如何安排生產(chǎn)，才能使總利潤最大？3.4.2混合問題的應(yīng)用舉例一：配料問題表3-9例3.4配料問題的相關(guān)數(shù)據(jù)原料A原料B原料C產(chǎn)品單價(jià)（元/千克）產(chǎn)品甲

50%

35%不限90產(chǎn)品乙

40%

45%不限85產(chǎn)品丙30%50%20%65原料供應(yīng)量（千克）200150100原料單價(jià)（元/千克）6035303.4.2混合問題的應(yīng)用舉例一：配料問題解：（1）決策變量本問題的難點(diǎn)在于給出的數(shù)據(jù)是非確定的數(shù)值，而且各產(chǎn)品與原料的關(guān)系較為復(fù)雜。為了方便，設(shè)xij為原料i（i=A，B，C）混合到產(chǎn)品j（j=1，2，3分別表示甲、乙、丙）的數(shù)量。（2）目標(biāo)函數(shù) 本問題的目標(biāo)是公司的總利潤最大，總利潤＝產(chǎn)品銷售收入－原料成本3.4.2混合問題的應(yīng)用舉例一：配料問題（3）約束條件

本問題的約束條件：原料供應(yīng)量限制3個(gè)、規(guī)格要求7個(gè)和非負(fù)。在例3.4中，有9個(gè)決策變量和10個(gè)函數(shù)約束條件（5個(gè)資源約束、2個(gè)收益約束和3個(gè)確定需求約束）3.4.2混合問題的應(yīng)用舉例一：配料問題例3.4的電子表格模型3.4.3混合問題的應(yīng)用舉例二：營養(yǎng)配餐問題例3.5某幼兒園想確定如何搭配學(xué)齡前兒童的午餐。一方面想要降低成本，另一方面又要使午餐達(dá)到一定的營養(yǎng)標(biāo)準(zhǔn)。午餐提供的食物的營養(yǎng)成分和相應(yīng)的成本如表3?12所示。兒童的營養(yǎng)要求：每個(gè)兒童攝取的總熱量為400～600卡路里，其中來自脂肪的熱量不超過30％。每位兒童至少要攝取60毫克維生素C和12克蛋白質(zhì)。此外，為了制作三明治，每位兒童需要兩片面包，花生醬的量至少是草莓醬的2倍，以及至少1杯飲料（牛奶和/或果汁）。請合理搭配各種食物，從而在達(dá)到營養(yǎng)標(biāo)準(zhǔn)的前提下，使得總成本最小。食物總熱量（卡路里）脂肪熱量（卡路里）維生素C（毫克）蛋白質(zhì)（克）成本（元）面包（1片）7010030.5花生醬（1匙）10075040.4草莓醬（1匙）500300.7餅干（1塊）6020010.8牛奶（1杯）15070281.5果汁（1杯）100012013.53.4.3混合問題的應(yīng)用舉例二：營養(yǎng)配餐問題例3.5的線性規(guī)劃模型

設(shè)搭配兒童營養(yǎng)午餐時(shí)，需要面包x1片、花生醬x2匙、草莓醬x3

匙、餅干x4

塊、牛奶x5

杯、果汁x6

杯。3.4.3混合問題的應(yīng)用舉例二：營養(yǎng)配餐問題例3.5的電子表格模型3.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題例3.6

某市場調(diào)查公司受某廠的委托，調(diào)查消費(fèi)者對某種新產(chǎn)品的了解和反應(yīng)情況。該廠對市場調(diào)查公司提出了以下要求：（1）共對500個(gè)家庭進(jìn)行調(diào)查；（2）在受訪家庭中，至少有200個(gè)有孩子的家庭，同時(shí)至少有200個(gè)無孩子的家庭；（3）至少對300個(gè)受訪家庭采用問卷式書面調(diào)查，對其余家庭可采用口頭調(diào)查；（4）在有孩子的受訪家庭中，至少對50％的家庭采用問卷式書面調(diào)查；（5）在無孩子的受訪家庭中，至少對60％的家庭采用問卷式書面調(diào)查。3.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題對不同家庭采用不同調(diào)查方式的費(fèi)用如表3-14所示。問：市場調(diào)查公司應(yīng)如何進(jìn)行調(diào)查，才能在滿足廠方要求的條件下，使得總調(diào)查費(fèi)用最少？表3-14不同家庭采用不同調(diào)查方式的費(fèi)用問卷式書面調(diào)查口頭調(diào)查有孩子的家庭5030無孩子的家庭40253.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題解：（1）決策變量根據(jù)題意，本問題的決策變量如下：

x11：對有孩子的家庭采用問卷式書面調(diào)查的家庭數(shù)

x12：對有孩子的家庭采用口頭調(diào)查的家庭數(shù)

x21：對無孩子的家庭采用問卷式書面調(diào)查的家庭數(shù)

x22：對無孩子的家庭采用口頭調(diào)查的家庭數(shù)。（2）目標(biāo)函數(shù)

本問題的目標(biāo)是市場調(diào)查公司的總調(diào)查費(fèi)用最少3.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題（3）約束條件共對500個(gè)家庭進(jìn)行調(diào)查； 至少有200個(gè)有孩子的家庭； 至少有200個(gè)無孩子的家庭； 至少對300個(gè)受訪家庭采用問卷式書面調(diào)查； 在有孩子的受訪家庭中，至少對50％的家庭采用問卷式書面調(diào)查；在無孩子的受訪家庭中，至少對60％的家庭采用問卷式書面調(diào)查；非負(fù)。3.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題例3.6的線性規(guī)劃模型3.4.4混合問題的應(yīng)用舉例三：市場調(diào)查問題例3.6的電子表格模型本章上機(jī)實(shí)驗(yàn)1．實(shí)驗(yàn)?zāi)康?/p>

掌握使用Excel軟件求解線性規(guī)劃問題的操作方法。2．內(nèi)容和要求

使用Excel軟件求解習(xí)題3.1、習(xí)題3.2、習(xí)題3.3、案例3.1（或其他例子、習(xí)題、案例等）。3．操作步驟

（1）在Excel中建立電子表格模型；

（2）使用Excel軟件中的“規(guī)劃求解”命令求解線性規(guī)劃問題；

（3）結(jié)果分析；

（4）在Excel文件或Word文檔中撰寫實(shí)驗(yàn)報(bào)告，包括線性規(guī)劃模型、電子表格模型和結(jié)果分析等。

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

4.1運(yùn)輸問題的基本概念例4.1某公司有三個(gè)加工廠（A1、A2和A3）生產(chǎn)某種產(chǎn)品，每日的產(chǎn)量分別為：7噸、4噸、9噸；該公司把這些產(chǎn)品分別運(yùn)往四個(gè)銷售點(diǎn)（B1、B2、B3和B4），各銷售點(diǎn)每日的銷量分別為：3噸、6噸、5噸、6噸；從三個(gè)加工廠（產(chǎn)地）到四個(gè)銷售點(diǎn)（銷地）的單位產(chǎn)品運(yùn)價(jià)如表4-2所示。問該公司應(yīng)如何調(diào)運(yùn)產(chǎn)品，才能在滿足四個(gè)銷售點(diǎn)的需求量的前提下，使總運(yùn)費(fèi)最少？

表4-2三個(gè)加工廠到四個(gè)銷售點(diǎn)的單位產(chǎn)品運(yùn)價(jià)（千元/噸）銷售點(diǎn)B1銷售點(diǎn)B2銷售點(diǎn)B3銷售點(diǎn)B4加工廠A1311310加工廠A21928加工廠A3741054.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型解：首先，三個(gè)加工廠A1、A2、A3的總產(chǎn)量為7＋4＋9＝20（噸）；四個(gè)銷售點(diǎn)B1、B2、B3、B4的總銷量為3＋6＋5＋6＝20（噸）。也就是說，總產(chǎn)量等于總銷量，故該運(yùn)輸問題是一個(gè)產(chǎn)銷平衡的運(yùn)輸問題。（1）決策變量設(shè)xij為從加工廠Ai（i＝1,2,3）運(yùn)往銷售點(diǎn)Bj（j=1,2,3,4）的運(yùn)輸量（噸）。（2）目標(biāo)函數(shù)本問題的目標(biāo)是使公司的總運(yùn)費(fèi)最少4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型（3）約束條件①三個(gè)加工廠的產(chǎn)品都要全部運(yùn)送出去（產(chǎn)量約束）②四個(gè)銷售點(diǎn)的產(chǎn)品都要全部得到滿足（銷量約束）③非負(fù)4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型運(yùn)輸問題是一種特殊的線性規(guī)劃問題，一般采用“表上作業(yè)法”求解運(yùn)輸問題，但Excel的“規(guī)劃求解”還是采用“單純形法”來求解。例4.1的電子表格模型（1）設(shè)置“條件格式”的操作請參見本章附錄Ⅱ（P142）（2）將單元格的字體和背景顏色設(shè)置為相同顏色以實(shí)現(xiàn)“渾然一體”的效果，這樣可以起到隱藏單元格內(nèi)容的作用。當(dāng)單元格被選中時(shí)，編輯欄中仍然會(huì)顯示單元格的真實(shí)數(shù)據(jù)。（3）本章所有例題的最優(yōu)解（運(yùn)輸方案或指派方案）有一個(gè)共同特點(diǎn)：“0”值較多，所以都使用了Excel的“條件格式”功能。4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型需要注意的是，運(yùn)輸問題有這樣一個(gè)性質(zhì)（整數(shù)解性質(zhì)），即只要它的供應(yīng)量和需求量都是整數(shù)，任何有可行解的運(yùn)輸問題就必然有所有決策變量都是整數(shù)的最優(yōu)解。因此，沒有必要加上所有變量都是整數(shù)的約束條件。由于運(yùn)輸量經(jīng)常以卡車、集裝箱等為單位，如果卡車不能裝滿，就很不經(jīng)濟(jì)了。整數(shù)解性質(zhì)避免了運(yùn)輸量（運(yùn)輸方案）為小數(shù)的麻煩。4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型（1）銷大于產(chǎn)（供不應(yīng)求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的產(chǎn)量為準(zhǔn)）4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型（2）產(chǎn)大于銷（供過于求）運(yùn)輸問題的數(shù)學(xué)模型（以滿足小的銷量為準(zhǔn)）4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2自來水輸送問題。某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來水由A、B、C三個(gè)水庫供應(yīng)。四個(gè)居民區(qū)每天必須得到保證的基本生活用水量分別為30、70、10、10千噸，但由于水源緊張，三個(gè)水庫每天最多只能分別供應(yīng)50、60、50千噸自來水。由于地理位置的差別，自來水公司從各水庫向各居民區(qū)供水所需付出的引水管理費(fèi)不同（見P95的表4?4，其中水庫C與丁區(qū)之間沒有輸水管道），其他管理費(fèi)用都是450元／千噸。根據(jù)公司規(guī)定，各居民區(qū)用戶按照統(tǒng)一標(biāo)準(zhǔn)900元／千噸收費(fèi)。此外，四個(gè)居民區(qū)都向公司申請了額外用水量，分別為每天50、70、20、40千噸。問：（1）該公司應(yīng)如何分配供水量，才能獲利最多？（2）為了增加供水量，自來水公司正在考慮進(jìn)行水庫改造，使三個(gè)水庫每天的最大供水量都提高一倍，問那時(shí)供水方案應(yīng)如何改變？公司利潤可增加到多少？4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（1）的線性規(guī)劃模型：目標(biāo)：從獲利最多轉(zhuǎn)化為引水管理費(fèi)最少4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（1）的電子表格模型：4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（1）的最優(yōu)供水方案網(wǎng)絡(luò)圖：BCA乙丙甲丁5080140305060505010504010水庫供水量居民區(qū)最大供水量最大用水量4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（2）方法1的線性規(guī)劃模型：目標(biāo)：將獲利最多轉(zhuǎn)化為引水管理費(fèi)最少4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（2）方法1的電子表格模型：4.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（2）的最優(yōu)供水方案網(wǎng)絡(luò)圖：BCA乙丙甲丁10080140305012010010050305030水庫供水量居民區(qū)最大供水量最大用水量404.2運(yùn)輸問題的數(shù)學(xué)模型和電子表格模型例4.2問題（2）方法2：目標(biāo)為獲利最多4.3運(yùn)輸問題的變形現(xiàn)實(shí)生活中符合產(chǎn)銷平衡運(yùn)輸問題的每一個(gè)條件的情況很少。一個(gè)特征近似但其中的一個(gè)或者幾個(gè)特征卻并不符合產(chǎn)銷平衡運(yùn)輸問題條件的運(yù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è)需求量（銷量）代表了在其目的地（銷地）中所接收到的最大數(shù)量（而不是一個(gè)固定的數(shù)值，≤）。（3）一個(gè)目的地（銷地）同時(shí)存在著最小需求量和最大需求量，于是所有在這兩個(gè)數(shù)值之間的數(shù)量都是可以接收的（需求量可在一定范圍內(nèi)變化，≥、≤）。（4）在運(yùn)輸中不能使用特定的出發(fā)地（產(chǎn)地）--目的地（銷地）組合（xij=0）。（5）目標(biāo)是使與運(yùn)輸量有關(guān)的總利潤最大而不是使總成本最?。∕in－>Max）4.3運(yùn)輸問題的變形例4.3

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

；并且，總供應(yīng)量（75+75+45=195）>總需求量（20+30+30+40=120）。其數(shù)學(xué)模型如下：設(shè)xij為工廠i生產(chǎn)產(chǎn)品j的數(shù)量4.3運(yùn)輸問題的變形例4.3的電子表格模型產(chǎn)品4分在2個(gè)工廠（工廠2和工廠3）生產(chǎn)4.3運(yùn)輸問題的變形例4.4需求量存在最小需求量和最大需求量（需求量可在一定范圍內(nèi)變化）的問題。某公司在三個(gè)工廠中專門生產(chǎn)一種產(chǎn)品。在未來的四個(gè)月中，四個(gè)處于國內(nèi)不同區(qū)域的潛在顧客（批發(fā)商）很可能有大量訂購。顧客1是公司最好的顧客，所以他的訂單要全部滿足；顧客2和顧客3也是公司很重要的顧客，所以營銷經(jīng)理認(rèn)為至少要滿足他們訂單的1/3；對于顧客4，營銷經(jīng)理認(rèn)為并不需要特殊考慮。由于運(yùn)輸成本上的差異，銷售一個(gè)產(chǎn)品得到的利潤也不同，利潤很大程度上取決于哪個(gè)工廠供應(yīng)哪個(gè)顧客（見表4-8）。問應(yīng)向每一個(gè)顧客供應(yīng)多少產(chǎn)品，才能使公司的總利潤最大？表4-8三個(gè)工廠供應(yīng)四個(gè)顧客的相關(guān)數(shù)據(jù)單位利潤（元）產(chǎn)量顧客1顧客2顧客3顧客4工廠1554246538000工廠2371832485000工廠3295951357000最少供應(yīng)量7000300020000要求訂購量70009000600080004.3運(yùn)輸問題的變形解：該問題要求滿足不同顧客的需求（訂購量），解決辦法：實(shí)際供應(yīng)量

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

要求訂購量

目標(biāo)是總利潤最大，而不是總成本最小。其數(shù)學(xué)模型如下：設(shè)xij為工廠i供應(yīng)顧客j的產(chǎn)品數(shù)量4.3運(yùn)輸問題的變形例4.4的電子表格模型4.4運(yùn)輸問題的應(yīng)用舉例例4.5（了解即可）

某航運(yùn)公司承擔(dān)六個(gè)港口城市A、B、C、D、E、F的四條固定航線的物資運(yùn)輸任務(wù)。各條航線的起點(diǎn)、終點(diǎn)城市及每天航班數(shù)如表4-9所示。假定各條航線使用相同型號的船只，各城市間的航程天數(shù)見表4-10。又知每艘船只每次裝卸貨的時(shí)間各需1天。問該航運(yùn)公司至少應(yīng)配備多少艘船，才能滿足所有航線的運(yùn)貨需求？解：該公司所需配備船只分為兩部分。（1）載貨航程需要的周轉(zhuǎn)船只數(shù)：直接計(jì)算。（2）各港口間調(diào)度所需船只數(shù)：運(yùn)輸問題。了解即可4.4運(yùn)輸問題的應(yīng)用舉例例4.5的電子表格模型了解即可4.4運(yùn)輸問題的應(yīng)用舉例例4.6設(shè)有某種原料的三個(gè)產(chǎn)地A1、A2和A3，把這種原料經(jīng)過加工制成成品，再運(yùn)往銷售地。假設(shè)用4噸原料可制成1噸成品。產(chǎn)地A1年產(chǎn)原料30萬噸，同時(shí)需要成品7萬噸；產(chǎn)地A2年產(chǎn)原料26萬噸，同時(shí)需要成品13萬噸；產(chǎn)地A3年產(chǎn)原料24萬噸，不需要成品。又知A1與A2的距離為150公里，A1與A3的距離為100公里，A2與A3的距離為200公里。原料運(yùn)費(fèi)為3千元/萬噸?公里，成品運(yùn)費(fèi)為2.5千元/萬噸?公里。且已知在產(chǎn)地A1把4萬噸原料制成1萬噸成品的加工費(fèi)為5.5千元，在產(chǎn)地A2為4千元，在產(chǎn)地A3為3千元，見表4-16。因條件限制，產(chǎn)地A2的生產(chǎn)規(guī)模不能超過年產(chǎn)成品5萬噸，而產(chǎn)地A1和產(chǎn)地A3沒有限制。問應(yīng)在何地設(shè)廠，生產(chǎn)多少成品，才能使總費(fèi)用（包括原料運(yùn)費(fèi)、成品運(yùn)費(fèi)、加工費(fèi)等）最少？

A1A2A3年產(chǎn)原料（萬噸）加工費(fèi)（千元/萬噸）A10150100305.5A21500200264A31002000243成品需求量（萬噸）7130

4.4運(yùn)輸問題的應(yīng)用舉例解：該問題包含兩個(gè)運(yùn)輸問題，一個(gè)是原料的運(yùn)輸問題，另一個(gè)是成品的運(yùn)輸問題。還有將原料制成成品的問題，所以，總費(fèi)用＝原料運(yùn)費(fèi)＋成品運(yùn)費(fèi)＋加工費(fèi)。例4.6的線性規(guī)劃模型4.4運(yùn)輸問題的應(yīng)用舉例例4.6的電子表格模型4.5指派問題的基本概念在生活中經(jīng)常會(huì)遇到這樣的問題：某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可以承擔(dān)這些任務(wù)。由于每個(gè)人的專長不同，各人完成的任務(wù)不同，所需的時(shí)間（或效率）也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)所需的總時(shí)間最短（或總效率最高）。這類問題稱為指派問題（assignmentproblem）或分派問題。平衡指派問題的假設(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)是要確定如何指派才能使總成本最小。4.5指派問題的基本概念設(shè)xij為是否指派第i個(gè)人去完成第j項(xiàng)任務(wù)，目標(biāo)函數(shù)系數(shù)cij為第i個(gè)人完成第j項(xiàng)任務(wù)所需要的單位成本。平衡指派問題的線性規(guī)劃模型如下：4.5指派問題的基本概念需要說明的是：指派問題實(shí)際上是一種特殊的運(yùn)輸問題。其中出發(fā)地是“人”，目的地是“任務(wù)”。只不過，每個(gè)出發(fā)地的供應(yīng)量都為1（因?yàn)槊總€(gè)人都要完成一項(xiàng)任務(wù)），每個(gè)目的地的需求量也都為1（因?yàn)槊宽?xiàng)任務(wù)都要完成）。由于運(yùn)輸問題有“整數(shù)解性質(zhì)”，因此，指派問題沒有必要加上所有決策變量都是0-1變量的約束條件。指派問題是一種特殊的線性規(guī)劃問題，有一種簡便的求解方法：匈牙利方法（HungarianMethod），但Excel的“規(guī)劃求解”還是采用“單純形法”來求解。4.5指派問題的基本概念例4.7

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

該問題是一個(gè)典型的平衡指派問題。單位成本為每個(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)）相等4.5指派問題的基本概念例4.7的線性規(guī)劃模型如下：設(shè)xij為是否指派人員i去完成任務(wù)j

4.5指派問題的基本概念例4.7的電子表格模型4.5指派問題的基本概念例4.7的最優(yōu)指派方案網(wǎng)絡(luò)圖小李小劉小張BCAD人指派任務(wù)小王4.6指派問題的變形經(jīng)常會(huì)遇到指派問題的變形，之所以稱它們?yōu)樽冃?，是因?yàn)樗鼈兌疾粷M足平衡指派問題所有假設(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í)被指派多個(gè)任務(wù)（一人可做多事）；（5）某事需要由多人共同完成（一事需多人做）；（6）目標(biāo)是與指派有關(guān)的總利潤最大而不是總成本最?。唬?）實(shí)際需要完成的任務(wù)數(shù)不超過總?cè)藬?shù)也不超過總?cè)蝿?wù)數(shù)。4.6指派問題的變形例4.8

題目見例4.3，即某公司需要安排三個(gè)工廠來生產(chǎn)四種新產(chǎn)品，相關(guān)的數(shù)據(jù)在表4-7中已經(jīng)給出。在例4.3中，允許產(chǎn)品生產(chǎn)分解，但這將產(chǎn)生與產(chǎn)品生產(chǎn)分解相關(guān)的隱性成本（包括額外的設(shè)置、配送和管理成本等）。因此，管理人員決定在禁止產(chǎn)品生產(chǎn)分解發(fā)生的情況下對問題進(jìn)行分析。新問題描述為：已知如表4-7所示的數(shù)據(jù)，問如何把每個(gè)工廠指派給至少一個(gè)新產(chǎn)品（每種產(chǎn)品只能在一個(gè)工廠生產(chǎn)），才能使總成本最少？4.6指派問題的變形解：

該問題可視為指派工廠生產(chǎn)產(chǎn)品問題，工廠可以看作指派問題中的人，產(chǎn)品則可以看作需要完成的任務(wù)。

由于有四種產(chǎn)品和三個(gè)工廠，所以就需要有一個(gè)工廠生產(chǎn)兩種新產(chǎn)品，只有工廠1和工廠2有生產(chǎn)兩種產(chǎn)品的能力，這是因?yàn)楣S