運(yùn)籌學(xué) 線性目標(biāo)規(guī)劃學(xué)習(xí)課件

線性目標(biāo)規(guī)劃OperationsResearch,Autumn2017,C.-J.Chang線性目標(biāo)規(guī)劃的介紹線性規(guī)劃問題存在兩方面的不足不能處理多目標(biāo)的優(yōu)化問題。約束條件過于剛性化，不允許約束條件有絲毫超差。目標(biāo)規(guī)劃是為了解決上述不足，而創(chuàng)建的一類數(shù)學(xué)模型，其主要在分析各類目標(biāo)重要性時(shí)，引入賦予各目標(biāo)優(yōu)先因子和加權(quán)系數(shù)的概念2何謂線性目標(biāo)規(guī)劃某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，已知有關(guān)數(shù)據(jù)見下表。試求獲利最大的生產(chǎn)方案。

這是求獲利最大的單目標(biāo)的規(guī)劃問題，用x1,x2分別表示Ⅰ、Ⅱ產(chǎn)品的產(chǎn)量，其線性規(guī)劃模型表述為：

經(jīng)計(jì)算其最優(yōu)決策方案為：x1*=4,x2*=3,z*=62(元)。3ⅠⅡ擁有量原材料/kg2111設(shè)備生產(chǎn)能力/小時(shí)1210利潤(rùn)/(元/件)810何謂線性目標(biāo)規(guī)劃實(shí)際上，工廠在作決策時(shí)，需要考慮包括市場(chǎng)因素在內(nèi)等一系列條件。例如:根據(jù)市場(chǎng)信息，產(chǎn)品Ⅰ的銷售量有下降的趨勢(shì)，因而希望產(chǎn)品Ⅰ的產(chǎn)量不應(yīng)大于產(chǎn)品Ⅱ。當(dāng)超過計(jì)劃供應(yīng)原材料時(shí)，需用高價(jià)采購，會(huì)使成本大幅度增加。應(yīng)盡可能充分利用設(shè)備臺(tái)時(shí)，但不希望加班。應(yīng)盡可能達(dá)到并超過計(jì)劃利潤(rùn)指標(biāo)：56元。這樣考慮的產(chǎn)品決策，稱為多目標(biāo)決策問題。目標(biāo)規(guī)劃問題是解決這類問題的方法之一。4正負(fù)偏差量設(shè)x1,x2為決策變量，引入正、負(fù)偏差變量d+,d?。正偏差變量d+表示決策值超過目標(biāo)值的部分。負(fù)偏差變量d?表示決策值未達(dá)到目標(biāo)值的部分。因決策值不可能既超過目標(biāo)值同時(shí)又未達(dá)到目標(biāo)值，即恒有d+×d?=0。5絕對(duì)約束和目標(biāo)約束絕對(duì)約束是指必須嚴(yán)格滿足的約束條件，不能滿足這些約束條件的解稱為非可行解，所以它們是硬約束。目標(biāo)約束是目標(biāo)規(guī)劃特有的，可把約束右端項(xiàng)看作要追求的目標(biāo)值。在達(dá)到此目標(biāo)值時(shí)允許發(fā)生正或負(fù)偏差。因此在這些約束中加入正、負(fù)偏差變量，它們是軟約束。線性規(guī)劃問題的目標(biāo)函數(shù)，在給定目標(biāo)值和加入正、負(fù)偏差變量后可變換為目標(biāo)約束。也可根據(jù)問題的需要將絕對(duì)約束變換為目標(biāo)約束。

目標(biāo)函數(shù)

z=8x1+10x2→

8x1+10x2+d1??d1+=56

約束條件 2x1+x2≤11→2x1+x2+d2??d2+=116優(yōu)先因子(優(yōu)先等級(jí))與權(quán)系數(shù)一個(gè)規(guī)劃問題常常有若干目標(biāo)。但決策者在要求達(dá)到這些目標(biāo)時(shí)，會(huì)有主次或輕重緩急的不同，我們可以透過賦予不同優(yōu)先因子來區(qū)別。例如，要求第一位達(dá)到的目標(biāo)賦予優(yōu)先因子P1，次位的目標(biāo)賦予優(yōu)先因子P2,…,并規(guī)定Pk>>Pk+1,k=1,2,…,K。表示Pk比Pk+1有更大的優(yōu)先權(quán)。首先保證P1級(jí)目標(biāo)的實(shí)現(xiàn)，這時(shí)可不考慮次級(jí)目標(biāo)。而P2級(jí)目標(biāo)僅在實(shí)現(xiàn)P1級(jí)目標(biāo)後才考慮；依此類推。若要區(qū)別具有相同優(yōu)先因子的兩個(gè)目標(biāo)的差別，可分別賦予它們不同的權(quán)系數(shù)wj，這些都由決策者按具體情況而定。7目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)(準(zhǔn)則函數(shù))是按各目標(biāo)約束的正、負(fù)偏差變量和賦予的優(yōu)先因子及權(quán)系數(shù)而構(gòu)造的。當(dāng)每一目標(biāo)值確定后，決策者的要求是盡可能縮小和目標(biāo)值的偏差。因此目標(biāo)規(guī)劃的目標(biāo)函數(shù)的形式通常是minz=f(d+,

d?)。其具體形式大致有三種：若要求恰好達(dá)到目標(biāo)值，則應(yīng)要求正、負(fù)偏差變量均盡可能地小，這時(shí)，目標(biāo)函數(shù)的形式為minz=f(d++d?)。若要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，但正偏差變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的形式為minz=f(d+)。若要求超過目標(biāo)值，即超過量不限，但負(fù)偏差變量要盡可能地小，這時(shí)目標(biāo)函數(shù)的形式為minz=f(d?)。8目標(biāo)規(guī)劃的數(shù)學(xué)模型9Ex.線性目標(biāo)規(guī)劃某工廠生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品，相關(guān)數(shù)據(jù)見下表。若在原材料的供應(yīng)受嚴(yán)格限制的基礎(chǔ)下依序考慮下列目標(biāo)，請(qǐng)?jiān)囍⑵淠繕?biāo)規(guī)劃模型：產(chǎn)品Ⅱ的產(chǎn)量不低于產(chǎn)品Ⅰ的產(chǎn)量。充分利用設(shè)備有效臺(tái)時(shí)，不加班。利潤(rùn)額不小于56元。

10ⅠⅡ擁有量原材料/kg2111設(shè)備生產(chǎn)能力/小時(shí)1210利潤(rùn)/(元/件)810絕對(duì)約束目標(biāo)約束(要加偏差變量)產(chǎn)品Ⅱ要較多，正偏差越小越好。充份利用且不加班，正負(fù)偏差皆越小越好。利潤(rùn)不小于56元，負(fù)偏差越小越好。隨堂練習(xí)某市計(jì)劃在下年度購置一批救護(hù)車，已知每輛購置價(jià)為20萬元。救護(hù)車用于所屬A,B兩個(gè)郊區(qū)縣，各分配xA輛和xB輛。A縣救護(hù)站從接到呼叫到出動(dòng)的響應(yīng)時(shí)間為(40?3xA)分鐘；B縣救護(hù)站的響應(yīng)時(shí)間為(50?4xB)分鐘。該市確認(rèn)如下優(yōu)先目標(biāo)，請(qǐng)建立目標(biāo)規(guī)劃模型。第一優(yōu)先級(jí)：用于救護(hù)車的購置費(fèi)不超過400萬元。第二優(yōu)先級(jí)：A縣的響應(yīng)時(shí)間不超過8分鐘。第三優(yōu)先級(jí)：B縣的響應(yīng)時(shí)間不超過8分鐘。11目標(biāo)規(guī)劃的圖解法對(duì)只具有兩個(gè)決策變量的目標(biāo)規(guī)劃數(shù)學(xué)模型，可以用圖解法來分析求解。先在平面直角坐標(biāo)系的第一象限內(nèi)畫出各約束條件。絕對(duì)約束的作圖與線性規(guī)劃相同。目標(biāo)約束則先令di?與di+皆為0，作相應(yīng)的直線，然后在這直線旁標(biāo)上di?與di+。之后根據(jù)目標(biāo)函數(shù)中的優(yōu)先因子來分析求解?？梢詽M足絕對(duì)約束與目標(biāo)約束的解就是目標(biāo)規(guī)劃的最優(yōu)解。若有某些約束得不到滿足，得到的解就稱為滿意解。絕對(duì)約束條件應(yīng)視為目標(biāo)規(guī)劃問題的最優(yōu)先級(jí)；若其不能滿足，則問題不存在可行解。12目標(biāo)規(guī)劃問題的圖解法13線段GD已滿足所有約束條件，故此線段為此目標(biāo)規(guī)劃問題的解。Ex.目標(biāo)規(guī)劃的圖解法某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí)。預(yù)計(jì)市場(chǎng)每周彩色電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利80元；黑白電視機(jī)的銷量是30臺(tái)，每臺(tái)可獲利40元。該廠確定的目標(biāo)如下，試建立本問題的目標(biāo)規(guī)劃模型，并求解黑白和彩色電視機(jī)的產(chǎn)量。第一優(yōu)先級(jí)：充分利用裝配線每周計(jì)劃開動(dòng)40小時(shí)；第二優(yōu)先級(jí)：允許裝配線加班；但加班時(shí)間每周盡量不超過10小時(shí)；第三優(yōu)先級(jí)：裝配電視機(jī)的數(shù)量盡量滿足市場(chǎng)需要。因彩色電視機(jī)的利潤(rùn)高，取其權(quán)系數(shù)為2。14充分利用裝配線，負(fù)偏差越小越好。加班時(shí)間不超過10小時(shí)，正偏差皆越小越好。盡量滿足需求，負(fù)偏差越小越好。

彩電系數(shù)設(shè)為2。Ex.以圖解法求解目標(biāo)規(guī)劃問題15因無公共區(qū)，故無法滿足P3目標(biāo)，只能比較鄰近的兩個(gè)點(diǎn)，找出較適合的滿意解。因?yàn)镋點(diǎn)的目標(biāo)函數(shù)值較優(yōu)，其為滿意解，故每周應(yīng)裝配彩色電視機(jī)24臺(tái)，黑白電視機(jī)26臺(tái)。隨堂練習(xí)請(qǐng)用圖解法解下列的目標(biāo)規(guī)劃：16目標(biāo)規(guī)劃的單純形法目標(biāo)規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)與線性規(guī)劃的數(shù)學(xué)模型結(jié)構(gòu)形式上沒有本質(zhì)的區(qū)別，所以可用單純形法求解。但要根據(jù)目標(biāo)規(guī)劃的特點(diǎn)，作以下規(guī)定：因目標(biāo)規(guī)劃問題的目標(biāo)函數(shù)都是求最小化，故以cj?zj≥0，j=1,2,…,n作為最優(yōu)性判別準(zhǔn)則。(即檢驗(yàn)數(shù)為負(fù)要計(jì)續(xù)算)因非基變量的檢驗(yàn)數(shù)中含有不同等級(jí)的優(yōu)先因子，且P1>>P2>>…>>PK；從每個(gè)檢驗(yàn)數(shù)的整體來看，檢驗(yàn)數(shù)的正、負(fù)取決于優(yōu)先因子較高的系數(shù)。(Ex.首先看P1的系數(shù)來決定正負(fù)；若P1的系數(shù)為0，再由P2的系數(shù)來決定正負(fù)；依此類推。)17目標(biāo)規(guī)劃單純形法的計(jì)算步驟建立初始單純形表，在表中將檢驗(yàn)數(shù)行按優(yōu)先因子個(gè)數(shù)分別列成K行，置k=1，即對(duì)應(yīng)優(yōu)先因子行中的第1行開始計(jì)數(shù)。檢查該行中是否存在負(fù)數(shù)，(僅考慮其對(duì)應(yīng)的前k?1行的系數(shù)是零的部份。)若有負(fù)數(shù)取其中最小者對(duì)應(yīng)的變量為換入變量，轉(zhuǎn)到(3)；若無負(fù)數(shù)，則轉(zhuǎn)到(5)。按最小比值規(guī)則確定換出變量。當(dāng)存在兩個(gè)和兩個(gè)以上相同的最小比值時(shí)，選取具有較高優(yōu)先級(jí)別的變量為換出變量。進(jìn)行基變換運(yùn)算，建立新的計(jì)算表，返回(2)。當(dāng)k=K時(shí)，計(jì)算結(jié)束，表中的解即為滿意解。否則，置k=k+1，返回到(2)。18Ex.目標(biāo)規(guī)劃的單純形法請(qǐng)用單純形解下列的目標(biāo)規(guī)劃19先將數(shù)學(xué)模型轉(zhuǎn)換成標(biāo)準(zhǔn)型建立初始單純形表cjP1P2P2P3θiCBXBbx1x2xsd1?d1+d2?d2+d3?d3+xs11211d1?01-11-1P2d2?10121-1P3d3?568101-1cj-zjP11P2-1-22P3-8-101P1的檢驗(yàn)數(shù)已為正，考慮P2的檢驗(yàn)數(shù)[]11-556/10Ex.目標(biāo)規(guī)劃的單純形法20cjP1P2P2P3θiCBXBbx1x2xsd1?d1+d2?d2+d3?d3+xs63/21-1/21/2d1?53/21-11/2-1/2x251/211/2-1/2P3d3?63-551-1cj-zjP11P211P3-35-51P1與P2的檢驗(yàn)數(shù)已為正，考慮P3的檢驗(yàn)數(shù)[]cjP1P2P2P3θiCBXBbx1x2xsd1?d1+d2?d2+d3?d3+xs312-2-1/21/2d1?21-1-2-3-1/21/2x2414/3-4/3-1/61/6x121-5/3