規(guī)劃實(shí)質(zhì)上屬于決策范疇.ppt

規(guī)劃實(shí)質(zhì)上屬于決策范疇，主要研究在一定約束條件下，如何使目標(biāo)達(dá)到最優(yōu).但是，普通的線(xiàn)性規(guī)劃、非線(xiàn)性規(guī)劃和0-1規(guī)劃都存在如下的問(wèn)題：（1）均是靜態(tài)規(guī)劃，不能反映約束條件隨時(shí)間變化的情況；（2）當(dāng)規(guī)劃模型或約束條件中出現(xiàn)灰數(shù)時(shí)，處理不便；（3）從理論上講定義在凸集上的凸函數(shù)是有解的，而實(shí)際計(jì)算中往往因技巧、技術(shù)問(wèn)題使求解過(guò)程難以進(jìn)行下去.灰色系統(tǒng)的思想和建模方法，可使上述問(wèn)題得到一定程度的解決.本章主要研究灰參數(shù)線(xiàn)性規(guī)劃、灰色0-1規(guī)劃、灰色多目標(biāo)規(guī)劃和灰色非線(xiàn)性規(guī)劃.,10.1灰參數(shù)線(xiàn)性規(guī)劃,定義10.1.1設(shè)均為常數(shù)，為未知變量，稱(chēng)(10.1.1)(10.1.2)為線(xiàn)性規(guī)劃問(wèn)題的一般模型，其中式(10.1.1)稱(chēng)為目標(biāo)函數(shù)，式(10.1.2)稱(chēng)為約束條件。定義10.1.2稱(chēng)為線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形式,定義10.1.3設(shè)，其中,則稱(chēng)為灰參數(shù)線(xiàn)性規(guī)劃(LPGP)問(wèn)題，并稱(chēng)為灰色價(jià)格向量，為灰色消耗矩陣，為灰色資源約束向量，X為決策向量.實(shí)際上，X也是一個(gè)灰向量.,定義10.1.4設(shè)令灰參數(shù)的白化值分別為同時(shí)分別用，表示價(jià)格白化向量、資源約束白化向量和消耗白化矩陣.則稱(chēng)為L(zhǎng)PGP的定位規(guī)劃，稱(chēng)為價(jià)格定位系數(shù)，為資源約束定位系數(shù)，為消耗定位系數(shù).,10.2灰色預(yù)測(cè)型線(xiàn)性規(guī)劃,定義10.2.1對(duì)于定義10.1.3中的灰色線(xiàn)性規(guī)劃問(wèn)題，將其中的，先行白化，設(shè)并根據(jù)的歷史資料建立GM(1,1)模型，求出其在s+k時(shí)的預(yù)值.記稱(chēng)為灰色預(yù)測(cè)型線(xiàn)性規(guī)劃問(wèn)題.,10.3灰色漂移型線(xiàn)性規(guī)劃,一漂移定理灰色漂移型線(xiàn)性規(guī)劃也稱(chēng)為灰參數(shù)線(xiàn)性規(guī)劃，其實(shí)，一個(gè)灰參數(shù)線(xiàn)性規(guī)劃問(wèn)題是由有限個(gè)或無(wú)限個(gè)一般線(xiàn)性規(guī)劃問(wèn)題構(gòu)成的集合.在以下的證明中，我們假定式(10.1.5)中的白化值和白化矩陣保持其非負(fù)性.定理10.3.1對(duì)于LPGP的定位規(guī)劃，當(dāng)價(jià)格定位系數(shù)滿(mǎn)足時(shí)，有,定理10.3.2對(duì)于LPGP的定位規(guī)劃，當(dāng)資源約束定位系數(shù)滿(mǎn)足，時(shí)，有定理10.3.3對(duì)于LPGP的定位規(guī)劃，當(dāng)消耗定位系數(shù)滿(mǎn)足，時(shí)，有定義10.3.1設(shè)對(duì)和有,則稱(chēng)相應(yīng)的定位規(guī)劃為定位規(guī)劃，記為L(zhǎng)P.其最優(yōu)值稱(chēng)為定位最優(yōu)值，記為.定理10.3.4對(duì)于LPGP的定位規(guī)劃，當(dāng)1、時(shí)，2、時(shí)，3、時(shí)，反映了n種產(chǎn)品的綜合價(jià)格水平，反映了m種資源的總的供應(yīng)狀況，則是生產(chǎn)過(guò)程中工藝技術(shù)水平、勞動(dòng)力素質(zhì)和管理水平的集中體現(xiàn).,二、LPGP的滿(mǎn)意解定義10.3.2當(dāng)時(shí)，對(duì)應(yīng)的定位規(guī)劃LP(1,1,0)稱(chēng)為L(zhǎng)PGP的理想模型，其最優(yōu)值記為.定義10.3.3當(dāng)時(shí)，對(duì)應(yīng)的定位規(guī)劃LP(0,0,1)稱(chēng)為L(zhǎng)PGP的臨界模型，其最優(yōu)值記為定義10.3.4當(dāng)時(shí)，對(duì)應(yīng)的定位規(guī)劃稱(chēng)為定位規(guī)劃，記為L(zhǎng)P()，其最優(yōu)值記為.特別地，當(dāng)=0.5時(shí)，對(duì)應(yīng)的定位規(guī)劃LP(0.5)稱(chēng)為均值白化規(guī)劃，通常情況下，對(duì)灰參數(shù)線(xiàn)性規(guī)劃而言，均值白化規(guī)劃最具代表性.定理10.3.5對(duì)任意的0,1時(shí)，有1、2、,定義10.3.5對(duì)于給定的0,1，稱(chēng)+（10.3.1）為L(zhǎng)P()的滿(mǎn)意度.命題10.3.1對(duì)于給定的0,1有定義10.3.6給定灰靶，若D，則稱(chēng)與之對(duì)應(yīng)的定位最優(yōu)解為L(zhǎng)PGP的滿(mǎn)意解.,10.4灰色線(xiàn)性規(guī)劃的準(zhǔn)優(yōu)解,在線(xiàn)性規(guī)劃問(wèn)題的求解過(guò)程中，常常遇到得不出最優(yōu)解的情形，此時(shí)可以考慮采用其他方法去尋求近似的最優(yōu)解。本節(jié)主要研究決策變量交替尋優(yōu)法，其步驟如下：第一步：確定灰色線(xiàn)性規(guī)劃的定位規(guī)劃第二步：按照常規(guī)的線(xiàn)性規(guī)劃方法求解，直到計(jì)算不能繼續(xù)進(jìn)行設(shè)最后一個(gè)可行解為,第三步：以為起點(diǎn)對(duì)固定的，優(yōu)化x1，設(shè)為固定時(shí)的最優(yōu)解，然后以為起點(diǎn)，對(duì)x2優(yōu)化，設(shè)為固定時(shí)的最優(yōu)解，再以為起點(diǎn)對(duì)x3進(jìn)行優(yōu)化,如此等等,直到求出第四步：以為新的起點(diǎn),重復(fù)第三步中的探索，得直到或與充分接近，且對(duì)應(yīng)的目標(biāo)函數(shù)值充分接近為止。,定義10.4.1稱(chēng)交替尋優(yōu)法所得的最終解為灰色線(xiàn)性規(guī)劃的準(zhǔn)優(yōu)解，與之相應(yīng)的目標(biāo)函數(shù)值稱(chēng)為準(zhǔn)優(yōu)值。,10.5灰色0-1規(guī)劃,0-1規(guī)劃中最典型的是分配問(wèn)題.本節(jié)著重討論灰色預(yù)測(cè)型分配問(wèn)題的求解.定義10.5.1將n項(xiàng)任務(wù)分配給m個(gè)承擔(dān)者，約定每個(gè)承擔(dān)者只能完成一項(xiàng)任務(wù)，當(dāng)n=m時(shí)，稱(chēng)此類(lèi)分配問(wèn)題為平衡分配問(wèn)題.定義10.5.2在平衡分配問(wèn)題中，令設(shè)為第j個(gè)承擔(dān)者完成第i項(xiàng)任務(wù)所需費(fèi)用，i,j=1,2,n，則稱(chēng),為分配問(wèn)題的數(shù)學(xué)模型.其中約束條件表示一項(xiàng)任務(wù)僅指派一位承擔(dān)者，而約束條件則表示每個(gè)承擔(dān)者只完成一項(xiàng)任務(wù).定義10.5.3稱(chēng)方陣為效率矩陣,定理10.5.1對(duì)效率矩陣C之各行或各列的元素分別加上或減去一個(gè)常數(shù)，新的效率矩陣解得的最優(yōu)分配與從C解得的最優(yōu)分配相同.定義10.5.4當(dāng)效率矩陣中的元素為效率序列的灰色預(yù)測(cè)值或灰色發(fā)展系數(shù)時(shí)，稱(chēng)相應(yīng)的0-1規(guī)劃為灰色0-1規(guī)劃.灰色0-1規(guī)劃的求解步驟如下：第一步：給出效益時(shí)間序列第二步：建立的GM(1,1)模型,設(shè)時(shí)間響應(yīng)式為第三步：寫(xiě)出效益矩陣C=(cij),可令，也可令第四步：求第五步：令，于是灰色0-1規(guī)劃模型為第六步：變換效率矩陣,在效率矩陣之各行各列中分別減去其最小元，使得每行每列至少有一個(gè)零元素.若不同行、不同列的零元素個(gè)數(shù)等于效率矩陣的階數(shù)n，則停止變換；否則反復(fù)進(jìn)行上述變換，直到不同行、不同列的零元素個(gè)數(shù)等于效率矩陣的階數(shù)n為止.第七步：對(duì)不同行、不同列的n個(gè)零元素加上“（）”，并稱(chēng)之為獨(dú)立零，令則即為所求的最優(yōu)解.,10.6灰色多目標(biāo)規(guī)劃,一般灰色線(xiàn)性規(guī)劃模型能解決資源合理利用與調(diào)配問(wèn)題，但也有局限性，一是目標(biāo)較單一；二是求解困難，一定要形成可行解域，才能得到灰色線(xiàn)性規(guī)劃解.如果目標(biāo)函數(shù)與約束條件有矛盾，不能形成可行解域時(shí)，灰色線(xiàn)性規(guī)劃就顯得無(wú)能為力了，這就使一些具體問(wèn)題得不到滿(mǎn)意的結(jié)果.灰色多目標(biāo)規(guī)劃就是針對(duì)灰色線(xiàn)性規(guī)劃存在的問(wèn)題而發(fā)展起來(lái)的.灰色多目標(biāo)規(guī)劃以灰色線(xiàn)性規(guī)劃為基礎(chǔ)，是灰色線(xiàn)性規(guī)劃的延伸和發(fā)展.灰色多目標(biāo)規(guī)劃的顯著特征是允許有序解.簡(jiǎn)單地說(shuō)，決策者雖不能精確地決定目標(biāo)或子目標(biāo)的數(shù)值或邊際效用，但是能給出每一個(gè)子目標(biāo)規(guī)劃的一個(gè)上限和下限，供決策者選定.,定義10.6.1設(shè)滿(mǎn)足稱(chēng)為目標(biāo)白化的灰色多目標(biāo)規(guī)劃定義10.6.2設(shè),滿(mǎn)足稱(chēng)為約束白化的灰色多目標(biāo)規(guī)劃.定義10.6.3設(shè)滿(mǎn)足其中,皆為區(qū)間灰數(shù)，稱(chēng)為灰色多目標(biāo)規(guī)劃問(wèn)題.灰色多目標(biāo)規(guī)劃突出之處在于它解決了約束白化的多目標(biāo)規(guī)劃問(wèn)題.它不是單純地提出某些折中解或滿(mǎn)意解，而是為決策者更加清楚地展現(xiàn)未來(lái)可能發(fā)生的多種情形，以及不同情形下的對(duì)策.,10.7灰色非線(xiàn)性規(guī)劃,定義10.7.1設(shè)為決策向量，為灰參數(shù)集，則稱(chēng)(10.7.1)為灰色無(wú)約束非線(xiàn)性規(guī)劃問(wèn)題，其中為灰色價(jià)格或消耗泛函.定義10.7.2白化中的灰元,稱(chēng)所得規(guī)劃問(wèn)題為的白化規(guī)劃，記為.定義10.7.3設(shè)f(X)為可微函數(shù)，則稱(chēng)梯度向量grad（10.7.2）的解為f(X)的駐點(diǎn).定理10.7.1設(shè)f(X)二階可微，海賽(Hesse)矩陣,若X0為f(X)的駐點(diǎn)，則當(dāng)1、H(X0)為正定矩陣時(shí)，X0為極小值點(diǎn)；2、H(X0)為負(fù)定矩陣時(shí)，X0為極大值點(diǎn)；3、H(X0)為半正定矩陣時(shí)，若存在X0的鄰域，使對(duì)，H(X)為半正定矩陣，則X0為極小值點(diǎn)；4、H(X0)為半負(fù)定矩陣時(shí)，若存在X0的鄰域，使對(duì)，H(X)為半負(fù)定矩陣，則X0為極大值點(diǎn)；5、H(X0)為非定矩陣時(shí)，X0不是f(X)的極值點(diǎn)；,定義10.7.4設(shè)為決策向量，,(j=1,2,m；i=1,2,s)皆為灰參數(shù)集，則稱(chēng)為灰色約束非線(xiàn)性規(guī)劃問(wèn)題，其中為灰色消耗泛函,，為灰色約束泛函.,10.8灰色動(dòng)態(tài)規(guī)劃,定義10.8.1設(shè)有區(qū)間灰數(shù)，定義灰數(shù)運(yùn)算滿(mǎn)足（10.8.6）稱(chēng)為灰數(shù)取小運(yùn)算。定義10.8.2設(shè)有一組區(qū)間灰數(shù)，其可能度矩陣的排序向量的最小分量為即，則定義稱(chēng)之為灰數(shù)的取小運(yùn)算。,定義10.8.3設(shè)有區(qū)間灰數(shù)，定義灰數(shù)取大運(yùn)算滿(mǎn)足(10.8.7)定義10.8.4設(shè)有一組區(qū)間灰數(shù)，其可能度矩陣的排序向量的最大分量為即，則定義稱(chēng)之為灰數(shù)的取大運(yùn)算。,10.9應(yīng)用實(shí)例,例10.9.1科技資源配置規(guī)劃在我國(guó)建設(shè)社會(huì)主義現(xiàn)代化強(qiáng)國(guó)的過(guò)程中,隨著市場(chǎng)經(jīng)濟(jì)體制的形成和發(fā)展,科技資源的稀缺性日益突出.如何有效地配置十分有限的科技資源,加快科技事業(yè)的發(fā)展,促進(jìn)社會(huì)、經(jīng)濟(jì)各項(xiàng)事業(yè)的全面振興，已成為擺在科技管理部門(mén)面前的一項(xiàng)重要任務(wù)。本節(jié)運(yùn)用灰參數(shù)線(xiàn)性規(guī)劃(LPGP)模型，對(duì)河南省的科技人才、研究經(jīng)費(fèi)、科研儀器設(shè)備和科技信息資源進(jìn)行優(yōu)化配置，并據(jù)此提出了河南省2000年及2010年的科技資源配置及調(diào)整方案。,例10.9.2灌區(qū)灌溉規(guī)劃2一個(gè)灌區(qū)的灌溉規(guī)劃要涉及許多因素，如灌區(qū)的自然特性、作物品種、灌水和施肥的時(shí)間及數(shù)量、可利用的土地、勞力和機(jī)械以及灌區(qū)的管理水平等.一般而言,這些因素以及他們之間的相互作用與相互影響大都具有不確定性.傳統(tǒng)的確定性規(guī)劃方法和隨機(jī)規(guī)劃方法存在以下不足：(1)對(duì)主觀(guān)因素及客觀(guān)不確定性因素重視不夠；(2)為得到各個(gè)因素的隨機(jī)特性,對(duì)原始信息的要求過(guò)高，許多實(shí)際問(wèn)題，難以獲得符合要求的信息；(3)無(wú)法處理系統(tǒng)中的未確知信息等.事實(shí)上,一個(gè)灌溉系統(tǒng)就是一個(gè)典型的灰色系統(tǒng),因此,可用灰色系統(tǒng)理論建立灌區(qū)