第3部分整數(shù)規(guī)劃

第3部分目標(biāo)規(guī)劃§1目標(biāo)規(guī)劃問題舉例§2目標(biāo)規(guī)劃的圖解法§3復(fù)雜情況下的目標(biāo)規(guī)劃§4加權(quán)目標(biāo)規(guī)劃

1目標(biāo)規(guī)劃問題舉例例1．企業(yè)生產(chǎn)不同企業(yè)的生產(chǎn)目標(biāo)是不同的。多數(shù)企業(yè)追求最大的經(jīng)濟(jì)效益。但隨著環(huán)境問題的日益突出，可持續(xù)發(fā)展已經(jīng)成為全社會(huì)所必須考慮的問題。因此，企業(yè)生產(chǎn)就不能再如以往那樣只考慮企業(yè)利潤，必須承擔(dān)起社會(huì)責(zé)任，要考慮環(huán)境污染、社會(huì)效益、公眾形象等多個(gè)方面。兼顧好這幾者關(guān)系，企業(yè)才可能保持長期的發(fā)展。例2．商務(wù)活動(dòng)企業(yè)在進(jìn)行盈虧平衡預(yù)算時(shí)，不能只集中在一種產(chǎn)品上，因?yàn)槟骋环N產(chǎn)品的投入和產(chǎn)出僅僅是企業(yè)所有投入和產(chǎn)出的一部分。因此，需要用多產(chǎn)品的盈虧分析來解決具有多個(gè)盈虧平衡點(diǎn)的決策問題（多產(chǎn)品的盈虧平衡點(diǎn)往往是不一致的）。2目標(biāo)規(guī)劃問題舉例例3．投資企業(yè)投資時(shí)不僅僅要考慮收益率，還要考慮風(fēng)險(xiǎn)。一般地，風(fēng)險(xiǎn)大的投資其收益率更高。因此，企業(yè)管理者只有在對(duì)收益率和風(fēng)險(xiǎn)承受水平有明確的期望值時(shí)，才能得到滿意的決策。例4．裁員同樣的，企業(yè)裁員時(shí)要考慮很多可能彼此矛盾的因素。裁員的首要目的是壓縮人員開支，但在人人自危的同時(shí)員工的忠誠度就很難保證，此外，員工的心理壓力、工作壓力等都會(huì)增加，可能產(chǎn)生負(fù)面影響。例5．營銷營銷方案的策劃和執(zhí)行存在多個(gè)目標(biāo)。既希望能達(dá)到立竿見影的效果，又希望營銷的成本控制在某一個(gè)范圍內(nèi)。此外，營銷活動(dòng)的深入程度也決定了營銷效果的好壞和持續(xù)時(shí)間。

3

例6．一位投資商有一筆資金準(zhǔn)備購買股票。資金總額為90000元，目前可選的股票有A和B兩種（可以同時(shí)投資于兩種股票）。其價(jià)格以及年收益率和風(fēng)險(xiǎn)系數(shù)如表1：從上表可知，A股票的收益率為（3／20）×100％＝15％，股票B的收益率為4／50×100％＝8％，A的收益率比B大，但同時(shí)A的風(fēng)險(xiǎn)也比B大。這也符合高風(fēng)險(xiǎn)高收益的規(guī)律。試求一種投資方案，使得一年的總投資風(fēng)險(xiǎn)不高于700，且投資收益不低于10000元。目標(biāo)規(guī)劃的圖解法股票價(jià)格（元）年收益（元）／年風(fēng)險(xiǎn)系數(shù)A2030.5B5040.24目標(biāo)規(guī)劃的圖解法

顯然，此問題屬于目標(biāo)規(guī)劃問題。它有兩個(gè)目標(biāo)變量：一是限制風(fēng)險(xiǎn)，一是確保收益。在求解之前，應(yīng)首先考慮兩個(gè)目標(biāo)的優(yōu)先權(quán)。假設(shè)第一個(gè)目標(biāo)（即限制風(fēng)險(xiǎn)）的優(yōu)先權(quán)比第二個(gè)目標(biāo)（確保收益）大，這意味著求解過程中必須首先滿足第一個(gè)目標(biāo)，然后在此基礎(chǔ)上再盡量滿足第二個(gè)目標(biāo)。建立模型：設(shè)x1、x2分別表示投資商所購買的A股票和B股票的數(shù)量。首先考慮資金總額的約束：總投資額不能高于90000元。即20x1＋50x2≤90000。5目標(biāo)規(guī)劃的圖解法一、約束條件再來考慮風(fēng)險(xiǎn)約束：總風(fēng)險(xiǎn)不能超過700。投資的總風(fēng)險(xiǎn)為0.5x1＋0.2x2。引入兩個(gè)變量d1+和d1-,建立等式如下：0.5x1+0.2x2=700+d1+-d1-其中，d1+表示總風(fēng)險(xiǎn)高于700的部分，d1-表示總風(fēng)險(xiǎn)少于700的部分，d1+≥0。目標(biāo)規(guī)劃中把d1+、d1-這樣的變量稱為偏差變量。偏差變量的作用是允許約束條件不被精確滿足。6目標(biāo)規(guī)劃的圖解法把等式轉(zhuǎn)換，可得到0.5x1+0.2x2-d1++d1-=700。再來考慮年收入:年收入=3x1+4x2引入變量d2+和d2-，分別表示年收入超過與低于10000的數(shù)量。于是，第2個(gè)目標(biāo)可以表示為3x1+4x2-d2++d2-=10000。

7目標(biāo)規(guī)劃的圖解法二、有優(yōu)先權(quán)的目標(biāo)函數(shù)本問題中第一個(gè)目標(biāo)的優(yōu)先權(quán)比第二個(gè)目標(biāo)大。即最重要的目標(biāo)是滿足風(fēng)險(xiǎn)不超過700。分配給第一個(gè)目標(biāo)較高的優(yōu)先權(quán)P1,分配給第二個(gè)目標(biāo)較低的優(yōu)先權(quán)P2。針對(duì)每一個(gè)優(yōu)先權(quán)，應(yīng)當(dāng)建立一個(gè)單一目標(biāo)的線性規(guī)劃模型。首先建立具有最高優(yōu)先權(quán)的目標(biāo)的線性規(guī)劃模型，求解；然后再按照優(yōu)先權(quán)逐漸降低的順序分別建立單一目標(biāo)的線性規(guī)劃模型，方法是在原來模型的基礎(chǔ)上修改目標(biāo)函數(shù)，并把原來模型求解所得的目標(biāo)最優(yōu)值作為一個(gè)新的約束條件加入到當(dāng)前模型中，并求解。

8目標(biāo)規(guī)劃的圖解法三、圖解法1．針對(duì)優(yōu)先權(quán)最高的目標(biāo)建立線性規(guī)劃建立線性規(guī)劃模型如下：Mind1+s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-≥09目標(biāo)規(guī)劃的圖解法圖2圖解法步驟2010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=70010目標(biāo)規(guī)劃的圖解法2．針對(duì)優(yōu)先權(quán)次高的目標(biāo)建立線性規(guī)劃優(yōu)先權(quán)次高（P2）的目標(biāo)是總收益超過10000。建立線性規(guī)劃如下：Mind2-s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000d1+＝0x1,x2,d1+,d1-,d2+,d2-≥011目標(biāo)規(guī)劃的圖解法3x1+4x2=10000圖3圖解法步驟3010002000300040005000200030004000x1x220x1＋50x2≤9000010000.5x1+0.2x2=700d1+>0d1+＝0d2-=0d2->0(810,1476)12目標(biāo)規(guī)劃的圖解法目標(biāo)規(guī)劃的這種求解方法可以表述如下：1．確定解的可行區(qū)域。2．對(duì)優(yōu)先權(quán)最高的目標(biāo)求解，如果找不到能滿足該目標(biāo)的解，則尋找最接近該目標(biāo)的解。3．對(duì)優(yōu)先權(quán)次之的目標(biāo)進(jìn)行求解。注意：必須保證優(yōu)先權(quán)高的目標(biāo)不變。4.重復(fù)第3步，直至所有優(yōu)先權(quán)的目標(biāo)求解完。

13目標(biāo)規(guī)劃的圖解法四、目標(biāo)規(guī)劃模型的標(biāo)準(zhǔn)化例6中對(duì)兩個(gè)不同優(yōu)先權(quán)的目標(biāo)單獨(dú)建立線性規(guī)劃進(jìn)行求解。為簡便，把它們用一個(gè)模型來表達(dá)，如下：MinP1（d1+）+P2（d2-）s.t.20x1＋50x2≤900000.5x1+0.2x2-d1++d1-=7003x1+4x2-d2++d2-=10000x1,x2,d1+,d1-,d2+,d2-≥0

14目標(biāo)規(guī)劃的基本概念（1）目標(biāo)規(guī)劃數(shù)學(xué)模型的形式有：線性模型、非線性模型、整數(shù)模型、交互作用模型等（2）一個(gè)目標(biāo)中的兩個(gè)偏差變量di-、di+至少一個(gè)等于零，偏差變量向量的叉積等于零：d－×d＋=0（3）一般目標(biāo)規(guī)劃是將多個(gè)目標(biāo)函數(shù)寫成一個(gè)由偏差變量構(gòu)成的函數(shù)求最小值，按多個(gè)目標(biāo)的重要性，確定優(yōu)先等級(jí)，順序求最小值（4）按決策者的意愿，事先給定所要達(dá)到的目標(biāo)值當(dāng)期望結(jié)果不超過目標(biāo)值時(shí)，目標(biāo)函數(shù)求正偏差變量最小;當(dāng)期望結(jié)果不低于目標(biāo)值時(shí)，目標(biāo)函數(shù)求負(fù)偏差變量最小;當(dāng)期望結(jié)果恰好等于目標(biāo)值時(shí)，目標(biāo)函數(shù)求正負(fù)偏差變量之和最小15目標(biāo)規(guī)劃的基本概念（5）由目標(biāo)構(gòu)成的約束稱為目標(biāo)約束，目標(biāo)約束具有更大的彈性，允許結(jié)果與所制定的目標(biāo)值存在正或負(fù)的偏差，如例4.1中的5個(gè)等式約束；如果決策者要求結(jié)果一定不能有正或負(fù)的偏差，這種約束稱為系統(tǒng)約束，如例4.1的材料約束；（6）目標(biāo)的排序問題。多個(gè)目標(biāo)之間有相互沖突時(shí)，決策者首先必須對(duì)目標(biāo)排序。排序的方法有兩兩比較法、專家評(píng)分等方法，構(gòu)造各目標(biāo)的權(quán)系數(shù)，依據(jù)權(quán)系數(shù)的大小確定目標(biāo)順序；（7）合理的確定目標(biāo)數(shù)。目標(biāo)規(guī)劃的目標(biāo)函數(shù)中包含了多個(gè)目標(biāo)，決策者對(duì)于具有相同重要性的目標(biāo)可以合并為一個(gè)目標(biāo)，如果同一目標(biāo)中還想分出先后次序，可以賦予不同的權(quán)系數(shù)，按系數(shù)大小再排序。16目標(biāo)規(guī)劃的基本概念

式中pk為第k級(jí)優(yōu)先因子,k=1、2、……K；wkl-、wkl+，為分別賦予第l個(gè)目標(biāo)約束的正負(fù)偏差變量的權(quán)系數(shù)；gl為目標(biāo)的預(yù)期目標(biāo)值，l=1,…L．(4.1b)為系統(tǒng)約束,（4.1c）為目標(biāo)約束（8）目標(biāo)規(guī)劃的一般模型．設(shè)xj（j=1,2,…,n）為決策變量1710、目標(biāo)規(guī)劃問題的解------------滿意解目標(biāo)規(guī)劃問題的求解是分級(jí)進(jìn)行的，首先求滿足級(jí)目標(biāo)的解，然后在保證級(jí)目標(biāo)不被破壞的前提下再求滿足級(jí)目標(biāo)的解.以此類推，因此，這樣最后求出的解就不是通常意義下的最優(yōu)解，稱之為滿意解.因?yàn)閷?duì)于這種解來說，前面的目標(biāo)是可以保證實(shí)現(xiàn)或部分實(shí)現(xiàn)的，后面的目標(biāo)就不一定能保證實(shí)現(xiàn)或部分實(shí)現(xiàn)，有些可能就不能實(shí)現(xiàn).滿意解這一概念的提出是對(duì)最優(yōu)化概念的一個(gè)突破.顯然它更切合實(shí)際，更便于運(yùn)用.9、目標(biāo)規(guī)劃的目標(biāo)函數(shù)目標(biāo)規(guī)劃的目標(biāo)函數(shù)，是由各目標(biāo)約束的偏差變量及相應(yīng)的優(yōu)先因子和權(quán)系數(shù)構(gòu)成，當(dāng)一個(gè)目標(biāo)規(guī)劃確定后決策者的要求是盡可能接近各既定目標(biāo)值，也就是偏差變量盡可能小，目標(biāo)函數(shù)一定是極小化的，三種基本表達(dá)式.（1）要求恰好達(dá)到目標(biāo)值.這時(shí)決策值超過或低于目標(biāo)值都是不希望的，因此有：（2）要求不超過目標(biāo)值，即允許達(dá)不到目標(biāo)值，就是正偏差變量要盡可能地小，因此有：

（3）要求不低于目標(biāo)值，即允許超過目標(biāo)值，就是負(fù)偏差變量要盡可能地小，因此有：18復(fù)雜情況下的目標(biāo)規(guī)劃例7．一工藝品廠商手工生產(chǎn)某兩種工藝品A、B，已知生產(chǎn)一件產(chǎn)品A需要耗費(fèi)人力2工時(shí)，生產(chǎn)一件產(chǎn)品B需要耗費(fèi)人力3工時(shí)。A、B產(chǎn)品的單位利潤分別為250元和125元。為了最大效率地利用人力資源，確定生產(chǎn)的首要任務(wù)是保證人員高負(fù)荷生產(chǎn)，要求每周總耗費(fèi)人力資源不能低于600工時(shí)，但也不能超過680工時(shí)的極限；次要任務(wù)是要求每周的利潤超過70000元；在前兩個(gè)任務(wù)的前提下，為了保證庫存需要，要求每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件，因?yàn)锽產(chǎn)品比A產(chǎn)品更重要，不妨假設(shè)B完成最低產(chǎn)量120件的重要性是A完成200件的重要性的1倍。試求如何安排生產(chǎn)？19復(fù)雜情況下的目標(biāo)規(guī)劃解：本問題中有3個(gè)不同優(yōu)先權(quán)的目標(biāo)，不妨用P1、P2、P3表示從高至低的優(yōu)先權(quán)。對(duì)應(yīng)P1有兩個(gè)目標(biāo)：每周總耗費(fèi)人力資源不能低于600工時(shí),也不能超過680工時(shí)；對(duì)應(yīng)P2有一個(gè)目標(biāo)：每周的利潤超過70000元；對(duì)應(yīng)P3有兩個(gè)目標(biāo)：每周產(chǎn)品A和B的產(chǎn)量分別不低于200和120件。20復(fù)雜情況下的目標(biāo)規(guī)劃采用簡化模式，最終得到目標(biāo)線性規(guī)劃如下：MinP1(d1+)+P1(d2－)+P2(d3-)+P3(d4-)+P3(2d5-)s.t.

2x1+3x2-d1++d1-=680對(duì)應(yīng)第1個(gè)目標(biāo)2x1+3x2-d2++d2-=600對(duì)應(yīng)第2個(gè)目標(biāo)250x1+125x2-d3-+d3+＝70000對(duì)應(yīng)第3個(gè)目標(biāo)x1-d4++d4-=200對(duì)應(yīng)第4個(gè)目標(biāo)x2-d5++d5-=120對(duì)應(yīng)第5個(gè)目標(biāo)x1,x2,d1+,d1-,d2+,d2-,d3+,d3-,d4+,d4-,d5+,d5-≥021復(fù)雜情況下的目標(biāo)規(guī)劃使用運(yùn)籌學(xué)軟件求解可得：x1=250；x2=60；d1+=0；d1-=0；d2+=80；d2-=0；d3+=0；d3-=0；d4+=50；d4-=0；d5+=0；d5-=60，目標(biāo)函數(shù)d4-+2d5-=120?？梢?，目標(biāo)1、目標(biāo)3和目標(biāo)4達(dá)到了，但目標(biāo)2、目標(biāo)5都有一些偏差。

22【例8】某企業(yè)集團(tuán)計(jì)劃用1000萬元對(duì)下屬5個(gè)企業(yè)進(jìn)行技術(shù)改造，各企業(yè)單位的投資額已知，考慮2種市場需求變化、現(xiàn)有競爭對(duì)手、替代品的威脅等影響收益的4個(gè)因素，技術(shù)改造完成后預(yù)測單位投資收益率(（單位投資獲得利潤/單位投資額）×100％)如表4－2所示．集團(tuán)制定的目標(biāo)是：（1）希望完成總投資額又不超過預(yù)算；（2）總期望收益率達(dá)到總投資的30%；（3）投資風(fēng)險(xiǎn)盡可能最??；（4）保證企業(yè)5的投資額占20%左右．集團(tuán)應(yīng)如何作出投資決策．復(fù)雜情況下的目標(biāo)規(guī)劃23表4－2復(fù)雜情況下的目標(biāo)規(guī)劃24【解】設(shè)xj（j=1,2,…,5）為集團(tuán)對(duì)第j個(gè)企業(yè)投資的單位數(shù)．

（1）總投資約束：（2）期望利潤率約束：整理得復(fù)雜情況下的目標(biāo)規(guī)劃25

（4）企業(yè)5占20%的投資的目標(biāo)函數(shù)為,約束條件即(3）投資風(fēng)險(xiǎn)約束．投資風(fēng)險(xiǎn)值的大小一般用期望收益率的方差表示，但方差是x的非線性函數(shù)．這里用離差（rij－E(rj)）近似表示風(fēng)險(xiǎn)值，例如，集團(tuán)投資5個(gè)企業(yè)后對(duì)于市場需求變化第一情形的風(fēng)險(xiǎn)是：則4種因素風(fēng)險(xiǎn)最小的目標(biāo)函數(shù)為：，約束條件為復(fù)雜情況下的目標(biāo)規(guī)劃26根據(jù)目標(biāo)重要性依次寫出目標(biāo)函數(shù)，整理后得到投資決策的目標(biāo)規(guī)劃數(shù)學(xué)模型：復(fù)雜情況下的目標(biāo)規(guī)劃27【例1】車間計(jì)劃生產(chǎn)I、II兩種產(chǎn)品，每種產(chǎn)品均需經(jīng)過A、B兩道工序加工．工藝資料如表4－3所示．（1）車間如何安排生產(chǎn)計(jì)劃，使產(chǎn)值和利潤都盡可能高（2）如果認(rèn)為利潤比產(chǎn)值重要，怎樣決策表4－3練習(xí)28【解】設(shè)x1、x2分別為產(chǎn)品甲和產(chǎn)品乙的日產(chǎn)量，得到線性多目標(biāo)規(guī)劃模型：練習(xí)29（1）將模型化為目標(biāo)規(guī)劃問題．首先，通過分別求產(chǎn)值最大和利潤最大的線性規(guī)劃最優(yōu)解．產(chǎn)值最大的最優(yōu)解：X(1)＝（20，40），Z1＝3800利潤最大的最優(yōu)解：X(2)＝（30，30），Z2＝540目標(biāo)確定為產(chǎn)值和利潤盡可能達(dá)到3800和540，得到目標(biāo)規(guī)劃數(shù)學(xué)模型：練習(xí)30．,等價(jià)于（2）給d2-賦予一個(gè)比d1-的系數(shù)大的權(quán)系數(shù),如，約束條件不變.權(quán)系數(shù)的大小依據(jù)重要程度給定，或者根據(jù)同一優(yōu)先級(jí)的偏差變量的關(guān)系給定，例如，當(dāng)利潤d2-減少一個(gè)單位時(shí)，產(chǎn)值d1-減少3個(gè)單位，則賦予d2-權(quán)系數(shù)3，則目標(biāo)函數(shù)為練習(xí)31例2某電視機(jī)廠裝配黑白和彩色兩種電視機(jī)，每裝配一臺(tái)，電視機(jī)需占用裝配線1小時(shí)，裝配線每周計(jì)劃開動(dòng)40小時(shí)，預(yù)計(jì)市場每周彩色電視機(jī)的銷量是24臺(tái)，每臺(tái)可獲利80元，黑白電視機(jī)的銷量是30臺(tái)，每臺(tái)可獲利40元，該廠確定的目標(biāo)為：

P1：充分利用裝配線每周計(jì)劃開動(dòng)40小時(shí)；

P2：允