線性代數(shù)第7章

1、1 1 1 1線性代數(shù)第一章線性代數(shù)第一章 1.1 第七章第七章 線性規(guī)線性規(guī)劃劃2 2 22線性代數(shù)線性代數(shù) 第七章第七章線性規(guī)劃研究的主要問題線性規(guī)劃研究的主要問題 一類是已有一定數(shù)量的資源（人力、物質(zhì)、時(shí)間等），研一類是已有一定數(shù)量的資源（人力、物質(zhì)、時(shí)間等），研究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。究如何充分合理地使用它們，才能使完成的任務(wù)量為最大。 實(shí)際上，上述兩類問題是一個(gè)問題的兩個(gè)不同的方面，實(shí)際上，上述兩類問題是一個(gè)問題的兩個(gè)不同的方面，都是求問題的最優(yōu)解（都是求問題的最優(yōu)解（ maxf 或或 minf ）。）。 另一類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，另一

2、類是當(dāng)一項(xiàng)任務(wù)確定以后，研究如何統(tǒng)籌安排，才能使完成任務(wù)所耗費(fèi)的資源量為最少。才能使完成任務(wù)所耗費(fèi)的資源量為最少。3 3 33線性代數(shù)線性代數(shù) 第七章第七章 1939年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高年，前蘇聯(lián)數(shù)學(xué)家康托洛維奇用線性模型研究提高組織和生產(chǎn)效率問題組織和生產(chǎn)效率問題 1947年，美國(guó)數(shù)學(xué)家丹茨格（年，美國(guó)數(shù)學(xué)家丹茨格（Dantzig）提出求解線性規(guī)）提出求解線性規(guī)劃的單純形法劃的單純形法 1950-1956年，主要研究線性規(guī)劃的對(duì)偶理論年，主要研究線性規(guī)劃的對(duì)偶理論 1958年，發(fā)表整數(shù)規(guī)劃的割平面法年，發(fā)表整數(shù)規(guī)劃的割平面法 1960年，年，Dantzig和和Wolf

3、e研究成功分解算法，奠定了大規(guī)研究成功分解算法，奠定了大規(guī)模線性規(guī)劃問題理論和算法的基礎(chǔ)。模線性規(guī)劃問題理論和算法的基礎(chǔ)。 1979年，年，Khachiyan，1984年，年，Karmarkaa研究成功線性研究成功線性規(guī)劃的多項(xiàng)式算法。規(guī)劃的多項(xiàng)式算法。線性規(guī)劃的發(fā)展線性規(guī)劃的發(fā)展4 4 44線性代數(shù)線性代數(shù) 第七章第七章例例1.1 某廠生產(chǎn)兩種產(chǎn)品，下表給某廠生產(chǎn)兩種產(chǎn)品，下表給出了單位產(chǎn)品所需資源及單位產(chǎn)品出了單位產(chǎn)品所需資源及單位產(chǎn)品利潤(rùn)利潤(rùn) 問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使問：應(yīng)如何安排生產(chǎn)計(jì)劃，才能使 總利潤(rùn)最大？總利潤(rùn)最大？ 7.1 7.1 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型一、問

4、題的提出一、問題的提出解：解：1.決策變量：設(shè)產(chǎn)品決策變量：設(shè)產(chǎn)品I、II的產(chǎn)量分的產(chǎn)量分 別為別為 x1、x22.目標(biāo)函數(shù)：設(shè)總利潤(rùn)為目標(biāo)函數(shù)：設(shè)總利潤(rùn)為z，則有：，則有： max z = 2 x1 + 3 x23.約束條件：約束條件： x1 + 2x2 8 4x1 16 4x2 12 x1， x205 5 55線性代數(shù)線性代數(shù) 第七章第七章例例1.2 某廠生產(chǎn)三種藥物，這些藥某廠生產(chǎn)三種藥物，這些藥物可以從四種不同的原料中提取。物可以從四種不同的原料中提取。下表給出了單位原料可提取的藥物下表給出了單位原料可提取的藥物量量要求：生產(chǎn)要求：生產(chǎn)A種藥物至少種藥物至少160單位；單位；B種藥物恰

5、好種藥物恰好200單位，單位，C種藥物不種藥物不超過超過180單位，且使原料總成本最單位，且使原料總成本最小。小。解：解：1.決策變量：設(shè)四種原料的使用決策變量：設(shè)四種原料的使用 量分別為：量分別為： x1、x2 、x3 、x42.目標(biāo)函數(shù)：設(shè)總成本為目標(biāo)函數(shù)：設(shè)總成本為z，則有：，則有： min z = 5 x1 + 6 x2 + 7 x3 + 8 x43.約束條件：約束條件： x1 + 2x2 + x3 + x4 160 2x1 +4 x3 +2 x4 160 3x1 x2 +x3 +2 x4 180 x1、x2 、x3 、x40 藥物藥物原料原料ABC單位成本單位成本（元噸）（元噸）甲甲

6、1235乙乙2016丙丙1417丁丁12286 6 66線性代數(shù)線性代數(shù) 第七章第七章模型特點(diǎn)模型特點(diǎn)1 都用一組決策變量都用一組決策變量X = (x1,x2,xn)T表示某一方案，且決策變量表示某一方案，且決策變量取值非負(fù)；取值非負(fù)； 滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃滿足以上三個(gè)條件的數(shù)學(xué)模型稱為線性規(guī)劃2 都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量都有一個(gè)要達(dá)到的目標(biāo)，并且目標(biāo)要求可以表示成決策變量的線性函數(shù)；的線性函數(shù)；3 都有一組約束條件，這些約束條件可以用決策變量的線性等都有一組約束條件，這些約束條件可以用決策變量的線性等式或線性不等式或線性不等 式來表示。式來表示。

7、7 7 77線性代數(shù)線性代數(shù) 第七章第七章二二. . 線性規(guī)劃的數(shù)學(xué)模型線性規(guī)劃的數(shù)學(xué)模型一般表示方式一般表示方式nnnxcxcxcxxf 22111),(min(max) 0,),(),(),(.2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxats均為實(shí)常數(shù)均為實(shí)常數(shù)式中的式中的ijijbca,8 8 88線性代數(shù)線性代數(shù) 第七章第七章線性規(guī)劃的標(biāo)準(zhǔn)形有如下四個(gè)特點(diǎn)：線性規(guī)劃的標(biāo)準(zhǔn)形有如下四個(gè)特點(diǎn)： 目標(biāo)最小化、目標(biāo)最小化、 約束為等式、約束為等式、 變量均非負(fù)、變量均非負(fù)、 右端約束常數(shù)非負(fù)。右端約束常數(shù)非負(fù)。 0,),(m

8、in212211222221211121211122111nmnmnmmnnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcxxf標(biāo)準(zhǔn)標(biāo)準(zhǔn)2134, 0 ib9 9 99線性代數(shù)線性代數(shù) 第七章第七章線性規(guī)劃模型的變換線性規(guī)劃模型的變換1 1 極小化目標(biāo)函數(shù)的問題極小化目標(biāo)函數(shù)的問題設(shè)目標(biāo)函數(shù)為設(shè)目標(biāo)函數(shù)為nnxcxcxcfMax 2211nnxcxcxcfMin 2211令令 則可轉(zhuǎn)化為標(biāo)準(zhǔn)形則可轉(zhuǎn)化為標(biāo)準(zhǔn)形ff 2 右端項(xiàng)有負(fù)值的問題右端項(xiàng)有負(fù)值的問題inniiibxaxaxa 2211 在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非在標(biāo)準(zhǔn)形式中，要求右端項(xiàng)必須每一個(gè)分量非

9、負(fù)負(fù)，當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，則把該等式約束兩當(dāng)某一個(gè)右端項(xiàng)系數(shù)為負(fù)時(shí)，則把該等式約束兩端同時(shí)乘以端同時(shí)乘以1 1，得到：，得到：10101010線性代數(shù)線性代數(shù) 第七章第七章3 3約束條件不是等式的問題約束條件不是等式的問題inniiibxaxaxa 2211isnniiibyxaxaxa 2211（1）設(shè)約束條件為：）設(shè)約束條件為：可以引進(jìn)一個(gè)新的變量可以引進(jìn)一個(gè)新的變量 使得：使得：iy顯然，顯然， 也具有非負(fù)約束，即也具有非負(fù)約束，即 0iyiy （2 2）當(dāng)約束條件為：）當(dāng)約束條件為：inniiibxaxaxa 2211 如果原問題中有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)如果原問題中

10、有若干個(gè)非等式約束，則將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量。形式時(shí)，必須對(duì)各個(gè)約束引進(jìn)不同的松弛變量?？梢砸M(jìn)一個(gè)新的變量可以引進(jìn)一個(gè)新的變量 使得：使得：syiinniiibyxaxaxa 2211顯然，顯然， 也具有非負(fù)約束，即也具有非負(fù)約束，即 0sysy為了使約束由不等式成為等式而引進(jìn)的變量為了使約束由不等式成為等式而引進(jìn)的變量 ， 稱為稱為“松弛變量松弛變量”。siyy ,11111111線性代數(shù)線性代數(shù) 第七章第七章 在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量有非負(fù)約束，當(dāng)在標(biāo)準(zhǔn)形式中，必須每一個(gè)變量有非負(fù)約束，當(dāng)某一個(gè)變量某一個(gè)變量 xj 沒有非負(fù)約束時(shí)，令沒有非負(fù)約束時(shí)，令

11、 jjjxxx0,0 jjxx變量無符號(hào)限制的問題變量無符號(hào)限制的問題12121212線性代數(shù)線性代數(shù) 第七章第七章例例1 將將 線性規(guī)劃模型化為標(biāo)準(zhǔn)型。線性規(guī)劃模型化為標(biāo)準(zhǔn)型。 0,12416482.212121xxxxxxts 2132minxxf5432100032minxxxxxf 0,12416482.43215241321xxxxxxxxxxxxts13131313線性代數(shù)線性代數(shù) 第七章第七章 例例2.2.線性規(guī)劃模型化為標(biāo)準(zhǔn)型。線性規(guī)劃模型化為標(biāo)準(zhǔn)型。 0,2004006653004432.0004423)(min:65433216332153321433216543321xx

12、xxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型 0, ,20040065300432.423)(max:213321321321321xxxxxxxxxxxxtsxxxxf不限不限原非標(biāo)準(zhǔn)型原非標(biāo)準(zhǔn)型14141414線性代數(shù)線性代數(shù) 第七章第七章標(biāo)準(zhǔn)標(biāo)準(zhǔn)矩陣式矩陣式 0bA.C)(min xxtsxxfTTmTnTnmnmmnnbbbxxxxcccaaaaaaaaa),(b),(;),(CA212121212222111211 其中，其中，15151515線性代數(shù)線性代數(shù) 第七章第七章三三 線性規(guī)劃模型解的基本概念線性規(guī)劃模型解的基本概念定義定義7.1.0,.),(

13、21稱為可行域稱為可行域有可行解的集合有可行解的集合為該問題的可行解。所為該問題的可行解。所則稱則稱標(biāo)準(zhǔn)形式中的約束條件標(biāo)準(zhǔn)形式中的約束條件若滿足線性規(guī)劃模型的若滿足線性規(guī)劃模型的向量向量DxxbAxtsxxxxTn 定義定義7.2.),()(,優(yōu)優(yōu)解解為為該該線線性性規(guī)規(guī)劃劃問問題題的的最最則則稱稱有有即即上上達(dá)達(dá)到到最最小小值值，在在解解，且且使使目目標(biāo)標(biāo)函函數(shù)數(shù)為為線線性性規(guī)規(guī)劃劃模模型型的的可可行行設(shè)設(shè)xxfxfDxDfx 性質(zhì)性質(zhì)7.1。其其可可行行解解，其其中中仍仍是是解解，則則為為線線性性規(guī)規(guī)劃劃模模型型的的可可行行若若10)1(,2121 xxxxxbbbAxAxxxAAxbA

14、xbAx )1()1()1(,212121 所有所有證明：因?yàn)樽C明：因?yàn)?6161616線性代數(shù)線性代數(shù) 第七章第七章.10)1(,2121為凸集為凸集，則稱集合，則稱集合其中其中有有意意為非空集合，如果對(duì)任為非空集合，如果對(duì)任一般地，設(shè)一般地，設(shè)DDxxDxxD 性質(zhì)性質(zhì)7.2 若線性規(guī)劃模型的可行域非空，則可行域?yàn)橥辜艟€性規(guī)劃模型的可行域非空，則可行域?yàn)橥辜?7171717線性代數(shù)線性代數(shù) 第七章第七章0123451243例例1.求解線性規(guī)劃問題求解線性規(guī)劃問題 )2 , 1(03482.43max212121jxxxxxtsxxfj., 0,. 33:4:82:. 2.,. 1.212

15、31221121域域取交集即為所求的可行取交集即為所求的可行半平面，結(jié)合半平面，結(jié)合確定每個(gè)不等式表示的確定每個(gè)不等式表示的約束畫出約束畫出用等式約束代替不等式用等式約束代替不等式看作平面上的點(diǎn)的坐標(biāo)看作平面上的點(diǎn)的坐標(biāo)把決策變量把決策變量定的可行域定的可行域一。畫出由約束條件確一。畫出由約束條件確 xxxlxlxxlxx., 1 , 04343443.1221坐坐標(biāo)標(biāo)就就是是要要求求的的最最優(yōu)優(yōu)解解因因此此，極極限限位位置置的的點(diǎn)點(diǎn)的的，增增多多的的方方向向如如箭箭頭頭所所指指平平行行線線簇簇在在平平面面上上截截距距的的平平行行線線簇簇，令令為為變變化化時(shí)時(shí)便便產(chǎn)產(chǎn)生生一一簇簇斜斜率率當(dāng)當(dāng)變

16、變形形為為為為此此，將將目目標(biāo)標(biāo)函函數(shù)數(shù)最最大大值值的的可可行行域域中中的的點(diǎn)點(diǎn)最最優(yōu)優(yōu)解解是是使使目目標(biāo)標(biāo)函函數(shù)數(shù)去去從從可可行行域域中中找找出出最最優(yōu)優(yōu)解解二二 ffxfxxxf7.2線性規(guī)劃問題的圖解法線性規(guī)劃問題的圖解法18181818線性代數(shù)線性代數(shù) 第七章第七章 482121xxx極值點(diǎn)滿足方程極值點(diǎn)滿足方程.20min,)2 , 4(.2024 fxfT最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值因此得唯一最優(yōu)解因此得唯一最優(yōu)解），此時(shí)），此時(shí)，求得極值點(diǎn)坐標(biāo)（求得極值點(diǎn)坐標(biāo)（19191919線性代數(shù)線性代數(shù) 第七章第七章 0022.2min21212121xxxxxxtsxxf為無界域。為無界

17、域。可以看到，其可行域可以看到，其可行域域域取交集即為所求的可行取交集即為所求的可行半平面，結(jié)合半平面，結(jié)合確定每個(gè)不等式表示的確定每個(gè)不等式表示的約束畫出約束畫出用等式約束代替不等式用等式約束代替不等式定的可行域定的可行域一。畫出由約束條件確一。畫出由約束條件確., 0,. 22:2:. 1.21212211 xxxxlxxl01234512431x2x., 1 , 0212212.1221坐標(biāo)就是要求的最優(yōu)解坐標(biāo)就是要求的最優(yōu)解因此，極限位置的點(diǎn)的因此，極限位置的點(diǎn)的，減少的方向如箭頭所指減少的方向如箭頭所指平行線簇在平面上截距平行線簇在平面上截距的平行線簇，令的平行線簇，令為為變化時(shí)便產(chǎn)

18、生一簇斜率變化時(shí)便產(chǎn)生一簇斜率當(dāng)當(dāng)變形為變形為為此，將目標(biāo)函數(shù)為此，將目標(biāo)函數(shù)從可行域中找出最優(yōu)解從可行域中找出最優(yōu)解二二 fffxxxxf 22121xxx 極值點(diǎn)滿足方程極值點(diǎn)滿足方程. 2min,)02(. 202 fxfT最優(yōu)目標(biāo)函數(shù)值最優(yōu)目標(biāo)函數(shù)值，因此得唯一最優(yōu)解因此得唯一最優(yōu)解），此時(shí)），此時(shí)，求得極值點(diǎn)坐標(biāo)（求得極值點(diǎn)坐標(biāo)（例例2.求解線性規(guī)劃問題求解線性規(guī)劃問題20202020線性代數(shù)線性代數(shù) 第七章第七章 04182.36max2212121xxxxxtsxxf01234512431x2x., 0,. 24:1:82:. 1.212312211域域取交集即為所求的可行取交集

19、即為所求的可行半平面，結(jié)合半平面，結(jié)合確定每個(gè)不等式表示的確定每個(gè)不等式表示的約束畫出約束畫出用等式約束代替不等式用等式約束代替不等式定的可行域定的可行域一。畫出由約束條件確一。畫出由約束條件確 xxxlxlxxl122112.632320,1,28.max24.ffxxxxffxxABf 二 從可行域中找出最優(yōu)解為此，將目標(biāo)函數(shù)變形為當(dāng) 變化時(shí)便產(chǎn)生一簇斜率為 的平行線簇，令平行線簇在平面上截距增大的方向如箭頭所指，此時(shí)，極限位置恰與可行域的邊界線 重合因此，邊界線段上的所有點(diǎn)均為最優(yōu)解例例3.求解線性規(guī)劃問題求解線性規(guī)劃問題21212121線性代數(shù)線性代數(shù) 第七章第七章0123451243

20、1x2x 0025.3min2112121xxxxxtsxxf為空集。為空集?？梢钥吹?，其可行域可以看到，其可行域域域取交集即為所求的可行取交集即為所求的可行半平面，結(jié)合半平面，結(jié)合確定每個(gè)不等式表示的確定每個(gè)不等式表示的約束畫出約束畫出用等式約束代替不等式用等式約束代替不等式定的可行域定的可行域一。畫出由約束條件確一。畫出由約束條件確., 0,. 22:5:. 1.2112211 xxxlxxl. 3也也就就沒沒有有最最優(yōu)優(yōu)解解因因此此沒沒有有可可行行解解，當(dāng)當(dāng)然然可可行行域域是是空空集集，由由于于該該線線性性規(guī)規(guī)劃劃問問題題的的例例4.求解線性規(guī)劃問題求解線性規(guī)劃問題22222222線性代

21、數(shù)線性代數(shù) 第七章第七章圖解法解題步驟： 1.確定可行域 2.做目標(biāo)函數(shù)等值線，確定目標(biāo)函數(shù)增大或減少的方向； 3.確定最優(yōu)解和最優(yōu)值23232323線性代數(shù)線性代數(shù) 第七章第七章線性規(guī)劃最優(yōu)解的3種情況： 1.不存在最優(yōu)解；此時(shí)可行域?yàn)榭占蛘邽榉强諢o界集； 2.存在唯一的最優(yōu)解，此最優(yōu)解為可行域的頂點(diǎn)，此時(shí)可行域?yàn)榉强沼薪缂蛘邽榉强諢o界集； 3.存在唯一的最優(yōu)解，此最優(yōu)解與可行域的一條邊界重回。 由于邊界上必包含可行域的頂點(diǎn)，因此，必有最優(yōu)解為可行域的頂點(diǎn)。24242424線性代數(shù)線性代數(shù) 第七章第七章7.3線性規(guī)劃問題的單純形法線性規(guī)劃模型的標(biāo)準(zhǔn)型線性規(guī)劃模型的標(biāo)準(zhǔn)型 ), 2 , 1

22、( , 0.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnnnnxcxcxcf 2211min其約束方程為其約束方程為 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121nmAr )(不不妨妨假假設(shè)設(shè)非非基基變變量量。為為基基變變量量，否否則則稱稱為為包包含含在在基基中中，則則稱稱所所對(duì)對(duì)應(yīng)應(yīng)的的列列向向量量若若變變量量基基矩矩陣陣，簡(jiǎn)簡(jiǎn)稱稱一一個(gè)個(gè)基基。為為線線性性規(guī)規(guī)劃劃模模型型的的一一個(gè)個(gè)則則稱稱若若階階子子陣陣，的的一一個(gè)個(gè)）為為約約束束矩矩陣陣（設(shè)設(shè)定定義義jjjjjjx

23、pxBmArmmApppBp,)(,3 . 721 1x2x25252525線性代數(shù)線性代數(shù) 第七章第七章 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121約束方程約束方程mAr )(每給非基變量一組值，就能得到非基變量的一組相應(yīng)的值，每給非基變量一組值，就能得到非基變量的一組相應(yīng)的值，從而得到線性規(guī)劃問題的一個(gè)解從而得到線性規(guī)劃問題的一個(gè)解。特別地特別地：127.4( , ,)TnBAx bxx xxBB 定義設(shè) 為線性規(guī)劃模型的一個(gè)基，令所有非基變量為零而得到的滿足的解稱為對(duì)應(yīng)于基 的基本解。如果基本解非負(fù)，則稱為基本可行解。此時(shí)，稱其對(duì)應(yīng)

24、的基 為可行基。注：若約束等式中有注：若約束等式中有n個(gè)變量，個(gè)變量，m個(gè)約束，則個(gè)約束，則基本解基本解的個(gè)數(shù)的個(gè)數(shù)mnC26262626線性代數(shù)線性代數(shù) 第七章第七章令非基變量令非基變量 x10，x2 0則得：則得：x (0, 0, 3, 1 )T基本解基本解2：基變量為：基變量為x2、x3，非基變量為，非基變量為x1、x4令非基變量令非基變量 x10，x4 0則得：則得：x (0, 1, 5, 0 )T基本解基本解非基本可行解非基本可行解基本可行解基本可行解例例 討論下述約束方程的解討論下述約束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解約束矩陣為：約束矩陣為：101201

25、21A1：基變量為：基變量為x3、x4，非基變量為，非基變量為x1、x23:x (1/2, 1/2, 3/2, 1/2)T不是基本解不是基本解可行解可行解不是基本可行解不是基本可行解27272727線性代數(shù)線性代數(shù) 第七章第七章線性規(guī)劃解的性質(zhì)線性規(guī)劃解的性質(zhì) 線性規(guī)劃問題的一個(gè)解線性規(guī)劃問題的一個(gè)解x x為基可行解的充分必要條件是：為基可行解的充分必要條件是：x x的的非零分量所對(duì)應(yīng)的系數(shù)矩陣非零分量所對(duì)應(yīng)的系數(shù)矩陣A A的列向量線性無關(guān)的列向量線性無關(guān)。 mnmmmmnmnmaaaaaaaaaaaa21222221111211 nnbbbxxx2121若線性規(guī)劃問題存在可行解，則一定存在基

26、本可行解若線性規(guī)劃問題存在可行解，則一定存在基本可行解若線性規(guī)劃問題存在最優(yōu)解，則一定存在基本可行解且此解為最若線性規(guī)劃問題存在最優(yōu)解，則一定存在基本可行解且此解為最 優(yōu)解優(yōu)解. .28282828線性代數(shù)線性代數(shù) 第七章第七章二二.單純形法基本思想單純形法基本思想.求解線性規(guī)劃問題：求解線性規(guī)劃問題： 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf1、構(gòu)造初始可行基；、構(gòu)造初始可行基； 1 0 00 1 00 0 1),(5430PPPB 1 0 0 4 00 1 0 0 40 0 1 2 1),.,(51PPA根據(jù)根據(jù)可構(gòu)成初始可行基可構(gòu)成

27、初始可行基為為基基變變量量443,xxx2、求出一個(gè)基本可行解、求出一個(gè)基本可行解032 )12,16, 8 , 0 , 0(, 0021)0()0(21 ）（，得得代代入入目目標(biāo)標(biāo)函函數(shù)數(shù)把把，得得一一基基本本可可行行解解代代入入約約束束方方程程令令：fxxfxxxx3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解； 是否是最優(yōu)解是否是最優(yōu)解？不是最優(yōu)基不是最優(yōu)基不是最優(yōu)解，不是最優(yōu)解，小，所以小，所以增大，便使目標(biāo)函數(shù)減增大，便使目標(biāo)函數(shù)減分析目標(biāo)函數(shù)，只要分析目標(biāo)函數(shù)，只要（0)02Bxx怎么辦？換基怎么辦？換基從一個(gè)基本可行解出發(fā)，經(jīng)從一個(gè)基本可行解出發(fā)，經(jīng)換基迭代，找出另

28、一個(gè)基本換基迭代，找出另一個(gè)基本可行解同時(shí)不斷改進(jìn)目標(biāo)函可行解同時(shí)不斷改進(jìn)目標(biāo)函數(shù)直到判斷出是否有最優(yōu)解數(shù)直到判斷出是否有最優(yōu)解.29292929線性代數(shù)線性代數(shù) 第七章第七章4、基變換，尋找新的基本可行解、基變換，尋找新的基本可行解.進(jìn)基：進(jìn)基：.22量量由由非非基基變變量量變變換換成成基基變變因因此此，把把小小增增大大，便便使使目目標(biāo)標(biāo)函函數(shù)數(shù)減減由由于于xx出基：出基：.2量量必必須須有有一一個(gè)個(gè)變變成成非非基基變變進(jìn)進(jìn)基基，因因而而原原基基變變量量中中由由于于x誰呢？誰呢？0,0543112 xxxxxx保保持持，并并要要新新基基本本可可行行解解中中仍仍取取仍仍為為非非基基變變量量，所

29、所以以在在進(jìn)進(jìn)基基后后，當(dāng)當(dāng).03.0. 0,3)4/12, 2/8min( 04 12 0 16 02 8 5525432543225423出出基基，因因此此確確定定時(shí)時(shí)，注注意意到到）解解中中取?。ǚ欠腔冏兞苛吭谠诨颈究煽尚行兄兄杏杏幸灰粋€(gè)個(gè)取取值值為為的的取取值值還還必必須須使使中中有有一一個(gè)個(gè)出出基基，為為使使xxxxxxxxxxxxxxxx 因此，基由因此，基由 變?yōu)樽優(yōu)?(5430PPPB )(2431PPPB 轉(zhuǎn)第轉(zhuǎn)第2步：求出一個(gè)基本可行解步：求出一個(gè)基本可行解.932 )0 ,16,2 ,3 ,0(,0121)0()1(51目目標(biāo)標(biāo)函函數(shù)數(shù)值值得得以以改改善善，得得代

30、代入入目目標(biāo)標(biāo)函函數(shù)數(shù)把把，得得一一基基本本可可行行解解代代入入約約束束方方程程令令：）（ fxxfXXxxf (1) 是否是最優(yōu)解是否是最優(yōu)解？30303030線性代數(shù)線性代數(shù) 第七章第七章3、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；、最優(yōu)性檢驗(yàn)：判斷是否最優(yōu)解；在新基下，把約束方程中的基變量用非基變量表示在新基下，把約束方程中的基變量用非基變量表示 04 16 0 21 2 41 3 1451352xxxxxxx9432325121 xxfxxf以以后后的的目目標(biāo)標(biāo)函函數(shù)數(shù)基基變變量量表表示示，得得到到改改進(jìn)進(jìn)這這樣樣，將將目目標(biāo)標(biāo)函函數(shù)數(shù)用用非非，再再代代入入目目標(biāo)標(biāo)函函數(shù)數(shù).0,51將將增增大大變

31、變大大時(shí)時(shí)，由由易易見見，非非基基變變量量fxx. 9min)0 ,16, 2 , 3 , 0()1( fX是是最最優(yōu)優(yōu)解解，所所以以 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf31313131線性代數(shù)線性代數(shù) 第七章第七章 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf上例可通過以下形式求解上例可通過以下形式求解),(5430PPPB 定定一一個(gè)個(gè)可可行行基基首首先先，從從約約束束方方程程中中選選03221 xxf成方程形式：成方程形式：將目標(biāo)函數(shù)表達(dá)式改寫將目標(biāo)函數(shù)表達(dá)式改寫 03212

32、 4 16 48 2215241321xxfxxxxxxx下下線線性性方方程程組組：于于是是，標(biāo)標(biāo)準(zhǔn)準(zhǔn)型型可可視視為為如如行行變變換換對(duì)對(duì)其其增增廣廣矩矩陣陣施施以以初初等等1x3x2x4x5xb 01216801 00 00 34 200 1 0 0 40 0 1 2 1 54321 bxxx xx.12x確確定定進(jìn)進(jìn)基基變變量量為為是是否否為為正正）按按目目標(biāo)標(biāo)函函數(shù)數(shù)中中的的系系數(shù)數(shù)（值值原原則則確確定定離離基基變變量量。列列的的正正系系數(shù)數(shù)，按按最最小小比比以以進(jìn)進(jìn)基基變變量量所所在在）用用約約束束常常數(shù)數(shù)項(xiàng)項(xiàng)分分別別除除（2.3量量進(jìn)進(jìn)基基變變量量成成為為單單位位列列向向上上通通過過

33、行行變變換換使使）換換基基迭迭代代過過程程，實(shí)實(shí)際際（非基變量非基變量基變量基變量001032323232線性代數(shù)線性代數(shù) 第七章第七章 01216801 00 00 34 200 1 0 0 40 0 1 2 1 54321 bxxx xx1x3x2x4x5xb 3162 00 00 0100 1 0 0 4 0 1 01 54321 bxxx xx1x3x2x4x5xb943251xxf. 9min)0 ,16, 2 , 3 , 0()1( fx是最優(yōu)解，是最優(yōu)解，所以所以21414329001033333333線性代數(shù)線性代數(shù) 第七章第七章 2 3 0 0 0 1 2 1 0 0 4 0

34、 0 1 0 0 4 0 0 1 8 16 122 3 0 0 0 03x5x1x2x3x4x5xjx基變量基變量4xjcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)單純形方法單純形方法單純形方法是表格化的換基迭代法單純形方法是表格化的換基迭代法.用單純形方法解線性規(guī)劃問題需將用單純形方法解線性規(guī)劃問題需將增廣矩陣換基迭代的過程用表格形式表示出來增廣矩陣換基迭代的過程用表格形式表示出來.,0, 03. 1222作作為為進(jìn)進(jìn)基基變變量量因因此此目目標(biāo)標(biāo)函函數(shù)數(shù)值值減減小小增增大大時(shí)時(shí)由由其其對(duì)對(duì)應(yīng)應(yīng)的的變變量量量量的的系系數(shù)數(shù)稱稱為為檢檢驗(yàn)驗(yàn)數(shù)數(shù)。成成方方程程形形式式，其其決決策策變變將將目目標(biāo)標(biāo)函函數(shù)數(shù)非非基基化

35、化后后寫寫xxcjj 就就是是離離基基變變量量。原原來來基基變變量量的的最最小小值值所所在在行行對(duì)對(duì)應(yīng)應(yīng)的的按按最最小小比比值值原原則則其其比比值值5. 2x代。代。，就完成了一次換基迭，就完成了一次換基迭列其余元素化為列其余元素化為，該，該為為，稱為主元素。將其化，稱為主元素。將其化的的基變量所在行的交叉處基變量所在行的交叉處以進(jìn)基變量所在列與離以進(jìn)基變量所在列與離014. 3 0,12 4 16 48 232min54321524132121xxxxxxxxxxxxxxf34343434線性代數(shù)線性代數(shù) 第七章第七章 2 0 0 0 1 0 1 0 4 0 0 1 0 0 1 0 0 8

36、16 3 0 0 0 3x2x1x2x3x4x5xjx基變量基變量4xjcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)21414343. 0 此時(shí)，因?yàn)槿繖z驗(yàn)數(shù)此時(shí)，因?yàn)槿繖z驗(yàn)數(shù). 9min)0 ,16, 2 , 3 , 0()1( fx是最優(yōu)解，是最優(yōu)解，所以所以2935353535線性代數(shù)線性代數(shù) 第七章第七章 . 3 , 2 , 1, 062253222.33max. 1321321321221jxxxxxxxxxxtsxxxfj求線性規(guī)劃問題求線性規(guī)劃問題例例 -3 -1 -3 0 0 0 2 1 1 1 0 0 1 2 3 0 1 0 2 2 1 0 0 1 2 5 6 3 1 3 0 0 0 0j

37、x基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x6x6x4x5x.2,2226,15,22min, 04111321xax，離離基基變變量量為為故故主主元元素素為為由由于于此此進(jìn)進(jìn)基基變變量量為為先先考考慮慮下下標(biāo)標(biāo)最最小小的的。因因，此此時(shí)時(shí)檢檢驗(yàn)驗(yàn)數(shù)數(shù) 6 , 5 , 4 , 3 , 2 , 1, 062253222.33min632153214321321jxxxxxxxxxxxxxtsxxxfj解：化為標(biāo)準(zhǔn)形式：解：化為標(biāo)準(zhǔn)形式：36363636線性代數(shù)線性代數(shù) 第七章第七章 jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x6x6x1x5x21212125

38、2323210212300000212311113440110002300為進(jìn)基變量。為進(jìn)基變量。此時(shí)，此時(shí)，33. 023x 254254,211min 由于由于為離基變量。為離基變量。，所以主元素為所以主元素為52325xa 代。代。，就完成了一次換基迭，就完成了一次換基迭，列其余元素化為，列其余元素化為將主元素化為將主元素化為01. 3037373737線性代數(shù)線性代數(shù) 第七章第七章 jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x6x6x1x3x15351151000005153515258000011140000575653527575653. 0 此時(shí)，因?yàn)槿繖z驗(yàn)

39、數(shù)此時(shí)，因?yàn)槿繖z驗(yàn)數(shù).527min)400 ,58, 0 ,51( fx是最優(yōu)解，是最優(yōu)解，所以所以.527max) ,58, 0 ,51( fx是最優(yōu)解，是最優(yōu)解，故，原問題中故，原問題中迭代。迭代。，再次完成了一次換基，再次完成了一次換基，列其余元素化為，列其余元素化為將主元素化為將主元素化為0138383838線性代數(shù)線性代數(shù) 第七章第七章321254540min. 3xxxf 求線性規(guī)劃問題求線性規(guī)劃問題例例 . 543 , 2 , 1, 012023310032.53214321，jxxxxxxxxxtsj53 jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x4x5

40、x jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x4x1x40454025000000000120321005116001111332452553323400311132031204005530340(二二)(一一)39393939線性代數(shù)線性代數(shù) 第七章第七章 jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x2x1x jx基變量基變量jcj 檢驗(yàn)數(shù)檢驗(yàn)數(shù)常常數(shù)數(shù)1x4x3x2x5x2x3x000000020110000000051017001111132313238031312015170051011120100510(四四)(三三)為為主主元元素素，得得表表四四。為為離離基基變變量量，為為進(jìn)進(jìn)基基變變量