運(yùn)籌學(xué)-第1章線性規(guī)劃與對(duì)偶問題

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

16、立總租借費(fèi)用最小的租借計(jì)劃。,2024/3/21,25,分析,,,,12 20 15 10,xij( i =1,2,3,4; j =1,2,3,4)第i月月初簽訂租借期為j個(gè)月的合同租借面積,租借期,,,,,,,,,,,,2024/3/21,26,xij( i =1,2,3,4; j =1,2,3,4)第i月月初簽訂租借期為j個(gè)月的合同租借面積資金數(shù),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 人員安排計(jì)劃 某晝夜服務(wù)的公交線路每天各時(shí)間區(qū)段所需司機(jī)和乘務(wù)人員數(shù)如表1-6所示。設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間區(qū)段一開始時(shí)上班，并連續(xù)工作8h，問該公交線路至少需配備多少名司機(jī)和乘務(wù)人員。,2024/3/21,28,設(shè)xi ，yi (i＝1，2，…，6)分別表示第i班次開始上班的司機(jī)和乘務(wù)員人數(shù)，,,2024/3/21,29,線性規(guī)劃模型特點(diǎn),決策變量：向量X=(x1… xn)T 決策人要考慮

19、和控制的因素，非負(fù)約束條件：關(guān)于X的線性等式或不等式目標(biāo)函數(shù)：Z=?(x1 … xn) 為關(guān)于X 的線性函數(shù)，求Z極大或極小,2024/3/21,30,一般式,Max(min)Z=c1x1+ c2x2+…+cnxn s.t.,2024/3/21,31,2024/3/21,32,隱含的假設(shè),比例性：決策變量變化引起目標(biāo)的改變量與決策變量改變量成正比可加性：每個(gè)決策變量對(duì)目標(biāo)和約束的影響?yīng)毩⒂谄渌兞窟B續(xù)性：每個(gè)決策變量取連續(xù)

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

21、，污水管理，服務(wù)系統(tǒng)設(shè)計(jì)、運(yùn)用),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,,,,,,,,,可行域,目標(biāo)函數(shù)等值線,最優(yōu)解,6,4,-8,

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

24、3) 無窮多最優(yōu)解例8 maxZ = 100x1 +200x2 s.t.,這兩條直線是平行的,,2024/3/21,40,結(jié)論解的幾種情況：最優(yōu)解（唯一和無窮），無最優(yōu)解（無解和目標(biāo)無界）。LP的可行解存在，則可行解域是一個(gè)凸集。,,,,凸集,凸集,不是凸集,極點(diǎn),,,2024/3/21,41,LP有最優(yōu)解，則最優(yōu)解或最優(yōu)解之一必在可行解域的凸集的頂點(diǎn)上達(dá)到。可行解域的一個(gè)頂點(diǎn)是最優(yōu)解的充分條件

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

26、討論5、注意的問題,2024/3/21,44,1、線性規(guī)劃的標(biāo)準(zhǔn)型,,2024/3/21,45,線性規(guī)劃的標(biāo)準(zhǔn)型定義,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,如何化標(biāo)準(zhǔn)型？要求目標(biāo)函數(shù)max 要求b非負(fù)要求x非負(fù)要求約束為等式約束舉例(對(duì)例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,,,對(duì)例1,松弛變量,2024/3/21,49,例9,這需要減一個(gè)剩余變量,2024/3/21,50,2、解的概念,可行解：滿足約束條件的解。最優(yōu)解：使目標(biāo)達(dá)到最優(yōu)的可行解?；仃嘇B （許多參考書用記號(hào)：B）基變量XB非基變量XN基解：基本可行解：基解，且非負(fù),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),,對(duì)例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),,對(duì)例1,基本可行解,,,,,,,2024/3/21,54,Sk最優(yōu),k←k+1,,存在一個(gè)極點(diǎn)So否,極點(diǎn)Sk有改善棱否,改善棱上有另一個(gè)極點(diǎn)否,極點(diǎn)Sk+1(比Sk改善),,,,,,LP無解,LP目標(biāo)無界,,,,否,否,否,,單純形算法,STEP 1,,STEP 2,,STEP 3,4,,STEP 5,,,單純

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

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

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

37、量，轉(zhuǎn)(4),2024/3/21,58,,,定xr為出基變量， 為主元，轉(zhuǎn)(5)。,由最小比值法求：,(4)選擇出基變量,,對(duì)應(yīng)變量xr,轉(zhuǎn)(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,,對(duì)例1,這個(gè)標(biāo)準(zhǔn)型中有一個(gè)明顯的基和基可行解,2024/3/21,60,,,基變量,初始基可行解,初始單純形表,,250-(0×0+0×1+0×2)=250,檢驗(yàn)數(shù)：,2024/3/21,61,,,,2024/3/21,62,,,,,2024/3/21,63,,舉例,,加入松弛變量

39、,,,所以把x3換出為非基變量，x2為換入變量即新的基變量。,,,,,,,可以看出，x1的檢驗(yàn)數(shù)為3，大于0，但是x1的系數(shù)列向量中的所有元素（-2,-1)T，都小于0，所以該題為無界解.,加入松弛變量,舉例,,,此時(shí)所有的檢驗(yàn)數(shù)都小于等于0，所以該解為最優(yōu)解。,最優(yōu)解為X＝（9/4，25/4，0，0）T，Z*＝63,非基變量x4的檢驗(yàn)數(shù)＝0，那么該LP問題有無窮多個(gè)最優(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,練習(xí) max z = 50 x1 + 100 x2 s.t. x1 + x2 ≤300 2 x1 + x2 ≤ 400

41、 x2 ≤ 250 x1 , x2 ≥ 0先標(biāo)準(zhǔn)化： 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（松弛標(biāo)量，表示原料A有50個(gè)單位的剩余）,,,,2024/3/21,75,注意：?jiǎn)渭冃畏ㄖ校?1、每一步運(yùn)算只能用矩陣初等行變換； 2、表中第b列的數(shù)總應(yīng)保持非負(fù)（≥ 0）； 3、當(dāng)所有檢驗(yàn)數(shù)均非正（≤

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

44、可行解。在實(shí)際問題中有些模型并不含有單位矩陣，為了得到一組基向量和初始基可行解，在約束條件的等式左端加一組虛擬變量，得到一組基變量。這種人為加的變量稱為人工變量，構(gòu)成的可行基稱為人工基，用大M法或兩階段法求解，這種用人工變量作橋梁的求解方法稱為人工變量法。,,不存在單位矩陣，如何構(gòu)造初始可行基？,2024/3/21,78,4、單純形算法的進(jìn)一步討論—兩階段法和大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、助問題的目標(biāo)函數(shù)ω=0, 也即人工變量都等于0，則進(jìn)入第二階段。 否則, 原問題無可行解。第二階段：去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，此時(shí)，就能得到原問題的初始單純形表。 繼續(xù)用單純形法求解即可。,2024/3/21,81,練習(xí) ： max z = -3x1 +x3,x1 +x2 +x3 ? 4-2x1 +x2 -x3 ? 1 3x2 +x3 =9x1 ，x2 ，x3?0,,s.t.,標(biāo)準(zhǔn)化,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,練習(xí)：,,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.,例：,構(gòu)造第一階段問題并求解,解：,用單純形法求解

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,,兩階段法,第二階段,將去掉人工變量，還原目標(biāo)函數(shù)系數(shù)，做出初始單純形表。,,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)解為目標(biāo)函數(shù)值 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.,建立一個(gè)新問題,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.,目標(biāo)函數(shù)中添加“罰因子”M（M是任意大的正數(shù)）為人工變量系數(shù)，只要人工變量>0，則目標(biāo)函數(shù)不可能實(shí)現(xiàn)最優(yōu)。,,判定無解條件：當(dāng)進(jìn)行到最優(yōu)表時(shí)，仍有人工變量在基中，且≠0，則說明原問題無可行解。,2024/3/21,94,練習(xí) ： 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,標(biāo)準(zhǔn)化,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.,目標(biāo)函數(shù)中添

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

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

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

57、Method)。,實(shí)例：某家電廠利用現(xiàn)有資源生產(chǎn)兩種產(chǎn)品， 有關(guān)數(shù)據(jù)如下表：,一、對(duì)偶問題的提出,如何安排生產(chǎn)，使獲利最多？,廠家,設(shè) Ⅰ產(chǎn)量––––– Ⅱ產(chǎn)量–––––,若廠長(zhǎng)決定不生產(chǎn)甲和乙型產(chǎn)品，決定出租機(jī)器用于接受外加工，只收加工費(fèi)，那么3種設(shè)備的機(jī)時(shí)如何定價(jià)才是最佳決策？,設(shè)：設(shè)備A —— 元／時(shí) 設(shè)備B –––– 元／時(shí) 調(diào)試工序 ––––

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

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

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

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

62、31,對(duì)例1,max Z= 100x1 +250x2 x1 ? 12 x2 ? 8 x1 + 2x2 ? 20 x1，x2 ? 0,X*=(4, 8), 求對(duì)偶問題的最優(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）求對(duì)偶問題的最優(yōu)解。,練習(xí),s.t.,2024/3/21,133,練習(xí),線性規(guī)劃的原問題存在可行解，則其對(duì)偶問題也一定存在可行解。( )線性規(guī)劃的對(duì)偶問題無可行解，則原問題也一定無可行解。 ( )在互為對(duì)偶的一對(duì)原問題和對(duì)偶問題中，不管原問題是求極大或極小，原問題可行解

64、的目標(biāo)函數(shù)值一定不超過其對(duì)偶問題可行解的目標(biāo)函數(shù)值。 ( )任何線性規(guī)劃問題具有唯一的對(duì)偶問題。 ( ),2024/3/21,134,練習(xí),已知線性規(guī)劃利用對(duì)偶理論證明: z≤1.,,2024/3/21,135,甲, 乙各生產(chǎn)多少,才能使工廠獲利最大 ?,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)表的松弛變量的檢驗(yàn)數(shù)的相反數(shù)對(duì)應(yīng)相等。見例1的單純形最終表,3、利用LP的最優(yōu)表求得DLP的最優(yōu)解,,,,2024/3/21,138,檢驗(yàn)數(shù),若它是原問題的最優(yōu)解,則-CB AB-1 為對(duì)偶問題的最優(yōu)解,最終單純形表：,初始單純形表：,,,2024/3/

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

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

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

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