实用运筹学课件

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

x2為窗的每週產量（扇）。（2）目標函數本問題的目標是兩種新產品的總利潤最大。由於門和窗的單位利潤分別為300元和500元，而其每週產量分別為x1和x2，所以每週總利潤z可表示为：

z=300x1＋500x2

（元）1.1線性規劃的基本概念和數學模型（3）約束條件本問題的約束條件共有四個。車間1每週可用工時限制：x1

4車間2每週可用工時限制：2x212車間3每週可用工時限制：3x1

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

達到最大時x1，x2

的取值。1.1線性規劃的基本概念和數學模型

本章討論的問題均為線性規劃問題。所謂“線性”規劃，是指如果目標函數是關於決策變數的線性函數，而且約束條件也都是關於決策變數的線性等式或線性不等式，則相應的規劃問題就稱為線性規劃問題。1.1線性規劃的基本概念和數學模型例1.2

營養配餐问题。某飼料公司希望用玉米、紅薯兩種原料配製一種混合飼料，兩種原料包含的營養成分和採購成本都不相同，公司管理層希望能夠確定混合飼料中兩種原料的數量，使得飼料能夠以最低的成本達到一定的營養要求。研究者根據這一目標收集到的有關數據如表1-2所示。營養成分每公斤玉米每公斤紅薯營養要求碳水化合物8420蛋白質3618維他命1516採購成本（元）1.81.6

1.1線性規劃的基本概念和數學模型解：（1）決策變數本問題要決策（確定）的是混合飼料中兩種原料的數量（原料採購量）。可設：x1為玉米採購量；x2

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

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

需求量－120130

1.1線性規劃的基本概念和數學模型例1.3物流網絡配送問題--配送網路圖9.22.390902.38.23.43.53.06060607.513TBA28070120130配送中心100產量工廠單位運輸成本倉庫需求量1.1線性規劃的基本概念和數學模型例1.3物流網絡配送問題的線性規劃模型為：1.1線性規劃的基本概念和數學模型線性規劃的一般形式為:對於一組決策變數x1，x2，，xn，取1.1線性規劃的基本概念和數學模型線上性規劃模型中，也直接稱z為目標函數；稱xj(j=1,2,

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

,n)

為目標函數係數、價值係數或費用係數；稱bi(i=1,2,

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

,m;j=1,2,

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

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

“規劃求解”工具求解線性規劃問題P23，圖1-22例1.3的電子錶格模型1.4線性規劃問題求解的幾種可能結果唯一解無窮多解無解可行域無界（目標值不收斂）1.4線性規劃問題求解的幾種可能結果唯一解線性規劃問題具有唯一解是指該線性規劃問題有且僅有一個既在可行域內、又使目標值達到最優的解。例1.1就是一個具有唯一解的線性規劃問題。1.4線性規劃問題求解的幾種可能結果無窮多解線性規劃問題具有無窮多解是指該線性規劃問題有無窮多個既在可行域内、又能使目標值達到最優的解。在例1.1中，假設門的單位利潤從300元增加至750元，這時該問題的解將發生變化。1.4線性規劃問題求解的幾種可能結果無解當線性規劃問題中的約束條件不能同時滿足時，無可行域的情況將會出現，這時不存在可行解，即該線性規劃問題無解。在例1.1中，若要求門的每週產量不得少於6，則需再加上一個約束條件：x161.4線性規劃問題求解的幾種可能結果可行域無界（目標值不收斂）線性規劃問題的可行域無界，是指最大化問題中的目標函數值可以無限增大，或最小化問題中的目標函數值可以無限減少。在例1.1中，如果沒有車間可用工時的約束，但要求門與窗的總產量不得少於4。1.5建立規劃模型的流程建立規劃模型的工作既是一門科學，又是一門藝術。NYNY實際問題向規劃問題的提煉確定決策變數確定目標函數確定約束條件有無法定量表述的成分輔助決策實際應用模型分析和檢驗，提交定量報告解讀軟體運行結果開展人機對話，把數學模型軟體化上機調試通過報告本章上机实验1．實驗目的

在Excel2010軟體中加載“規劃求解”工具，使用Excel2010軟體求解線性規劃問題。2．內容和要求

（1）在Excel2010軟體中，加載“規劃求解”工具；

（2）在Excel2010軟體中，建立新問題，輸入模型，求解模型，對結果進行簡單分析。3．操作步驟

使用Excel2010軟體求解習題1.1、案例1.1（或其他例子、習題、案例等）。

（1）在Excel中建立電子錶格模型：輸入數據、給單元格或區域命名、輸入公式等。

（2）使用Excel2010軟體中的“規劃求解”工具求解线性规划问题。

（3）結果分析：如每月生產四種產品各多少噸？總利潤是多少？哪些原料有剩餘？並對結果提出自己的看法。

（4）在Excel檔或Word文檔中撰寫實驗报告，包括线性规划模型、电子表格模型和结果分析等。

線性規劃靈敏度分析SensitivityAnalysisforLinearProgramming2.1線性規劃的靈敏度分析在第1章的討論中，假定線性規劃模型中的各個參數cj、aij、bi是確定的常數，並根據這些數據，求得最優解。2.1線性規劃的靈敏度分析其實，参数cj、aij、bi都有可能变化，因此，需要進行進一步的分析，以決定是否需要調整決策。靈敏度分析研究的另一類問題是探討在原線性規劃模型的基礎上增加一個變數或者一個約束條件對最優解的影響。2.1線性規劃的靈敏度分析對例1.1進行靈敏度分析最優解為（2，6）最優值為36002.1線性規劃的靈敏度分析問題1：如果門的單位利潤由原來的300元增加到500元，最優解是否會改變？對總利潤又會產生怎樣的影響?問題2：如果門和窗的單位利潤都發生變化，最優解會不會發生改變？對總利潤又會產生怎樣的影響?問題3：如果車間2的可用工時增加1小時，總利潤是否會發生變化？如何改變?最優解是否會發生變化?問題4：如果同時改變多個車間的可用工時，總利潤是否會發生變化？如何改變?最優解是否會發生變化?問題5：如果車間2更新生產工藝，生產一扇窗由原來的2小時下降为1.5小時,最優解是否會發生改變？總利潤是否會發生變化？問題6：工廠考慮增加一種新產品，總利潤是否會發生變化？問題7：如果工廠新增用電限制，是否会改变原来的最優方案？2.2單個目標函數係數变化的灵敏度分析下麵討論在假定只有一個係數cj發生變化，模型中的其他參數保持不變的情況下，單個目標函數係數變化對最優解的影響。如果當初對門的單位利潤估計不准確，如把它改成500元，是否會影響求得的最優解呢？方法1：使用電子錶格進行互動分析（重新運行Excel“規劃求解”命令）方法2：運用“敏感性報告”尋找單個目標函數係數的允許變化範圍2.2單個目標函數係數變化的靈敏度分析方法1：使用電子錶格进行互动分析（重新运行Excel“規劃求解”命令）可以借助电子表格互动地展開靈敏度分析。當模型參數發生改變時，只要修改电子表格模型中相应的参数，再重新运行Excel“規劃求解”命令，就可以看出改变参数對最優解和最優值的影響。需要逐個進行嘗試，效率略顯低下2.2單個目標函數係數變化的靈敏度分析方法2：運用“敏感性報告”尋找單個目標函數係數的允許變化範圍生成“敏感性報告”工作表讀懂相應的資訊2.2單個目標函數係數變化的靈敏度分析結果：最優解沒有发生变化，仍然是（2，6）由於門的單位利潤增加了500－300＝200（元），因此總利潤增加了200×2＝400（元）。2.2單個目標函數係數變化的靈敏度分析圖解法（直觀）可以看到，

最優解（2，6）保持不變

2.3多個目標函數係數同時變化的靈敏度分析假如，原先門的單位利潤（300元）估計低了，現在升為450元；同時，以前窗的單位利潤（500元）估計高了，現在降為400元。這樣的變化，是否會導致最優解發生變化呢？方法1：使用電子錶格進行互動分析（重新運行Excel“規劃求解”命令）方法2：運用“敏感性報告”進行分析（目標函數係數同時變化的百分之百法則）2.3多個目標函數係數同時變化的靈敏度分析方法1：使用電子錶格進行互動分析，重新運行Excel“規劃求解”命令可以看出，最優解並沒有發生變化，總利潤由於門和窗的單位利潤的改變相應地改變了(450－300)×2＋(400－500)×6＝－3002.3多個目標函數係數同時變化的靈敏度分析方法2：運用“敏感性報告”進行分析目標函數係數同時变化的百分之百法則:如果目標函數係數同时变化，計算出每一係數变化量占该系数允许變化量（允许的增量或允许的减量）的百分比，然后将各個系数变化的百分比相加。如果所得的变化的百分比總和不超过100%，則最優解不会变化；如果超过了100%，則不能確定最優解是否改变（可能改变，也可能不变），可通过重新運行“規劃求解”命令來判斷。2.3多個目標函數係數同時變化的靈敏度分析但是變化的百分比總和超過100%，並不表示最優解一定會改變。例如，門和窗的單位利潤都減半變化的百分比總和超過了100%，但從右圖看最優解還是（2，6），沒有發生改變。這是由於這兩個單位利潤同比例变化，等利潤直線的斜率不變，因此最優解就保持不变。2.4單個約束右端值變化的靈敏度分析單個約束右端值变化对目標值的影響如果車間2的可用工時增加1小時，總利潤是否會發生變化？如何改變?最優解是否會發生變化?方法1：使用電子錶格进行互动分析（重新運行“規劃求解”命令）方法2：從“敏感性報告”中獲得關鍵資訊（影子價格，shadowprice）2.4單個約束右端值變化的靈敏度分析方法1：使用電子錶格进行互动分析，重新運行“規劃求解”命令總利潤為3750元，增加了3750－3600＝150（元）。由於總利潤增加了，而目標函數係數不變，所以最優解一定會發生改變，從圖中可以看出，最優解由原來的（2，6）變為（1.667，6.5）

2.4單個約束右端值變化的灵敏度分析方法2：從“敏感性報告”中獲得關鍵資訊在給定線性規劃模型的最優解和目标函数值（最优值）的條件下，影子价格（shadowprice）就是約束右端值每增加（或减少）1個單位，目標函數值（最优值）增加（或减少）的数量第二個約束條件（車間2的工時約束）的影子價格是150，說明在允許的範圍[6，18]（即[12-6，12+6]）內，再增加（或減少）1小時的可用工时，总利润将增加（或减少）150（元）。2.4單個約束右端值變化的靈敏度分析圖解法（直觀）可以看到，

在這個範圍內，车间2的約束右端值每增加（或减少）1個單位，交点的移动就使利润增长（或减少）1個影子價格的数量（150元）2.5多個約束右端值同時變化的靈敏度分析多個約束右端值同時變化對目標值的影響將1小時的工時從車間3移到車間2，對總利潤所產生的影響方法1：使用電子錶格進行互動分析（重新運行“規劃求解”命令）方法2：運用“敏感性報告”進行分析（約束右端值同時變化的百分之百法則）2.5多個約束右端值同時變化的靈敏度分析方法1：使用電子錶格进行互动分析（重新運行“規劃求解”命令）總利潤增加了3650-3600=50（元），影子價格有效。2.5多個約束右端值同時變化的靈敏度分析方法2：運用“敏感性報告”進行分析約束右端值同时變化的百分之百法则：如果约束右端值同時變化，计算每一右端值变化量占該約束右端值允許变化量（允许的增量或允许的减量）的百分比，然後将各个右端值变化的百分比相加。如果所得的变化的百分比总和不超過100%，那麼影子价格依然有效；如果超過了100％，那就無法確定影子價格是否依然有效（可能有效，也可能无效），可通过重新運行“規劃求解”命令來判斷。2.5多個約束右端值同時變化的靈敏度分析在影子價格的有效範圍內，總利潤的變化量可以直接通過影子價格來計算。比如將車間3的3個工時轉移給車間2，由於所以，總利潤的變化量為2.6約束條件係數變化的靈敏度分析車間2更新生產工藝，生產一扇窗由原來的2小時下降为1.5小時,此時最優解是否会发生改变？总利润是否会发生变化？使用電子錶格进行互动分析(重新運行“規劃求解”命令)重新運行“規劃求解”命令後，最优解发生了改变，變為（2/3，8），總利潤也由原来的3600元增加到4200元。可見，車間2更新生產工藝後，為工廠增加了利潤。2.7增加一個新變數例2.1工廠考虑增加一种新产品：防盜門，假設其单位利润为400元。生產一扇防盗门會佔用車間1、車間2、車間3各2、1、1小時，總利润是否会发生变化？使用電子錶格进行互动分析（重新運行“規劃求解”命令)最優解為(2,5.5,1）,總利潤為3750元。可見新產品為工廠增加了利润。2.8增加一個約束條件增加電力供应限制(例2.2假定生产一扇门和窗需要消耗電力分別為20kw和10kw，工廠可供電量最多为90kw),最優解是否會發生變化?使用電子錶格进行互动分析(重新運行“規劃求解”命令)可見電力約束的確限制了門的每週產量（而窗的每週產量不變），最优解變成(1.5,6),總利潤也相应地下降為3450元。2.9靈敏度分析的應用舉例例2.3力浦公司是一家生產外牆塗料的建材公司，目前生產甲、乙兩種規格的產品，這兩種產品在市場上的單位利潤分別是4萬元和5萬元。甲、乙兩種產品均需要同時消耗A、B、C三種化工材料，生產1單位的產品甲需要消耗三種材料的情況是：1單位的材料A、2單位的材料B和1單位的材料C；而生產1單位的產品乙則需要1單位的材料A、1單位的材料B和3單位的材料C。當前市場上的甲、乙兩種產品供不應求，但是在每個生產週期（假設一年）內，公司的A、B、C三種原材料資源的儲備量分別是45單位、80單位和90單位，年終剩餘的資源必須無償調回，而且近期也沒有籌集到額外資源的管道。面對這種局面，力浦公司應如何安排生產計畫，以獲得最大的市場利潤？2.9靈敏度分析的應用舉例該公司在运营了一年后，管理层为第二年的运营进行了以下的预想（假设以下问题均单独出现）：問題1：由於建材市場受到其他競爭者的影響，公司市場行銷部門預測當年的產品甲的價格會產生變化：產品甲的單位利潤將會在3.8萬元～5.2萬元之間波動。公司該如何應對這種情況，提前對生產格局做好調整預案？問題2：由於供應鏈上游的化工原料價格不斷上漲，給力浦公司帶來資源購置上的壓力。公司採購部門預測現有45單位限額的材料A將會出現3單位的資源缺口，但是也不排除通過其他管道籌措來1單位材料A的可能。對於材料A的資源上限的增加或減少，力浦公司應如何進行新的規劃？問題3：經過規劃分析已經知道，材料B在最優生產格局中出現了12.5單位的剩餘，那麼應如何重新制訂限額，做好節約工作？問題4：最壞的可能是公司停止生产，把各種原材料清倉變賣。但是应如何在原材料市场上对A、B和C三種資源進行報價，以使得公司在直接出售原材料的清算業務中損失最小？問題5：如果企業打算通過增加原材料投入擴大生產規模，面對資源市場上的A、B和C三種材料的市價，力浦公司應如何做出經濟合理的決策？2.9靈敏度分析的應用舉例例2.3力浦公司的線性規劃模型和電子錶格模型。2.9靈敏度分析的應用舉例力浦公司的靈敏度分析（問題1、問題2和問題3）力浦公司的“敏感性報告”2.9靈敏度分析的應用舉例問題1：產品甲的单位利润变化对最优解和最优值的影響產品甲的單位利潤將會在3.8～5.2萬元之間波動。根據“敏感性報告”，分段分析。針對產品甲的單位利潤將會在3.8～5.2萬元之間波動的預測，力浦公司應制訂兩套預案：當單位利潤在3.8～5.0萬元之間時，甲、乙兩種產品的產量均為22.5單位；而單位利潤在5.0～5.2萬元之間時，甲、乙兩種產品分別生產35單位和10單位。可以看出，当产品甲的单位利润逐渐增加时，力浦公司一定会理性地将资源配置向产品甲倾斜。2.9靈敏度分析的應用舉例問題2：當資源A的限額（儲備量）在42～46單位變化時對規劃（最優值和最優解）的影响。從“敏感性報告”可知：當资源A的限額（儲備量）在[30,50]範圍內變化時，影子價格有效。如果资源A的限額（儲備量）從45減少到42（出現3單位的缺口），則可以方便地計算出最優值（總利潤）為202.5－3×3.5＝192（萬元）。重新规划求解后，可知新的最优解是（18，24）。同理，如果资源A的限額（儲備量）從45增加到46，則最優值（總利潤）為202.5＋1×3.5＝206（萬元），重新規劃求解後，可知新的最優解是（24，22）。2.9靈敏度分析的應用舉例問題3：對资源B的限額（儲備量）的考察資源B是力浦公司尋求市場收益活動中的一個有趣的“約束”。實質上，該“約束”在當前的最優規劃的生產格局下，並沒有真正起到“約束”的作用。正如實際的規劃結果所表明的，資源B在取得最優值後，尚有12.5單位的剩餘。從“敏感性報告”中可知，资源B的限額（儲備量）允許的變化範圍是：資源B的最小合理儲備量是67.5單位。2.9靈敏度分析的應用舉例問題4和問題5：影子價格与线性规划的对偶問題瞭解即可2.9靈敏度分析的應用舉例問題4和問題5：影子價格與線性規劃的對偶问题方法1：對偶問題的電子錶格模型瞭解即可方法2：“敏感性報告”中的影子價格資源A的影子價格是3.5萬元，資源B的影子價格是0萬元，資源C的影子價格是0.5萬元。本章上机实验1．實驗目的掌握使用Excel軟體進行靈敏度分析的操作方法。2．內容和要求使用Excel軟體求解習題2.3、案例2.1（或其他例子、習題、案例等）。3．操作步驟（1）在Excel中建立電子錶格模型；（2）使用Excel軟體中的“規劃求解”命令求解線性規劃問題並生成“敏感性報告”；（3）結果分析：哪些問題可以直接利用“敏感性報告”中的資訊求解，哪些問題需要重新運行“規劃求解”命令，並對結果提出自己的看法；（4）在Excel檔或Word文檔中撰寫實驗報告，包括線性規劃模型、電子錶格模型、敏感性報告和結果分析等。

第3章線性規劃的建模與應用LinearProgrammingFormulationandApplications3.1資源分配問題資源分配問題是將有限的資源分配到各種活動（決策）中去的線性規劃問題。這一類問題的共性是：在線性規劃模型中，每一个函數約束均為資源约束，並且每一種資源都可以表現為如下形式：使用的资源数量

可用的資源數量對於資源分配问题，有三種數據必須收集：（1）每種資源的可供量（可用的資源數量）；（2）每一種活動所需要的各種資源的数量，对于每一種資源與活動的組合,必須首先估计出单位活動所消耗的資源量；（3）每一種活動對總的績效測度（如總利潤）的單位貢獻（如單位利潤）。3.1資源分配問題例3.1

某公司是商務房地產開發專案的主要投資商。目前，該公司有機會在三個建設專案中投資： 專案1：建造高層辦公樓； 專案2：建造賓館； 專案3：建造購物中心。三个專案都要求投資者在四個不同的時期投資：在當前預付定金，以及一年、二年、三年後分別追加投資。表3-1顯示了四個时期三个项目所需资金。投资者可以按一定的比例进行投资和获得相应比例的收益。辦公樓專案賓館專案購物中心專案現在408090一年後608050兩年後908020三年後108070收益500780600公司目前有2500萬元資金可供投資，預計一年後，又可獲得2000萬元，兩年後獲得另外的2000萬元，三年後還有1500萬元可供投资。那么，该公司要在三個项目中投资多少比例，才能使其投資组合所获得的总收益最大？3.1資源分配問題解：本問題是一個資源分配問題。（1）決策變數設：x1，x2，x3分別為公司在辦公樓專案、賓館專案、購物中心專案中的投資比例（2）目標函數本問題的目標是公司所獲得的總收益最大3.1資源分配問題（3）約束條件本問題的约束条件是公司在各个时期可獲得的资金限制（資源約束）。但需要注意的是：前一时期尚未使用的资金，可以在下一時期使用（為了簡化問題，不考慮資金可獲得的利息）。因此，每一时期的資金限制就表現為累计資金。表3-2顯示了四個時期三個專案所需累計資金和公司累計可用資金。辦公樓專案賓館專案購物中心專案可用資金現在40809025一年後10016014045兩年後19024016065三年後20032023080收益500780600

3.1資源分配問題例3.1的線性規劃模型3.1資源分配問題例3.1的電子錶格模型3.2成本收益平衡問題成本收益平衡問題與資源分配問題的形式完全不同，這種差異主要是由两种問題的管理目标不同造成的。在資源分配問題中，各種資源是受限制的因素（包括財務資源），問題的目標是最有效地利用各種資源，使獲利最大。而對於成本收益平衡問題，管理層採取更為主動的姿態，他們指明哪些收益必須實現（不管如何使用資源），並且要以最低的成本實現所指明的收益。這樣，通過指明每種收益的最低可接受水準，以及實現這些收益的最小成本，管理層期望獲得成本和收益之間的適度平衡。因此，成本收益平衡问题代表了一类線性規劃问题。在这类问题中，通过选择各种活动水平的组合，从而以最小的成本來實現最低的可接受的各種收益水準。3.2成本收益平衡問題成本收益平衡問題的共性是：所有的函数约束均為收益約束，並具有如下形式：

完成的水準

最低的可接受水準如果将收益的含义扩大，可稱以“

”表示的函數约束为“收益約束”。在多数情况下，最低的可接受水平是作为一项政策由管理层制訂的，但有时这一数据也可能是由其他条件决定。成本收益平衡問題需要收集的三種數據：（1）每種收益最低的可接受水準（管理決策）；（2）每種活动对每种收益的贡献（单位活动的贡献）；（3）每種活動的單位成本。3.2成本收益平衡問題排班問題是成本收益平衡問題研究的最重要的應用領域之一。在這一領域中，管理層意識到在向顧客提供令人滿意的服務水準的同時必須進行成本控制，因此，必須尋找成本和收益之間的平衡。於是，研究如何規劃每個輪班人員的排班才能以最小的成本提供令人滿意的服務。3.2成本收益平衡問題例3.2某航空公司正準備增加其中心機場的往來航班，因此需要雇用更多的服務人員。不同時段有最少需求人数，有5種排班方式（連續工作8個小時）。時段排班1排班2排班3排班4排班5最少需求人數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）決策變數確定不同排班的上班人數。設：xi為排班i的上班人數(i＝1,2,

,5)（2）目標函數每天的总成本（工资）最少。（3）約束條件①每个時段的在崗人數必須不少於最低的可接受水準（最少需求人數）②非负3.2成本收益平衡問題例3.2的線性規劃模型3.2成本收益平衡問題例3.2的電子錶格模型3.3網路配送問題通過配送網路，以最小的成本完成貨物的配送，所以稱之為網路配送問題。網路配送問題將在第4章和第5章中重點介紹。與確定資源和收益一樣，在網路配送問題中，必須確定需求並相應地確定需求的約束條件。確定需求約束的形式如下：提供的數量＝需求的數量3.3網路配送問題例3.3

某公司網路配送問題。某公司在兩個工廠生產某種產品。現在收到三個顾客下个月要購買這種产品的订单。这些產品將被单独运送，表3-5顯示了工廠運送一个產品給顧客的成本。该表还给出了每個顧客的訂貨量和每個工廠的产量。现在公司的物流经理要確定每個工廠需運送多少个产品给每个顾客，才能使公司的总运输成本最小？

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

RHS對於特定的資源使用的數量

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

RHS對於特定的收益實現的水準

最低的可接受水準成本收益平衡問題混合問題確定需求約束LHS=RHS對於特定的數量提供的數量=需求的數量網路配送問題混合問題注：LHS=左式（一个SUMPRODUCT函數）

RHS=右式（一般為常數）3.4.2混合問題的應用舉例一：配料问题配料問題的一般提法是：生產某類由各種原料混合而成的產品，如何在滿足規定的品質標準的條件下，使所用原料的總成本最低。例3.4某公司計畫要用Ａ、Ｂ、C三種原料混合調製出三種不同規格的產品甲、乙、丙，產品的規格要求和單價、原料供應量和單價等數據如表3-9所示。問該公司應如何安排生產，才能使總利潤最大？3.4.2混合問題的應用舉例一：配料問題表3-9例3.4配料問題的相關數據原料A原料B原料C產品單價（元/千克）產品甲

50%

35%不限90產品乙

40%

45%不限85產品丙30%50%20%65原料供應量（千克）200150100原料單價（元/千克）6035303.4.2混合問題的應用舉例一：配料問題解：（1）決策變數本問題的難點在於給出的數據是非确定的数值，而且各產品與原料的關係較為複雜。為了方便，設xij為原料i（i=A，B，C）混合到產品j（j=1，2，3分別表示甲、乙、丙）的数量。（2）目標函數 本問題的目標是公司的总利潤最大，總利潤＝产品销售收入－原料成本3.4.2混合問題的應用舉例一：配料問題（3）約束條件

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

設搭配兒童營養午餐時，需要面包x1片、花生酱x2匙、草莓酱x3

匙、饼干x4

塊、牛奶x5

杯、果汁x6

杯。3.4.3混合問題的應用舉例二：營養配餐問題例3.5的電子錶格模型3.4.4混合问题的应用举例三：市场调查问题例3.6

某市場調查公司受某廠的委託，調查消費者對某種新產品的瞭解和反應情況。該廠對市場調查公司提出了以下要求：（1）共對500個家庭進行調查；（2）在受訪家庭中，至少有200個有孩子的家庭，同时至少有200個無孩子的家庭；（3）至少對300個受訪家庭采用问卷式书面调查，對其餘家庭可采用口头调查；（4）在有孩子的受访家庭中，至少对50％的家庭採用問卷式書面調查；（5）在無孩子的受訪家庭中，至少对60％的家庭採用問卷式書面調查。3.4.4混合問題的應用舉例三：市場調查問題對不同家庭採用不同調查方式的費用如表3-14所示。问：市场调查公司应如何进行调查，才能在满足厂方要求的条件下，使得总调查费用最少？表3-14不同家庭采用不同调查方式的费用問卷式書面調查口頭調查有孩子的家庭5030無孩子的家庭40253.4.4混合問題的應用舉例三：市場調查問題解：（1）決策變數根據题意，本问题的决策变量如下：

x11：對有孩子的家庭採用問卷式書面調查的家庭數

x12：對有孩子的家庭採用口頭調查的家庭数

x21：對無孩子的家庭採用問卷式書面調查的家庭数

x22：對無孩子的家庭採用口頭調查的家庭數。（2）目標函數

本問題的目標是市場調查公司的總調查費用最少3.4.4混合問題的應用舉例三：市場調查問題（3）約束條件共對500個家庭進行調查； 至少有200個有孩子的家庭； 至少有200個無孩子的家庭； 至少對300個受訪家庭採用問卷式書面調查； 在有孩子的受訪家庭中，至少對50％的家庭採用問卷式書面調查；在無孩子的受訪家庭中，至少對60％的家庭採用問卷式書面調查；非負。3.4.4混合問題的應用舉例三：市場調查問題例3.6的線性規劃模型3.4.4混合問題的應用舉例三：市場調查問題例3.6的電子錶格模型本章上机实验1．實驗目的

掌握使用Excel軟體求解線性規劃問題的操作方法。2．內容和要求

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

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

（2）使用Excel軟體中的“規劃求解”命令求解線性規劃問題；

（3）結果分析；

（4）在Excel檔或Word文檔中撰寫實驗報告，包括線性規劃模型、電子錶格模型和結果分析等。

運輸問題和指派問題TheTransportationandAssignmentProblems4.1運輸問題的基本概念運輸問題最初起源于在日常生活中人們把某些物品或人們自身從一些地方轉移到另一些地方，要求所採用的运输路线或運輸方案是最經濟或成本最低的，這就成為了一個運籌學問題。隨著經濟的不斷發展，現代物流业的蓬勃發展，如何充分利用時間、資訊、倉儲、配送和聯運體系創造更多的價值，向運籌學提出了更高的挑戰。要求科學地組織貨源、運輸和配送，使得運輸問題變得日益複雜，但是其基本思想仍然是实现现有资源的最优化配置。4.1運輸問題的基本概念一般的運輸問題就是解決如何把某種產品從若干個產地調運到若干個銷地，在每個產地的供應量和每個銷地的需求量以及各地之间的運輸单价已知的前提下，确定一個使得总运输成本最小的方案。平衡運輸問題的條件如下：（1）明確出发地（產地）、目的地（銷地）、供應量（產量）、需求量（銷量）和單位運輸成本。（2）需求假設：每一個出發地（產地）都有一个固定的供應量，所有的供應量都必須配送到目的地（銷地）。与之类似，每一个目的地（銷地）都有一個固定的需求量，整個需求量都必須由出發（產地）地滿足。即“總供應量＝总需求量”。（3）成本假設：從任何一個出發地（產地）到任何一個目的地（銷地）的货物运输成本與所运送的货物数量成线性比例关系，因此，貨物運輸成本就等于单位运输成本乘以所运送的货物数量（目标函数是线性的）。4.1運輸問題的基本概念產銷平衡運輸問題的數學模型：設从產地Ai運往销地Bj的物資數量为xij（i=1,2,⋯,m;j=1,2,⋯,n)

4.1運輸問題的基本概念例4.1某公司有三個加工厂（A1、A2和A3）生產某種產品，每日的产量分别为：7噸、4噸、9噸；該公司把這些產品分別運往四個销售点（B1、B2、B3和B4），各销售点每日的銷量分别为：3噸、6噸、5噸、6噸；从三个加工厂（产地）到四个销售点（销地）的單位產品運價如表4-2所示。問該公司應如何调运产品，才能在满足四个销售点的需求量的前提下，使总运费最少？

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

某公司決定使用三個有生產餘力的工廠進行四種新產品的生產。每單位產品需要等量的工作，所以工廠的有效生產能力以每天生產的任意種產品的數量來衡量（見表4-7的最右列）。而每種產品每天有一定的需求量（見表4-7的最後一行）。除了工廠2不能生產產品3以外，每個工廠都可以生產這些产品。然而，每种产品在不同工厂中的单位成本是有差异的（如表4-7所示）。現在需要決定的是：在哪個工廠生產哪種產品，可使總成本最小。表4-7三個工廠生產四種新產品的有关数据單位成本生產能力產品1產品2產品3產品4工廠24029－2375工廠33730272145需求量203030404.3運輸問題的變形解：把“指定工厂生产產品問題”看作“運輸問題”。本問題中，工厂2不能生產產品3，這樣可以增加約束條件x23＝0

；並且，總供应量（75+75+45=195）>總需求量（20+30+30+40=120）。其數學模型如下：設xij為工廠i生產產品j的數量4.3運輸問題的變形例4.3的電子錶格模型產品4分在2個工廠（工廠2和工廠3）生產4.3運輸問題的變形例4.4需求量存在最小需求量和最大需求量（需求量可在一定范围内变化）的问题。某公司在三個工廠中專門生產一種產品。在未來的四個月中，四个处于国内不同区域的潜在顾客（批发商）很可能有大量訂購。顾客1是公司最好的顾客，所以他的訂单要全部滿足；顾客2和顾客3也是公司很重要的顾客，所以营销经理認為至少要滿足他們訂單的1/3；對於顧客4，行銷經理認為並不需要特殊考虑。由于运输成本上的差异，销售一个产品得到的利潤也不同，利潤很大程度上取决于哪个工厂供应哪个顾客（见表4-8）。问應向每一個顧客供應多少產品，才能使公司的總利潤最大？表4-8三個工廠供應四個顧客的相关数据單位利潤（元）產量顧客1顧客2顧客3顧客4工廠1554246538000工廠2371832485000工廠3295951357000最少供應量7000300020000要求訂購量70009000600080004.3運輸問題的變形解：該問題要求滿足不同顧客的需求（订购量），解決辦法：实际供應量

最少供應量實際供应量

要求訂購量

目標是总利润最大，而不是总成本最小。其數學模型如下：設xij為工廠i供應顧客j的產品數量4.3運輸問題的變形例4.4的電子錶格模型4.4運輸問題的應用舉例例4.5（瞭解即可）

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

A1A2A3年產原料（萬噸）加工費（千元/萬噸）A10150100305.5A21500200264A31002000243成品需求量（萬噸）7130

4.4運輸問題的應用舉例解：該问题包含兩個運輸問題，一個是原料的運輸問題，另一個是成品的運輸問題。還有將原料製成成品的問題，所以，總費用＝原料運費＋成品運費＋加工費。例4.6的線性規劃模型4.4運輸問題的應用舉例例4.6的電子錶格模型4.5指派問題的基本概念在生活中經常會遇到這樣的問題：某單位需完成n項任務，恰好有n個人可以承擔這些任務。由於每個人的專長不同，各人完成的任務不同，所需的時間（或效率）也不同。於是產生應指派哪個人去完成哪項任務，使完成n項任務所需的總時間最短（或總效率最高）。這類問題稱為指派問題（assignmentproblem）或分派問題。平衡指派問題的假设：（1）人的數量和任务的數量相等；（2）每個人只能完成一项任務；（3）每项任务只能由一个人來完成；（4）每個人和每项任务的組合都會有一個相關的成本（单位成本）；（5）目標是要確定如何指派才能使總成本最小。4.5指派問題的基本概念設xij為是否指派第i個人去完成第j項任務，目標函數系数cij為第i個人完成第j項任務所需要的單位成本。平衡指派問題的线性规划模型如下：4.5指派問題的基本概念需要說明的是：指派問題實際上是一種特殊的運輸問題。其中出發地是“人”，目的地是“任务”。只不过，每個出发地的供应量都为1（因為每個人都要完成一项任务），每个目的地的需求量也都為1（因為每项任务都要完成）。由於运输问题有“整數解性質”，因此，指派問題沒有必要加上所有決策變數都是0-1變數的約束條件。指派问题是一种特殊的线性规划问题，有一種簡便的求解方法：匈牙利方法（HungarianMethod），但Excel的“規劃求解”還是采用“單純形法”來求解。4.5指派問題的基本概念例4.7

某公司的行銷經理將要主持召開一年一度的由行銷區域經理以及銷售人員參加的銷售協商會議。為了更好地安排這次會議，他安排小張、小王、小李、小劉四個人，每個人負責完成一项任务：A、B、C和D。由於每個人完成每項任務的時間和工資不同。問公司應指派何人去完成何任務，才能使總成本最少？完成每項任務的時間（小時）每小時工資（元）任務A任務B任務C任務D小張3541274014小王4745325112小李3956364313小劉32512546154.5指派問題的基本概念解：

該問題是一個典型的平衡指派問題。單位成本為每個人完成每項任務的总工资；目標是要確定哪個人去完成哪项任务，才能使總成本最少；供應量為1表示每個人都只能完成一項任務；需求量为1表示每項任務也只能由一個人来完成；總人數（4人）和總任務數（4項）相等4.5指派問題的基本概念例4.7的線性規劃模型如下：设xij為是否指派人员i去完成任務j

4.5指派問題的基本概念例4.7的電子錶格模型4.5指派問題的基本概念例4.7的最優指派方案網路圖小李小劉小張BCAD人指派任務小王4.6指派問題的變形經常會遇到指派問題的變形，之所以稱它們為變形，是因為它們都不滿足平衡指派問題所有假设中的一個或者多個。一般考虑下面的一些特征：（1）某人不能完成某項任務（相應的xij＝0）;（2）每個人只能完成一项任务，但是任務數比人数多(人少事多);（3）每項任务只由一个人完成，但是人數比任務數多（人多事少）；（4）某人可以同時被指派多個任務（一人可做多事）；（5）某事需要由多人共同完成（一事需多人做）；（6）目標是與指派有關的總利潤最大而不是總成本最小；（7）實際需要完成的任务數不超過總人數也不超過總任務數。4.6指派問題的變形例4.8

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

該問題可視為指派工厂生产产品问题，工廠可以看作指派問題中的人，產品則可以看作需要完成的任务。

由於有四種產品和三個工廠，所以就需要有一個工廠生產兩種新產品，只有工廠1和工廠2有生產兩種產品的能力，這是因為工廠1和工