運(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é)科.它所研究的問題主要包括兩個(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ī)劃問題的圖解法2.4線性規(guī)劃問題解的性質(zhì)2.5解線性規(guī)劃問題的單純形法2.6線性規(guī)劃的應(yīng)用2.7WinQSB軟件應(yīng)用第二章線性規(guī)劃及其應(yīng)用2023/2/542.1線性規(guī)劃是什么2023/2/552.1線性規(guī)劃是什么我們先通過幾個(gè)實(shí)際問題來認(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)最大化問題2023/2/562.1線性規(guī)劃是什么試問：該企業(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ī)劃是什么由此得到問題的數(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的這類問題稱為最優(yōu)生產(chǎn)計(jì)劃問題.其一般描述是利用種資源組織生產(chǎn)種產(chǎn)品.以表示資源的限制，表示產(chǎn)品的單位利潤(rùn)，表示單位產(chǎn)品消耗資源的數(shù)量（代表該企業(yè)當(dāng)前的技術(shù)水平），情況如表2.2所示.現(xiàn)在的問題是：如果該企業(yè)生產(chǎn)的這種產(chǎn)品都可以賣出，如何合理充分地利用現(xiàn)有的資源，給出一個(gè)使總利潤(rùn)達(dá)到最大的產(chǎn)品生產(chǎn)計(jì)劃？2023/2/59有了解決上述問題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品的計(jì)劃產(chǎn)量分別為單位，則問題的數(shù)學(xué)模型為2.1線性規(guī)劃是什么2023/2/510模型中的都是實(shí)際問題給定的常數(shù)；未知量為決策變量.這類決策問題的應(yīng)用領(lǐng)域非常廣泛.

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

2.成本最小化問題【例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ì)量沒有損耗，問：要熔煉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ì)量沒有損耗，熔煉該種不銹鋼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ù).綜合上述討論，我們得到該問題的數(shù)學(xué)模型為2023/2/5142.1線性規(guī)劃是什么易求得此模型的解為.也就是說，選用原料依次為27，32，41，0噸時(shí)，達(dá)到最低成本957.1萬(wàn)元.例2.2的這類問題也稱為混合配料問題.其一般描述是：把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í)重量沒有損耗，問：要生產(chǎn)數(shù)量為的這種產(chǎn)品，應(yīng)選用原料各多少能夠使成本最?。?023/2/5152.1線性規(guī)劃是什么2023/2/5162.1線性規(guī)劃是什么類似于例2.2，設(shè)選用原料的數(shù)量依次為，則得到此問題的數(shù)學(xué)模型為2023/2/5172.1線性規(guī)劃是什么這類決策問題的應(yīng)用領(lǐng)域同樣是非常廣泛的.再進(jìn)一步抽象，就可以將其歸納為一類決策問題：當(dāng)某個(gè)任務(wù)確定之后，如何統(tǒng)籌安排，盡量用最少的資金、人力、物力等資源去完成該項(xiàng)任務(wù).3.運(yùn)輸問題【例2.3】某建材公司有三個(gè)水泥廠，四個(gè)銷地，其產(chǎn)量、銷量、運(yùn)費(fèi)見表2.5.2023/2/5182.1線性規(guī)劃是什么如何制定調(diào)運(yùn)方案，使總的運(yùn)費(fèi)或總貨運(yùn)量最??？

解設(shè)由水泥廠運(yùn)到銷地的貨運(yùn)量為，則得到問題的數(shù)學(xué)模型為2023/2/5192.1線性規(guī)劃是什么其解為.最佳運(yùn)輸方案見表2.6.2023/2/5202.1線性規(guī)劃是什么運(yù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所示.問題是：制定一個(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)輸問題的數(shù)學(xué)模型為2023/2/5222.1線性規(guī)劃是什么4.

合理下料問題【例2.4】

現(xiàn)有一批長(zhǎng)度一定的鋼管，由于生產(chǎn)的需要，要求截出若干不同規(guī)格的鋼管.試問：要如何截取原材料，既能滿足生產(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根.問題轉(zhuǎn)化為確定每種下料方式各用多少根7.4m的原料，可使被使用的原料根數(shù)最少.2023/2/5232.1線性規(guī)劃是什么設(shè)分別為按照方式下料的原料根數(shù)，則得到問題的數(shù)學(xué)模型為2023/2/5242.1線性規(guī)劃是什么其解為

根.即最佳下料方案為：方式：200根；方式：800根；方式：200根；其他方式為0根.2023/2/5252.1線性規(guī)劃是什么下料問題的一般描述：已知有一批原材料，每根長(zhǎng)度為L(zhǎng)，由于生產(chǎn)的需要，要求截出規(guī)格分別為的零件根.問：如何截取使得總用料最??？即要求制定一個(gè)既能滿足生產(chǎn)的需要，又使得使用的原材料數(shù)量最少的下料方案.同樣可以仿照例2.4的建模過程列出此一般問題的數(shù)學(xué)模型.總之，類似于例2.1—2.4的實(shí)際問題很多，而且形式多種多樣.通過這些問題，我們可以看到上述各種問題的共同點(diǎn)，即每一個(gè)問題都用一組決策變量來表示某一方案，追求的目標(biāo)可以用關(guān)于決策變量的線性函數(shù)刻畫，或是最大化或是最小化，而要達(dá)到目標(biāo)的條件又都有一定的限制，每個(gè)限制條件均可由關(guān)于決策變量的線性等式或不等式表示.

2023/2/5262.1線性規(guī)劃是什么這類問題所構(gòu)成的數(shù)學(xué)模型,稱為線性規(guī)劃模型.有時(shí)也直接將線性規(guī)劃模型稱為線性規(guī)劃問題.針對(duì)這類模型,可以用根據(jù)數(shù)學(xué)理論設(shè)計(jì)的計(jì)算機(jī)軟件，如軟件求解，得出實(shí)際問題需要的答案.2023/2/5272.1線性規(guī)劃是什么本節(jié)學(xué)習(xí)要點(diǎn)1.通過實(shí)例，了解什么是線性規(guī)劃，了解線性規(guī)劃在管理中的幾類應(yīng)用例子2.線性規(guī)劃數(shù)學(xué)模型的組成及其特征2023/2/5282.2建立線性規(guī)劃模型的一般步驟2023/2/5292.2建立線性規(guī)劃模型的一般步驟從§2.1節(jié)中對(duì)實(shí)際問題建立數(shù)學(xué)模型的過程，可以得到一般線性規(guī)劃問題建模過程如下：第1步理解要解決的問題.搞清在什么條件下追求什么目標(biāo).第2步定義決策變量.每一個(gè)問題都用一組決策變量來表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值是非負(fù)的.第3步確定約束條件.用一組決策變量的線性等式或不等式來表示在解決問題過程中所必須遵循的約束條件.第4步列出目標(biāo)函數(shù).按實(shí)際問題的不同，用決策變量的線性函數(shù)最大化或最小化形式寫出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù).2023/2/5302.2建立線性規(guī)劃模型的一般步驟對(duì)于一些比較復(fù)雜的線性規(guī)劃問題，為了便于建立其數(shù)學(xué)模型，常需要把反映問題的背景數(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ī)劃問題；當(dāng)要求決策變量均取0或1時(shí)，稱（2.1）為整數(shù)線性規(guī)劃問題.當(dāng)要求決策變量既取實(shí)數(shù)又取整數(shù)時(shí)，稱（2.1）為混合整數(shù)線性規(guī)劃問題.我們把滿足所有約束條件的解稱為線性規(guī)劃問題（2.1）的可行解.全體可行解的集合稱為問題（2.1）的可行域,記為.使目標(biāo)函數(shù)值最大（或最?。┑目尚薪夥Q為該線性2023/2/5322.2建立線性規(guī)劃模型的一般步驟

規(guī)劃問題的最優(yōu)解，與此最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值稱為最優(yōu)目標(biāo)函數(shù)值，簡(jiǎn)稱最優(yōu)值.因此，若記，求解線性規(guī)劃問題（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所示.問：該工廠應(yīng)分別生產(chǎn)多少甲產(chǎn)品和乙產(chǎn)品才能使工廠獲利最大？2023/2/5332.2建立線性規(guī)劃模型的一般步驟解首先，確定決策變量.工廠目前要決策的是甲產(chǎn)品和乙產(chǎn)品的生產(chǎn)量，可以分別用變量來表示.由于它們表示產(chǎn)品產(chǎn)量，所以只取非負(fù)數(shù).其次，根據(jù)問題的限制條件，列出表示約束條件的線性不等式：2023/2/5342.2建立線性規(guī)劃模型的一般步驟，（非負(fù)限制）

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

，（原材料限制）

，（原材料限制）最后，根據(jù)實(shí)際問題所追求的目標(biāo)，列出其線性函數(shù)表達(dá)式.由于問題的目標(biāo)是工廠獲利最大，假如產(chǎn)品都能銷售，則總利潤(rùn)可表示為，最大利潤(rùn)記為2023/2/5352.2建立線性規(guī)劃模型的一般步驟綜上所述，就得到了描述該問題的線性規(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í)段開始上班的人數(shù)，.目標(biāo)是要求護(hù)士的總數(shù)最少.因?yàn)槊總€(gè)護(hù)士都工作8小時(shí)，即連續(xù)工作2個(gè)時(shí)段后休息，所以問題的線性規(guī)劃模型為：2023/2/5392.2建立線性規(guī)劃模型的一般步驟計(jì)算最優(yōu)解為： 故該醫(yī)院需雇用150名護(hù)士，最佳安排見表2.10所示.2023/2/5402.2建立線性規(guī)劃模型的一般步驟本節(jié)學(xué)習(xí)要點(diǎn)線性規(guī)劃的一般形式，可行解、最優(yōu)解等概念線性規(guī)劃問題建模過程：第1步理解要解決的問題.

第2步定義決策變量.

第3步確定約束條件.

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

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

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

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

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

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

以下結(jié)合實(shí)例來具體說明.

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

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

最后求解線性方程組

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

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

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

例2.7與例2.8中求解得到的問題的最優(yōu)解是惟一的，但對(duì)一般線性規(guī)劃問題，求解結(jié)果還可能出現(xiàn)其他情況.2023/2/5502.3線性規(guī)劃問題的圖解法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ī)劃問題有無窮多最優(yōu)解，這些最優(yōu)解都對(duì)應(yīng)著相同的最大值2023/2/5512.3線性規(guī)劃問題的圖解法（2）無界解的情況

【例2.10】

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

【例2.11】

對(duì)線性規(guī)劃問題由圖2.3(b)可以看出，同時(shí)滿足所有約束條件的點(diǎn)不存在，即可行域?yàn)榭占簿褪菦]有可行解，故不存在最優(yōu)解.2023/2/5532.3線性規(guī)劃問題的圖解法2023/2/5542.3線性規(guī)劃問題的圖解法當(dāng)根據(jù)實(shí)際問題建立的線性規(guī)劃模型的求解結(jié)果出現(xiàn)（2）,（3）兩種情況時(shí)，一般說明建模有錯(cuò)誤.前者缺乏必要的約束條件，后者是有矛盾的約束條件，建模時(shí)應(yīng)注意.下面再給出一個(gè)求目標(biāo)函數(shù)最小化的線性規(guī)劃問題.【例2.12】

求解線性規(guī)劃2023/2/5552.3線性規(guī)劃問題的圖解法解畫出此線性規(guī)劃問題的可行域，如圖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ī)劃問題的最優(yōu)解，且.2023/2/5562.3線性規(guī)劃問題的圖解法2023/2/5572.3線性規(guī)劃問題的圖解法本節(jié)學(xué)習(xí)要點(diǎn)1.通過圖解法了解線性規(guī)劃有幾種解的形式2.作圖的關(guān)鍵有三點(diǎn)

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

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

(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng)2023/2/5582.4線性規(guī)劃問題解的性質(zhì)2023/2/5591.線性規(guī)劃問題的標(biāo)準(zhǔn)形

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

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

其中常數(shù)非負(fù).一般可以通過以下方法，把非標(biāo)準(zhǔn)形線性規(guī)劃問題化為標(biāo)準(zhǔn)形：（1）目標(biāo)函數(shù)的標(biāo)準(zhǔn)化如果線性規(guī)劃問題是求目標(biāo)函數(shù)的最小值，即則令，得，這就同標(biāo)準(zhǔn)形的目標(biāo)函數(shù)的形式一致了.但要注意，如果要求原問題的最優(yōu)值，應(yīng)取最優(yōu)值的相反數(shù).2.4線性規(guī)劃問題解的性質(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ī)劃問題解的性質(zhì)2023/2/564（3）決策變量的標(biāo)準(zhǔn)化如果某一決策變量是一個(gè)符號(hào)不受限制的“自由變量”，可以引入兩個(gè)非負(fù)的新變量和，并作變換，將決策變量標(biāo)準(zhǔn)化..2.4線性規(guī)劃問題解的性質(zhì)2023/2/565（4）約束常數(shù)的標(biāo)準(zhǔn)化如果有某約束常數(shù)為負(fù)數(shù)，可在等式（或不等式）兩邊同時(shí)乘以，把約束常數(shù)變?yōu)檎龜?shù).2.4線性規(guī)劃問題解的性質(zhì)2023/2/566【例2.13】把下面的線性規(guī)劃問題化為標(biāo)準(zhǔn)形：【解】此例只有約束條件不符合標(biāo)準(zhǔn)形，為此引入非負(fù)的松弛變量，并分別把它們加到第1個(gè)和第2個(gè)不等式的左邊，即得標(biāo)準(zhǔn)形：注意，所加松弛變量表示沒有被利用的資源，當(dāng)然也沒有利潤(rùn)，所以在目標(biāo)函數(shù)中的系數(shù)應(yīng)為零.2.4線性規(guī)劃問題解的性質(zhì)2023/2/5672.4線性規(guī)劃問題解的性質(zhì)【例2.14】將下面線性規(guī)劃問題化為標(biāo)準(zhǔn)形【解】令，把求改為求；用替換，其中；在第1個(gè)約束不等式的左邊加入松弛變量，在第2個(gè)約束不等式的左邊減去剩余變量，這樣即可得到該問題的標(biāo)準(zhǔn)形為2023/2/568，

2.4線性規(guī)劃問題解的性質(zhì)標(biāo)準(zhǔ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ī)劃問題解的基本性質(zhì)(a)(b)(c)(d)(e)

圖2.5凸集與非凸集示例2.4線性規(guī)劃問題解的性質(zhì)2023/2/570【定義2.2

】如果凸集K中的點(diǎn)x不能成為任何線段的內(nèi)點(diǎn)，即對(duì)任意，都不存在，使得，則稱x

為K

的一個(gè)頂點(diǎn).例如三角形、正方形、凸多邊形、凸無界區(qū)域的頂點(diǎn)及圓周上的點(diǎn)，都是相應(yīng)凸集的頂點(diǎn).從圖解法的例子中知道線性規(guī)劃問題的可行域是一個(gè)凸集，且如果問題有最優(yōu)值，都是在頂點(diǎn)上達(dá)到.這些性質(zhì)推廣到一般，就是下面幾個(gè)重要定理.2.4線性規(guī)劃問題解的性質(zhì)2023/2/571【定理2.1

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

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

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

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

2023/2/574

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

稱此表為初始單純形表.表中的數(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.這一過程如下：將矩陣

可知位于第2行、第3列的元素3為主元，標(biāo)為,2.5解線性規(guī)劃問題的單純形法2023/2/579的第2行乘以1/3，得

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

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

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

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

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

解線性規(guī)劃問題

2023/2/5852.5解線性規(guī)劃問題的單純形法初始單純形表為由于檢驗(yàn)數(shù)1所在列無正數(shù)元素，故此問題無最優(yōu)解.2023/2/586【注2】在上例的初始單純形表中，由虛線隔開的左上部分，所在列的元素構(gòu)成一個(gè)二階單位矩陣我們稱為基變量.

一般地，對(duì)含有n個(gè)變量、m個(gè)約束的線性規(guī)劃問題，當(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ī)劃問題的單純形法2023/2/5872.5解線性規(guī)劃問題的單純形法本節(jié)學(xué)習(xí)要點(diǎn)1.判斷基本可行解.有3種情形：①已是最優(yōu)解，②是無界解，③不能確定.前2種情形計(jì)算結(jié)束，第3種情形需要繼續(xù)迭代，先進(jìn)基、后出基，用矩陣的初等行變換求下一個(gè)基本可行解，直到出現(xiàn)最優(yōu)解或無界解為止.2.判定方法唯一最優(yōu)解的判定：所有非基變量的檢驗(yàn)數(shù)為正,則線規(guī)劃具有唯一最優(yōu)解多重最優(yōu)解的判斷:最優(yōu)表中存在非基變量的檢驗(yàn)數(shù)為零,則線則性規(guī)劃具有多重最優(yōu)解無界解的判斷:

某個(gè)檢驗(yàn)數(shù)小于0且該檢驗(yàn)數(shù)所在列中所有元素小或等于0，則線性規(guī)劃具有無界解2023/2/5882.6線性規(guī)劃的應(yīng)用2023/2/5892.6線性規(guī)劃的應(yīng)用

線性規(guī)劃在國(guó)內(nèi)外很多部門的規(guī)劃、管理、決策過程中有大量成功的應(yīng)用，并收到了良好的效果.但是，應(yīng)用線性規(guī)劃來解決某一類實(shí)際問題時(shí)，由于問題的復(fù)雜性和情況的多變性，要真正建立一個(gè)反映實(shí)際問題的、能得出正確結(jié)論的理想模型，并不是一件容易的事情.它要求建模者具有豐富的經(jīng)驗(yàn)、較強(qiáng)的創(chuàng)造力和比較熟練的技巧.本節(jié)通過一些被簡(jiǎn)化了的問題，介紹建立線性規(guī)劃模型的基本思路和基本技巧.2023/2/5901.辦學(xué)規(guī)模問題【例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ì)除書費(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)最大.問：大約經(jīng)過多少年可以收回全部投資？2.6線性規(guī)劃的應(yīng)用2023/2/591即.于是此問題的線性規(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)過n年可收回投資.第1年利潤(rùn)為第2年利潤(rùn)為

2×11.6=23.2(萬(wàn)元);以后每年的利潤(rùn)均為34.8萬(wàn)元.故依題意應(yīng)有解得(年).即約經(jīng)過36年可以收回全部投資.2.6線性規(guī)劃的應(yīng)用2023/2/5932.投資問題【例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)目投資不得超過5萬(wàn)元；項(xiàng)目C在第2年初投資，第3年底收回本金，并獲利潤(rùn)40%，但該項(xiàng)目投資不得超過3萬(wàn)元；項(xiàng)目D在第3年初投資，于該年底收回本金，且獲利潤(rùn)30%，但該項(xiàng)目投資不得超過2萬(wàn)元.該投資人準(zhǔn)備拿出6萬(wàn)元資金，問如何制訂投資計(jì)劃，使該企業(yè)在第3年底，投資的本利之和最大？2.6線性規(guī)劃的應(yīng)用2023/2/594【解】這是一個(gè)連續(xù)投資問題.設(shè)決策變量xij為第j年投資到第i

個(gè)項(xiàng)目的資金(i=1,2,3,4,分別對(duì)應(yīng)于項(xiàng)目A,B,C,D；分別對(duì)應(yīng)于投資年份),見列表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不得超過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ù)和約束條件整理后即可得出該問題完整的線性規(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ì)劃問題【例2.18】某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題.該公司生產(chǎn)甲、乙、丙3種產(chǎn)品，這3種產(chǎn)品都要經(jīng)過鑄造、機(jī)加工和裝配3個(gè)車間.甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，也可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量.有關(guā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建立此問題的線性規(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.人力資源分配問題【例2.19】某百貨商場(chǎng)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如表2.16所示.為了保證售貨員充分休息，售貨員每周工作5天，休息2天，并要求休息的2天是連續(xù)的，問：應(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開始休息的人數(shù)（j=1,2,…，７，分別對(duì)應(yīng)星期一、二、三、四、五、六、日）.目標(biāo)是要求售貨員的總數(shù)最少.因?yàn)槊總€(gè)售貨員都工作5天，休息2天，所以只要計(jì)算出連續(xù)休息2天的售貨員數(shù)，也就計(jì)算出了售貨員的總數(shù).這里可以把連續(xù)休息2天的售貨員按照開始休息的時(shí)間分成7類，各類的人數(shù)分別為xj

（j=1,2,…，７），即有目標(biāo)函數(shù)：再按照每天所需售貨員的人數(shù)寫出約束條件.例如星期日需要28人，商場(chǎng)中的全體售貨員中除了星期六和星期日開始休息的人外都應(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)用綜上得問題的線性規(guī)劃模型為：2023/2/51062.6線性規(guī)劃的應(yīng)用計(jì)算結(jié)果：也就是說該商場(chǎng)至少需要售貨員36人.他們的的休息安排為：星期一12人；星期三11人；星期五5人；星期日8人.2023/2/51075.應(yīng)用案例【例2.20】剎車用的氣泵年度生產(chǎn)計(jì)劃.（1）問題描述某廠生產(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”及“配件”的煤的約束量，其余資源的約束量類推.它們的約束和總量見表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”及配件的約束量，見表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ì)說明見本章§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é)果見表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ù)，見表2.26.特別注意最后一行與表2.24的區(qū)別.計(jì)算結(jié)果見表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）問題的描述：某大型冶金礦山公司共有14個(gè)出礦點(diǎn)，年產(chǎn)量及各礦點(diǎ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％.問：應(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ī)劃模型2.6線性規(guī)劃的應(yīng)用2023/2/5129

2.6線性規(guī)劃的應(yīng)用（3）計(jì)算結(jié)果及分析①計(jì)算結(jié)果利用單純形法可得出該線性規(guī)劃問題的最優(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

解決此問題的思路：經(jīng)過分析后可知，在礦石品位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è)方案，均不能解決貧礦石大量積壓的問題，且造成對(duì)環(huán)境的破壞，故不予以考慮.②TFe值取43％和42％的兩個(gè)方案，可使貧礦石全部入選，配礦總量均在150萬(wàn)噸以上，且剩余的礦石皆為超過50％的富礦，可以用于生產(chǎn)高附加值的產(chǎn)品精礦粉，大大提高經(jīng)濟(jì)效益.因而，這兩個(gè)方案對(duì)資源的利用比較合理.③經(jīng)測(cè)算，按TFe值取42％的方案配礦，其混合礦