線性規(guī)劃方法及其應(yīng)用

《線性規(guī)劃方法及其應(yīng)用》由會(huì)員分享，可在線閱讀，更多相關(guān)《線性規(guī)劃方法及其應(yīng)用（109頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,*,第9章 線性規(guī)劃方法及其應(yīng)用,10/22/2024,1,線性規(guī)劃,（Linear Programming）,作為運(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)代管

2、理工作中幫助管理者做出科學(xué)決策的重要手段。,10/22/2024,2,1、,康托洛維奇,生產(chǎn)組織與計(jì)劃中的數(shù)學(xué)方法,一本小冊(cè)子，1939;,2、康托洛維奇“最佳資源利用的經(jīng)濟(jì)計(jì)算”1942完成、1959發(fā)表的著作 ；,3、自1947年,丹茲格,（）提出求解線性規(guī)劃問題的一般方法-單純形法之后，線性規(guī)劃在理論上趨于成熟，應(yīng)用日益廣泛與深入； 隨著電子計(jì)算機(jī)的發(fā)展和計(jì)算速度的不斷提高，其適用的領(lǐng)域更加廣泛，它已成為必不可少的重要手段之一。,10/22/2024,3,4、,1975年庫伯曼斯(Koopmans)因?qū)Y源最優(yōu)分配理論的貢獻(xiàn)而獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)；,5、馮諾伊曼和摩根斯坦1944年發(fā)表的,對(duì)

3、策論與經(jīng)濟(jì)行為,涉及與線性規(guī)劃等價(jià)的對(duì)策問題及線性規(guī)劃對(duì)偶理論。,10/22/2024,4,線性規(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ǔ)是線性變換。,10/22/2024,5,數(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ǎng)絡(luò)優(yōu)化,排序問題,統(tǒng)籌圖,隨,機(jī),優(yōu),化,對(duì)策論,排隊(duì)論,庫存論,決策分析,可靠性分析,運(yùn)籌學(xué)

4、的主要內(nèi)容,10/22/2024,6,9.1 線性規(guī)劃是什么,9.2 建立線性規(guī)劃模型的一般步驟,9.3 線性規(guī)劃問題的圖解法,9.4 線性規(guī)劃問題解的性質(zhì),9.5 解線性規(guī)劃問題的單純形法,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,7,9.1 線性規(guī)劃是什么,10/22/2024,8,9.1 線性規(guī)劃是什么,我們先通過幾個(gè)實(shí)際問題來認(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)最大化問題,10/22/2024,9,9.1 線性

5、規(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ù)的限制，即,10/22/2024,10,9.1 線性規(guī)劃是什么,由此得到問題的數(shù)學(xué)模型為,其中 為英文“subject to”的縮寫，表示決策變量 受它后面的條件約束. 最優(yōu)解為 （具體解法后面介紹,），代入總利潤(rùn)的表達(dá)式 得對(duì)應(yīng)的目標(biāo)函數(shù)最大值為250.由此得到該企業(yè)在現(xiàn)有資源條件下，日,生產(chǎn)的最優(yōu)安排

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

7、生產(chǎn)， 生產(chǎn)25噸， 生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.,其中 為英文“subject to”的縮寫，表示決策變量 受它后面的條件約束. 最優(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千元/日.,其中 為英文“subject to”的縮寫，表示決策變量 受它后面的條件約束. 最優(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)

8、25噸， 生產(chǎn)25噸，可實(shí)現(xiàn)最大利潤(rùn)250千元/日.,10/22/2024,11,9.1 線性規(guī)劃是什么,類似于例9.1的這類問題稱為最優(yōu)生產(chǎn)計(jì)劃問題.其一般描述是利用 種資源 組織生產(chǎn) 種產(chǎn)品 .以 表示資源 的限制， 表示產(chǎn)品 的單位利潤(rùn)， 表示單位產(chǎn)品,消耗資源 的數(shù)量（代表該企業(yè)當(dāng)前的技術(shù)水平），情況如表9.2所示. 現(xiàn)在的問題是：如果該企業(yè)生產(chǎn)的這 種產(chǎn)品 都可以賣出，如何合理充分地利用現(xiàn)有的資源，給出一個(gè)使總利潤(rùn)達(dá)到最大的產(chǎn)品生產(chǎn)計(jì)劃？,10/22/2024,12,有了解決上述問題的經(jīng)驗(yàn)，我們可以假設(shè)產(chǎn)品 的計(jì)劃產(chǎn)量分別為 單位，則問題的數(shù)學(xué)模型為,9.1 線性規(guī)劃是什么,10/2

9、2/2024,13,模型中 的都是實(shí)際問題給定的常數(shù)；未知量 為決策變量.這類決策問題的應(yīng)用領(lǐng)域非常廣泛.,注,本章的數(shù)學(xué)模型均可用軟件求解。,2. 成本最小化問題,【,例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ì)量沒有損耗，問：要熔煉100噸這樣的不銹鋼，應(yīng)選用原料 各多少噸，能夠使成本最?。?9.1 線性規(guī)劃是什么,10/22/2024,14,9.1 線性規(guī)劃是什么,下料問題的一般描述：已知有一批原材料，每根長(zhǎng)度

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

11、構(gòu)成的數(shù)學(xué)模型,稱為,線性規(guī)劃,模型,.,有時(shí)也直接將線性規(guī)劃模型稱為線性規(guī)劃問題.,針對(duì)這類模型,可以用根據(jù)數(shù)學(xué)理論設(shè)計(jì)的計(jì)算機(jī)軟件，如軟件求解，得出實(shí)際問題需要的答案。,10/22/2024,16,9.2 建立線性規(guī)劃模型的,一般步驟,10/22/2024,17,9.2 建立線性規(guī)劃模型的一般步驟,從9.1節(jié)中對(duì)實(shí)際問題建立數(shù)學(xué)模型的過程，可以得到一般線性規(guī)劃問題建模過程如下：,第1步,理解要解決的問題. 搞清在什么條件下追求什么目標(biāo).,第2步,定義,決策變量,. 每一個(gè)問題都用一組決策變量,來表示某一方案；這組決策變量的值就代表一個(gè)具體方案，一般這些變量取值,是非負(fù)的,.,第3步,確定,

12、約束條件,. 用一組決策變量的線性等式或不等式來表示在解決問題過程中所必須遵循的約束條件.,第4步,列出,目標(biāo)函數(shù),. 按實(shí)際問題的不同，用決策變量的線性函數(shù)最大化或最小化形式寫出所要追求的目標(biāo)，稱之為目標(biāo)函數(shù).,10/22/2024,18,9.2 建立線性規(guī)劃模型的一般步驟,對(duì)于一些比較復(fù)雜的線性規(guī)劃問題，為了便于建立其數(shù)學(xué)模型，常需要把反映問題的背景數(shù)據(jù)資料用表格形式歸類綜合，以揭示各個(gè)量之間的內(nèi)在聯(lián)系.,線性規(guī)劃的一般形式可表示為：,10/22/2024,19,9.2 建立線性規(guī)劃模型的一般步驟,其中稱 為目標(biāo)函數(shù)， 為決策變量， 為約束常數(shù)，后面的式子為約束條件.這里的 為常數(shù).,當(dāng)要

13、求決策變量 均為整數(shù)時(shí)，稱（9.1）為,純整數(shù)線性規(guī)劃問題,；,當(dāng)要求決策變量 均取0或1時(shí)，稱（9.1）為,整數(shù)線性規(guī)劃問題,.,當(dāng)要求決策變量 既取實(shí)數(shù)又取整數(shù)時(shí)，稱（9.1）為混合整數(shù)線性規(guī)劃問題.,我們把滿足所有約束條件的解稱為線性規(guī)劃問題（9.1）的,可行解,.全體可行解的集合稱為問題（9.1）的,可行域,記為,.使目標(biāo)函數(shù)值最大（或最?。┑目尚薪夥Q為該線性,10/22/2024,20,9.2 建立線性規(guī)劃模型的一般步驟,規(guī)劃問題的,最優(yōu)解,，與此最優(yōu)解相應(yīng)的目標(biāo)函數(shù)值稱為,最優(yōu)目標(biāo)函數(shù)值,，,簡(jiǎn)稱,最優(yōu)值,.,因此，若記 ，求解線性規(guī)劃問題（9.1），本質(zhì)上就是尋找一點(diǎn),，使得,均

14、滿足不等式,【,例9.3,】,某工廠在計(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)品才能使工廠獲利最大？,10/22/2024,21,9.2 建立線性規(guī)劃模型的一般步驟,解,首先，確定決策變量.工廠目前要決策的是甲產(chǎn)品和乙產(chǎn)品的生產(chǎn)量，可以分別用變量 來表示.由于它們表示產(chǎn)品產(chǎn)量，所以只取非負(fù)數(shù).,其次，根據(jù)問題的限制條件，列出表示約束條件的線性不等式：,10/22/2024,22,9.2 建立線性規(guī)劃模型的一般步驟,，（非負(fù)限制）,，（臺(tái)時(shí)數(shù)限制）,，（原材料 限制）,，

15、（原材料 限制）,最后，根據(jù)實(shí)際問題所追求的目標(biāo)，列出其線性函數(shù)表達(dá)式.由于問題的目標(biāo)是工廠獲利最大，假如產(chǎn)品都能銷售，則總利潤(rùn)可表示為 ，最大利潤(rùn)記為,10/22/2024,23,9.2 建立線性規(guī)劃模型的一般步驟,綜上所述，就得到了描述該問題的線性規(guī)劃模型：,10/22/2024,24,計(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ī)劃模型的一般步驟,10/22/2024,25,9.2 建立線性規(guī)劃模型的一般步驟,【例9.4】,某醫(yī)院護(hù)士24小時(shí)值班，每次值班8小時(shí).不

16、同時(shí)段需要的護(hù)士人數(shù)不等.據(jù)統(tǒng)計(jì)，各時(shí)段所需護(hù)士的最少人數(shù)如表2.9所示. 如何安排才能做到安排最少的護(hù)士就能滿足工作的需要？,10/22/2024,26,9.2 建立線性規(guī)劃模型的一般步驟,解 設(shè) 為時(shí)段 開始上班的人數(shù)， .目標(biāo)是要求護(hù)士的總數(shù)最少.因?yàn)槊總€(gè)護(hù)士都工作8小時(shí)，即連續(xù)工作2個(gè)時(shí)段后休息，所以問題的線性規(guī)劃模型為：,10/22/2024,27,9.2 建立線性規(guī)劃模型的一般步驟,計(jì)算最優(yōu)解為： 故該醫(yī)院需雇用150名護(hù)士，最佳安排見表9.10所示.,10/22/2024,28,9.2 建立線性規(guī)劃模型的一般步驟,線性規(guī)劃的一般形式，可行解、最優(yōu)解等概念,線性規(guī)劃問題建模過程：,

17、第1步,理解要解決的問題。,第2步,定義決策變量。,第3步,確定約束條件。,第4步,列出目標(biāo)函數(shù)。,10/22/2024,29,9.3 線性規(guī)劃問題的圖解法,10/22/2024,30,9.3 線性規(guī)劃問題的圖解法,1. 圖解法,對(duì)一個(gè)線性規(guī)劃問題建立數(shù)學(xué)模型之后，就面臨著如何求解的問題.這里先介紹含有兩個(gè)決策變量 的線性規(guī)劃問題的圖解法.它簡(jiǎn)單直觀，有助于了解線性規(guī)劃問題求解的基本原理.,10/22/2024,31,圖解法的步驟可概括為：,（1）在平面上建立直角坐標(biāo)系 ；,（2）圖示約束條件，找出可行域（由于 ，可行域必位于第一象限）；,（3）圖示目標(biāo)函數(shù)，即畫出目標(biāo)函數(shù)等值線；,（4）對(duì)

18、（或 ）問題朝著增大（或減少）縱截距的方向平行移動(dòng)目標(biāo)函數(shù)等值線，至與可行域的邊界相切時(shí)為止.切點(diǎn)（即某個(gè)邊界點(diǎn)）就是代表最優(yōu)解的點(diǎn)；,（5）尋找該點(diǎn)的坐標(biāo)得到最優(yōu)解.,以下結(jié)合實(shí)例來具體說明.,10/22/2024,32,9.3 線性規(guī)劃問題的圖解法,【例9.5】,用圖解法求解線性規(guī)劃問題,10/22/2024,33,9.3 線性規(guī)劃問題的圖解法,解 先畫出線性規(guī)劃的可行域如圖9.1陰影部分.,再畫出目標(biāo)函數(shù)等值線，朝著增大縱截距的方向平行移動(dòng)等值線至點(diǎn) .,最后求解線性方程組,求解得到點(diǎn) 的坐標(biāo)，從而得到最優(yōu)解 ，最大值,10/22/2024,34,9.3 線性規(guī)劃問題的圖解法,10/22

19、/2024,35,9.3 線性規(guī)劃問題的圖解法,【例9.6】,用圖解法求解線性規(guī)劃問題,解 先畫出線性規(guī)劃的可行域，如圖9.2陰影部分.,10/22/2024,36,9.3 線性規(guī)劃問題的圖解法,10/22/2024,37,9.3 線性規(guī)劃問題的圖解法,再畫出目標(biāo)函數(shù)等值線，朝著增大縱截距的方向平行移動(dòng)等值線至點(diǎn)B.最后求解線性方程組,得到解出點(diǎn)B的坐標(biāo) ，從而得到最優(yōu)解 ，最大值,例9.5與例9.6中求解得到的問題的最優(yōu)解是惟一的，但對(duì)一般線性規(guī)劃問題，求解結(jié)果還可能出現(xiàn)其他情況.,10/22/2024,38,9.3 線性規(guī)劃問題的圖解法,2. 線性規(guī)劃解的其他情況,（1）多重最優(yōu)解的情況,

20、【例9.9】,若將例9.5中的目標(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)著相同的最大值,10/22/2024,39,MAX,10/22/2024,40,9.3 線性規(guī)劃問題的圖解法,（,2,）無界解的情況,（3）無可行解的情況,10/22/2024,41,9.3 線性規(guī)劃問題的圖解法,（2）無界解的情況,【例9.10】,對(duì)下述線性規(guī)劃問題,用圖解法求解結(jié)果如圖2.3(a) 所示. 從圖中可以看出，由于可行域是無界區(qū)域，當(dāng)目標(biāo)函數(shù)等值線沿箭頭方向平行

21、移動(dòng)時(shí)，始終與該無界區(qū)域相交. 此時(shí)，目標(biāo)函數(shù)值無上界，因此無最優(yōu)解，也稱,最優(yōu)解無界,.,10/22/2024,42,9.3 線性規(guī)劃問題的圖解法,（3）無可行解的情況,【例9.11】,對(duì)線性規(guī)劃問題,由圖2.3(b)可以看出，同時(shí)滿足所有約束條件的點(diǎn)不存在，即可行域?yàn)榭占?，也就是沒有可行解，故不存在最優(yōu)解.,10/22/2024,43,9.3 線性規(guī)劃問題的圖解法,當(dāng)根據(jù)實(shí)際問題建立的線性規(guī)劃模型的求解結(jié)果出現(xiàn)（2）, （3）兩種情況時(shí)，一般說明建模有錯(cuò)誤.前者缺乏必要的約束條件，后者是有矛盾的約束條件，建模時(shí)應(yīng)注意.下面再給出一個(gè)求目標(biāo)函數(shù)最小化的線性規(guī)劃問題.,【例9.12】,求解線性

22、規(guī)劃,10/22/2024,44,9.3 線性規(guī)劃問題的圖解法,解 畫出此線性規(guī)劃問題的可行域，如圖中的陰影部分.目標(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)解，且 .,10/22/2024,45,9.3 線性規(guī)劃問題的圖解法,10/22/2024,46,9.3 線性規(guī)劃問題的圖解法,1.通過圖解法了解線性規(guī)劃有幾種解的形式,2.作圖的關(guān)鍵有三點(diǎn),(1)可行解區(qū)域要畫正確,(2)目標(biāo)函數(shù)增加的方向不能畫錯(cuò),(3)目標(biāo)函數(shù)的直線怎樣平行移動(dòng),10

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

24、；,（3）所有決策變量均取非負(fù)數(shù)；,（4）所有約束常數(shù)均為非負(fù)數(shù).,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,51,于是，具有個(gè)約束條件和個(gè)決策變量的線性規(guī)劃問題的,標(biāo)準(zhǔn)形,為：,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,52,在約束條件,0,（,j = 1,，,2,，,，,n,）,下，求一組未知變量（,j,=,1，2，,，,n,）的值，使得,。常記為如下更為緊湊的形式,或,其縮寫形式為：,10/22/2024,53,其中 b和C為已知非負(fù)常數(shù)，A為已知常數(shù)矩陣，且rank(A)=m。一般可以通過以下方法，把,非標(biāo)準(zhǔn)形線性規(guī)劃問題化為標(biāo)準(zhǔn)形：,（1）目標(biāo)函數(shù)的標(biāo)準(zhǔn)化,如果線

25、性規(guī)劃問題是求目標(biāo)函數(shù)的最小值，即,則令 ，得 ，這就同標(biāo)準(zhǔn)形的目標(biāo)函數(shù)的形式一致了.但要注意，如果要求原問題的最優(yōu)值，應(yīng)取最優(yōu)值的相反數(shù).,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,54,（,2）約束條件的標(biāo)準(zhǔn)化,當(dāng)約束條件為,形式的不等式時(shí)，可在不等式左邊加上一個(gè)非負(fù)的新變量（稱為,松弛變量,(slack variables),），把不等號(hào)變?yōu)榈忍?hào)；,當(dāng)約束條件為,形式的不等式時(shí)，可在不等式左邊減去一個(gè)非負(fù)的新變量（稱為,剩余變量,），把不等號(hào)變?yōu)榈忍?hào).,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,55,（3）決策變量的標(biāo)準(zhǔn)化,如果某一決策變量是一個(gè)符號(hào)不受限制的“自由變

26、量”，可以引入兩個(gè)非負(fù)的新變量 和 ，并作變換 ，將決策變量標(biāo)準(zhǔn)化。,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,56,（4）約束常數(shù)的標(biāo)準(zhǔn)化,如果有某約束常數(shù)為負(fù)數(shù)，可在等式（或不等式）兩邊同時(shí)乘以，把約束常數(shù)變?yōu)檎龜?shù).,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,57,【例9.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)為零.,9.4 線性規(guī)劃問題解的性質(zhì),10/22/20

27、24,58,9.4 線性規(guī)劃問題解的性質(zhì),【例9.14】,將下面線性規(guī)劃問題化為標(biāo)準(zhǔn)形,【解 】令 ，把求 改為求 ；用 替換 ，其中 ；在第1個(gè)約束不等式的左邊加入松弛變量 ，在第2個(gè)約束不等式的左邊減去剩余變量 ，這樣即可得到該問題的標(biāo)準(zhǔn)形為,10/22/2024,59,，,9.4 線性規(guī)劃問題解的性質(zhì),標(biāo)準(zhǔn)形,原問題,10/22/2024,60,2.線性規(guī)劃的解,可行解與最優(yōu)解,滿足約束條件（即滿足線性約束和非負(fù)約束）的一組變量為可行解。所有可行解組成的集合稱為可行域。,使目標(biāo)函數(shù)最大或最小化的可行解稱為最優(yōu)解。,10/22/2024,61,基本解與基本可行解,在線性規(guī)劃問題中，將,約束

28、方程組的,m,n,階矩陣,A,寫成由,n,個(gè)列向量組成的分塊矩陣,10/22/2024,62,如果,B,是,A,中的一個(gè)m階的非奇異子陣，則稱,B,為該線性規(guī)劃問題的一個(gè)基。不失一般性，不妨設(shè),則稱 為基向量，與基向量相對(duì)應(yīng)的向量,為基變量，而其余的變量為,非基變量。,10/22/2024,63,如果 是方程組 的解, 則 就是方程,組 的一個(gè)解，它稱之為對(duì)應(yīng)于基,B,的,基本解,，簡(jiǎn)稱基解。,滿足非負(fù)約束條件的基本解，稱為,基本可行解,。對(duì)應(yīng)于基本可行解的基，稱為可行基。,10/22/2024,64,線性規(guī)劃問題的以上幾個(gè)解的關(guān)系，可用下圖來描述：,10/22/2024,65,【,定義9.1

29、,】,如果集合K中任意兩點(diǎn)s,t之間連線上所有的點(diǎn)都是集合K中的點(diǎn)，即對(duì)于任意的 ，都有 ，則稱K為凸集.,例如圖9.5中（a）, （b）, （c）為凸集，而（d）, （e）不是凸集.,3. 線性規(guī)劃問題解的基本性質(zhì),(a) (b) (c) (d) (e),圖9.5 凸集與非凸集示例,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,66,【,定理9.1,】,線性規(guī)劃問題的可行域,是一個(gè)凸集.,這兩個(gè)定理我們不給予數(shù)學(xué)證明.結(jié)合圖解法，我們可以清晰地了解到線性規(guī)劃問題解的有關(guān)性質(zhì).定理9.1說明：聯(lián)結(jié)線性規(guī)劃問題任意兩個(gè)可行解的線段上的點(diǎn)（坐標(biāo)）仍是可行解.定理9.2則告訴我們：如果一個(gè)線性

30、規(guī)劃問題有最優(yōu)解，則一定可以從可行域的有限個(gè)頂點(diǎn)中找到.,【,定理9.2,】,若可行域非空有界，則線性規(guī)劃問題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到.,9.4 線性規(guī)劃問題解的性質(zhì),10/22/2024,67,【,定義9.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è)重要定理.,9.4 線性規(guī)劃問題解的性質(zhì),10/

31、22/2024,68,9.4 線性規(guī)劃問題解的性質(zhì),1.將非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形的方法,2.線性規(guī)劃問題的解,3.線性規(guī)劃問題解的性質(zhì),（1）線性規(guī)劃問題的可行域,是一個(gè)凸集。,（2）若可行域非空有界，則線性規(guī)劃問題的最優(yōu)值一定可以在可行域的某個(gè)頂點(diǎn)上達(dá)到。,10/22/2024,69,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,70,單純形法是求解線性規(guī)劃的一種通用方法，1947年由美國(guó)數(shù)學(xué)家丹茲格（）給出.下面結(jié)合9.1中的利潤(rùn)最大化問題介紹單純形法的基本內(nèi)容.由9.1中的例9.1提供的,數(shù)學(xué)模型,為:,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,71,（1）先化為標(biāo)準(zhǔn)

32、形. 引入松弛變量 得到,標(biāo)準(zhǔn)形,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,72,（2）再把目標(biāo)函數(shù),改寫成,并把它加入到約束方程組中去，即得到方程組,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,73,將此方程組的系數(shù)及常數(shù)項(xiàng)b,列成一個(gè)數(shù)表，即,.,9.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)到下一步.,10/22/2024,74,（3）在負(fù)檢驗(yàn)數(shù)中選絕對(duì)值最大

33、的負(fù)數(shù)（即,7,），在對(duì)應(yīng)的列中，將該列中的正數(shù)分別去除對(duì)應(yīng)的常數(shù)項(xiàng)，選擇比值最小者所對(duì)應(yīng)的元素為主元（稱為最小比值原則）.在這里,然后用矩陣的初等行變換，將主元化為1，把同列的其他元素化為0.這一過程如下：,將矩陣,可知位于第2行、第3列的元素3為主元，標(biāo)為 ,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,75,的第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，把

34、同列的其他元素化為0，,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,76,過程如下：,將矩陣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,.,9.5 解線性規(guī)劃問題的單純形法,再將矩陣的第2行乘以（,2,）加到第1行，第2行乘以7加到,第3行，得,10/22/2024,77,上述求解線性規(guī)劃問題的方法稱為,單純形法,.,單純形法步驟如下,：,第,1,步，將線性規(guī)劃化成標(biāo)準(zhǔn)形；,第,2,步，寫出初始單純形表；,第,3,步，

35、對(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)值.,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,78,從上例求解過程看到，單純形表中,所對(duì)應(yīng)的列始終不變，故在實(shí)際計(jì)算中可省去不寫.上例的求解過程本質(zhì)上是矩陣的初等行變換過程，我們可以把此例的單純形法求解過程簡(jiǎn)化為,9.5 解線性規(guī)劃問題的單純形法,10/22/2

36、024,79,9.5 解線性規(guī)劃問題的單純形法,所以最優(yōu)解及最優(yōu)值分別為,【,注1,】,若在計(jì)算過程中，單純形表出現(xiàn)某檢驗(yàn)數(shù)為負(fù)，但其所在的列無正元素的情況，則可以證明該問題無最優(yōu)解.,10/22/2024,80,【解 】引入松弛變量，化為標(biāo)準(zhǔn)形,9.5 解線性規(guī)劃問題的單純形法,【例9.15】,解線性規(guī)劃問題,10/22/2024,81,初始單純形表為,由于檢驗(yàn)數(shù),1,所在列無正數(shù)元素，故此問題無最優(yōu)解.,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,82,【,注2,】在上例的初始單純形表中，由虛線隔開的左上部分，,所在列的元素構(gòu)成一個(gè)二階單位矩陣,我們稱,為基變量.,一般地，對(duì)含

37、有,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ì)偶單純形法,.,9.5 解線性規(guī)劃問題的單純形法,10/22/2024,83,9.5 解線性規(guī)劃問題的單純形法,1.判斷基本可行解.有3種情形：已是最優(yōu)解，是無界解，不能確定.前2種情形計(jì)算結(jié)束，第3種情形需要繼續(xù)迭代，先進(jìn)基后出基，初等變換求下一個(gè)基本可行解，直到出現(xiàn)最優(yōu)解或無界解為止。

38、,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ù)所在列中所有元素小或等于，則線性規(guī)劃具有無界解。,10/22/2024,84,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,85,9.6 線性規(guī)劃的應(yīng)用,線性規(guī)劃在國(guó)內(nèi)外很多部門的規(guī)劃、管理、決策過程中有大量成功的應(yīng)用，并收到了良好的效果.但是，應(yīng)用線性規(guī)劃來解決某一類實(shí)際問題時(shí)，由于問題的復(fù)雜性和情況的多變性，要真正建立一個(gè)反映實(shí)際問題的、能得出正確結(jié)論的理想模型，并不是一件容易

39、的事情.它要求建模者具有豐富的經(jīng)驗(yàn)、較強(qiáng)的創(chuàng)造力和比較熟練的技巧.本節(jié)通過一些被簡(jiǎn)化了的問題，介紹建立線性規(guī)劃模型的基本思路和基本技巧.,10/22/2024,86,1.辦學(xué)規(guī)模問題,【例9.16】 某人準(zhǔn)備投資1200萬元辦一所中學(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)（萬元）,教師年薪（萬元）,初中,50,2.0,28,1.2,高中,40,2.5,58,1.6,根據(jù)物價(jià)部門的有關(guān)文件，初中是義務(wù)教育階段，收費(fèi)標(biāo)準(zhǔn)適當(dāng)控制，預(yù)計(jì)除書費(fèi)、辦公費(fèi)外，初中

40、每個(gè)學(xué)生每年可收取600元，而高中每個(gè)學(xué)生每年可收取1500元.因生源和環(huán)境等條件限制，辦學(xué)規(guī)模以2030個(gè)（含20與30）班為宜.教師實(shí)行聘任制.初、高中的教育周期均為3年.請(qǐng)你合理地安排招生計(jì)劃，使年利潤(rùn)最大. 問：大約經(jīng)過多少年可以收回全部投資？,10/22/2024,87,解 設(shè)初中編制班數(shù)為,x,高中編制班數(shù)為,y,又設(shè)年利潤(rùn)為 f , （單位：萬元），那么,即,.于是此問題的線性規(guī)劃模型為,解得最優(yōu)解,代入,中得,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,88,故學(xué)校的最優(yōu)規(guī)模和招生計(jì)劃分別為,最優(yōu)規(guī)模：初中18個(gè)班，高中12個(gè)班；,招生計(jì)劃：第1年初中招生6個(gè)班約300人，高

41、中招生4個(gè)班約160人.以后每年按此計(jì)劃招生.,設(shè)經(jīng)過n,年可收回投資.,第1年利潤(rùn)為,第2年利潤(rùn)為,211.6=23.2,(萬元);,以后每年的利潤(rùn)均為34.8萬元.故依題意應(yīng)有,解得,(年).即約經(jīng)過36年可以收回全部投資.,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,89,2. 投資問題,【例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)目投資不得超過5萬元；項(xiàng)目,C,在第2年初投資，第3年底收回本金，并獲利潤(rùn)40%，但該項(xiàng)目

42、投資不得超過3萬元；項(xiàng)目,D,在第3年初投資，于該年底收回本金，且獲利潤(rùn)30%，但該項(xiàng)目投資不得超過2萬元.該投資人準(zhǔn)備拿出6萬元資金，問如何制訂投資計(jì)劃，使該企業(yè)在第3年底，投資的本利之和最大？,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,90,【解】 這是一個(gè)連續(xù)投資問題.設(shè)決策變量,x,ij,為第,j,年投資到第,i,個(gè)項(xiàng)目的資金(,i,=,1,2,3,4,分別對(duì)應(yīng)于項(xiàng)目,A,B,C,D,； 分別對(duì)應(yīng)于投資年份),見列表9.13.,表9.13 投資項(xiàng)目,投資機(jī)會(huì),項(xiàng)目名稱,第1年年初 第2年年初 第3年年初,A,B,C,D,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,91,下面分析每

43、年資金的使用情況并建立線性規(guī)劃模型.,第1年初，,有,A, B,兩個(gè)項(xiàng)目，企業(yè)只能提供6萬元資金，故有,:,.項(xiàng)目,B,不得超過5萬元，有,第2年初,，有,A,C,兩個(gè)投資項(xiàng)目.此時(shí)第1年初投資到項(xiàng)目,A,的資金已全部收回，本利和為,.這些資金可用于第2年的投資，,，而且要求,9.6 線性規(guī)劃的應(yīng)用,于是,；,；,10/22/2024,92,9.6 線性規(guī)劃的應(yīng)用,第3年初,，第1年初投資到項(xiàng)目,B,的資金全部收回，本利和為,;,第2年初投資于項(xiàng)目,A,的資金也全部收回，本利和為,以上兩筆資金可供該年繼續(xù)投資.第3年內(nèi)還有,A,D,兩個(gè)項(xiàng),目的投資，可得,，而且要求,第3年底,，到期把所有本利

44、和收回.所能收回的資金有第2年,初投資到項(xiàng)目,C,的本利和,，第3年初投資到項(xiàng)目,A,的,本利和,及投資到項(xiàng)目,D,的本利和,，則第3年底獲,得的本利和為,;,10/22/2024,93,將上述目標(biāo)函數(shù)和約束條件整理后即可得出該問題完整的,線性規(guī)劃模型,:,求解得到最優(yōu)投資方案如表9.14所示，且在第3年底收回投資的本利和最大為11.528萬元 .,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,94,表9.14 最優(yōu)投資方案,投資機(jī)會(huì),項(xiàng)目名稱,第1年年初 第2年年初 第3年年初,A,X,11,=1,X,12,=1.2,X,13,=7.44,B,X,21,=5,C,X,32,=0,D,X,43

45、,=2,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,95,3.人力資源分配問題,【例9.19】某百貨商場(chǎng)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如表9.16所示. 為了保證售貨員充分休息，售貨員每周工作5天，休息2天，并要求休息的2天是連續(xù)的，問：應(yīng)該如何安排售貨員的作息時(shí)間，既滿足工作需要，又使配備的售貨員人數(shù)最少？,表9.16 售貨人員需求統(tǒng)計(jì)表,時(shí)間,所需售貨員人數(shù),星期日,28,星期一,15,星期二,24,星期三,25,星期四,19,星期五,31,星期六,28,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,96,【解】 設(shè)x,j,為星期j開始休息的人數(shù)（j=1,2,，分別對(duì)應(yīng)星期一、二、三、四、五、

46、六、日）.目標(biāo)是要求售貨員的總數(shù)最少.因?yàn)槊總€(gè)售貨員都工作5天，休息2天，所以只要計(jì)算出連續(xù)休息2天的售貨員數(shù)，也就計(jì)算出了售貨員的總數(shù).,這里可以把連續(xù)休息2天的售貨員按照開始休息的時(shí)間分成7類，各類的人數(shù)分別為 x,j,（j=1,2,，），即有目標(biāo)函數(shù)：,再按照每天所需售貨員的人數(shù)寫出約束條件. 例如星期日需要28人，商場(chǎng)中的全體售貨員中除了星期六和星期日開始休息的人外都應(yīng)該上班，即有約束條件,9.6 線性規(guī)劃的應(yīng)用,10/22/2024,97,同理有,因x,j,（j=1,2,，）表示人數(shù)，故有,x,j, j=1,2,，） ，且為整數(shù),9.6 線性規(guī)劃的應(yīng)用,綜上得問題的線性規(guī)劃模型為：,

47、10/22/2024,98,9.6 線性規(guī)劃的應(yīng)用,計(jì)算結(jié)果： 也就是說該商場(chǎng)至少需要售貨員36人.他們的的休息安排為：,星期一 12人；星期三 11人；星期五 5人；星期日 8人.,10/22/2024,99,一、對(duì)偶問題的提出,線性規(guī)劃的,對(duì)偶原理,對(duì)偶是什么：對(duì)同一事物（或問題），從不同的角度（或立場(chǎng)）提出對(duì)立的兩種不同的表述。,對(duì)偶思想舉例,在平面內(nèi)，矩形的面積與其周長(zhǎng)之間的關(guān)系，有兩種不同的表述方法。,（1）周長(zhǎng)一定，面積最大的矩形是正方形。,（2）面積一定，周長(zhǎng)最短的矩形是正方形。,10/22/2024,100,二、原問題和對(duì)偶問題的關(guān)系,1,、對(duì)稱形式的對(duì)偶關(guān)系,（,1,）定義：

48、若原問題是,10/22/2024,101,則定義其對(duì)偶問題為,這兩個(gè)式子之間的變換關(guān)系稱為“,對(duì)稱形式的對(duì)偶關(guān)系,”,。,10/22/2024,102,（,2,）對(duì)稱形式的對(duì)偶關(guān)系的矩陣描述,（D）,（L）,（3）怎樣從原始問題寫出其對(duì)偶問題？,按照定義；,記憶法則：,“上、下”交換，“左、右”換位，,不等式變號(hào)，“極大”變“極小”,10/22/2024,103,例 寫出下面線性規(guī)劃的對(duì)偶問題：,2,、非對(duì)稱形式的對(duì)偶關(guān)系：,10/22/2024,104,（1） 原問題 對(duì)偶問題,（特點(diǎn)：對(duì)偶變量符號(hào) 不限，系數(shù)陣轉(zhuǎn)置）,(,特點(diǎn)：等式約束,),10/22/2024,105,（,2,）怎樣寫出

49、非對(duì)稱形式的對(duì)偶問題？,把一個(gè)等式約束寫成兩個(gè)不等式約束，再根據(jù)對(duì)稱形式的對(duì)偶關(guān)系定義寫出；,按照原始-對(duì)偶表直接寫出,；,（,3,）原始,-,對(duì)偶表,10/22/2024,106,原問題（或?qū)ε紗栴}）,對(duì)偶問題（或原問題）,目標(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è)約束條件類型為“,=,”,10/22/2024,107,練習(xí)：寫出下面線性規(guī)劃的對(duì)偶規(guī)劃：,10/22/2024,108,下面的答案哪一個(gè)是正確的？為什麼？,（原問題是極小化問題，因此,應(yīng)從原始對(duì)偶表的,右邊,往,左邊,查！,）,10/22/2024,109,