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

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

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

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


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



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

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

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

無(wú)界解Unbounded solution)


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