線性規(guī)劃作為運(yùn)籌學(xué)的一人重要分支是研究較早理論較PPT課件

1、B1 B2 B3 A1 600 300 400 A2 400 700 300 問每個(gè)產(chǎn)地向每個(gè)銷地各發(fā)貨多少，才干使總的運(yùn)費(fèi)最少？解1在該問題中，所要確定的量是各產(chǎn)地運(yùn)往各銷地的香蕉數(shù)量，即決策變量是運(yùn)輸量。設(shè)Xij(i=1,2; j =1,2,3)分別表示由產(chǎn)地Ai運(yùn)往銷地Bi的數(shù)量。 2在處理問題的過程中，要遭到如下條件限制，即約束條件： 8060232221131211xxxxxx 各銷地運(yùn)進(jìn)的數(shù)量應(yīng)等于其當(dāng)?shù)仡A(yù)測(cè)的銷售量，即405050231322122111xxxxxx 從各產(chǎn)地運(yùn)往各銷地的數(shù)量不能為負(fù)值，即)3 , 2 , 1; 2 , 1(0jixij(3) 該問題的目的是運(yùn)價(jià)最

2、低，所以運(yùn)價(jià)是目的函數(shù)，即xxxxxxS232221121211300700400400300600因此，該問題的數(shù)學(xué)模型為： 終了條件4050508060231322122111232221131211xxxxxxxxxxxx AAAm，21aaam,21BBBn,21。噸，)(,321bbbAiBjCij解 設(shè) 表示由產(chǎn)地 運(yùn)往銷地 的數(shù)是(i=1,，m；j=1,2,，n)那么該問題數(shù)學(xué)模型為： xijAiBj求變量 的一組值，使它們滿足xij),.,2, 1;,.,2, 1(0.212222121121112111211njmixbxxxbxxxbxxxaxxxaxxxijnmnnnmm

3、mmnmmn并使目的函數(shù) 的值最小。 xCxCxCmnmnS.12121111二、消費(fèi)組織與方案問題二、消費(fèi)組織與方案問題 例例2 設(shè)某用設(shè)某用 種原料，消費(fèi)種原料，消費(fèi) 種產(chǎn)品，其中種產(chǎn)品，其中 種種產(chǎn)品每單位需求原粉分別為產(chǎn)品每單位需求原粉分別為 ；而該廠現(xiàn)有原；而該廠現(xiàn)有原料料 ；的數(shù)量分別為；的數(shù)量分別為 各種產(chǎn)品每單位可各種產(chǎn)品每單位可是利潤(rùn)分別為是利潤(rùn)分別為 。在該廠產(chǎn)品全部能銷售情況下，。在該廠產(chǎn)品全部能銷售情況下，應(yīng)如何組織消費(fèi)，才干使該企業(yè)獲得最大？應(yīng)如何組織消費(fèi)，才干使該企業(yè)獲得最大？AAAm,.,21BBBm,.,21BjAAAm,.,21aaamj,.,21BBBbbb

4、nm,.,.,2121CCCn,.,2, 1解 設(shè)消費(fèi)產(chǎn) 中數(shù)量為 ，那么此問題的數(shù)學(xué)模型為：求一組變量 的值，使?jié)M足Bj),.,2 , 1(njxj),.,1(0.22112222212111212111njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn終了條件 .并使目的函數(shù) 的值最大。xCxCxCnnS.2211三、配料問題三、配料問題例 設(shè)有 種原料，配制含有幾種成分 的產(chǎn)品，要求產(chǎn)品中各種成分的含量不低于 ；不高于 ； 種成分在 種原料中的單位含量為， AAm,.,1BBBn,.,21aaan,.,21bbbn,.,21BjAi各種原料的單位價(jià)錢依次為 問如何調(diào)配

5、原料，才干使產(chǎn)品符合要求，又使本錢最低？.,.,21dddm解 設(shè) 表示每單位產(chǎn)品中原料 的運(yùn)用量(即決策變量)， 那么 數(shù)學(xué)模型為：求一組變量的值，使其滿足 xiAi,.,2 , 1mi ),.,1( , 01.212211222221122112211111mixxxxbxCxCxCabxCxCxCabxCxCxCaimnnmnnnnmmmm約束條件 .并使目的函數(shù) 最小。 xdxdmmS.11四四線性規(guī)劃問題數(shù)學(xué)模型的普通方式和規(guī)范方式線性規(guī)劃問題數(shù)學(xué)模型的普通方式和規(guī)范方式 上面我們建立了經(jīng)濟(jì)領(lǐng)域中常見的實(shí)踐問題的數(shù)學(xué)模型，雖然這些實(shí)踐問題本身是多種多樣的，但是它們的數(shù)學(xué)模型卻具有一樣

6、的特征：要確定某些變量(決策變量)的一組值，使得在確定確實(shí)定的約束條件下，目的函數(shù)是獲得最大值或最小值。其中，約束條件是決策變量的線性方程或線性不等式。目的函數(shù)是決策變量的線性函數(shù)。因此，我們把這種規(guī)劃問題稱為線性規(guī)劃問題。同時(shí)，我們可以得到對(duì)于一個(gè)線性規(guī)劃問題，其數(shù)學(xué)模型應(yīng)具有如下方式： 求xCxCxCnnS2211min)max(或 ),.,2 , 1(0),(.)(.)(.xi22221122222221211111212111nibbbxaxaxabbbxaxaxabbbxaxaxamnmnmmnnnn或或，或或，或或 我們稱這種方式的線性規(guī)劃模型為普通方式。其中， 為目的函數(shù)系數(shù)約束

7、方程系數(shù)； 為約束方程常數(shù)項(xiàng)；(i=1,m;j=1,n).Cjbi由此可見，一個(gè)線性規(guī)劃問題問題的數(shù)學(xué)模型，必需含有三個(gè)要素：決策變量、約束條件和目的函數(shù)。 由上面的例子可知，線性規(guī)劃問題的數(shù)學(xué)模型的普通方式很多。目的函數(shù)有求最大值和最小值；約束條件有“，“，“三種情況。這種多樣性給問題的討論帶來很大的不便。為此，我們引見線性規(guī)劃問題的一種一致方式規(guī)范方式。規(guī)定線性規(guī)劃問題的數(shù)學(xué)模型的規(guī)范方式為：xCxCxCnnS.min2211),.,2 , 1(0.22112222222111212111njxbxaxaxabxaxaxabxaxaxaimnmnmmnnnnS.t 線性規(guī)劃問題的規(guī)范13.

8、1也可寫成矩陣方式CXS min0XbAXs.t 其中).,(, 21cccnC ，xxx321.X ， aaaaaaaaamnmmnn.212222111212A ， bbbm21B 對(duì)于線性規(guī)劃問題的普通方式，可以按如下方法化成規(guī)范形：xcxcnnS11maxSSxcxcxcnnS2211min1假設(shè)線性規(guī)劃問題是求目的函數(shù)的最大值，即求，只需令，即可化為求目的函數(shù)的最小值，即求 2假設(shè)某個(gè)約束條件為線性不等式，那么可將其化為線性議程式的方式。 設(shè)第k個(gè)約束條件為： 那么參與一個(gè)新變量，將其約束條件改為：bxaxaxaknkmkk2211bxxaxaxakknnknkk2211這個(gè)所加的變量稱為松弛變量。假設(shè)第 個(gè)約束條件為： bxaxaxalnllln2211l那么參與一個(gè)新變量，將上述約束條件變?yōu)椋篵xxaxaxallnnllln22113假設(shè)對(duì)某變量沒有非負(fù)限制，那么引進(jìn)兩個(gè)非負(fù)變量0, 0 xxjj令令 代入約束條件和目的函數(shù)，可化為全部變量都有非負(fù)限制。xxxjjj 例4 將以下線性規(guī)劃模型化為規(guī)范形xxS2132max為非負(fù)限制