管理學(xué)第一章-線性規(guī)劃課件

運籌學(xué)——管理科學(xué)與工程系經(jīng)濟與管理學(xué)院浙江科技學(xué)院經(jīng)濟管理學(xué)院管工系課堂要求1.要求學(xué)生上課不遲到，不早退，不得曠課；2.上課認真聽講，要求每位同學(xué)都做筆記；3.上課不得講話，看書，玩手機等與課堂無關(guān)的內(nèi)容；4.課后要求獨自完成作業(yè)，不得抄襲或不做課后作業(yè)。11/27/20232參考資料1.胡運權(quán)主編，運籌學(xué)教程（第三版），清華大學(xué)出版社；2.周華任主編，運籌學(xué)解題指導(dǎo)，清華大學(xué)出版社；3.運籌學(xué)習題集（修訂版），清華大學(xué)出版社；4.熊偉編著，運籌學(xué)，機械工業(yè)出版社；5.運籌學(xué)——數(shù)據(jù)、模型、決策，科學(xué)出版社。11/27/20233前言—運籌學(xué)簡介運籌學(xué)是管理科學(xué)的重要理論基礎(chǔ)和應(yīng)用手段，是管理專業(yè)的重要專業(yè)基礎(chǔ)課程之一。運籌學(xué)根據(jù)管理問題的環(huán)境條件和決策要求，建立相應(yīng)的數(shù)學(xué)模型，利用數(shù)學(xué)模型對實際問題進行分析和求解，經(jīng)過分析和比較，得到適合實際問題的方案。求解結(jié)果….求解結(jié)果….建立模型求解模型修改模型求解結(jié)果….修改模型實際問題數(shù)學(xué)模型11/27/20234運籌學(xué)是在第二次世界大戰(zhàn)中誕生和發(fā)展起來的。由于戰(zhàn)爭的需要，英國和美國招募了一批年輕的科學(xué)家和工程師，在軍隊將軍的領(lǐng)導(dǎo)下研究戰(zhàn)爭中的問題，例如大規(guī)模轟炸的效果，搜索和攻擊敵軍潛水艇的策略，兵力和軍需物質(zhì)的調(diào)運等等。這些研究在戰(zhàn)爭中取得了很好的效果。當時英國把這些研究成為“作戰(zhàn)研究”，英文是OperationalResearch，在美國稱為OperationsResearch。11/27/20235戰(zhàn)后這些研究成果逐漸公開發(fā)表，這些理論和方法被應(yīng)用到經(jīng)濟計劃，生產(chǎn)管理領(lǐng)域，也產(chǎn)生了很好的效果。這樣，OperationsResearch就轉(zhuǎn)義成為“作業(yè)研究”。我國把OperationsResearch譯成“運籌學(xué)”，非常貼切地涵蓋了這個詞作戰(zhàn)研究和作業(yè)研究兩方面的涵義。運籌學(xué)的內(nèi)容十分廣泛，包括線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、非線性規(guī)劃、圖論與網(wǎng)絡(luò)優(yōu)化、排隊論、決策理論、庫存理論等。在本課程中，結(jié)合管理學(xué)科的特點，主要介紹線性規(guī)劃、對偶問題，整數(shù)規(guī)劃、運輸問題、動態(tài)規(guī)劃、圖與網(wǎng)絡(luò)分析。11/27/20236授課主要內(nèi)容目錄：緒論（1）第一章 線性規(guī)劃（12）第二章 對偶問題（10）第三章 運輸問題（6）第五章 整數(shù)規(guī)劃（6）第七章 動態(tài)規(guī)劃（8）第八章圖與網(wǎng)絡(luò)分析（8）上課總課時：51課時課程設(shè)計1周（下學(xué)期開學(xué)前）11/27/20237第一章線性規(guī)劃及單純形法1.1線性規(guī)劃問題及其數(shù)學(xué)模型1.2圖解法1.3單純形法原理1.4單純形法計算步驟1.5單純形法進一步討論11/27/20238本章學(xué)習要求能建立實際問題的數(shù)學(xué)規(guī)劃模型理解線性規(guī)劃模型的特點，標準型掌握線性規(guī)劃的圖解法及其幾何意義掌握單純形法原理掌握運用單純形表計算線性規(guī)劃問題的步驟及解法能用二階段法和大M法求解線性規(guī)劃問題。掌握任何基可行解原表及單純形表的對應(yīng)關(guān)系11/27/202391.1線性規(guī)劃問題及其數(shù)學(xué)模型舉例說明線性規(guī)劃數(shù)學(xué)模型的標準形式11/27/202310一、線性規(guī)劃問題舉例說明生產(chǎn)計劃問題配料問題背包問題運輸問題指派問題下料問題11/27/202311例1：美佳公司－生產(chǎn)計劃問題1、確定決策變量——通常由目標問題分解設(shè)x1代表生產(chǎn)Ⅰ種家電數(shù)量；x2代表生產(chǎn)Ⅱ種家電數(shù)量；2、分析并表達限制條件，包括約束條件——通常由等式或不等式表示。0x1+5x2≤156x1+2x2≤24x1+x2≤5x1≥0,x2≥03、分析目標——是利潤最大化MaxZ=2x1+x211/27/202312例2：捷運公司表1－2所需倉庫面積1、確定決策變量——通常由目標問題分解每個月有不同的租用方案，共有4個月需要租用倉庫。則：表1－3租金與期限的關(guān)系11/27/2023131.生產(chǎn)計劃問題（ProductionPlanning）某工廠擁有A、B、C三種類型的設(shè)備，生產(chǎn)甲、乙、丙、丁四種產(chǎn)品。每件產(chǎn)品在生產(chǎn)中需要占有的設(shè)備機時數(shù)，每件產(chǎn)品可以獲得的利潤以及三種設(shè)備可利用的時數(shù)如下表所示：求使得總利潤最大的生產(chǎn)計劃。設(shè)四種產(chǎn)品的產(chǎn)量分別為x1，x2，x3，x4，總利潤為z，線性規(guī)劃模型為：maxz=5.24x1+7.30x2+8.34x3+4.18x4s.t.1.5x1+1.0x2+2.4x3+1.0x4≤20001.0x1+5.0x2+1.0x3+3.5x4≤80001.5x1+3.0x2+3.5x3+1.0x4≤5000x1,x2,x3,x4≥011/27/2023142.配料問題（MaterialBlending）某工廠要用四種合金T1、T2、T3、T4為原料，經(jīng)熔煉成為新的不銹鋼G。這四種原料含鉻（Cr）、錳（Mn）和鎳（Ni）的含量（％），這四種原料的單價以及新的不銹鋼G所要求的Cr、Mn、Ni的最低含量（％）如下表：要求配100公斤不銹鋼G，并假定在配制過程中沒有損耗。求使得總成本最低的配料方案。設(shè)四種原料分別選取x1，x2，x3，x4公斤，總成本為z。minz=115x1+97x2+82x3+76x4s.t.3.21x1+4.53x2+2.19x3+1.76x4≥3.20Cr的含量下限約束2.04x1+1.12x2+3.57x3+4.33x4≥2.10Mn的含量下限約束5.82x1+3.06x2+4.27x3+2.73x4≥4.30Ni的含量下限約束x1+x2+x3+x4=100物料平衡約束x1,x2,x3,x4≥011/27/2023153.背包問題（KnapsackProblem）一只背包最大裝載重量為50公斤?，F(xiàn)有三種物品，每種物品數(shù)量無限。每種物品每件的重量、價格如下表：求背包中裝入每種物品各多少件，使背包中物品總價值最高。設(shè)三種物品的件數(shù)各為x1，x2，x3件，總價值為z。maxz=17x1+72x2+35x3s.t.10x1+41x2+20x3≤50x1，x2，x3≥0x1，x2，x3為整數(shù)這是一個整數(shù)規(guī)劃問題（IntegerProgramming）。這個問題的最優(yōu)解為：x1=1件，x2=0件，x3=2件，最高價值z=87元11/27/2023164.運輸問題（Transportation）某種物資從兩個供應(yīng)地A1，A2運往三個需求地B1，B2，B3。各供應(yīng)地的供應(yīng)量、各需求地的需求量、每個供應(yīng)地到每個需求地每噸物資的運輸價格如下表：求總運費最低的運輸方案。A1A2B3B2B135噸25噸10噸30噸20噸23547811/27/202317設(shè)從兩個供應(yīng)地到三個需求地的運量（噸）如下表：minz=2x11+3x12+5x13+4x21+7x22+8x23s.t.x11+x12+x13=35供應(yīng)地A1x21+x22+x23=25供應(yīng)地A2x11+x21=10需求地B1x12+x22=30需求地B2x13+x23=20需求地B3x11,x12,x13,x21,x22,x23≥011/27/202318這個問題的最優(yōu)解表示如下：最小總運費為：z=3×30+5×5+4×10+8×15=275元A1A2B3B2B135噸25噸10噸30噸20噸23547830噸5噸10噸15噸11/27/2023195.指派問題（AssignmentProblem）有n項任務(wù)由n個人完成，每項任務(wù)交給一個人，每人都有一項任務(wù)。由i個人完成j項任務(wù)的成本（或效益）為cij。求使總成本最?。ɑ蚩傂б孀畲螅┑姆峙浞桨?。設(shè)：11/27/202320張、王、李、趙四位老師被分配教語文、數(shù)學(xué)、物理化學(xué)四門課程，每位老師教一門課，每門課由一位老師教。根據(jù)這四位老師以往教課的情況，他們分別教四這門課程的平均成績?nèi)缦卤怼Ｒ蟠_定哪一位老師上哪一門課，使四門課的平均總成績最高。設(shè)：11/27/202321設(shè)：maxz=92x11+68x12+85x13+76x14+82x21+91x22+77x23+63x24+83x31+90x32+74x33+65x34+93x41+61x42+83x43+75x44s.t. x11+x12+x13+x14=1(1)x21+x22+x23+x24=1(2)x31+x32+x33+x34=1(3)x41+x42+x43+x44=1(4)x11+x21+x31+x41=1(5)x12+x22+x32+x42=1(6)x13+x23+x33+x43=1(7)x14+x24+x34+x44=1(8)xij=0,111/27/2023226.下料問題

現(xiàn)將1m長的鋼切成A＝0.4m,B=0.3m，C=0.2m長的三種鋼，其中A，B，C三種鋼分別需要20根，45根和50根，問如何進行切割使得需要的1m鋼為最少？解：將1m的鋼分別切成A，B，C三種鋼的可能方案如下：設(shè)第i種方案進行切割的1m鋼的為xi根；minZ=0.1x3+0.1x5+0.1x7s.t.2x1+x2+x3+x4≥202x2+x3+3x5+2x6+x7≥45x1+x3+3x4+2x6+3x7+5x8≥50xi≥0(i=1,2……8)11/27/202323小結(jié)線性規(guī)劃問題要求目標函數(shù)和約束方程必須是線性函數(shù)，隱含如下假定：比例性假定：每個決策變量對目標函數(shù)的貢獻與決策變量的值成比例。每個變量對約束條件左端的貢獻與變量的值成比例；可加性假定：任何變量對目標函數(shù)的貢獻都與其他決策變量的值無關(guān)。一個變量對每個約束條件左端的貢獻與該變量的值無關(guān)。連續(xù)性假定（可除性假定）：允許每個決策變量值使用分數(shù)值。確定性假定：已經(jīng)確切知道每個參數(shù)（價值系數(shù)，工藝系數(shù)，右側(cè)常數(shù)）線性規(guī)劃數(shù)學(xué)模型三個要素：決策變量目標函數(shù)約束條件11/27/202324課堂習題P451.131.14(1)課后作業(yè)P461.14(2)1.1511/27/202325二、線性規(guī)劃模型標準形式min(max)z=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn≥(≤,＝)b1a21x1+a22x2+……+a2nxn≥(≤,＝)b2……am1x1+am2x2+……+amnxn≥(≤,＝)bmx1,x2,……,xn≥0(≤,Free)線性規(guī)劃模型的目標函數(shù)必須是變量的線性函數(shù)，約束條件必須是變量的線性等式或不等式。如右的問題就不是線性規(guī)劃問題：1.一般形式11/27/2023262.線性規(guī)劃的標準形式目標函數(shù)為極大化，約束條件全部為等號約束，所有變量全部是非負的，這樣的線性規(guī)劃模型稱為標準形式maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥011/27/2023273.線性規(guī)劃模型用矩陣和向量表示maxz=c1x1+c2x2+……+cnxns.t.a11x1+a12x2+……+a1nxn＝b1a21x1+a22x2+……+a2nxn＝b2……am1x1+am2x2+……+amnxn＝bmx1,x2,……,xn≥0價值系數(shù)工藝系數(shù)矩陣資源約束11/27/202328線性規(guī)劃模型用矩陣和向量表示（續(xù)）因此，線性規(guī)劃模型可以寫成如下矩陣和向量的形式MaxZ=CXs.t.AX=bX≥011/27/2023294.線性規(guī)劃模型總結(jié)線性規(guī)劃模型的結(jié)構(gòu)目標函數(shù)：max，min約束條件：≥,=,≤變量符號：：≥0,≤0,Free線性規(guī)劃的標準形式目標函數(shù)：max約束條件 ：=變量符號 ：≥0MaxZ=CXs.t.AX=bX≥0

11/27/2023305.線性規(guī)劃問題的標準化極小化目標函數(shù)轉(zhuǎn)化為極大化小于等于約束條件轉(zhuǎn)化為等號約束大于等于約束條件轉(zhuǎn)化為等號約束變量沒有符號限制（Free）的標準化變量小于等于0的標準化11/27/202331minz=2x1-3x2+x3令z’=-z，z’=-2x1+3x2-x3新的目標函數(shù)maxz’=-2x1+3x2-x3取得極小化的最優(yōu)解時，這個最優(yōu)解同時使原目標函數(shù)值取得最大化的最優(yōu)解。但兩個問題最優(yōu)解的目標函數(shù)值相差一個負號。極小化目標函數(shù)問題轉(zhuǎn)化為極大化目標函數(shù)例如，對于以下兩個線性規(guī)劃問題Maxz=2x1+3x2s.t.x1+x2≤3x2≤1(A)x1,x2≥0Minz’=-2x1-3x2s.t.x1+x2≤3x2≤1(B)x1,x2≥0它們的最優(yōu)解都是x1=2,x2=1，但(A)的最大化的目標函數(shù)值為maxz=7，(B)的最小化的目標函數(shù)值為minz’=-711/27/2023322x1+3x2-4x3≤5引進松弛變量(Slackvariable)x4≥02x1+3x2-4x3+x4=5如果有一個以上小于等于約束，要引進不同的松弛變量。例如：2x1+3x2-4x3≤53x1-2x2+5x3≤8在兩個約束中分別引進松弛變量x4，x5≥02x1+3x2-4x3+x4=53x1-2x2+5x3+x5=8小于等于約束條件轉(zhuǎn)化為等號約束大于等于約束條件轉(zhuǎn)化為等號約束將不等式約束變?yōu)榈仁郊s束。例如：2x1+3x2-4x3≥53x1-2x2+5x3≥8在兩個約束的左邊分別減去剩余變量x4，x5≥02x1+3x2-4x3-x4=53x1-2x2+5x3-x5=811/27/202333沒有符號限制的變量，用兩個非負變量之差表示。例如：minz=x1+2x2-3x3s.t.2x1+3x2-4x3≤53x1-2x2+5x3≥8x1≥0,x2:free,x3≥0先將目標函數(shù)轉(zhuǎn)化為極小化，并在約束中引進松弛變量，把不等式約束變?yōu)榈仁健axz’=-x1-2x2+3x3s.t.2x1+3x2-4x3+x4=53x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0變量沒有符號限制(Free)的標準化11/27/202334 Maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8x1≥0,x2:free,x3,x4,x5≥0然后，令x2=x2’-x2”，其中x2’,x2”≥0。代入模型，消去x2 Maxz’=-x1-2(x’2-x”2)+3x3 s.t.2x1+3(x’2-x”2)-4x3+x4=5 3x1-2(x’2-x”2)+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥0整理，得到標準形式： Maxz’=-x1-2x’2+x”2+3x3 s.t.2x1+3x’2-3x”2-4x3+x4=5 3x1-2x’2+2x”2+5x3-x5=8 x1,x’2,x”2,x3,x4,x5≥011/27/202335 minz=x1+2x2-3x3 s.t.2x1+3x2-4x3≤5 3x1-2x2+5x3≥8 x1≥0,x2≤0,x3≥0 maxz’=-x1-2x2+3x3 s.t.2x1+3x2-4x3+x4=5 3x1-2x2+5x3-x5=8 x1≥0,x2≤0,x3,x4,x5≥0令x2=-x’2，x’2≥0,代入模型 maxz’=-x1+2x’2+3x3 s.t.2x1-3x’2-4x3+x4=5 3x1+2x’2+5x3-x5=8 x1≥0,x’2≥0,x3,x4,x5≥0變量小于等于0的的標準化11/27/202336課堂習題P431.211/27/2023371.2圖解法相關(guān)概念和圖解法步驟線性規(guī)劃問題圖解法求解的幾種結(jié)果結(jié)論11/27/202338模型中只有兩個變量的線性規(guī)劃問題，可以通過在平面上作圖的方法求解?？尚薪猓阂粋€線性規(guī)劃問題有解，是指能找出一組xj(j=1,2……,n)滿足約束條件，稱這組xj為問題的可行解?？尚杏颍和ǔ＞€性規(guī)劃問題總是含有多個可行解，全部可行解的集合為可行域。最優(yōu)解：可行域中使目標函數(shù)為最優(yōu)的可行解為最優(yōu)解。圖解法的步驟：建立坐標系，確定比例尺；畫出各約束條件的邊界，定出可行域；畫出目標函數(shù)的一根等值線，平移得出最優(yōu)解；算出目標函數(shù)最優(yōu)值。1.相關(guān)概念和圖解法步驟11/27/202339線性規(guī)劃的圖解max z=x1+3x2s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目標函數(shù)等值線最優(yōu)解654321123456-8-7-6-5-4-3-2-10x1x2z=6z=3z=9z=12問題：1、線性規(guī)劃的最優(yōu)解是否可能位于可行域的內(nèi)部？2、線性規(guī)劃的最優(yōu)解是否可能位于可行域的邊界上？11/27/202340唯一最優(yōu)解無窮多最優(yōu)解無界解（→可行域無界）無解（無可行解）2.線性規(guī)劃問題圖解法求解的幾種結(jié)果1、唯一最優(yōu)解（封閉）2、多個最優(yōu)解（封閉）3、唯一最優(yōu)解（開放）4、多個最優(yōu)解（開放）5、目標函數(shù)無界（開放）6、無可行解11/27/202341線性規(guī)劃問題解的形式:唯一最優(yōu)解，無窮多最優(yōu)解，無界解，無可行解；若LP的可行域存在，即有可行解，則可行域是一個凸集；若LP的最優(yōu)解存在，則一定可以在可行域的某個頂點達到，如果在某兩個頂點上達到最優(yōu)，則該LP有無窮多最優(yōu)解；用圖解法求解LP時，如果可行域封閉，可比較可行域的頂點的目標函數(shù)值，得到最優(yōu)解；注意用圖解法如果可以得到封閉的可行域，則定有最優(yōu)解存在；如果可行域不封閉，則解的三種形式都可能出現(xiàn)，必須用目標函數(shù)等值線的平移來判斷。3.結(jié)論11/27/202342舉例：1.maxZ=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0唯一最優(yōu)解2.maxZ=x1+x2-2x1+x2≤4x1-x2≤2x1,x2≥0無界解3.maxZ=3x1+9x2x1+3x2≤22-x1+x2≤4x1,x2≥0無窮多最優(yōu)解

4.maxZ=x1+x2x1+x2≤12x1+2x2≥4x1,x2≥0無解11/27/202343課后作業(yè)P431.111/27/2023441.3單純形法原理LP解的相關(guān)概念凸集及其頂點幾個基本定理單純形法迭代原理11/27/202345x3=0x4=0max

z=x1+2x2s.t.x1+x2

3x2

1x1,x2

0max

z=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x40x1=0,x2=0x3=3,x4=1x1=0,x4=0x2=1,x3=2x2=0,x3=0x1=3,x4=1x3=0,x4=0x1=2,x2=1x1=0,x3=0x2=3,

x4=-2x2=0x1=0OABCD一.LP解的相關(guān)概念1.可行域，可行解，最優(yōu)解11/27/202346LP問題數(shù)學(xué)模型因此：可行解：滿足（1.7）（1.8）的解稱為LP的可行解；可行域：全部可行解的集合；最優(yōu)解：使目標函數(shù)(1.6)達到最大值的可行解11/27/202347定義1：從n個變量中任取m個變量xi1,xi2,…,xim，若這m個變量對應(yīng)的系數(shù)列向量Pi1,Pi2,…,Pim線性無關(guān)，即對應(yīng)系數(shù)列向量行列式≠0，則稱B=(Pi1,Pi2,…,Pim)為基矩陣，簡稱基，xi1,xi2,…,xim為基變量，其余n-m變量為非基變量。定義2：在約束方程(1.7)中，令所有非基變量為0，根據(jù)克萊姆法則，則(1.7)有唯一解。令xi1＝α1,xi2＝α2,…,xim＝αm，稱為一組基解。基可行解：滿足（1.8）中的基解為基可行解，即基解中每一分量均非負。可行基：基可行解對應(yīng)的基。退化解：基變量中有分量為0的解。線性規(guī)劃的基可行解就是可行域的頂點。2.基，基變量，非基變量；基解，基可行解，可行基11/27/202348maxz=x1+2x2s.t.x1+x2

3x2

1x1,x2

0maxz=x1+2x2s.t.x1+x2+x3=3x2

+x4=1x1,x2,x3,x4

0x1=0,x2=0x3=3,x4=1基可行解x1=0,x4=0x2=1,x3=2基可行解x2=0,x3=0x1=3,x4=1基可行解x3=0,x4=0x1=2,x2=1基可行解x1=0,x3=0x2=3,x4=-2是基解，但不是可行解OABx3=0x4=0x2=0x1=0CD可行域11/27/2023491.maxZ=2x1+3x2x1+x3＝5x1+2x2+x4＝10x2+

x5＝4xi≥0最優(yōu)解為x1＝2，x2＝4，x3＝3，Z＝1911/27/202350二.凸集和頂點1.凸集如果集合C中任意兩點x1，x2，其連線上的所有點也都是集合C中的點，則稱C為凸集，其中x1，x2的連線可以表示為：αx1＋（1－α）x2(0＜α＜1)數(shù)學(xué)解析式為：x1

∈C，x2

∈C，有αx1＋（1－α）x2∈C(0＜α＜1)，則C為凸集。2.頂點如果集合C中不存在任何兩個不同的點x1，x2，使x為這兩點連線上的一個點，稱x為頂點。對任何x1

∈C，x2

∈C，不存在x=αx1＋（1－α）x2(0＜α＜1)，則稱x為凸集的頂點。11/27/202351三.幾個基本定理定理1：若線性規(guī)劃問題存在可行解，則問題的可行域是凸集引理：線性規(guī)劃問題的可行解X＝(x1,x2,……xn)為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的（所組成的矩陣是非奇異的）。11/27/202352定理2：線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域的頂點。分兩步：1）頂點→基可行解2）基可行解→頂點反證法：1）假設(shè)X0是可行域的頂點，X0不是基可行解，X0的前k個分量大于0，其余為0，因不是基可行解，則存在所以X0不是可行域的頂點，與假設(shè)矛盾，則X0必為基可行解。11/27/2023532）假設(shè)X0是基可行解，X0不是頂點。假設(shè)X0是一個基可行解，設(shè)X0的前m個分量為正，令X0=(x1,x2,…,xm,0,…,0)T,因為不是頂點，則X0可以表示成另外兩個點X(1)，X(2)的凸組合，且P1,…,Pm線性無關(guān)。所以X不能表示成可行域中另外兩點的凸組合，與假設(shè)相矛盾，則X必為可行域的頂點。11/27/202354定理3：若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。X0為LP的最優(yōu)解，Z*=CX0，如果X0不是基可行解，則定有X(1)＝X0-ta,X(2)=X0+ta為可行解，則有CX(1)=CX0+tCa≤CX0CX(2)=CX0-tCa≤CX0則必有tCa=0所以X0，X(1)，X(2)均為最優(yōu)解，如果X(1)，X(2)不是基可行解，繼續(xù)下去，則必可以找到基可行解為最優(yōu)解。11/27/202355四.單純形法迭代原理迭代基礎(chǔ)：如果LP存在最優(yōu)解，則一定有一個基可行最優(yōu)解，且對應(yīng)LP可行域的頂點。（可行，基解，最優(yōu)）1.確定初始基可行解基解，可行解11/27/2023562.最優(yōu)性檢驗和解的判別非基變量檢驗數(shù)11/27/202357由檢驗數(shù)可以判斷解的最優(yōu)性情況（1）因為所有Xj≥0，當所有σj<0時，則Z≤Z0,則該基可行解對應(yīng)最優(yōu)解；（2）因為所有Xj≥0，當σj≤

0且存在σj＝0（j=m+1,…,n)時，則該線性規(guī)劃問題有無窮多最優(yōu)解。（3）對基可行解X0,若存在某個σk>0,且所有aik≤0(Pj≤0),i=1,2,…,m，則該問題無界。（4）因為所有Xj≥0，當存在σj>0時，則該基可行解不是最優(yōu)解，需要尋找另一個基可行解；11/27/2023583.基變換變換目的：使目標函數(shù)Z值得到改善，接近最優(yōu)解，一次基變換，是從該頂點到相鄰頂點，即一次基變換僅變換一個基變量。換入變量的確定σk>0,aik至少一個大于0，若σk=Max{σj|σj>0},則xk為換入變量。換出變量的確定令xk=θ>0,xj=0,j=m+1,…,n,j≠k則xi=bi-aik

θ≥0，i=1,…,m當aik

≤0時，θ可任??；當aik>0時，θ<則xl為換出變量。系數(shù)變換11/27/202359以alk為主元進行初等行變換11/27/202360習題1.8；1.611/27/2023611.4單純形法計算步驟求初始基可行解最優(yōu)性檢驗基變換11/27/202362單純形法原理—單純形法總結(jié)STEP0找到一個初始的基礎(chǔ)可行解，確定基變量和非基變量。轉(zhuǎn)STEP1。STEP1將目標函數(shù)和基變量分別用非基變量表示。轉(zhuǎn)STEP2。STEP2如果目標函數(shù)中所有非基變量的檢驗數(shù)全部為非正數(shù)，則已經(jīng)獲得最優(yōu)解，如果全為負數(shù)，則為唯一最優(yōu)解，運算終止。；如果有為0的非基變量檢驗數(shù)，則有無窮多最優(yōu)解。運算終止。如果有某非基變量檢驗數(shù)為正，且工藝系數(shù)全非正，則無界，運算終止。

否則，選取檢驗數(shù)為正數(shù)最大的非基變量進基。轉(zhuǎn)STEP3。STEP3選擇最小比值對應(yīng)的基變量離基，進行系數(shù)初等行變換，得新的基可行解，轉(zhuǎn)STEP1。11/27/202363一.求初始基可行解1.當約束條件為“≤”時，直接在約束不等式左邊加上非負的松弛變量，使約束方程的系數(shù)矩陣很容易找到一個單位矩陣，求出一個初始基可行解。2.當約束條件為“≥時，直接在約束不等式左邊減去非負的剩余變量，此情況下很難找到一個單位矩陣，為求出初始基可行解，為此需要引入人工變量，以方便構(gòu)成初始基可行解的一個基。為了不改變問題的性質(zhì)，對引入人工變量Xi”的線性規(guī)劃問題，需要在目標函數(shù)中減去MXi”,M為足夠大的正數(shù)，稱罰因子，促使Xi”最終必為0。3.當約束條件為”=“時，同樣需要引入人工變量，以方便構(gòu)成初始基可行解的一個基。目標函數(shù)需要減去罰因子。11/27/202364二.最優(yōu)性檢驗（1）若所有σj<0時，則已得唯一最優(yōu)解，計算終止；如果基變量中存在非0人工變量，則無解。（2）當所有σj≤

0且存在σj＝0（j=m+1,…,n)時，則已得最優(yōu)解，且有無窮多最優(yōu)解，計算終止。（3）若存在某個σk>0,且所有aik≤0(Pj≤0),i=1,2,…,m，則該問題無界，計算終止。（4）當存在σj>0時，且有aik>0,繼續(xù)第三步；11/27/202365三.基變換用單純形法按上述步驟求解時，可采用表格形式，這樣更直觀，易于避免錯誤，該表格稱為單純形表。11/27/202366例σj21000[]-45[]x1入，x4出σj01/30-1/30[]x2入，x5出3123/2[]σj000-1/4-1/2所以：X*=(x1,x2,x3)T=(7/2,3/2,15/2)TZ*=17/211/27/202367例:1.4(1)σj10500[]38/5[]x1入,x4出σj010-2[]x2入,x3出3/24σj00-5/14-25/14所以：X*=(x1,x2)T=(1,3/2)TZ*=35/2[]0:(0,0)C:(0,9/4)A:(8/5,0)B:(1,3/2)x1x2對應(yīng)0對應(yīng)A對應(yīng)B11/27/202368課堂作業(yè)1.4(1)課后作業(yè)P431.4（2）11/27/2023691.5單純形法的進一步討論一、人工變量法（大M法）約束條件：“≥”→減一個剩余變量后，再加一個人工變量“＝”→加一個人工變量目標函數(shù)：人工變量的系數(shù)為“－M”，即罰因子若線性規(guī)劃問題有最優(yōu)解則人工變量必為0。11/27/202370MaxZ=-3x1+x3x1+x2+x3≤4-2x1+x2-x3≥13x2+x3=9xi≥0,j=1,2,3增加人工變量后，線性規(guī)劃問題中就存在一個B為單位矩陣，后面可以根據(jù)我們前面所講的單純形法來進行求解。MaxZ=-3x1+x3-Mx6-Mx7x1+x2+x3+x4=4-2x1+x2-x3-x5+x6=13x2+x3+x7=9xi≥0,j=1,…,7標準化及變形11/27/202371單純形表σj-3-2M4M100[]3x2入，x6出-M041[]σj6M-304M+10-4M[]-x1入，x7出3M011[]σj0030-M-3/2[]9x3入，x1出3/2-M+1/23/2-[]σj-9/2000-M+3/4-3/4-M-1/4所以：X*=(x2,x3,x4)T=(5/2,3/2,0)TZ*=3/211/