運(yùn)籌學(xué)思想方法及應(yīng)用 ch2 線性規(guī)劃及其應(yīng)用

2023/2/51第二章線性規(guī)劃及其應(yīng)用運(yùn)籌學(xué)Operational

Research2023/2/52第二章線性規(guī)劃及其應(yīng)用線性規(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é)決策的重要手段.2023/2/532.1線性規(guī)劃是什么2.2建立線性規(guī)劃模型的一般步驟2.3線性規(guī)劃問(wèn)題的圖解法2.4線性規(guī)劃問(wèn)題解的性質(zhì)2.5解線性規(guī)劃問(wèn)題的單純形法2.6線性規(guī)劃的應(yīng)用2.7WinQSB軟件應(yīng)用第二章線性規(guī)劃及其應(yīng)用2023/2/542.1線性規(guī)劃是什么2023/2/552.1線性規(guī)劃是什么我們先通過(guò)幾個(gè)實(shí)際問(wèn)題來(lái)認(rèn)識(shí)什么是線性規(guī)劃.【例2.1】

某企業(yè)生產(chǎn)三種產(chǎn)品，這些產(chǎn)品分別需要甲、乙兩種原料.生產(chǎn)每種產(chǎn)品一噸所需原料和每天原料總限量及每噸不同產(chǎn)品可獲利潤(rùn)情況如表2.1所示.

表2.1企業(yè)生產(chǎn)數(shù)據(jù)表1.利潤(rùn)最大化問(wèn)題2023/2/562.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ù)的限制，即

2023/2/572.1線性規(guī)劃是什么由此得到問(wèn)題的數(shù)學(xué)模型為其中為英文“subjectto”的縮寫，表示決策變量受它后面的條件約束.最優(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”的縮寫，表示決策變量受它后面的條件約束.最優(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”的縮寫，表示決策變量受它后面的條件約束.最優(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”的縮寫，表示決策變量受它后面的條件約束.最優(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”的縮寫，表示決策變量受它后面的條件約束.最優(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千元/日.

2023/2/582.1線性規(guī)劃是什么類似于例2.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ù)水平），情況如表2.2所示.現(xiàn)在的問(wèn)題是：如果該企業(yè)生產(chǎn)的這種產(chǎn)品都可以賣出，如何合理充分地利用現(xiàn)有的資源，給出一個(gè)使總利潤(rùn)達(dá)到最大的產(chǎn)品生產(chǎn)計(jì)劃？2023/2/59有了解決上述問(wèn)題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的計(jì)劃產(chǎn)量分別為單位，則問(wèn)題的數(shù)學(xué)模型為2.1線性規(guī)劃是什么2023/2/510模型中的都是實(shí)際問(wèn)題給定的常數(shù)；未知量為決策變量.這類決策問(wèn)題的應(yīng)用領(lǐng)域非常廣泛.

注本章的數(shù)學(xué)模型均可用軟件求解，具體使用方法見(jiàn)本章的§2.7.

2.成本最小化問(wèn)題【例2.2】

某鋼鐵廠熔煉一種新型不銹鋼，需要4種合金為原料經(jīng)測(cè)定這4種原料關(guān)于元素鉻（Cr）、錳（Mn）和鎳（Ni）的質(zhì)量分?jǐn)?shù)（%）、單價(jià)以及這種新型不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)，情況如表2.3所示.假設(shè)熔煉時(shí)質(zhì)量沒(méi)有損耗，問(wèn)：要熔煉100噸這樣的不銹鋼，應(yīng)選用原料各多少噸，能夠使成本最??？2.1線性規(guī)劃是什么2023/2/5112.1線性規(guī)劃是什么

表2.3生產(chǎn)某種不銹鋼的相關(guān)數(shù)據(jù)表2023/2/5122.1線性規(guī)劃是什么解設(shè)選用原料的量分別為（單位：噸）.由于追求的目標(biāo)是成本最小，故有最小成本表達(dá)式：

以下分析約束條件.由于假設(shè)熔煉時(shí)質(zhì)量沒(méi)有損耗，熔煉該種不銹鋼100噸，它由原料熔煉而成，故有等式約束

又因該不銹鋼所需鉻、錳和鎳的最低質(zhì)量分?jǐn)?shù)是由4種合金對(duì)相應(yīng)元素的質(zhì)量分?jǐn)?shù)構(gòu)成，注意到要熔煉該種不銹鋼100噸，于是得到鉻、錳和鎳的質(zhì)量分?jǐn)?shù)滿足的不等式依次為2023/2/5132.1線性規(guī)劃是什么此外，各種合金的加入量以整噸為單位，即有限制且為整數(shù).綜合上述討論，我們得到該問(wèn)題的數(shù)學(xué)模型為2023/2/5142.1線性規(guī)劃是什么易求得此模型的解為.也就是說(shuō)，選用原料依次為27，32，41，0噸時(shí)，達(dá)到最低成本957.1萬(wàn)元.例2.2的這類問(wèn)題也稱為混合配料問(wèn)題.其一般描述是：把n種不同的原料配制成含有m種成分的一種產(chǎn)品，生產(chǎn)數(shù)量為.經(jīng)測(cè)定這n種原料關(guān)于m種成分的質(zhì)量分?jǐn)?shù)（%）、單價(jià)以及這種產(chǎn)品所需m種成分的最低質(zhì)量分?jǐn)?shù)（%）如表2.4所示.假設(shè)產(chǎn)品配制時(shí)重量沒(méi)有損耗，問(wèn)：要生產(chǎn)數(shù)量為的這種產(chǎn)品，應(yīng)選用原料各多少能夠使成本最??？2023/2/5152.1線性規(guī)劃是什么2023/2/5162.1線性規(guī)劃是什么類似于例2.2，設(shè)選用原料的數(shù)量依次為，則得到此問(wèn)題的數(shù)學(xué)模型為2023/2/5172.1線性規(guī)劃是什么這類決策問(wèn)題的應(yīng)用領(lǐng)域同樣是非常廣泛的.再進(jìn)一步抽象，就可以將其歸納為一類決策問(wèn)題：當(dāng)某個(gè)任務(wù)確定之后，如何統(tǒng)籌安排，盡量用最少的資金、人力、物力等資源去完成該項(xiàng)任務(wù).3.運(yùn)輸問(wèn)題【例2.3】某建材公司有三個(gè)水泥廠，四個(gè)銷地，其產(chǎn)量、銷量、運(yùn)費(fèi)見(jiàn)表2.5.2023/2/5182.1線性規(guī)劃是什么如何制定調(diào)運(yùn)方案，使總的運(yùn)費(fèi)或總貨運(yùn)量最??？

解設(shè)由水泥廠運(yùn)到銷地的貨運(yùn)量為，則得到問(wèn)題的數(shù)學(xué)模型為2023/2/5192.1線性規(guī)劃是什么其解為.最佳運(yùn)輸方案見(jiàn)表2.6.2023/2/5202.1線性規(guī)劃是什么運(yùn)輸問(wèn)題的一般描述：將個(gè)產(chǎn)地生產(chǎn)的一種產(chǎn)品運(yùn)到個(gè)銷地，表示產(chǎn)地的產(chǎn)量限制，表示銷地的銷量需求，表示單位產(chǎn)品從運(yùn)到的運(yùn)費(fèi).情況如表2.7所示.問(wèn)題是：制定一個(gè)使總的運(yùn)費(fèi)或總貨運(yùn)量最小的調(diào)運(yùn)方案.2023/2/5212.1線性規(guī)劃是什么設(shè)由產(chǎn)地運(yùn)到銷地的貨運(yùn)量為，則得到此運(yùn)輸問(wèn)題的數(shù)學(xué)模型為2023/2/5222.1線性規(guī)劃是什么4.

合理下料問(wèn)題【例2.4】

現(xiàn)有一批長(zhǎng)度一定的鋼管，由于生產(chǎn)的需要，要求截出若干不同規(guī)格的鋼管.試問(wèn)：要如何截取原材料，既能滿足生產(chǎn)的需要，又使得使用的原材料鋼管數(shù)量最少或廢材最少？具體數(shù)據(jù)：原材料鋼管長(zhǎng)7.4m，截成2.9m,2.1m,1.5m各為1000根，2000根，1000根.

解把所有可能的下料方式、按照各種下料方式從長(zhǎng)7.4m的原料上得到的不同規(guī)格鋼管的根數(shù)、殘料長(zhǎng)度，以及需要量列于表2.8中.例如，按照下料方式，可以得到2.9m鋼管2根,1.5m鋼管1根.問(wèn)題轉(zhuǎn)化為確定每種下料方式各用多少根7.4m的原料，可使被使用的原料根數(shù)最少.2023/2/5232.1線性規(guī)劃是什么設(shè)分別為按照方式下料的原料根數(shù)，則得到問(wèn)題的數(shù)學(xué)模型為2023/2/5242.1線性規(guī)劃是什么其解為

根.即最佳下料方案為：方式：200根；方式：800根；方式：200根；其他方式為0根.2023/2/5252.1線性規(guī)劃是什么下料問(wèn)題的一般描述：已知有一批原材料，每根長(zhǎng)度為L(zhǎng)，由于生產(chǎn)的需要，要求截出規(guī)格分別為的零件根.問(wèn)：如何截取使得總用料最??？即要求制定一個(gè)既能滿足生產(chǎn)的需要，又使得使用的原材料數(shù)量最少的下料方案.同樣可以仿照例2.4的建模過(guò)程列出此一般問(wèn)題的數(shù)學(xué)模型.總之，類似于例2.1—2.4的實(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)于決策變量的線性等式或不等式表示.

2023/2/5262.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)題需要的答案.2023/2/5272.1線性規(guī)劃是什么本節(jié)學(xué)習(xí)要點(diǎn)1.通過(guò)實(shí)例，了解什么是線性規(guī)劃，了解線性規(guī)劃在管理中的幾類應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征2023/2/5282.2建立線性規(guī)劃模型的一般步驟2023/2/5292.2建立線性規(guī)劃模型的一般步驟從§2.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ù)最大化或最小化形式寫出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù).2023/2/5302.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)劃問(wèn)題，為了便于建立其數(shù)學(xué)模型，常需要把反映問(wèn)題的背景數(shù)據(jù)資料用表格形式歸類綜合，以揭示各個(gè)量之間的內(nèi)在聯(lián)系.線性規(guī)劃的一般形式可表示為：2023/2/5312.2建立線性規(guī)劃模型的一般步驟其中稱為目標(biāo)函數(shù)，為決策變量，為約束常數(shù)，后面的式子為約束條件.這里的為常數(shù).當(dāng)要求決策變量均為整數(shù)時(shí)，稱（2.1）為純整數(shù)線性規(guī)劃問(wèn)題；當(dāng)要求決策變量均取0或1時(shí)，稱（2.1）為整數(shù)線性規(guī)劃問(wèn)題.當(dāng)要求決策變量既取實(shí)數(shù)又取整數(shù)時(shí)，稱（2.1）為混合整數(shù)線性規(guī)劃問(wèn)題.我們把滿足所有約束條件的解稱為線性規(guī)劃問(wèn)題（2.1）的可行解.全體可行解的集合稱為問(wèn)題（2.1）的可行域,記為.使目標(biāo)函數(shù)值最大（或最?。┑目尚薪夥Q為該線性2023/2/5322.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)題（2.1），本質(zhì)上就是尋找一點(diǎn)，使得均滿足不等式【例2.5】

某工廠在計(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)品才能使工廠獲利最大？2023/2/5332.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量.工廠目前要決策的是甲產(chǎn)品和乙產(chǎn)品的生產(chǎn)量，可以分別用變量來(lái)表示.由于它們表示產(chǎn)品產(chǎn)量，所以只取非負(fù)數(shù).其次，根據(jù)問(wèn)題的限制條件，列出表示約束條件的線性不等式：2023/2/5342.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)記為2023/2/5352.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該問(wèn)題的線性規(guī)劃模型：計(jì)算最優(yōu)解為：元.即在現(xiàn)有資源條件下，該企業(yè)在計(jì)劃期內(nèi)生產(chǎn)的最優(yōu)計(jì)劃是：2023/2/5362.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元.2023/2/5372.2建立線性規(guī)劃模型的一般步驟

【例2.6】

某醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí).不同時(shí)段需要的護(hù)士人數(shù)不等.據(jù)統(tǒng)計(jì)，各時(shí)段所需護(hù)士的最少人數(shù)如表2.9所示.如何安排才能做到安排最少的護(hù)士就能滿足工作的需要？2023/2/5382.2建立線性規(guī)劃模型的一般步驟解設(shè)為時(shí)段開(kāi)始上班的人數(shù)，.目標(biāo)是要求護(hù)士的總數(shù)最少.因?yàn)槊總€(gè)護(hù)士都工作8小時(shí)，即連續(xù)工作2個(gè)時(shí)段后休息，所以問(wèn)題的線性規(guī)劃模型為：2023/2/5392.2建立線性規(guī)劃模型的一般步驟計(jì)算最優(yōu)解為： 故該醫(yī)院需雇用150名護(hù)士，最佳安排見(jiàn)表2.10所示.2023/2/5402.2建立線性規(guī)劃模型的一般步驟本節(jié)學(xué)習(xí)要點(diǎn)線性規(guī)劃的一般形式，可行解、最優(yōu)解等概念線性規(guī)劃問(wèn)題建模過(guò)程：第1步理解要解決的問(wèn)題.

第2步定義決策變量.

第3步確定約束條件.

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

2023/2/5412.3線性規(guī)劃問(wèn)題的圖解法2023/2/5422.3線性規(guī)劃問(wèn)題的圖解法1.圖解法

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

圖解法的步驟可概括為：（1）在平面上建立直角坐標(biāo)系；（2）圖示約束條件，找出可行域（由于，可行域必位于第一象限）；

2023/2/5432.3線性規(guī)劃問(wèn)題的圖解法圖解法的步驟可概括為：（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ō)明.

2023/2/5442.3線性規(guī)劃問(wèn)題的圖解法

以下結(jié)合實(shí)例來(lái)具體說(shuō)明.

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

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

最后求解線性方程組

求解得到點(diǎn)的坐標(biāo)，從而得到最優(yōu)解，最大值2023/2/5462.3線性規(guī)劃問(wèn)題的圖解法2023/2/5472.3線性規(guī)劃問(wèn)題的圖解法【例2.8】用圖解法求解線性規(guī)劃問(wèn)題解先畫(huà)出線性規(guī)劃的可行域，如圖2.2陰影部分.

2023/2/5482.3線性規(guī)劃問(wèn)題的圖解法2023/2/5492.3線性規(guī)劃問(wèn)題的圖解法再畫(huà)出目標(biāo)函數(shù)等值線，朝著增大縱截距的方向平行移動(dòng)等值線至點(diǎn)B.最后求解線性方程組

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

例2.7與例2.8中求解得到的問(wèn)題的最優(yōu)解是惟一的，但對(duì)一般線性規(guī)劃問(wèn)題，求解結(jié)果還可能出現(xiàn)其他情況.2023/2/5502.3線性規(guī)劃問(wèn)題的圖解法2.線性規(guī)劃解的其他情況（1）多重最優(yōu)解的情況

【例2.9】

若將例2.7中的目標(biāo)函數(shù)變?yōu)?，則代表目標(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)著相同的最大值2023/2/5512.3線性規(guī)劃問(wèn)題的圖解法（2）無(wú)界解的情況

【例2.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ú)界.2023/2/5522.3線性規(guī)劃問(wèn)題的圖解法（3）無(wú)可行解的情況

【例2.11】

對(duì)線性規(guī)劃問(wèn)題由圖2.3(b)可以看出，同時(shí)滿足所有約束條件的點(diǎn)不存在，即可行域?yàn)榭占?，也就是沒(méi)有可行解，故不存在最優(yōu)解.2023/2/5532.3線性規(guī)劃問(wèn)題的圖解法2023/2/5542.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)題.【例2.12】

求解線性規(guī)劃2023/2/5552.3線性規(guī)劃問(wèn)題的圖解法解畫(huà)出此線性規(guī)劃問(wèn)題的可行域，如圖2.4中的陰影部分.目標(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)解，且.2023/2/5562.3線性規(guī)劃問(wèn)題的圖解法2023/2/5572.3線性規(guī)劃問(wèn)題的圖解法本節(jié)學(xué)習(xí)要點(diǎn)1.通過(guò)圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn)

(1)可行解區(qū)域要畫(huà)正確

(2)目標(biāo)函數(shù)增加的方向不能畫(huà)錯(cuò)

(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)2023/2/5582.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/5591.線性規(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)形式.2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/560這里的標(biāo)準(zhǔn)形式有以下規(guī)定：（1）目標(biāo)函數(shù)是求最大值；（2）所有約束條件均用等式表示；（3）所有決策變量均取非負(fù)數(shù)；（4）所有約束常數(shù)均為非負(fù)數(shù).2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/561

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

其中常數(shù)非負(fù).一般可以通過(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ù).2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/563（2）約束條件的標(biāo)準(zhǔn)化當(dāng)約束條件為≤形式的不等式時(shí)，可在不等式左邊加上一個(gè)非負(fù)的新變量（稱為松弛變量），把不等號(hào)變?yōu)榈忍?hào)；當(dāng)約束條件為≥形式的不等式時(shí)，可在不等式左邊減去一個(gè)非負(fù)的新變量（稱為剩余變量），把不等號(hào)變?yōu)榈忍?hào).2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/564（3）決策變量的標(biāo)準(zhǔn)化如果某一決策變量是一個(gè)符號(hào)不受限制的“自由變量”，可以引入兩個(gè)非負(fù)的新變量和，并作變換，將決策變量標(biāo)準(zhǔn)化..2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/565（4）約束常數(shù)的標(biāo)準(zhǔn)化如果有某約束常數(shù)為負(fù)數(shù)，可在等式（或不等式）兩邊同時(shí)乘以，把約束常數(shù)變?yōu)檎龜?shù).2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/566【例2.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)為零.2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/5672.4線性規(guī)劃問(wèn)題解的性質(zhì)【例2.14】將下面線性規(guī)劃問(wèn)題化為標(biāo)準(zhǔn)形【解】令，把求改為求；用替換，其中；在第1個(gè)約束不等式的左邊加入松弛變量，在第2個(gè)約束不等式的左邊減去剩余變量，這樣即可得到該問(wèn)題的標(biāo)準(zhǔn)形為2023/2/568，

2.4線性規(guī)劃問(wèn)題解的性質(zhì)標(biāo)準(zhǔn)形原問(wèn)題2023/2/569【定義2.1】如果集合K中任意兩點(diǎn)s,t之間連線上所有的點(diǎn)都是集合K中的點(diǎn)，即對(duì)于任意的，都有，則稱K為凸集.例如圖2.5中（a）,（b）,（c）為凸集，而（d）,（e）不是凸集.

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

圖2.5凸集與非凸集示例2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/570【定義2.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è)重要定理.2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/571【定理2.1

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

】若可行域非空有界，則線性規(guī)劃問(wèn)題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到.2.4線性規(guī)劃問(wèn)題解的性質(zhì)2023/2/5722.4線性規(guī)劃問(wèn)題解的性質(zhì)本節(jié)學(xué)習(xí)要點(diǎn)1.將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形的方法

2.線性規(guī)劃問(wèn)題解的性質(zhì)（1）線性規(guī)劃問(wèn)題的可行域是一個(gè)凸集.

（2）若可行域非空有界，則線性規(guī)劃問(wèn)題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到.2023/2/5732.5解線性規(guī)劃問(wèn)題的單純形法

2023/2/574

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

2023/2/578（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)為,2.5解線性規(guī)劃問(wèn)題的單純形法2023/2/579的第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，

2.5解線性規(guī)劃問(wèn)題的單純形法2023/2/580過(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.2.5解線性規(guī)劃問(wèn)題的單純形法再將矩陣的第2行乘以（2）加到第1行，第2行乘以7加到第3行，得2023/2/581上述求解線性規(guī)劃問(wèn)題的方法稱為單純形法.單純形法步驟如下：第1步，將線性規(guī)劃化成標(biāo)準(zhǔn)形；第2步，寫出初始單純形表；第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)單純形表直接寫出最優(yōu)解和最優(yōu)值.2.5解線性規(guī)劃問(wèn)題的單純形法2023/2/582從上例求解過(guò)程看到，單純形表中所對(duì)應(yīng)的列始終不變，故在實(shí)際計(jì)算中可省去不寫.上例的求解過(guò)程本質(zhì)上是矩陣的初等行變換過(guò)程，我們可以把此例的單純形法求解過(guò)程簡(jiǎn)化為2.5解線性規(guī)劃問(wèn)題的單純形法2023/2/5832.5解線性規(guī)劃問(wèn)題的單純形法所以最優(yōu)解及最優(yōu)值分別為【注1】若在計(jì)算過(guò)程中，單純形表出現(xiàn)某檢驗(yàn)數(shù)為負(fù)，但其所在的列無(wú)正元素的情況，則可以證明該問(wèn)題無(wú)最優(yōu)解.

2023/2/584【解】引入松弛變量，化為標(biāo)準(zhǔn)形

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

解線性規(guī)劃問(wèn)題

2023/2/5852.5解線性規(guī)劃問(wèn)題的單純形法初始單純形表為由于檢驗(yàn)數(shù)1所在列無(wú)正數(shù)元素，故此問(wèn)題無(wú)最優(yōu)解.2023/2/586【注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ì)偶單純形法.2.5解線性規(guī)劃問(wèn)題的單純形法2023/2/5872.5解線性規(guī)劃問(wèn)題的單純形法本節(jié)學(xué)習(xí)要點(diǎ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ù)所在列中所有元素小或等于0，則線性規(guī)劃具有無(wú)界解2023/2/5882.6線性規(guī)劃的應(yīng)用2023/2/5892.6線性規(guī)劃的應(yīng)用

線性規(guī)劃在國(guó)內(nèi)外很多部門的規(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ī)劃模型的基本思路和基本技巧.2023/2/5901.辦學(xué)規(guī)模問(wèn)題【例2.16】某人準(zhǔn)備投資1200萬(wàn)元辦一所中學(xué)，為了考慮社會(huì)效益和經(jīng)濟(jì)效益，對(duì)該地區(qū)教育市場(chǎng)進(jìn)行調(diào)查，得出一組數(shù)據(jù)，如表2.12所示.表2.12市場(chǎng)調(diào)查表班級(jí)班級(jí)學(xué)生數(shù)配備教師數(shù)硬件建設(shè)費(fèi)（萬(wàn)元）教師年薪（萬(wàn)元）初中502.0281.2高中402.5581.6根據(jù)物價(jià)部門的有關(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ò)多少年可以收回全部投資？2.6線性規(guī)劃的應(yīng)用2023/2/591即.于是此問(wèn)題的線性規(guī)劃模型為解得最優(yōu)解代入中得2.6線性規(guī)劃的應(yīng)用解設(shè)初中編制班數(shù)為x,高中編制班數(shù)為y,又設(shè)年利潤(rùn)為f,（單位：萬(wàn)元），那么2023/2/592故學(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年可以收回全部投資.2.6線性規(guī)劃的應(yīng)用2023/2/5932.投資問(wèn)題【例2.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年底，投資的本利之和最大？2.6線性規(guī)劃的應(yīng)用2023/2/594【解】這是一個(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)列表2.13.表2.13投資項(xiàng)目投資機(jī)會(huì)項(xiàng)目名稱

第1年年初第2年年初第3年年初ABCD2.6線性規(guī)劃的應(yīng)用2023/2/595下面分析每年資金的使用情況并建立線性規(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年的投資，，而且要求

2.6線性規(guī)劃的應(yīng)用于是；；2023/2/5962.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年底獲得的本利和為

;2023/2/597將上述目標(biāo)函數(shù)和約束條件整理后即可得出該問(wèn)題完整的線性規(guī)劃模型:求解得到最優(yōu)投資方案如表2.14所示，且在第3年底收回投資的本利和最大為11.528萬(wàn)元.2.6線性規(guī)劃的應(yīng)用2023/2/598表2.14最優(yōu)投資方案

投資機(jī)會(huì)

項(xiàng)目名稱

第1年年初第2年年初第3年年初AX11=1X12=1.2X13=7.44BX21=5CX32=0DX43=22.6線性規(guī)劃的應(yīng)用2023/2/599配套生產(chǎn)計(jì)劃問(wèn)題【例2.18】某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問(wèn)題.該公司生產(chǎn)甲、乙、丙3種產(chǎn)品，這3種產(chǎn)品都要經(jīng)過(guò)鑄造、機(jī)加工和裝配3個(gè)車間.甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量.有關(guān)情況見(jiàn)表2.15.該公司中可利用的總工時(shí)為：鑄造8000小時(shí)、機(jī)加工12000小時(shí)和裝配10000小時(shí).為使該公司獲得最大利潤(rùn)，甲、乙、丙3種產(chǎn)品應(yīng)各生產(chǎn)多少件？甲、乙兩種產(chǎn)品由本公司鑄造多少件？外包協(xié)作鑄造多少件？2.6線性規(guī)劃的應(yīng)用2023/2/5100表2.15某公司工時(shí)與成本數(shù)據(jù)表

產(chǎn)品工時(shí)與成本甲乙丙每件鑄造工時(shí)（小時(shí)）5107每件機(jī)加工工時(shí)（小時(shí)）648每件裝配工時(shí)（小時(shí)）322自產(chǎn)鑄件每件成（元）354外協(xié)鑄件每件成（元）56—機(jī)加工每件成本（元）213裝配每件成本（元）322每件產(chǎn)品售價(jià)（元）2318162.6線性規(guī)劃的應(yīng)用2023/2/5101【解】設(shè)x1,x2,x3分別為3道工序都由該公司加工的甲、乙、丙3種產(chǎn)品的件數(shù)，設(shè)

x4,x5,分別為由外協(xié)鑄造再由該公司加工、裝配的甲、乙兩種產(chǎn)品的件數(shù).每件產(chǎn)品的利潤(rùn)分別如下：每件產(chǎn)品甲全部自制的利潤(rùn)=23-(3+2+3)=15(元)；每件產(chǎn)品甲由外協(xié)鑄造，其余自制的利潤(rùn)=23-(5+2+3)(元)；每件產(chǎn)品乙全部自制的利潤(rùn)=18-(5+1+2)=10(元)；每件產(chǎn)品乙由外協(xié)鑄造，其余自制的利潤(rùn)18-(6+1+2)=9(元)；每件產(chǎn)品丙的利潤(rùn)=16-(4+3+2)=7(元).

2.6線性規(guī)劃的應(yīng)用2023/2/5102建立此問(wèn)題的線性規(guī)劃模型如下：（鑄造工時(shí)約束）（機(jī)加工工時(shí)約束）

（裝配工時(shí)約束）（非負(fù)約束）經(jīng)計(jì)算得結(jié)果：

故最優(yōu)計(jì)劃為：產(chǎn)品甲生產(chǎn)1600件，全部由該公司鑄造；產(chǎn)品乙生產(chǎn)600件，由外協(xié)鑄造后再由該公司加工、裝配；產(chǎn)品丙不生產(chǎn).2.6線性規(guī)劃的應(yīng)用2023/2/51034.人力資源分配問(wèn)題【例2.19】某百貨商場(chǎng)售貨員的需求經(jīng)過(guò)統(tǒng)計(jì)分析如表2.16所示.為了保證售貨員充分休息，售貨員每周工作5天，休息2天，并要求休息的2天是連續(xù)的，問(wèn)：應(yīng)該如何安排售貨員的作息時(shí)間，既滿足工作需要，又使配備的售貨員人數(shù)最少？表2.16售貨人員需求統(tǒng)計(jì)表時(shí)間所需售貨員人數(shù)星期日28星期一15星期二24星期三25星期四19星期五31星期六282.6線性規(guī)劃的應(yīng)用2023/2/5104【解】

設(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ù)寫出約束條件.例如星期日需要28人，商場(chǎng)中的全體售貨員中除了星期六和星期日開(kāi)始休息的人外都應(yīng)該上班，即有約束條件2.6線性規(guī)劃的應(yīng)用2023/2/5105同理有因xj

（j=1,2,…，７）表示人數(shù)，故有

xj

≥０j=1,2,…，７），且為整數(shù)2.6線性規(guī)劃的應(yīng)用綜上得問(wèn)題的線性規(guī)劃模型為：2023/2/51062.6線性規(guī)劃的應(yīng)用計(jì)算結(jié)果：也就是說(shuō)該商場(chǎng)至少需要售貨員36人.他們的的休息安排為：星期一12人；星期三11人；星期五5人；星期日8人.2023/2/51075.應(yīng)用案例【例2.20】剎車用的氣泵年度生產(chǎn)計(jì)劃.（1）問(wèn)題描述某廠生產(chǎn)剎車用的氣泵，產(chǎn)品類型有“東風(fēng)1”、“東風(fēng)2”、“東風(fēng)3”、“東風(fēng)4”、“東風(fēng)5”、“東風(fēng)6”及其配件，其中“東風(fēng)4”、“東風(fēng)5”、“東風(fēng)6”3種型號(hào)是新產(chǎn)品.尚未大量生產(chǎn).為了提高質(zhì)量，改進(jìn)性能，降低成本，廠里決定生產(chǎn)“東風(fēng)4”250臺(tái)，每臺(tái)盈利30元；生產(chǎn)“東風(fēng)5”7000臺(tái)，每臺(tái)盈利89元；生產(chǎn)“東風(fēng)6”1000臺(tái)，每臺(tái)虧損7.5元.這3種型號(hào)產(chǎn)品的產(chǎn)量不作為最優(yōu)生產(chǎn)計(jì)劃的決策變量.由于“東風(fēng)1”、“東風(fēng)2”、“東風(fēng)3”及配件為暢銷產(chǎn)品，以這4種產(chǎn)品的產(chǎn)量作為決策變量.該廠各種產(chǎn)品的利潤(rùn)、生產(chǎn)條件等統(tǒng)計(jì)資料如表2.17～表2.20所示.2.6線性規(guī)劃的應(yīng)用2023/2/5108表2.17年計(jì)劃產(chǎn)量、成本、利潤(rùn)統(tǒng)計(jì)表產(chǎn)品指標(biāo)東風(fēng)-1東風(fēng)-2東風(fēng)-3配件東風(fēng)-4東風(fēng)-5東風(fēng)-6年計(jì)劃產(chǎn)量（臺(tái)）1100015000240001500025070001000銷售收入（元/臺(tái)）416.4201.6317082.84成本（元/臺(tái)）314.49153.63133.0945.55利潤(rùn)（元/臺(tái)）85.4533.7724.9931.5430897.5稅金（元/臺(tái)）16.4614.2311.925.75

表2.18年原材料、燃料、動(dòng)力供應(yīng)情況表（單位：噸）煤焦碳生鐵鋼材鋁材銅材電（萬(wàn)度）柴油汽油6021074.12189.61369.149.1435.81245.5285542.6線性規(guī)劃的應(yīng)用2023/2/5109

表2.19單位產(chǎn)品原材料、燃料、動(dòng)力消耗統(tǒng)計(jì)表（單位：kg）產(chǎn)品消耗量資源東風(fēng)-1東風(fēng)-2東風(fēng)-3配件東風(fēng)-4東風(fēng)-5東風(fēng)-6煤15.198.41.48715焦碳17.1124.9516.714.6410.9214.03生鐵34.8850.8634.0429.8422.2828.6鋼材39.86.142.990.62.9212.76.26鋁材0.0740.0070.0133.1850.01620.01460.016銅材0.1440.3620.370.03050.0040.012電（度）6337346353042柴油1.21.210.210.91.3汽油10.90.900.90.812.6線性規(guī)劃的應(yīng)用2023/2/5110表2.20各車間單位產(chǎn)品占用工時(shí)統(tǒng)計(jì)表（單位：分鐘）產(chǎn)品

加工時(shí)間車間東風(fēng)-1東風(fēng)-2東風(fēng)-3配件東風(fēng)-4東風(fēng)-5東風(fēng)-6全年提供最大工時(shí)數(shù)金一281.5940.63129.0674請(qǐng)外單位加工1554.988419360金二69.378.2522.6812.8826.798.053572620金三60.5883.6576.3532.2254165872830金四90.73177.19167.7857832600鑄工1140.5120.967.216.12134540鍛工1460.736.5102856750鉚焊43.569.642.914.15899068熱處理31.477.7222.3453.7221982320組裝173.5146.5146.58613550146121042002.6線性規(guī)劃的應(yīng)用2023/2/5111由表2.19可以計(jì)算出完成“東風(fēng)4”、“東風(fēng)5”和“東風(fēng)6”生產(chǎn)任務(wù)所消耗的各種資源的數(shù)量.如消耗煤的量：（8250+77000+151000）kg=66000kg.再由表2.18知，(60200066000)kg=536000kg才是用于生產(chǎn)“東風(fēng)1”、“東風(fēng)2”、“東風(fēng)3”及“配件”的煤的約束量，其余資源的約束量類推.它們的約束和總量見(jiàn)表2.21.表2.21原材料、燃料、動(dòng)力的約束量和總量

約束量資源可用的量總量煤536000602000焦碳9799701074100生鐵19975802189600鋼材1343209.751369100鋁材49017.7549140銅材35762.37535810電（度）21944502455200柴油7715085000汽油47175540002.6線性規(guī)劃的應(yīng)用2023/2/5112同樣由表2.20可以計(jì)算出各車間可用于生產(chǎn)“東風(fēng)-1”、“東風(fēng)-2”、“東風(fēng)-3”及配件的約束量，見(jiàn)表2.22.表2.22工時(shí)的約束量和總量（單位：分鐘）約束量車間量總量金一82593808419360金二32876703572620金三54788305872830金四77976007832600鑄工20680402134540鍛工28467502856750鉚焊58949685899068熱處理19344201982320組裝10874450121042002.6線性規(guī)劃的應(yīng)用2023/2/5113（2）建立數(shù)學(xué)模型根據(jù)以上資料，建立使該廠年總利潤(rùn)最大的數(shù)學(xué)模型.設(shè)產(chǎn)品“東風(fēng)-1”、“東風(fēng)-2”、“東風(fēng)-3”及配件的產(chǎn)量依次為X1,X2,X3,X4.目標(biāo)函數(shù)：約束條件組：煤的約束：焦炭的約束：生鐵的約束：鋼材的約束：鋁材的約束：銅材的約束：2.6線性規(guī)劃的應(yīng)用2023/2/5114電力的約束:柴油的約束：汽油的約束：金一車間的工時(shí)約束：金二車間的工時(shí)約束:金三車間的工時(shí)約束：金四車間的工時(shí)約束：鑄工車間的工時(shí)約束：鍛工車間的工時(shí)約束：鉚焊車間的工時(shí)約束：熱處理車間的工時(shí)約束：組裝車間的工時(shí)約束:非負(fù)約束：xj≥0(j=1,2,3,4),且為整數(shù).2.6線性規(guī)劃的應(yīng)用2023/2/5115線性規(guī)劃模型為

且為整數(shù).2.6線性規(guī)劃的應(yīng)用2023/2/5116（3）用WinQSB軟件求解：調(diào)用WinQSB中的“LinearandIntegerProgrem”子程序（該子程序使用的詳細(xì)說(shuō)明見(jiàn)本章§2.7），填寫相應(yīng)數(shù)據(jù)如圖2.6之后，點(diǎn)擊“OK”健得到表2.23.再填寫線性規(guī)劃模型中的數(shù)據(jù)如表2.24.圖2.62.6線性規(guī)劃的應(yīng)用2023/2/5117表2.232.6線性規(guī)劃的應(yīng)用2023/2/5118表2.242.6線性規(guī)劃的應(yīng)用2023/2/5119（4）計(jì)算結(jié)果：計(jì)算結(jié)果見(jiàn)表2.25.2.6線性規(guī)劃的應(yīng)用2023/2/5120最優(yōu)解為最優(yōu)值為顯然,計(jì)算結(jié)果不符合實(shí)際要求,因?yàn)闅獗玫呐_(tái)數(shù)應(yīng)為整數(shù).因此,我們應(yīng)改用整數(shù)規(guī)劃方法計(jì)算，數(shù)據(jù)操作如圖2.7.點(diǎn)擊“”健得到一表，在其上填寫線性規(guī)劃模型中的數(shù)據(jù)，見(jiàn)表2.26.特別注意最后一行與表2.24的區(qū)別.計(jì)算結(jié)果見(jiàn)表2.27.2.6線性規(guī)劃的應(yīng)用2023/2/51212.6線性規(guī)劃的應(yīng)用2023/2/51222.6線性規(guī)劃的應(yīng)用2023/2/51232.6線性規(guī)劃的應(yīng)用2023/2/51242.6線性規(guī)劃的應(yīng)用（5）結(jié)論：最優(yōu)年生產(chǎn)計(jì)劃為：生產(chǎn)“東風(fēng)-1”22836臺(tái)；生產(chǎn)“東風(fēng)-2”18023臺(tái)；生產(chǎn)配件14820臺(tái)，而“東風(fēng)-3”不宜生產(chǎn).執(zhí)行此計(jì)劃，生產(chǎn)“東風(fēng)-1”、“東風(fēng)-2”及配件，年總利潤(rùn)為3027396元.由表2.17知，原計(jì)劃的總利潤(rùn)為2519360元.最優(yōu)年生產(chǎn)計(jì)劃與原生產(chǎn)計(jì)劃比較，在不增加任何投入的情況下，增加利潤(rùn)

3027396元2519360元=508036元.2023/2/5125【例2.21】年度配礦計(jì)劃優(yōu)化決策（1）問(wèn)題的描述：某大型冶金礦山公司共有14個(gè)出礦點(diǎn)，年產(chǎn)量及各礦點(diǎn)礦石的平均品位（含鐵量的百分比）見(jiàn)表2.28.按照煉鐵生產(chǎn)要求，在礦石產(chǎn)出后，需按要求指定的品位值TFe進(jìn)行不同品位礦石的混合配料，然后進(jìn)入燒結(jié)工序.最后，將小球狀的燒結(jié)球團(tuán)礦送入高爐進(jìn)行高溫?zé)掕F，生產(chǎn)出生鐵.該公司要求：將這14個(gè)出礦點(diǎn)的礦石進(jìn)行混合配礦.依據(jù)生產(chǎn)設(shè)備及生產(chǎn)工藝要求，混合礦石的平均品位TFe規(guī)定為45％.問(wèn)：應(yīng)如何配礦才能獲得最佳效益？2.6線性規(guī)劃的應(yīng)用2023/2/5126表2.28年產(chǎn)量及各礦點(diǎn)礦石的平均品位（含鐵量的百分比）礦點(diǎn)出礦量（萬(wàn)噸）平均品位（％）17037.162751.2531740.0042347.005342.0069.549.967151.41815.448.3492.749.08107.640.221113.552.71122.756.92131.240.72147.250.202.6線性規(guī)劃的應(yīng)用2023/2/51272.6線性規(guī)劃的應(yīng)用2023/2/5128③目標(biāo)函數(shù)：此題目要求“效益最佳”有一定的模糊性，由于配礦后的混合礦石將作為后面工序的原料而產(chǎn)生利潤(rùn)，故在初始階段，可將目標(biāo)函數(shù)選作配礦總量的最大化.通過(guò)以上分析，我們得到問(wèn)題的線性規(guī)劃模型2.6線性規(guī)劃的應(yīng)用2023/2/5129

2.6線性規(guī)劃的應(yīng)用（3）計(jì)算結(jié)果及分析①計(jì)算結(jié)果利用單純形法可得出該線性規(guī)劃問(wèn)題的最優(yōu)解為

最優(yōu)值為萬(wàn)噸.

2023/2/51302.6線性規(guī)劃的應(yīng)用②分析與討論計(jì)算結(jié)果是否可被該公司接受？回答是否定的.因?yàn)椋涸谧顑?yōu)解中，除第1個(gè)采礦點(diǎn)有富裕外，其余13個(gè)采礦點(diǎn)的出礦量全部參與了配礦.

而礦點(diǎn)1在配礦以后尚有富余量（70－31.121）萬(wàn)噸＝38.879萬(wàn)噸，但礦點(diǎn)1的礦石品位僅為37.16%，屬貧礦.該公司花費(fèi)了大量人力、物力、財(cái)力后，在礦點(diǎn)1生產(chǎn)的貧礦中卻有近39萬(wàn)噸礦石被閑置，而且在大量積壓的同時(shí)，還會(huì)對(duì)環(huán)境造成破壞，作為該公司的負(fù)責(zé)人或公司決策者是難以接受這樣的生產(chǎn)方案的.2023/2/5131

解決此問(wèn)題的思路：經(jīng)過(guò)分析后可知，在礦石品位TFe及出礦量都不可變更的情況下，只能把注意力集中在混合礦石的品位TFe要求上.不難看出，降低TFe的值，可以使更多的低品位礦石參與配礦.但TFe的值可以降低嗎？在降低TFe的值使更多的貧礦入選的同時(shí)會(huì)產(chǎn)生什么影響？經(jīng)調(diào)查，以及向?qū)嶋H操作人員、工程技術(shù)人員、管理人員學(xué)習(xí)、咨詢，擬定了三個(gè)TFe的新值：44％，43％，42％.2.6線性規(guī)劃的應(yīng)用2023/2/5132

.③變動(dòng)參數(shù)之后再計(jì)算，結(jié)果如下表2.29所示.礦點(diǎn)品位（%）出礦量（噸）TFe=45％TFe=44％TFe=43％TFe=42％最優(yōu)解剩余最優(yōu)解剩余最優(yōu)解剩余最優(yōu)解剩余137.167031.12138.87951.871825770707070340.0017170170170170447.0023230230230230542.00330303030649.969.59.509.509.509.50751.41110101010848.3415.415.4015.4015.4015.40949.082.72.702.702.702.701040.22

7.6

7.60

7.60

7.60

7.601152.7113.513.5013.5013.50013.51256.922.72.702.7002.702.71340.721.21.201.201.201.201450.207.27.207.204.532.670.776.43合計(jì)141.92138.879162.6718.13175.435.37158.1722.632.6線性規(guī)劃的應(yīng)用2023/2/5133(4)綜合評(píng)判及結(jié)論：①TFe值取45％和44％的兩個(gè)方案，均不能解決貧礦石大量積壓的問(wèn)題，且造成對(duì)環(huán)境的破壞，故不予以考慮.②TFe值取43％和42％的兩個(gè)方案，可使貧礦石全部入選，配礦總量均在150萬(wàn)噸以上，且剩余的礦石皆為超過(guò)50％的富礦，可以用于生產(chǎn)高附加值的產(chǎn)品精礦粉，大大提高經(jīng)濟(jì)效益.因而，這兩個(gè)方案對(duì)資源的利用比較合理.③經(jīng)測(cè)算，按TFe值取42％的方案配礦，其混合礦