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

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

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

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

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

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

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

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

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

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

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

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

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

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

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