線性規(guī)劃LP

本章學(xué)習(xí)的目的使學(xué)員掌握線性規(guī)劃問題的一般定義和數(shù)學(xué)模型的特征。掌握兩個變量的線性規(guī)劃問題的幾何作圖求解方法。重點是數(shù)學(xué)模型的建立和兩個變量線性規(guī)劃模型的可行域的特點及最優(yōu)解存在的位置。同時理解最優(yōu)解在極點達(dá)到這一結(jié)果對于一般線性規(guī)劃也成立。熟悉計算機(jī)QM軟件求解LP問題的步驟。
第二章、線性規(guī)劃LP (Linear Programming) 線性規(guī)劃是一種對問題進(jìn)行求解的方法，可以幫組決策者制定決策.1947年丹捷格(G.B.Dantzig)提出一般線性規(guī)劃問題的求解方法——單純形法后，LP在理論上趨向成熟。在世界500家大公司中，有85%使用LP方法。
一、使用線性規(guī)劃方法的典型情況。
生產(chǎn)的組織與計劃問題
運輸問題
合理下料問題
配料問題
布局問題
營銷管理問題
投資組合問題
分派問題

二、線性規(guī)劃問題的提出及數(shù)學(xué)模型
例1 某工廠在計劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時和A、B兩種原材料的消耗以及資源的限制情況，如表1-1所示：
問工廠應(yīng)分別生產(chǎn)多少個甲產(chǎn)品和乙產(chǎn)品才能使工廠獲利最大？
表1-1

例2 M&D公司生產(chǎn)兩種產(chǎn)品A和B，基于對現(xiàn)有的存儲水平和下一個月的市場潛力的分析，M&D公司管理層決定A和B的總產(chǎn)量至少要達(dá)到350千克，此外，公司的一個客戶訂了125千克的A產(chǎn)品必須首先滿足。每千克A、B產(chǎn)品的制造時間分別為2小時和1小時，總工作時間為600小時。每千克A、B產(chǎn)品的原材料成本分別為2$和3$。確定在滿足客戶要求的前提下，成本最小的生產(chǎn)計劃。  

例3 營養(yǎng)問題 某公司飼養(yǎng)試驗用的動物以供出售。已知這些動物的生長對飼料中的三種營養(yǎng)元素特別敏感，分別稱為營養(yǎng)元素A、B、C。已求出這些動物每天至少需要700克營養(yǎng)元素A,30克營養(yǎng)元素B，而營養(yǎng)元素C每天恰好為200克?，F(xiàn)有五種飼料可供選擇，各種飼料的營養(yǎng)元素及單價如下表2-2所示，為了避免過多使用某種飼料，規(guī)定混合飼料中各種飼料的最高含量分別為：50、60、50、70、40克。求滿足動物需要且費用最低的飼料配方。


例4 某晝夜服務(wù)的公交線路每天每個時間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：
假設(shè)司機(jī)和乘務(wù)人員分別在各時間段一經(jīng)上班，就連續(xù)工作八小時。問該公司怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員。
解：設(shè) 表示第 班次時開始上班的司機(jī)和乘務(wù)人員數(shù)， 在第 班工作的人數(shù)應(yīng)包括——第 班才開始上班的人數(shù)和第 -1班次開始上班的還需繼續(xù)工作的人數(shù)。 這樣建立的數(shù)學(xué)模型為：



三、圖解法 對于簡單的線性規(guī)劃問題(只有兩個決策變量的線性規(guī)劃問題),我們通過圖解法可以對它進(jìn)行求解。 我們可以參考教材具體給出求解的方法。圖解法簡單直觀，有助于了解線性規(guī)劃問題求解的基本原理.
圖解法求模型的解 可行解(Feasible Solution)：滿足所有約束條件的解為可行解。 可行域(Feasible region)：可行解所組成的區(qū)域稱為可行域。 圖解法步驟： ·畫出滿足每個約束條件的范圍。 ·確定可行域 ·畫出一條目標(biāo)函數(shù)的直線 ·平移目標(biāo)函數(shù)直線，使其可行域在直線的一側(cè)。 ·確定最優(yōu)解。

松弛變量(Slack Variable)
當(dāng)線性規(guī)劃的所有約束條件都用等式來表達(dá)時，這種形式就稱為標(biāo)準(zhǔn)型。 注釋 在線性規(guī)劃的標(biāo)準(zhǔn)型中，松弛變量的系數(shù)為零，這個零表示未使用的資源，不對目標(biāo)函數(shù)產(chǎn)生任何影響，但在實際中，可以出售未使用的資源，以使公司獲利，從這一角度看，松弛變量就變成了表示公司可以出售多少未使用的資源的決策變量。
極點和最優(yōu)解(Extreme Point and optimal) 對于上述問題現(xiàn)在假設(shè)每生產(chǎn)一單位產(chǎn)品Ⅰ可獲利1元，每生產(chǎn)一單位產(chǎn)品Ⅱ可獲利5元，約束條件不變，顯然約束條件不變，可行域就不變，此時目標(biāo)函數(shù)的改變對最優(yōu)解產(chǎn)生什么影響呢？ 我們?nèi)杂脠D解法進(jìn)行求解
線性規(guī)劃問題的最優(yōu)解一定可以在可行域的一個極點上找到 練習(xí)：找可行域的極點，并通過計算和比較極點所對應(yīng)的目標(biāo)函數(shù)值來求最優(yōu)解。
一個簡單的最小化問題 M&D公司生產(chǎn)兩種產(chǎn)品 ----。
用圖解法進(jìn)行求解 通過作圖法我們找到了最小成本的解為：（250，100）最小成本為800。同時，我們也發(fā)現(xiàn)最優(yōu)解仍然在極點出。
剩余變量(Surplus Variable) 通過對該公司的最優(yōu)解的分析，我們知道最大生產(chǎn)量已經(jīng)達(dá)到，需要的生產(chǎn)時間是600小時，此外，A的產(chǎn)量已達(dá)到其最低要求，事實上，已經(jīng)超過了A的最小限額250-125=125，多生產(chǎn)出來的這一部分產(chǎn)品就稱為剩余。由于剩余不參與目標(biāo)函數(shù)值的計算，因此剩余變量在目標(biāo)函數(shù)中的系數(shù)為零，將該模型引入松弛變量和剩余變量后為：

特殊情況 無窮多最優(yōu)解(Alternative optimal solution)
最優(yōu)解為:A(2,3),B(4,2)。而且在A、B兩點之間的任何點也都是最優(yōu)解，因為線段A、B及其內(nèi)部的點都使得目標(biāo)函數(shù)值最大。對于一個LP問題來講，有無窮多最優(yōu)解是一個好消息，有多種決策變量的組合可供選擇。
無可行解(Infeasibility Solution) 無可行解是指不存在滿足全部約束條件的解。在圖形中，無可行解是指可行域不存在。也就是說，沒有任何一個點能夠同時滿足所有約束條件。 舉例說明這一情況。在2.1中如果我們增加約束條件，生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品至少分別需要3千克。
現(xiàn)有的資源無法生產(chǎn)滿足需要（3，3）的產(chǎn)品，此外，我們可以準(zhǔn)確地告訴管理者要生產(chǎn)(3,3)換需要多少資源

無界解Unbounded solution)


可行域D非空有界：（1）有唯一解、（2）有無窮多最優(yōu)解
從圖解法中可直觀地看到: ※ 當(dāng)線性規(guī)劃問題的可行域非空時,它是有界或無界凸多面體(形). ※若線性規(guī)劃問題存在有界最優(yōu)解,則最優(yōu)解必定可在可行域的某個頂點上取得。
QM軟件求解兩個變量的LP問題的方法。（演示）
Step1
Step2
Step3
Step4
課堂練習(xí) A、用圖解法求解兩個變量的LP問題。 B、用QM軟件求解兩個變量的LP問題。

線性規(guī)劃LP