第9章線性規(guī)劃方法及其應(yīng)用講解課件

第9章線性規(guī)劃方法及其應(yīng)用1/4/20231第9章線性規(guī)劃方法及其應(yīng)用12/29/20221線性規(guī)劃（LinearProgramming）作為運(yùn)籌學(xué)的一個(gè)重要分支，是研究較早、理論較完善、應(yīng)用最廣泛的一個(gè)學(xué)科。它所研究的問(wèn)題主要包括兩個(gè)方面：一是在一項(xiàng)任務(wù)確定后，如何以最低成本（如人力、物力、資金和時(shí)間等）去完成這一任務(wù)；二是如何在現(xiàn)有資源條件下進(jìn)行組織和安排，以產(chǎn)生最大收益。因此，線性規(guī)劃是求一組變量的值，使它滿足一組線性式子，并使一個(gè)線性函數(shù)的值最大（或最小）的數(shù)學(xué)方法。線性規(guī)劃不僅僅是一種數(shù)學(xué)理論和方法，而且已成為現(xiàn)代管理工作中幫助管理者做出科學(xué)決策的重要手段。1/4/20232線性規(guī)劃（LinearProgramming）作為運(yùn)籌學(xué)的

1、康托洛維奇生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法,一本小冊(cè)子，1939;2、康托洛維奇“最佳資源利用的經(jīng)濟(jì)計(jì)算”——1942完成、1959發(fā)表的著作；3、自1947年丹茲格（G.B.Dantzing）提出求解線性規(guī)劃問(wèn)題的一般方法--單純形法之后，線性規(guī)劃在理論上趨于成熟，應(yīng)用日益廣泛與深入；

隨著電子計(jì)算機(jī)的發(fā)展和計(jì)算速度的不斷提高，其適用的領(lǐng)域更加廣泛，它已成為必不可少的重要手段之一。1/4/202331、康托洛維奇生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法,一

4、1975年庫(kù)伯曼斯(Koopmans)因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)；5、馮?諾伊曼和摩根斯坦1944年發(fā)表的

《對(duì)策論與經(jīng)濟(jì)行為》涉及與線性規(guī)劃等價(jià)的對(duì)策問(wèn)題及線性規(guī)劃對(duì)偶理論。1/4/202344、1975年庫(kù)伯曼斯(Koopmans)因線性規(guī)劃方法是數(shù)學(xué)規(guī)劃中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分支。最優(yōu)化/運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。線性規(guī)劃的基礎(chǔ)是線性變換。1/4/20235線性規(guī)劃方法是數(shù)學(xué)規(guī)劃中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分?jǐn)?shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃雙層規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容1/4/20236數(shù)非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)多目標(biāo)規(guī)劃雙層規(guī)劃組最優(yōu)計(jì)數(shù)問(wèn)9.1線性規(guī)劃是什么9.2建立線性規(guī)劃模型的一般步驟9.3線性規(guī)劃問(wèn)題的圖解法9.4線性規(guī)劃問(wèn)題解的性質(zhì)9.5解線性規(guī)劃問(wèn)題的單純形法9.6線性規(guī)劃的應(yīng)用1/4/202379.1線性規(guī)劃是什么12/29/202279.1線性規(guī)劃是什么1/4/202389.1線性規(guī)劃是什么12/29/202289.1線性規(guī)劃是什么我們先通過(guò)幾個(gè)實(shí)際問(wèn)題來(lái)認(rèn)識(shí)什么是線性規(guī)劃.【例9.1】

某企業(yè)生產(chǎn)三種產(chǎn)品，這些產(chǎn)品分別需要甲、乙兩種原料.生產(chǎn)每種產(chǎn)品一噸所需原料和每天原料總限量及每噸不同產(chǎn)品可獲利潤(rùn)情況如表9.1所示.表9.1企業(yè)生產(chǎn)數(shù)據(jù)表1.利潤(rùn)最大化問(wèn)題1/4/202399.1線性規(guī)劃是什么我們先通過(guò)幾個(gè)實(shí)際問(wèn)題來(lái)認(rèn)識(shí)什么是線9.1線性規(guī)劃是什么試問(wèn)：該企業(yè)怎樣安排生產(chǎn)才會(huì)使每天的利潤(rùn)最大？解設(shè)該企業(yè)每天生產(chǎn)產(chǎn)品的數(shù)量分別為（單位：噸），則總利潤(rùn)的表達(dá)式為我們希望在現(xiàn)有資源條件下總利潤(rùn)最大.現(xiàn)有資源的限制為（原料甲的限制）

（原料乙的限制）此外，由于未知數(shù)（我們稱之為決策變量）是計(jì)劃產(chǎn)量，應(yīng)有為非負(fù)的限制，即

1/4/2023109.1線性規(guī)劃是什么試問(wèn)：該企業(yè)怎樣安排生產(chǎn)才會(huì)使每天的9.1線性規(guī)劃是什么由此得到問(wèn)題的數(shù)學(xué)模型為其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

1/4/2023119.1線性規(guī)劃是什么由此得到問(wèn)題的數(shù)學(xué)模型為其中9.1線性規(guī)劃是什么類似于例9.1的這類問(wèn)題稱為最優(yōu)生產(chǎn)計(jì)劃問(wèn)題.其一般描述是利用種資源組織生產(chǎn)種產(chǎn)品.以表示資源的限制，表示產(chǎn)品的單位利潤(rùn)，表示單位產(chǎn)品消耗資源的數(shù)量（代表該企業(yè)當(dāng)前的技術(shù)水平），情況如表9.2所示.現(xiàn)在的問(wèn)題是：如果該企業(yè)生產(chǎn)的這種產(chǎn)品都可以賣出，如何合理充分地利用現(xiàn)有的資源，給出一個(gè)使總利潤(rùn)達(dá)到最大的產(chǎn)品生產(chǎn)計(jì)劃？1/4/2023129.1線性規(guī)劃是什么類似于例9.1的這類問(wèn)題稱為最優(yōu)生產(chǎn)有了解決上述問(wèn)題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的計(jì)劃產(chǎn)量分別為單位，則問(wèn)題的數(shù)學(xué)模型為9.1線性規(guī)劃是什么1/4/202313有了解決上述問(wèn)題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的模型中的都是實(shí)際問(wèn)題給定的常數(shù)；未知量為決策變量.這類決策問(wèn)題的應(yīng)用領(lǐng)域非常廣泛.

注本章的數(shù)學(xué)模型均可用軟件求解。

2.成本最小化問(wèn)題【例9.2】某鋼鐵廠熔煉一種新型不銹鋼，需要4種合金為原料經(jīng)測(cè)定這4種原料關(guān)于元素鉻（Cr）、錳（Mn）和鎳（Ni）的質(zhì)量分?jǐn)?shù)（%）、單價(jià)以及這種新型不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)，情況如表9.3所示.假設(shè)熔煉時(shí)質(zhì)量沒(méi)有損耗，問(wèn)：要熔煉100噸這樣的不銹鋼，應(yīng)選用原料各多少噸，能夠使成本最?。?.1線性規(guī)劃是什么1/4/202314模型中9.1線性規(guī)劃是什么下料問(wèn)題的一般描述：已知有一批原材料，每根長(zhǎng)度為L(zhǎng)，由于生產(chǎn)的需要，要求截出規(guī)格分別為的零件根.問(wèn)：如何截取使得總用料最省？即要求制定一個(gè)既能滿足生產(chǎn)的需要，又使得使用的原材料數(shù)量最少的下料方案.同樣可以仿照例9.4的建模過(guò)程列出此一般問(wèn)題的數(shù)學(xué)模型.總之，類似例9.1、9.2的實(shí)際問(wèn)題很多，而且形式多種多樣.通過(guò)這些問(wèn)題，我們可以看到上述各種問(wèn)題的共同點(diǎn)，即每一個(gè)問(wèn)題都用一組決策變量來(lái)表示某一方案，追求的目標(biāo)可以用關(guān)于決策變量的線性函數(shù)刻畫(huà)，或是最大化或是最小化，而要達(dá)到目標(biāo)的條件又都有一定的限制，每個(gè)限制條件均可由關(guān)于決策變量的線性等式或不等式表示.

1/4/2023159.1線性規(guī)劃是什么下料問(wèn)題的一般描述：已知有一批原材料9.1線性規(guī)劃是什么這類問(wèn)題所構(gòu)成的數(shù)學(xué)模型,稱為線性規(guī)劃模型.有時(shí)也直接將線性規(guī)劃模型稱為線性規(guī)劃問(wèn)題.針對(duì)這類模型,可以用根據(jù)數(shù)學(xué)理論設(shè)計(jì)的計(jì)算機(jī)軟件，如軟件求解，得出實(shí)際問(wèn)題需要的答案。1/4/2023169.1線性規(guī)劃是什么這類問(wèn)題所構(gòu)成的數(shù)學(xué)模型,稱為線性規(guī)9.2建立線性規(guī)劃模型的一般步驟1/4/2023179.2建立線性規(guī)劃模型的12/29/2022179.2建立線性規(guī)劃模型的一般步驟從§9.1節(jié)中對(duì)實(shí)際問(wèn)題建立數(shù)學(xué)模型的過(guò)程，可以得到一般線性規(guī)劃問(wèn)題建模過(guò)程如下：第1步理解要解決的問(wèn)題.搞清在什么條件下追求什么目標(biāo).第2步定義決策變量.每一個(gè)問(wèn)題都用一組決策變量來(lái)表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的.第3步確定約束條件.用一組決策變量的線性等式或不等式來(lái)表示在解決問(wèn)題過(guò)程中所必須遵循的約束條件.第4步列出目標(biāo)函數(shù).按實(shí)際問(wèn)題的不同，用決策變量的線性函數(shù)最大化或最小化形式寫(xiě)出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù).1/4/2023189.2建立線性規(guī)劃模型的一般步驟從§9.1節(jié)中對(duì)實(shí)際問(wèn)題9.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)劃問(wèn)題，為了便于建立其數(shù)學(xué)模型，常需要把反映問(wèn)題的背景數(shù)據(jù)資料用表格形式歸類綜合，以揭示各個(gè)量之間的內(nèi)在聯(lián)系.線性規(guī)劃的一般形式可表示為：1/4/2023199.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)9.2建立線性規(guī)劃模型的一般步驟其中稱為目標(biāo)函數(shù)，為決策變量，為約束常數(shù)，后面的式子為約束條件.這里的為常數(shù).當(dāng)要求決策變量均為整數(shù)時(shí)，稱（9.1）為純整數(shù)線性規(guī)劃問(wèn)題；當(dāng)要求決策變量均取0或1時(shí)，稱（9.1）為整數(shù)線性規(guī)劃問(wèn)題.當(dāng)要求決策變量既取實(shí)數(shù)又取整數(shù)時(shí)，稱（9.1）為混合整數(shù)線性規(guī)劃問(wèn)題.我們把滿足所有約束條件的解稱為線性規(guī)劃問(wèn)題（9.1）的可行解.全體可行解的集合稱為問(wèn)題（9.1）的可行域,記為.使目標(biāo)函數(shù)值最大（或最小）的可行解稱為該線性1/4/2023209.2建立線性規(guī)劃模型的一般步驟其中稱9.2建立線性規(guī)劃模型的一般步驟規(guī)劃問(wèn)題的最優(yōu)解，與此最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡(jiǎn)稱最優(yōu)值.因此，若記，求解線性規(guī)劃問(wèn)題（9.1），本質(zhì)上就是尋找一點(diǎn)，使得均滿足不等式【例9.3】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備（臺(tái)時(shí)），A、B兩種原材料的消耗以及資源的限制情況如表2.11所示.問(wèn)：該工廠應(yīng)分別生產(chǎn)多少甲產(chǎn)品和乙產(chǎn)品才能使工廠獲利最大？1/4/2023219.2建立線性規(guī)劃模型的一般步驟規(guī)劃問(wèn)題的最優(yōu)解，與9.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量.工廠目前要決策的是甲產(chǎn)品和乙產(chǎn)品的生產(chǎn)量，可以分別用變量來(lái)表示.由于它們表示產(chǎn)品產(chǎn)量，所以只取非負(fù)數(shù).其次，根據(jù)問(wèn)題的限制條件，列出表示約束條件的線性不等式：1/4/2023229.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量9.2建立線性規(guī)劃模型的一般步驟，（非負(fù)限制）

，（臺(tái)時(shí)數(shù)限制）

，（原材料限制）

，（原材料限制）最后，根據(jù)實(shí)際問(wèn)題所追求的目標(biāo)，列出其線性函數(shù)表達(dá)式.由于問(wèn)題的目標(biāo)是工廠獲利最大，假如產(chǎn)品都能銷售，則總利潤(rùn)可表示為，最大利潤(rùn)記為1/4/2023239.2建立線性規(guī)劃模型的一般步驟，（非負(fù)限制），（臺(tái)時(shí)9.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該問(wèn)題的線性規(guī)劃模型：1/4/2023249.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該計(jì)算最優(yōu)解為：即在現(xiàn)有資源條件下，該企業(yè)在計(jì)劃期內(nèi)生產(chǎn)的最優(yōu)計(jì)劃是：產(chǎn)品甲生產(chǎn)100單位，產(chǎn)品乙生產(chǎn)200單位，可實(shí)現(xiàn)最大利潤(rùn)130000元.9.2建立線性規(guī)劃模型的一般步驟1/4/202325計(jì)算最優(yōu)解為：9.2建立線性規(guī)劃模型的一般步驟12/299.2建立線性規(guī)劃模型的一般步驟

【例9.4】某醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí).不同時(shí)段需要的護(hù)士人數(shù)不等.據(jù)統(tǒng)計(jì)，各時(shí)段所需護(hù)士的最少人數(shù)如表2.9所示.如何安排才能做到安排最少的護(hù)士就能滿足工作的需要？1/4/2023269.2建立線性規(guī)劃模型的一般步驟【例9.4】某醫(yī)院9.2建立線性規(guī)劃模型的一般步驟解設(shè)為時(shí)段開(kāi)始上班的人數(shù)，.目標(biāo)是要求護(hù)士的總數(shù)最少.因?yàn)槊總€(gè)護(hù)士都工作8小時(shí)，即連續(xù)工作2個(gè)時(shí)段后休息，所以問(wèn)題的線性規(guī)劃模型為：1/4/2023279.2建立線性規(guī)劃模型的一般步驟解設(shè)為時(shí)段開(kāi)9.2建立線性規(guī)劃模型的一般步驟計(jì)算最優(yōu)解為： 故該醫(yī)院需雇用150名護(hù)士，最佳安排見(jiàn)表9.10所示.1/4/2023289.2建立線性規(guī)劃模型的一般步驟計(jì)算最優(yōu)解為：9.2建立線性規(guī)劃模型的一般步驟線性規(guī)劃的一般形式，可行解、最優(yōu)解等概念線性規(guī)劃問(wèn)題建模過(guò)程：第1步理解要解決的問(wèn)題。第2步定義決策變量。第3步確定約束條件。

第4步列出目標(biāo)函數(shù)。

1/4/2023299.2建立線性規(guī)劃模型的一般步驟線性規(guī)劃的一般形式，可行9.3線性規(guī)劃問(wèn)題的圖解法1/4/2023309.3線性規(guī)劃問(wèn)題的圖解法12/29/2022309.3線性規(guī)劃問(wèn)題的圖解法1.圖解法

對(duì)一個(gè)線性規(guī)劃問(wèn)題建立數(shù)學(xué)模型之后，就面臨著如何求解的問(wèn)題.這里先介紹含有兩個(gè)決策變量的線性規(guī)劃問(wèn)題的圖解法.它簡(jiǎn)單直觀，有助于了解線性規(guī)劃問(wèn)題求解的基本原理.

1/4/2023319.3線性規(guī)劃問(wèn)題的圖解法1.圖解法12/29/20圖解法的步驟可概括為：（1）在平面上建立直角坐標(biāo)系；（2）圖示約束條件，找出可行域（由于，可行域必位于第一象限）；（3）圖示目標(biāo)函數(shù)，即畫(huà)出目標(biāo)函數(shù)等值線；（4）對(duì)（或）問(wèn)題朝著增大（或減少）縱截距的方向平行移動(dòng)目標(biāo)函數(shù)等值線，至與可行域的邊界相切時(shí)為止.切點(diǎn)（即某個(gè)邊界點(diǎn)）就是代表最優(yōu)解的點(diǎn)；（5）尋找該點(diǎn)的坐標(biāo)得到最優(yōu)解.以下結(jié)合實(shí)例來(lái)具體說(shuō)明.

1/4/202332圖解法的步驟可概括為：12/29/2022329.3線性規(guī)劃問(wèn)題的圖解法

【例9.5】用圖解法求解線性規(guī)劃問(wèn)題

1/4/2023339.3線性規(guī)劃問(wèn)題的圖解法12/29/2022339.3線性規(guī)劃問(wèn)題的圖解法解先畫(huà)出線性規(guī)劃的可行域如圖9.1陰影部分.再畫(huà)出目標(biāo)函數(shù)等值線，朝著增大縱截距的方向平行移動(dòng)等值線至點(diǎn).最后求解線性方程組

求解得到點(diǎn)的坐標(biāo)，從而得到最優(yōu)解，最大值1/4/2023349.3線性規(guī)劃問(wèn)題的圖解法解先畫(huà)出線性規(guī)劃的可行域如9.3線性規(guī)劃問(wèn)題的圖解法1/4/2023359.3線性規(guī)劃問(wèn)題的圖解法12/29/2022359.3線性規(guī)劃問(wèn)題的圖解法【例9.6】用圖解法求解線性規(guī)劃問(wèn)題解先畫(huà)出線性規(guī)劃的可行域，如圖9.2陰影部分.

1/4/2023369.3線性規(guī)劃問(wèn)題的圖解法【例9.6】用圖解法求解線性規(guī)9.3線性規(guī)劃問(wèn)題的圖解法1/4/2023379.3線性規(guī)劃問(wèn)題的圖解法12/29/2022379.3線性規(guī)劃問(wèn)題的圖解法再畫(huà)出目標(biāo)函數(shù)等值線，朝著增大縱截距的方向平行移動(dòng)等值線至點(diǎn)B.最后求解線性方程組

得到解出點(diǎn)B的坐標(biāo)，從而得到最優(yōu)解，最大值

例9.5與例9.6中求解得到的問(wèn)題的最優(yōu)解是惟一的，但對(duì)一般線性規(guī)劃問(wèn)題，求解結(jié)果還可能出現(xiàn)其他情況.1/4/2023389.3線性規(guī)劃問(wèn)題的圖解法再畫(huà)出目標(biāo)函數(shù)等值線，朝著增大9.3線性規(guī)劃問(wèn)題的圖解法2.線性規(guī)劃解的其他情況（1）多重最優(yōu)解的情況

【例9.9】若將例9.5中的目標(biāo)函數(shù)變?yōu)椋瑒t代表目標(biāo)函數(shù)的直線平移到最優(yōu)位置后將和直線重合.此時(shí)，不僅頂點(diǎn)A，B都代表了最優(yōu)解，而且線段上AB的所有點(diǎn)都代表了最優(yōu)解.這個(gè)線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解，這些最優(yōu)解都對(duì)應(yīng)著相同的最大值1/4/2023399.3線性規(guī)劃問(wèn)題的圖解法2.線性規(guī)劃解的其他情況12MAX1/4/202340MAX12/29/2022409.3線性規(guī)劃問(wèn)題的圖解法（2）無(wú)界解的情況（3）無(wú)可行解的情況1/4/2023419.3線性規(guī)劃問(wèn)題的圖解法（2）無(wú)界解的情況（3）無(wú)可行9.3線性規(guī)劃問(wèn)題的圖解法（2）無(wú)界解的情況

【例9.10】對(duì)下述線性規(guī)劃問(wèn)題用圖解法求解結(jié)果如圖2.3(a)所示.從圖中可以看出，由于可行域是無(wú)界區(qū)域，當(dāng)目標(biāo)函數(shù)等值線沿箭頭方向平行移動(dòng)時(shí)，始終與該無(wú)界區(qū)域相交.此時(shí)，目標(biāo)函數(shù)值無(wú)上界，因此無(wú)最優(yōu)解，也稱最優(yōu)解無(wú)界.1/4/2023429.3線性規(guī)劃問(wèn)題的圖解法（2）無(wú)界解的情況12/29/9.3線性規(guī)劃問(wèn)題的圖解法（3）無(wú)可行解的情況

【例9.11】對(duì)線性規(guī)劃問(wèn)題由圖2.3(b)可以看出，同時(shí)滿足所有約束條件的點(diǎn)不存在，即可行域?yàn)榭占簿褪菦](méi)有可行解，故不存在最優(yōu)解.1/4/2023439.3線性規(guī)劃問(wèn)題的圖解法（3）無(wú)可行解的情況由圖2.39.3線性規(guī)劃問(wèn)題的圖解法當(dāng)根據(jù)實(shí)際問(wèn)題建立的線性規(guī)劃模型的求解結(jié)果出現(xiàn)（2）,（3）兩種情況時(shí)，一般說(shuō)明建模有錯(cuò)誤.前者缺乏必要的約束條件，后者是有矛盾的約束條件，建模時(shí)應(yīng)注意.下面再給出一個(gè)求目標(biāo)函數(shù)最小化的線性規(guī)劃問(wèn)題.【例9.12】求解線性規(guī)劃1/4/2023449.3線性規(guī)劃問(wèn)題的圖解法當(dāng)根據(jù)實(shí)際問(wèn)題建立的線性規(guī)劃模9.3線性規(guī)劃問(wèn)題的圖解法解畫(huà)出此線性規(guī)劃問(wèn)題的可行域，如圖中的陰影部分.目標(biāo)函數(shù)，它在坐標(biāo)平面上可表示為以f為參數(shù)，以-2/4為斜率的一組等值線.當(dāng)?shù)戎稻€移動(dòng)到B點(diǎn)時(shí)，目標(biāo)函數(shù)在可行域中取最小值.B點(diǎn)的坐標(biāo)可以從線性方程組中求出，為.這就是所求線性規(guī)劃問(wèn)題的最優(yōu)解，且.1/4/2023459.3線性規(guī)劃問(wèn)題的圖解法解畫(huà)出此線性規(guī)劃問(wèn)題的可行9.3線性規(guī)劃問(wèn)題的圖解法1/4/2023469.3線性規(guī)劃問(wèn)題的圖解法12/29/2022469.3線性規(guī)劃問(wèn)題的圖解法1.通過(guò)圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn)(1)可行解區(qū)域要畫(huà)正確(2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò)(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)1/4/2023479.3線性規(guī)劃問(wèn)題的圖解法1.通過(guò)圖解法了解線性規(guī)劃有幾9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/2023489.4線性規(guī)劃問(wèn)題解的性質(zhì)12/29/2022481.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形

前面曾給出了線性規(guī)劃問(wèn)題的一般形式，可以看出，其中有的要求目標(biāo)函數(shù)最大化，有的要求目標(biāo)函數(shù)最小化；約束條件可以是“≤”或“≥”形式的不等式，也可以是等式；決策變量一般是非負(fù)約束，但也允許在范圍內(nèi)取值，即無(wú)約束。為了進(jìn)一步研究和討論，就需要把線性規(guī)劃問(wèn)題的一般形式化為統(tǒng)一的標(biāo)準(zhǔn)形式。9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/2023491.線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形

前面曾給出了線性規(guī)劃問(wèn)題的一般形線性規(guī)劃的一般形式可表示為：1/4/202350線性規(guī)劃的一般形式可表示為：12/29/202250這里的標(biāo)準(zhǔn)形式有以下規(guī)定：（1）目標(biāo)函數(shù)是求最大值；（2）所有約束條件均用等式表示；（3）所有決策變量均取非負(fù)數(shù)；（4）所有約束常數(shù)均為非負(fù)數(shù).9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202351這里的標(biāo)準(zhǔn)形式有以下規(guī)定：9.4線性規(guī)劃問(wèn)題解的性質(zhì)1

于是，具有個(gè)約束條件和個(gè)決策變量的線性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)形為：9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202352于是，具有個(gè)約束條件和個(gè)決策變量的線性在約束條件

≥0（j=1，2，…，n）

下，求一組未知變量（j

=1，2，…，n）的值，使得。常記為如下更為緊湊的形式

或其縮寫(xiě)形式為：1/4/202353在約束條件

其中b和C為已知非負(fù)常數(shù)，A為已知常數(shù)矩陣，且rank(A)=m。一般可以通過(guò)以下方法，把非標(biāo)準(zhǔn)形線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形：（1）目標(biāo)函數(shù)的標(biāo)準(zhǔn)化如果線性規(guī)劃問(wèn)題是求目標(biāo)函數(shù)的最小值，即則令，得，這就同標(biāo)準(zhǔn)形的目標(biāo)函數(shù)的形式一致了.但要注意，如果要求原問(wèn)題的最優(yōu)值，應(yīng)取最優(yōu)值的相反數(shù).9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202354其中b和C為已知非負(fù)常數(shù)，A為已知常數(shù)矩陣，（2）約束條件的標(biāo)準(zhǔn)化當(dāng)約束條件為≤形式的不等式時(shí)，可在不等式左邊加上一個(gè)非負(fù)的新變量（稱為松弛變量(slackvariables)

），把不等號(hào)變?yōu)榈忍?hào)；當(dāng)約束條件為≥形式的不等式時(shí)，可在不等式左邊減去一個(gè)非負(fù)的新變量（稱為剩余變量），把不等號(hào)變?yōu)榈忍?hào).9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202355（2）約束條件的標(biāo)準(zhǔn)化9.4線性規(guī)劃問(wèn)題解的性質(zhì)12/（3）決策變量的標(biāo)準(zhǔn)化如果某一決策變量是一個(gè)符號(hào)不受限制的“自由變量”，可以引入兩個(gè)非負(fù)的新變量和，并作變換，將決策變量標(biāo)準(zhǔn)化。9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202356（3）決策變量的標(biāo)準(zhǔn)化9.4線性規(guī)劃問(wèn)題解的性質(zhì)12/（4）約束常數(shù)的標(biāo)準(zhǔn)化如果有某約束常數(shù)為負(fù)數(shù)，可在等式（或不等式）兩邊同時(shí)乘以，把約束常數(shù)變?yōu)檎龜?shù).9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202357（4）約束常數(shù)的標(biāo)準(zhǔn)化9.4線性規(guī)劃問(wèn)題解的性質(zhì)12/【例9.13】把下面的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形：【解】此例只有約束條件不符合標(biāo)準(zhǔn)形，為此引入非負(fù)的松弛變量，并分別把它們加到第1個(gè)和第2個(gè)不等式的左邊，即得標(biāo)準(zhǔn)形：注意，所加松弛變量表示沒(méi)有被利用的資源，當(dāng)然也沒(méi)有利潤(rùn)，所以在目標(biāo)函數(shù)中的系數(shù)應(yīng)為零.9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202358【例9.13】把下面的線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形：9.4線9.4線性規(guī)劃問(wèn)題解的性質(zhì)【例9.14】將下面線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形【解】令，把求改為求；用替換，其中；在第1個(gè)約束不等式的左邊加入松弛變量，在第2個(gè)約束不等式的左邊減去剩余變量，這樣即可得到該問(wèn)題的標(biāo)準(zhǔn)形為1/4/2023599.4線性規(guī)劃問(wèn)題解的性質(zhì)【例9.14】將下面線性規(guī)劃問(wèn)，

9.4線性規(guī)劃問(wèn)題解的性質(zhì)標(biāo)準(zhǔn)形原問(wèn)題1/4/202360，9.4線性規(guī)劃問(wèn)題解的性質(zhì)標(biāo)準(zhǔn)形原問(wèn)題12/29/22.線性規(guī)劃的解

可行解與最優(yōu)解

滿足約束條件（即滿足線性約束和非負(fù)約束）的一組變量為可行解。所有可行解組成的集合稱為可行域。使目標(biāo)函數(shù)最大或最小化的可行解稱為最優(yōu)解。

1/4/2023612.線性規(guī)劃的解12/29/202261基本解與基本可行解

在線性規(guī)劃問(wèn)題中，將約束方程組的m×n階矩陣A寫(xiě)成由n個(gè)列向量組成的分塊矩陣1/4/202362基本解與基本可行解12/29/202262如果B是A中的一個(gè)m階的非奇異子陣，則稱B為該線性規(guī)劃問(wèn)題的一個(gè)基。不失一般性，不妨設(shè)則稱為基向量，與基向量相對(duì)應(yīng)的向量為基變量，而其余的變量為非基變量。

1/4/202363如果B是A中的一個(gè)m階的非奇異子陣，則稱B為如果是方程組的解,則就是方程組的一個(gè)解，它稱之為對(duì)應(yīng)于基B的基本解，簡(jiǎn)稱基解。滿足非負(fù)約束條件的基本解，稱為基本可行解。對(duì)應(yīng)于基本可行解的基，稱為可行基。1/4/202364如果線性規(guī)劃問(wèn)題的以上幾個(gè)解的關(guān)系，可用下圖來(lái)描述：1/4/202365線性規(guī)劃問(wèn)題的以上幾個(gè)解的關(guān)系，可用下圖來(lái)描述：12/29/【定義9.1】如果集合K中任意兩點(diǎn)s,t之間連線上所有的點(diǎn)都是集合K中的點(diǎn)，即對(duì)于任意的，都有，則稱K為凸集.例如圖9.5中（a）,（b）,（c）為凸集，而（d）,（e）不是凸集.

3.線性規(guī)劃問(wèn)題解的基本性質(zhì)(a)(b)(c)(d)(e)

圖9.5凸集與非凸集示例9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202366【定義9.1】如果集合K中任意兩點(diǎn)s,t之間連線上所有的【定理9.1

】線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集.這兩個(gè)定理我們不給予數(shù)學(xué)證明.結(jié)合圖解法，我們可以清晰地了解到線性規(guī)劃問(wèn)題解的有關(guān)性質(zhì).定理9.1說(shuō)明：聯(lián)結(jié)線性規(guī)劃問(wèn)題任意兩個(gè)可行解的線段上的點(diǎn)（坐標(biāo)）仍是可行解.定理9.2則告訴我們：如果一個(gè)線性規(guī)劃問(wèn)題有最優(yōu)解，則一定可以從可行域的有限個(gè)頂點(diǎn)中找到.【定理9.2

】若可行域非空有界，則線性規(guī)劃問(wèn)題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到.9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202367【定理9.1】線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集.這兩個(gè)定理【定義9.2

】如果凸集K中的點(diǎn)x不能成為任何線段的內(nèi)點(diǎn)，即對(duì)任意，都不存在，使得，則稱x為K的一個(gè)頂點(diǎn).例如三角形、正方形、凸多邊形、凸無(wú)界區(qū)域的頂點(diǎn)及圓周上的點(diǎn)，都是相應(yīng)凸集的頂點(diǎn).從圖解法的例子中知道線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集，且如果問(wèn)題有最優(yōu)值，都是在頂點(diǎn)上達(dá)到.這些性質(zhì)推廣到一般，就是下面幾個(gè)重要定理.9.4線性規(guī)劃問(wèn)題解的性質(zhì)1/4/202368【定義9.2】如果凸集K中的點(diǎn)x不能成為任何線段的內(nèi)點(diǎn)，9.4線性規(guī)劃問(wèn)題解的性質(zhì)1.將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形的方法2.線性規(guī)劃問(wèn)題的解3.線性規(guī)劃問(wèn)題解的性質(zhì)（1）線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集。（2）若可行域非空有界，則線性規(guī)劃問(wèn)題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到。1/4/2023699.4線性規(guī)劃問(wèn)題解的性質(zhì)1.將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形的方9.5解線性規(guī)劃問(wèn)題的單純形法

1/4/2023709.5解線性規(guī)劃問(wèn)題的單純形法12/29/202270單純形法是求解線性規(guī)劃的一種通用方法，1947年由美國(guó)數(shù)學(xué)家丹茲格（G.B.Dantzig）給出.下面結(jié)合§9.1中的利潤(rùn)最大化問(wèn)題介紹單純形法的基本內(nèi)容.由§9.1中的例9.1提供的數(shù)學(xué)模型為:9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202371單純形法是求解線性規(guī)劃的一種通用方法，1947（1）先化為標(biāo)準(zhǔn)形.引入松弛變量得到標(biāo)準(zhǔn)形9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202372（1）先化為標(biāo)準(zhǔn)形.引入松弛變量（2）再把目標(biāo)函數(shù)改寫(xiě)成并把它加入到約束方程組中去，即得到方程組9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202373（2）再把目標(biāo)函數(shù)改寫(xiě)成并把它加入到約束方程組中去，即得到方將此方程組的系數(shù)及常數(shù)項(xiàng)b列成一個(gè)數(shù)表，即.9.5解線性規(guī)劃問(wèn)題的單純形法

稱此表為初始單純形表.表中的數(shù)字被分成了4部分，位于左下角的每個(gè)數(shù)字稱為檢驗(yàn)數(shù).此時(shí)與對(duì)應(yīng)的檢驗(yàn)數(shù)都是負(fù)數(shù)，因此，若不令

，只要有一個(gè)是正數(shù)，則它與負(fù)數(shù)相乘后仍是負(fù)數(shù)，移項(xiàng)到右邊，函數(shù)值就會(huì)增大，為此轉(zhuǎn)到下一步.

1/4/202374將此方程組的系數(shù)及常數(shù)項(xiàng)b列成一個(gè)數(shù)表，即.9.5解線性（3）在負(fù)檢驗(yàn)數(shù)中選絕對(duì)值最大的負(fù)數(shù)（即7），在對(duì)應(yīng)的列中，將該列中的正數(shù)分別去除對(duì)應(yīng)的常數(shù)項(xiàng)，選擇比值最小者所對(duì)應(yīng)的元素為主元（稱為最小比值原則）.在這里然后用矩陣的初等行變換，將主元化為1，把同列的其他元素化為0.這一過(guò)程如下：將矩陣

可知位于第2行、第3列的元素3為主元，標(biāo)為,9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202375（3）在負(fù)檢驗(yàn)數(shù)中選絕對(duì)值最大的負(fù)數(shù)（即7），在對(duì)應(yīng)的列中的第2行乘以1/3，得

再將矩陣的第2行乘以（2）加到第1行，第2行乘以7加到第3行，得

此時(shí)的目標(biāo)函數(shù)值已經(jīng)由原來(lái)的0增加到700/3.由于檢驗(yàn)數(shù)中仍有負(fù)數(shù)，按照最小比值原則，可知位于第1行、第2列的元素4/3為主元.同樣用矩陣的初等行變換，將主元化為1，把同列的其他元素化為0，

9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202376的第2行乘以1/3，得再將矩陣的第2行乘以（2）加到過(guò)程如下：將矩陣A的第1行乘以3/4，得這時(shí)表中已經(jīng)沒(méi)有負(fù)檢驗(yàn)數(shù)，表明目標(biāo)函數(shù)已經(jīng)達(dá)到最大值.最后這張表稱為最優(yōu)單純形表.易知最優(yōu)解為最優(yōu)值為250.從而原線性規(guī)劃問(wèn)題的最優(yōu)解為對(duì)應(yīng)的目標(biāo)函數(shù)最優(yōu)值為250.9.5解線性規(guī)劃問(wèn)題的單純形法再將矩陣的第2行乘以（2）加到第1行，第2行乘以7加到第3行，得1/4/202377過(guò)程如下：將矩陣A的第1行乘以3/4，得這時(shí)表中已經(jīng)沒(méi)有上述求解線性規(guī)劃問(wèn)題的方法稱為單純形法.單純形法步驟如下：第1步，將線性規(guī)劃化成標(biāo)準(zhǔn)形；第2步，寫(xiě)出初始單純形表；第3步，對(duì)檢驗(yàn)數(shù)進(jìn)行檢驗(yàn).若檢驗(yàn)數(shù)均為非負(fù)數(shù)，則得到最優(yōu)單純形表.若有負(fù)數(shù)，則在檢驗(yàn)數(shù)絕對(duì)值最大的負(fù)數(shù)所對(duì)應(yīng)的列中，按最小比值原則選主元，用初等行變換化主元為1，主元所在列其余元素化為0，得到一張新單純形表.再檢驗(yàn)該表是否為最優(yōu)單純形表，若不是，重復(fù)上述過(guò)程，直到得出最優(yōu)單純形表.第4步，從最優(yōu)單純形表直接寫(xiě)出最優(yōu)解和最優(yōu)值.9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202378上述求解線性規(guī)劃問(wèn)題的方法稱為單純形法.9.5解從上例求解過(guò)程看到，單純形表中所對(duì)應(yīng)的列始終不變，故在實(shí)際計(jì)算中可省去不寫(xiě).上例的求解過(guò)程本質(zhì)上是矩陣的初等行變換過(guò)程，我們可以把此例的單純形法求解過(guò)程簡(jiǎn)化為9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202379從上例求解過(guò)程看到，單純形表中所對(duì)應(yīng)的列始終不變，故在實(shí)9.5解線性規(guī)劃問(wèn)題的單純形法所以最優(yōu)解及最優(yōu)值分別為【注1】若在計(jì)算過(guò)程中，單純形表出現(xiàn)某檢驗(yàn)數(shù)為負(fù)，但其所在的列無(wú)正元素的情況，則可以證明該問(wèn)題無(wú)最優(yōu)解.

1/4/2023809.5解線性規(guī)劃問(wèn)題的單純形法所以最優(yōu)解及最優(yōu)值分別為【【解】引入松弛變量，化為標(biāo)準(zhǔn)形

9.5解線性規(guī)劃問(wèn)題的單純形法【例9.15】解線性規(guī)劃問(wèn)題

1/4/202381【解】引入松弛變量，化為標(biāo)準(zhǔn)形9.5解線性規(guī)劃問(wèn)題的單初始單純形表為由于檢驗(yàn)數(shù)1所在列無(wú)正數(shù)元素，故此問(wèn)題無(wú)最優(yōu)解.9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202382初始單純形表為由于檢驗(yàn)數(shù)1所在列無(wú)正數(shù)元素，故此問(wèn)題無(wú)最優(yōu)【注2】在上例的初始單純形表中，由虛線隔開(kāi)的左上部分，所在列的元素構(gòu)成一個(gè)二階單位矩陣我們稱為基變量.一般地，對(duì)含有n個(gè)變量、m個(gè)約束的線性規(guī)劃問(wèn)題，當(dāng)把它化為標(biāo)準(zhǔn)形后，若恰有一個(gè)m階單位矩陣，就可以用前面的單純形法求出最優(yōu)解（若最優(yōu)解存在）；若基變量不足m個(gè)，則用改進(jìn)單純形法或?qū)ε紗渭冃畏ㄇ蠼?由于這兩種方法用到較多的數(shù)學(xué)知識(shí)，這里不再介紹，但WinQSB軟件中的線性規(guī)劃程序已經(jīng)包含了改進(jìn)單純形法和對(duì)偶單純形法.9.5解線性規(guī)劃問(wèn)題的單純形法1/4/202383【注2】在上例的初始單純形表中，由虛線隔開(kāi)的左上部分，所在列9.5解線性規(guī)劃問(wèn)題的單純形法1.判斷基本可行解.有3種情形：①已是最優(yōu)解，②是無(wú)界解，③不能確定.前2種情形計(jì)算結(jié)束，第3種情形需要繼續(xù)迭代，先進(jìn)基后出基，初等變換求下一個(gè)基本可行解，直到出現(xiàn)最優(yōu)解或無(wú)界解為止。2.判定方法唯一最優(yōu)解的判定：所有非基變量的檢驗(yàn)數(shù)非零,則線規(guī)劃具有唯一最優(yōu)解。多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解。無(wú)界解的判斷:

某個(gè)檢驗(yàn)數(shù)大于0且該檢驗(yàn)數(shù)所在列中所有元素小或等于，則線性規(guī)劃具有無(wú)界解。1/4/2023849.5解線性規(guī)劃問(wèn)題的單純形法1.判斷基本可行解.有3種9.6線性規(guī)劃的應(yīng)用1/4/2023859.6線性規(guī)劃的應(yīng)用12/29/2022859.6線性規(guī)劃的應(yīng)用

線性規(guī)劃在國(guó)內(nèi)外很多部門(mén)的規(guī)劃、管理、決策過(guò)程中有大量成功的應(yīng)用，并收到了良好的效果.但是，應(yīng)用線性規(guī)劃來(lái)解決某一類實(shí)際問(wèn)題時(shí)，由于問(wèn)題的復(fù)雜性和情況的多變性，要真正建立一個(gè)反映實(shí)際問(wèn)題的、能得出正確結(jié)論的理想模型，并不是一件容易的事情.它要求建模者具有豐富的經(jīng)驗(yàn)、較強(qiáng)的創(chuàng)造力和比較熟練的技巧.本節(jié)通過(guò)一些被簡(jiǎn)化了的問(wèn)題，介紹建立線性規(guī)劃模型的基本思路和基本技巧.1/4/2023869.6線性規(guī)劃的應(yīng)用線性規(guī)劃在國(guó)內(nèi)外很多部門(mén)1.辦學(xué)規(guī)模問(wèn)題【例9.16】某人準(zhǔn)備投資1200萬(wàn)元辦一所中學(xué)，為了考慮社會(huì)效益和經(jīng)濟(jì)效益，對(duì)該地區(qū)教育市場(chǎng)進(jìn)行調(diào)查，得出一組數(shù)據(jù)，如表9.12所示.表9.12市場(chǎng)調(diào)查表9.6線性規(guī)劃的應(yīng)用班級(jí)班級(jí)學(xué)生數(shù)配備教師數(shù)硬件建設(shè)費(fèi)（萬(wàn)元）教師年薪（萬(wàn)元）初中502.0281.2高中402.5581.6根據(jù)物價(jià)部門(mén)的有關(guān)文件，初中是義務(wù)教育階段，收費(fèi)標(biāo)準(zhǔn)適當(dāng)控制，預(yù)計(jì)除書(shū)費(fèi)、辦公費(fèi)外，初中每個(gè)學(xué)生每年可收取600元，而高中每個(gè)學(xué)生每年可收取1500元.因生源和環(huán)境等條件限制，辦學(xué)規(guī)模以20～30個(gè)（含20與30）班為宜.教師實(shí)行聘任制.初、高中的教育周期均為3年.請(qǐng)你合理地安排招生計(jì)劃，使年利潤(rùn)最大.問(wèn)：大約經(jīng)過(guò)多少年可以收回全部投資？1/4/2023871.辦學(xué)規(guī)模問(wèn)題9.6線性規(guī)劃的應(yīng)用班級(jí)班級(jí)學(xué)生數(shù)配備教解設(shè)初中編制班數(shù)為x,高中編制班數(shù)為y,又設(shè)年利潤(rùn)為f,（單位：萬(wàn)元），那么即.于是此問(wèn)題的線性規(guī)劃模型為解得最優(yōu)解代入中得9.6線性規(guī)劃的應(yīng)用1/4/202388解設(shè)初中編制班數(shù)為x,高中編制班數(shù)為y,又設(shè)年利潤(rùn)為f故學(xué)校的最優(yōu)規(guī)模和招生計(jì)劃分別為最優(yōu)規(guī)模：初中18個(gè)班，高中12個(gè)班；招生計(jì)劃：第1年初中招生6個(gè)班約300人，高中招生4個(gè)班約160人.以后每年按此計(jì)劃招生.設(shè)經(jīng)過(guò)n年可收回投資.第1年利潤(rùn)為第2年利潤(rùn)為

2×11.6=23.2(萬(wàn)元);以后每年的利潤(rùn)均為34.8萬(wàn)元.故依題意應(yīng)有解得(年).即約經(jīng)過(guò)36年可以收回全部投資.9.6線性規(guī)劃的應(yīng)用1/4/202389故學(xué)校的最優(yōu)規(guī)模和招生計(jì)劃分別為設(shè)經(jīng)過(guò)n年可收回投資.2.投資問(wèn)題【例9.17】某投資人在今后3年內(nèi)有A,B,C,D共4個(gè)投資項(xiàng)目，項(xiàng)目A在3年內(nèi)每年初投資，年底可獲利潤(rùn)20%，并可將本金收回；項(xiàng)目B在第1年年初投資，第2年年底可獲利潤(rùn)60%，并將本金收回，但該項(xiàng)目投資不得超過(guò)5萬(wàn)元；項(xiàng)目C在第2年初投資，第3年底收回本金，并獲利潤(rùn)40%，但該項(xiàng)目投資不得超過(guò)3萬(wàn)元；項(xiàng)目D在第3年初投資，于該年底收回本金，且獲利潤(rùn)30%，但該項(xiàng)目投資不得超過(guò)2萬(wàn)元.該投資人準(zhǔn)備拿出6萬(wàn)元資金，問(wèn)如何制訂投資計(jì)劃，使該企業(yè)在第3年底，投資的本利之和最大？9.6線性規(guī)劃的應(yīng)用1/4/2023902.投資問(wèn)題9.6線性規(guī)劃的應(yīng)用12/29/20229【解】這是一個(gè)連續(xù)投資問(wèn)題.設(shè)決策變量xij為第j年投資到第i個(gè)項(xiàng)目的資金(i=1,2,3,4,分別對(duì)應(yīng)于項(xiàng)目A,B,C,D；分別對(duì)應(yīng)于投資年份),見(jiàn)列表9.13.表9.13投資項(xiàng)目投資機(jī)會(huì)項(xiàng)目名稱第1年年初第2年年初第3年年初ABCD9.6線性規(guī)劃的應(yīng)用1/4/202391【解】這是一個(gè)連續(xù)投資問(wèn)題.設(shè)決策變量xij為第j年投資下面分析每年資金的使用情況并建立線性規(guī)劃模型.第1年初，有A,B兩個(gè)項(xiàng)目，企業(yè)只能提供6萬(wàn)元資金，故有:.項(xiàng)目B不得超過(guò)5萬(wàn)元，有

第2年初，有A,C兩個(gè)投資項(xiàng)目.此時(shí)第1年初投資到項(xiàng)目A的資金已全部收回，本利和為

.這些資金可用于第2年的投資，，而且要求

9.6線性規(guī)劃的應(yīng)用于是；；1/4/202392下面分析每年資金的使用情況并建立線性規(guī)劃模型..項(xiàng)目B不得超9.6線性規(guī)劃的應(yīng)用第3年初，第1年初投資到項(xiàng)目B的資金全部收回，本利和為;第2年初投資于項(xiàng)目A的資金也全部收回，本利和為以上兩筆資金可供該年繼續(xù)投資.第3年內(nèi)還有A,D兩個(gè)項(xiàng)目的投資，可得，而且要求

第3年底，到期把所有本利和收回.所能收回的資金有第2年初投資到項(xiàng)目C的本利和，第3年初投資到項(xiàng)目A的本利和

及投資到項(xiàng)目D的本利和，則第3年底獲得的本利和為

;1/4/2023939.6線性規(guī)劃的應(yīng)用第3年初，第1年初投資到項(xiàng)目B的資金將上述目標(biāo)函數(shù)和約束條件整理后即可得出該問(wèn)題完整的線性規(guī)劃模型:求解得到最優(yōu)投資方案如表9.14所示，且在第3年底收回投資的本利和最大為11.528萬(wàn)元.9.6線性規(guī)劃的應(yīng)用1/4/202394將上述目標(biāo)函數(shù)和約束條件整理后即可得出該問(wèn)題完整的線性規(guī)劃模表9.14最優(yōu)投資方案投資機(jī)會(huì)

項(xiàng)目名稱第1年年初第2年年初第3年年初AX11=1X12=1.2X13=7.44BX21=5CX32=0DX43=29.6線性規(guī)劃的應(yīng)用1/4/202395表9.14最優(yōu)投資方案投資機(jī)會(huì)3.人力資源分配問(wèn)題【例9.19】某百貨商場(chǎng)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如表9.16所示.為了保證售貨員充分休息，售貨員每周工作5天，休息2天，并要求休息的2天是連續(xù)的，問(wèn)：應(yīng)該如何安排售貨員的作息時(shí)間，既滿足工作需要，又使配備的售貨員人數(shù)最少？表9.16售貨人員需求統(tǒng)計(jì)表時(shí)間所需售貨員人數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六289.6線性規(guī)劃的應(yīng)用1/4/2023963.人力資源分配問(wèn)題表9.16售貨人員需求統(tǒng)計(jì)表時(shí)間所需【解】設(shè)xj為星期j開(kāi)始休息的人數(shù)（j=1,2,…，７，分別對(duì)應(yīng)星期一、二、三、四、五、六、日）.目標(biāo)是要求售貨員的總數(shù)最少.因?yàn)槊總€(gè)售貨員都工作5天，休息2天，所以只要計(jì)算出連續(xù)休息2天的售貨員數(shù)，也就計(jì)算出了售貨員的總數(shù).這里可以把連續(xù)休息2天的售貨員按照開(kāi)始休息的時(shí)間分成7類，各類的人數(shù)分別為xj（j=1,2,…，７），即有目標(biāo)函數(shù)：再按照每天所需售貨員的人數(shù)寫(xiě)出約束條件.例如星期日需要28人，商場(chǎng)中的全體售貨員中除了星期六和星期日開(kāi)始休息的人外都應(yīng)該上班，即有約束條件9.6線性規(guī)劃的應(yīng)用1/4/202397【解】設(shè)xj為星期j開(kāi)始休息的人數(shù)（j=1,2,…，７，同理有因xj（j=1,2,…，７）表示人數(shù)，故有xj≥０j=1,2,…，７），且為整數(shù)9.6線性規(guī)劃的應(yīng)用綜上得問(wèn)題的線性規(guī)劃模型為：1/4/202398同理有因xj（j=1,2,…，７）表示人數(shù)，故有9.69.6線性規(guī)劃的應(yīng)用計(jì)算結(jié)果：也就是說(shuō)該商場(chǎng)至少需要售貨員36人.他們的的休息安排為：星期一12人；星期三11人；星期五5人；星期日8人.1/4/2023999.6線性規(guī)劃的應(yīng)用計(jì)算結(jié)果：一、對(duì)偶問(wèn)題的提出

線性規(guī)劃的對(duì)偶原理對(duì)偶是什么：對(duì)同一事物（或問(wèn)題），從不同的角度（或立場(chǎng)）提出對(duì)立的兩種不同的表述。對(duì)偶思想舉例在平面內(nèi)，矩形的面積與其周長(zhǎng)之間的關(guān)系，有兩種不同的表述方法。（1）周長(zhǎng)一定，面積最大的矩形是正方形。（2）面積一定，周長(zhǎng)最短的矩形是正方形。1/4/2023100一、對(duì)偶問(wèn)題的提出線性規(guī)劃的對(duì)偶原理對(duì)偶是什么：二、原問(wèn)題和對(duì)偶問(wèn)題的關(guān)系1、對(duì)稱形式的對(duì)偶關(guān)系（1）定義：若原問(wèn)題是

1/4/2023101二、原問(wèn)題和對(duì)偶問(wèn)題的關(guān)系（1）定義：若原問(wèn)題是12/29則定義其對(duì)偶問(wèn)題為

這兩個(gè)式子之間的變換關(guān)系稱為“對(duì)稱形式的對(duì)偶關(guān)系”。

1/4/2023102則定義其對(duì)偶問(wèn)題為這兩個(gè)式子之間的變換關(guān)系稱為“（2）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述（D）（L）

（3）怎樣從原始問(wèn)題寫(xiě)出其對(duì)偶問(wèn)題？

按照定義；記憶法則：“上、下”交換，“左、右”換位，不等式變號(hào)，“極大”變“極小”1/4/2023103（2）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述（D）（L）（3）怎樣例寫(xiě)出下面線性規(guī)劃的對(duì)偶問(wèn)題：

2、非對(duì)稱形式的對(duì)偶關(guān)系：1/4/2023104例寫(xiě)出下面線性規(guī)劃的對(duì)偶問(wèn)題：2、非對(duì)稱形式的對(duì)偶關(guān)系（1）原問(wèn)題對(duì)偶問(wèn)題（特點(diǎn)：對(duì)偶變量符號(hào)不限，系數(shù)陣轉(zhuǎn)置）(特點(diǎn)：等式約束)1/4/2023105（1）原問(wèn)題對(duì)（2）怎樣寫(xiě)出非對(duì)稱形式的對(duì)偶問(wèn)題？把一個(gè)等式約束寫(xiě)成兩個(gè)不等式約束，再根據(jù)對(duì)稱形式的對(duì)偶關(guān)系定義寫(xiě)出；按照原始-對(duì)偶表直接寫(xiě)出；（3）原始-對(duì)偶表1/4/2023106（2）怎樣寫(xiě)出非對(duì)稱形式的對(duì)偶問(wèn)題？12/29/202210

原問(wèn)題（或?qū)ε紗?wèn)題）

對(duì)偶問(wèn)題（或原問(wèn)題）

目標(biāo)函數(shù)MaxZ目標(biāo)函數(shù)MinW約束條件數(shù)：m個(gè)第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“=”

對(duì)偶變量數(shù)：m個(gè)第i個(gè)變量≥0第i個(gè)變量≤0第i個(gè)變量是自由變量

決策變量數(shù)：n個(gè)第j個(gè)變量≥0第j個(gè)變量≤0第j個(gè)變量是自由變量

約束條件數(shù)：n第i個(gè)約束條件類型為“≥”第i個(gè)約束條件類型為“≤”第i個(gè)約束條件類型為“=”

1/4/2023107原問(wèn)題（或?qū)ε紗?wèn)題）對(duì)偶問(wèn)題（或原問(wèn)題）目標(biāo)函數(shù)練習(xí)：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃：1/4/2023108練習(xí)：寫(xiě)出下面線性規(guī)劃的對(duì)偶規(guī)劃：12/29/2022108下面的答案哪一個(gè)是正確的？為什麼？

（原問(wèn)題是極小化問(wèn)題，因此應(yīng)從原始對(duì)偶表的右邊往左邊查！）√

×

1/4/2023109下面的答案哪一個(gè)是正確的？為什麼？（原問(wèn)題是極小化問(wèn)題，因第9章線性規(guī)劃方法及其應(yīng)用1/4/2023110第9章線性規(guī)劃方法及其應(yīng)用12/29/20221線性規(guī)劃（LinearProgramming）作為運(yùn)籌學(xué)的一個(gè)重要分支，是研究較早、理論較完善、應(yīng)用最廣泛的一個(gè)學(xué)科。它所研究的問(wèn)題主要包括兩個(gè)方面：一是在一項(xiàng)任務(wù)確定后，如何以最低成本（如人力、物力、資金和時(shí)間等）去完成這一任務(wù)；二是如何在現(xiàn)有資源條件下進(jìn)行組織和安排，以產(chǎn)生最大收益。因此，線性規(guī)劃是求一組變量的值，使它滿足一組線性式子，并使一個(gè)線性函數(shù)的值最大（或最小）的數(shù)學(xué)方法。線性規(guī)劃不僅僅是一種數(shù)學(xué)理論和方法，而且已成為現(xiàn)代管理工作中幫助管理者做出科學(xué)決策的重要手段。1/4/2023111線性規(guī)劃（LinearProgramming）作為運(yùn)籌學(xué)的

1、康托洛維奇生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法,一本小冊(cè)子，1939;2、康托洛維奇“最佳資源利用的經(jīng)濟(jì)計(jì)算”——1942完成、1959發(fā)表的著作；3、自1947年丹茲格（G.B.Dantzing）提出求解線性規(guī)劃問(wèn)題的一般方法--單純形法之后，線性規(guī)劃在理論上趨于成熟，應(yīng)用日益廣泛與深入；

隨著電子計(jì)算機(jī)的發(fā)展和計(jì)算速度的不斷提高，其適用的領(lǐng)域更加廣泛，它已成為必不可少的重要手段之一。1/4/20231121、康托洛維奇生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法,一

4、1975年庫(kù)伯曼斯(Koopmans)因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)；5、馮?諾伊曼和摩根斯坦1944年發(fā)表的

《對(duì)策論與經(jīng)濟(jì)行為》涉及與線性規(guī)劃等價(jià)的對(duì)策問(wèn)題及線性規(guī)劃對(duì)偶理論。1/4/20231134、1975年庫(kù)伯曼斯(Koopmans)因線性規(guī)劃方法是數(shù)學(xué)規(guī)劃中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分支。最優(yōu)化/運(yùn)籌學(xué)的最基本的方法之一，網(wǎng)絡(luò)規(guī)劃，整數(shù)規(guī)劃，目標(biāo)規(guī)劃和多目標(biāo)規(guī)劃都是以線性規(guī)劃為基礎(chǔ)的。解決稀缺資源最優(yōu)分配的有效方法，使付出的費(fèi)用最小或獲得的收益最大。線性規(guī)劃的基礎(chǔ)是線性變換。1/4/2023114線性規(guī)劃方法是數(shù)學(xué)規(guī)劃中發(fā)展較快、應(yīng)用較廣和比較成熟的一個(gè)分?jǐn)?shù)學(xué)規(guī)劃非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)科內(nèi)容多目標(biāo)規(guī)劃雙層規(guī)劃組合優(yōu)化最優(yōu)計(jì)數(shù)問(wèn)題網(wǎng)絡(luò)優(yōu)化排序問(wèn)題統(tǒng)籌圖隨機(jī)優(yōu)化對(duì)策論排隊(duì)論庫(kù)存論決策分析可靠性分析運(yùn)籌學(xué)的主要內(nèi)容1/4/2023115數(shù)非線性規(guī)劃整數(shù)規(guī)劃動(dòng)態(tài)規(guī)劃學(xué)多目標(biāo)規(guī)劃雙層規(guī)劃組最優(yōu)計(jì)數(shù)問(wèn)9.1線性規(guī)劃是什么9.2建立線性規(guī)劃模型的一般步驟9.3線性規(guī)劃問(wèn)題的圖解法9.4線性規(guī)劃問(wèn)題解的性質(zhì)9.5解線性規(guī)劃問(wèn)題的單純形法9.6線性規(guī)劃的應(yīng)用1/4/20231169.1線性規(guī)劃是什么12/29/202279.1線性規(guī)劃是什么1/4/20231179.1線性規(guī)劃是什么12/29/202289.1線性規(guī)劃是什么我們先通過(guò)幾個(gè)實(shí)際問(wèn)題來(lái)認(rèn)識(shí)什么是線性規(guī)劃.【例9.1】

某企業(yè)生產(chǎn)三種產(chǎn)品，這些產(chǎn)品分別需要甲、乙兩種原料.生產(chǎn)每種產(chǎn)品一噸所需原料和每天原料總限量及每噸不同產(chǎn)品可獲利潤(rùn)情況如表9.1所示.表9.1企業(yè)生產(chǎn)數(shù)據(jù)表1.利潤(rùn)最大化問(wèn)題1/4/20231189.1線性規(guī)劃是什么我們先通過(guò)幾個(gè)實(shí)際問(wèn)題來(lái)認(rèn)識(shí)什么是線9.1線性規(guī)劃是什么試問(wèn)：該企業(yè)怎樣安排生產(chǎn)才會(huì)使每天的利潤(rùn)最大？解設(shè)該企業(yè)每天生產(chǎn)產(chǎn)品的數(shù)量分別為（單位：噸），則總利潤(rùn)的表達(dá)式為我們希望在現(xiàn)有資源條件下總利潤(rùn)最大.現(xiàn)有資源的限制為（原料甲的限制）

（原料乙的限制）此外，由于未知數(shù)（我們稱之為決策變量）是計(jì)劃產(chǎn)量，應(yīng)有為非負(fù)的限制，即

1/4/20231199.1線性規(guī)劃是什么試問(wèn)：該企業(yè)怎樣安排生產(chǎn)才會(huì)使每天的9.1線性規(guī)劃是什么由此得到問(wèn)題的數(shù)學(xué)模型為其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

其中為英文“subjectto”的縮寫(xiě)，表示決策變量受它后面的條件約束.最優(yōu)解為（具體解法后面介紹），代入總利潤(rùn)的表達(dá)式得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日生產(chǎn)的最優(yōu)安排是：產(chǎn)品不生產(chǎn)，生產(chǎn)25噸，生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.

1/4/20231209.1線性規(guī)劃是什么由此得到問(wèn)題的數(shù)學(xué)模型為其中9.1線性規(guī)劃是什么類似于例9.1的這類問(wèn)題稱為最優(yōu)生產(chǎn)計(jì)劃問(wèn)題.其一般描述是利用種資源組織生產(chǎn)種產(chǎn)品.以表示資源的限制，表示產(chǎn)品的單位利潤(rùn)，表示單位產(chǎn)品消耗資源的數(shù)量（代表該企業(yè)當(dāng)前的技術(shù)水平），情況如表9.2所示.現(xiàn)在的問(wèn)題是：如果該企業(yè)生產(chǎn)的這種產(chǎn)品都可以賣出，如何合理充分地利用現(xiàn)有的資源，給出一個(gè)使總利潤(rùn)達(dá)到最大的產(chǎn)品生產(chǎn)計(jì)劃？1/4/20231219.1線性規(guī)劃是什么類似于例9.1的這類問(wèn)題稱為最優(yōu)生產(chǎn)有了解決上述問(wèn)題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的計(jì)劃產(chǎn)量分別為單位，則問(wèn)題的數(shù)學(xué)模型為9.1線性規(guī)劃是什么1/4/2023122有了解決上述問(wèn)題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的模型中的都是實(shí)際問(wèn)題給定的常數(shù)；未知量為決策變量.這類決策問(wèn)題的應(yīng)用領(lǐng)域非常廣泛.

注本章的數(shù)學(xué)模型均可用軟件求解。

2.成本最小化問(wèn)題【例9.2】某鋼鐵廠熔煉一種新型不銹鋼，需要4種合金為原料經(jīng)測(cè)定這4種原料關(guān)于元素鉻（Cr）、錳（Mn）和鎳（Ni）的質(zhì)量分?jǐn)?shù)（%）、單價(jià)以及這種新型不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)，情況如表9.3所示.假設(shè)熔煉時(shí)質(zhì)量沒(méi)有損耗，問(wèn)：要熔煉100噸這樣的不銹鋼，應(yīng)選用原料各多少噸，能夠使成本最?。?.1線性規(guī)劃是什么1/4/2023123模型中9.1線性規(guī)劃是什么下料問(wèn)題的一般描述：已知有一批原材料，每根長(zhǎng)度為L(zhǎng)，由于生產(chǎn)的需要，要求截出規(guī)格分別為的零件根.問(wèn)：如何截取使得總用料最省？即要求制定一個(gè)既能滿足生產(chǎn)的需要，又使得使用的原材料數(shù)量最少的下料方案.同樣可以仿照例9.4的建模過(guò)程列出此一般問(wèn)題的數(shù)學(xué)模型.總之，類似例9.1、9.2的實(shí)際問(wèn)題很多，而且形式多種多樣.通過(guò)這些問(wèn)題，我們可以看到上述各種問(wèn)題的共同點(diǎn)，即每一個(gè)問(wèn)題都用一組決策變量來(lái)表示某一方案，追求的目標(biāo)可以用關(guān)于決策變量的線性函數(shù)刻畫(huà)，或是最大化或是最小化，而要達(dá)到目標(biāo)的條件又都有一定的限制，每個(gè)限制條件均可由關(guān)于決策變量的線性等式或不等式表示.

1/4/20231249.1線性規(guī)劃是什么下料問(wèn)題的一般描述：已知有一批原材料9.1線性規(guī)劃是什么這類問(wèn)題所構(gòu)成的數(shù)學(xué)模型,稱為線性規(guī)劃模型.有時(shí)也直接將線性規(guī)劃模型稱為線性規(guī)劃問(wèn)題.針對(duì)這類模型,可以用根據(jù)數(shù)學(xué)理論設(shè)計(jì)的計(jì)算機(jī)軟件，如軟件求解，得出實(shí)際問(wèn)題需要的答案。1/4/20231259.1線性規(guī)劃是什么這類問(wèn)題所構(gòu)成的數(shù)學(xué)模型,稱為線性規(guī)9.2建立線性規(guī)劃模型的一般步驟1/4/20231269.2建立線性規(guī)劃模型的12/29/2022179.2建立線性規(guī)劃模型的一般步驟從§9.1節(jié)中對(duì)實(shí)際問(wèn)題建立數(shù)學(xué)模型的過(guò)程，可以得到一般線性規(guī)劃問(wèn)題建模過(guò)程如下：第1步理解要解決的問(wèn)題.搞清在什么條件下追求什么目標(biāo).第2步定義決策變量.每一個(gè)問(wèn)題都用一組決策變量來(lái)表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的.第3步確定約束條件.用一組決策變量的線性等式或不等式來(lái)表示在解決問(wèn)題過(guò)程中所必須遵循的約束條件.第4步列出目標(biāo)函數(shù).按實(shí)際問(wèn)題的不同，用決策變量的線性函數(shù)最大化或最小化形式寫(xiě)出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù).1/4/20231279.2建立線性規(guī)劃模型的一般步驟從§9.1節(jié)中對(duì)實(shí)際問(wèn)題9.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)劃問(wèn)題，為了便于建立其數(shù)學(xué)模型，常需要把反映問(wèn)題的背景數(shù)據(jù)資料用表格形式歸類綜合，以揭示各個(gè)量之間的內(nèi)在聯(lián)系.線性規(guī)劃的一般形式可表示為：1/4/20231289.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)9.2建立線性規(guī)劃模型的一般步驟其中稱為目標(biāo)函數(shù)，為決策變量，為約束常數(shù)，后面的式子為約束條件.這里的為常數(shù).當(dāng)要求決策變量均為整數(shù)時(shí)，稱（9.1）為純整數(shù)線性規(guī)劃問(wèn)題；當(dāng)要求決策變量均取0或1時(shí)，稱（9.1）為整數(shù)線性規(guī)劃問(wèn)題.當(dāng)要求決策變量既取實(shí)數(shù)又取整數(shù)時(shí)，稱（9.1）為混合整數(shù)線性規(guī)劃問(wèn)題.我們把滿足所有約束條件的解稱為線性規(guī)劃問(wèn)題（9.1）的可行解.全體可行解的集合稱為問(wèn)題（9.1）的可行域,記為.使目標(biāo)函數(shù)值最大（或最?。┑目尚薪夥Q為該線性1/4/20231299.2建立線性規(guī)劃模型的一般步驟其中稱9.2建立線性規(guī)劃模型的一般步驟規(guī)劃問(wèn)題的最優(yōu)解，與此最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡(jiǎn)稱最優(yōu)值.因此，若記，求解線性規(guī)劃問(wèn)題（9.1），本質(zhì)上就是尋找一點(diǎn)，使得均滿足不等式【例9.3】某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備（臺(tái)時(shí)），A、B兩種原材料的消耗以及資源的限制情況如表2.11所示.問(wèn)：該工廠應(yīng)分別生產(chǎn)多少甲產(chǎn)品和乙產(chǎn)品才能使工廠獲利最大？1/4/20231309.2建立線性規(guī)劃模型的一般步驟規(guī)劃問(wèn)題的最優(yōu)解，與9.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量.工廠目前要決策的是甲產(chǎn)品和乙產(chǎn)品的生產(chǎn)量，可以分別用變量來(lái)表示.由于它們表示產(chǎn)品產(chǎn)量，所以只取非負(fù)數(shù).其次，根據(jù)問(wèn)題的限制條件，列出表示約束條件的線性不等式：1/4/20231319.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量9.2建立線性規(guī)劃模型的一般步驟，（非負(fù)限制）

，（臺(tái)時(shí)數(shù)限制）

，（原材料限制）

，（原材料限制）最后，根據(jù)實(shí)際問(wèn)題所追求的目標(biāo)，列出其線性函數(shù)表達(dá)式.由于問(wèn)題的目標(biāo)是工廠獲利最大，假如產(chǎn)品都能銷售，則總利潤(rùn)可表示為，最大利潤(rùn)記為1/4/20231329.2建立線性規(guī)劃模型的一般步驟，（非負(fù)限制），（臺(tái)時(shí)9.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該問(wèn)題的線性規(guī)劃模型：1/4/20231339.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該計(jì)算最優(yōu)解為：即在現(xiàn)有資源條件下，該企業(yè)在計(jì)劃期內(nèi)生產(chǎn)的最優(yōu)計(jì)劃是：產(chǎn)品甲生產(chǎn)100單位，產(chǎn)品乙生產(chǎn)200單位，可實(shí)現(xiàn)最大利潤(rùn)130000元.9.2建立線性規(guī)劃模型的一般步驟1/4/2023134計(jì)算最優(yōu)解為：9.2建立線性規(guī)劃模型的一般步驟12/299.2建立線性規(guī)劃模型的一般步驟

【例9.4】某醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí).不同時(shí)段需要的護(hù)士人數(shù)不等.據(jù)統(tǒng)計(jì)，各時(shí)段所需護(hù)士的最少人數(shù)如表2.9所示.如何安排才能做到安排最少的護(hù)士就能滿足工作的需要？1/4/20231359.2建立線性規(guī)劃模型的一般步驟【例9.4】某醫(yī)院9.2建立線性規(guī)劃模型的一般步驟解設(shè)為時(shí)段開(kāi)始上班的人數(shù)，.目標(biāo)是要求護(hù)士的總數(shù)最少.因?yàn)槊總€(gè)護(hù)士都工作8小時(shí)，即連續(xù)工作2個(gè)時(shí)段后休息，所以問(wèn)題的線性規(guī)劃模型為：1/4/20231369.2建立線性規(guī)劃模型的一般步驟解設(shè)為時(shí)段開(kāi)9.2建立線性規(guī)劃模型的一般步驟計(jì)算最優(yōu)