第一章線性規(guī)劃及單純形法演示文稿

第一章線性規(guī)劃及單純形法演示文稿目前一頁\總數(shù)一百二十六頁\編于十七點(diǎn)優(yōu)選第一章線性規(guī)劃及單純形法目前二頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃理論的發(fā)展：1939年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ）《生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法》提出“解乘數(shù)法”。1．線性規(guī)劃介紹列奧尼德·康托羅維奇，前蘇聯(lián)人，由于在1939年創(chuàng)立了享譽(yù)全球的線形規(guī)劃要點(diǎn)，對(duì)資源最優(yōu)分配理論做出了貢獻(xiàn)，而獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。目前三頁\總數(shù)一百二十六頁\編于十七點(diǎn)美國(guó)科學(xué)院院士DANTZIG（丹齊克），1948年在研究美國(guó)空軍資源的優(yōu)化配置時(shí)提出線性規(guī)劃及其通用解法“單純形法”。被稱為線性規(guī)劃之父。1．線性規(guī)劃介紹線性規(guī)劃之父的Dantzig(丹齊克)。據(jù)說，一次上課，Dantzig遲到了，仰頭看去，黑板上留了幾個(gè)幾個(gè)題目，他就抄了一下，回家后埋頭苦做。幾個(gè)星期之后，疲憊的去找老師說，這件事情真的對(duì)不起，作業(yè)好像太難了，我所以現(xiàn)在才交，言下很是慚愧。幾天之后，他的老師就把他召了過去，興奮的告訴他說他太興奮了。Dantzig很不解,后來才知道原來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解決的問題，他給出的那個(gè)解法也就是單純形法。這個(gè)方法是上個(gè)世紀(jì)前十位的算法。目前四頁\總數(shù)一百二十六頁\編于十七點(diǎn)1．線性規(guī)劃介紹1960年，“最佳資源利用的經(jīng)濟(jì)計(jì)算”康托洛維奇和庫伯曼斯(Koopmans)。兩人因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲1975年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)佳林·庫普曼斯，美國(guó)人，他將數(shù)理統(tǒng)計(jì)學(xué)成功運(yùn)用于經(jīng)濟(jì)計(jì)量學(xué)，對(duì)資源最優(yōu)分配理論做出了貢獻(xiàn)。目前五頁\總數(shù)一百二十六頁\編于十七點(diǎn)1961年，查恩斯與庫伯提出了目標(biāo)規(guī)劃，艾吉利提出了用優(yōu)先因子來處理多目標(biāo)問題。20世紀(jì)70年代，斯．姆．李與杰斯開萊尼應(yīng)用計(jì)算機(jī)處理目標(biāo)規(guī)劃問題。計(jì)算機(jī)50約束100變量

30000約束3000000變量1．線性規(guī)劃介紹目前六頁\總數(shù)一百二十六頁\編于十七點(diǎn)從1964年諾貝爾獎(jiǎng)設(shè)經(jīng)濟(jì)學(xué)獎(jiǎng)后，到1992年28年間的32名獲獎(jiǎng)?wù)咧杏?3人(40%)從事過與線性規(guī)劃有關(guān)的研究工作，其中著名的有Simon，Samullson，Leontief，Arrow，Miller等。1．線性規(guī)劃介紹保羅-薩繆爾遜（PAULASAMUELSON）,他發(fā)展了數(shù)理和動(dòng)態(tài)經(jīng)濟(jì)理論，將經(jīng)濟(jì)科學(xué)提高到新的水平。他的研究涉及經(jīng)濟(jì)學(xué)的全部領(lǐng)域。于1970年獲得諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。華西里·列昂惕夫（WASSILYLEONTIEF），美國(guó)人，他發(fā)展了投入產(chǎn)出方法，該方法在許多重要的經(jīng)濟(jì)問題中得到運(yùn)用。曾獲1973年諾貝爾經(jīng)濟(jì)科學(xué)獎(jiǎng)?？夏崴?J-阿羅（KENNETHJ.ARROW）,美國(guó)人，因與約翰-?？怂梗↗OHNR.HICKS）共同深入研究了經(jīng)濟(jì)均衡理論和福利理論獲得1972年諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)。牟頓-米勒（MERTONM.MILLER）,1923-2000,美國(guó)人,由于他在金融經(jīng)濟(jì)學(xué)方面做出了開創(chuàng)性工作，于1990年獲得諾貝爾經(jīng)濟(jì)獎(jiǎng)。目前七頁\總數(shù)一百二十六頁\編于十七點(diǎn)1．線性規(guī)劃介紹線性規(guī)劃研究的主要問題：有一定的人力、財(cái)力、資源條件下，如何合理安排使用，效益最高?某項(xiàng)任務(wù)確定后，如何安排人、財(cái)、物，使之最省?

目前八頁\總數(shù)一百二十六頁\編于十七點(diǎn)例1美佳公司計(jì)劃制造I，II兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試時(shí)間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況如表I—l所示。問該公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤(rùn)為最大？項(xiàng)目III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤(rùn)（元）212．線性規(guī)劃數(shù)學(xué)模型目前九頁\總數(shù)一百二十六頁\編于十七點(diǎn)目標(biāo)函數(shù)約束條件解：用變量x1和x2分別表示美佳公司制造家電I和II的數(shù)量。項(xiàng)目III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤(rùn)（元）21例1用數(shù)學(xué)語言描述2．線性規(guī)劃數(shù)學(xué)模型目前十頁\總數(shù)一百二十六頁\編于十七點(diǎn)解：(1)、確定可行域

x10x1=0(縱)x20x2=0(橫)

x1+2x230x1+2x2=30(0,15)(30,0)x20102030DABC3x1+2x2=60(0,30)(20,0)

2x2=24203010x1線性規(guī)劃的圖解法目前十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)例2捷運(yùn)公司擬在下一年度的1-4月的4個(gè)月內(nèi)需租用倉(cāng)庫堆放物資。已知各月份所需倉(cāng)庫面積數(shù)列見下表。倉(cāng)庫租借費(fèi)用隨合同期定，期限越長(zhǎng)折扣越大，具體數(shù)字見下表。租借倉(cāng)庫的合同每月初都可辦理，每份臺(tái)同具體現(xiàn)定租用面積數(shù)和期限。因此該廠可根據(jù)需要，在任何一個(gè)月初辦理租借臺(tái)同。每次辦理時(shí)可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。月份1234所需倉(cāng)庫面積15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)28004500600073002．線性規(guī)劃數(shù)學(xué)模型目前十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)解：設(shè)變量xij表示捷運(yùn)公司在第i(i＝1．…，4)個(gè)月初簽訂的租借期為j〔j＝1，…，4)個(gè)月的倉(cāng)庫面積的合同(單位為100m2)。約束條件目標(biāo)函數(shù)例2月份1234所需倉(cāng)庫面積15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)28004500600073002．線性規(guī)劃數(shù)學(xué)模型目前十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)max(min)Z=c1x1+c2x2+…+cnxnn個(gè)變量?jī)r(jià)值系數(shù)第i種資源的擁有量技術(shù)系數(shù)或工藝系數(shù)a11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2………am1x1+am2x2+…+amnxn(=,)bmxj0(j=1,…,n)s.t.線性規(guī)劃的一般式2．線性規(guī)劃數(shù)學(xué)模型目前十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃的簡(jiǎn)寫式2．線性規(guī)劃數(shù)學(xué)模型目前十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃的向量表示式2．線性規(guī)劃數(shù)學(xué)模型目前十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃的矩陣表示式2．線性規(guī)劃數(shù)學(xué)模型目前十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù)：max，min約束條件：≥,=,≤變量符號(hào)：：≥0,≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：max約束條件 ：=變量符號(hào) ：≥03．線性規(guī)劃標(biāo)準(zhǔn)形式目前十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)標(biāo)準(zhǔn)型的一般型maxZ=c1x1+c2x2+…+cnxn其中

bi

0(i=1,2,…,m)a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmxj0(j=1,2,…,n)s.t.3．線性規(guī)劃標(biāo)準(zhǔn)形式目前十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)

P1P2………Pna11a12………a1n其中A=a21a22………

a2n

…am1am2………amn

x1x=x2

xn…

b1b=b2

bm…C=(C1C2…Cn)標(biāo)準(zhǔn)型的矩陣型maxZ=CxAx=bx0b0

3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十頁\總數(shù)一百二十六頁\編于十七點(diǎn)

x1Ax=(P1P2…Pn)x2=b

xn

…P1x1+

P2x2+…+Pnxn=b標(biāo)準(zhǔn)型的向量型3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)線性規(guī)劃問題化標(biāo)準(zhǔn)型：(1)、約束條件(2)、變量(3)、目標(biāo)函數(shù)(4)、右端常數(shù)3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)目前二十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)(1)、約束條件x3為松弛變量x4為剩余變量松弛變量或剩余變量在實(shí)際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價(jià)值和利潤(rùn)，所以引進(jìn)模型后它們?cè)谀繕?biāo)函數(shù)中的系數(shù)均為零。當(dāng)約束條件為“”時(shí)：當(dāng)約束條件為“”時(shí)：3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)(2)、變量3x1'-3x1"+2x28x1'

-x1"-4x2

14x1',x1",x201、x

0的情況，3x1+2x28x1-4x214x20令x1=x1'-x1"2、x取值無約束的情況。令x’＝-x。令x=x'-x"3x1'-3x1"+2x2+x3=8x1'

-x1"-4x2+x4=14x1',x1",x2,x3,x403．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)x1'

+x211x1'16x1',x20（3）、x兩邊有約束的情況。x1+x25-6x110x20-6+6x1+6

10+6

令x1'

=x1+6

0x1'

163．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)(3)、目標(biāo)函數(shù)xoZ-Z令Z'

=-Z

3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)(4)、右端常數(shù)右端項(xiàng)b＜0時(shí)，只需將等式或不等式兩端同乘(一1)，則等式右端項(xiàng)必大于零。3．線性規(guī)劃標(biāo)準(zhǔn)形式目前二十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)3．線性規(guī)劃標(biāo)準(zhǔn)形式

X1+2X2+X3=30s.t.3X1+2X2+X4=602X2

+X5=24

X1,

…,X50轉(zhuǎn)化為：maxZ=40X1+50X2+0·X3+0·X4+0·X5

x1

+2x2

303x1+2x2

60s.t.2x2

24

x1，x2

0

例：maxZ=40x1+50x2松弛變量目前二十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)3．線性規(guī)劃標(biāo)準(zhǔn)形式例：

4x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)4X1+6X2+X3+2X4-X5=12X1+X2+7X3+5X4-X6=142X2+X3+3X4-X7=8

X1,

…,X70剩余變量目前三十頁\總數(shù)一百二十六頁\編于十七點(diǎn)例3：將minZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3無限制化為標(biāo)準(zhǔn)型3．線性規(guī)劃標(biāo)準(zhǔn)形式目前三十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)解：①令x3=x4-

x5②加松弛變量x6③加剩余變量x7

④令Z'=-ZmaxZ'=x1-2x2+3x4-3x5x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,

x2,

x4,…,x70minZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3無限制3．線性規(guī)劃標(biāo)準(zhǔn)形式目前三十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)(1)minZ=2x1-x2+2x3練習(xí)5將下列線性規(guī)劃問題化成標(biāo)準(zhǔn)型：-x1

+x2+x3

=

4-x1

+x2-x3

6x1

0

，x2

0,x3

無約束

s.t.(2)maxZ=2x1+x2+3x3+x4x1

+x2+x3+x3

72x1

-3x2+x3

=-8x1

-2x3+2x4

1x1,

x3

0,x2

0

，x4

無約束

s.t.3．線性規(guī)劃標(biāo)準(zhǔn)形式目前三十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)(3)minZ=2x1+3x2+5x3x1

+x2-x3

-5

-6x1

+7x2-9x3

=15|19x1

-7x2+5x3|13x1,

x2

0,x3

無約束

s.t.(4)maxZ=x1-3x2-x1

+2x2-5

x1

+3x2=10x1,

x2

無約束

s.t.3．線性規(guī)劃標(biāo)準(zhǔn)形式目前三十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)Ax=b(1)x

0(2)maxZ=Cx(3)定義1：滿足約束(1)、(2)的x=(x1…xn)T稱為L(zhǎng)P問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(3)的可行解稱為L(zhǎng)P問題的最優(yōu)解線性規(guī)劃的標(biāo)準(zhǔn)型4．線性規(guī)劃的圖解法目前三十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)圖解法求解的目的：一是判別線性規(guī)劃問題的求解結(jié)局；二是在存在最優(yōu)解的條件下，把問題的最優(yōu)解找出來。

4．線性規(guī)劃的圖解法目前三十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)圖解法的步驟：1、在平面上建立直角坐標(biāo)系；2、圖示約束條件，找出可行域；3、圖示目標(biāo)函數(shù)和尋找最優(yōu)解。4．線性規(guī)劃的圖解法目前三十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)例1maxZ=40x1+50x2

x1+2x2303x1+2x2602x224

x1,x204．線性規(guī)劃的圖解法目前三十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)解：(1)、確定可行域

x10x1=0(縱)x20x2=0(橫)x1+2x230x1+2x2=30(0,15)(30,0)x20102030DABC3x1+2x2=60(0,30)(20,0)

2x2=24203010x14．線性規(guī)劃的圖解法目前三十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)(2)、求最優(yōu)解最優(yōu)解：x*=(15,7.5)Zmax=975Z=40x1+50x20=40x1+50x2(0,0)，(10,-8)x20102030203010x1DABCC點(diǎn)：x1+2x2=30

3x1+2x2=604．線性規(guī)劃的圖解法目前四十頁\總數(shù)一百二十六頁\編于十七點(diǎn)Z=40x1+80x2=0

x1+2x2=30DABCx20x1解:最優(yōu)解：BC線段B點(diǎn)C點(diǎn)x(1)=(6,12)x(2)=(15,7.5)x=x(1)+(1-)x(2)(01)例2maxZ=40x1+80x2

x1+2x2303x1+2x2602x224

x1,x204．線性規(guī)劃的圖解法目前四十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)4．線性規(guī)劃的圖解法X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5目前四十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)無界解無有限最優(yōu)解例3maxZ=2x1+4x2

2x1+x28-2x1+x22x1,x20Z=02x1+x2=8-2x1+x2=28246x240x14．線性規(guī)劃的圖解法目前四十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)例4、maxZ=3x1+2x2-x1-x21x1,x20無解無可行解-1x1-1x204．線性規(guī)劃的圖解法目前四十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)唯一解無窮多解無有限最優(yōu)解無可行解有解無解當(dāng)目標(biāo)函數(shù)的直線族與某約束條件平行，且該問題有解時(shí)。約束條件無公共區(qū)域。有解但可行域可伸展到無窮時(shí)總結(jié)4．線性規(guī)劃的圖解法目前四十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)由圖解法得到的啟示(1)、線性規(guī)劃問題的解的情況有四種：唯一最優(yōu)解；無窮多最優(yōu)解；無界解；無可行解。(2)、若線性規(guī)劃可行域存在，則可行域是一個(gè)凸集。(3)、若有最優(yōu)解，定可在可行域的頂點(diǎn)得到。(4)、解題思路是找出凸集的各頂點(diǎn)的最大目標(biāo)函數(shù)值。4．線性規(guī)劃的圖解法目前四十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)練習(xí)：用圖解法解以下問題：

maxZ=5x1+6x2x1

-2x2

2

-2x1

+3x22x1,

x2

無約束

s.t.4．線性規(guī)劃的圖解法目前四十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)Ax=b(1)x

0(2)maxZ=Cx(3)1、可行解：滿足約束(1)、(2)的x=(x1…xn)T稱為L(zhǎng)P問題的可行解，全部可行解的集合稱為可行域。2、最優(yōu)解：滿足(3)的可行解稱為L(zhǎng)P問題的最優(yōu)解線性規(guī)劃的標(biāo)準(zhǔn)型一、線性規(guī)劃問題的解的概念5．線性規(guī)劃基本概念目前四十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)3、基(基陣)——設(shè)A為約束方程組的m×n階系數(shù)矩陣設(shè)(n>m)，其秩為m，B是矩陣A中的一個(gè)m×m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個(gè)基。

P1P2…Pm……Pna11a12…

a1m……a1nA=a21a22…

a2m……

a2n

……am1am2…

amm……amnB5．線性規(guī)劃基本概念目前四十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)A=(P1…

PmPm+1…

Pn)=(BN)基向量非基向量…x=(x1…

xmxm+1…

xn)T=(xBxN)T

基變量非基變量

xB

xN…B中的每一個(gè)列向量Pj稱為基向量，與基向量對(duì)應(yīng)的變量稱為基變量，其他變量稱為非基變量。5．線性規(guī)劃基本概念目前五十頁\總數(shù)一百二十六頁\編于十七點(diǎn)4、基解——在約束方程組中，令所有非基變量等于零，又因?yàn)榫仃嘊不等于0，根據(jù)克萊姆法則，由m個(gè)約束方程可以解出m個(gè)集變量的唯一解，將這個(gè)解加上非基變量取0的值，稱為線性規(guī)劃問題的基解。5、基本可行解——基B，基本解x=若B-1b0，稱基解為基本可行解，也稱基可行解?！窘庵凶疃嘤衜個(gè)非零分量?！窘獾臄?shù)目不超過Cnm=個(gè)。n!m!(n-m)!6、可行基——對(duì)應(yīng)于基可行解的基稱為可行基。5．線性規(guī)劃基本概念目前五十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)例8x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50121003201002001P1P2P3P4P5A=5．線性規(guī)劃基本概念B=(P3P4P5)=I

是滿秩子矩陣非基N=(P1P2)x1x2x3x4x5x==00306024令x1=

x2=0,x3=30,x4=60,x5=24目前五十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)例9：給定約束條件

-x3+x4=0x2+x3+x4=3-x1+x2+x3+x4=2xj0(j=1,2,3,4)求出基變量是x1,x3,x4的基本解，是不是可行解？5．線性規(guī)劃基本概念目前五十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)

0-11解：B=(P1P3P4)=011-111

01-10B-1=-1/21/2031/21/202b=5．線性規(guī)劃基本概念目前五十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)

x1

x3=B-1b

x4

xB=

01-101

=-1/21/203=3/2

1/21/2023/2∴x=(1,0,3/2,3/2)T是5．線性規(guī)劃基本概念目前五十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)凸集——D是n維空間的一個(gè)集合，x(1),

x(2)∈D,若對(duì)任何x(1),

x(2)，有x=x(1)+(1-)x(2)∈D(01)，則D為凸集。定義1：凸集——如果集合D中任意兩個(gè)點(diǎn)，其連線上的所有點(diǎn)也都是集合D中的點(diǎn)，則稱D為凸集。二、凸集及其頂點(diǎn)5．線性規(guī)劃基本概念目前五十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)x(1)x(2)凸多邊形凹多邊形x(1)x(2)5．線性規(guī)劃基本概念第一章目前五十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)

x(1),x(2),…,x(k)

是n維歐氏空間中的k個(gè)點(diǎn)，若有一組數(shù)

μ1,μ2,…,μk

滿足

0μi1(i=1,…,k)定義2μ

i=1ki=1有點(diǎn)x=μ1x(1)

+…+μkx(k)則稱點(diǎn)x為x(1),x(2),…,x(k)

的凸組合。凸組合5．線性規(guī)劃基本概念目前五十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)凸集D,點(diǎn)xD，若找不到兩個(gè)不同的點(diǎn)x(1),x(2)D使得x=x(1)

+(1-)x(2)

(0<<1)

則稱x為D的頂點(diǎn)。定義3頂點(diǎn)5．線性規(guī)劃基本概念目前五十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)證明：設(shè)LP問題的可行解域?yàn)榧螩C={x|Ax=bx0}任取x(1),x(2)C,則

x=x(1)

+(1-)x(2)

0

(0

1)又因?yàn)锳x(1)

=b，Ax(2)

=b所以Ax=A[x(1)

+(1-)x(2)

]=b

+(1-)b=b

則xC，C為凸集定理1：LP問題的可行解域一定是凸集。三、幾個(gè)基本定理的證明5．線性規(guī)劃基本概念目前六十頁\總數(shù)一百二十六頁\編于十七點(diǎn)只須證明：

D的k個(gè)頂點(diǎn)x(1),…,x(k)

，有

預(yù)理1D為有界凸多面集，xD，x必可表為D的頂點(diǎn)的凸組合。0μi1，使x=μ1x(1)

+…+μkx(k)μ

i=1ki=15．線性規(guī)劃基本概念目前六十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)證明可用歸納法（略）x(1)x(2)x(3)x’xx’在邊界上x在內(nèi)部x(1)(1-)x(2)(1-)x(3)x=++x＝x’

+(1-)x(2)

(0

1)x’＝x(1)

+(1-)x(3)

(0

1)5．線性規(guī)劃基本概念目前六十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)證明：設(shè)x(1),…,x(k)

為可行域頂點(diǎn)，若x*不是頂點(diǎn)，但maxZ=Cx*

定理2：可行域有界，最優(yōu)值必可在頂點(diǎn)得到Cx*=μ

iC

x(i)ki=1μ

iCx(m)

ki=1=Cx(m)[設(shè)Cx(m)＝Max(C

x(i))]1ikμ

ix(i)ki=1μ

i=1ki=10μi1x*=5．線性規(guī)劃基本概念目前六十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)引理2：LP問題的可行解x是基本可行解x的非0分量對(duì)應(yīng)的系數(shù)列向量線性無關(guān)證明：（1）必要性。由基可行解的定義顯然。（2）充分性。若向量P1，P2,…Pk線性獨(dú)立，則必有k

m。當(dāng)k=m時(shí)，它們恰好構(gòu)成一個(gè)基，從而x=(x1,x2,…,xm,0,…,0)為相應(yīng)的基可行解。當(dāng)k<m時(shí)，則一定可從其余列向量中找出(m-k)個(gè)與P1,P2,…,Pk構(gòu)成一個(gè)基，其對(duì)應(yīng)的解恰為x，所以據(jù)定義它是基可行解。5．線性規(guī)劃基本概念目前六十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)證明(反證法）：()假設(shè)x不是基本可行解x＝(x1,…,xn)Txj>0j=1,…,kxj=0j=k+1,…,n由引理2知，p1,…,pk線性相關(guān)必有不全為0的1,…,

k使1p1+…+

kpk=0做＝(1,…,

k,0…,0)T則有A

＝1p1+…+

kpk=0可行域C中點(diǎn)x是頂點(diǎn)x是基本可行解定理3：5．線性規(guī)劃基本概念目前六十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)選任一不為零的數(shù)令

x(1)

=x+

0

x(2)

=x－

0又Ax(1)

=Ax+A＝b

Ax(2)

=Ax－A=b

所以x(1)Cx(2)C因?yàn)閤＝1/2x(1)+1/2x(2)所以x不是可行域的頂點(diǎn)5．線性規(guī)劃基本概念目前六十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)證明：()不是頂點(diǎn)，不是基可行解設(shè)x為可行解xj>0j=1,…,kxj=0j=k+1,…,n若x不是頂點(diǎn)，則有x(1)＝x(2)C，使得：

x=x(1)

+(1-)x(2)

(0<

<

1)xj=xj(1)

+(1-)xj(2)

(j=1,…,k)0=xj(1)

+(1-)xj(2)

(j=k+1,…,n)5．線性規(guī)劃基本概念目前六十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)因?yàn)?gt;0，1->0，xj(1)

0，xj(2)

0所以xj(1)＝

xj(2)＝

0(j=k+1,…,n)因?yàn)锳x(1)

=bAx(2)

=bp

jxj(1)=bnj=1p

jxj(2)=bnj=1即p1x1(1)+…+pkxk(1)=b(a)p1x1(2)+…+pkxk(2)=b(b)5．線性規(guī)劃基本概念目前六十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)由(a)－(b)

得(x1(1)－x1(2))p1+…+(xk(1)－xk(2))pk=0即x不是基可行解所以p1,…,pk線性相關(guān)定理4若線性規(guī)劃問題有最優(yōu)解，一定存在一個(gè)基可行解是最優(yōu)解。5．線性規(guī)劃基本概念目前六十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)

(LP)問題的基本可行解可行域的頂點(diǎn)。若(LP)問題有最優(yōu)解，必可以在基本可行解(頂點(diǎn))達(dá)到。若(LP)問題有可行解，則可行解集(可行域)是凸集(可能有界，也可能無界)，有有限個(gè)頂點(diǎn)。5．線性規(guī)劃基本概念LP問題解的性質(zhì)目前七十頁\總數(shù)一百二十六頁\編于十七點(diǎn)6．單純形法

6.1、單純形法迭代原理

6.2、單純形法計(jì)算步驟

6.3、人工變量法

6.4、兩階段法

6.5、計(jì)算中的幾個(gè)問題目前七十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.1單純形法迭代原理一、確定初始基可行解二、從一個(gè)基可行解轉(zhuǎn)換為相鄰基可行解三、最優(yōu)性檢驗(yàn)和解的判別目前七十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)A中總存在一個(gè)單位矩陣（P1,P2,…,Pm)。一、確定初始基可行解當(dāng)約束條件為時(shí)，加上松馳變量的系數(shù)矩陣即為單位矩陣。當(dāng)約束條件為或＝時(shí)，可以構(gòu)造人工基，人為產(chǎn)生一個(gè)單位矩陣。基向量、基變量、非基向量、非基變量可得初始基可行解:x=(x1,…,xm,xm+1,…xn)T=(b1,…,bm,0,…,0)T6.1單純形法迭代原理目前七十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)兩個(gè)基可行解相鄰指的是它們之間變換且僅變換一個(gè)基變量。設(shè)x(0)=(x10,x20,…xm0,0,…0)T，有Pixi0=bmi=1系數(shù)矩陣的增廣矩陣二、基可行解的轉(zhuǎn)換6.1單純形法迭代原理目前七十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)Pj=aijPimi=1Pj－aijPi＝0

m

i=1兩邊乘上一個(gè)正數(shù)θ>0，得θ

(Pj－aij

Pi）=0

m

i=1同相加整理得：Pixi0=bmi=1所以得到另一個(gè)點(diǎn)x(1),使Pixi(1)=bni=1可行解?基解?6.1單純形法迭代原理目前七十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)所以x(1)是可行解令存在：6.1單純形法迭代原理目前七十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)重新排列后不含非基向量的增廣矩陣：因alj＞0，故上述矩陣元素組成的行列式不為零，P1,P2,…Pl-1,Pj,Pl+1,…,Pm

是一個(gè)基。所以，x(1)

，是基可行解。00…010…06.1單純形法迭代原理進(jìn)行初等變換：b=(b1-θa1j,…,bl-1-θal-1,j,θ,bl+1-

θal+1,j,…bm-amj)T由此x(1)是x(0)相鄰的基可行解，且由基向量組成的矩陣仍為單位矩陣。目前七十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)將基本可行解x（0）和x（1）分別代入目標(biāo)函數(shù)得：三、最優(yōu)性檢驗(yàn)和解的判別6.1單純形法迭代原理目前七十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)是對(duì)線性規(guī)劃問題的解進(jìn)行最優(yōu)性檢驗(yàn)的標(biāo)志。當(dāng)所有的σi<=0時(shí)，現(xiàn)有頂點(diǎn)為最優(yōu)解。當(dāng)所有的σi<=0時(shí)，又對(duì)某個(gè)非基變量xj,有Cj-Zj=0，且可找到θ

＞0，則有無窮多最優(yōu)解。當(dāng)存在某個(gè)σj>0，又Pj<=0,則有無界解。通常簡(jiǎn)寫為6.1單純形法迭代原理目前七十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.2單純形法計(jì)算步驟

5）以a’l,k為主元素進(jìn)行旋轉(zhuǎn)運(yùn)算，轉(zhuǎn)2）。1)找出初始基可行解，建立單純形表。目前八十頁\總數(shù)一百二十六頁\編于十七點(diǎn)單純形表格6.2單純形法計(jì)算步驟Cjc1…cm…cj…cnθCBxBbx1…xm…xj…xnc1x1b110…a1j…a1nc2x2b200…a2j…a2n…………….………………cmxmbm01…amj…amnσj=cj-zj0…0……目前八十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)例10

用單純形法求解線性規(guī)劃問題maxZ=2x1+x25x2

156x1

+2x2

24x1

+x3

5x1,

x2

0s.t.6.2單純形法計(jì)算步驟目前八十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)解：1、先將上述問題化成標(biāo)準(zhǔn)形式有

5x2+x3=15s.t.6x1+2x2+x4=24x1+x2

+x5=5

x1,

…,x50maxZ=2x1+x2+0·x3+0·x4+0·x56.2單純形法計(jì)算步驟找到一個(gè)初始基可行解x=(0,0,15,24,5)目前八十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)2、列初始單純形表：因?yàn)棣?＞σ2，確定x1為換入變量。因?yàn)棣龋絤in{-，24/6，5/1}＝4所以6為主元素，x4為換出變量。Cj21000θCBxBbx1x2x3x4x50x315051000x424620100x5511001σj=cj-zj6.2單純形法計(jì)算步驟/24/65/121000目前八十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)3、列新單純形表：因?yàn)棣?＞0

，確定x2為換入變量。因?yàn)棣龋絤in{15/5，4/2/6，1/4/6}＝3/2。所以4/6為主元素，x5為換出元素。Cj21000θCBxBbx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61σj=cj-zj6.2單純形法計(jì)算步驟15/54/(2/6)1/(4/6)01/30-1/30目前八十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)4、列新單純形表：因?yàn)镃j-Zj＜0，所以達(dá)到最優(yōu)解。最優(yōu)解為：x=(7/2,3/2,15/2,0,0)。目標(biāo)函數(shù)值為Z＝2×7/2+1×3/2+0×15/2+0+0=8.5Cj21000θCBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2σj=cj-zj6.2單純形法計(jì)算步驟000-1/4-1/2目前八十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)練習(xí)題解：原問題化為標(biāo)準(zhǔn)型6.2單純形法計(jì)算步驟目前八十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj3501000θCBxBbx1x2x3x4x5x6x70x5351110100350x612510-1010120x7500-11001－σj=cj-zj3501000列初始單純形表156.2單純形法計(jì)算步驟目前八十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj3501000θCBxBbx1x2x3x4x5x6x70x523-40111-10235x212510-1010－0x7500-110015σj=cj-zj-220060-5016列新單純形表6.2單純形法計(jì)算步驟目前八十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj3501000θCBxBbx1x2x3x4x5x6x70x518-40201-1-195x21751-10011－1x4500-11001－σj=cj-zj-220600-5－626列新單純形表6.2單純形法計(jì)算步驟目前九十頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj3501000θCBxBbx1x2x3x4x5x6x70x39-20100.5-0.5-0.55x22631001x414-20010.5-0.50.5σj=cj-zj-10000-3-2-36.2單純形法計(jì)算步驟目前九十一頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.3人工變量法當(dāng)化為標(biāo)準(zhǔn)形后的約束條件的系數(shù)矩陣中不存在單位矩陣時(shí)，可以人為地增加變量，在最優(yōu)解中人工變量取值必須為零。為此，令目標(biāo)函數(shù)中人工變量的系數(shù)為任意大的負(fù)值－M。亦稱大M法。目前九十二頁\總數(shù)一百二十六頁\編于十七點(diǎn)例1：maxZ=6x1+4x22x1+3x2

1004x1+2x2

120x1=14x2

22x1x2

06.3人工變量法目前九十三頁\總數(shù)一百二十六頁\編于十七點(diǎn)maxZ=6x1+4x22x1+3x2+x3=1004x1+2x2+x4=120x1=14x2-x5=

22x1…x5

0解：化成標(biāo)準(zhǔn)型6.3人工變量法目前九十四頁\總數(shù)一百二十六頁\編于十七點(diǎn)maxZ=6x1+4x2-Mx6-Mx72x1+3x2+x3=1004x1+2x2+x4=120x1+x6=14x2-x5+x7=

22x1…x7

0加人工變量6.3人工變量法目前九十五頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x310023100000x41204201000-Mx6141000010-Mx7220100-101σj=cj-zj列初始單純形表6.3人工變量法目前九十六頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x31002310000500x4120420100030-Mx614100001014-Mx7220100-101

σj=cj-zjM＋6M+400-M000x37203100-200x46402010-406x1141000010-Mx7220100-101

σj=cj-zj0M+400-M6-M06.3人工變量法目前九十七頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x3600103-2-30x42000012-4-26x11410000104x2220100-101

σj=cj-zj000046-M4-M0x52001/301-2/3-10x41600-2/310-8/306x11410000104x224011/300-2/3-2

σj=cj-zj00-4/300-M-10/3-M6.3人工變量法目前九十八頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.4兩階段法為了克服大M法的困難，對(duì)添加人工變量后的線性規(guī)劃問題分兩個(gè)階段來計(jì)算，稱為兩階段法。解題思路：第一階段是先求解一個(gè)目標(biāo)函數(shù)中只包含人工變量的線性規(guī)劃問題，即令目標(biāo)函數(shù)中其它變量的系數(shù)取零，人工變量的系數(shù)取某個(gè)正的常數(shù)(一般取1)，在保持原問題約束條件不變的情況下求這個(gè)目標(biāo)函數(shù)極小化時(shí)的解。顯然在第一階段中，當(dāng)人工變量取值為0時(shí)，目標(biāo)函數(shù)值也為0。這時(shí)候的最優(yōu)解就是原線性規(guī)劃問題的一個(gè)基可行解。目前九十九頁\總數(shù)一百二十六頁\編于十七點(diǎn)作輔助問題minW=yii=1mxj，yi0j=1naijxj+yi

=bi(i=1,2,…,m)原問題maxZ=Cjxjj=1nxj0j=1naijxj=bi(i=1,2,…,m)6.4兩階段法目前一百頁\總數(shù)一百二十六頁\編于十七點(diǎn)解題過程：第1階段：解輔助問題。當(dāng)進(jìn)行到最優(yōu)表時(shí)，①、若W=0,則得到原問題的一個(gè)基本可行解，轉(zhuǎn)入第2階段。②、若W>0,則判定原問題無可行解。第2階段：去除人工變量，求解原問題。第一階段的最優(yōu)解為原問題的初始基可行解。6.4兩階段法目前一百零一頁\總數(shù)一百二十六頁\編于十七點(diǎn)例2：maxZ=-x1+2x2

x1+x2

2-x1+x21x2

3x1x2

0解：第(1)階段：minW=x6+x7

x1+x2-x3+x6=2-x1+x2-x4+x7=1x2+x5=3x1…x7

06.4兩階段法目前一百零二頁\總數(shù)一百二十六頁\編于十七點(diǎn)列初始單純形表Cj00000-1-1θCBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100σj=cj-zj02-1-1000第二階段：去除人工變量，列新單純形表求解。6.4兩階段法目前一百零三頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj00000-1-1θCBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100σj=cj-zj02-1-10006.4兩階段法-1x6120-1101-10x71-110-10010x52100110-1σj=cj-zj20-1100-2目前一百零四頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj00000-1-1θCBxBbx1x2x3x4x5x6x70x11/210-1/21/201/2-1/20x23/201-1/2-1/201/21/20x53/2001/21/21-1/2-1/2σj=cj-zj00000-1-16.4兩階段法-1x6120-1101-11/20x21-110-10010x52100110-12/1σj=cj-zj20-1100-2目前一百零五頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj-12000-1-1θCBxBbx1x2x3x4x5x6x7-1x11/210-1/21/201/2-1/212x23/201-1/2-1/201/21/20x53/2001/21/21-1/2-1/23σj=cj-zj001/23/20-1-16.4兩階段法0x4120-1101-12x2211-100010x51-101010-11σj=cj-zj-302000-2目前一百零六頁\總數(shù)一百二十六頁\編于十七點(diǎn)Cj-12000-1-1θCBxBbx1x2x3x4x5x6x70x42100111/2-1/22x23010011/21/20x31-10101-1/2-1/2σj=cj-zj-6-1000-2-1-16.4兩階段法0x4120-1101-12x2211-100010x51-101010-11σj=cj-zj-302000-2目前一百零七頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.5計(jì)算中的幾個(gè)問題2、退化：（非退化θ值唯一）在下一次迭代中有一個(gè)或幾個(gè)基變量為0，從而出現(xiàn)退化解?？赡軙?huì)導(dǎo)致循環(huán)，永遠(yuǎn)達(dá)不到最優(yōu)解。1、目標(biāo)函數(shù)極小化時(shí)解的最優(yōu)性判別以σi0作為判別表中解是否最優(yōu)的標(biāo)志目前一百零八頁\總數(shù)一百二十六頁\編于十七點(diǎn)則xk進(jìn)基1）若有兩個(gè)以上檢驗(yàn)數(shù)如何解決退化問題？

Dantzig規(guī)則：6.5計(jì)算中的幾個(gè)問題目前一百零九頁\總數(shù)一百二十六頁\編于十七點(diǎn)6.5計(jì)算中的幾個(gè)問題

1951年Hoffman給出反例。（3個(gè)方程，11個(gè)變量）1955年E.M.L.Beale3個(gè)方程，7個(gè)變量。6次迭代后，出現(xiàn)循環(huán)。

按照Dantzig規(guī)則：（5，6，7）（1，6，7）（1，2，7）（3，2，7）（