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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，（臺時數(shù)限制）

，（原材料限制）

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

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

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

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

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

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

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

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

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

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

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

得到解出點B的坐標，從而得到最優(yōu)解，最大值

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

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

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

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

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

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

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

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

下，求一組未知變量（j

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第2年初，有A,C兩個投資項目.此時第1年初投資到項目A的資金已全部收回，本利和為

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

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

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

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

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

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

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

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

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

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

（3）怎樣從原始問題寫出其對偶問題？

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

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

原問題（或?qū)ε紗栴}）

對偶問題（或原問題）

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

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

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

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

1/4/2023107原問題（或?qū)ε紗栴}）對偶問題（或原問題）目標函數(shù)練習：寫出下面線性規(guī)劃的對偶規(guī)劃：1/4/2023108練習：寫出下面線性規(guī)劃的對偶規(guī)劃：12/29/2022108下面的答案哪一個是正確的？為什麼？

（原問題是極小化問題，因此應(yīng)從原始對偶表的右邊往左邊查?。?/p>

×

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，（臺時數(shù)限制）

，（原材料限制）

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

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