4.4-線性規(guī)劃(部編)課件

線性規(guī)劃§4.4§4.4.1

線性規(guī)劃問題的數(shù)學模型§4.4.2線性規(guī)劃問題的圖解法§4.4.3線性規(guī)劃問題的計算機求解1線性規(guī)劃是目前應用最為廣泛的一種系統(tǒng)優(yōu)化方法.它是運籌學的一個重要分支.自1947年丹捷格（G.B.Dantzig）提出了一般線性規(guī)劃的求解方法——單純形法之后，線性規(guī)劃在理論上趨向成熟，在實際應用中日益廣泛與深入.特別是在電子計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃更為廣泛地應用于工業(yè)、農(nóng)業(yè)、商業(yè)、交通運輸業(yè)、軍事、經(jīng)濟計劃和管理決策等各個領(lǐng)域，成為現(xiàn)代科學管理的重要工具之一.

簡單的線性規(guī)劃問題大都用圖解法或單純形法求解，而復雜的線性規(guī)劃問題可以用相應的數(shù)學軟件包（LINDO或LINGO）求解.引言24.4.1線性規(guī)劃問題的數(shù)學模型

在實際問題中，我們會經(jīng)常遇到在一定條件下使解決的問題達到最優(yōu).例如：在有限資源條件下，確定生產(chǎn)產(chǎn)品的品種、數(shù)量，使產(chǎn)值或利潤最大；用最小的人力、物力耗費來完成某項既定的任務等等.這在數(shù)學上我們稱之為規(guī)劃問題.線性規(guī)劃問題是規(guī)劃問題中最基本、最重要的一類問題.3單位產(chǎn)品所需原料原料產(chǎn)品AB原料供應量（公斤）甲116乙128丙105單位利潤（元）34求最大值[引例4.5]

生產(chǎn)組織與計劃問題某工廠計劃生產(chǎn)A、B兩種產(chǎn)品，要用甲、乙、丙三種不同的原料.每天原料供應的能力及每天生產(chǎn)一件產(chǎn)品A與B所需的原料與獲得的利潤如表4-6所示.問如何安排生產(chǎn)才能使一天的利潤為最大？4[分析]

設(shè)工廠每天生產(chǎn)A、B兩種產(chǎn)品的產(chǎn)量分別為（公斤），可獲得的利潤為（元），因此我們的目標是最大.但是由于生產(chǎn)受到外界條件的限制：每天甲原料最大供應量為每天乙原料最大供應量為每天丙原料最大供應量為且5綜上所述，本問題的數(shù)學模型為滿足其中，記號“”表示函數(shù)的最大值，函數(shù)稱為目標函數(shù)，不等式組稱為約束條件.6[引例4.6]合理下料問題某建筑工地，需要直徑相同、長度不同的成套鋼筋，每套由7根2m長與2根7m長的鋼筋組成.今有15m長的鋼筋150根，問如何下料，才能使廢料最少？[分析]

將一根15m長的鋼筋切割成長分別是7m和2m的兩種規(guī)格，有三種比較經(jīng)濟的方法，其結(jié)果如下表所示.切割方法7m長2m長廢料長方案一140方案二201方案三071設(shè)方案一、方案二和方案三的下料的原料根數(shù)分別為，則要解決的問題是采用合理的下料方案，使廢料的總長最少.7問題中所受的條件限制：鋼筋的總根數(shù)為根據(jù)配套的要求，即每套由7根2m長與2根7m長的鋼筋組成：即按方案一、二、三下料的原料根數(shù)都必須是非負的：同樣，我們將上述實際問題數(shù)學模型為滿足8上述兩個實例的數(shù)學模型有共同特征：

(1)每個問題都是求一組變量的值，這組變量稱為決策變量.它用來表示相應的活動方案，由于實際問題的要求，這些決策變量通常都是非負的.(2)每個問題都存在一定的限制條件，稱為約束條件，約束條件是決策變量的線性不等式或等式.(3)每個問題都有一個目標函數(shù)，要求目標函數(shù)的最大值或最小值，目標函數(shù)是決策變量的線性函數(shù).

我們將具有這些共同特征數(shù)學模型稱為線性規(guī)劃問題的數(shù)學模型.9一般的線性規(guī)劃問題的數(shù)學模型可記為：目標函數(shù)約束條件()滿足約束條件的一組變量的值稱為該線性規(guī)劃問題的可行解.所有可行解構(gòu)成的集合稱為可行域，使目標函數(shù)取得最大（或最小）值的可行解，稱為最優(yōu)解.104.4.2線性規(guī)劃問題的圖解法

若線性規(guī)劃問題只含有兩個決策變量，則可考慮用幾何作圖法求解.下面通過例題說明圖解法的一般步驟.例1對引例4.5給出的線性規(guī)劃問題的數(shù)學模型試用圖解法求解.11解如圖直角坐標系中，所有滿足約束條件的點必須落在陰影部分(它是可行域,這里的每一個點的坐標值都是可行解).目標函數(shù)可以看成是以S為參數(shù)，為斜率的一族平行直線：位于同一條直線上的點，具有同樣的目標函數(shù)值.12直線沿著法線的方向向右上角移動時，的值由小到大.當移動到B點時，S的值最大.即目標函數(shù)值在頂點B處取得最大值.(此時,B點坐標就是最優(yōu)解)而B點就是直線和直線的交點，求得B點坐標為（4，2），即當時，目標函數(shù)的最大值.即當該工廠生產(chǎn)4件產(chǎn)品A,2件產(chǎn)品B時，一天能獲得的最大利潤為20元.結(jié)論：若線性規(guī)劃問題存在最優(yōu)解，則它一定在可行域的某個頂點處.若在兩個頂點同時達到最優(yōu)值，則這兩個頂點連線上的任意一點都是最優(yōu)解.

13例2討論線性規(guī)劃問題的解的存在性?

解可作圖看出,同時滿足四個不等式組成的約束條件的點不存在,也就是說,該問題的可行域是空集.因此,無最優(yōu)點,即沒有最優(yōu)解.14除了以上幾種情況外,有時候可行域還可能出現(xiàn)無界區(qū)域.該類線性規(guī)劃問題的最優(yōu)解是否存在就與目標函數(shù)有緊密的聯(lián)系.

因此利用圖解法求線性規(guī)劃問題的最優(yōu)解時，可以先根據(jù)約束條件求出可行域（一般情況下是凸多邊形），然后把可行域的每個頂點代入目標函數(shù)，確定出最優(yōu)解即可.154.4.3線性規(guī)劃問題的計算機求解

1．線性規(guī)劃模型例3某公司長期飼養(yǎng)實驗用的動物,已知這些動物的生長對飼料中的蛋白質(zhì)、礦物質(zhì)、維生素這三種營養(yǎng)成分特別敏感，每個動物每天至少需要蛋白質(zhì)70g、礦物質(zhì)3g、維生素10mg.該公司能買到五種不同的飼料,每kg飼料所含的營養(yǎng)成分如表4-8所示,每kg飼料的成本如表4-9所示,試為該公司制定相應的飼料配方,以滿足動物生長的營養(yǎng)的需要,并使投入的總成本最低.16表4–8每千克飼料所含的營養(yǎng)成分

飼料蛋白質(zhì)(g)礦物質(zhì)(g)維生素(mg)123450.3210.61.80.10.050.020.20.050.050.10.020.20.08表4–9每千克飼料的成本飼料12345成本(元)0.20.70.40.30.517解設(shè)表示混合飼料中所含的第種飼料的數(shù)量(即決策變量),因為每個動物每天至少需要蛋白質(zhì)70g、礦物質(zhì)3g、維生素10mg,所以應滿足的約束條件為因要求配出來的飼料其總成本S最低,故其目標函數(shù)為18由于約束條件及目標函數(shù)均為線性函數(shù),故飼料配比問題的線性規(guī)劃模型為該問題可以利用LINGO軟件求解.在LINGO軟件中打開一個新文件,像書寫模型一樣,直接輸入:min0.2x1+0.7x2+0.4x3+0.3x4+0.5x5st0.3x1+2x2+x3+0.6x4+1.8x5>=700.1x1+0.05x2+0.02x3+0.2x4+0.05x5>=30.05x1+0.1x2+0.02x3+0.2x4+0.08x5>=10end19[注]①LINGO中已規(guī)定的所有決策變量均為非負,所以非負條件不需要在程序中體現(xiàn).②LINGO中乘號省略,式子中不能有括號,右端不能有數(shù)學符號.③LINGO程序中符號≤,≥用＜=,＞=形式輸入,它們與＜,＞等效④第一為目標函數(shù),其輸入時min或max后的變量及等號都不需要輸入.⑤在輸入約束條件的前一行要輸入st表示要滿足的約束條件.程序最后要以end語句表示結(jié)束.20程序運行輸出結(jié)果為Globaloptimalsolutionfound.Objectivevalue:24.74359Totalsolveriterations:4VariableValueReducedCostX10.0000000.8846154E-01X20.0000000.1358974X30.0000000.1410256X439.743590.000000X525.641030.000000RowSlackorSurplusDualPrice124.74359-1.00000020.000000-0.243589736.2307690.00000040.000000-0.769230821根據(jù)上述輸出結(jié)果可知最優(yōu)解為從而最低成本為[注意]在上述問題求解的基礎(chǔ)上,我們可以進一步進行以下思考:(1)如果每個動物每天至少所需的蛋白質(zhì)量增加到80g,則公司的飼料配方要如何調(diào)整?(2)如果飼料2每千克的成本降低到0.5元,則公司的飼料配方要如何調(diào)整?222．整數(shù)規(guī)劃模型如果一個線性規(guī)劃的某些決策變量或全部決策變量要求必須取整數(shù)，則這樣的問題成為整數(shù)線性規(guī)劃問題.例4一汽車廠生產(chǎn)小、中、大三種類型的汽車，已知各類型的每輛車對鋼材、勞動時間的需求，利潤以及每月工廠鋼材、勞動時間的現(xiàn)有量如下表所示.試制定每月生產(chǎn)計劃,使工廠的利潤最大.小型中型大型現(xiàn)有量鋼材(t)1.535600勞動時間(h)28025040060000利潤(萬元)23423解設(shè)每月生產(chǎn)小、中、大型汽車的數(shù)量分別為，工廠的月利潤為，在題目所給參數(shù)均不隨生產(chǎn)數(shù)量變化的假設(shè)下，立即可得線性規(guī)劃模型.目標函數(shù)在LINGO軟件求解中，程序最后即end語句后一行輸入：“gin3”表示均為整數(shù)，求得該問題的最優(yōu)解最優(yōu)值S=632，即問題要求的月生產(chǎn)計劃為生產(chǎn)小型車64輛，中型車168輛，不生產(chǎn)大型車.243．0-1規(guī)劃模型在實際的規(guī)劃問題中常常可以遇到這樣的問題:一個決策只用來指明一項可能的行動.究竟是采用()呢？還是采用()呢？這里的決策變量僅取0或1兩個值，即二元決策變量.25例5解下列0-1規(guī)劃問題:由于為0-1變量,用LINGO軟件求解時.可在程序最后類似整數(shù)規(guī)劃輸入:“int3”.最后求得該問題的最優(yōu)解，最優(yōu)值.264.指派問題我們常會遇到這樣的問題:有n項任務要完成,恰好有n人且每人可以分別去完成其中一項(即每一人都應分配一項任務,每一任務也只能由一人去完成),但由于任務性質(zhì)和各人任務的效率(或所花費的時間)有差別,因此提出下述問題:應當指派哪些人去完成哪些任務使總的效率為最高(或花費的總時間為最小)？這類問題稱為指派問題，或稱分派問題.27例6有一份說明書，要分別譯成英、日、德、俄四種文字，交給甲、乙、丙、丁四個人完成，每人完成一種，因各人專長不同，他們翻譯成不同文字所需要的時間（單位：分鐘）如下表所示.問指派哪個人去完成哪項任務可使總的花費時間最少？英日德俄甲215134乙1041415丙9141613丁7811928解設(shè)用來表示當不指派第個人去完成第項任務,令:這是個指派問題,從人力資源最佳分配角度,要以花費時間最少為目標:要合理分配資源且正常完成任務受到一些客觀條件的制約:(1)由于每個人只能接受一項任務:(2)又因每項任務只能分配給一個人:29所以該規(guī)劃問題的數(shù)學模型為由LINGO軟件運行的結(jié)果,得最佳分配方案為甲-—俄，乙—-日，丙-—英，丁---德，完成任務最少時間為28分鐘.30練習題4.41．用圖解法解下列線性規(guī)劃問題:(1)(2)(3)(4)312．某廠擬用集裝箱托運甲、乙兩種物資，每箱的體積、重量可獲利潤及托運所受限制如下表所示．問兩種物資各托運多少箱，可使獲得利潤最大？(請按兩種要求分別解題：①可拆箱裝運②整箱裝運)物資體積（立方米）重量（百公斤/箱）利潤（百元/箱）甲乙54252010托運限制2413323.某公司有1億元資金用于4個工程項目的投資,其投資各項目時所得的凈收益如下表所示工程項目ABCD收益(%)1510812由于某種原因,決定用于項目A的投資不大于其他各項投資之和,而用于項目B和C的投資要大