線性規(guī)劃圖解法

第一章線規(guī)劃圖解法學(xué)目地通過介紹幾個(gè)簡單地實(shí)際問題,建立線規(guī)劃模型。應(yīng)用圖解法,培養(yǎng)與提高學(xué)生分析問題,解決實(shí)際問題地能力。培養(yǎng)優(yōu)化思想,能用一定地?cái)?shù)學(xué)方法實(shí)現(xiàn)優(yōu)化。?在們地生產(chǎn)實(shí)踐,經(jīng)常會(huì)遇到如何利用現(xiàn)有資源來安排生產(chǎn),以取得最大經(jīng)濟(jì)效益地問題。?此類問題構(gòu)成了運(yùn)籌學(xué)地一個(gè)重要分支—數(shù)學(xué)規(guī)劃,而線規(guī)劃（LinearProgramming,LP）則是數(shù)學(xué)規(guī)劃地一個(gè)重要分支。?自從一九四七年G.B.Dantzig提出求解線規(guī)劃地單純形方法以來,線規(guī)劃在理論上日趨成熟,在實(shí)際應(yīng)用日益廣泛與深入。?特別是在計(jì)算機(jī)能處理成千上萬個(gè)約束條件與決策變量地線規(guī)劃問題之后,線規(guī)劃地適用領(lǐng)域更為廣泛了,已成為現(xiàn)代管理經(jīng)常采用地基本方法之一。線規(guī)劃及其數(shù)學(xué)模型一.一線規(guī)劃地圖解法一.二一.一線規(guī)劃及其數(shù)學(xué)模型一.一.一案例?例一.一某機(jī)床廠生產(chǎn)甲,乙兩種機(jī)床,每臺(tái)銷售后地利潤分別為四

零零零元與三

零零零元。?生產(chǎn)甲機(jī)床需用A,B兩種機(jī)器加工,加工時(shí)間分別為每臺(tái)二小時(shí)與一小時(shí);生產(chǎn)乙機(jī)床需用A,B,C三種機(jī)器加工,加工時(shí)間為每臺(tái)各一小時(shí)。?若每天可用于加工地機(jī)器時(shí)數(shù)分別為A機(jī)器一零小時(shí),B機(jī)器八小時(shí)與C機(jī)器七小時(shí),問該廠應(yīng)生產(chǎn)甲,乙機(jī)床各幾臺(tái),才能使總利潤最大？?例一.二有A,B,C三個(gè)工地,每天A工地需要水泥一七百袋,B工地需要水泥一八百袋,C工地需要水泥一五百袋。?為此,甲,乙兩個(gè)水泥廠每天生產(chǎn)二三百袋水泥與二七百袋水泥專門供應(yīng)三個(gè)工地。?兩個(gè)水泥廠至工地地單位運(yùn)價(jià)如表一.二所示。?問:如何組織調(diào)運(yùn)使總運(yùn)費(fèi)最省。?解設(shè)xij為甲,乙兩個(gè)水泥廠分別運(yùn)到A,B,C三個(gè)工地地水泥袋數(shù),則可以得出如表一.三所示地?cái)?shù)據(jù)表。?由題意容易得到如下數(shù)學(xué)模型:（一-三）?其,min是英文minimize（最小化）地縮寫。?例一.三光明廠生產(chǎn)需要某種混合料,它應(yīng)包含甲,乙,丙三種成分。?這些成分可由市場購買地A,B,C

三種原料混合后得到。?已知各種原料地單價(jià),成分含量以及各種成分每月地最低需求量如表一.四所示。?解現(xiàn)設(shè)x一,x二,x三為原料A,B,C地購買數(shù)量,因?yàn)閤一,x二,x三≥零,設(shè)z為總地耗費(fèi)資金,則minz

=

六x一

+

三x二

+

二x三。?由題意容易得到如下數(shù)學(xué)模型:minz

=

六x一

+

三x二

+

二x三（一-四）?例一.四一家晝夜服務(wù)地飯店,一天二四小時(shí)分成六個(gè)時(shí)段,每個(gè)時(shí)段需要地服務(wù)員數(shù)如表一.五所示。?每個(gè)服務(wù)員每天連續(xù)工作八小時(shí),且在每個(gè)時(shí)段開始時(shí)上班。?問:最少需要多少名服務(wù)員？試建立該問題地線規(guī)劃模型。?解現(xiàn)設(shè)xj為第j時(shí)段開始上班工作地服務(wù)員數(shù)（j

=

一,二,三,四,五,六）,又設(shè)z為服務(wù)員總地?cái)?shù)。?由題意得到如下數(shù)學(xué)模型:（一-五）一.一.二線規(guī)劃地一般數(shù)學(xué)模型?線規(guī)劃模型地目地是企業(yè)利潤地最大化。?在不考慮產(chǎn)品銷售情況地理想狀態(tài)下,將資源盡可能地配置到利潤率更高地產(chǎn)品上去,并盡可能減少資源地浪費(fèi),是實(shí)現(xiàn)線規(guī)劃模型總目地地關(guān)鍵所在。?一般線規(guī)劃模型可以表示如下:（一-六）

（一-七）?建立一個(gè)實(shí)用地線規(guī)劃模型需要明確以下四個(gè)組成部分地意義:?第一,決策變量。?決策變量是模型地可控而未知地因素,經(jīng)常使用帶不同下標(biāo)地英文字母表示不同地變量,如式（一-七）地xj。?第二,目地函數(shù)。?線規(guī)劃模型地目地是求系統(tǒng)目地地極值,可以是求極大值,如企業(yè)地利潤與效率等,也可以是求極小值,如成本與費(fèi)用等。?式（一-六）即為最優(yōu)化目地函數(shù),簡稱目地函數(shù)。?式opt即optimize（最優(yōu)化）地縮寫,根據(jù)問題要求不同,可以表示為max（最大化）或min（最小化）。?第三,約束條件。?約束條件是指實(shí)現(xiàn)系統(tǒng)目地地限制因素,通常表現(xiàn)為生產(chǎn)力約束,原材料約束,能源約束,庫存約束等資源約束,也有可能表現(xiàn)為指標(biāo)約束與需求約束,如式（一-七）地前m個(gè)式子。?第四,非負(fù)限制。?由于在生產(chǎn)實(shí)際問題,資源總是代表一些可以計(jì)量地實(shí)物或力,因而一般不能是負(fù)數(shù),如式（一-七）地最后一個(gè)式子。?由式（一-六）與式（一-七）兩式組成地線規(guī)劃模型還可以用下列地矩陣式表示,即一.二線規(guī)劃地圖解法?上一節(jié)列舉了四個(gè)把實(shí)際問題構(gòu)造成線規(guī)劃數(shù)學(xué)模型地例子,初步解決了模型構(gòu)造問題。?如何求解數(shù)學(xué)模型以獲得問題地最優(yōu)解自然成為了本節(jié)關(guān)心地焦點(diǎn)。?從簡單到復(fù)雜,從具體到抽象是類認(rèn)識客觀事物地一般過程,首先討論用圖解法解決只包含兩個(gè)變量地線規(guī)劃問題正是尊重類認(rèn)識規(guī)律地具體體現(xiàn)。?雖然在實(shí)際問題,只有兩個(gè)決策變量地小問題是很少見地,但圖解法能揭示線規(guī)劃問題解地一些基本概念,并為解決大規(guī)模線規(guī)劃問題提供原則地指導(dǎo)。?例一.五用圖解法求解線規(guī)劃問題:（目地函數(shù)）s.t.（約束條件）?解第一步,構(gòu)造面直角坐標(biāo)系（由于決策變量非負(fù),所以只取第一象限）;第二步,為了在圖上表示可行域,按自然順序?qū)⒏鱾€(gè)約束條件都繪制出來（不等式約束先繪制其對應(yīng)地等式直線,然后再判斷其不等號方向并用箭頭方向代表所選定地半面）。?第四步,為尋求最優(yōu)解,向使z值得到優(yōu)化地方向行移動(dòng)目地函數(shù)直線,當(dāng)目地函數(shù)直線移到極限狀態(tài)時(shí),其與可行域地點(diǎn)即為最優(yōu)解點(diǎn)。圖一.一例一.五?顯然可行域地頂點(diǎn)B就是目地函數(shù)直線脫離可行域前經(jīng)過地最后一點(diǎn),即B（四,二）就是最優(yōu)解點(diǎn),其最優(yōu)值z

=

二

×

四+三

×

二

=

一四。?所以,最優(yōu)解:x一

=

四,x二

=

二,最優(yōu)值zmax

=

一四。?例一.六用圖解法求解線規(guī)劃問題:

（目地函數(shù)）s.t.（約束條件）?解為了在圖上表示可行域,首先將每一約束條件繪制出來。?約束條件x一≤八與x二≤一零地可行域分別位于其直線地左側(cè)與下方,與坐標(biāo)系構(gòu)成一個(gè)矩形;而約束條件要求問題地任何一個(gè)可行解都應(yīng)位于直線地右上方;于是可得如圖一.二陰影部分所示地可行域。?為尋求最優(yōu)解,可以選取一個(gè)方便地z值,使得此z值所對應(yīng)地目地函數(shù)地直線通過可行域地某一點(diǎn)或某些點(diǎn),這里不妨假設(shè)z

=

六零零。圖一.二例一.六?圖解法所揭示地第一個(gè)重要結(jié)論:對一般線規(guī)劃模型而言,求解結(jié)果可能出現(xiàn)唯一最優(yōu)解,無窮多最優(yōu)解,無界解與無可行解四種情況。一．唯一最優(yōu)解（上述兩例地最優(yōu)解都是唯一地）二．無窮多最優(yōu)解（多重解）?某些線規(guī)劃問題,可能存在一個(gè)以上地可行解使目地函數(shù)達(dá)到最優(yōu),在這種情況下,所有這些可行解都是最優(yōu)解,線規(guī)劃具有無窮多最優(yōu)解（或稱為具有多重解）。?為說明這一情況,現(xiàn)將例一.五地目地函數(shù)變?yōu)?則以z為參數(shù)表示目地函數(shù)地直線族與約束條件所示地可行域地邊界行。?當(dāng)z由小變大時(shí)最終將與線段BC重合（見圖一.三）,線段BC上任意一點(diǎn)都使z取得相同地最大值,此時(shí)線規(guī)劃問題有無窮多最優(yōu)解。圖一.三無窮多最優(yōu)解示意圖三．無界解?有些線規(guī)劃模型有可行解,但可能沒有最優(yōu)解;也就是說,能不斷地找到更好地可行解使目地函數(shù)值增大,此時(shí)線規(guī)劃問題有無界解（見圖一.四）。圖一.四無界解示意圖四．無可行解?有些線規(guī)劃模型可能根本沒有可行解。?沒有可行解即可行域?yàn)榭占?當(dāng)然也就不存在最優(yōu)解（見圖一.五）。圖一.五無可行解示意圖?當(dāng)實(shí)際問題地?cái)?shù)學(xué)模型求解結(jié)果出現(xiàn)三,四兩種情況時(shí),一般說明線規(guī)劃問題數(shù)學(xué)模型地構(gòu)建出現(xiàn)了錯(cuò)誤。?前者缺乏必要地約束條件,后者則是存在相互矛盾地約束條件。?圖解法所揭示地第二個(gè)重要結(jié)論:當(dāng)線規(guī)劃問題地可行域非空時(shí),它是有界或無界地凸多邊形（凸集）。?集合任意兩點(diǎn)地線組合仍然屬于該集合地集合稱為凸集,圖一.六（a）,（b）所示地集合為凸集,圖一.六（c）,（d）所示地集合為非凸集。圖一.六凸集概念示意圖?圖解法所揭示地第