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

1、山西大學(xué)經(jīng)濟(jì)與管理學(xué)院山西大學(xué)經(jīng)濟(jì)與管理學(xué)院主講：范建平主講：范建平 博士博士運(yùn)籌學(xué)山西大學(xué)經(jīng)濟(jì)與管理學(xué)院山西大學(xué)經(jīng)濟(jì)與管理學(xué)院第一章 線性規(guī)劃基本模型1.1 線性規(guī)劃的實(shí)用模型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平3在管理中一些典型的線性規(guī)劃應(yīng)用4p合理利用線材問(wèn)題合理利用線材問(wèn)題：如何在保證生產(chǎn)的條件下，下料最少：如何在保證生產(chǎn)的條件下，下料最少p配料問(wèn)題配料問(wèn)題：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)：在原料供應(yīng)量的限制下如何獲取最大利潤(rùn)p投資問(wèn)題投資問(wèn)題：從投資項(xiàng)目中選取方案，使投資回報(bào)最大：從投資項(xiàng)目中選取方案，使投資回報(bào)最大p產(chǎn)品生產(chǎn)計(jì)劃產(chǎn)品生產(chǎn)計(jì)劃：合理利用人力、

2、物力、財(cái)力等，使獲利最大：合理利用人力、物力、財(cái)力等，使獲利最大p勞動(dòng)力安排勞動(dòng)力安排：用最少的勞動(dòng)力來(lái)滿足工作的需要：用最少的勞動(dòng)力來(lái)滿足工作的需要p運(yùn)輸問(wèn)題運(yùn)輸問(wèn)題：如何制定調(diào)運(yùn)方案，使總運(yùn)費(fèi)最?。喝绾沃贫ㄕ{(diào)運(yùn)方案，使總運(yùn)費(fèi)最小2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、資源分配模型p 例例1.1 某裝配廠擬生產(chǎn)甲、乙兩種新產(chǎn)品，每件利潤(rùn)分某裝配廠擬生產(chǎn)甲、乙兩種新產(chǎn)品，每件利潤(rùn)分別為別為300元和元和200元。甲、乙產(chǎn)品的部件分別在元。甲、乙產(chǎn)品的部件分別在A、B兩個(gè)兩個(gè)車間生產(chǎn)，每件甲、乙產(chǎn)品的部件分別消耗車間生產(chǎn)，每件甲、乙產(chǎn)品的部件分別消耗A、B車間車間1、2工時(shí)。

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

4、/周周) )甲乙A106B028C2318利潤(rùn)/（1100元/件）321、資源分配模型2022年6月10日星期五6山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、資源分配模型設(shè)設(shè) x1, x2 分別為甲、乙產(chǎn)品的周產(chǎn)量（分別為甲、乙產(chǎn)品的周產(chǎn)量（決策變量決策變量） z為這兩種產(chǎn)品每周的總利潤(rùn)，則由于，z取值受限于x1, x2 ，而x1, x2 受限于A，B，C三個(gè)車間的生產(chǎn)能力，則 式（0）稱為目標(biāo)函數(shù)目標(biāo)函數(shù)，z為目標(biāo)值目標(biāo)值 產(chǎn)品產(chǎn)品車間車間單耗單耗/ /（工時(shí)（工時(shí)/ /件）件）最大生產(chǎn)能力最大生產(chǎn)能力/(/(工時(shí)工時(shí)/ /周周) )甲乙A106B028C2318利潤(rùn)/（1100元/件）32 1232

5、0zxx1212121060282318xxxxxx約束條件2022年6月10日星期五7山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、資源分配模型p上述函數(shù)約束和非負(fù)性約束，統(tǒng)稱為約束條件或約束方程，上述函數(shù)約束和非負(fù)性約束，統(tǒng)稱為約束條件或約束方程，簡(jiǎn)稱簡(jiǎn)稱約束約束。p綜上所述，例題綜上所述，例題1.1的數(shù)學(xué)模型簡(jiǎn)記如下：的數(shù)學(xué)模型簡(jiǎn)記如下：又因產(chǎn)量x1, x2 取值不能為負(fù)，則非負(fù)性約束非負(fù)性約束120,0 xx 12121212max3201628. .2318,0zxxxxstxxxx2022年6月10日星期五8山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、資源分配模型小結(jié)p由目標(biāo)函數(shù)和約束方程構(gòu)成的一組數(shù)學(xué)

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

7、式稱約束條件把各種限制條件表示為一組等式或不等式稱約束條件n約束條件是決策方案可行的保障約束條件是決策方案可行的保障n約束條件是決策變量的約束條件是決策變量的線性函數(shù)線性函數(shù)p目標(biāo)函數(shù)目標(biāo)函數(shù)n衡量決策優(yōu)劣的準(zhǔn)則，如時(shí)間最省、利潤(rùn)最大、成本最低衡量決策優(yōu)劣的準(zhǔn)則，如時(shí)間最省、利潤(rùn)最大、成本最低n目標(biāo)函數(shù)是決策變量的目標(biāo)函數(shù)是決策變量的線性函數(shù)線性函數(shù)n有的目標(biāo)要實(shí)現(xiàn)極大，有的則要求極小有的目標(biāo)要實(shí)現(xiàn)極大，有的則要求極小2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、資源分配模型小結(jié)p小結(jié)小結(jié)：對(duì)于例題：對(duì)于例題1.1的資源分配問(wèn)題（的資源分配問(wèn)題（經(jīng)營(yíng)規(guī)劃問(wèn)題經(jīng)營(yíng)規(guī)劃問(wèn)題），），一

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

9、濟(jì)與管理學(xué)院 范建平1、資源分配模型小結(jié)p建立線性規(guī)劃模型的一般步驟：建立線性規(guī)劃模型的一般步驟：p1.正確設(shè)立決策變量正確設(shè)立決策變量n設(shè)設(shè)xj（j=1,2,n）為項(xiàng)目）為項(xiàng)目j的經(jīng)營(yíng)數(shù)量。的經(jīng)營(yíng)數(shù)量。p2.恰當(dāng)建立目標(biāo)函數(shù)恰當(dāng)建立目標(biāo)函數(shù)nn項(xiàng)經(jīng)營(yíng)活動(dòng)的總利潤(rùn)（或總產(chǎn)值，總收入）為項(xiàng)經(jīng)營(yíng)活動(dòng)的總利潤(rùn)（或總產(chǎn)值，總收入）為p3. 適度構(gòu)建約束方程適度構(gòu)建約束方程n（1）合同約束）合同約束n（2）需求約束）需求約束n（3）資源約束）資源約束1njjjzc x1,2,jjxejn1,2,jjxdjn11,2,nijjija xbim2022年6月10日星期五12山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1、

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

11、最大產(chǎn)量（即生產(chǎn)率：件/日）見(jiàn)日）見(jiàn)表表1-2。則應(yīng)如何安排生產(chǎn)？試建立其數(shù)學(xué)模型。則應(yīng)如何安排生產(chǎn)？試建立其數(shù)學(xué)模型。機(jī)床種類機(jī)床種類現(xiàn)有數(shù)量現(xiàn)有數(shù)量/ /臺(tái)臺(tái)每臺(tái)機(jī)床生產(chǎn)率每臺(tái)機(jī)床生產(chǎn)率/ /（件（件/ /日）日）A零件B零件甲23040乙32535丙42730表1-22022年6月10日星期五14山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平2、產(chǎn)品配套模型p求解本題，不能單純追求兩種零件的總產(chǎn)量達(dá)到最大，求解本題，不能單純追求兩種零件的總產(chǎn)量達(dá)到最大，而應(yīng)要求每個(gè)工作日按而應(yīng)要求每個(gè)工作日按3:5的比例生產(chǎn)出來(lái)的的比例生產(chǎn)出來(lái)的A，B兩零兩零件的套數(shù)達(dá)到最大。件的套數(shù)達(dá)到最大。1. 決策變量： 2.

12、約束條件： （1）工時(shí)約束1,2,3;1,2A,B3:5ijijzxij設(shè)表示機(jī)床 每個(gè)工；為兩種零件按作日加工零件 的時(shí)間（單位：工的比例配套的數(shù)量作日）（套 日）111221223132111xxxxxx2022年6月10日星期五15山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平2、產(chǎn)品配套模型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平16p（2）配套約束）配套約束(表表1.3)機(jī)床種類機(jī)床種類每種機(jī)床生產(chǎn)率每種機(jī)床生產(chǎn)率/(/(件件/ /日日) )A A零件零件B B零件零件甲6080乙75105丙108120表表1-3 每臺(tái)機(jī)床的生產(chǎn)率每臺(tái)機(jī)床的生產(chǎn)率112131122232min607

13、51083, 801051205zxxxxxx2、產(chǎn)品配套模型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平17p非線性約束等價(jià)轉(zhuǎn)換非線性約束等價(jià)轉(zhuǎn)換1121311221321121311221326075108/380105120/520253601621240zxxxzxxxzxxxzxxx即2、產(chǎn)品配套模型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平18pLP模型如下：模型如下：112131122132111221223132max202536016212401. .110,1,2,3;1,2ijzzxxxzxxxxxstxxxxxij3、下料模型p 例例1.3 某

14、項(xiàng)管網(wǎng)工程，要用某一口徑的管材，其原材長(zhǎng)某項(xiàng)管網(wǎng)工程，要用某一口徑的管材，其原材長(zhǎng)5m，但用材的長(zhǎng)度、數(shù)量不盡相同，見(jiàn)表，但用材的長(zhǎng)度、數(shù)量不盡相同，見(jiàn)表1-4。應(yīng)如何。應(yīng)如何下料才能耗材最??？試建立其數(shù)學(xué)模下料才能耗材最省？試建立其數(shù)學(xué)模型。型。用材用材長(zhǎng)度長(zhǎng)度/m/m需求量需求量/ /根根A2.6150B1.8200C1.1360表1-42022年6月10日星期五19山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平3、下料模型解：首先需要找出全部省料截法(見(jiàn)表1-5) 。（所謂省料截法，這里指一個(gè)原材截后的余料長(zhǎng)度小于最短的用材C的長(zhǎng)度的各種截法） 截法截法j j用材用材一根原材所截各種用材的數(shù)量（根）一根

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

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

17、表1-6 原料原料食品食品食物規(guī)格（配用的原料所占比率）食物規(guī)格（配用的原料所占比率）/%/%食品食品ABC加工費(fèi)銷價(jià)甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料購(gòu)價(jià)562元/kg供量10060不限Kg/元2022年6月10日星期五22山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平4、配料模型解題要點(diǎn)：解題要點(diǎn)：p決策變量：決策變量：p約束條件：規(guī)格約束；原料供應(yīng)量約束約束條件：規(guī)格約束；原料供應(yīng)量約束p目標(biāo)函數(shù)：總利潤(rùn)目標(biāo)函數(shù)：總利潤(rùn)=總收益總收益-原料總費(fèi)用原料總費(fèi)用2022年6月10日星期五23山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平4、配料模型2022年6月1

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

19、配料模型p約束條件約束條件原理供應(yīng)約束原理供應(yīng)約束p總總收益收益p原原料總費(fèi)料總費(fèi)用用p目標(biāo)函數(shù)目標(biāo)函數(shù)：總利潤(rùn)總利潤(rùn)=總收益總收益-原料總費(fèi)原料總費(fèi)用用112131122232A10060Bxxxxxx原料原料 3332312322211312113628210 xxxxxxxxx332313322212312111265xxxxxxxxx2022年6月10日星期五26山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1112132122233132331121311222321311121321233123323333863-326425-6-2=3xxxxxxxxxxxxxxxxxxxxxxxxxx4、配料

20、模型p綜上可得綜上可得LP模型如下：模型如下：)3 , 2 , 1; 3 , 2 , 1( , 0601000233022304033203730. .324623max3222123121113332313332312322212322211312111312113332312321131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxzij2022年6月10日星期五27山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平5、人力資源分配的問(wèn)題28 班次時(shí)間所需人數(shù)16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522：

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

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

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

24、71234 28 15 24. . 25 19 31 28min xxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxxxxxxxx2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1.2 線性規(guī)劃的一般模型2022年6月10日星期五32山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平1.2.1 線性規(guī)劃的通式2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平33p1.基本概念基本概念p線性規(guī)劃的通用模型（簡(jiǎn)稱線性規(guī)劃的通用模型（簡(jiǎn)稱通式通式）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模型的模型的參數(shù)參數(shù)，其中，其中aij稱為稱為消耗系數(shù)消耗系數(shù)，bi稱為稱為右端常數(shù)右端常數(shù)，cj稱為稱為價(jià)值系數(shù)價(jià)值系數(shù)。1.2.1 線性規(guī)劃的通式2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平34p2. 解的概念解的概念（1）可行解）可行解 方程組方程組(1-1b)，(1-1c)的解的解X=(x1,x2,xn)T稱為稱為L(zhǎng)P問(wèn)題的問(wèn)題的可可行解行解，其集合稱為，其集合稱為可行集可行集，或，或可行域可行域，記為，記為: R=X|(1-1b),(1-1c

26、).（2）最優(yōu)解）最優(yōu)解 滿足滿足(1-1a)，即能使目標(biāo)函數(shù)達(dá)到最優(yōu)化的可行解，稱為，即能使目標(biāo)函數(shù)達(dá)到最優(yōu)化的可行解，稱為L(zhǎng)P問(wèn)題的問(wèn)題的最優(yōu)解最優(yōu)解，簡(jiǎn)稱為解，記為：，簡(jiǎn)稱為解，記為：X*=(x1*,x2 *,xn *)T 它對(duì)應(yīng)的目標(biāo)函數(shù)值稱為它對(duì)應(yīng)的目標(biāo)函數(shù)值稱為最優(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ī)劃的標(biāo)準(zhǔn)型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平35p單純形法要求單純形法要求LP模型必須為下述特定形式（模型必須為下述特定形式（LP標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型）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ī)劃的標(biāo)準(zhǔn)型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平36pLP標(biāo)準(zhǔn)型標(biāo)準(zhǔn)型也可也可簡(jiǎn)記簡(jiǎn)記為：為：211:max1,2,m. .01,2,njjjnijjijj

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

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

30、xk 0 用以xk -xk 取代 xk，即可符合標(biāo)準(zhǔn).（3）當(dāng)有多個(gè)自由變量xj時(shí)，為避免無(wú)謂增加變量個(gè)數(shù)，可令xj=xj -x , x 對(duì)其所在式中的一切j都是同一個(gè)變量。例1-5 將（例1-1）問(wèn)題化為標(biāo)準(zhǔn)型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平39 12121212max320161282. .23183,04zxxxxstxxxx 產(chǎn)品產(chǎn)品車間車間單耗單耗/ /（工時(shí)（工時(shí)/ /件）件）最大生產(chǎn)能力最大生產(chǎn)能力/(/(工時(shí)工時(shí)/ /周周) )甲乙A106B028C2318利潤(rùn)/（1100元/件）32例1-5 將（例1-1）問(wèn)題化為標(biāo)準(zhǔn)型2022年6月10日星期五山西大

31、學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平40p將將(1)、(2)、(3)式加上松弛變量，化為等式即可式加上松弛變量，化為等式即可12345132412512345max32+0001628. .2318,0zxxxxxxxxxstxxxx x x x x例1-6 將下述LP問(wèn)題化為標(biāo)準(zhǔn)型2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平41 123412341234123423min23023313222. .32130,04zxxxxxxxxxxxxstxxxxxx 123412345123461234723567max2323+ 3322. .3210,0zxxxxxxxxxxxxxxstxxxxx

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

33、能用單純形方法1 12211,111122,1122,11max. .1 301,2,nnmmnnmmnnmm mmmnnmjzc xc xc xxaxa xbxaxa xbstxaxaxbxjn2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平44p方程組（方程組（1-3）的系數(shù)矩陣為）的系數(shù)矩陣為1,112,12m,1100010001mnmnmmnaaaaaa（1）標(biāo)準(zhǔn)型（）標(biāo)準(zhǔn)型（M）為典）為典式的充要條件是：在其函式的充要條件是：在其函數(shù)約束方程組的系數(shù)矩陣數(shù)約束方程組的系數(shù)矩陣中，存在一個(gè)滿秩排列陣，中，存在一個(gè)滿秩排列陣，即每行每列僅有一個(gè)元素即每行每列僅有一個(gè)元素為為1，

34、其他元素全為，其他元素全為0的的m階方陣。階方陣。（2）LP問(wèn)題的標(biāo)準(zhǔn)型多問(wèn)題的標(biāo)準(zhǔn)型多為非典式，將標(biāo)準(zhǔn)型轉(zhuǎn)化為非典式，將標(biāo)準(zhǔn)型轉(zhuǎn)化為典式需要加人工變量為典式需要加人工變量1.3 線性規(guī)劃的圖解法2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平45p1.3.1 基本步驟基本步驟n1.建立平面直角坐標(biāo)系建立平面直角坐標(biāo)系n2.畫(huà)出可行域畫(huà)出可行域n3.畫(huà)出目標(biāo)函數(shù)等值線及其法線畫(huà)出目標(biāo)函數(shù)等值線及其法線n4.平移目標(biāo)函數(shù)等值線，確定問(wèn)題的解平移目標(biāo)函數(shù)等值線，確定問(wèn)題的解【例1-7】 用圖解法求范例的的LP問(wèn)題2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平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問(wèn)題2022年6月10日星期五山西大學(xué)經(jīng)濟(jì)與管理學(xué)院 范建平47 12121212max3201628. .2318,0zxxxxstxxxxD(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=22 沿著法線方向平行移動(dòng)目標(biāo)函數(shù)等值線，當(dāng)與可沿著法線方向平行移動(dòng)目標(biāo)函數(shù)等值線，當(dāng)與可行域相切時(shí)，恰在邊界點(diǎn)行域相切時(shí)，恰在邊界點(diǎn)B處，處，B點(diǎn)就是最優(yōu)點(diǎn)，

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

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

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

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

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

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

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