第1章 線性規(guī)劃基本模型

1、山西大學經濟與管理學院山西大學經濟與管理學院主講：范建平主講：范建平 博士博士運籌學山西大學經濟與管理學院山西大學經濟與管理學院第一章 線性規(guī)劃基本模型1.1 線性規(guī)劃的實用模型2021年11月3日星期三山西大學經濟與管理學院 范建平3在管理中一些典型的線性規(guī)劃應用4p合理利用線材問題合理利用線材問題：如何在保證生產的條件下，下料最少：如何在保證生產的條件下，下料最少p配料問題配料問題：在原料供應量的限制下如何獲取最大利潤：在原料供應量的限制下如何獲取最大利潤p投資問題投資問題：從投資項目中選取方案，使投資回報最大：從投資項目中選取方案，使投資回報最大p產品生產計劃產品生產計劃：合理利用人力、

2、物力、財力等，使獲利最大：合理利用人力、物力、財力等，使獲利最大p勞動力安排勞動力安排：用最少的勞動力來滿足工作的需要：用最少的勞動力來滿足工作的需要p運輸問題運輸問題：如何制定調運方案，使總運費最?。喝绾沃贫ㄕ{運方案，使總運費最小2021年11月3日星期三山西大學經濟與管理學院 范建平1、資源分配模型p 例例1.1 某裝配廠擬生產甲、乙兩種新產品，每件利潤分某裝配廠擬生產甲、乙兩種新產品，每件利潤分別為別為300元和元和200元。甲、乙產品的部件分別在元。甲、乙產品的部件分別在A、B兩個兩個車間生產，每件甲、乙產品的部件分別消耗車間生產，每件甲、乙產品的部件分別消耗A、B車間車間1、2工時。

3、兩種產品的部件最后都要在工時。兩種產品的部件最后都要在C車間裝配，裝配每車間裝配，裝配每件甲、乙產品分別消耗件甲、乙產品分別消耗2工時和工時和3工時。已知工時。已知A，B，C三三個車間每周可用于這兩種產品的最大生產能力分別為個車間每周可用于這兩種產品的最大生產能力分別為6工工時、時、8工時、工時、18工時，則每周各生產甲、乙產品多少件？工時，則每周各生產甲、乙產品多少件？試建立該問題的數學模型。試建立該問題的數學模型。2021年11月3日星期三5山西大學經濟與管理學院 范建平解：p 列出數據表 產品產品車間車間單耗單耗/ /（工時（工時/ /件）件）最大生產能力最大生產能力/(/(工時工時/

4、/周周) )甲乙A106B028C2318利潤/（1100元/件）321、資源分配模型2021年11月3日星期三6山西大學經濟與管理學院 范建平1、資源分配模型設設 x1, x2 分別為甲、乙產品的周產量（分別為甲、乙產品的周產量（決策變量決策變量） z為這兩種產品每周的總利潤，則由于，z取值受限于x1, x2 ，而x1, x2 受限于A，B，C三個車間的生產能力，則 式（0）稱為目標函數目標函數，z為目標值目標值 產品產品車間車間單耗單耗/ /（工時（工時/ /件）件）最大生產能力最大生產能力/(/(工時工時/ /周周) )甲乙A106B028C2318利潤/（1100元/件）32 1232

5、0zxx1212121060282318xxxxxx約束條件2021年11月3日星期三7山西大學經濟與管理學院 范建平1、資源分配模型p上述函數約束和非負性約束，統(tǒng)稱為約束條件或約束方程，上述函數約束和非負性約束，統(tǒng)稱為約束條件或約束方程，簡稱簡稱約束約束。p綜上所述，例題綜上所述，例題1.1的數學模型簡記如下：的數學模型簡記如下：又因產量x1, x2 取值不能為負，則非負性約束非負性約束120,0 xx 12121212max3201628. .2318,0zxxxxstxxxx2021年11月3日星期三8山西大學經濟與管理學院 范建平1、資源分配模型小結p由目標函數和約束方程構成的一組數學

6、表達式，稱為由目標函數和約束方程構成的一組數學表達式，稱為數數學規(guī)劃學規(guī)劃（模型）；（模型）；p若全為線性表達式，則稱為若全為線性表達式，則稱為線性規(guī)劃線性規(guī)劃（模型）；（模型）；p若組中有一個或更多表達式非線性，則稱為若組中有一個或更多表達式非線性，則稱為非線性規(guī)劃非線性規(guī)劃（模型）。（模型）。2021年11月3日星期三9山西大學經濟與管理學院 范建平線性規(guī)劃的三個要素10p決策變量決策變量n決策問題待定的量值決策問題待定的量值n取值要求非負取值要求非負p約束條件約束條件n任何管理決策問題都是限定在一定的條件下求解任何管理決策問題都是限定在一定的條件下求解n把各種限制條件表示為一組等式或不等

7、式稱約束條件把各種限制條件表示為一組等式或不等式稱約束條件n約束條件是決策方案可行的保障約束條件是決策方案可行的保障n約束條件是決策變量的約束條件是決策變量的線性函數線性函數p目標函數目標函數n衡量決策優(yōu)劣的準則，如時間最省、利潤最大、成本最低衡量決策優(yōu)劣的準則，如時間最省、利潤最大、成本最低n目標函數是決策變量的目標函數是決策變量的線性函數線性函數n有的目標要實現極大，有的則要求極小有的目標要實現極大，有的則要求極小2021年11月3日星期三山西大學經濟與管理學院 范建平1、資源分配模型小結p小結小結：對于例題：對于例題1.1的資源分配問題（的資源分配問題（經營規(guī)劃問題經營規(guī)劃問題），），一

8、般可表述為：一般可表述為：n某企業(yè)擬將現有的某企業(yè)擬將現有的m種資源（用種資源（用i=1,2，m表示）投入表示）投入n項生產或商務活動（用項生產或商務活動（用j=1，2，n表示）。其中第表示）。其中第i種資種資源的數量為源的數量為bi，項目，項目j每經營每經營1個單位所創(chuàng)造的利潤（或價值）個單位所創(chuàng)造的利潤（或價值）為為cj，所消耗的第，所消耗的第i種資源的數量為種資源的數量為aij。為履行合同，項目。為履行合同，項目j的經營數量至少為的經營數量至少為ej；而市場調查，其最高需求量為；而市場調查，其最高需求量為dj。試。試建立其數學模型。建立其數學模型。2021年11月3日星期三11山西大學經

9、濟與管理學院 范建平1、資源分配模型小結p建立線性規(guī)劃模型的一般步驟：建立線性規(guī)劃模型的一般步驟：p1.正確設立決策變量正確設立決策變量n設設xj（j=1,2,n）為項目）為項目j的經營數量。的經營數量。p2.恰當建立目標函數恰當建立目標函數nn項經營活動的總利潤（或總產值，總收入）為項經營活動的總利潤（或總產值，總收入）為p3. 適度構建約束方程適度構建約束方程n（1）合同約束）合同約束n（2）需求約束）需求約束n（3）資源約束）資源約束1njjjzc x1,2,jjxejn1,2,jjxdjn11,2,nijjija xbim2021年11月3日星期三12山西大學經濟與管理學院 范建平1、

10、資源分配模型小結p綜上所述可得綜上所述可得LP模型如下：模型如下：11max1,2,. .1,2,1,2,njjjnijjijjjjjzc xa xbimstxejnxdjn2021年11月3日星期三13山西大學經濟與管理學院 范建平2、產品配套模型p 例例1.2某廠生產一種部件，由某廠生產一種部件，由3個個A零件和零件和5個個B零件配套零件配套組裝成品。該廠有甲、乙、丙三種機床可加工組裝成品。該廠有甲、乙、丙三種機床可加工A，B兩種兩種零件，每種機床的臺數，以及每臺機床每個工作日全部零件，每種機床的臺數，以及每臺機床每個工作日全部用于加工某一種零件的最大產量（即生產率：件用于加工某一種零件的

11、最大產量（即生產率：件/日）見日）見表表1-2。則應如何安排生產？試建立其數學模型。則應如何安排生產？試建立其數學模型。機床種類機床種類現有數量現有數量/ /臺臺每臺機床生產率每臺機床生產率/ /（件（件/ /日）日）A零件B零件甲23040乙32535丙42730表1-22021年11月3日星期三14山西大學經濟與管理學院 范建平2、產品配套模型p求解本題，不能單純追求兩種零件的總產量達到最大，求解本題，不能單純追求兩種零件的總產量達到最大，而應要求每個工作日按而應要求每個工作日按3:5的比例生產出來的的比例生產出來的A，B兩零兩零件的套數達到最大。件的套數達到最大。1. 決策變量： 2.

12、約束條件： （1）工時約束1,2,3;1,2A,B3:5ijijzxij設表示機床 每個工；為兩種零件按作日加工零件 的時間（單位：工的比例配套的數量作日）（套 日）111221223132111xxxxxx2021年11月3日星期三15山西大學經濟與管理學院 范建平2、產品配套模型2021年11月3日星期三山西大學經濟與管理學院 范建平16p（2）配套約束）配套約束(表表1.3)機床種類機床種類每種機床生產率每種機床生產率/(/(件件/ /日日) )A A零件零件B B零件零件甲6080乙75105丙108120表表1-3 每臺機床的生產率每臺機床的生產率112131122232min607

13、51083, 801051205zxxxxxx2、產品配套模型2021年11月3日星期三山西大學經濟與管理學院 范建平17p非線性約束等價轉換非線性約束等價轉換1121311221321121311221326075108/380105120/520253601621240zxxxzxxxzxxxzxxx即2、產品配套模型2021年11月3日星期三山西大學經濟與管理學院 范建平18pLP模型如下：模型如下：112131122132111221223132max202536016212401. .110,1,2,3;1,2ijzzxxxzxxxxxstxxxxxij3、下料模型p 例例1.3 某

14、項管網工程，要用某一口徑的管材，其原材長某項管網工程，要用某一口徑的管材，其原材長5m，但用材的長度、數量不盡相同，見表，但用材的長度、數量不盡相同，見表1-4。應如何。應如何下料才能耗材最?。吭嚱⑵鋽祵W模型。下料才能耗材最?。吭嚱⑵鋽祵W模型。用材用材長度長度/m/m需求量需求量/ /根根A2.6150B1.8200C1.1360表1-42021年11月3日星期三19山西大學經濟與管理學院 范建平3、下料模型解：首先需要找出全部省料截法(見表1-5) 。（所謂省料截法，這里指一個原材截后的余料長度小于最短的用材C的長度的各種截法） 截法截法j j用材用材一根原材所截各種用材的數量（根）一根

15、原材所截各種用材的數量（根）需求量需求量/ /根根12345A（2.6）11000150B（1.8）10210200C（1.1）02124300余料/m0.60.20.31.00.6表1-52021年11月3日星期三20山西大學經濟與管理學院 范建平3、下料模型p設設xj表示第表示第j種截法下料的根數（種截法下料的根數（j=1,2,3,4,5），），z為下料為下料總根數總根數p則則LP模型如下：模型如下： 截法截法j j用材用材一根原材所截各種用材的數量（根）一根原材所截各種用材的數量（根）需求量需求量/ /根根12345A（2.6）11000150B（1.8）10210200C（1.1）02

16、124300余料/m0.60.20.31.00.61234512134234512345min1502200. .224360,0zxxxxxxxxxxstxxxxx x x x x2021年11月3日星期三21山西大學經濟與管理學院 范建平4、配料模型p例例1.4 某食品廠擬用某食品廠擬用A，B兩種緊俏原料和一種普通原料兩種緊俏原料和一種普通原料C，加工制作甲、乙、丙三種食品。食品的規(guī)格、加工費、加工制作甲、乙、丙三種食品。食品的規(guī)格、加工費、銷價，以及原料的購價、供量見表銷價，以及原料的購價、供量見表1-6。應如何為三種食。應如何為三種食品配料？試建立其數學模型。品配料？試建立其數學模型。

17、表1-6 原料原料食品食品食物規(guī)格（配用的原料所占比率）食物規(guī)格（配用的原料所占比率）/%/%食品食品ABC加工費銷價甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料購價562元/kg供量10060不限Kg/元2021年11月3日星期三22山西大學經濟與管理學院 范建平4、配料模型解題要點：解題要點：p決策變量：決策變量：p約束條件：規(guī)格約束；原料供應量約束約束條件：規(guī)格約束；原料供應量約束p目標函數：總利潤目標函數：總利潤=總收益總收益-原料總費用原料總費用2021年11月3日星期三23山西大學經濟與管理學院 范建平4、配料模型2021年11月

18、3日星期三山西大學經濟與管理學院 范建平24p決策變量：設決策變量：設xij表示每天給食品表示每天給食品i所配用的原料所配用的原料j的數量的數量（kg/天）（天）（i=1,2,3; j=1,2,3） 原原料料j食品食品iA AB BC C甲x11x12x13乙x21x22x23丙x31x32x334、配料模型2021年11月3日星期三山西大學經濟與管理學院 范建平25p約束條件約束條件規(guī)格約束規(guī)格約束1112111213111213212221222321222331333132333132330.5;0.3;0.6;0.2;0.4;0.6;xxxxxxxxxxxxxxxxxxxxxxxx4、

19、配料模型p約束條件約束條件原理供應約束原理供應約束p總收益總收益p原料總費用原料總費用p目標函數目標函數：總利潤總利潤=總收益總收益-原料總費用原料總費用112131122232A10060Bxxxxxx原料原料 3332312322211312113628210 xxxxxxxxx332313322212312111265xxxxxxxxx2021年11月3日星期三26山西大學經濟與管理學院 范建平1112132122233132331121311222321311121321233123323333863-326425-6-2=3xxxxxxxxxxxxxxxxxxxxxxxxxx4、配料

20、模型p綜上可得綜上可得LP模型如下：模型如下：)3 , 2 , 1; 3 , 2 , 1( , 0601000233022304033203730. .324623max3222123121113332313332312322212322211312111312113332312321131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxzij2021年11月3日星期三27山西大學經濟與管理學院 范建平5、人力資源分配的問題28 班次時間所需人數16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522：

21、00 2：002062：00 6：0030某某晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下：晝夜服務的公交線路每天各時間段內所需司機和乘務人員數如下： 設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八設司機和乘務人員分別在各時間段一開始時上班，并連續(xù)工作八小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，小時，問該公交線路怎樣安排司機和乘務人員，既能滿足工作需要，又配備最少司機和乘務人員又配備最少司機和乘務人員? ?2021年11月3日星期三山西大學經濟與管理學院 范建平5、人力資源分配的問題29p解：設解：設 xi 表示第表示第i班次時開始上班的司機和乘務人員數

22、班次時開始上班的司機和乘務人員數,這這樣我們建立如下的數學模型。樣我們建立如下的數學模型。123456161223344556 123456 60 70 60. . 50 20 30, 0min xxxxxxxxxxxxstxxxxxxx x x x x x2021年11月3日星期三山西大學經濟與管理學院 范建平5、人力資源分配的問題時間所需售貨員人數星期日28星期一15星期二24星期三25星期四19星期五31星期六28 例例2 2一家中型的百貨商場，它對售貨員的需求經過統(tǒng)計分析如下表所一家中型的百貨商場，它對售貨員的需求經過統(tǒng)計分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作示。為

23、了保證售貨人員充分休息，售貨人員每周工作5 5天，休息兩天，并要天，休息兩天，并要求休息的兩天是連續(xù)的。問應該如何安排售貨人員的作息，既滿足工作需求休息的兩天是連續(xù)的。問應該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數最少？要，又使配備的售貨人員的人數最少？2021年11月3日星期三30山西大學經濟與管理學院 范建平5、人力資源分配的問題31p 解：設解：設 xi ( i = 1,2,7)表示星期一至日開始休息的人表示星期一至日開始休息的人數數,這樣我們建立如下的數學模型。這樣我們建立如下的數學模型。1234567123452345634567456715671267123

24、71234 28 15 24. . 25 19 31 28min xxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxxxxxxxx2021年11月3日星期三山西大學經濟與管理學院 范建平1.2 線性規(guī)劃的一般模型2021年11月3日星期三32山西大學經濟與管理學院 范建平1.2.1 線性規(guī)劃的通式2021年11月3日星期三山西大學經濟與管理學院 范建平33p1.基本概念基本概念p線性規(guī)劃的通用模型（簡稱線性規(guī)劃的通用模型（簡稱通式通式）1 12211 11221121 1222221 1221 1=1 1. .=01,2,1 1nnnnnnmmmnnmjopt zc x

25、c xc xaa xa xa xba xa xa xbbsta xaxaxbxjnc或或或或，或自由，aij,bi,cj稱謂稱謂LP模型的模型的參數參數，其中，其中aij稱為稱為消耗系數消耗系數，bi稱為稱為右端常數右端常數，cj稱為稱為價值系數價值系數。1.2.1 線性規(guī)劃的通式2021年11月3日星期三山西大學經濟與管理學院 范建平34p2. 解的概念解的概念（1）可行解）可行解 方程組方程組(1-1b)，(1-1c)的解的解X=(x1,x2,xn)T稱為稱為LP問題的問題的可可行解行解，其集合稱為，其集合稱為可行集可行集，或，或可行域可行域，記為，記為: R=X|(1-1b),(1-1c

26、).（2）最優(yōu)解）最優(yōu)解 滿足滿足(1-1a)，即能使目標函數達到最優(yōu)化的可行解，稱為，即能使目標函數達到最優(yōu)化的可行解，稱為LP問題的問題的最優(yōu)解最優(yōu)解，簡稱為解，記為：，簡稱為解，記為：X*=(x1*,x2 *,xn *)T 它對應的目標函數值稱為它對應的目標函數值稱為最優(yōu)值最優(yōu)值，記為：，記為： z*=c1x1*+c2x2 *+cnxn *1 12211 11221121 1222221 1221 1=. .=01,2,1 11 1nnnnnnmmmnnmjopt zc xc xc xaa xa xa xba xa xa xbsta xaxaxbxbcjn或或或或，或自由，1.2.2 線

27、性規(guī)劃的標準型2021年11月3日星期三山西大學經濟與管理學院 范建平35p單純形法要求單純形法要求LP模型必須為下述特定形式（模型必須為下述特定形式（LP標準型標準型）11 12211 11221121 1222221 122:max1 21 2. .01,2,1 2nnnnnnmmmnnmjMzc xc xc xaa xa xa xba xa xa xbbsta xaxaxbxjnc01,2,ibim1.2.2 線性規(guī)劃的標準型2021年11月3日星期三山西大學經濟與管理學院 范建平36pLP標準型標準型也可也可簡記簡記為：為：211:max1,2,m. .01,2,njjjnijjijj

28、Mzc xa xbistxjn1.2.2 線性規(guī)劃的標準型2021年11月3日星期三山西大學經濟與管理學院 范建平37pLP標準型標準型矩陣向量的形式矩陣向量的形式：3121112111212222212:max. .0=,TTnnnnnmmmnMzC XAXbstXCc ccaaaxbaaaxbAXbxbaaa其中上述標準型的三種形式（M1），（M2），（M3）統(tǒng)稱為標準型（問題）M1.2.3 線性規(guī)劃的標準化2021年11月3日星期三山西大學經濟與管理學院 范建平38p實際問題的實際問題的LP模型通常都不是標準型，但可通過等價變模型通常都不是標準型，但可通過等價變換最終都能化成標準型。這類

29、轉化工作稱為換最終都能化成標準型。這類轉化工作稱為標準化標準化。p非標準型包括以下幾種情況：非標準型包括以下幾種情況：n1.min型目標函數型目標函數n2.非標準型約束方程非標準型約束方程n3.取值非正的變量取值非正的變量（1）bi0,兩端同乘以-1.（2）某個方程為形式，左端加非負的松弛變量化為等式.（3）某個方程為形式，左端減非負的剩余變量化為等式.松弛變量和剩余變量可統(tǒng)稱為松弛變量，其價值系數為0（1）若xk0，只需通過變量代換 xk=-xk 則 xk 0，用以取代 xk，即可符合標準.（2）若xk為自由變量（可正，可負，可0），只需通過變量 代換. xk=xk -xk ,且 xk ,

30、xk 0 用以xk -xk 取代 xk，即可符合標準.（3）當有多個自由變量xj時，為避免無謂增加變量個數，可令xj=xj -x , x 對其所在式中的一切j都是同一個變量。例1-5 將（例1-1）問題化為標準型2021年11月3日星期三山西大學經濟與管理學院 范建平39 12121212max320161282. .23183,04zxxxxstxxxx 產品產品車間車間單耗單耗/ /（工時（工時/ /件）件）最大生產能力最大生產能力/(/(工時工時/ /周周) )甲乙A106B028C2318利潤/（1100元/件）32例1-5 將（例1-1）問題化為標準型2021年11月3日星期三山西大

31、學經濟與管理學院 范建平40p將將(1)、(2)、(3)式加上松弛變量，化為等式即可式加上松弛變量，化為等式即可12345132412512345max32+0001628. .2318,0zxxxxxxxxxstxxxx x x x x例1-6 將下述LP問題化為標準型2021年11月3日星期三山西大學經濟與管理學院 范建平41 123412341234123423min23023313222. .32130,04zxxxxxxxxxxxxstxxxxxx 123412345123461234723567max2323+ 3322. .3210,0zxxxxxxxxxxxxxxstxxxxx

32、xx x x x 例1-6 將下述LP問題化為標準型2021年11月3日星期三山西大學經濟與管理學院 范建平4211123411234511234611234711234567max23233+ 33222. .2321,0zxxxxxxxxxxxxxxxxxstxxxxxxxxxx x x x x1122,01,4 ;=- ;jjjxxxxxjxx令且 ，再令 分別代入上式，即可得原問題的標準型：1.2.4 線性規(guī)劃的典式2021年11月3日星期三山西大學經濟與管理學院 范建平43p標準化是單純形法的預備步驟，還需化成下述標準化是單純形法的預備步驟，還需化成下述典式，典式，才才能用單純形方法

33、能用單純形方法1 12211,111122,1122,11max. .1 301,2,nnmmnnmmnnmm mmmnnmjzc xc xc xxaxa xbxaxa xbstxaxaxbxjn2021年11月3日星期三山西大學經濟與管理學院 范建平44p方程組（方程組（1-3）的系數矩陣為）的系數矩陣為1,112,12m,1100010001mnmnmmnaaaaaa（1）標準型（）標準型（M）為典）為典式的充要條件是：在其函式的充要條件是：在其函數約束方程組的系數矩陣數約束方程組的系數矩陣中，存在一個滿秩排列陣，中，存在一個滿秩排列陣，即每行每列僅有一個元素即每行每列僅有一個元素為為1，

34、其他元素全為，其他元素全為0的的m階方陣。階方陣。（2）LP問題的標準型多問題的標準型多為非典式，將標準型轉化為非典式，將標準型轉化為典式需要加人工變量為典式需要加人工變量1.3 線性規(guī)劃的圖解法2021年11月3日星期三山西大學經濟與管理學院 范建平45p1.3.1 基本步驟基本步驟n1.建立平面直角坐標系建立平面直角坐標系n2.畫出可行域畫出可行域n3.畫出目標函數等值線及其法線畫出目標函數等值線及其法線n4.平移目標函數等值線，確定問題的解平移目標函數等值線，確定問題的解【例1-7】 用圖解法求范例的的LP問題2021年11月3日星期三山西大學經濟與管理學院 范建平46 12121212

35、max3201628. .2318,0zxxxxstxxxxD(0,4)A(6,0)O(0,0)x1=62x2=8x1x2G(0,6)E(9,0)F(6,4)C(3,4)B(6,2)【例1-7】 用圖解法求范例的的LP問題2021年11月3日星期三山西大學經濟與管理學院 范建平47 12121212max3201628. .2318,0zxxxxstxxxxD(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=22 沿著法線方向平行移動目標函數等值線，當與可沿著法線方向平行移動目標函數等值線，當與可行域相切時，恰在邊界點行域相切時，恰在邊界點B處，處，B點就是最優(yōu)點，

36、其坐點就是最優(yōu)點，其坐標（標（6,2）就是最優(yōu)解，代入目標函數，得最優(yōu)值）就是最優(yōu)解，代入目標函數，得最優(yōu)值z=22.1.3.2 求解結果2021年11月3日星期三山西大學經濟與管理學院 范建平48p1. 唯一解唯一解n如范例，只有一個最優(yōu)解如范例，只有一個最優(yōu)解Bp2.多重解多重解n【例例1-8】若將范例的目標函數改為若將范例的目標函數改為: z=3x1+4.5x2D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=271.3.2 求解結果2021年11月3日星期三山西大學經濟與管理學院 范建平49p3. 解無界解無界n【例例1-9】求解下列求解下列LP問題問題1

37、2121212max322+2. . -+ 23,0zxxxxstxxxxO(0,0)x1x2z法向R2021年11月3日星期三山西大學經濟與管理學院 范建平50p4. 無可行解無可行解n【例例1-10】考慮范例考慮范例, 若該廠從產量管理上規(guī)定，甲、乙兩若該廠從產量管理上規(guī)定，甲、乙兩種產品每周總量不低于種產品每周總量不低于10件，試就此做出分析。件，試就此做出分析。1212121212max321628. . 23181110,0zxxxxstxxxxxxG(0,6)O(0,0)x1x2 x1+x210 2x1+3x218R=E(9,0)1.4 標準線性規(guī)劃的解2021年11月3日星期三山

38、西大學經濟與管理學院 范建平51p1.基本解基本解12132412512345max321 416281 4. .2318,01 4zxxaxxxxbstxxxx x x x xc123451234510 10 00 2 01 02 3 00 1xxxxxAa aaaa0345Baaap其系數矩陣為：其系數矩陣為：12345,TXx x x x x令非基變量 x1=x2=0由方程組（1-4b）得： x3=6，x4=8, x5=18方程組（1-4b）的一個特解為：00,0,6,8,18TX 1. 基本解2021年11月3日星期三山西大學經濟與管理學院 范建平52考慮標準形線性規(guī)劃：考慮標準形線性

39、規(guī)劃：max1 51 5. .01 5TzC XaAXbbstXc 假設假設A=(aij)mn是滿秩陣，且秩數為是滿秩陣，且秩數為r(A)=mn，將其系數，將其系數陣陣A記為：記為： 則有下述定義：則有下述定義：121,mmnAa aaaa1. 基本解2021年11月3日星期三山西大學經濟與管理學院 范建平53p（1）基矩陣）基矩陣n設設B為為A的一個的一個m階子矩陣，若其行列式階子矩陣，若其行列式|B|0，則稱，則稱B為方為方程組（程組（1-5b）或線性規(guī)劃（）或線性規(guī)劃（1-5）的一個）的一個基矩陣基矩陣，簡稱一個，簡稱一個基基。1. 基本解2021年11月3日星期三山西大學經濟與管理學院

40、 范建平54p（2）基變量）基變量12,0mBa aaB不失一般性，設基矩陣為：121212,mmmnmmnBmAnma aaaaaNaaaAB NA基向量非基則 中的 個向量為,矩陣 中其余個向量為。將所有非基向量構成的矩陣記為:則系數矩陣 可改寫為：向量1. 基本解2021年11月3日星期三山西大學經濟與管理學院 范建平5512,Bmx xxm稱基向量對應的 個變?yōu)?以 為基量為的 基變量12,Bmmnxmxx稱非基向量對應的n-為 以 為基的個變量為非基變量XB將所有基變量構成的向量記為，稱為基變矢XN所有非基變量構成的向量記為，稱為非基變矢,(1 5b )BABABNXXXAXbB N

41、bXBXNXb則變矢X可寫為：X=而方程組可改寫為即1. 基本解2021年11月3日星期三山西大學經濟與管理學院 范建平56p（3）基本解）基本解- bBBXbB令非基變量全部取值為0,即X N=0,這是方程組（1 5 ）-1-110,B0- b0- b-BNBBBXB bXB b0由前假設 的行列式則可逆，用左乘上式兩端，解得與一起構成方程組（1 5 ）的一個特解X =稱為方程組（1 5 ）或線性規(guī)劃（1 5）的一個以B為基的基本解，簡稱基本解2. 最優(yōu)基本解2021年11月3日星期三山西大學經濟與管理學院 范建平57p（1）基本可行解）基本可行解n既是既是基本解基本解，又是，又是可行解可行

42、解，就是基本可行解。，就是基本可行解。n滿足非負約束的基本解為滿足非負約束的基本解為基本可行解基本可行解。max1 51 5. .01 5TzC XaAXbbstXc034500,0,6,8,18TBaaaX00取，以B 為基的基本解為：X =所有分量取值為非負，是基本可行解。123411300,6,6,-4,0TBaaaBX14取為基，解為： X =x =-4，不是基本可行解。2124222306,2,0,4,0TBa aaBX取為基，解為： X =是基本可行解。2. 最優(yōu)基本解2021年11月3日星期三山西大學經濟與管理學院 范建平58p（2）最優(yōu)基本解）最優(yōu)基本解n滿足式（滿足式（1-5a），能使目標函數），能使目標函數z=CTX取得最大值的基本可取得最大值的基本可行解行解 ，稱為標準型，稱為標準型LP問題（問題（1-5）的最優(yōu)基本解，記為）的最優(yōu)基本解，記為X*,它所對應的目標函數值稱為它所對應的目標函數值稱為最優(yōu)值最優(yōu)值，記為，記為z*=CTX*max1 51 5. .01 5TzC XaAXbbstXc22- a6,2,0,4,0TX將代入目標函數（1 5 ）中，算的,由前面的圖解法知這z=2是范例的最優(yōu)值，故X =為范例的2最優(yōu)基本解。2