《運籌學(xué)（第3版）》 課件 第1章 線性規(guī)劃

實用運籌學(xué)

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

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

，所以每周總利潤z可表示為：

z=300x1＋500x2

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

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

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

達到最大時x1，x2

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

本章討論的問題均為線性規(guī)劃問題。

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

營養(yǎng)配餐問題。某飼料公司希望用玉米、紅薯兩種原料配制一種混合飼料，兩種原料包含的營養(yǎng)成分和采購成本都不相同，公司管理層希望能夠確定混合飼料中兩種原料的數(shù)量，使得飼料能夠以最小的成本達到一定的營養(yǎng)要求。研究者根據(jù)這一目標收集到的有關(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）目標函數(shù)本問題的目標是混合飼料的總成本最小，即：1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型（3）約束條件本問題共有四個約束條件。①滿足三種營養(yǎng)要求

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

+4x220

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

+6x218

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

+5x216

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

達到最小時x1，x2的取值。1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問題。某物流公司需將三個工廠（工廠1、工廠2、工廠3）生產(chǎn)的一種新產(chǎn)品運送到A、B兩個倉庫，工廠1和工廠2的產(chǎn)品可以通過鐵路運送到倉庫A，數(shù)量不限；工廠3的產(chǎn)品可以通過鐵路運送到倉庫B，同樣，數(shù)量不限。由于鐵路運輸成本較高，公司同時考慮用卡車來運送，但每個工廠要用卡車先將產(chǎn)品運送到配送中心（每個工廠用卡車最多運送60單位），再從配送中心用卡車運送到各個倉庫（每個倉庫最多收到用卡車運送來的貨物90單位）。公司管理層希望以最小的成本來運送所需的貨物。1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問題（續(xù)）。每條線路上的單位運輸成本和各工廠產(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)量工廠單位運輸成本倉庫需求量1.1線性規(guī)劃的基本概念和數(shù)學(xué)模型例1-3物流網(wǎng)絡(luò)配送問題--線性規(guī)劃模型1.1.2線性規(guī)劃的模型結(jié)構(gòu)線性規(guī)劃的一般形式為:

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

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

,n)

為“目標函數(shù)系數(shù)”、“價值系數(shù)”或“費用系數(shù)”；稱bi(i=1,2,

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

,m;j=1,2,

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

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

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

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