運(yùn)籌學(xué)A-第1章線性規(guī)劃

第1章線性規(guī)劃

與單純形法5/17/20241編輯版ppt第1章線性規(guī)劃內(nèi)容提要第一節(jié)線性規(guī)劃問(wèn)題的數(shù)學(xué)模型第二節(jié)兩個(gè)變量LP問(wèn)題的圖解法第三節(jié)LP問(wèn)題數(shù)學(xué)模型的標(biāo)準(zhǔn)型第四節(jié)線性規(guī)劃問(wèn)題解的性質(zhì)第五節(jié)單純形法原理及求解步驟2024/5/172編輯版ppt第一節(jié)線性規(guī)劃問(wèn)題的數(shù)學(xué)模型

線性規(guī)劃(LinearProgramming，LP)是運(yùn)籌學(xué)的重要分支之一，在實(shí)際中應(yīng)用得較廣泛，其方法也較成熟，借助計(jì)算機(jī)，使得計(jì)算更方便，應(yīng)用領(lǐng)域更廣泛和深入。線性規(guī)劃通常研究資源的最優(yōu)利用、設(shè)備最佳運(yùn)行以及費(fèi)用最低等問(wèn)題。例如，當(dāng)任務(wù)或目標(biāo)確定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源（如資金、設(shè)備、原標(biāo)材料、人工、時(shí)間等）去完成確定的任務(wù)或目標(biāo)；企業(yè)在一定的資源條件限制下，如何組織安排生產(chǎn)獲得最好的經(jīng)濟(jì)效益（如產(chǎn)品量最多、利潤(rùn)最大）。2024/5/173編輯版ppt一、問(wèn)題的提出（線性規(guī)劃問(wèn)題舉例）3.26

例1-1(生產(chǎn)計(jì)劃問(wèn)題)

某廠在計(jì)劃期內(nèi)安排Ⅰ、Ⅱ生產(chǎn)兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺(tái)數(shù)、A和B兩種原材料的消耗量以及利潤(rùn)如表1-1所示，問(wèn)如何安排生產(chǎn)使利潤(rùn)最大？（假設(shè)產(chǎn)品全部售出）

產(chǎn)品資源ⅠⅡ資源限量設(shè)備（臺(tái)）原材料A（kg）原材料B（kg）單位產(chǎn)品利潤(rùn)

1402

204381612x1x1x1x2

x2x22024/5/174編輯版ppt(1)決策變量：設(shè)x1為甲產(chǎn)品的產(chǎn)量，x2為乙產(chǎn)品的產(chǎn)量。(2)約束條件：生產(chǎn)受資源制約，不能突破有限供給量。設(shè)備約束條件的數(shù)學(xué)表達(dá)為：x1+2x2≤8原材料A約束條件數(shù)學(xué)表達(dá)為：4x1≤16原材料B約束條件數(shù)學(xué)表達(dá)為：4x2≤12(3)目標(biāo)函數(shù)：目標(biāo)函數(shù)反映企業(yè)利潤(rùn)最大化

maxZ=

2x1+3x2

(4)非負(fù)約束：兩產(chǎn)品的產(chǎn)量為非負(fù)

x1≥0，x2≥0LP模型：s.t.(subjectto)使?jié)M足，使服從例1-2見(jiàn)教材第5頁(yè)2024/5/175編輯版ppt例1-3.某工地租賃甲、乙兩種機(jī)械安裝A、B、C三種構(gòu)件，這兩種機(jī)械每天的安裝能力、租賃費(fèi)用以及工程任務(wù)如下表所示，問(wèn)如何租賃甲、乙兩機(jī)械才能使總的租賃費(fèi)用最低？構(gòu)件機(jī)械A(chǔ)BC租賃費(fèi)(元/天)甲（根/天）乙（根/天）任務(wù)（根）

56250

8630010207002503502024/5/176編輯版ppt【解】設(shè)租賃機(jī)械甲x1天、機(jī)械乙x2天，則該線性規(guī)劃問(wèn)題的數(shù)學(xué)模型為：例1-4見(jiàn)教材第6頁(yè)，例【1.2】人員分配問(wèn)題構(gòu)件機(jī)械A(chǔ)BC租賃費(fèi)(元/天)甲（根/天）乙（根/天）任務(wù)（根）

56250

8630010207002503502024/5/177編輯版ppt某一機(jī)床需要用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是2.9、2.1和1.5m，這些軸需要用同一種圓鋼切割而成，圓鋼長(zhǎng)度為7.4m?，F(xiàn)在要制造100臺(tái)機(jī)床，問(wèn)：最少要用多少圓鋼來(lái)生產(chǎn)這些軸？(切割損失不計(jì))解：1、設(shè)一根圓鋼切割成甲、乙、丙三種軸的根數(shù)分別為y1,y2,y3,則切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示，求這個(gè)不等式關(guān)于y1，y2，y3的非負(fù)整數(shù)解。例如：y1=2，y2=0，則y3只能為1，余料為0.1。像這樣的非負(fù)整數(shù)解共有8組，也就是有8種下料方式，如表1.4所示。

2、建立線性規(guī)劃數(shù)學(xué)模型。設(shè)xj(j=1,2…,8)為第j種下料方案所用圓鋼的根數(shù)。思考題：（下料問(wèn)題）2024/5/178編輯版ppt方案規(guī)格12345678需求量y1(2.9m)21110000100y2(2.1m)02103210100y3(1.5m)10130234100總長(zhǎng)7.4m0.10.30.90.01.10.20.81.4余料minZ=x1+x2+x3+x4+x5+x6+x7+x82x1+x2+x3+x4

1002x2+x3+3x5+2x6+x7

100x1+x3+3x4+2x6+3x7+4x8

100xj

0,j=1,2,…,8

(x1=10,x2=50,x4=30,16m)2024/5/179編輯版ppt思考題：某糖果廠用原料A，B，C加工成三種不同牌號(hào)糖果甲、乙、丙。已知各種糖果的中A，B，C的含量，原料成本，各種原料每月的限制用量，三種牌號(hào)糖果的單位加工費(fèi)及售價(jià)如下表所示。問(wèn)該廠每月生產(chǎn)這三種牌號(hào)糖果各多少kg，利潤(rùn)最大？甲乙丙原料成本(元/kg)每月限制用量(kg)A≥60%≥30%2.002000B1.502500C≤20%≤50%≤60%1.001200加工費(fèi)(元/kg)0.500.400.30售價(jià)(元/kg)3.402.852.252024/5/1710編輯版ppt解：設(shè)xij為生產(chǎn)第j種糖果使用的第i種原料的公斤數(shù)，i=1,2,3；j=1,2,3，則該問(wèn)題的數(shù)學(xué)模型可歸結(jié)為：

最優(yōu)解：即該廠每月應(yīng)生產(chǎn)甲種牌號(hào)糖果906.67kg，乙種牌號(hào)糖果4793.33kg。2024/5/1711編輯版ppt思考題：（投資問(wèn)題）

某投資公司在第一年初有100萬(wàn)元資金，每年都有如下的投資方案：假使第一年初投入一筆資金，第二年初又繼續(xù)投入此資金的50%，那么到第三年初就可回收第一年初投入資金的兩倍。問(wèn)：該投資公司如何確定投資策略使第六年初所擁有的資金最多？解：設(shè)x1為第一年的投資，x2為第一年的保留資金，則：x1

+x2=100第二年：設(shè)x3為第二年新的投資，x4為第二年的保留資金，則：2024/5/1712編輯版ppt第三年：設(shè)x5為新的投資，x6為第三年的保留資金；第四年：設(shè)新的投資x7，第四年的保留資金x8

；第五年：設(shè)x9為第五年的保留資金。根據(jù)題意，第五年初不再進(jìn)行新的投資，因?yàn)檫@筆投資要到第七年初才能收回。約束條件每年應(yīng)滿足如下的關(guān)系：追加投資金額+新投資金額+保留資金=可利用的資金總額

2024/5/1713編輯版pptX*＝(22.64,72.36,58.54,0,26.02,0,104.06,0,0)T，Z*＝208.12。到第六年初，實(shí)有資金總額為x9+2x7，整理后得到下列線性規(guī)劃模型：maxZ=2x7+x9

第一年投資22.64元;第二年新投資58.54元;第三年新投資26.02元;第四年新投資104.06元;第六年初擁有資金208.12萬(wàn)元。2024/5/1714編輯版ppt思考題：某人有30萬(wàn)元資金，在今后的三年內(nèi)有以下投資項(xiàng)目可供參考：

(1)三年內(nèi)的每年年初均可投資，每年獲利為投資額的20%，其本利可一起用于下一年的投資；

(2)只允許第一年年初投入，第二年末可收回，本利合計(jì)為投資額的150%，但此類投資額不超過(guò)15萬(wàn)元；

(3)第二年初允許投資，可于第三年末收回，本利合計(jì)為投資額的160%，這類投資限額20萬(wàn)元；

(4)第三年初允許投資，一年回收，可獲利40%，投資限額為10萬(wàn)元。試為該人確定一個(gè)使第三年末本利和為最大的投資計(jì)劃？（假設(shè)有錢(qián)就用于投資）設(shè)xij為第i年初投入到j(luò)項(xiàng)目的資金額2024/5/1715編輯版ppt項(xiàng)目投資時(shí)間1234第1年初x11x12第2年初x21x23第3年初x31x34對(duì)于約束條件：第1年，可用于項(xiàng)目1和2投資：

x11+x12=300000第2年，可用于項(xiàng)目1和3投資，投資額為x11的本利和：x21+x23=1.2x11第3年，可用于項(xiàng)目1和4投資，投資額x21和x12有關(guān)：x31+x34=1.2x21+1.5x12投資限額：x12≤150000;x23≤200000;x34≤100000非負(fù)約束：xij

≥0(i=1,2,3;j=1,2,3,4)對(duì)于目標(biāo)函數(shù)，只需考慮第3年末的收益：項(xiàng)目1：x31→1.2x31(本利和)；項(xiàng)目2：x22→0；項(xiàng)目3：x23→1.6x23

(本利和)；項(xiàng)目4：x34→1.4x34

(本利和)；maxZ=1.2x31+1.6x23+1.4x34

2024/5/1716編輯版ppt解：設(shè)xij為第i年初投入到j(luò)項(xiàng)目的資金額，其數(shù)學(xué)模型為：maxZ=1.2x31+1.6x23+1.4x34

注意本題條件：有錢(qián)就會(huì)用于投資，即：可利用的資金=投資金額，據(jù)此建立約束等式。x11+x12=300000x21+x23=1.2x11x31+x34=1.2x21+1.5x12x12≤150000x23≤200000x34≤100000xij≥0(i=1,2,3;j=1,2,3,4)2024/5/1717編輯版ppt二、線性規(guī)劃問(wèn)題的數(shù)學(xué)模型3.30線性規(guī)劃問(wèn)題的數(shù)學(xué)模型包括三大要素：（1）一組決策變量（x1,x2,…,xn），是模型中需要首確定的未知量。（2）一組約束條件，是模型中決策變量受到的約束限制，包括兩個(gè)部分：不等式或等式；非負(fù)取值（實(shí)際問(wèn)題）。（3）一個(gè)目標(biāo)函數(shù)，是關(guān)于決策變量的最優(yōu)函數(shù)，max或min。2024/5/1718編輯版ppt思考：為什么稱以上問(wèn)題為線性規(guī)劃問(wèn)題呢？其主要特征是：1.解決的問(wèn)題是規(guī)劃問(wèn)題；2．解決問(wèn)題的目標(biāo)函數(shù)是多個(gè)決策變量的線性函數(shù)，通常是求最大值或最小值；3．解決問(wèn)題的約束條件是多個(gè)決策變量的線性不等式或等式。2024/5/1719編輯版ppt線性規(guī)劃問(wèn)題模型的一般形式可總結(jié)為：線性規(guī)劃問(wèn)題模型的一般形式用一組非負(fù)決策變量表示的一個(gè)決策問(wèn)題；存在一組等式或不等式的線性約束條件；有一個(gè)希望達(dá)到的目標(biāo)，可表示成決策變量的極值線性函數(shù)。為了書(shū)寫(xiě)方便，上式也可簡(jiǎn)寫(xiě)：2024/5/1720編輯版ppt一般地，xj≥0，但有時(shí)xj≤0或xj無(wú)符號(hào)限制。2024/5/1721編輯版ppt其中：cj為價(jià)值系數(shù)，C=(c1,c2,…,cn)為價(jià)值向量；aij為技術(shù)系數(shù)，A=(P1,P2,…,Pn)為技術(shù)矩陣，如：

P1=(a11,a21,…,am1)T，

P2=(a12,a22,…,am2)T，

……Pn=(a1n,a2n,…,amn)T；

bi為限制系數(shù)，b=(b1,b2,…,bm)T。2024/5/1722編輯版ppt線性規(guī)劃模型矩陣形式，其中：X=(x1,x2,…,xn)T；

C=(c1,c2,…,cn)

；

b=(b1,b2,…,bm)T。技術(shù)系數(shù)矩陣：2024/5/1723編輯版ppt第二節(jié)用于兩個(gè)變量線性規(guī)劃問(wèn)題的圖解法1、概念：利用幾何圖形求解兩個(gè)變量線性規(guī)劃問(wèn)題的方法。

3、求解步驟：

第一步：建立平面直角坐標(biāo)系；

第三步：在可行域內(nèi)平移目標(biāo)函數(shù)等值線，確定最優(yōu)解及最優(yōu)目標(biāo)函數(shù)值。

2、特點(diǎn)：簡(jiǎn)單、直觀，但只適用于兩個(gè)變量的LP問(wèn)題。

第二步：根據(jù)約束條件畫(huà)出可行域；2024/5/1724編輯版ppt可行解：滿足約束條件的解；可行域：所有可行解的集合；最優(yōu)解：使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解。

可行域：滿足所有約束條件的解的集合，即所有約束條件共同圍城的區(qū)域。maxZ=3x1+5x2

2x1≤162x2≤10

3x1+4x2≤32x1≥0,x2≥0s.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD2024/5/1725編輯版ppt2x1=162x2=10x1x28103583x1+4x2=320ABCD目標(biāo)函數(shù)等值線目標(biāo)函數(shù)Z=3x1+5x2

代表以Z

為參數(shù)的一族平行線。Z=25Z=37Z=15(4,5)2024/5/1726編輯版ppt例：用圖解法求解線性規(guī)劃問(wèn)題？

①坐標(biāo)系：橫坐標(biāo)x1

，縱坐標(biāo)x2

Z=360(2,6)②先將約束不等式變?yōu)榈仁?，?huà)出各等式對(duì)應(yīng)的直線，然后再根據(jù)不等式符號(hào)確定可行域*線性規(guī)劃問(wèn)題解的可能結(jié)論：該問(wèn)題具有唯一最優(yōu)解，X*=(2,6)T，Z*=360③向上平移目標(biāo)函數(shù)等值線x2=-3x1/5+Z/50，確定最優(yōu)解。2024/5/1727編輯版pptx1x2O1020304010203040(15,10)最優(yōu)解X*=(15,10)T最優(yōu)值Z*

=852024/5/1728編輯版ppt246x1x2246最優(yōu)解X*

=(3,1)T最優(yōu)值Z*

=5(3,1)minZ=x1+2x22024/5/1729編輯版ppt例：用圖解法進(jìn)行求解線性規(guī)劃問(wèn)題？

如果線性規(guī)劃問(wèn)題有兩個(gè)最優(yōu)解，則它一定有無(wú)窮多最優(yōu)解（多重最優(yōu)解）。2024/5/1730編輯版ppt例用圖解法求線性規(guī)劃問(wèn)題？2024/5/1731編輯版ppt該線性規(guī)劃問(wèn)題具有無(wú)界解。可行域無(wú)上界，目標(biāo)值可以無(wú)限增大(缺乏必要約束)2024/5/1732編輯版ppt例2024/5/1733編輯版ppt該線性規(guī)劃問(wèn)題無(wú)可行解，原因：線性規(guī)劃問(wèn)題的可行域是空集(約束條件相互矛盾)2024/5/1734編輯版pptx2x1O10203040102030405050無(wú)可行解即無(wú)最優(yōu)解maxZ=10x1+4x22024/5/1735編輯版ppt

圖解法的解題思路和幾何上的直觀表示，對(duì)求解線性規(guī)劃問(wèn)題的求解具有重要啟示：

（1）LP問(wèn)題的解一般有唯一解、無(wú)窮多最優(yōu)解、無(wú)界解和無(wú)可行解四種情況。（2）LP問(wèn)題的可行域一般為無(wú)界或有界凸多邊形。（3）若LP問(wèn)題的最優(yōu)解存在，即有唯一最優(yōu)解或無(wú)窮多最優(yōu)解，則必在可行域的某個(gè)項(xiàng)點(diǎn)上找到最優(yōu)解。（4）若LP問(wèn)題有兩個(gè)最優(yōu)解，則在它們的連線上的任意一點(diǎn)都是最優(yōu)解。

作業(yè)：教材第37頁(yè)，1.3：(1)、(2)、(3)；1.42024/5/1736編輯版ppt一、線性規(guī)劃數(shù)學(xué)模型的標(biāo)準(zhǔn)型第三節(jié)線性規(guī)劃問(wèn)題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式1、標(biāo)準(zhǔn)型表達(dá)方式(1)代數(shù)式：

(2)向量式：

(3)矩陣式：

A：技術(shù)系數(shù)矩陣，簡(jiǎn)稱系數(shù)矩陣；B：可用的資源量，稱資源向量；C：決策變量對(duì)目標(biāo)的貢獻(xiàn)，稱價(jià)值向量；X：決策向量。2024/5/1737編輯版ppt通常X記為：

，其中，Ａ為約束方程的系數(shù)矩陣，m是約束方程的個(gè)數(shù)，n是決策變量的個(gè)數(shù)，一般情況m≤n，且r(Ａ)＝m。其中:2024/5/1738編輯版ppt2、一般型→標(biāo)準(zhǔn)型的轉(zhuǎn)換方法(1)“決策變量非負(fù)”。若某決策變量xk為“取值無(wú)約束”(無(wú)符號(hào)限制)，令：xk=x’k–x”k，(x’k≥0,x”k≥0)。(2)“目標(biāo)函數(shù)求最大值”。如果極小化原問(wèn)題minZ=CX，則令Z’=–Z，轉(zhuǎn)為求maxZ’=–CX。注意：求解后還原。(3)“約束條件為等式”。對(duì)于“≤”型約束，則在“≤”左端加上一個(gè)非負(fù)松弛變量(slackvariable)，使其為等式。對(duì)于“≥”型約束，則在“≥”左端減去一個(gè)非負(fù)剩余變量(Surplusvariable)，使其為等式。(4)“資源限量非負(fù)”。若某個(gè)bi<0，則將該約束兩端同乘“–1”，以滿足非負(fù)性的要求。2024/5/1739編輯版ppt【例】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型？【解】(1)因?yàn)閤3無(wú)符號(hào)要求(取值無(wú)約束)，x3可以取正值也可取負(fù)值，但標(biāo)準(zhǔn)型中要求變量非負(fù)，所以可令：對(duì)于x1≤0

，可令：2024/5/1740編輯版ppt

(3)第二個(gè)約束條件是“≥”號(hào)，在“≥”左端減去剩余變量x5，x5≥0，x5也稱松馳變量

(2)第一個(gè)約束條件是“≤”號(hào)，在“≤”左端加入松馳變量x4，x4≥0，化為等式；(4)第三個(gè)約束條件右端常數(shù)項(xiàng)為負(fù)數(shù)，因此在不等式兩端乘以“－1”。

(5)目標(biāo)函數(shù)是最小值，令Z′=－Z,得到maxZ′=max(－Z)，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值，反之亦然。(1)x3取值無(wú)約束，令x3=x3’－x3’’，x3’,x3’’≥0。同時(shí)2024/5/1741編輯版ppt標(biāo)準(zhǔn)型為：2024/5/1742編輯版ppt【練習(xí)】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型？【解】(1)因?yàn)閤3無(wú)符號(hào)要求(取值無(wú)約束)，即x3取正值也可取負(fù)值，但標(biāo)準(zhǔn)型中要求變量非負(fù)，所以可令：2024/5/1743編輯版ppt

(3)第二個(gè)約束條件是“≥號(hào)”，在“≥號(hào)”左端減去剩余變量x5，x5≥0，x5也稱松馳變量

(2)第一個(gè)約束條件是“≤號(hào)”，在“≤”左端加入松馳變量x4，x4≥0，化為等式；(4)第三個(gè)約束條件是“≤號(hào)”且常數(shù)項(xiàng)為負(fù)數(shù)，因此在“≤”左邊加入松馳變量x6，x6≥0，同時(shí)不等式兩端乘以“－1”。

(5)目標(biāo)函數(shù)是最小值，令Z′=－Z,得到maxZ′=max(－Z)，即當(dāng)Z達(dá)到最小值時(shí)Z′達(dá)到最大值，反之亦然。(1)x3取值無(wú)約束，令x3=x3’－x3’’，x3’,x3’’≥0。

作業(yè)：教材第38頁(yè)，1.5：(1)、(2)、(3)2024/5/1744編輯版ppt【練習(xí)】將下列線性規(guī)劃化為標(biāo)準(zhǔn)型？(教材第38頁(yè)，1.5)【解】先將模型變換成一般形式：標(biāo)準(zhǔn)型：2024/5/1745編輯版ppt第四節(jié)線性規(guī)劃問(wèn)題解的一般性質(zhì)

1、線性規(guī)劃解的概念

基矩陣：一個(gè)非奇異的子矩陣（線性無(wú)關(guān)）。矩陣A中任意一個(gè)m列的線性無(wú)關(guān)子矩陣B

，稱為一個(gè)基(矩陣)。組成基的列向量稱為基向量，用Pj表示(i=1,2,…,m)?；兞浚号c基向量Pj相對(duì)應(yīng)的變量xj稱為基變量。其余的n–m個(gè)變量稱為非基變量(基矩陣以外的列向量對(duì)應(yīng)變量)?；?本)解：令所有非基變量等于零，得出的唯一解。2024/5/1746編輯版ppt重要概念

可行解：滿足約束條件AX=b和X≥0的解?；?本)解：令所有非基變量等于零，得出的唯一解?；?本)可行解：滿足X≥0的基解?？尚谢夯尚薪鈱?duì)應(yīng)的基矩陣。最優(yōu)解：使目標(biāo)函數(shù)最優(yōu)的基可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對(duì)應(yīng)的基矩陣，稱為最優(yōu)基。2024/5/1747編輯版ppt基的概念

假設(shè)線性規(guī)劃問(wèn)題模型系數(shù)矩陣為m行、n列，則系數(shù)矩陣中秩為m的m行m列子矩陣，稱為基矩陣，簡(jiǎn)稱為基?；械牧邢蛄繉?duì)應(yīng)的變量稱為基變量，決策變量中基變量以外的變量稱為非基變量。2024/5/1748編輯版ppt基本解

對(duì)于某一確定的基，令所有非基變量為0，由約束方程組AX=b可解出m個(gè)基變量的唯一解，稱為一個(gè)基本解。2024/5/1749編輯版ppt基本可行解

滿足非負(fù)條件的基本解，稱為基本可行解，基本可行解對(duì)應(yīng)于凸多邊形的項(xiàng)點(diǎn)。2024/5/1750編輯版ppt練習(xí)：已知線性規(guī)劃問(wèn)題4.2

問(wèn)：中哪一個(gè)是基本可行解？2024/5/1751編輯版ppt二、線性規(guī)劃問(wèn)題解的性質(zhì)1、凸集和極點(diǎn)(頂點(diǎn))的概念由約束條件形成的可行域是凸多邊形(凸集)凸集：對(duì)于某一集合內(nèi)部任意兩點(diǎn)連線上的點(diǎn)都屬于這個(gè)集合，我們就稱這個(gè)集合為凸集(直觀理解)。abcd可行域具有有限個(gè)頂點(diǎn)。目標(biāo)函數(shù)最優(yōu)值一定在可行域的邊界(頂點(diǎn))達(dá)到，而不可能在其區(qū)域的內(nèi)部。2024/5/1752編輯版ppt凸集的數(shù)學(xué)定義設(shè)K為n維歐氏空間的一個(gè)點(diǎn)集，若K中任意兩個(gè)點(diǎn)X1和X2連線上的所有點(diǎn)都屬于K，則稱K為凸集。X2X1X設(shè)X(x1,x2,…,xn);X1(u1,u2,…,un);X2(v1,v2,…,vn)2024/5/1753編輯版ppt極點(diǎn)：設(shè)S為凸集，若S中的點(diǎn)x不能成為S中任何線段的內(nèi)點(diǎn)，即“不能用S中兩個(gè)不同的點(diǎn)線性表示”，則稱x為S的極點(diǎn)。2024/5/1754編輯版ppt定理1.1

若線性規(guī)劃問(wèn)題的可行域非空，則S為凸集(有界或無(wú)界)。即連接任意兩個(gè)可行解的線段上的點(diǎn)仍為可行解。定理1.2

線性規(guī)劃問(wèn)題的可行域S中的點(diǎn)X是極點(diǎn)的充要條件是X是基本可行解。即凸多邊形的頂點(diǎn)就是基本可行解。定理1.3

若可行域有界，線性規(guī)劃的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)。如果線性規(guī)劃問(wèn)題有最優(yōu)解，則最優(yōu)解一定在可行域S的某個(gè)極點(diǎn)上得到。

2024/5/1755編輯版ppt第五節(jié)單純形法原理一、線性規(guī)劃問(wèn)題的解題思路⑴首先，找到一個(gè)初始基可行解，也就是找到一個(gè)初始可行基，想辦法判斷這個(gè)基可行解是不是最優(yōu)解。⑵如果是最優(yōu)解，就得到這個(gè)線性規(guī)劃問(wèn)題的最優(yōu)解；⑶如果判斷出不是最優(yōu)解，就想法由這個(gè)可行基按一定規(guī)則變化到下一個(gè)可行基，然后再判斷新得到的基可行解是不是最優(yōu)解；⑷如果還不是，再接著進(jìn)行下一個(gè)可行基變化，直至找到最優(yōu)解。2024/5/1756編輯版ppt求解線性規(guī)劃問(wèn)題的思路﹣單純形法確定初始基本可行解判斷該可行解是否最優(yōu)確定新的基本可行解結(jié)束是否2024/5/1757編輯版ppt一、用消化法求解線性規(guī)劃問(wèn)題（教材第20頁(yè)例題）解：(一)標(biāo)準(zhǔn)化：(二)求初始基可行解2024/5/1758編輯版ppt令非基變量：x1=x2=0，

得到初始基可行解：

X(0)=(0,0,4,3,8)T此時(shí)，目標(biāo)函數(shù)值：

Z(0)=2x1+5x2+0=0

目標(biāo)函數(shù)用非基變量表示。(三)判優(yōu)對(duì)于Z(0)=2x1+5x2，若x1或x2從0變?yōu)檎龜?shù)，則目標(biāo)函數(shù)值會(huì)增加，因此可判斷X(0)一定不是最優(yōu)解。

(X(0)≠X*)2024/5/1759編輯版pptZ(0)=2x1+5x2(四)方案調(diào)整(換基)尋找一個(gè)新的基可行解，使目標(biāo)函數(shù)值得到改善。

①選擇入基變量

尋找使目標(biāo)函數(shù)增加量最大的非基變量入基，即目標(biāo)函數(shù)中系數(shù)最大的變量。(x2↓)

②選擇出基變量

為什么要選擇原基變量出基？要求決策變量非負(fù)，因此有：說(shuō)明x2最大可以是3，且當(dāng)x2=3時(shí)，x4=0，即x4出基

。(←

x4)

2024/5/1760編輯版ppt(五)求新的基可行解此時(shí)，基變量為x3、x2和x5，非基變量為x1和x4。

用非基變量表示基變量：

用x4表示x2，x2=3–x4，

用x4表示x5，x5=2–x1–2x4。

令非基變量x1=x4=0，則X(1)=(0,3,4,0,2)T。2024/5/1761編輯版ppt(六)判優(yōu)(檢驗(yàn))

將式(4)代入目標(biāo)函數(shù)，目的：用非基變量表示目標(biāo)函數(shù)，得到新的目標(biāo)函數(shù)值：

Z(1)=2x1+5x2=2x1+5(3–x4)

=2x1–5x4+15非基變量x1的系數(shù)為2，大于零，可見(jiàn)，如果x1能從非基變量變?yōu)榛兞浚醋優(yōu)檎龜?shù)，則目標(biāo)函數(shù)值會(huì)增加，因此X(1)=(0,3,4,0,2)T不是最優(yōu)解。2024/5/1762編輯版pptZ(1)=2x1–5x4+15(七)換基當(dāng)x1=2時(shí)，x5=0即：當(dāng)x1入基，x5

出基。2024/5/1763編輯版ppt(八)求新的基可行解此時(shí)，基變量為x3、x2和x1，非基變量為x4和x5。

用非基變量表示基變量：

x1=2+2x4–x5，

x3=2–2x4+x5

。

令非基變量x4=x5=0，則

X(2)=(2,3,2,0,0)T。2024/5/1764編輯版ppt松弛變量x3=2說(shuō)明第一項(xiàng)資源有剩余，資源相對(duì)寬松，這就是松馳變量的經(jīng)濟(jì)含義。(九)判優(yōu)(檢驗(yàn))非基變量x4和x5的系數(shù)均為負(fù)值，如果x4和x5從非基變量變?yōu)榛兞浚磸牧阕優(yōu)檎龜?shù)，則目標(biāo)函數(shù)值會(huì)減少，因此X(2)=(2,3,2,0,0)T是最優(yōu)解，目標(biāo)函數(shù)最優(yōu)值Z*=19。2024/5/1765編輯版ppt求解過(guò)程(換基迭代過(guò)程)初始基初始基可行解：X(0)=(0,0,4,3,8)TZ(0)=0新的基可行解：X(1)=(0,3,4,0,2)TZ(1)=15新的可行基最優(yōu)基最優(yōu)解：X*=(2,3,2,0,0)TZ*=192024/5/1766編輯版ppt單純形法原理-矩陣推導(dǎo)(1)2024/5/1767編輯版ppt單純形法原理-矩陣推導(dǎo)(2)非基變量檢驗(yàn)數(shù)令非基變量等于0，則2024/5/1768編輯版pptCjCBCNCBXBbXBXN0XBbBNσjCBCNCBXBbXBXNCBXBB-1bIB-1Nσj0CN–CBB-1N單純形法原理(單純形表)2024/5/1769編輯版ppt

單純形法求解線性規(guī)劃問(wèn)題的步驟：

(1)求出初始基本可行解(標(biāo)準(zhǔn)化、單位基)；

(2)最優(yōu)性檢驗(yàn)(非基變量檢驗(yàn)數(shù)非正時(shí)停止，否則進(jìn)入下一步)；

(3)換基(迭代)；①確定入基變量②確定出基變量③初等變換，求出新的基本可行解

(4)重復(fù)步驟(2)、(3)，直到求出最優(yōu)解。2024/5/1770編輯版ppt單純形法求解步驟舉例

maxZ=2x1+5x2

+0x3

+0x4+0x5x1+x3

=4

x2+x4

=3x1+2x2+x5=8

xj≥0,j=1,2,…,5CjθiCBXBb檢驗(yàn)數(shù)

jx1x2x3x4x525000410100301010812001x3x4x5000025000–3/1=38/2=42024/5/1771編輯版ppt4101003010102100-21x3x2x5050200-504–2CjθiCBXBb檢驗(yàn)數(shù)

jx1x2x3x4x525000檢驗(yàn)數(shù)

j2001221x3x2x1052000-1-2最優(yōu)解:X*=(2,3,2,0,0)T，Z*=19思考:在最終單純形表中，B-1=？4.82024/5/1772編輯版ppt單純形法的管理啟示x1=4x2=3x1+2x2

=8x1x2430ABC(2,3)DX(0)=(0,0,4,3,8)TX(1)=(0,3,4,0,2)TX(2)=(2,3,2,0,0)T在管理過(guò)程中，把現(xiàn)有方案作為初始方案，找到最急需要改進(jìn)的某個(gè)問(wèn)題和改進(jìn)方向，一次做好某個(gè)主要問(wèn)題的解決與改進(jìn)；一次只解決和改進(jìn)一個(gè)問(wèn)題的難度最小；解決之后，再尋求可以改進(jìn)的其它地方，再次改進(jìn)，不斷地追求更優(yōu)。2024/5/1773編輯版ppt解：引入松馳變量x3,x4,x5

，化為標(biāo)準(zhǔn)形式：2024/5/1774編輯版ppt

cj

25000

CB

XB

b

x1

x2

x3

x4x5

000

x3x4x5

438

101000101012001

σj

0

25000由于x1，x2的檢驗(yàn)數(shù)均為非負(fù)，且x2的檢驗(yàn)數(shù)σ2最大，選x2為入基變量；再按最小比值θl=min(-,3/1,8/2)=3，選x4為出基變量。

cj

25000

CB

XB

b

x1

x2

x3

x4x5

0

0

x3

x5

43

1010001010

σj

x252100-21200-50152024/5/1775編輯版ppt

cj

25000

CB

XB

b

x1

x2

x3

x4x5

050

x3x2x5

432

1010001010100-21

σj

15

200-50由于x1檢驗(yàn)數(shù)為非負(fù)，選x1為入基變量；再按最小比值

θl

=min（4/1,-,2/1）=2，選x5為出基變量。

cj

25000

CB

XB

b

x1

x2

x3

x4x5

05

x3x2

32

01010100-21

σj

x122001

2-1000-1-2192024/5/1776編輯版ppt

初始基本可行解：X(0)=(0,0,4,3,8)T，Z(0)=0

新的基本可行解：X(1)=(0,3,4,0,2)T，Z(1)=15

新的基本可行解：X(2)=(2,3,2,0,0)T，Z(2)=19

判別定理1：在單純形表中，若所有非基變量的檢驗(yàn)數(shù)小于零，且B-1b均為非負(fù)，則線性規(guī)劃問(wèn)題具有唯一最優(yōu)解。2024/5/1777編輯版ppt圖解法與單純形法求解結(jié)果對(duì)照：x1x1=4x2=3x1+2x2=8x2(2,3)x2=-(2/5)x1+Z/5

A

(0,0)A：X(0)=(0,0,4,3,8)T，Z(0)=0

B

(0,3)B：X(1)=(0,3,4,0,2)T，Z(1)=15

C

C：X*=(2,3,2,0,0)T，Z*=19

D(4,2)

E(4,0)2024/5/1778編輯版ppt課堂練習(xí)

求解下列線性規(guī)劃問(wèn)題解：引進(jìn)松馳變量x3,x4,x5，化為標(biāo)準(zhǔn)形式：2024/5/1779編輯版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

000

x3x4x5

4102

-12100120101-1001

σj

0

24000

cj

24000

CB

XB

b

x1

x2

x3

x4x5

00

x4x5

σj

x242-1/21

1/200620-11041/201/20140-20082024/5/1780編輯版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

400

x2x4x5

264

-1/211/20020-1101/201/201

σj

8

40-200

cj

24000

CB

XB

b

x1

x2

x3

x4x5

4

0

x2

x5

σj

x12310-1/2

1/20011/41/407/2003/4-1/415/200-202002024/5/1781編輯版ppt

cj

24000

CB

XB

b

x1

x2

x3

x4x5

420

x2x1x5

7/235/2

011/41/4010-1/21/20003/4-1/41

σj

20

000-20

cj

24000

CB

XB

b

x1

x2

x3

x4x5

42

x2x1

σj

x3010/3001

-1/34/38/30101/3-1/314/31001/32/300-200202024/5/1782編輯版ppt

初始基本可行解：X(0)=(0,0,4,10,2)T，Z(0)=0

新的基本可行解：X(1)=(0,2,0,6,4)T，Z(1)=8

新的基本可行解：X(2)=(3,7/2,0,0,5/2)T，Z(2)=20

新的基本可行解：X(3)=(14/3,8/3,10/3,0,0)T，Z(3)=20

判別定理2：在單純形表中，若所有非基變量的檢驗(yàn)數(shù)小于等于零，且B-1b均為非負(fù)，其中某個(gè)檢驗(yàn)數(shù)等于零，則線性規(guī)劃問(wèn)題具有無(wú)窮多最優(yōu)解(多重最優(yōu)解)。2024/5/1783編輯版ppt圖解法求解結(jié)果：

A

(0,0)A：X(0)=(0,0,4,10,2)T，Z(0)=0

B

(0,2)B：X(1)=(0,2,0,6,4)T，Z(1)=8

C(3,7/2)C：XC*=(3,7/2,0,0,5/2)T，Z*=20D(14/3,8/3)E(2,0)D：XD*=(14/3,8/3,10/3,0,0)T，Z*=202024/5/1784編輯版ppt例

求解下列線性規(guī)劃問(wèn)題解：引進(jìn)松馳變量x3,x4，標(biāo)準(zhǔn)化：2024/5/1785編輯版ppt

cj

-2300

CB

XB

b

x1

x2

x3

x4

00

x3x4

24

4-2102-301

σj

0

-2300不滿足出基變量確定法則：雖然，不能確定x3和x4中哪個(gè)變量出基，但無(wú)論哪個(gè)變量出基，都必須滿足：x3≥0，x4≥0。x2入基，則：x2>

0(x2≥0)。說(shuō)明x2可以無(wú)限增大，所以目標(biāo)函數(shù)值可以無(wú)限增大。2024/5/1786編輯版ppt圖解法求解結(jié)果：判定定理3：在單純形表中，若某個(gè)檢驗(yàn)數(shù)σk大于零，且xk對(duì)應(yīng)列向量的元素均為非正，導(dǎo)致出基變量無(wú)法確定，則線性規(guī)劃問(wèn)題具有無(wú)界解。2024/5/1787編輯版ppt練習(xí)

求解下列線性規(guī)劃問(wèn)題解：引進(jìn)松馳變量x3,x4，化為標(biāo)準(zhǔn)形式：從標(biāo)準(zhǔn)形中可看出存在可行基B=(P3，P4)=I，基變量為X3，X4；非基變量為X1，X2。建立初始單純形表得：2024/5/1788編輯版pptcj

4300CBXBb

x1

x2

x3

x400x3x42426

23103201

0

4300

由于x1，x2的檢驗(yàn)數(shù)均為非負(fù)，且x1的檢驗(yàn)數(shù)絕對(duì)值最大，選取x1為進(jìn)基變量；再按最小比值θ=min（24/2，26/3）=26/3，選取x4為出基變量，進(jìn)行換基迭代。cj

4300CBXBb

x1

x2x3

x404x3x120/326/3

05/31-2/312/301/3

104/3

01/30-4/32024/5/1789編輯版pptcj

4300CBXBb

x1

x2

x3

x434x2x146

013/5-2/510-2/53/5

36

00-1/5-6/5表中最后一行的所有檢驗(yàn)數(shù)均為非正，表明目標(biāo)函數(shù)已達(dá)到最大值，上表為最優(yōu)單純形表。從表中可得到最優(yōu)解為：X*=(x1,x2,x3,x4)T=(6,4,0,0)T，最優(yōu)值為：Z*=36。作業(yè)：教材39頁(yè)，1.8第(1),(4)題在最終單純形表中，所有非基變量檢驗(yàn)數(shù)均為負(fù)數(shù)，說(shuō)明該線性規(guī)劃問(wèn)題具有唯一最優(yōu)解：X=(6,4,0,0)T，Z*=36。2024/5/1790編輯版pptcj

2-11000CBXBb

x1

x2

x3

x4

x5

x6000x4x5x6601020

3111001-1201011-1001

-21-1000

練習(xí)：已知某線性規(guī)劃用單純形法求得的某兩步迭代表如下，請(qǐng)將表中空白處填上適當(dāng)?shù)臄?shù)字。

cj

000011CBXBb

x1

x2

x3

x4

x5

x602-1x4x1x2

1-1-201/21/20-1/21/2

cj

000011CBXBb

x1

x2

x3

x4

x5

x602-1x4x1x210155

0011-1-2

101/201/21/2

01-3/20-1/21/2

25

00-3/20-3/2-1/22024/5/1791編輯版ppt討論：用單純形法求解某極大化問(wèn)題的單純形表如下，問(wèn)表中參數(shù)a1,a2,a3,d,

1,

2為何取值范圍時(shí)，下列結(jié)論成立。

cj

000011

CB

XB

b

x1

x2

x3

x4

x5

x6

300

x3

x4

x6

d23

4a110a20-1-301-10

a3-500-41

j

1

200-30

(1)表中解為唯一最優(yōu)解：(2)表中解為無(wú)窮多最優(yōu)解：(3)該問(wèn)題具有無(wú)界解：(4)表中解為退化的基解：(5)表中解為不可行解：(6)x1入基，x6出基：

1≤0,

2≤0,

1×

2=0,d

0

1<

0,

2<

0,d

0

2>0,a1

0,d

0d=0

d<0

1>0,a3

>0,d

>0,d/4>

3/a32024/5/1792編輯版ppt思考題：已知線性規(guī)劃問(wèn)題：其中b1,b2是常數(shù)，且已知此問(wèn)題的最終單純形表如下。試確定表中所有的參數(shù)及b1和b2的值？cj

52300CBXBb

x1

x2

x3

x4

x5

50x1x53010

1b2100c-8-11

150

0a-7d

e

e=0,d=–5,

b=5,c=–10,a=–23,b1=30,b2=402024/5/1793編輯版ppt思考題：已知線性規(guī)劃問(wèn)題的最優(yōu)單純形表如下，求初始單純形表中參數(shù)C,A,b以及最優(yōu)基B？cj

c1

c2c3c4c5

CB

XB

b

x1

x2

x3

x4

x5

c1c2

x1x2

62

10

41/61/1501-301/5

σj

00-1-2-32024/5/1794編輯版ppt解法(一)：矩陣初等行變換增廣矩陣：求A和b：2024/5/1795編輯版ppt求cj：cj

c