《最優(yōu)化方法》研究生配套教學(xué)課件

最優(yōu)化方法2序研究內(nèi)容：在有限種或無限種可行方案中挑選最優(yōu)方案，構(gòu)造尋求最優(yōu)解的計算方法研究目的：主要解決最優(yōu)計劃、最優(yōu)分配、最優(yōu)決策、最佳設(shè)計、最佳管理等最優(yōu)化問題。應(yīng)用領(lǐng)域：科學(xué)工程、國防、交通、管理、經(jīng)濟、金融、計算機等。1.最優(yōu)化方法概述3

最優(yōu)化方法(OptimizationTechniques)隸屬于運籌學(xué).

運籌學(xué)（OperationsResearch）是用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問題，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。數(shù)學(xué)規(guī)劃又包括線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃，目標(biāo)規(guī)劃和動態(tài)規(guī)劃等，是運籌學(xué)的主要內(nèi)容.一些背景知識4運籌學(xué)這一名詞最早出現(xiàn)于1938年。當(dāng)時英，美等國盟軍在與德國的戰(zhàn)爭中遇到了許多錯綜復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題難以解決，比如(１)防空雷達(dá)的布置問題：(２)護航艦隊的編隊問題：為了應(yīng)付上述各種復(fù)雜問題，英美等國逐批召集不同專業(yè)背景的科學(xué)家，在三軍組織了各種研究小組，研究的問題都是軍事性質(zhì)的，在英國稱為“OperationalResearch”，其他英語國家稱為“OperationsResearch”，意思是軍事行動研究。這些研究小組運用系統(tǒng)優(yōu)化的思想，應(yīng)用數(shù)學(xué)技術(shù)分析軍事問題，取得了非常理想的效果。5二次大戰(zhàn)以后，在軍事運籌小組中工作過的一部分科學(xué)家開始轉(zhuǎn)入民用部門，他們把對軍事系統(tǒng)最優(yōu)化的研究成果拓展到各種民用系統(tǒng)的研究上。

1947年美國數(shù)學(xué)家G.B.Dantzig在研究美國空軍資源配置時,提出了求解線性規(guī)劃的有效方法—單純形法。二十世紀(jì)五十年代初，應(yīng)用計算機求解線性規(guī)劃獲得成功。至五十年代末，一些工業(yè)先進(jìn)國家的大型企業(yè)已經(jīng)較普遍地使用運籌學(xué)方法解決在生產(chǎn)經(jīng)營管理中遇到的實際問題，并取得了良好的效果，至六十年代中期，運籌學(xué)開始應(yīng)用于一些服務(wù)性行業(yè)和公用事業(yè)。6

我國運籌學(xué)的研究始于五十年代中期，當(dāng)時由錢學(xué)森教授將運籌學(xué)從西方國家引入我國，以華羅庚教授為首的一大批科學(xué)家在有關(guān)企事業(yè)單位積極推廣和普及運籌學(xué)方法，在建筑，紡織，交通運輸，水利建設(shè)和郵電等行業(yè)都有不少應(yīng)用。關(guān)于郵遞員投遞的最佳路線問題就是由我國年輕的數(shù)學(xué)家管梅谷于1962年首先提出的，在國際上統(tǒng)稱為中國郵遞員問題。我國運籌學(xué)的理論和應(yīng)用研究在較短時間內(nèi)趕上了世界水平。72.學(xué)習(xí)本課程所需的數(shù)學(xué)知識向量、向量的模（范數(shù)）、向量的運算、線性相關(guān)與無關(guān)、基.

矩陣的運算及性質(zhì)、矩陣的秩、特征值、正定性。

向量函數(shù)、連續(xù)性、可微性、梯度、海森矩陣、向量函數(shù)（多元函數(shù)）的Taylor定理3.課程基本內(nèi)容：線性規(guī)劃無約束最優(yōu)化方法約束最優(yōu)化方法多目標(biāo)最優(yōu)化方法894.學(xué)習(xí)要求及考評

掌握主要的優(yōu)化模型的數(shù)學(xué)計算方法.

了解現(xiàn)代優(yōu)化方法及其數(shù)學(xué)原理.

熟練掌握應(yīng)用數(shù)學(xué)軟件計算優(yōu)化問題.

最終成績（討論待定）

=作業(yè)30%+期末70%?=作業(yè)30%

+論文70%？

=作業(yè)30%+論文30%+期末30%？

105.參考書目主要參考書目：理論方面：(1)解可新、韓健，《最優(yōu)化方法》，天津大學(xué)出版社,2004(2)何堅勇，《最優(yōu)化方法》,清華大學(xué)出版社，2007計算方面：(3)曹衛(wèi)華，郭正，《最優(yōu)化技術(shù)方法及MATLAB的實現(xiàn)》，化學(xué)工業(yè)出版社，2005(4)朱德通，《最優(yōu)化模型與實驗》,同濟大學(xué)出版社，2003

其它參考書：(5)盧名高、劉慶吉編著，《最優(yōu)化應(yīng)用技術(shù)》，石油工業(yè)出版社,2002(6)唐煥文，秦學(xué)志,《實用最優(yōu)化方法》，大連理工大學(xué)出版社，2004(7)錢頌迪，《運籌學(xué)》，清華大學(xué)出版社，1990(8)袁亞湘、孫文瑜著，《最優(yōu)化理論與方法》，科學(xué)出版社，2005第一講線性規(guī)劃的基本概念

線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃的圖解法線性規(guī)劃問題的標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型線性規(guī)劃的解線性規(guī)劃的基本原理1.問題的提出：

在生產(chǎn)管理的經(jīng)營活動中，通常需要對“有限的資源”尋求“最佳”的利用或分配方式。有限資源：勞動力、原材料、設(shè)備或資金等最佳：有一個標(biāo)準(zhǔn)或目標(biāo)，使利潤達(dá)到最大或成本達(dá)到最小。有限資源的合理配置有兩類問題如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大；在生產(chǎn)或經(jīng)營的任務(wù)確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營活動，使所消耗的資源數(shù)最少。1.1線性規(guī)劃問題及其數(shù)學(xué)模型例１:某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時間，以及該廠每周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）

3020160設(shè)備（臺）

5115

已知該廠生產(chǎn)每噸甲、乙藥品的利潤分別為5萬元和2萬元。但根據(jù)市場需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應(yīng)超過4噸。問該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤最大？

定義:

x1為生產(chǎn)甲種藥品的計劃產(chǎn)量數(shù)，

x2為生產(chǎn)乙種藥品的計劃產(chǎn)量數(shù)。

目標(biāo)：要使總利潤最大化maxz=5x1+2x2

約束：每周資源總量的限制，

30x1+20x2≤1605x1+x2≤15甲種藥品每周產(chǎn)量不應(yīng)超過4噸的限制x1≤4計劃生產(chǎn)數(shù)不可能是負(fù)數(shù)，x1≥0x2≥0每噸產(chǎn)品的消耗

每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺）

5115單位利潤(萬元)

5２

數(shù)學(xué)模型為每噸產(chǎn)品的消耗每周資源總量甲乙維生素（公斤）3020160設(shè)備（臺）5115單位利潤(萬元)5２這是一個如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問題。在滿足一組約束條件的限制下，尋求決策變量x1，x2的決策值，使目標(biāo)函數(shù)達(dá)到最大值。例２：某化工廠根據(jù)一項合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品。已知甲、乙兩種原料都含有A、B、C三種化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示：已知甲、乙兩種原料的成本分別是每公斤3元和2元，廠方希望總成本達(dá)到最小，問如何配置該產(chǎn)品？

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155化學(xué)成分定義x1，x2分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，目標(biāo)：使總成本最小化minz=3x1+2x2約束：配料平衡條件，x1+x2=1產(chǎn)品中A、B、C三種化學(xué)成分的最低含量

12x1+3x2≥4

2x1+3x2≥2

3x1+15x2≥5非負(fù)性條件x1≥0,x2≥0

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分?jǐn)?shù)學(xué)模型：

原料化學(xué)成分含量（%）產(chǎn)品中化學(xué)成分的最低含量（%）甲乙A1234B232C3155單位成本（元）３２化學(xué)成分這是一個原料配制問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。滿足一組約束條件的同時，尋求變量x1和x2的值使目標(biāo)函數(shù)取得最小值。例３:某鐵器加工廠要制作100套鋼架，每套要用長為2.9米，2.1米和1.5米的圓鋼各一根。已知原料長為7.4米，問應(yīng)如何下料，可使材料最??？

分析：在長度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出8種不同的下料方案：圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料頭（米）00.10.20.30.80.91.１1.4

問題歸納為如何混合使用這8種不同的下料方案，來制造100套鋼架，且要使剩余的余料總長為最短。

設(shè)表示用第j種下料方案下料的原料根數(shù)，j=1,2…,8,目標(biāo)：使余料總長度最小化minz=0x1+0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8約束：三種規(guī)格圓鋼根數(shù)x1+2x2+x4+x6=100

2x3+2x4+x5+x6+3x7=1003x1+x2+2x3+3x5+x6+4x8=100非負(fù)取整條件xj≥0(j=1,2…8)且取整數(shù)圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104余料（米）00.10.20.30.80.91.１1.4

數(shù)學(xué)模型

s.t.

這是一個下料問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。滿足一組約束條件的同時，尋求變量x1至x8的值,使目標(biāo)函數(shù)取得最小值。圓鋼（米）ⅠⅡⅢⅣⅤⅥⅦⅦ2．9120101002．1002211301．531203104料頭（米）00.10.20.30.80.91.11.4且為整數(shù)

與規(guī)劃問題有關(guān)的數(shù)學(xué)模型總有兩部分組成：

約束條件：反映了有限資源對生產(chǎn)經(jīng)營活動的種種約束，或者生產(chǎn)經(jīng)營必須完成的任務(wù)；目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營者在有限資源條件下希望達(dá)到的生產(chǎn)或經(jīng)營的目標(biāo)。2.線性規(guī)劃的一般數(shù)學(xué)模型

線性規(guī)劃模型的特征：（1）用一組決策變量x1，x2，…,xn表示某一方案，且在一般情況下，變量的取值是非負(fù)的。（2）有一個目標(biāo)函數(shù)，這個目標(biāo)函數(shù)可表示為這組變量的線性函數(shù)。（3）存在若干個約束條件，約束條件用決策變量的線性等式或線性不等式來表達(dá)。（4）要求目標(biāo)函數(shù)實現(xiàn)最大化（max）或最小化（min）。滿足上述4個特征的規(guī)劃問題稱為線性規(guī)劃問題。通常稱為決策變量，為價值系數(shù)，為消耗系數(shù),為資源限制系數(shù)。線性規(guī)劃的模型的一般形式:目標(biāo)函數(shù)

滿足約束條件min(max)1.2線性規(guī)劃的圖解法

適用于求解兩個變量的線性規(guī)劃問題1.圖解法的基本步驟例4:利用例1說明圖解法的主要步驟，例1的數(shù)學(xué)模型為O51015x1x1=4x2101AB(2,5)C▽z5x1+x2=1530x1+20x2=1605x1+2x2=5

線性規(guī)劃圖解法的基本步驟（1）建立以x1,x2為坐標(biāo)軸的直角坐標(biāo)系，畫出線性規(guī)劃問題的可行域,（2）求目標(biāo)函數(shù)z=C1x1+C2x2的梯度▽z=（c1,c2）,（3）任取等值線

C1x1+C2x2=z0,沿梯度▽z正方向平移,

（若是極小化問題，則沿負(fù)梯度方向－▽z平移），求等直線將離未離可行域時與可行域的交點。（4）若交點存在，則該點坐標(biāo)就是最優(yōu)解X*

。例如：max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8

x1≥0,x2≥028可行域目標(biāo)函數(shù)等值線最優(yōu)解64-860x1x22.圖解法的幾種可能結(jié)果

(1）有唯一最優(yōu)解，如例1

則目標(biāo)函數(shù)等值線10x1+2x2=z

與第二約束5x1+x2≤15

的邊界線平行。將等值線沿梯度▽z=（10，2）正方向平移至B點時與可行域OABC的整條邊界線AB重合。這表明線段AB上的每一點都使目標(biāo)函數(shù)取得同樣的最大值，因而都是最優(yōu)解。（2）有無窮多最優(yōu)解如例1中的目標(biāo)函數(shù)設(shè)為:maxz=10x1+2x2

例5:試用圖解法求解下列線性規(guī)劃問題

（3）無界解（或稱無最優(yōu)解）無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標(biāo)函數(shù)值z→+∝,

極小化問題則可使目標(biāo)函數(shù)值z→-∝，有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之則不必然。-1O24x1x224－▽z=(3,2)-2x1+x2=2x1-3x2=3-1O33（4）無可行解某些線性規(guī)劃問題的可行域是空集，既不存在滿足所有約束條件的點，這時問題無可行解，當(dāng)然更談不上最優(yōu)解了。在實際中出現(xiàn)這種情況可以認(rèn)為資源條件無法滿足人們的要求，既不存在可行方案。

（3）無界解（或稱無最優(yōu)解）無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標(biāo)函數(shù)值z→+∝,

極小化問題則可使目標(biāo)函數(shù)值z→-∝，有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之則不必然。1.標(biāo)準(zhǔn)線性規(guī)劃模型

(1)線性規(guī)劃問題的標(biāo)準(zhǔn)形式：

其中(1.1)為目標(biāo)函數(shù)，(1.2)為約束條件，(1.3)為非負(fù)條件，為稱呼方便，有時將(1.3)也稱為約束條件。（1.2）

（1.3）1.3線性規(guī)劃的標(biāo)準(zhǔn)形式（1.1）其中C=(c1,c2,…,cn)稱為價值向量，

X=(x1,x2,…,xn)T為決策變量向量，

Pj=(a1j,x2j,…,xmj)T為決策變量xj所對應(yīng)的消耗系數(shù)向量，

b=(b1,b2,…,bm)T為資源向量。(2)緊湊格式：(3)向量格式：35其中為m×n階矩陣(4)矩陣格式：C=(c1,c2,…,cn)，

X=(x1,x2,…,xn)T，

b=(b1,b2,…,bm)T。2.非標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)化（1）極大化與極小化：原目標(biāo)函數(shù)(2)

線性不等式與線性等式：其中xn+i

為非負(fù)松弛變量，其中xn+k

為非負(fù)剩余變量。37

(3)非負(fù)變量與符號不受限制的變量若xi的符號不受限制，則可引進(jìn)非負(fù)變量xi1,xi2，令xi=xi1-xi2，使線性規(guī)劃里所有的變量都轉(zhuǎn)化為有非負(fù)限制的變量。(4)右端項有負(fù)值的問題：在標(biāo)準(zhǔn)形式中，要求右端項必須每一個分量非負(fù)。當(dāng)某一個右端項系數(shù)為負(fù)時，如bi<0，則把該等式約束兩端同時乘以－1，得到：－ai1x1－ai2x2－

…－ainxn

=－bi

。38例6:將下述線性規(guī)劃問題化為標(biāo)準(zhǔn)型

符號不受限制解:令,可將目標(biāo)函數(shù)化為min型，令,其中39考慮一個標(biāo)準(zhǔn)的線性規(guī)劃問題：1.4標(biāo)準(zhǔn)型線性規(guī)劃的解其中Ｃ為n維行向量，

Ｘ是n維列向量，

ｂ是m維列向量，

Ａ是m×n階矩陣，假定滿足m≤n，且Ｒ(Ａ)=m.40

(2)最優(yōu)解:使目標(biāo)函數(shù)（1.4)達(dá)到最優(yōu)值的的可行解稱為最優(yōu)解，最優(yōu)解常用X*

表示。

(3)基:若Ｂ是Ａ中m×m階非奇異矩陣，即|Ｂ|≠0，則稱Ｂ是線性規(guī)劃問題的一個基?？尚薪饧Q為線性規(guī)劃問題的可行域。線性規(guī)劃問題解的概念：

(1)可行解:滿足約束條件(1.5)，(1.6)的解稱為線性規(guī)劃問題的可行解。41一個線性規(guī)劃的基通常不是唯一的，但是基的個數(shù)也不會超過Cnm

個。一旦確定了線性規(guī)劃的基，則相應(yīng)的基向量、基變量和非基變量也就確定。若Ｂ是線性規(guī)劃問題的一個基，那么Ｂ一定是由m個線性無關(guān)的列向量組成，不失一般性，可設(shè)

稱為基向量，

與基向量Pj相對應(yīng)的變量xj(j=1,2，…，m)稱為基變量。42(4)基本解。設(shè)B是線性規(guī)劃的一個基，若令n-m個非基變量等于0，則所得的方程組ＡＸ=b的解稱為線性規(guī)劃問題的一個基本解（簡稱基解）。有一個基就可以求得一個基本解。由基的有限性可知，基本解的個數(shù)也不會超過Cnm

個。由于基本解中的非零分量可能是負(fù)數(shù)，所以基本解不一定是可行的。(5)基本可行解。滿足非負(fù)條件的基本解稱為基本可行解(簡稱基可行解)。與基本可行解對應(yīng)的基成為可行基。基本可行解的非零向量的個數(shù)小于等于m，并且都是非負(fù)的。由于基本可行解的數(shù)目一般少于基本解的數(shù)目，因此可行基的數(shù)目也要少于基的數(shù)目。

當(dāng)基本可行解中有一個或多個基變量是取零值時，稱此解為

退化的基本可行解。43

線性規(guī)劃問題各種解的關(guān)系可用文氏圖表示，

可行解

基本解基本可行解44例7：求下列約束方程所對應(yīng)的線性規(guī)劃的所有基本解，基本可行解。解：化為標(biāo)準(zhǔn)形式后為2×4階矩陣。且R(A)=2,所以該線性規(guī)劃基的個數(shù)≤=6個

若令非基變量，約束方程組為可得對應(yīng)的基本解是一個基本可行解。x1,x2為基變量，45對應(yīng)基本基本解對應(yīng)基本基本解對應(yīng)基本基本解

按相同步驟，可求得線性規(guī)劃其他4個基：對應(yīng)基本基本解46若利用圖解法畫出線性規(guī)劃的可行域，如圖，COBA4481.5

線性規(guī)劃的基本原理

47

由圖解法的步驟，可以從幾何的角度得出以下兩個結(jié)論：（1）線性規(guī)劃問題的可行域是一個有界或無界的凸多邊形，其頂點個數(shù)是有限個。（2）若線性規(guī)劃問題有最優(yōu)解，那么最優(yōu)解一定可在可行域的某個頂點上找到。1.幾個基本概念

48（1）凸集：設(shè)K是n維歐式空間的一個點集，若任意兩點X(1)∈K,X(2)∈K的連線上的一切點αX(1)+(1-α)X(2)∈K

(0<α<1),則稱K為凸集。線性約束條件凸集例頂點個數(shù)有限有限無限有限無限非凸集例1.幾個基本概念

49（1）凸集：設(shè)K是n維歐式空間的一個點集，若任意兩點X(1)∈K,X(2)∈K的連線上的一切點αX(1)+(1-α)X(2)∈K

(0<α<1),則稱K為凸集。

連接幾何形體中任意兩點的線段仍完全在該幾何形體之中。有限個凸集的交集仍然是凸集。線性約束條件凸集定義的幾何解釋50（2）凸組合：設(shè)X(1)，X(2)，…，X(k)是n維歐式空間En中的k個點，若存在μ1,

μ2,…,μk滿足0≤μi≤1,(i=1,2,…,k),且μ1+μ2+…+μk=1，使X=μ1X(1)+μ2X(2)+…μk

X(k)，則稱X為X(1)，X(2)，…，X(k)的凸組合。凸組合的幾何意義

凸集K中任意兩點X(1)，X(2)連線上的任一點X都是X(1)與X(2)的一個凸組合。51X(1)X(3)X(2)X’X=X’

+(1-)X(2)，(0<<1)x1x2OX’=X(1)+(1-)X(3)，

(0<<1)52X(1)X(3)X(2)X’X=u1X(1)+u2X(2)+u3X(3)x1x2OX’=X(1)+(1-)X(3)，

(0<<1)53（2）凸組合：設(shè)X(1)，X(2)，…，X(k)是n維歐式空間En中的k個點，若存在μ1,

μ2,…,μk滿足0≤μi≤1,(i=1,2,…,k),且μ1+μ2+…+μk=1，使X=μ1X(1)+μ2X(2)+…μk

X(k)，則稱X為X(1)，X(2)，…，X(k)的凸組合。凸集K中任意兩點X(1)，X(2)連線上的任一點X都是X(1)與X(2)的一個凸組合。(3)頂點：設(shè)K為凸集，X∈K,若X不能用X(1)∈K,X(2)∈K兩點(X(1)≠X(2))的一個凸組合表示為X=αX(1)+(1-α)X(2),其中0<α<1，則稱X為K的一個頂點?；蛉敉辜疜中的點X不能成為K中任何線段的內(nèi)點，則稱X為K的一個頂點。2.線性規(guī)劃的基本定理

54定理1：若線性規(guī)劃問題存在可行域，則其可行域

D={X/AX=b,x≥0}是一個凸集。

證明：為了證明滿足ＡＸ=ｂ，Ｘ≥0的所有點（可行解）組成的幾何體是凸集，只要證明Ｄ中任意兩點任意兩點X(1)，X(2)

連線上的一切點均滿足線性約束條件既可。任取，滿足則對任意的有又因為均≥0，所以由此可知，即Ｄ是凸集。55證明：必要性：因為Ｘ是基本解，由基本解的定義，Ｘ的非零分量所對應(yīng)的系數(shù)列向量線性無關(guān)，又因為Ｘ是可行解，由基本可行解的定義，非零分量均是正的，所以Ｘ的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。

充分性：設(shè)Ｘ是線性規(guī)劃問題的可行解，且正分量所對應(yīng)的列向量也線性無關(guān)，則必有k≤m,若k=m，則剛好構(gòu)成一個基，為相應(yīng)的基本可行解。若k<m，則由線性代數(shù)知識，一定可以從其余的n-k個系數(shù)列向量中取出m-k個與構(gòu)成最大線性無關(guān)向量組，其對應(yīng)的基本可行解恰好為Ｘ，不過此時的Ｘ是一個退化的基本可行解。

引理1：線性規(guī)劃問題的可行解

是基本可行解的充要條件是Ｘ的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。56

定理2：設(shè)線性規(guī)劃問題的可行域，則Ｘ是Ｄ的一個頂點的充分必要條件是Ｘ為線性規(guī)劃問題的基本可行解。

證明思路：必要性：由引理1，若X是D的一個頂點，要證明X是線性規(guī)劃的一個基本可行解，只要證明Ｘ的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。

用反證法，倘若Ｘ的正分量所對應(yīng)的系數(shù)列向量線性相關(guān)，則可以在Ｄ中找到兩點，使，與Ｘ是Ｄ的頂點矛盾.

充分性：若Ｘ是線性規(guī)劃的一個基本可行解，要證明Ｘ是可行域Ｄ的一個頂點，

仍用反證法，倘若Ｘ不是可行域Ｄ的頂點，可以證明Ｘ的基變量所對應(yīng)的系數(shù)列向量線性相關(guān)，與X是基本可行解矛盾。57例8:已知線性規(guī)劃問題的約束條件為

試討論可行域頂點和基本可行解之間的對應(yīng)關(guān)系。

解:可行域為四維凸多面體，可以推得在四維空間中有3個頂點，Ａ=(0,0,10,10)，Ｂ=(0,10,0,10)，Ｃ=(10,0,0,0)。這3個頂點與線性規(guī)劃的5個基本可行解的對應(yīng)關(guān)系如下：頂點Ａ對應(yīng)以x3,x4為基變量的基本可行解；頂點Ｂ對應(yīng)以x2,x4為基變量的基本可行解；頂點Ｃ對應(yīng)x1,x2;x1,x3和x1,x4為基變量的退化基本可行解.一個線性規(guī)劃問題，如果它的所有基本可行解都是非退化的，那么稱這個線性規(guī)劃是非退化的，只有在這種情況下，頂點和基本可行解之間才是一一對應(yīng)的。

定理3(線性規(guī)劃的基本定理):

若可行域D非空有界，那么線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域D的頂點上達(dá)到最優(yōu)值。證明思路：因為可行域非空有界，所以線性規(guī)劃一定有最優(yōu)解，倘若X(0)不是頂點，且目標(biāo)函數(shù)在該點處取到最優(yōu)值z*，則必能找到可行域的一個頂點X(m)

，使目標(biāo)函數(shù)在的值也等于z*

。58定理3(線性規(guī)劃的基本定理):

若可行域D非空有界，那么線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域D的頂點上達(dá)到最優(yōu)值。59說明:

定理3并不排除在一個非頂點上有一個最優(yōu)解的可能性。但是在一個給定的線性規(guī)劃問題的所有最優(yōu)解中，至少有一個是頂點。如果可行域無界，則線性規(guī)劃問題可能無最優(yōu)解。如果目標(biāo)函數(shù)同時在兩個頂點上達(dá)到最優(yōu)解，那么不難證明在這兩個點的凸組合上也達(dá)到最優(yōu)解，這時線性規(guī)劃問題有無窮多最優(yōu)解。60定理1：若線性規(guī)劃問題存在可行域，則其可行域是一個凸集。

定理2：設(shè)線性規(guī)劃問題的可行域，則Ｘ是Ｄ的一個頂點的充分必要條件是Ｘ為線性規(guī)劃問題的基本可行解。

定理3：若可行域D非空有界，那么線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域D的頂點上達(dá)到最優(yōu)值。LinearProgramminginMATLAB61第二講單純形法

單純形法的一般原理表格單純形法借助人工變量求初始的基本可行解單純形表與線性規(guī)劃問題的討論改進(jìn)單純形法

622.1單純形法的一般原理1確定初始的基本可行解2判斷現(xiàn)行的基本可行解是否最優(yōu)3基本可行解的改進(jìn)——基變換4用初等變換求改進(jìn)了的基本可行解——旋轉(zhuǎn)變換6364

Dantzig的單純形法把尋優(yōu)的目標(biāo)集中在所有基本可行解（即可行域頂點）中。其基本思路是從一個初始的基本可行解出發(fā)，尋找一條達(dá)到最優(yōu)基本可行解的最佳途徑。單純形法的一般步驟如下：（1）尋找一個初始的基本可行解。（2）檢查現(xiàn)行的基本可行解是否最優(yōu)，如果為最優(yōu)，則停止迭代，已找到最優(yōu)解，否則轉(zhuǎn)一步。（3）移至目標(biāo)函數(shù)值有所改善的另一個基本可行解，然后轉(zhuǎn)會到步驟（2）。其步驟如下：65找出一個初始可行解是否最優(yōu)轉(zhuǎn)移到另一個目標(biāo)函數(shù)（找更小的基本可行解）最優(yōu)解是否循環(huán)直到找出為止，核心是：變量迭代結(jié)束1確定初始的基本可行解

66

確定初始的基本可行解等價于確定初始的可行基，一旦初始的可行基確定了，那么對應(yīng)的初始基本可行解也就唯一確定.

為了討論方便，不妨假設(shè)在標(biāo)準(zhǔn)型線性規(guī)劃中，系數(shù)矩陣Ａ中前m個系數(shù)列向量恰好構(gòu)成一個可行基，即其中為基變量x1，x2，…,xm的系數(shù)列向量構(gòu)成的可行基，為非基變量xm+1，xm+2，

…,xn的系數(shù)列向量構(gòu)成的矩陣。線性規(guī)劃問題基變換的矩陣表示67==目標(biāo)函數(shù)約束條件右邊常數(shù)68===69線性規(guī)劃問題基變換的表格表示C0AbCBCN0BNbCBCN0IB-1NB-1b70所以約束方程AX=b就可以表示為:得：

若令所有非基變量XN=0,

則基變量由此可得初始的基本可行解712.判斷現(xiàn)行的基本可行解是否最優(yōu)

假如已求得一個基本可行解將這一基本可行解代入目標(biāo)函數(shù)，可求得相應(yīng)的目標(biāo)函數(shù)值

其中分別表示基變量和非基變量所對應(yīng)的目標(biāo)函數(shù)系數(shù)子向量。怎樣判定是否已經(jīng)達(dá)到最小值???72zXBXNRHS10－(CBB-1N－CN)CBB-1b0IB-1NB-1b73

其中稱為非基變量ＸN的檢驗向量，它的各個分量稱為檢驗數(shù)。若σN的每一個檢驗數(shù)均大于等于0，即σN≥0，那么現(xiàn)在的基本可行解就是最優(yōu)解。74定理3.2設(shè)是對應(yīng)基的基可行解，如果向量的第個分量，且向量，則原問題無界（無最優(yōu)解）7576定理1：最優(yōu)解判別定理對于線性規(guī)劃問題若某個基本可行解所對應(yīng)的檢驗向量，則這個基本可行解就是最優(yōu)解。定理2：無窮多最優(yōu)解判別定理

若是一個基本可行解，所對應(yīng)的檢驗向量，其中存在一個檢驗數(shù)σm+k=0，則線性規(guī)劃問題有無窮多最優(yōu)解。77定理1：最優(yōu)解判別定理對于線性規(guī)劃問題若某個基本可行解所對應(yīng)的檢驗向量，則這個基本可行解就是最優(yōu)解。定理3：無有界最優(yōu)解判別定理

若是一個基本可行解，所對應(yīng)的檢驗向量

,其中存在一個檢驗數(shù)，且該檢驗數(shù)所對應(yīng)的非基變量的系數(shù)列向量的全部系數(shù)都為負(fù)數(shù)或零，則線性規(guī)劃問題無有界最優(yōu)解。783.基本可行解的改進(jìn)

——基變換

如果現(xiàn)行的基本可行解Ｘ不是最優(yōu)解，即在檢驗向量σN=CN－CBB－1N

中存在負(fù)的檢驗數(shù)，則需在原基本可行解Ｘ的基礎(chǔ)上尋找一個新的基本可行解，并使目標(biāo)函數(shù)值有所改善。具體做法是：先從檢驗數(shù)為負(fù)的非基變量中確定一個換入變量，使它從非基變量變成基變量，再從原來的基變量中確定一個換出變量，使它從基變量變成非基變量。由此可得一個新的基本可行解，由可知，這樣的變換一定能使目標(biāo)函數(shù)值有所減少。79則選取對應(yīng)的xm+k為換入變量，由于σm+k<0

且為最小，

換入變量和換出變量的確定：換入變量的確定—

最大減小原則若其中有兩個以上的檢驗數(shù)為負(fù)，那么為了使目標(biāo)函數(shù)值下降得快些，通常要用“最大減小原則”，即選取最小負(fù)檢驗數(shù)所對應(yīng)的非基變量為換入變量，即若因此當(dāng)xm+k由零增至正值，假設(shè)檢驗向量

可使目標(biāo)函數(shù)值最大限度的減小。80如果確定Xm+k

為換入變量，方程則選取對應(yīng)的基變量Xl為換出變量。其中Pm+k為Ａ中與Xm+k

對應(yīng)的系數(shù)列向量。現(xiàn)在需在XB=(x1,x2,…,xm)T

中確定一個基變量為換出變量。當(dāng)xm+k由零慢慢增加到某個值時，XB

的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：

換出變量的確定—最小比值原則814.用初等變換求改進(jìn)了的基本可行解——旋轉(zhuǎn)運算

假設(shè)Ｂ是線性規(guī)劃的可行基，則令非基變量，則基變量?？傻没究尚薪狻Ｓ媚骊囎蟪思s束方程組的兩端，等價于對方程組施以一系列的初等“行變換”。變換的結(jié)果是將系數(shù)矩陣Ａ中的可行基Ｂ變換成單位矩陣I，把非基變量系數(shù)列向量構(gòu)成的矩陣Ｎ變換成，把向量b變換成。82CBB-1aj－cj=zj－cj

稱為非基變量的檢驗數(shù)B-1aj=Yj，B-1b=b’，CBB-1b=z0zXB…xj…RHSz1CB…-cj…00B…aj…bz10…CBB-1aj－cj…CBB-1b0I…B-1aj…B-1bz10…zj－cj…z00I…Yj…b’83

且改進(jìn)了的基本可行解只是在Ｘ的基變量的基礎(chǔ)上用一個換入變量替代其中一個換出變量，其它的基變量仍然保持不變。這些基變量的系數(shù)列向量是單位矩陣I中的單位向量。為了求得改進(jìn)的基本可行解，只需對增廣矩陣施行初等行變換，將換入變量的系數(shù)列向量變換成換出變量所對應(yīng)的單位向量即可。

由于行初等變換后的方程組與原約束方程組或同解84(１)確定初始的基本可行解。例1解：，基變量，非基變量。85檢驗向量(2)檢驗

是否最優(yōu)。因為σ1=－3，σ3=－4均小于零，所以不是最優(yōu)解。86選取x4為換出變量.②

選取換出變量（3）基本可行解的改進(jìn)

①

選取換入變量因為min{－3，－4}=－4，取x3為換入變量。87（4）求改進(jìn)了的基本可行解X’——旋轉(zhuǎn)運算

對約束方程組的增廣矩陣施以初等行變換，使換入變量x3所對應(yīng)的系數(shù)列向量變換成換出變量x4所對應(yīng)的單位向量,注意保持基變量x5的系數(shù)列向量為單位向量不變。第一行除以２第二行減去第一行88可得改進(jìn)的基本可行解。

，基變量x3,x5,非基變量

x1,x2,x4。目標(biāo)函數(shù)值基本可行解易見目標(biāo)函數(shù)值比原來的Z=1減小了，再轉(zhuǎn)向步驟(2)89（2）檢驗

是否最優(yōu)。檢驗向量所以仍不是最優(yōu)解。90①

選取換入變量因為，取x1為換入變量。②

選取換出變量且，選取x5為換出變量.（3）基本可行解的改進(jìn)91（4）求改進(jìn)了的基本可行解X”——旋轉(zhuǎn)運算對約束方程組的增廣矩陣施以初等行變換，使換入變量x1所對應(yīng)的系數(shù)列向量變換成換出變量x5所對應(yīng)的單位向量,第二行乘以２/５第一行減以第二行的１/２倍92——————————————————————————可得改進(jìn)的基本可行解。

，基變量，非基變量

基本可行解

目標(biāo)函數(shù)值比ｚ=－15減小了，再轉(zhuǎn)向步驟(2)93（2）檢驗

是否最優(yōu)。檢驗向量因為所有檢驗數(shù)均大于零，所以是最優(yōu)解，942.2表格單純形法

通過例１我們發(fā)現(xiàn)，在單純形法的求解過程中，有下列重要指標(biāo)：每一個基本可行解的檢驗向量根據(jù)檢驗向量可以確定所求得的基本可行解是否為最優(yōu)解。如果不是最優(yōu)又可以通過檢驗向量確定合適的換入變量。每一個基本可行解所對應(yīng)的目標(biāo)函數(shù)值通過目標(biāo)函數(shù)值可以觀察單純形法的每次迭代是否能使目標(biāo)函數(shù)值有效地減小，直至求得最優(yōu)目標(biāo)函數(shù)為止。

在單純形法求解過程中，每一個基本可行解Ｘ都以某個經(jīng)過初等行變換的約束方程組中的單位矩陣Ι為可行基。當(dāng)Ｂ=Ｉ時，Ｂ-1=Ｉ，易知：95

可將這些重要結(jié)論的計算設(shè)計成如下一個簡單的表格，即單純形表來完成：C

CBCN

θ

CB

XB

b

x1x2

···xm

xm+1xm+2···xn

c1c2..cm

x1x2

.xm

b1b2..bm

I

N

θ1θ2..θm

Z

CBb

0

CN-CBN

96

例2、試?yán)脝渭冃伪砬罄?中的最優(yōu)解解：

得初始的單純形表：初始基本可行解，Z=1，122108x41

－30－4001Z341017x5－1x1x2x3x4x5bXBCBθ

－5－2－31－1C97x3換入變量，x4換出變量，２為主元進(jìn)行旋轉(zhuǎn)變換基本可行解1/2

1

1

1/2

04x3－3

－14020－15Z5/230-1/213x5－1

x1

x2

x3

x4

x5bXBCBθC122108x41

－30－4001Z341017x5－1x1x2x3x4x5bXBCBθC8/27/1

－5－2－31－1

－5－2－31－198

最優(yōu)解最優(yōu)值

x1換入變量，x5換出變量，５/２為主元進(jìn)行旋轉(zhuǎn)變換4/1/21/2

1

1

1/2

04x33

－14020－15Z3/5/25/230-1/213x5－1

x1

x2

x3

x4

x5bXBCBθC02/513/5-1/517/5x3－3026/509/52/5－81/5Z16/50-1/52/56/5x1－5x1x2x3x4x5bXBCBθC

－5－2－31－1

－5－2－31－199解：本題的目標(biāo)函數(shù)是求極大化的線性函數(shù)，可以令則這兩個線性規(guī)劃問題具有相同的可行域和最優(yōu)解，只是目標(biāo)函數(shù)相差一個符號而已。

例3、用單純形方法求解線性規(guī)劃問題100010103x2－20012-12x30-010103x2－24/1101004x303/1010103x40_101004x3000001－8Z’100-212x1－1－100

20－6Z’2/1100-212x500Z’8/2120018x50x1x2x3x4x5bXBCBΘ

－1－2000C最優(yōu)解最優(yōu)值2/23/1-

－1－2000101因為非基變量x4的檢驗數(shù)σ4=0，由無窮多最優(yōu)解判別定理，本例的線性規(guī)劃問題存在無窮多最優(yōu)解。事實上若以x4為換入變量，以x3為換出變量，再進(jìn)行一次迭代，可得一下單純形表：最優(yōu)解最優(yōu)值C

－1－2000ΘCBXBbx1x2x3x4x5021x4x2x1124001/21－1/201－1/20

1/21010

0Z’－800001最優(yōu)解的一般表示式102對于極大化的線性規(guī)劃問題的處理：檢驗是否最優(yōu)的準(zhǔn)則有所不同。即：若某個基本可行解的所有非基變量對應(yīng)的檢驗數(shù)（而不是≥０），則基本可行解為最優(yōu)解．采用最大增加原則（而非最大減少原則）來確定換入變量。即：若則選取對應(yīng)的非基變量xm+k

為換入變量．確定了換入變量以后，換出變量仍采用最小比值原則來確定。直接利用單純形方法求解，但，先化為標(biāo)準(zhǔn)型，即將極大化問題變換為極小化問題，然后利用單純形方法求解．103為了求得基本可行解，必須求基Ｂ的逆陣Ｂ-1。但是求逆陣Ｂ-1也是一件麻煩的事。問題：判斷m個系數(shù)列向量是否恰好構(gòu)成一個基?并不是一件容易的事。判斷m個系數(shù)列向量是否線性無關(guān)?并非易事。即使系數(shù)矩陣Ａ中找到了一個基B，也不能保證B恰好是可行基。因為不能保證基變量ＸB=Ｂ-1b≥0。結(jié)論：在線性規(guī)劃標(biāo)準(zhǔn)化過程中設(shè)法得到一個m階單位矩陣I作為初始可行基Ｂ，104②若在化標(biāo)準(zhǔn)形式前，約束方程中有“≥”不等式，那么在化標(biāo)準(zhǔn)形時除了在方程式左端減去剩余變量使不等式變成等式以外，還必須在左端再加上一個非負(fù)新變量，稱為人工變量．（第2.3節(jié)將講到）③若在化標(biāo)準(zhǔn)形式前，約束方程中有等式方程，那么可以直接在等式左端添加人工變量。（第2.3節(jié)將講到）為了設(shè)法得到一個m階單位矩陣I作為初始可行基Ｂ，可在性規(guī)劃標(biāo)準(zhǔn)化過程中作如下處理：①若在化標(biāo)準(zhǔn)形式前，m個約束方程都是“≤”的形式，那么在化標(biāo)準(zhǔn)形時只需在一個約束不等式左端都加上一個松弛變量xn+i(i=12…m)。1052.3借助人工變量求初始的基本可行解

若約束方程組含有“≥”不等式，那么在化標(biāo)準(zhǔn)形時除了在方程式左端減去剩余變量，還必須在左端加上一個非負(fù)的人工變量。因為人工變量是在約束方程已為等式的基礎(chǔ)上，人為的加上去的一個新變量，因此加入人工變量后的約束方程組與原約束方程組是不等價的。加上人工變量以后，線性規(guī)劃的基本可行解不一定是原線性規(guī)劃的問題的基本可行解。只有當(dāng)基本可行解中所有人工變量都為取零值的非基變量時，該基本可行解對原線性規(guī)劃才有意義。因為此時只需去掉基本可行解中的人工變量部分，剩余部分即為原線性規(guī)劃的一個基本可行解．而這正是我們引入人工變量的主要目的。106

考慮線性規(guī)劃問題：為了在約束方程組的系數(shù)矩陣中得到一個

階單位矩陣作為初始可行基，在每個約束方程組的左端加上一個人工變量

可得到：

107

添加了

個人工變量以后，在系數(shù)矩陣中得到一個階單位矩陣，以該單位矩陣對應(yīng)的人工變量為基變量，即可得到一個初始的基本可行解這樣的基本可行解對原線性規(guī)劃沒有意義的。但是我們可以從X(0)出發(fā)進(jìn)行迭代，一旦所有的人工變量都從基變量迭代出來，變成只能取零值的非基變量，那么我們實際上已經(jīng)求得了原線性規(guī)劃問題的一個初始的基本可行解。此時可以把所有人工變量剔除，開始正式進(jìn)入求原線性規(guī)劃最優(yōu)解的過程。1081.大M法

大M法首先將線性規(guī)劃問題化為標(biāo)準(zhǔn)型。如果約束方程組中包含有一個單位矩陣I，那么已經(jīng)得到了一個初始可行基。否則在約束方程組的左邊加上若干個非負(fù)的人工變量，使人工變量對應(yīng)的系數(shù)列向量與其它變量的系數(shù)列向量共同構(gòu)成一個單位矩陣。以單位矩陣為初始基，即可求得一個初始的基本可行解。為了求得原問題的初始基本可行解，必須盡快通過迭代過程把人工變量從基變量中替換出來成為非基變量。為此可以在目標(biāo)函數(shù)中賦予人工變量一個絕對值很大的正系數(shù)Ｍ。這樣只要基變量中還存在人工變量，目標(biāo)函數(shù)就不可能實現(xiàn)極大化。以后的計算與單純形表解法相同，Ｍ只需認(rèn)定是一個很大的正數(shù)即可。假如在單純形最優(yōu)表的基變量中還包含人工變量，則說明原問題無可行解。否則最優(yōu)解中剔除人工變量的剩余部分即為原問題的初始基本可行解。109例4、用大M法求解下面的線性規(guī)劃問題:解：首先將原問題化為標(biāo)準(zhǔn)型添加人工變量x6，x7，并在目標(biāo)函數(shù)中分別賦予Ｍ110-01-1/2-1/201/21/23/2x2－2

－101/2-1/20-1/21/21/2x11--110-10011x2－21/2

201－10－111x6M1/1-110-10011x7M2/111-100102x6M00-1/2-3/201/2+M3/2+M-5/2Z001/21/21-1/2-1/23/2x50-1-2M0-M-2+M002+2M-2+MZ2/1100110-12x501-2-2MMM0003MZ3/101001003x50

x1x2x3x4x5x6x7bXBCBθ

1－2000MMC11101001003x2-2100110-12x4011-100102x2-220-1101-11x40-01-1/2-1/201/21/23/2x2-21/2/1/210-1/21/201/2-1/21/2x1110002MM-6Z-10101-101x3030-2002+MM-4Z+-10101-101x5000-1/2-3/20?+M3/2+M-5/2Z3/2/1/2001/21/21-1/2-1/23/2x50x1x2x3x4x5x6x7bXBCBθ最優(yōu)解,最優(yōu)值

1－2000MMC1122.兩階段法

兩階段法引入人工變量的目的和原則與大M法相同，所不同的是處理人工變量的方法。

兩階段法的步驟：

求解一個輔助線性規(guī)劃。目標(biāo)函數(shù)取所有人工變量之和，并取極小化；約束條件為原問題中引入人工變量后包含一個單位矩陣的標(biāo)準(zhǔn)型的約束條件。如果輔助線性規(guī)劃存在一個基本可行解，使目標(biāo)函數(shù)的最小值等于零，則所有人工變量都已經(jīng)“離基”。表明原問題已經(jīng)得了一個初始的基本可行解，可轉(zhuǎn)入第二階段繼續(xù)計算；否則說明原問題沒有可行解，可停止計算。

求原問題的最優(yōu)解。在第一階段已求得原問題的一個初始基本可行解的基礎(chǔ)上，繼續(xù)用單純形法求原問題的最優(yōu)解.113例5、用兩階段法求解線性規(guī)劃問題。解：首先將問題化為標(biāo)準(zhǔn)型由于輔助線性規(guī)劃的目標(biāo)函數(shù)是極小化，因此最優(yōu)解的判別準(zhǔn)則應(yīng)為：添加人工變量x6,x7,并建立輔助線性規(guī)劃如下：11401-1/2-1/201/21/23/2x2010-1/21/201/2-1/21/2x10--110-10011x201/220-1101-11x611/1-110-10011x712/111-100102x6100000110w001/21/21-1/2-1/23/2x50-201-10021w2/1100110-12x500-2110003w3/101001003x50x1x2x3x4x5x6x7bXBCBθ0000011C輔助規(guī)劃所有檢驗數(shù)：原問題已得一個初始基本可行解，115由上表可知，通過若干次旋轉(zhuǎn)變換，原問題的約束方程組已變換成包含一個單位矩陣的約束方程組該約束方程組可作為第二階段初始約束方程組，將目標(biāo)函數(shù)則還原成原問題的目標(biāo)函數(shù)，可繼續(xù)利用單純形表求解。116-1000-26Z1001101001-10101231x4x2x3020-302004Z20-11011-100-10101121x4x2x5020

001/23/205/2Z1/2/1/2-3/2/1/210-1/21/2001-1/2-1/20001/21/211/23/23/2x1x2x5-120

x1x2