線性規(guī)劃的數(shù)學(xué)模型與基本性質(zhì)

線性規(guī)劃及單純形法

1．線性規(guī)劃介紹

2．線性規(guī)劃數(shù)學(xué)模型

3．線性規(guī)劃標(biāo)準(zhǔn)形式

4．線性規(guī)劃的圖解法

5．線性規(guī)劃基本概念

6．單純形法

7．應(yīng)用舉例1．線性規(guī)劃介紹歷史悠久，理論成熟，應(yīng)用廣泛運籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費用最小或獲得的收益最大。線性規(guī)劃理論的發(fā)展：1939年前蘇聯(lián)康托洛維奇（KOHTOPOBUZ）《生產(chǎn)組織與計劃中的數(shù)學(xué)方法》提出“解乘數(shù)法”。1．線性規(guī)劃介紹列奧尼德·康托羅維奇，前蘇聯(lián)人，由于在1939年創(chuàng)立了享譽全球的線形規(guī)劃要點，對資源最優(yōu)分配理論做出了貢獻，而獲得諾貝爾經(jīng)濟學(xué)獎。美國科學(xué)院院士DANTZIG（丹齊克），1948年在研究美國空軍資源的優(yōu)化配置時提出線性規(guī)劃及其通用解法“單純形法”。被稱為線性規(guī)劃之父。1．線性規(guī)劃介紹

線性規(guī)劃之父的Dantzig(丹齊克)。據(jù)說，一次上課，Dantzig遲到了，仰頭看去，黑板上留了幾個幾個題目，他就抄了一下，回家后埋頭苦做。幾個星期之后，疲憊的去找老師說，這件事情真的對不起，作業(yè)好像太難了，我所以現(xiàn)在才交，言下很是慚愧。幾天之后，他的老師就把他召了過去，興奮的告訴他說他太興奮了。Dantzig很不解,后來才知道原來黑板上的題目根本就不是什么家庭作業(yè)，而是老師說的本領(lǐng)域的未解決的問題，他給出的那個解法也就是單純形法。這個方法是上個世紀(jì)前十位的算法。1．線性規(guī)劃介紹1960年，“最佳資源利用的經(jīng)濟計算”康托洛維奇和庫伯曼斯(Koopmans)。兩人因?qū)Y源最優(yōu)分配理論的貢獻而獲1975年諾貝爾經(jīng)濟學(xué)獎

佳林·庫普曼斯，美國人，他將數(shù)理統(tǒng)計學(xué)成功運用于經(jīng)濟計量學(xué)，對資源最優(yōu)分配理論做出了貢獻。1961年，查恩斯與庫伯提出了目標(biāo)規(guī)劃，艾吉利提出了用優(yōu)先因子來處理多目標(biāo)問題。20世紀(jì)70年代，斯．姆．李與杰斯開萊尼應(yīng)用計算機處理目標(biāo)規(guī)劃問題。計算機50約束100變量

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

例1美佳公司計劃制造I，II兩種家電產(chǎn)品。已知各制造一件時分別占用的設(shè)備A、B的臺時、調(diào)試時間及A、B設(shè)備和調(diào)試工序每天可用于這兩種家電的能力、各售出一件時的獲利情況如表I—l所示。問該公司應(yīng)制造A、B兩種家電各多少件，使獲取的利潤為最大？項目III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤（元）212．線性規(guī)劃數(shù)學(xué)模型例2捷運公司擬在下一年度的1-4月的4個月內(nèi)需租用倉庫堆放物資。已知各月份所需倉庫面積數(shù)列見下表。倉庫租借費用隨合同期定，期限越長折扣越大，具體數(shù)字見下表。租借倉庫的合同每月初都可辦理，每份臺同具體現(xiàn)定租用面積數(shù)和期限。因此該廠可根據(jù)需要，在任何一個月初辦理租借臺同。每次辦理時可簽一份，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費用最小。月份1234所需倉庫面積15102012合同租借期限1個月2個月3個月4個月合同期內(nèi)的租費28004500600073002．線性規(guī)劃數(shù)學(xué)模型目標(biāo)函數(shù)約束條件解：用變量x1和x2分別表示美佳公司制造家電I和II的數(shù)量。項目III每天可用能力設(shè)備A（h）設(shè)備B（h）調(diào)試工序（h）06152115245利潤（元）21例1用數(shù)學(xué)語言描述2．線性規(guī)劃數(shù)學(xué)模型解：設(shè)變量xij表示捷運公司在第i(i＝1．…，4)個月初簽訂的租借期為j〔j＝1，…，4)個月的倉庫面積的合同(單位為100m2)。約束條件目標(biāo)函數(shù)例2月份1234所需倉庫面積15102012合同租借期限1個月2個月3個月4個月合同期內(nèi)的租費28004500600073002．線性規(guī)劃數(shù)學(xué)模型AB備用資源煤1230

勞動日3260

倉庫0224

利潤4050求：最大利潤的生產(chǎn)計劃。練習(xí)1生產(chǎn)計劃問題2．線性規(guī)劃數(shù)學(xué)模型maxZ=40x1+50x2解:設(shè)產(chǎn)品A,B產(chǎn)量分別為變量x1

，x2x1

+2x2

303x1+2x2

602x2

24x1，x2

0s.t.2．線性規(guī)劃數(shù)學(xué)模型求：最低成本的原料混合方案？

原料ABＣ每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量練習(xí)2混合配料問題2．線性規(guī)劃數(shù)學(xué)模型解：設(shè)每單位添加劑中原料i的用量為xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x4

4x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)s.t.2．線性規(guī)劃數(shù)學(xué)模型決策變量：向量(x1…xn)T

決策人要考慮和控制的因素。非負(fù)約束條件：線性等式或不等式目標(biāo)函數(shù)：Z=?(x1

…xn)線性式，求Z極大或極小線性規(guī)劃模型特點2．線性規(guī)劃數(shù)學(xué)模型如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值可以是連續(xù)的，目標(biāo)函數(shù)是決策變量的線性函數(shù)，約束條件是含決策變量的線性等式或不等式，則該類規(guī)劃問題的數(shù)學(xué)模型稱為線性規(guī)劃的數(shù)學(xué)模型。實際問題中線性的含義：一是嚴(yán)格的比例性二是可疊加性關(guān)于線性的界定2．線性規(guī)劃數(shù)學(xué)模型19max(min)Z=c1x1+c2x2+…+cnxnn個變量價值系數(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é)模型線性規(guī)劃的簡寫式2．線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃的向量表示式2．線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃的矩陣表示式2．線性規(guī)劃數(shù)學(xué)模型比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比；可加性：每個決策變量對目標(biāo)和約束的影響?yīng)毩⒂谄渌兞浚贿B續(xù)性：每個決策變量取連續(xù)值；確定性：線性規(guī)劃中的參數(shù)aij,bi,ci為確定值。隱含的假設(shè)2．線性規(guī)劃數(shù)學(xué)模型倉庫\工廠123庫存

121350222430334210

需求401535練習(xí)3運輸問題工廠需要的原棉存放在三個倉庫中，現(xiàn)將原棉運往工廠以滿足工廠生產(chǎn)的需求。已知原棉運到各個工廠的單位運費如表所示。問使總運費最小的運輸方案？2．線性規(guī)劃數(shù)學(xué)模型解：設(shè)xij為i

倉庫運到j(luò)工廠的原棉數(shù)量(i

=1,2,3j=1,2,3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x13

50x21+x22+x23

30x31+x32+x33

10x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij

0st.2．線性規(guī)劃數(shù)學(xué)模型練習(xí)4連續(xù)投資10萬元A：從第1年到第4年每年初投資，次年末回收本利1.15；B：第3年初投資，到第5年末回收本利1.25，最大投資4萬元；C：第2年初投資，到第5年末回收本利1.40，最大投資3萬元；D：每年初投資，每年末回收本利1.11。求：使5年末總資本最大的投資方案。分析：

12345Ax1A

x2A

x3A

x4ABx3BCx2CDx1Dx2Dx3Dx4Dx5D2．線性規(guī)劃數(shù)學(xué)模型解：xik(i=1,2,…,5;k=A,B,C,D)為第i年初投資到第k個項目的資金數(shù)。MaxZ=1.15x4A+1.40x2C+1.25x3B+1.11x5Dx1A+x1D=10x2A+x2C+x2D=1.11x1Dx2C

3x3A+x3B+x3D=1.15x1A+

1.11x2Dx3B

4x4A+x4D=1.15x2A+

1.11x3Dx5D=1.15x3A+

1.11x4Dxik0s.t.2．線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃問題應(yīng)用市場營銷(廣告預(yù)算和媒介選擇，競爭性定價，新產(chǎn)品開發(fā)，制定銷售計劃)生產(chǎn)計劃制定(合理下料，配料，“生產(chǎn)計劃、庫存、勞力綜合”)庫存管理(合理物資庫存量，停車場大小，設(shè)備容量)運輸問題財政、會計(預(yù)算，貸款，成本分析，投資，證券管理)人事(人員分配，人才評價，工資和獎金的確定)設(shè)備管理(維修計劃，設(shè)備更新)城市管理(供水，污水管理，服務(wù)系統(tǒng)設(shè)計、運用)2．線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃的適用情況要解決的問題的目標(biāo)可以用數(shù)值指標(biāo)反映對于要實現(xiàn)的目標(biāo)有多種方案可選擇有影響決策的若干約束條件2．線性規(guī)劃數(shù)學(xué)模型線性規(guī)劃模型的結(jié)構(gòu)目標(biāo)函數(shù)：max，min約束條件：≥,=,≤變量符號：：≥0,≤0線性規(guī)劃的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)：max約束條件 ：=變量符號 ：≥03．線性規(guī)劃標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)型的一般型minz=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)形式P1P2………Pna11a12………a1n其中A=a21a22………

a2n

…am1am2………amnx1x=x2

xn…

b1b=b2

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

3．線性規(guī)劃標(biāo)準(zhǔn)形式x1Ax=(P1P2…Pn)x2=b

xn

…P1x1+

P2x2+…+Pnxn=b標(biāo)準(zhǔn)型的向量型3．線性規(guī)劃標(biāo)準(zhǔn)形式線性規(guī)劃問題化標(biāo)準(zhǔn)型：(1)、約束條件(2)、變量(3)、目標(biāo)函數(shù)(4)、右端常數(shù)3．線性規(guī)劃標(biāo)準(zhǔn)形式(1)、約束條件x3為松弛變量x4為剩余變量

松弛變量或剩余變量在實際問題中分別表示未被充分利用的資源和超出的資源數(shù)，均未轉(zhuǎn)化為價值和利潤，所以引進模型后它們在目標(biāo)函數(shù)中的系數(shù)均為零。當(dāng)約束條件為“”時：當(dāng)約束條件為“”時：3．線性規(guī)劃標(biāo)準(zhǔn)形式3．線性規(guī)劃標(biāo)準(zhǔn)形式

x1+2x2+x3=30s.t.3x1+2x2+x4=60

2x2

+x5=24x1,

…,x50轉(zhuǎn)化為：minZ=40x1+50x2+0-x3

+0·x4+0·x5

x1

+2x2

303x1+2x2

60s.t.2x2

24

x1，x2

0

例：minZ=40x1+50x2松弛變量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

=12

x1+x2+7x3+5x4-x6=14

2x2+x3+3x4-x7=8

x1,

…,x70剩余變量(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)形式x1'

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

10+6

令x1'

=x1+6

0x1'

163．線性規(guī)劃標(biāo)準(zhǔn)形式(3)、目標(biāo)函數(shù)xo-ZZ令Z'

=-Z

3．線性規(guī)劃標(biāo)準(zhǔn)形式(4)、右端常數(shù)右端項b＜0時，只需將等式或不等式兩端同乘(一1)，則等式右端項必大于零。3．線性規(guī)劃標(biāo)準(zhǔn)形式例3：將maxZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3無限制化為標(biāo)準(zhǔn)型3．線性規(guī)劃標(biāo)準(zhǔn)形式解：①令x3=x4-

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

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

x2,

x4,…,x70maxZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1，x20，x3無限制3．線性規(guī)劃標(biāo)準(zhǔ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)形式(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)形式Ax=b(1)x

0(2)maxZ=(3)定義1：滿足約束(1)、(2)的x=(x1…xn)T稱為LP問題的可行解，全部可行解的集合稱為可行域。定義2：滿足(3)的可行解稱為LP問題的最優(yōu)解線性規(guī)劃的標(biāo)準(zhǔn)型4．線性規(guī)劃的圖解法圖解法求解的目的：一是判別線性規(guī)劃問題的求解結(jié)局；二是在存在最優(yōu)解的條件下，把問題的最優(yōu)解找出來。

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

x1+2x2303x1+2x2602x224

x1,x204．線性規(guī)劃的圖解法解：(1)、確定可行域

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

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

2x2=24203010x14．線性規(guī)劃的圖解法(2)、求最優(yōu)解最優(yōu)解：x*=(15,7.5)Zmax=975Z=40x1+50x20=40x1+50x2(0,0)，(10,-8)x20102030203010x1DABCC點：x1+2x2=30

3x1+2x2=604．線性規(guī)劃的圖解法Z=40x1+80x2=0

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

x1,x204．線性規(guī)劃的圖解法4．線性規(guī)劃的圖解法X1=6+(1-)·15X2=12+(1-)·7.5X1=15-9X2=7.5+4.5(01)X==+(1-)maxZ=1200

X1615

X2127.5無界解無有限最優(yōu)解例6、maxZ=2x1+4x2

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

=bx0Am×n滿秩x

=(x1…xn)T

一、線性規(guī)劃問題的解的概念5．線性規(guī)劃基本概念定義1：基(基陣)——設(shè)A為約束方程組的m×n階系數(shù)矩陣設(shè)(n>m)，其秩為m，B是矩陣A中的一個m×m階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個基。P1P2…Pm……Pna11a12…

a1m……a1nA=a21a22…

a2m……

a2n

……am1am2…

amm……amnB5．線性規(guī)劃基本概念A(yù)=(P1…

PmPm+1…

Pn)=(BN)

基向量非基向量…x=(x1…

xmxm+1…

xn)T=(xBxN)T

基變量非基變量

xB

xN…B中的每一個列向量Pj稱為基向量，與基向量對應(yīng)的變量稱為基變量，其他變量稱為非基變量。5．線性規(guī)劃基本概念A(yù)x=b的求解xBxN(BN)=bBxB+NxN=bBxB=b-NxNxB=B-1b-B-1NxNA=(BN)x=(xBxN)T若B為單位矩陣xB=b-NxN若xN＝0xB=B-1b5．線性規(guī)劃基本概念定義2：可行解——滿足方程約束條件的解x＝（x1，x2，…xn)T,稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。定義3：最優(yōu)解——使目標(biāo)函數(shù)達到最大值的可行解，稱為最優(yōu)解。5．線性規(guī)劃基本概念定義4：基本解——對應(yīng)于基B，x=為Ax=b的一個解，則x為線性規(guī)劃問題的基本解，也稱基解。B-1b0定義5：基本可行解——基B，基本解x=若B-1b0，稱基解為基本可行解，也稱基可行解。B-1b0※基本解中最多有m個非零分量。※基本解的數(shù)目不超過Cnm=個。n!m!(n-m)!定義6：可行基——對應(yīng)于基可行解的基稱為可行基。5．線性規(guī)劃基本概念例8x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50121003201002001P1P2P3P4P5A=5．線性規(guī)劃基本概念x1x2x3x4x5x=b=306024B=(P3P4P5)=I

是滿秩子矩陣

非基N=(P1P2)x3=30-(x1+2x2)x4=60-(3x1+2x2)x5=24-2x25．線性規(guī)劃基本概念令x1=

x2=0,x3=30,x4=60,x5=24x===xN0xBB-1b003060245．線性規(guī)劃基本概念例9：給定約束條件

-x3+x4=0x2+x3+x4=3-x1+x2+x3+x4=2xj0(j=1,2,3,4)求出基變量是x1,x3,x4的基本解，是不是可行解？5．線性規(guī)劃基本概念

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

01-10B-1=-1/21/2031/21/202b=5．線性規(guī)劃基本概念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ī)劃基本概念凸集——D是n維空間的一個集合，x(1),

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

x(2)，有x=x(1)+(1-)x(2)∈D(01)，則D為凸集。定義1：凸集——如果集合D中任意兩個點，其連線上的所有點也都是集合D中的點，則稱D為凸集。二、凸集及其頂點5．線性規(guī)劃基本概念x(1)x(2)凸多邊形凹多邊形x(1)x(2)5．線性規(guī)劃基本概念第一章

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

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

μ1,μ2,…,μk

滿足

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

i=1ki=1有點x=μ1x(1)

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

的凸組合。凸組合5．線性規(guī)劃基本概念

凸集D,點xD，若找不到兩個不同的點x(1),x(2)D使得

x=x(1)

+(1-)x(2)

(0<<1)

則稱x為D的頂點。定義3頂點5．線性規(guī)劃基本概念證明：設(shè)LP問題的可行解域為集合CC={x|Ax=bx0}任取x(1),x(2)C,則

x=x(1)

+(1-)x(2)

0

(0

1)又因為Ax(1)

=b，Ax(2)

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

+(1-)x(2)

]=b

+(1-)b=b

則

xC，C為凸集定理1：LP問題的可行解域一定是凸集。三、幾個基本定理的證明5．線性規(guī)劃基本概念只須證明：

D的k個頂點x(1),…,x(k)

，有

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

+…+μkx(k)μ

i=1ki=15．線性規(guī)劃基本概念證明可用歸納法（略）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è)x(1),…,x(k)

為可行域頂點，若x*不是頂點，但

maxZ=Cx*

定理2：可行域有界，最優(yōu)值必可在頂點得到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ī)劃基本概念引理2：LP問