運籌學(線性規(guī)劃)_第1頁
運籌學(線性規(guī)劃)_第2頁
運籌學(線性規(guī)劃)_第3頁
運籌學(線性規(guī)劃)_第4頁
運籌學(線性規(guī)劃)_第5頁
已閱讀5頁,還剩133頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

線性規(guī)劃之父的Dantzig(丹齊克)。據(jù)說,一次上課,Dantzig遲到了,仰頭看去,黑板上留了幾個幾個題目,他就抄了一下,回家后埋頭苦做。幾個星期之后,疲憊的去找老師說,這件事情真的對不起,作業(yè)好像太難了,我所以現(xiàn)在才交,言下很是慚愧。幾天之后,他的老師就把他召了過去,興奮的告訴他說他太興奮了。Dantzig很不解,后來才知道原來黑板上的題目根本就不是什么家庭作業(yè),而是老師說的本領域的未解決的問題,他給出的那個解法也就是單純形法。這個方法是上個世紀前十位的算法。

page4線性規(guī)劃介紹

1960年,“最佳資源利用的經濟計算”康托洛維奇和庫伯曼斯(Koopmans)。兩人因對資源最優(yōu)分配理論的貢獻而獲1975年諾貝爾經濟學獎

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

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

page8線性規(guī)劃(LinearProgramming)

LP的數(shù)學模型圖解法單純形法單純形法的進一步討論-人工變量法

LP模型的應用本章主要內容:page9生產和經營管理中經常提出如何合理安排,使人力、物力等各種資源得到充分利用,獲得最大的效益,這就是規(guī)劃問題。線性規(guī)劃通常解決下列兩類問題:(1)當任務或目標確定后,如何統(tǒng)籌兼顧,合理安排,用最少的資源(如資金、設備、原標材料、人工、時間等)去完成確定的任務或目標(2)在一定的資源條件限制下,如何組織安排生產獲得最好的經濟效益(如產品量最多、利潤最大.)線性規(guī)劃問題的數(shù)學模型1.規(guī)劃問題page10

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

某企業(yè)計劃生產甲、乙兩種產品。這些產品分別要在A、B、C、D、四種不同的設備上加工。按工藝資料規(guī)定,單件產品在不同設備上加工所需要的臺時如下表所示,企業(yè)決策者應如何安排生產計劃,使企業(yè)總的利潤最大?設備產品ABCD利潤(元)

2

1

4

0

2

2

2

0

4

3有效臺時12

81612線性規(guī)劃問題的數(shù)學模型page17解:設x1、x2分別為甲、乙兩種產品的產量,則數(shù)學模型為:maxZ=2x1+3x2

x1≥0,x2≥0s.t.

2x1+2x2≤12x1+2x2≤84x1≤164x2≤12運輸問題page18問題分析page19模型page20

AB備用資源煤1230

勞動日3260

倉庫0224

利潤4050求:最大利潤的生產計劃。練習1生產計劃問題線性規(guī)劃數(shù)學模型page21maxZ=40x1+50x2解:設產品A,B產量分別為變量x1

,x2x1

+2x2

303x1+2x2

602x2

24x1,x2

0s.t.線性規(guī)劃數(shù)學模型page22求:最低成本的原料混合方案?

原料ABC每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量練習2混合配料問題線性規(guī)劃數(shù)學模型page23

原料ABC每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量

原料ABC每單位成本

14102261253171642538

每單位添加劑中維生12148

素最低含量解:設每單位添加劑中原料i的用量為xi(i=1,2,3,4)minZ=2x1

+5x2+6x3+8x44x1

+6x2+x3+2x412x1

+x2+7x3+5x4142x2

+x3+3x4

8

xi

0(i=1,…,4)線性規(guī)劃數(shù)學模型page24s.t.2.線性規(guī)劃的數(shù)學模型由三個要素構成決策變量Decisionvariables目標函數(shù)Objectivefunction約束條件Constraints其特征是:(1)問題的目標函數(shù)是多個決策變量的線性函數(shù),通常是求最大值或最小值;(2)問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型?

線性規(guī)劃問題的數(shù)學模型page25線性規(guī)劃問題的數(shù)學模型page26目標函數(shù):約束條件:3.線性規(guī)劃數(shù)學模型的一般形式簡寫為:注釋page27概念page28線性規(guī)劃問題的數(shù)學模型page29向量形式:其中:線性規(guī)劃問題的數(shù)學模型page30矩陣形式:其中:比例性:決策變量變化引起目標的改變量與決策變量改變量成正比;可加性:每個決策變量對目標和約束的影響獨立于其它變量;連續(xù)性:每個決策變量取連續(xù)值;確定性:線性規(guī)劃中的參數(shù)aij,bi,ci為確定值。隱含的假設線性規(guī)劃數(shù)學模型page31線性規(guī)劃的適用情況要解決的問題的目標可以用數(shù)值指標反映對于要實現(xiàn)的目標有多種方案可選擇有影響決策的若干約束條件線性規(guī)劃數(shù)學模型page32線性規(guī)劃問題的數(shù)學模型page333.線性規(guī)劃問題的標準形式特點:(1)目標函數(shù)求最大值(有時求最小值)(2)約束條件都為等式方程,且右端常數(shù)項bi都大于或等于零(3)決策變量xj為非負。規(guī)范形式page34線性規(guī)劃問題的數(shù)學模型模型轉換約束轉換目標轉換變量轉換實例page35約束轉換不等式變等式等式變不等式不等式變不等式page36不等式變等式松弛變量剩余變量page37不等式變不等式page38例5:將minZ=-x1+2x2-3x3x1+x2+x37x1-x2+x32x1,x20,x3無限制化為標準型線性規(guī)劃標準形式page39解:①令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無限制線性規(guī)劃標準形式page40

例6

把問題轉化為標準形式page41(1)minZ=2x1-x2+2x3練習3將下列線性規(guī)劃問題化成標準型:-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.線性規(guī)劃標準形式(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.線性規(guī)劃標準形式page43定義1:滿足約束(2)、(3)的x=(x1…xn)T稱為LP問題的可行解,全部可行解的集合稱為可行域。定義2:滿足(1)的可行解稱為LP問題的最優(yōu)解線性規(guī)劃的標準型4.線性規(guī)劃的圖解法page44maxZ=Cx(1)Ax=b(2)x

0(3)圖解法求解的目的:一是判別線性規(guī)劃問題的求解結局;二是在存在最優(yōu)解的條件下,把問題的最優(yōu)解找出來。

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

x1+2x2303x1+2x2602x224

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

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

2x2=244.線性規(guī)劃的圖解法0102030DABC203010x1page48(2)、求最優(yōu)解最優(yōu)解:x*=(15,7.5)

Zmax

=975Z=40x1+50x20=40x1+50x2(0,0),(10,-8)C點:x1+2x2=30

3x1+2x2=604.線性規(guī)劃的圖解法page490102030DABC203010x1x2Z=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)例8、maxZ=40x1+80x2

x1+2x2303x1+2x2602x224

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

X1615

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

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

maxZ=5x1+6x2x1

-2x2

2

-2x1

+3x22x1,

x2

無約束

s.t.4.線性規(guī)劃的圖解法page56maxZ=CxAx

=bx0Am×n

滿秩

x

=(x1…xn)T

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

P1P2…Pm……Pna11a12…

a1m……a1nA=a21a22…

a2m……

a2n

……am1am2…

amm

……amnB5.線性規(guī)劃基本概念page58A=(P1…

PmPm+1…

Pn

)=(BN)

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

xm

xm+1…

xn

)T=(xB

xN)T

基變量非基變量

xB

xN…B中的每一個列向量Pj稱為基向量,與基向量對應的變量稱為基變量,其他變量稱為非基變量。5.線性規(guī)劃基本概念page59Ax=b的求解xB

xN(BN)=bBxB

+NxN=bBxB

=b-NxNxB

=B-1b-B-1NxNA=(BN)x=(xB

xN

)T若B為單位矩陣xB

=b-NxN若xN=0xB

=B-1b5.線性規(guī)劃基本概念page60定義2:可行解——滿足方程約束條件的解x=(x1,x2,…xn)T,稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。定義3:最優(yōu)解——使目標函數(shù)達到最大值的可行解,稱為最優(yōu)解。5.線性規(guī)劃基本概念page61定義4:基本解——對應于基B,x=為Ax=b的一個解,則x為線性規(guī)劃問題的基本解,也稱基解。B-1b0定義5:基本可行解——基B,基本解x=若B-1b0,稱基解為基本可行解,也稱基可行解。

B-1b0※基本解中最多有m個非零分量?!窘獾臄?shù)目不超過Cnm=個。n!m!(n-m)!定義6:可行基——對應于基可行解的基稱為可行基。5.線性規(guī)劃基本概念page62例11x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1…x50121003201002001P1P2P3P4P5A=5.線性規(guī)劃基本概念page63x1x2x3x4x5x=b=306024B=(P3P4P5)=I

是滿秩子矩陣

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

x2=0,x3=30,x4=60,x5=2400306024x===xN

0xB

B-1b5.線性規(guī)劃基本概念page65例12:給定約束條件

-x3+x4=0x2+x3+x4=3-x1+x2+x3+x4=2

xj

0(j=1,2,3,4)求出基變量是x1,x3,x4的基本解,是不是可行解?5.線性規(guī)劃基本概念page66

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

01-10B-1=-1/21/2031/21/202b=5.線性規(guī)劃基本概念page67

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ī)劃基本概念page68線性規(guī)劃解之間的關系線性規(guī)劃解之間的關系:可行解基本解非可行解基本可行解最優(yōu)解page69退化基本可行解與退化基1、退化基本可行解:基本可行解中存在取零值的基變量,則稱該基本可行解為退化的基本可行解。2、退化基:退化的基本可行解對應的基,稱為退化基。page70凸集——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ī)劃基本概念page71x(1)x(2)凸多邊形凹多邊形x(1)x(2)5.線性規(guī)劃基本概念page72

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ī)劃基本概念page73

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

x=x(1)

+(1-)x(2)

(0<<1)

則稱x為D的頂點。定義3頂點5.線性規(guī)劃基本概念page74證明:設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ī)劃基本概念page75只須證明:

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

,有

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

+…+μkx(k)μ

i=1ki=15.線性規(guī)劃基本概念page76證明可用歸納法(略)x(1)x(2)x(3)x’xx’在邊界上x在內部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ī)劃基本概念page77證明:設x(1),…,x(k)

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

maxZ=Cx*

定理2:可行域有界,最優(yōu)值必可在頂點得到Cx*=μ

iC

x(i)ki=1μ

iCx(m)ki=1=Cx(m)[設Cx(m)=Max(C

x(i))]1ikμ

ix(i)ki=1μ

i=1ki=10μi1x*=5.線性規(guī)劃基本概念page78引理2:LP問題的可行解x是基本可行解x的非0分量對應的系數(shù)列向量線性無關證明:(1)必要性。由基可行解的定義顯然。(2)充分性。若向量P1,P2,…

Pk線性獨立,則必有k

m。

當k=m時,它們恰好構成一個基,從而x=(x1,x2,…,xm,0,…,0)為相應的基可行解。當k<m時,則一定可從其余列向量中找出(m-k)個與P1,P2,…,Pk構成一個基,其對應的解恰為x,所以據(jù)定義它是基可行解。5.線性規(guī)劃基本概念page79證明(反證法):()假設x不是基本可行解x=(x1,…,xn

)Txj

>0j=1,…,kxj

=0j=k+1,…,n由引理2知,p1,…,pk

線性相關必有不全為0的1,…,

k使1p1+…+

k

pk

=0做=(1,…,

k,0…,0)T則有A

=1p1+…+

k

pk

=0可行域C中點x是頂點x是基本可行解定理3:5.線性規(guī)劃基本概念page80選任一不為零的數(shù)令

x(1)

=x+

0

x(2)

=x-

0又Ax(1)

=Ax+A=b

Ax(2)

=Ax-A=b

所以x(1)Cx(2)C因為x=1/2x(1)+1/2x(2)所以x不是可行域的頂點5.線性規(guī)劃基本概念page81證明:()不是頂點,不是基可行解設x為可行解xj

>0j=1,…,kxj

=0j=k+1,…,n若x不是頂點,則有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ī)劃基本概念page82因為>0,1->0,xj

(1)

0,xj

(2)

0所以xj

(1)=

xj

(2)=

0(j=k+1,…,n)因為Ax(1)

=bAx(2)

=bp

jxj(1)=bnj=1p

jxj(2)=bnj=1即p1x1(1)+…+pk

xk(1)=b(a)p1x1(2)+…+pk

xk(2)=b(b)5.線性規(guī)劃基本概念page83由(a)-(b)得(x1(1)-x1(2))p1+…+(xk(1)-xk(2))pk=0即x不是基可行解所以p1,…,pk

線性相關定理4若線性規(guī)劃問題有最優(yōu)解,一定存在一個基可行解是最優(yōu)解。5.線性規(guī)劃基本概念page84

(LP)問題的基本可行解可行域的頂點。若(LP)問題有最優(yōu)解,必可以在基本可行解(頂點)達到。若(LP)問題有可行解,則可行解集(可行域)是凸集(可能有界,也可能無界),有有限個頂點。5.線性規(guī)劃基本概念LP問題解的性質page856.單純形法

6.1、單純形法迭代原理

6.2、單純形法計算步驟

6.3、人工變量法

6.4、兩階段法

6.5、計算中的幾個問題page866.1單純形法迭代原理一、確定初始基可行解二、從一個基可行解轉換為相鄰基可行解三、最優(yōu)性檢驗和解的判別page87A中總存在一個單位矩陣(P1,P2,…,Pm)。一、確定初始基可行解當約束條件為時,加上松馳變量的系數(shù)矩陣即為單位矩陣。當約束條件為或=時,可以構造人工基,人為產生一個單位矩陣。基向量、基變量、非基向量、非基變量可得初始基可行解:x=(x1,…,xm,xm+1,…xn)T=(b1,…,bm,0,…,0)T6.1單純形法迭代原理page88兩個基可行解相鄰指的是它們之間變換且僅變換一個基變量。設x(0)=(x10,x20,…xm0,0,…0)T,有Pixi0=bmi=1系數(shù)矩陣的增廣矩陣二、基可行解的轉換6.1單純形法迭代原理page89Pj=aijPimi=1Pj-

aijPi=0

mi=1兩邊乘上一個正數(shù)θ>0,得θ

(Pj-aij

Pi)=0

mi=1同相加整理得:Pixi0=bmi=1所以得到另一個點x(1),使Pixi(1)=bni=1可行解?基解?6.1單純形法迭代原理page90所以x(1)是可行解令存在:6.1單純形法迭代原理page91重新排列后不含非基向量的增廣矩陣:因alj>0,故上述矩陣元素組成的行列式不為零,P1,P2,…Pl-1,Pj,Pl+1,…,Pm

是一個基。所以,x(1)

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

θal+1,j,…bm-amj)T由此x(1)是x(0)相鄰的基可行解,且由基向量組成的矩陣仍為單位矩陣。x(1)=(b1-θa1j,…,bl-1-θal-1,j,θ,bl+1-

θal+1,j,…bm-amj)T

?6.1單純形法迭代原理page93將基本可行解x(0)和x(1)分別代入目標函數(shù)得:三、最優(yōu)性檢驗和解的判別6.1單純形法迭代原理page94是對線性規(guī)劃問題的解進行最優(yōu)性檢驗的標志。當所有的σi<=0時,現(xiàn)有頂點為最優(yōu)解。當所有的σi<=0時,又對某個非基變量xj,有Cj-Zj=0,且可找到θ

>0,則有無窮多最優(yōu)解。當存在某個σj>0,又Pj<=0,則有無界解。通常簡寫為6.1單純形法迭代原理page951)找出初始基可行解,建立單純形表。6.2單純形法計算步驟Cjc1…cm…cj…cnCBxBbx1…xm…xj…xnc1x1b110…a1j…a1nc2x2b200…a2j…a2n…………….……………cmxmbm01…amj…amn

σj=cj-zj0…0……page966.2單純形法計算步驟

5)以a’l,k為主元素進行旋轉運算,轉2)。3)若,使得但則此問題無界解,停止.否則,轉下一步.page97例13用單純形法求解線性規(guī)劃問題maxZ=2x1+x25x2

156x1

+2x2

24x1

+x2

5x1,

x2

0s.t.6.2單純形法計算步驟page98解:1、先將上述問題化成標準形式有maxZ=2x1+x2+0·x3+0·x4+0·x56.2單純形法計算步驟找到一個初始基可行解x=(0,0,15,24,5)

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

+x5=5

x1,

…,x50page992、列初始單純形表:因為σ1>σ2,確定x1為換入變量。因為θ=min{-,24/6,5/}=4所以6為主元素,x4為換出變量。Cj21000θCBxBbx1x2x3x4x50x315051000x424620100x5511001

σj=cj-zj6.2單純形法計算步驟page1003、列新單純形表:因為σ2>0

,確定x2為換入變量。因為θ=min{15/5,4/2/6,1/4/6}=3/2。所以4/6為主元素,x5為換出元素。Cj21000θCBxBbx1x2x3x4x50x315051002x1412/601/600x5104/60-1/61

σj=cj-zj6.2單純形法計算步驟page1014、列新單純形表:因為Cj-Zj<0,所以達到最優(yōu)解。最優(yōu)解為:x=(7/2,3/2,15/2,0,0)。目標函數(shù)值為Z=2×7/2+1×3/2+0×15/2+0+0=8.5Cj21000θCBxBbx1x2x3x4x50x315/20015/4-15/22x17/21001/4-1/21x23/2000-1/42/3

σj=cj-zj6.2單純形法計算步驟page102練習題解:原問題化為標準型6.2單純形法計算步驟page103Cj3501000θCBxBbx1x2x3x4x5x6x70x5351110100350x612510-1010120x7500-11001-

σj=cj-zj3501000列初始單純形表156.2單純形法計算步驟page104Cj3501000θCBxBbx1x2x3x4x5x6x70x523-40111-10235x212510-1010-0x7500-110015

σj=cj-zj-220060-5016列新單純形表6.2單純形法計算步驟page105Cj3501000θCBxBbx1x2x3x4x5x6x70x518-40201-1-195x21751-10011-1x4500-11001-

σj=cj-zj-220600-5-626列新單純形表6.2單純形法計算步驟page106Cj3501000θCBxBbx1x2x3x4x5x6x70x39-20100.5-0.5-0.55x22631001x414-20010.5-0.50.5

σj=cj-zj-10000-3-2-36.2單純形法計算步驟page1076.3人工變量法當化為標準形后的約束條件的系數(shù)矩陣中不存在單位矩陣時,可以人為地增加變量,在最優(yōu)解中人工變量取值必須為零。為此,令目標函數(shù)中人工變量的系數(shù)為任意大的負值-M。亦稱大M法。page108例1:maxZ=6x1+4x22x1+3x2

1004x1+2x2

120x1=14x2

22x1x2

06.3人工變量法page109maxZ=6x1+4x22x1+3x2+x3=1004x1+2x2+x4=120x1=14x2-x5=

22x1…x5

0解:化成標準型6.3人工變量法page110maxZ=6x1+4x2-Mx6-Mx72x1+3x2+x3=1004x1+2x2+x4=120x1+x6=14x2-x5+x7=

22x1…x7

0加人工變量6.3人工變量法page111Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x310023100000x41204201000-Mx6141000010-Mx7220100-101

σj=cj-zj列初始單純形表6.3人工變量法page112Cj64000-M-MθCBxBbx1x2x3x4x5x6x70x31002310000500x4120420100030-Mx614100001014-Mx7220100-101

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

σj=cj-zj0M+400-M6-M06.3人工變量法page113Cj64000-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人工變量法page114Cj64000-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.4兩階段法為了克服大M法的困難,對添加人工變量后的線性規(guī)劃問題分兩個階段來計算,稱為兩階段法。解題思路:第一階段是先求解一個目標函數(shù)中只包含人工變量的線性規(guī)劃問題,即令目標函數(shù)中其它變量的系數(shù)取零,人工變量的系數(shù)取某個正的常數(shù)(一般取1),在保持原問題約束條件不變的情況下求這個目標函數(shù)極小化時的解。顯然在第一階段中,當人工變量取值為0時,目標函數(shù)值也為0。這時候的最優(yōu)解就是原線性規(guī)劃問題的一個基可行解。page115作輔助問題minW=yi

i=1mxj

yi0j=1naij

xj

+yi

=bi(i=1,2,…,m)原問題maxZ=Cj

xj

j=1nxj

0j=1naij

xj

=bi(i=1,2,…,m)6.4兩階段法page116解題過程:第1階段:解輔助問題。當進行到最優(yōu)表時,①、若W=0,則得到原問題的一個基本可行解,轉入第2階段。②、若W>0,則判定原問題無可行解。第2階段:去除人工變量,求解原問題。第一階段的最優(yōu)解為原問題的初始基可行解。6.4兩階段法page117例2:maxZ=-x1+2x2x1+x2

2-x1+x21x2

3x1x2

0解:第(1)階段:minW=x6+x7x1+x2-x3+x6=2-x1+x2-x4+x7=1x2+x5=3x1…x7

06.4兩階段法page118列初始單純形表Cj00000-1-1θCBxBbx1x2x3x4x5x6x7-1x6211-10010-1x71-110-10010x530100100

σj=cj-zj第二階段:去除人工變量,列新單純形表求解。6.4兩階段法page119

0000011

x1x2x3x4x5x6x7CBxB

3

0

-2110

001x6211-100101x71-1

(1)0-10010x530100100CB

xB

1

-201-1002x61(2)0-1101-1x21-1

10-1001x52100110-1

xB

0

0000011x11/210-1/21/201/2-1/2x23/20

1-1/2-1/201/21/2x53/200-1/21/21-1/2-1/2

6.4兩階段法page120

-12000x1x2x3x4x5CBxB

3/2001/23/20-1x11/210-1/2(1/2)02x23/201-1/2-1/200x53/2001/21/21

xB4-30200x4120-110x2211-100x51-10(1)01

xB

6

1000-2x4210011x2301001x31-10

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論