規(guī)劃模型(運(yùn)籌學(xué))課件

1、運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations ResearchOperations Research）是用數(shù)學(xué)方法研究各種系統(tǒng)的最）是用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問題，運(yùn)籌學(xué)強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利優(yōu)化問題，運(yùn)籌學(xué)強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。 運(yùn)籌學(xué)的內(nèi)容有數(shù)學(xué)規(guī)劃，運(yùn)輸問題，圖與網(wǎng)絡(luò)分析，排隊(duì)論，存運(yùn)籌學(xué)的內(nèi)容有數(shù)學(xué)規(guī)劃，運(yùn)輸問題，圖與網(wǎng)絡(luò)分析，排隊(duì)論，存儲(chǔ)論，決策論和對(duì)策論等，其中數(shù)學(xué)規(guī)劃又包括線性規(guī)劃，整數(shù)規(guī)劃，儲(chǔ)論，決策論和對(duì)策論等，其中數(shù)學(xué)規(guī)劃又包括線

2、性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃，目標(biāo)規(guī)劃和動(dòng)態(tài)規(guī)劃等，非線性規(guī)劃，目標(biāo)規(guī)劃和動(dòng)態(tài)規(guī)劃等，雖然運(yùn)籌學(xué)包括的內(nèi)容較多，但是它們有兩個(gè)共同的特點(diǎn)：一是以雖然運(yùn)籌學(xué)包括的內(nèi)容較多，但是它們有兩個(gè)共同的特點(diǎn)：一是以全局最優(yōu)作為問題的基本出發(fā)點(diǎn)；二是通過建立數(shù)學(xué)模型，運(yùn)用優(yōu)化技全局最優(yōu)作為問題的基本出發(fā)點(diǎn)；二是通過建立數(shù)學(xué)模型，運(yùn)用優(yōu)化技術(shù)求得系統(tǒng)最合理的運(yùn)營方案。由于各種系統(tǒng)的運(yùn)營機(jī)制和性能不盡相術(shù)求得系統(tǒng)最合理的運(yùn)營方案。由于各種系統(tǒng)的運(yùn)營機(jī)制和性能不盡相同，它們的數(shù)學(xué)模型也各不相同，從而形成了運(yùn)籌學(xué)的不同分支。同，它們的數(shù)學(xué)模型也各不相同，從而形成了運(yùn)籌學(xué)的不同分支。學(xué)習(xí)內(nèi)容：線性規(guī)劃、整數(shù)規(guī)劃學(xué)習(xí)內(nèi)

3、容：線性規(guī)劃、整數(shù)規(guī)劃要求：建立模型、軟件求解（要求：建立模型、軟件求解（Matlab）運(yùn)籌學(xué)（運(yùn)籌學(xué)（Operations ResearchOperations Research）是用數(shù)學(xué)方法研究各種系統(tǒng)的最）是用數(shù)學(xué)方法研究各種系統(tǒng)的最優(yōu)化問題，運(yùn)籌學(xué)強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利優(yōu)化問題，運(yùn)籌學(xué)強(qiáng)調(diào)發(fā)揮現(xiàn)有系統(tǒng)的效能，應(yīng)用數(shù)學(xué)模型求得合理利用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。用各種資源的最佳方案，為決策者提供科學(xué)決策的依據(jù)。 運(yùn)籌學(xué)的內(nèi)容有數(shù)學(xué)規(guī)劃，運(yùn)輸問題，圖與網(wǎng)絡(luò)分析，排隊(duì)論，存運(yùn)籌學(xué)的內(nèi)容有數(shù)學(xué)規(guī)劃，運(yùn)輸問題，圖與網(wǎng)絡(luò)分析，排隊(duì)論，存儲(chǔ)論，決策論和對(duì)策

4、論等，其中數(shù)學(xué)規(guī)劃又包括線性規(guī)劃，整數(shù)規(guī)劃，儲(chǔ)論，決策論和對(duì)策論等，其中數(shù)學(xué)規(guī)劃又包括線性規(guī)劃，整數(shù)規(guī)劃，非線性規(guī)劃，目標(biāo)規(guī)劃和動(dòng)態(tài)規(guī)劃等，非線性規(guī)劃，目標(biāo)規(guī)劃和動(dòng)態(tài)規(guī)劃等，雖然運(yùn)籌學(xué)包括的內(nèi)容較多，但是它們有兩個(gè)共同的特點(diǎn)：一是以雖然運(yùn)籌學(xué)包括的內(nèi)容較多，但是它們有兩個(gè)共同的特點(diǎn)：一是以全局最優(yōu)作為問題的基本出發(fā)點(diǎn)；二是通過建立數(shù)學(xué)模型，運(yùn)用優(yōu)化技全局最優(yōu)作為問題的基本出發(fā)點(diǎn)；二是通過建立數(shù)學(xué)模型，運(yùn)用優(yōu)化技術(shù)求得系統(tǒng)最合理的運(yùn)營方案。由于各種系統(tǒng)的運(yùn)營機(jī)制和性能不盡相術(shù)求得系統(tǒng)最合理的運(yùn)營方案。由于各種系統(tǒng)的運(yùn)營機(jī)制和性能不盡相同，它們的數(shù)學(xué)模型也各不相同，從而形成了運(yùn)籌學(xué)的不同分支。同，

5、它們的數(shù)學(xué)模型也各不相同，從而形成了運(yùn)籌學(xué)的不同分支。 所以可對(duì)運(yùn)籌學(xué)做如下概括：所以可對(duì)運(yùn)籌學(xué)做如下概括：，運(yùn)籌學(xué)的研究對(duì)象是各種系統(tǒng)，運(yùn)籌學(xué)的研究對(duì)象是各種系統(tǒng)，運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源，運(yùn)籌學(xué)的研究目的是實(shí)現(xiàn)系統(tǒng)的最優(yōu)化，求得合理利用各種資源的最優(yōu)方案，的最優(yōu)方案，運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，通過建立數(shù)，運(yùn)籌學(xué)的研究方法是運(yùn)用數(shù)學(xué)語言來描述實(shí)際系統(tǒng)，通過建立數(shù)學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營的最優(yōu)解。學(xué)模型和優(yōu)化技術(shù)求得系統(tǒng)運(yùn)營的最優(yōu)解。，運(yùn)籌學(xué)的研究動(dòng)機(jī)是，運(yùn)籌學(xué)的研究動(dòng)機(jī)是為決策者提供科學(xué)決策的依據(jù)。為決策者提供科學(xué)決策的依據(jù)。 運(yùn)籌學(xué)在

6、工業(yè)，農(nóng)業(yè)，商業(yè)，物流，經(jīng)濟(jì)計(jì)劃，人力資源，軍事運(yùn)籌學(xué)在工業(yè)，農(nóng)業(yè)，商業(yè)，物流，經(jīng)濟(jì)計(jì)劃，人力資源，軍事等行業(yè)都有著非常廣泛的應(yīng)用。有人曾對(duì)世界上等行業(yè)都有著非常廣泛的應(yīng)用。有人曾對(duì)世界上500500家著名的企業(yè)集家著名的企業(yè)集團(tuán)或跨國公司進(jìn)行過調(diào)查，發(fā)現(xiàn)其中團(tuán)或跨國公司進(jìn)行過調(diào)查，發(fā)現(xiàn)其中95%95%曾使用過線性規(guī)劃，曾使用過線性規(guī)劃，75%75%使用使用過運(yùn)輸模型，過運(yùn)輸模型，90%90%使用過網(wǎng)絡(luò)計(jì)劃技術(shù)，使用過網(wǎng)絡(luò)計(jì)劃技術(shù)，90%90%使用過存儲(chǔ)模型，使用過存儲(chǔ)模型，43%43%使使用過動(dòng)態(tài)規(guī)劃。用過動(dòng)態(tài)規(guī)劃。 由此可見運(yùn)籌學(xué)一門應(yīng)用性很強(qiáng)的學(xué)科。特別是隨著計(jì)算機(jī)技術(shù)由此可見運(yùn)籌學(xué)一門

7、應(yīng)用性很強(qiáng)的學(xué)科。特別是隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，計(jì)算機(jī)成為運(yùn)籌學(xué)最強(qiáng)有力的運(yùn)算工具，運(yùn)籌學(xué)越來越的不斷發(fā)展，計(jì)算機(jī)成為運(yùn)籌學(xué)最強(qiáng)有力的運(yùn)算工具，運(yùn)籌學(xué)越來越顯示出其廣泛的使用價(jià)值。顯示出其廣泛的使用價(jià)值。 運(yùn)籌學(xué)這一名詞最早出現(xiàn)于運(yùn)籌學(xué)這一名詞最早出現(xiàn)于19381938年。當(dāng)時(shí)英，美等國盟軍在與德年。當(dāng)時(shí)英，美等國盟軍在與德國的戰(zhàn)爭(zhēng)中遇到了許多錯(cuò)綜復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題難以解決，比如國的戰(zhàn)爭(zhēng)中遇到了許多錯(cuò)綜復(fù)雜的戰(zhàn)略和戰(zhàn)術(shù)問題難以解決，比如，防空雷達(dá)的布置問題：英美等國為了對(duì)付德國的空襲配備了先進(jìn)，防空雷達(dá)的布置問題：英美等國為了對(duì)付德國的空襲配備了先進(jìn)的雷達(dá)作為防空系統(tǒng)的一部分，但是由于雷達(dá)

8、系統(tǒng)的布置不甚合理，的雷達(dá)作為防空系統(tǒng)的一部分，但是由于雷達(dá)系統(tǒng)的布置不甚合理，通過防空演習(xí)發(fā)現(xiàn)實(shí)際效果并不理想，通過防空演習(xí)發(fā)現(xiàn)實(shí)際效果并不理想，護(hù)航艦隊(duì)的編隊(duì)問題：英美等國需要對(duì)本國的商船隊(duì)配備護(hù)航艦，護(hù)航艦隊(duì)的編隊(duì)問題：英美等國需要對(duì)本國的商船隊(duì)配備護(hù)航艦隊(duì)，以防止德國潛艇的攻擊，這里有一個(gè)如何合理編隊(duì)才能使商船隊(duì)隊(duì)，以防止德國潛艇的攻擊，這里有一個(gè)如何合理編隊(duì)才能使商船隊(duì)一旦遭受德國潛艇攻擊時(shí)損失最少的問題。一旦遭受德國潛艇攻擊時(shí)損失最少的問題。 為了應(yīng)付上述各種復(fù)雜問題，英美等國逐批召集不同專業(yè)背景的為了應(yīng)付上述各種復(fù)雜問題，英美等國逐批召集不同專業(yè)背景的科學(xué)家，在三軍組織了各種研究

9、小組，研究的問題都是軍事性質(zhì)的，科學(xué)家，在三軍組織了各種研究小組，研究的問題都是軍事性質(zhì)的，在英國稱為在英國稱為“Operational ResearchOperational Research”，其他英語國家稱為，其他英語國家稱為“Operations ResearchOperations Research”，意思是軍事行動(dòng)研究。這些研究小組運(yùn)用，意思是軍事行動(dòng)研究。這些研究小組運(yùn)用系統(tǒng)優(yōu)化的思想，應(yīng)用數(shù)學(xué)技術(shù)分析軍事問題，取得了非常理想的效系統(tǒng)優(yōu)化的思想，應(yīng)用數(shù)學(xué)技術(shù)分析軍事問題，取得了非常理想的效果。果。二次大戰(zhàn)以后，在軍事運(yùn)籌小組中工作過的一部分科學(xué)家開始轉(zhuǎn)二次大戰(zhàn)以后，在軍事運(yùn)籌小組

10、中工作過的一部分科學(xué)家開始轉(zhuǎn)入民用部門，他們把對(duì)軍事系統(tǒng)最優(yōu)化的研究成果拓展到各種民用系入民用部門，他們把對(duì)軍事系統(tǒng)最優(yōu)化的研究成果拓展到各種民用系統(tǒng)的研究上。統(tǒng)的研究上。 19471947年美國數(shù)學(xué)家年美國數(shù)學(xué)家G.B.DantzigG.B.Dantzig在研究美國空軍資源配置時(shí)在研究美國空軍資源配置時(shí), ,提提出了求解線性規(guī)劃的有效方法出了求解線性規(guī)劃的有效方法單純形法。二十世紀(jì)五十年代初，應(yīng)單純形法。二十世紀(jì)五十年代初，應(yīng)用計(jì)算機(jī)求解線性規(guī)劃獲得成功。用計(jì)算機(jī)求解線性規(guī)劃獲得成功。 至五十年代末，一些工業(yè)先進(jìn)國家的大型企業(yè)已經(jīng)較普遍地使用至五十年代末，一些工業(yè)先進(jìn)國家的大型企業(yè)已經(jīng)較普遍

11、地使用運(yùn)籌學(xué)方法解決在生產(chǎn)經(jīng)營管理中遇到的實(shí)際問題，并取得了良好的運(yùn)籌學(xué)方法解決在生產(chǎn)經(jīng)營管理中遇到的實(shí)際問題，并取得了良好的效果，至六十年代中期，運(yùn)籌學(xué)開始應(yīng)用于一些服務(wù)性行業(yè)和公用事效果，至六十年代中期，運(yùn)籌學(xué)開始應(yīng)用于一些服務(wù)性行業(yè)和公用事業(yè)。業(yè)。 同時(shí)同時(shí)很多國家成立了運(yùn)籌學(xué)研究學(xué)會(huì)，很多國家成立了運(yùn)籌學(xué)研究學(xué)會(huì)，一些大學(xué)的相關(guān)專業(yè)也陸一些大學(xué)的相關(guān)專業(yè)也陸續(xù)設(shè)置了運(yùn)籌學(xué)的有關(guān)課程。專門發(fā)表運(yùn)籌學(xué)研究論文的刊物開始出續(xù)設(shè)置了運(yùn)籌學(xué)的有關(guān)課程。專門發(fā)表運(yùn)籌學(xué)研究論文的刊物開始出版，運(yùn)籌學(xué)的理論研究日趨成熟，在實(shí)際應(yīng)用上則日趨廣泛。版，運(yùn)籌學(xué)的理論研究日趨成熟，在實(shí)際應(yīng)用上則日趨廣泛。 問

12、題的提出：?jiǎn)栴}的提出： 在生產(chǎn)管理的經(jīng)營活動(dòng)中，通常需要對(duì)在生產(chǎn)管理的經(jīng)營活動(dòng)中，通常需要對(duì)“有限的資源有限的資源”尋求尋求“最佳最佳”的利用或分配方式。的利用或分配方式。l有限資源：勞動(dòng)力、原材料、設(shè)備或資金等有限資源：勞動(dòng)力、原材料、設(shè)備或資金等 l最佳：有一個(gè)標(biāo)準(zhǔn)或目標(biāo)，使利潤(rùn)達(dá)到最大或成本達(dá)到最小。最佳：有一個(gè)標(biāo)準(zhǔn)或目標(biāo)，使利潤(rùn)達(dá)到最大或成本達(dá)到最小。 有限資源的合理配置有兩類問題有限資源的合理配置有兩類問題l如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大；如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大；l在生產(chǎn)或經(jīng)營的任務(wù)確定的條件下，合理的組織生產(chǎn)，安排經(jīng)在生產(chǎn)或經(jīng)營的任務(wù)

13、確定的條件下，合理的組織生產(chǎn)，安排經(jīng)營活動(dòng)，使所消耗的資源數(shù)最少。營活動(dòng)，使所消耗的資源數(shù)最少。 線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃問題及其數(shù)學(xué)模型 與規(guī)劃問題有關(guān)的數(shù)學(xué)模型總有兩部分組成：與規(guī)劃問題有關(guān)的數(shù)學(xué)模型總有兩部分組成：l約束條件：反映了有限資源對(duì)生產(chǎn)經(jīng)營活動(dòng)的種種約束，約束條件：反映了有限資源對(duì)生產(chǎn)經(jīng)營活動(dòng)的種種約束，或者生產(chǎn)經(jīng)營必須完成的任務(wù)；或者生產(chǎn)經(jīng)營必須完成的任務(wù)；l目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營者在有限資源條件下希望達(dá)到目標(biāo)函數(shù)：反映生產(chǎn)經(jīng)營者在有限資源條件下希望達(dá)到的生產(chǎn)或經(jīng)營的目標(biāo)。的生產(chǎn)或經(jīng)營的目標(biāo)。例，例，某制藥廠生產(chǎn)甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生某制藥廠生產(chǎn)

14、甲、乙兩種藥品，生產(chǎn)這兩種藥品要消耗某種維生素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時(shí)間，以及該廠每素。生產(chǎn)每噸藥品所需要的維生素量，所占用的設(shè)備時(shí)間，以及該廠每周可提供的資源總量如下表所示：周可提供的資源總量如下表所示：每噸產(chǎn)品的消耗每噸產(chǎn)品的消耗 每周資源總量每周資源總量 甲甲乙乙維生素（公斤）維生素（公斤） 30302020160160設(shè)備（臺(tái)班）設(shè)備（臺(tái)班） 5 51 11515已知該廠生產(chǎn)每噸甲、乙藥品的利潤(rùn)分別為已知該廠生產(chǎn)每噸甲、乙藥品的利潤(rùn)分別為5 5萬元和萬元和2 2萬元。但根據(jù)萬元。但根據(jù)市場(chǎng)需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量不應(yīng)超過市場(chǎng)需求調(diào)查的結(jié)果，甲藥品每周的產(chǎn)量

15、不應(yīng)超過4 4噸。問該廠應(yīng)如何安噸。問該廠應(yīng)如何安排兩種藥品的產(chǎn)量才能使每周獲得的利潤(rùn)最大？排兩種藥品的產(chǎn)量才能使每周獲得的利潤(rùn)最大？ 定義定義x x1 1為生產(chǎn)甲種藥品的計(jì)劃產(chǎn)量數(shù)，為生產(chǎn)甲種藥品的計(jì)劃產(chǎn)量數(shù)，x x2 2為生產(chǎn)乙種藥品的計(jì)劃產(chǎn)量數(shù)。為生產(chǎn)乙種藥品的計(jì)劃產(chǎn)量數(shù)。目標(biāo)：目標(biāo)： 使總利潤(rùn)使總利潤(rùn) Z=5xZ=5x1 1+2x+2x2 2 極大化極大化 約束：約束： 每周資源總量的限制，每周資源總量的限制， 30 x30 x1 1+20 x+20 x2 2160160 5x5x1 1+ x+ x2 2 1515甲種藥品每周產(chǎn)量不應(yīng)超過甲種藥品每周產(chǎn)量不應(yīng)超過4 4噸的限制噸的限制

16、x x1 144計(jì)劃生產(chǎn)數(shù)不可能是負(fù)數(shù)，計(jì)劃生產(chǎn)數(shù)不可能是負(fù)數(shù)， x x1 10 x0 x2 200每噸產(chǎn)品的消耗每噸產(chǎn)品的消耗 每周資源總量每周資源總量 甲甲乙乙維生素（公斤）維生素（公斤） 30302020160160設(shè)備（臺(tái)班）設(shè)備（臺(tái)班） 5 51 11515單位利潤(rùn)（萬元）單位利潤(rùn)（萬元） 5 5 數(shù)學(xué)模型為數(shù)學(xué)模型為 s.t.s.t. （subject to)subject to) (such that) (such that) 這是一個(gè)如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大這是一個(gè)如何合理的使用有限的資源，使生產(chǎn)經(jīng)營的效益達(dá)到最大的數(shù)學(xué)規(guī)劃問題。的數(shù)學(xué)規(guī)劃問題。 在滿

17、足一組約束條件的限制下，尋求決策變量在滿足一組約束條件的限制下，尋求決策變量x x1 1，x x2 2的決策值，使目的決策值，使目標(biāo)函數(shù)達(dá)到最大值。標(biāo)函數(shù)達(dá)到最大值。121212112maxZ=5x +2x30 x20 x1605xx15x4x0,x0每噸產(chǎn)品的消耗每噸產(chǎn)品的消耗 每周資源總量每周資源總量 甲甲乙乙維生素（公斤）維生素（公斤） 30302020160160設(shè)備（臺(tái)班）設(shè)備（臺(tái)班） 5 51 11515單位利潤(rùn)（萬元）單位利潤(rùn)（萬元） 5 5例：例：某化工廠根據(jù)一項(xiàng)合同要求為用戶生產(chǎn)一種用甲、乙兩種原料某化工廠根據(jù)一項(xiàng)合同要求為用戶生產(chǎn)一種用甲、乙兩種原料混合配制而成的特種產(chǎn)品。

18、已知甲、乙兩種原料都含有混合配制而成的特種產(chǎn)品。已知甲、乙兩種原料都含有A A、B B、C C三種三種化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合化學(xué)成分，兩種原料分別所含三種化學(xué)成分的百分比含量，以及按合同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示：同規(guī)定的產(chǎn)品中三種化學(xué)成分的最低含量如下表所示： 已知甲、乙兩種原料的成本分別是每公斤已知甲、乙兩種原料的成本分別是每公斤3 3元和元和2 2元，廠方希望元，廠方希望總成本達(dá)到最小，問如何配置該產(chǎn)品？總成本達(dá)到最小，問如何配置該產(chǎn)品？ 原料原料化學(xué)成分含量（化學(xué)成分含量（% %） 產(chǎn)品中化學(xué)成分的最低含量產(chǎn)品中化學(xué)成分的最低含量

19、（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化學(xué)成分化學(xué)成分定義定義x x1 1，x x2 2分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，分別為每公斤產(chǎn)品中甲，乙兩種原料的數(shù)量，目標(biāo)：使總成本目標(biāo)：使總成本 Z=3xZ=3x1 1+2x+2x2 2 極小化極小化 約束：配料平衡條件，約束：配料平衡條件， x x1 1+x+x2 2=1=1產(chǎn)品中產(chǎn)品中A A、B B、C C三種化學(xué)成分的最低含量三種化學(xué)成分的最低含量 12x12x1 1+3x+3x2 244 2x2x1 1+3x+3x2 222 3x3x1 1+15x+15x2 255非負(fù)性條件非

20、負(fù)性條件 x x1 10,x0,x2 200 原料原料化學(xué)成分含量（化學(xué)成分含量（% %） 產(chǎn)品中化學(xué)成分的最低含量產(chǎn)品中化學(xué)成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5單位成本（元）單位成本（元）化學(xué)成分化學(xué)成分 數(shù)學(xué)模型：數(shù)學(xué)模型： s.t.s.t. 這是一個(gè)原料配制問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織這是一個(gè)原料配制問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織 生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。生產(chǎn)，使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。 滿足一組約束條件的同時(shí)，尋求變量滿足一組約束條件的同時(shí)，尋求變量x x1

21、1和和x x2 2的值使目標(biāo)函數(shù)取得最小的值使目標(biāo)函數(shù)取得最小 值。值。 原料原料化學(xué)成分含量（化學(xué)成分含量（% %） 產(chǎn)品中化學(xué)成分的最低含量（產(chǎn)品中化學(xué)成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5單位成本（元）單位成本（元）化學(xué)成分化學(xué)成分121212121212minZ=3x +2xxx112x3x42x3x23x15x0 x0,x0例，例，某鐵器加工廠要制作某鐵器加工廠要制作100100套鋼架，每套要用長(zhǎng)為套鋼架，每套要用長(zhǎng)為2.92.9米，米，2.12.1米米和和1.51.5米的圓鋼各一根。已知原料長(zhǎng)為米的圓鋼各一根。

22、已知原料長(zhǎng)為7.47.4米，問應(yīng)如何下料，可使材米，問應(yīng)如何下料，可使材料最??？料最省？分析：在長(zhǎng)度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納分析：在長(zhǎng)度確定的原料上截取三種不同規(guī)格的圓鋼，可以歸納出出8 8種不同的下料方案：種不同的下料方案：圓鋼（米）圓鋼（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料頭（米）料頭（米）0 00.10.10.20.20.30.30.80.80.90.91.1.1.41.4 問題歸納為如何混合使用這問題歸納為如何混合使用

23、這8 8種不同的下料方案，來制造種不同的下料方案，來制造100100套鋼架，且要使剩余的料頭總長(zhǎng)為最短。套鋼架，且要使剩余的料頭總長(zhǎng)為最短。 設(shè)設(shè)x xj j表示用第表示用第j j種下料方案下料的原料根數(shù)，種下料方案下料的原料根數(shù)，j=1,2j=1,28,8,目標(biāo)：使料頭總長(zhǎng)度目標(biāo)：使料頭總長(zhǎng)度Z=0.1xZ=0.1x2 2+0.2x+0.2x3 3+0.3x+0.3x4 4+0.8x+0.8x5 5+0.9x+0.9x6 6+1.1x+1.1x7 7+1.4x+1.4x8 8極小化極小化約束：三種規(guī)格圓鋼根數(shù)約束：三種規(guī)格圓鋼根數(shù) x x1 1+2x+2x2 2+ x+ x4 4+ x+ x

24、6 6 =100 =100 2x2x3 3+2x+2x4 4+x+x5 5+ x+ x6 6+3x+3x7 7=100=100 3x 3x1 1+x+x2 2+2x+2x3 3+3x+3x5 5+x+x6 6+4x+4x8 8=100=100非負(fù)取整條件非負(fù)取整條件 x xj j0 (j=1,20 (j=1,28)8)且取整數(shù)且取整數(shù)圓鋼（米）圓鋼（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料頭（米）料頭（米）0 00.10.10.20.20.30.30

25、.80.80.90.91.1.1.41.4 數(shù)學(xué)模型數(shù)學(xué)模型 s.t.s.t. 這是一個(gè)下料問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)，這是一個(gè)下料問題，是在生產(chǎn)任務(wù)確定的條件下，合理的組織生產(chǎn)， 使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。使所消耗的資源數(shù)最少的數(shù)學(xué)規(guī)劃問題。 滿足一組約束條件的同時(shí)，尋求變量滿足一組約束條件的同時(shí)，尋求變量x x1 1至至x x8 8的值的值, ,使目標(biāo)函數(shù)取得最使目標(biāo)函數(shù)取得最 小值。小值。 2345678124634567 123568jminZ=0.1x +0.2x +0.3x +0.8x +0.9x +1.1x +1.4xx2x x x 100 2x2x

26、x x3x 1003xx2x 3x x 4x 100 x0 j1,2，8 ,圓鋼（米）圓鋼（米）2 29 91 12 20 01 10 01 10 00 02 21 10 00 02 22 21 11 13 30 01 15 53 31 12 20 03 31 10 04 4料頭（米）料頭（米）0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.4且為整數(shù)且為整數(shù)n 線性規(guī)劃的一般數(shù)學(xué)模型線性規(guī)劃的一般數(shù)學(xué)模型 線性規(guī)劃模型的特征：線性規(guī)劃模型的特征：（1 1）用一組決策變量）用一組決策變量x x1 1，x x2 2，x xn n表示某一方案，且在一般情況下

27、，表示某一方案，且在一般情況下，變量的取值是非負(fù)的。變量的取值是非負(fù)的。（2 2）有一個(gè)目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)可表示為這組變量的線性函數(shù)。）有一個(gè)目標(biāo)函數(shù)，這個(gè)目標(biāo)函數(shù)可表示為這組變量的線性函數(shù)。（3 3）存在若干個(gè)約束條件，約束條件用決策變量的線性等式或線）存在若干個(gè)約束條件，約束條件用決策變量的線性等式或線性不等式來表達(dá)。性不等式來表達(dá)。（4 4）要求目標(biāo)函數(shù)實(shí)現(xiàn)極大化（）要求目標(biāo)函數(shù)實(shí)現(xiàn)極大化（maxmax）或極小化（）或極小化（minmin）。）。滿足上述滿足上述4 4個(gè)特征的規(guī)劃問題稱為線性規(guī)劃問題個(gè)特征的規(guī)劃問題稱為線性規(guī)劃問題 線性規(guī)劃的模型的一般形式線性規(guī)劃的模型的一般形式:

28、: 目標(biāo)函數(shù)目標(biāo)函數(shù) 滿足約束條件滿足約束條件 通常稱通常稱 為決策變量，為決策變量， 為價(jià)值系數(shù)，為價(jià)值系數(shù)， 為消耗系數(shù)為消耗系數(shù), , 為資源限制系數(shù)。為資源限制系數(shù)。 1122nnmax(min)Z=c x +c x +c x1111221nn12112222nn2m11m22mnnm12n a xa xa x(,)b a xa xa x(,)b axaxax(,)b x ,x ,x0 12nx ,x ,x12nc ,c ,c1112mna ,a ,a12mb ,b ,b線性規(guī)劃的圖解法線性規(guī)劃的圖解法 適用于求解兩個(gè)變量的線性規(guī)劃問題適用于求解兩個(gè)變量的線性規(guī)劃問題n 圖解法的基本步

29、驟圖解法的基本步驟例例4,4,利用例利用例1 1說明圖解法的主要步驟，說明圖解法的主要步驟， 例例1 1的數(shù)學(xué)模型為的數(shù)學(xué)模型為 s.t. 121212112maxZ5x2x30 x2 0 x160 5xx15 x4x0, x0O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5121212112maxZ5x2x30 x2 0 x160 5xx15 x4x0, x012ZZZ=5 2xx，（ ，） 線性規(guī)劃圖解法的基本步驟：線性規(guī)劃圖解法的基本步驟：（1 1）建立以）建立以x x1 1,x,x2 2為坐標(biāo)軸的直角坐標(biāo)系，畫

30、出線性規(guī)劃為坐標(biāo)軸的直角坐標(biāo)系，畫出線性規(guī)劃 問題的可行域問題的可行域, ,（2 2）求目標(biāo)函數(shù)）求目標(biāo)函數(shù) Z=CZ=C1 1x x1 1+C+C2 2x x2 2 的梯度的梯度Z =Z =（c c1 1,c,c2 2）, ,（3 3）任取等值線）任取等值線 C C1 1x x1 1+C+C2 2x x2 2=Z=Z0 0, , 沿梯度沿梯度Z Z正方向平移正方向平移, , （若是極小化問題，則沿負(fù)梯度方向（若是極小化問題，則沿負(fù)梯度方向- -Z Z平移），平移）， 求等直線將離未離可行域時(shí)與可行域的交點(diǎn)。求等直線將離未離可行域時(shí)與可行域的交點(diǎn)。（4 4）若交點(diǎn)存在，則該點(diǎn)坐標(biāo)就是最優(yōu)解）若

31、交點(diǎn)存在，則該點(diǎn)坐標(biāo)就是最優(yōu)解 。*Xn 圖解法的幾種可能結(jié)果圖解法的幾種可能結(jié)果 (1(1）有唯一最優(yōu)解，如例）有唯一最優(yōu)解，如例1 1。（2 2）有無窮多最優(yōu)解）有無窮多最優(yōu)解 如例如例1 1中的目標(biāo)函數(shù)設(shè)為中的目標(biāo)函數(shù)設(shè)為 maxZ=10 xmaxZ=10 x1 1+2x+2x2 2 則目標(biāo)函數(shù)等值線則目標(biāo)函數(shù)等值線10 x10 x1 1+2x+2x2 2=Z =Z 與第二約束與第二約束 5x5x1 1+x+x2 21515 的邊界線平行。將等值線沿梯度的邊界線平行。將等值線沿梯度Z =Z =（1010，2 2）正方向平移）正方向平移 至至B B點(diǎn)時(shí)與可行域點(diǎn)時(shí)與可行域OABCOABC的

32、整條邊界線的整條邊界線ABAB重合。重合。 這表明線段這表明線段ABAB上的每一點(diǎn)都使目標(biāo)函數(shù)取得同樣的最大值，上的每一點(diǎn)都使目標(biāo)函數(shù)取得同樣的最大值， 因而都是最優(yōu)解。因而都是最優(yōu)解。O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5212xx10maxZ12ZZZ=2xx，（10，）例例5 5，試用圖解法求解下列線性規(guī)劃問題試用圖解法求解下列線性規(guī)劃問題 st.（3 3） 無界解（或稱無最優(yōu)解）無界解（或稱無最優(yōu)解） 無界解是指線性規(guī)劃問題的最優(yōu)解無界。無界解是指線性規(guī)劃問題的最優(yōu)解無界。若是極大化問題，則可使目標(biāo)函

33、數(shù)值若是極大化問題，則可使目標(biāo)函數(shù)值Z+,Z+, 極小化問題極小化問題 則可使目標(biāo)函數(shù)值則可使目標(biāo)函數(shù)值Z-Z-， 有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之有無界解的線性規(guī)劃問題的可行域通常是無界區(qū)域，但反之則不必然。則不必然。12121212minZ3x2x-2xx2 x -3x3 x0,x0 -1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O3312121212minZ3x2x-2xx2 x -3x3 x0,x012ZZZ=2xx，（-3,- ）（4 4）無可行解）無可行解 某些線性規(guī)劃問題的可行域是空集，既不存在滿足所有約束條某些線性規(guī)劃問題的

34、可行域是空集，既不存在滿足所有約束條件的點(diǎn)，這時(shí)問題無可行解，當(dāng)然更談不上最優(yōu)解了。件的點(diǎn)，這時(shí)問題無可行解，當(dāng)然更談不上最優(yōu)解了。 在實(shí)際中出現(xiàn)這種情況可以認(rèn)為資源條件無法滿足人們的要求，在實(shí)際中出現(xiàn)這種情況可以認(rèn)為資源條件無法滿足人們的要求，既不存在可行方案。既不存在可行方案。 標(biāo)準(zhǔn)線性規(guī)劃模型標(biāo)準(zhǔn)線性規(guī)劃模型 線性規(guī)劃問題的標(biāo)準(zhǔn)形式：線性規(guī)劃問題的標(biāo)準(zhǔn)形式： s.t s.t 其中其中(1.1)(1.1)為目標(biāo)函數(shù)，為目標(biāo)函數(shù)，(1.2)(1.2)為約束條件，為約束條件，(1.3)(1.3)為非負(fù)條件，為非負(fù)條件， 為稱呼方便，有時(shí)將為稱呼方便，有時(shí)將(1.3)(1.3)也稱為約束條件。也

35、稱為約束條件。（1.21.2） （1.31.3）線性規(guī)劃的標(biāo)準(zhǔn)形式線性規(guī)劃的標(biāo)準(zhǔn)形式（1.11.1）1122nn1111221nn12112222nn2 m11m22mnnm 12nmaxZ=c x +c x +c xa x +a x +a x =ba x +a x +a x =bax +ax +ax =b x ,x ,x0（一）、整數(shù)規(guī)劃問題實(shí)例（一）、整數(shù)規(guī)劃問題實(shí)例 例一、合理下料問題例一、合理下料問題設(shè)用某型號(hào)的圓鋼下零件設(shè)用某型號(hào)的圓鋼下零件A1, A2,Am 的毛坯。在一根圓鋼的毛坯。在一根圓鋼上下料的方式有上下料的方式有B1,B2, Bn 種，每種下料方式可以得到各種，每種下料方

36、式可以得到各種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎種零件的毛坯數(shù)以及每種零件的需要量，如表所示。問怎樣安排下料方式，使得即滿足需要，所用的原材料又最少？樣安排下料方式，使得即滿足需要，所用的原材料又最少？零件 方 個(gè)數(shù) 式零件零 件毛坯數(shù)nBB 1mAA 1mbb 1mnmnaaaa 1111二、整數(shù)規(guī)劃的模型二、整數(shù)規(guī)劃的模型 設(shè)：設(shè)：xj 表示用表示用Bj (j=1.2n) 種方式下料根數(shù)種方式下料根數(shù) 模型：模型：且且為為整整數(shù)數(shù)n)1.2(j 0)2 . 1( min11jnjijijnjjxmibxaxZ例二、例二、某公司計(jì)劃在某公司計(jì)劃在m個(gè)地點(diǎn)建廠，可供選擇的地點(diǎn)個(gè)地

37、點(diǎn)建廠，可供選擇的地點(diǎn)有有A1,A2Am ，他們的生產(chǎn)能力分別是他們的生產(chǎn)能力分別是a1,a2,am（假設(shè)（假設(shè)生產(chǎn)同一產(chǎn)品）。第生產(chǎn)同一產(chǎn)品）。第i i個(gè)工廠的建設(shè)費(fèi)用為個(gè)工廠的建設(shè)費(fèi)用為fi (i=1.2m),又有又有n個(gè)地點(diǎn)個(gè)地點(diǎn)B1,B2, Bn 需要銷售這種產(chǎn)品，需要銷售這種產(chǎn)品，其銷量分別為其銷量分別為b1.b2bn 。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)。從工廠運(yùn)往銷地的單位運(yùn)費(fèi)為為Cij。試決定應(yīng)在哪些地方建廠，即滿足各地需要，。試決定應(yīng)在哪些地方建廠，即滿足各地需要，又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？又使總建設(shè)費(fèi)用和總運(yùn)輸費(fèi)用最省？單 銷地廠址 價(jià)生產(chǎn)能力建設(shè)費(fèi)用銷量nmmmnmmmnnb

38、bbfacccAfacccAfacccABnBB 2121222222121111211121 設(shè)：設(shè)： xij 表示從工廠運(yùn)往銷地的運(yùn)量表示從工廠運(yùn)往銷地的運(yùn)量( (i=1.2m、j=1.2n), 1 ), 1 在在Ai建廠建廠 又設(shè)又設(shè) Yi （i=1.2m） 0 0 不在不在Ai建廠建廠 模型：模型：n)1.2jm1.2(i 1 0, 0n)1.2(j )2 . 1( min111、或或iijmijijnjiiijmiiiijijyxbxmiyaxyfxcZ（二）、整數(shù)規(guī)劃的數(shù)學(xué)模型（二）、整數(shù)規(guī)劃的數(shù)學(xué)模型一般形式一般形式且且部部分分或或全全部部為為整整數(shù)數(shù)或或 n)1.2(j 0)2

39、 . 1( )min(max11jnjijijnjjjxmibxaxcZZ 依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整依照決策變量取整要求的不同，整數(shù)規(guī)劃可分為純整數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、數(shù)規(guī)劃、全整數(shù)規(guī)劃、混合整數(shù)規(guī)劃、0 01 1整數(shù)規(guī)劃。整數(shù)規(guī)劃。 純整數(shù)規(guī)劃：純整數(shù)規(guī)劃：所有決策變量要求取非負(fù)整所有決策變量要求取非負(fù)整數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要數(shù)（這時(shí)引進(jìn)的松弛變量和剩余變量可以不要求取整數(shù)）。求取整數(shù)）。 全整數(shù)規(guī)劃：全整數(shù)規(guī)劃：除了所有決策變量要求取非負(fù)除了所有決策變量要求取非負(fù)整數(shù)外，系數(shù)整數(shù)外，系數(shù)aij和常數(shù)和常數(shù)bi也要求取整數(shù)（這時(shí)引也要求取整數(shù)（這