運籌學-第1章線性規(guī)劃與對偶問題

1、2024/3/21,1,運籌學OPERATIONS RESEARCH,單而芳(上海大學 管理學院 )公共郵箱 cst_shu@163.com 20150325（密碼）,2024/3/21,2,一、課程基本情況,課程名稱：運籌學 Operations Research 參考書：管理運籌學，于麗英（主編），同濟大學出版社,2012運籌學教程（第三版），胡運權（主編），清華大學出版社,2007運籌學（第三版），《運籌學

2、》教材編寫組，清華大學出版社,2005,2024/3/21,3,二、課程主要內容,緒論線性規(guī)劃運輸問題整數規(guī)劃網絡優(yōu)化（網絡規(guī)劃，網絡計劃技術）動態(tài)規(guī)劃決策分析,2024/3/21,4,三、課程考核方法,平時成績占30%，包括：課堂考勤平時作業(yè)課堂討論，練習課堂提問期末閉卷考試占70%。,2024/3/21,5,緒 論,運籌學的含義及其發(fā)展運籌學的模型化方法論,2024/3/21,6,運籌學的產生與發(fā)展

3、三個來源－軍事、管理、經濟運籌學的發(fā)展歷程 運籌學是在第二次世界大戰(zhàn)中誕生和發(fā)展起來的。由于戰(zhàn)爭的需要，英國和美國招募了一批年輕的科學家和工程師，在軍隊將軍的領導下研究戰(zhàn)爭中的問題.大規(guī)模轟炸的效果搜索和攻擊敵軍潛水艇的策略兵力和軍需物質的調運等等。 這些研究在戰(zhàn)爭中取得了很好的效果。當時英國把這些研究成為“作戰(zhàn)研究”，英文是Operational Research，在美國稱為Operations R

4、esearch。,0.1 運籌學的含義及其發(fā)展,2024/3/21,7,第二次世界大戰(zhàn)期間，“OR”成功地解決了許多重要作戰(zhàn)問題，顯示了科學的巨大物質威力，為“OR”后來的發(fā)展鋪平了道路。戰(zhàn)后這些研究成果逐漸公開發(fā)表，這些理論和方法被應用到經濟計劃，生產管理領域，也產生了很好的效果。這樣，Operations Research就轉義成為“作業(yè)研究”。 世界上不少國家已成立了致力于該領域及相關活動的專門學會，美國于1952年成立了運

5、籌學會，并出版期刊《運籌學》，世界其它國家也先后創(chuàng)辦了運籌學會與期刊，1957年成立了國際運籌學協會。運籌學在中國的發(fā)展1957年，我國科學家從《史記》中的古語“夫運籌帷幄之中、決勝千里之外”摘取“運籌”二字，把Operations Research譯成“運籌學”，非常貼切地涵蓋了這個詞作戰(zhàn)研究和作業(yè)研究兩方面的涵義 我國運籌學的主要奠基人:錢學森、華羅庚、許國志等。,2024/3/21,8,運籌學的含義及其與其他學科的關系

6、運籌學Operations Research ,簡稱OR研究如何以合理的方式，組織具有明確目標的活動的學科。研究在某一系統中，如何統籌安排，合理利用，以使該系統在某些方面的總效益達到最優(yōu)的一門學科。是由各領域的專家學者協力完成并從各領域角度出發(fā)而得出的定量解決問題的方法。,2024/3/21,9,運籌學與決策科學的關系決策科學是研究決策過程規(guī)律, 提供決策方法的科學。,決策過程可用決策問題表達如下:OPT{z(x)?x∈

7、S(?)}其中x為決策方案； S(?)為環(huán)境條件?下所有決策方案x的集合； z(x)為關于決策方案x的目標(評價)指標體系； OPT為關于z(x)的“最優(yōu)”選擇。,對于環(huán)境?下的所有可行方案x∈S(?),依據決策準則OPT，依據指標z(x)選擇“最優(yōu)”者。,2024/3/21,10,運籌學與管理科學的關系從管理的角度看，可以說運籌學是用定量方法為管理決策提供依據的一門學科。以便實現有效管理、正確決策和現代

8、化管理可簡單地歸結為一句話：“依照給定條件和目標，從眾多方案中選擇最佳方案”?，F在普遍認為，運籌學是近代應用數學的一個分支，主要是將生產、管理等事件中出現的一些帶有普遍性的運籌問題加以提煉，然后利用數學方法進行解決。運籌學已成為管理科學中最重要的組成部分之一。,2024/3/21,11,0.2 運籌學的模型化方法論,運籌學解決問題的關鍵—建立模型,2024/3/21,12,按照模型特征的分類：線性規(guī)劃整數規(guī)劃網絡規(guī)劃動態(tài)規(guī)

9、劃非線性規(guī)劃多目標規(guī)劃存貯論決策論排隊論博弈論搜索論， 等等,2024/3/21,13,運籌學模型求解的軟件介紹 EXCELMATLAB WINQSB LINDO LINGO 等等,2024/3/21,14,運籌學在管理中的應用,生產計劃：生產作業(yè)的計劃、日程表的編排、合理下料、配料問題、物料管理等庫存管理：多種物資庫存量的管理，庫存方式、庫存量等運輸問題：確定最小成本的運輸線路、物資的調撥、運輸工具的調

10、度以及建廠地址的選擇等人事管理：對人員的需求和使用的預測，確定人員編制、人員合理分配，建立人才評價體系等市場營銷：廣告預算、媒介選擇、定價、產品開發(fā)與銷售計劃制定等財務和會計：預測、貸款、成本分析、定價、證券管理、現金管理等 設備維修、更新，項目選擇、評價，工程優(yōu)化設計與管理等城市交通,2024/3/21,15,第一章 線性規(guī)劃(Linear Programming, LP),線性規(guī)劃模型圖解法及單純形算法幾何意義單純

11、形算法及擴展對偶線性規(guī)劃靈敏度分析線性規(guī)劃應用舉例軟件應用,2024/3/21,16,1.1 線性規(guī)劃模型,生產計劃模型運輸模型投資模型人員安排模型等等,2024/3/21,17,例1 生產計劃問題,2024/3/21,18,x1 ? 12 x2 ? 8 x1 + 2x2 ? 20 x1，x

12、2 ? 0,,max Z= 100x1 +250x2 s.t.,解: 設產品甲, 乙產量分別為變量 x1 ， x2,注意模型特點,這是約束條件（資源量的限制和產品數量非負的限制）,這是目標函數,2024/3/21,19,例2 運輸問題,如何安排運輸，可使總運費最?。?銷售點,工廠,2024/3/21,20,設xij為i 廠運到 j銷售點的運輸量(i ＝1,2,3， j ＝1,2,3),minZ= 7x11 + 9x12+3

13、x13+x21 +5x22 +4x23 +2x31 +4x32 +2x33 s.t.,注意模型特點,2024/3/21,21,例3 投資計劃問題。 某公司現有資金10萬元，欲制定其后三年對四個項目的投資計劃，四個項目投資要求和收益如下：項目1， 第一年至第三年每年年初投資，每年末回收本年本利111%(即投資額的111%，以下同);項目2， 第二年年初

14、投資，第三年末回收本利125%，但規(guī)定投資不超過3萬元;項目3， 第三年初投資，年末收本利120%， 但規(guī)定投資額不超過4萬元;項目4， 第一年，第二年每年初投資，次年末收本利115%。,公司應怎樣對各年各項目投資，才能使第三年末擁有的資金量(本利和)最大?,2024/3/21,22,分析,,,,,max,Xik( i =1,2,3; k =1,2,3,4)第i年初投k項目的資金數,,,,,,,,2024/3/21,23,xik(

15、i =1,2,3; k =1,2,3,4)第i年初投k項目的資金數MaxZ= 1.11x31 +1.25 x22+1.2x33+1.15x24 s.t.,2024/3/21,24,例4 租借計劃 某公司擬在下一年度的1-4月的4個月內需租用倉庫堆放物資。已知各月所需倉庫面積如表。倉庫租借費用隨合同期而定，期限越長，折扣越大，具體如表。該公司可根據需要在任何一個月初辦理租借合同，每次辦理時可簽訂各類合同。試建

16、立總租借費用最小的租借計劃。,2024/3/21,25,分析,,,,12 20 15 10,xij( i =1,2,3,4; j =1,2,3,4)第i月月初簽訂租借期為j個月的合同租借面積,租借期,,,,,,,,,,,,2024/3/21,26,xij( i =1,2,3,4; j =1,2,3,4)第i月月初簽訂租借期為j個月的合同租借面積資金數,minZ= 2000（x11 + x21+x31+x

17、41 ）+3200（x12 +x22 + x32 ） + 4200（x13 +x23 ）＋4800 x14 s.t.,x11 +x12+x13 +x14 =12x21+x22+x23 + x12 +x23+x14=20x31+x22+x32 +x13 +x23+x14 =15x41 +x32+x23 +x14 = 10 xij ? 0 ( i =1,2,3,4; j =1,2,3,4),,2024/

18、3/21,27,例5 人員安排計劃 某晝夜服務的公交線路每天各時間區(qū)段所需司機和乘務人員數如表1-6所示。設司機和乘務人員分別在各時間區(qū)段一開始時上班，并連續(xù)工作8h，問該公交線路至少需配備多少名司機和乘務人員。,2024/3/21,28,設xi ，yi (i＝1，2，…，6)分別表示第i班次開始上班的司機和乘務員人數，,,2024/3/21,29,線性規(guī)劃模型特點,決策變量：向量X=(x1… xn)T 決策人要考慮

19、和控制的因素，非負約束條件：關于X的線性等式或不等式目標函數：Z=?(x1 … xn) 為關于X 的線性函數，求Z極大或極小,2024/3/21,30,一般式,Max(min)Z=c1x1+ c2x2+…+cnxn s.t.,2024/3/21,31,2024/3/21,32,隱含的假設,比例性：決策變量變化引起目標的改變量與決策變量改變量成正比可加性：每個決策變量對目標和約束的影響獨立于其它變量連續(xù)性：每個決策變量取連續(xù)

20、值確定性：線性規(guī)劃中的參數aij , bi , ci為確定值,2024/3/21,33,LP模型應用,市場營銷(廣告預算和媒介選擇，競爭性定價，新產品開發(fā)，制定銷售計劃)生產計劃制定(合理下料，配料，“生產計劃、庫存、勞力綜合”)庫存管理(合理物資庫存量，停車場大小，設備容量)運輸問題財政、會計(預算，貸款，成本分析，投資，證券管理)人事(人員分配，人才評價，工資和獎金的確定)設備管理(維修計劃，設備更新)城市管理(供水

21、，污水管理，服務系統設計、運用),2024/3/21,34,1.2 圖解法及單純形算法幾何,圖解法舉例—例1： max Z= 100x1 +250x2 s.t. x1 ? 12 x2 ? 8 x1 + 2x2 ? 20 x1，x

22、2 ? 0,,2024/3/21,35,,,,,x2,P5,,P4,P3,P2,P1,x1,,x2=8,x1+2x2=20,x1=12,100x1+250x2=h,z= z0,,(4,8),Z*=100*4+250*8=2400,,等值線,2024/3/21,36,max z=x1+3x2s.t. x1+ x2≤6-x1+2x2≤8x1 ≥0, x2≥0,,,,,,,,,可行域,目標函數等值線,最優(yōu)解,6,4,-8,

23、6,0,x1,x2,,2024/3/21,37,(1) 無解例6 maxZ = 100x1 +200x2 s.t.,幾點說明：,這兩個約束是不相容的,2024/3/21,38,(2) 目標無界例7,maxZ= 2x1 +3x2 s.t.,x1 - x2 ? 2 -3x1 +x2 ? 3/2x1 , x2 ?0,,,約束構成無界區(qū)域，目標函數的等值線無限延伸,2024/3/21,39,(

24、3) 無窮多最優(yōu)解例8 maxZ = 100x1 +200x2 s.t.,這兩條直線是平行的,,2024/3/21,40,結論解的幾種情況：最優(yōu)解（唯一和無窮），無最優(yōu)解（無解和目標無界）。LP的可行解存在，則可行解域是一個凸集。,,,,凸集,凸集,不是凸集,極點,,,2024/3/21,41,LP有最優(yōu)解，則最優(yōu)解或最優(yōu)解之一必在可行解域的凸集的頂點上達到?？尚薪庥虻囊粋€頂點是最優(yōu)解的充分條件

25、是：在這個頂點處每條棱均不改善。從可行解域的一個頂點出發(fā)，沿著改善棱前進，有限次后會找到最優(yōu)頂點。,2024/3/21,42,Sk最優(yōu),k←k+1,,存在一個極點So否,極點Sk有改善棱否,改善棱上有另一個極點否,極點Sk+1(比Sk改善),,,,,,LP無解,LP目標無界,,,,否,否,否,,單純形算法的幾何敘述,2024/3/21,43,1.3 單純形算法及擴展,1、LP標準型2、解的概念3、單純形法4、單純形法的進一步

26、討論5、注意的問題,2024/3/21,44,1、線性規(guī)劃的標準型,,2024/3/21,45,線性規(guī)劃的標準型定義,max (min) Z=c1x1+ c2x2+…+cnxn s.t. a11x1+ a12x2+…+ a1nxn =b1 a21x1+ a22x2+…+ a2nxn=b2 … … … am1x1+ am2x2+…+ amnxn =bm xj ?0(j=1,…,

27、n),,,其中 : bi≥0,2024/3/21,46,其中 : bi≥0,其中 : b≥0,矩陣形式,2024/3/21,47,如何化標準型？要求目標函數max 要求b非負要求x非負要求約束為等式約束舉例(對例1）,2024/3/21,48,max Z=100x1 +250x2s.t. x1 +x3 =12 x2

28、 +x4 =8 x1 + 2x2 +x5 =20 x1 … x5 ?0,,max Z= 100x1 +250x2 s.t. x1 ? 12 x2 ? 8

29、 x1 + 2x2 ? 20 x1，x2 ? 0,,,對例1,松弛變量,2024/3/21,49,例9,這需要減一個剩余變量,2024/3/21,50,2、解的概念,可行解：滿足約束條件的解。最優(yōu)解：使目標達到最優(yōu)的可行解?；仃嘇B （許多參考書用記號：B）基變量XB非基變量XN基解：基本可行解：基解，且非負,AB-1 b

30、 0,X=,,令非基變量=0,2024/3/21,51,max Z= 100x1 +250x2 s.t. x1 ? 12 x2 ? 8

31、 x1 +2 x2 ? 20 x1，x2 ? 0,,,,x1,x2,,x2＝8,,x1 + 2x2 ＝ 20,,x1 ＝12,(12,0),(12,4),(4,8),(0,8),(0,0),,對例1,可行解域,最優(yōu)解,2024/3/21,52,,2024/3/21,53,max Z= 100x1 +250x2 s.t.

32、 x1 + x3 = 12 x2 + x4 =8 x1 +2 x2 + x5= 20 x1，x2 ? 0,,,,x1,x2,,x2＝8,,x1 + 2x2 ＝ 20,,x1 ＝12,(12

33、,0,0,8,8),(12,4,0,4,0),(4,8,8,0,0),(0,8,12,0,4),(0,0,12,8,20),,對例1,基本可行解,,,,,,,2024/3/21,54,Sk最優(yōu),k←k+1,,存在一個極點So否,極點Sk有改善棱否,改善棱上有另一個極點否,極點Sk+1(比Sk改善),,,,,,LP無解,LP目標無界,,,,否,否,否,,單純形算法,STEP 1,,STEP 2,,STEP 3,4,,STEP 5,,,單純

34、形法原理示意圖,,,,,,,,,,,,,,,,頂點4，最優(yōu)解,,初始頂點1,頂點2,頂點3,其實，不必搜索可行域的每一個頂點，只要從一個頂點出發(fā)，沿著使目標函數改善的方向，到達下一個相鄰的頂。如果相鄰的所有頂點都不能改善目標函數，這個頂點就是最優(yōu)頂點。用這樣的搜索策略，可以大大減少搜索頂點的個數。按照這樣的搜索策略建立的算法，叫做單純形法(simplex algorithm )。它是由美國數學家G.B.丹齊克于1947年首先提出來的

35、，是線性規(guī)劃問題的數值求解的流行技術 。,,,目標函數改善,目標函數改善,目標函數改善,單純形法的基本思想,它的理論根據是：線性規(guī)劃問題的可行域是 n維向量空間Rn中的多面凸集，其最優(yōu)值如果存在必在該凸集的某頂點處達到。頂點所對應的可行解稱為基本可行解。單純形法的基本思想是：先找出一個基本可行解，對它進行鑒別，看是否是最優(yōu)解；若不是，則按照一定法則轉換到另一改進的基本可行解,再鑒別；若仍不是，則再轉換,按此重復進行。因基本可行解的個數

36、有限，故經有限次轉換必能得出問題的最優(yōu)解。如果問題無最優(yōu)解也可用此法判別。,2024/3/21,57,3、單純形算法--基本步驟(對max問題),(1)給出初始單純形表, 確定初始基本可行解。（注意初始單純形表的特征）(2)檢驗。檢驗非基變量檢驗數 是否全? 0。 若是，停止，得到最優(yōu)解； 若否，轉(3)(3)選擇進基變量。若非基變量檢驗數有 >0，對應的系數Pk全? 0，停止，原問題目標無界。 否則選擇為進基變

37、量，轉(4),2024/3/21,58,,,定xr為出基變量， 為主元，轉(5)。,由最小比值法求：,(4)選擇出基變量,,對應變量xr,轉(2)。,(5)修正表格。以 為中心，換基迭代,2024/3/21,59,max Z=100x1 +250x2 s.t. x1 +x3 =12 x2 +x4

38、 =8 x1 + 2x2 +x5 =20 x1 … x5 ?0,,對例1,這個標準型中有一個明顯的基和基可行解,2024/3/21,60,,,基變量,初始基可行解,初始單純形表,,250-(0×0+0×1+0×2)=250,檢驗數：,2024/3/21,61,,,,2024/3/21,62,,,,,2024/3/21,63,,舉例,,加入松弛變量

39、,,,所以把x3換出為非基變量，x2為換入變量即新的基變量。,,,,,,,可以看出，x1的檢驗數為3，大于0，但是x1的系數列向量中的所有元素（-2,-1)T，都小于0，所以該題為無界解.,加入松弛變量,舉例,,,此時所有的檢驗數都小于等于0，所以該解為最優(yōu)解。,最優(yōu)解為X＝（9/4，25/4，0，0）T，Z*＝63,非基變量x4的檢驗數＝0，那么該LP問題有無窮多個最優(yōu)解,,2024/3/21,72,max Z= -2x1 +x2

40、–x3 +5x4 -22x5 s.t.,x1+ 2x4 +x5= 6 x2 +x4+4x5=3 x3 +3x4 +2x5 =10x1 , ……，x5 ?0,,例10,2024/3/21,73,練習 max z = 50 x1 + 100 x2 s.t. x1 + x2 ≤300 2 x1 + x2 ≤ 400

41、 x2 ≤ 250 x1 , x2 ≥ 0先標準化： max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2 x1 + x2 + x4 = 400 x2 + x5 = 250

42、 x1 , x2 , x3 , x4 , x5 ≥ 0,,,,2024/3/21,74,,最優(yōu)解 x1 = 50 x2 = 250 x4 = 50（松弛標量，表示原料A有50個單位的剩余）,,,,2024/3/21,75,注意：單純形法中， 1、每一步運算只能用矩陣初等行變換； 2、表中第b列的數總應保持非負（≥ 0）； 3、當所有檢驗數均非正（≤

43、0）時，得到最優(yōu)單純形表。,2024/3/21,76,幾何概念,代數概念,,約束直線,滿足一個等式約束的解,約束半平面,滿足一個不等式約束的解,約束半平面的交集：凸多邊形,滿足一組不等式約束的解,約束直線的交點,基解,可行域的極點,基本可行解,,,,,,目標函數等值線：一組平行線,目標函數值等于一個常數的解,,2024/3/21,77,4、單純形算法的進一步討論—兩階段法和大M法,前面討論了在標準型中系數矩陣有單位矩陣，很容易確定一組基

44、可行解。在實際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。,,不存在單位矩陣，如何構造初始可行基？,2024/3/21,78,4、單純形算法的進一步討論—兩階段法和大M法,s.t.,,s.t.,yi－人工變量（偽變量）,2024/3/21

45、,79,例11 min z = 4x1 + x2 +x3,2x1 +x2 +2x3 =43x1 +3x2 +x3 =3x1 ，x2 ，x3?0,,s.t.,輔助問題： min W= y1 + y2,2x1 +x2 +2x3 + y1=43x1 +3x2 +x3 + y2 =3x1 ，… x3,y1 ,y2?0,,,s.t.,人工變量,,,,2024/3/21,80,解題過程：第一階段：用單純形法求解輔助問題。 若求得輔

46、助問題的目標函數ω=0, 也即人工變量都等于0，則進入第二階段。 否則, 原問題無可行解。第二階段：去掉人工變量，還原目標函數系數，此時，就能得到原問題的初始單純形表。 繼續(xù)用單純形法求解即可。,2024/3/21,81,練習 ： max z = -3x1 +x3,x1 +x2 +x3 ? 4-2x1 +x2 -x3 ? 1 3x2 +x3 =9x1 ，x2 ，x3?0,,s.t.,標準化,x

47、1 +x2 +x3 + x4 =4-2x1 +x2 -x3 - x5 =1 3x3 + x3 =9x1 …, x5 ?0,,max z = -3x1 +x3,2024/3/21,82,,輔助問題：min w=y1 +y2,s.t.,2024/3/21,83,max z= -x1 +2x2,x1 +x2 ? 2-x1 +x2 ? 1 x2 ? 3x1 ,x2 ?0,練習：,,s.t.

48、,2024/3/21,84,第(1)階段：,min w=x6 +x7,x1 +x2 -x3 +x6 =2-x1 +x2 -x4 +x7 =1 x2 +x5 =3x1 … x7 ?0,,s.t.,例：,構造第一階段問題并求解,解：,用單純形法求解

49、,兩階段法—（第一階段、求min ω ）,,表1,,,,,1 0 0 0 -1 1 0 0 0,0 -1 0,0 0 -1,x4 x5 x6,,,,,,兩階段法—（第一階段、求min ω ）,表2,1,,,,,1 -2 2 0 -1 1 0 0 0,0 0

50、-1,0 0 -1,x4 x5 x6,,,,,,兩階段法—（第一階段、求min ω ）,表3：最終單純形表,第二階段,不含人工變量且ω=0,,兩階段法,第二階段,將去掉人工變量，還原目標函數系數，做出初始單純形表。,,1 0 0 0 -1,兩階段法,,,,,1/3 -2/3 0 -1 2/3 -4/3,,0 0,x4 x5

51、,,,,,第二階段,0 0 0 -1/3 -1/3,最優(yōu)解為目標函數值 z=2,2024/3/21,92,(2) 人工變量法（大M法）,例11 min z= 4x1 + x2 +x3,2x1 +x2 +2x3 =43x1 +3x2 +x3 =3x1 ，x2 ，x3?0,,s.t.,建立一個新問題,2024/3/21,93,min z= 4x1 + x2 +x3+My1+My2,2x1 +x2

52、+2x3 +y1=43x1 +3x2 +x3 +y2=3x1 ，……，y2?0,,,s.t.,目標函數中添加“罰因子”M（M是任意大的正數）為人工變量系數，只要人工變量>0，則目標函數不可能實現最優(yōu)。,,判定無解條件：當進行到最優(yōu)表時，仍有人工變量在基中，且≠0，則說明原問題無可行解。,2024/3/21,94,練習 ： max z= -3x1 +x3,x1 +x2 +x3 ? 4-2x1 +x2 -x3 ?

53、1 3x2 +x3 =9x1 ，x2 ，x3?0,,s.t.,2024/3/21,95,標準化,max z=-3x1+x3,x1 +x2 +x3 +x4 =4-2x1 +x2 -x3 -x5 =1 3x2 +x3 = 9x1 … x7 ?0,,s.t.,2024/3/21,96,加入人工變量,s.t.,目標函數中添

54、加“罰因子”-M為人工變量系數，只要人工變量>0，則目標函數不可能實現最優(yōu)。,約束條件：“≥”：則減去一個剩余變量后，再加一個人工變量.“＝”：則加一個人工變量.目標函數求最大：人工變量的系數為“－M”，即罰因子.若線性規(guī)劃問題有最優(yōu)解則人工變量必為0.,例題,標準化,,加入人工變量,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,2024/3/21,114,5、單純形法計算中的幾

55、個注意問題,1) 判定最優(yōu)解定理： max z問題，非基變量檢驗數? 0min z問題，非基變量檢驗數?0 2) 退化解問題3）計算中注意（1）標準型中有初始基本可行解，用單純形法求解。（2) 標準型中沒有初始基本可行解，用大M法（或者用二階段法）加人工變量，使之構成單位基。,2024/3/21,115,4) 解的幾種情況：唯一解:最優(yōu)表中非基變量檢驗數<0(max)。無窮多最優(yōu)解:最優(yōu)表中非基變量檢驗數有

56、為0者。無可行解:最優(yōu)表中人工變量在基中，且不等于0。（用大M法或兩階段法判別）目標無界：存在進基變量，其對應的系數均? 0。,,2024/3/21,116,1.4 對偶線性規(guī)劃Dual linear programming, DLP,1、對偶問題的建立2、對偶規(guī)劃性質3、利用LP的最優(yōu)表求DLP的最優(yōu)解4、經濟解釋5、對偶單純形算法,1954年美國數學家C.萊姆基提出對偶單純形法(Dual Simplex

57、Method)。,實例：某家電廠利用現有資源生產兩種產品， 有關數據如下表：,一、對偶問題的提出,如何安排生產，使獲利最多？,廠家,設 Ⅰ產量––––– Ⅱ產量–––––,若廠長決定不生產甲和乙型產品，決定出租機器用于接受外加工，只收加工費，那么3種設備的機時如何定價才是最佳決策？,設：設備A —— 元／時 設備B –––– 元／時 調試工序 ––––

58、 元／時,收購,出讓代價應不低于用同等數量的資源自己生產的利潤。,付出的代價最小，且對方能接受。,廠家,廠家能接受的條件：收購方的意愿：,出讓代價應不低于用同等數量的資源自己生產的利潤。,,,,,,廠家,對偶問題,原問題,收購,廠家,一對對偶問題,2024/3/21,122,甲, 乙各生產多少,才能使工廠獲利最大 ?,y1,y2,y3,1、對偶問題的建立,2024/3/21,123,max Z= 100

59、x1 +250x2,min W= 8y1 +5y2 +12y3,,s.t.,s.t.,2024/3/21,124,定義：,是互為對偶的線性規(guī)劃。,Dual linear programming,,s.t.,s.t.,2024/3/21,125,對一般線性規(guī)劃模型--對偶規(guī)劃建立的法則,2024/3/21,126,例13,,2024/3/21,127,例14,,2024/3/21,128,練習：,s.t.,2024/3/21,129,對稱

60、性弱對偶性: 若X*和Y* 分別是原問題（1）及對偶問題（2）的可行解，則有CX*≤bTY* LP有可行解，且目標無界，則DLP無可行解。DLP有可行解，且目標無界，則LP無可行解。LP有可行解， DLP無可行解，則LP目標無界。DLP有可行解， LP無可行解，則DLP目標無界。最優(yōu)性LP有一個可行解X， DLP有一個可行解Y，且目標值相等，則分別為LP和DLP的最優(yōu)解。,2、對偶規(guī)劃性質,2024/3/21,130,強對

61、偶性：若LP和DLP均有可行解，則兩者均有最優(yōu)解，且他們的最優(yōu)解的目標值相等。互補松馳性：每個約束的松弛變量（或者剩余變量）和該約束相對應的對偶變量的乘積為0。利用該性質可以求出DLP的最優(yōu)解。注: 在線性規(guī)劃問題的最優(yōu)解中，如果對應某一約束條件的對偶變量值為非零，則該約束條件取嚴格等式；反之如果約束條件取嚴格不等式，則其對應的對偶變量一定為零。,(b-AX) TY=0, X T(ATY-CT)=0,2024/3/21,1

62、31,對例1,max Z= 100x1 +250x2 x1 ? 12 x2 ? 8 x1 + 2x2 ? 20 x1，x2 ? 0,X*=(4, 8), 求對偶問題的最優(yōu)解。,s.t.,,2024/3/21,132,min Z= 2x1 -x2 +2x3,-x1 +

63、x2 +x3 = 4-x1 +x2 -kx3 ? 6x1 ? 0，x2 ?0, x3無約束,,其最優(yōu)解為X=（-5，0，-1）。（1）求 k值；（2）求對偶問題的最優(yōu)解。,練習,s.t.,2024/3/21,133,練習,線性規(guī)劃的原問題存在可行解，則其對偶問題也一定存在可行解。( )線性規(guī)劃的對偶問題無可行解，則原問題也一定無可行解。 ( )在互為對偶的一對原問題和對偶問題中，不管原問題是求極大或極小，原問題可行解

64、的目標函數值一定不超過其對偶問題可行解的目標函數值。 ( )任何線性規(guī)劃問題具有唯一的對偶問題。 ( ),2024/3/21,134,練習,已知線性規(guī)劃利用對偶理論證明: z≤1.,,2024/3/21,135,甲, 乙各生產多少,才能使工廠獲利最大 ?,y1,y2,y3,利用LP的最優(yōu)表求得DLP的最優(yōu)解,2024/3/21,136,max Z= 100x1 +250x2,min W= 8y1 +5y2 +12

65、y3,,s.t.,s.t.,最優(yōu)解: x1=4, x2=8, x3=8,最優(yōu)解: y1=0, y2=50, y3=100,2024/3/21,137,DLP的最優(yōu)解的變量值與LP的最優(yōu)表的松弛變量的檢驗數的相反數對應相等。見例1的單純形最終表,3、利用LP的最優(yōu)表求得DLP的最優(yōu)解,,,,2024/3/21,138,檢驗數,若它是原問題的最優(yōu)解,則-CB AB-1 為對偶問題的最優(yōu)解,最終單純形表：,初始單純形表：,,,2024/3/

66、21,139,求偏導：,對偶解y：b 的單位改變量所引起的目標函數值的改變量。yi 的大小表示: 在其他條件不變的情況下，單位第i資源變化對目標的貢獻，可以看作對資源i的一種估價，稱為影子價格。,4、經濟解釋,,2024/3/21,140,影子價格是一種邊際價格：單位資源的變化所引起的目標值的變化量。A生產線的資源影子價格y1=0說明生產能力的增加對獲利沒有影響；B生產線資源影子價格y2=50，說明B生產線增加生產能力一臺(由12臺

67、/天變?yōu)?3臺/天)，最大日利潤增加50元；檢測車間的勞動力資源影子價格y3=100，說明檢測車間每增加一位勞動力可以增加利潤100元 。影子價格可以確定資源是否充分利用。影子價格是一種機會成本，當資源的市場價格低于影子價格時，企業(yè)應買進該種資源，以擴大再生產；反之，則應將已有資源賣掉。 注意：隨著生產任務、產品結構等情況的不同，資源的影子價格也可能變化。,對線性規(guī)劃問題的求解是確定資源的最優(yōu)分配方案， 而對于對偶問題的求

68、解則是確定對資源的恰當估價，這種估價直接涉及到資源的最有效利用。,2024/3/21,141,2024/3/21,142,(1)基解,(2)基可行解,(3)對偶可行解,保持對偶可行，尋找原始可行的頂點。三個概念,單純形法思路在滿足條件(1)和(2)的前提下逐步滿足條件(3),對偶單純形法思路在滿足條件(1)和(3)的前提下逐步滿足條件(2),5、對偶單純形法,2024/3/21,143,步驟：建立初始表（對偶可行）檢驗（是否原

69、始可行）選擇出基變量選擇進基變量修正表格,2024/3/21,144,STEP1. 建立初始單純形表，滿足對偶可行。STEP2. 檢驗:若所有常數項b非負,則x*為最優(yōu)解;否則,轉下一步。STEP3.選擇出基變量。根據 bl =min {bi <0 | i=1,2,…,m} 確定第l個變量xl為出基變量;若在小于零的常數項中,若有某一系數行向量≥ 0,則此問題無界(沒有最優(yōu)解)。