4-運籌學B-第1章線性規(guī)劃ppt課件

1、第第1 1章章 線性規(guī)劃線性規(guī)劃OR:SM第一節(jié)第一節(jié) 線性規(guī)劃的普通模型線性規(guī)劃的普通模型一、線性規(guī)劃模型的舉例一、線性規(guī)劃模型的舉例二、二、LPLP模型的要素及特征模型的要素及特征三、線性規(guī)劃的圖解方法三、線性規(guī)劃的圖解方法四、線性規(guī)劃解的能夠性四、線性規(guī)劃解的能夠性第二節(jié)第二節(jié) 線性規(guī)劃的單純形法線性規(guī)劃的單純形法一、線性規(guī)劃的規(guī)范型式一、線性規(guī)劃的規(guī)范型式二、線性規(guī)劃之解的概念二、線性規(guī)劃之解的概念三、單純形法的根本原理三、單純形法的根本原理OR:SM第一節(jié)第一節(jié) 線性規(guī)劃的普通模型線性規(guī)劃的普通模型 線性規(guī)劃線性規(guī)劃(Linear Programming，LP)是運籌學的重要是運籌學

2、的重要分支之一，研討較早、開展較快、方法較成熟，而且是眾分支之一，研討較早、開展較快、方法較成熟，而且是眾多分支的根底，借助計算機計算更方便，運用更廣泛。多分支的根底，借助計算機計算更方便，運用更廣泛。 線性規(guī)劃通常研討資源的最優(yōu)利用、設備最正確運轉線性規(guī)劃通常研討資源的最優(yōu)利用、設備最正確運轉以及費用最低等問題。例如，當義務或目確實定后，如何以及費用最低等問題。例如，當義務或目確實定后，如何統(tǒng)籌兼顧，合理安排，用最少的資源統(tǒng)籌兼顧，合理安排，用最少的資源 如資金、設備、如資金、設備、原標資料、人工、時間等去完成確定的義務或目的；企原標資料、人工、時間等去完成確定的義務或目的；企業(yè)在一定的資源

3、條件限制下，如何組織安排消費獲得最好業(yè)在一定的資源條件限制下，如何組織安排消費獲得最好的經(jīng)濟效益如產(chǎn)品量最多的經(jīng)濟效益如產(chǎn)品量最多 、利潤最大。、利潤最大。OR:SM【例】消費方案問題?！纠肯M方案問題。 某企業(yè)在方案期內(nèi)方案消費甲、乙、丙三種產(chǎn)品。這某企業(yè)在方案期內(nèi)方案消費甲、乙、丙三種產(chǎn)品。這些產(chǎn)品分別需求在設備些產(chǎn)品分別需求在設備A、B上加工，需求耗費資料上加工，需求耗費資料C、D，按工藝資料規(guī)定，單件產(chǎn)品在不同設備上加工及所需求的按工藝資料規(guī)定，單件產(chǎn)品在不同設備上加工及所需求的資源如表資源如表1.1所示。知在方案期內(nèi)設備的加工才干各為所示。知在方案期內(nèi)設備的加工才干各為200小時，

4、可供資料分別為小時，可供資料分別為360、300公斤；每消費一件甲、乙、公斤；每消費一件甲、乙、丙三種產(chǎn)品，企業(yè)可獲得利潤分別為丙三種產(chǎn)品，企業(yè)可獲得利潤分別為40、30、50元，假定元，假定市場需求無限制。問：企業(yè)決策者應如何安排消費方案，市場需求無限制。問：企業(yè)決策者應如何安排消費方案，使企業(yè)在方案期內(nèi)總的利潤最大？使企業(yè)在方案期內(nèi)總的利潤最大？第一節(jié)第一節(jié) 線性規(guī)劃的普通模型線性規(guī)劃的普通模型 一、線性規(guī)劃模型的舉例一、線性規(guī)劃模型的舉例 OR:SM 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙丙丙現(xiàn)有資源現(xiàn)有資源設備設備A 3 1 2 200(h)設備設備B 2 2 4 200(h)材料材料C 4

5、5 1 360(kg)材料材料D 2 3 5 300(kg)利潤（元利潤（元/件）件） 40 30 50表表1.1 某企業(yè)單位產(chǎn)品資源耗費及利某企業(yè)單位產(chǎn)品資源耗費及利潤潤OR:SM321503040maxxxxZ12312312312312332200224200. . 45360235300000 xxxxxxstxxxxxxxxx，【解】設【解】設x1、x2、x3 為甲、乙、丙三種產(chǎn)品的產(chǎn)量，那為甲、乙、丙三種產(chǎn)品的產(chǎn)量，那么該線性規(guī)劃問題的數(shù)學模型為：么該線性規(guī)劃問題的數(shù)學模型為： 產(chǎn)品產(chǎn)品 資源資源 甲甲 乙乙 丙丙現(xiàn)有資現(xiàn)有資源源設備設備A 3 1 2 200設備設備B 2 2 4

6、 200材料材料C 4 5 1 360材料材料D 2 3 5 300利潤（元利潤（元/件）件） 40 30 50最優(yōu)解：最優(yōu)解：X*=(50, 30, 10)T，Z*=3400，即在方案期內(nèi)甲、乙、丙產(chǎn)，即在方案期內(nèi)甲、乙、丙產(chǎn)量分別為量分別為50、30和和10件，利潤最大，為件，利潤最大，為3400元。元。留意：最優(yōu)解的表達方式！留意：最優(yōu)解的表達方式！OR:SM二、線性規(guī)劃的三個要素二、線性規(guī)劃的三個要素 第一節(jié)第一節(jié) 線性規(guī)劃的普通模型線性規(guī)劃的普通模型 決策變量一組決策變量一組決策問題待定的量值決策問題待定的量值取值要求非負取值要求非負約束條件一組約束條件一組任何管理決策問題都是限定在

7、一定的條件下求解任何管理決策問題都是限定在一定的條件下求解把各種限制條件表示為一組等式或不等式稱約束條件把各種限制條件表示為一組等式或不等式稱約束條件約束條件是決策方案可行的保證約束條件是決策方案可行的保證約束條件是決策變量的線性函數(shù)約束條件是決策變量的線性函數(shù)目的函數(shù)一個目的函數(shù)一個衡量決策優(yōu)劣的準那么，如時間最省、利潤最大、本錢最低衡量決策優(yōu)劣的準那么，如時間最省、利潤最大、本錢最低目的函數(shù)是決策變量的線性函數(shù)目的函數(shù)是決策變量的線性函數(shù)有的目的要實現(xiàn)極大，有的那么要求極小有的目的要實現(xiàn)極大，有的那么要求極小OR:SM 產(chǎn)品產(chǎn)品設備設備工時消耗工時消耗甲甲 乙乙工時成本工時成本(元元/h)

8、生產(chǎn)能力生產(chǎn)能力(h)ABC 2 0 0 2 3 4 20 15 10161032OR:SM12121212max35216210. .3432,0Zxxxxs txxxx s.t. (subject to) 使?jié)M足，使服從使?jié)M足，使服從OR:SM練習練習1.21.2：某廠消費甲、乙兩種產(chǎn)品，均需在：某廠消費甲、乙兩種產(chǎn)品，均需在A A、B B、C C三種不同的設三種不同的設備上加工，單位產(chǎn)品加工所需工時、銷售后能獲得的利潤及設備有備上加工，單位產(chǎn)品加工所需工時、銷售后能獲得的利潤及設備有效工時數(shù)見下表。問：如何安排消費方案，才干使該廠獲得總利潤效工時數(shù)見下表。問：如何安排消費方案，才干使該廠

9、獲得總利潤最大？最大？ 解解: 設甲、乙產(chǎn)品產(chǎn)量分別設甲、乙產(chǎn)品產(chǎn)量分別 為為x1、x2 公斤，公斤， 設總利潤為設總利潤為Z，那么：，那么： max Z = 70 x130 x2 設備設備產(chǎn)品產(chǎn)品 ABC利潤利潤甲甲 乙乙3955937030限時限時 540450720 設備可用工時數(shù)限制設備可用工時數(shù)限制 3x1 + 9x2 540 5x1 + 5x2 450 9x1 + 3x2 720max Z = 70 x130 x2 3x1 + 9x2 540 s.t. 5x1 + 5x2 450 9x1 + 3x2 720 x1 , x2 0OR:SM線性規(guī)劃的數(shù)學模型由線性規(guī)劃的數(shù)學模型由決策變

10、量決策變量 Decision variables 目的函數(shù)目的函數(shù) Objective function 構成，稱為三要素。構成，稱為三要素。約束條件約束條件 Constraintsn其主要特征是：其主要特征是：n1. 處理的問題是規(guī)劃問題；處理的問題是規(guī)劃問題；n2處理問題的目的函數(shù)是多個決策變量的處理問題的目的函數(shù)是多個決策變量的n 線性函數(shù)，通常是求最大值或最小值；線性函數(shù)，通常是求最大值或最小值；n3處理問題的約束條件是多個決策變量處理問題的約束條件是多個決策變量n 的線性不等式或等式。的線性不等式或等式。怎樣區(qū)分一個模型是線性規(guī)劃模型？怎樣區(qū)分一個模型是線性規(guī)劃模型？OR:SM二、線

11、性規(guī)劃模型的舉例二、線性規(guī)劃模型的舉例 2、物資運輸問題、物資運輸問題 銷地銷地產(chǎn)地產(chǎn)地B1B2B3B4產(chǎn)量產(chǎn)量A16 32550A27 5 8 4 20A33 2 9 7 30銷量銷量20301040產(chǎn)銷平衡產(chǎn)銷平衡(產(chǎn)量等于銷量產(chǎn)量等于銷量)OR:SMx11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30 銷售平衡條件銷售平衡條件x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40 非負約束非負約束 xij0 (i=1,2,3；j=1,2,3,4) 4.5 線性規(guī)劃

12、的數(shù)學模型由三個要素組成：線性規(guī)劃的數(shù)學模型由三個要素組成：OR:SM【練習】現(xiàn)有【練習】現(xiàn)有A1，A2，A3三個產(chǎn)糧區(qū)，可供應糧食分別三個產(chǎn)糧區(qū)，可供應糧食分別為為10，8，5(萬噸萬噸)，現(xiàn)將糧食運往，現(xiàn)將糧食運往B1，B2，B3，B4四個四個地域，其需求量分別為地域，其需求量分別為5，7，8，3(萬噸萬噸)。產(chǎn)糧地到需求。產(chǎn)糧地到需求地的運價地的運價(元元/噸噸)如下表所示，問如何安排一個運輸方案，如下表所示，問如何安排一個運輸方案，使總的運輸費用最少？使總的運輸費用最少？地區(qū)地區(qū)產(chǎn)糧區(qū)產(chǎn)糧區(qū)B1B2B3B4產(chǎn)量產(chǎn)量A1326310A253828A341295需求量需求量578323/2

13、3OR:SM解：設解：設 xij (i=1,2,3；j=1,2,3,4)為為 i 個產(chǎn)糧地運往第個產(chǎn)糧地運往第 j 個需個需求地的運輸量，這樣得到以下運輸問題的數(shù)學模型：求地的運輸量，這樣得到以下運輸問題的數(shù)學模型：34333231242322211413121192428353623minxxxxxxxxxxxxZ5810343332312423222114131211xxxxxxxxxxxx3875342414332313322212312111xxxxxxxxxxxx運輸量應大于或等于零非負運輸量應大于或等于零非負)4,3,2, 13,2, 1,0jixij；B1B2B3B4產(chǎn)量產(chǎn)量A1

14、326310A253828A341295需要需要量量578323OR:SM3 3、產(chǎn)品配比問題、產(chǎn)品配比問題12120.450.920.8 100100 xxxxOR:SM 假設有假設有5種不同濃度的硫酸可選種不同濃度的硫酸可選(30%,45%,73%,85%,92%)會如何呢？會如何呢？12345123451000.30.450.730.850.920.8 100 xxxxxxxxxx 5種硫酸數(shù)量分別為種硫酸數(shù)量分別為 x1、x2、x3、x4、x5 ，有：，有：假設假設5種硫酸價錢分別為種硫酸價錢分別為400, 700, 1400, 1900, 2500元元/t，那么：那么：1234512

15、345123454007001400190025001000304507308509208 1000125mins.t., ,.,jZxxxxxxxxxxxxxxxxjOR:SM練習：某糖果廠用原料練習：某糖果廠用原料A，B，C加工成三種不同牌號的加工成三種不同牌號的糖果甲、乙、丙。知各種糖果的中糖果甲、乙、丙。知各種糖果的中A，B，C的含量要求，的含量要求，原料本錢，各種原料每月的限制用量，三種牌號糖果的單原料本錢，各種原料每月的限制用量，三種牌號糖果的單位加工費及售價如下表所示。位加工費及售價如下表所示。問該廠每月消費這三種牌號糖果各多少問該廠每月消費這三種牌號糖果各多少kg，利潤最大？，

16、利潤最大？甲甲乙乙丙丙原料成本原料成本 (元元/kg) 每月限制用量每月限制用量 (kg)A60%30%2.002000B1.502500C20%50%60%1.001200加工費加工費 (元元/kg)0.500.400.30售價售價 (元元/kg)3.402.852.25OR:SM解：設解：設xij為消費第為消費第j種糖果運用的第種糖果運用的第i種原料的數(shù)量，那么該問題的數(shù)學模型為：種原料的數(shù)量，那么該問題的數(shù)學模型為： 112131122232max3.400.502.850.40Zxxxxxx 1323331112132.250.302.0 xxxxxx 2122233132331.50

17、1.0 xxxxxx1121311222321323330.91.41.90.450.951.450.050.450.95xxxxxxxxx 111213212223313233200025001200 xxxxxxxxx 11112131121222323111213132122232331323320.6()0.3()0.2()0.5()0.6()xxxxxxxxxxxxxxxxxxxx 0,1,2,3;1,2,3ijxij最優(yōu)解：最優(yōu)解：*5801420021X3262173033012000 *5450Z 即該廠每月應消費甲種牌號糖果即該廠每月應消費甲種牌號糖果906.67kg，乙種牌

18、號糖果乙種牌號糖果4793.33kg，利潤最大為，利潤最大為5450元。元。OR:SM練習：消費某一機床需求用甲、乙、丙三種規(guī)格的軸各一根，這些練習：消費某一機床需求用甲、乙、丙三種規(guī)格的軸各一根，這些軸的規(guī)格分別是軸的規(guī)格分別是2.9、2.1和和1.5m，這些軸需求用同一種圓鋼切割而，這些軸需求用同一種圓鋼切割而成，圓鋼長度為成，圓鋼長度為7.4m。如今要制造。如今要制造100臺機床，問：最少要用多少臺機床，問：最少要用多少圓鋼來消費這些軸？圓鋼來消費這些軸？(假設切割損失不計假設切割損失不計)4、合理下料問題、合理下料問題OR:SM 方案方案規(guī)格規(guī)格12345678需求量需求量y1(2.9

19、m)21110000100y2(2.1m)02103210100y3(1.5m)10130234100總長總長7.4m0.10.30.90.01.10.20.81.4余料余料min Z = x1+x2+x3 +x4+x5 +x6+x7 +x82x1+x2+x3 +x4 1002x2+x3+3x5 +2x6 +x7 100 x1+x3 +3x4 +2x6 +3x7 +4x8 100 xj 0, j =1, 2, , 8OR:SM5、投資問題、投資問題 某投資公司在第一年初有100萬元資金，假設每年都有如下的投資方案：第一年初投入一筆資金，第二年初又繼續(xù)投入此資金的50%，第三年初就可回收第一年初

20、投入資金的兩倍。問：該投資公司應如何確定投資戰(zhàn)略才干使第六年初所擁有的資金最多？2431)2(xxxxOR:SM146532)2(xxxxx368752)2(xxxxx589722xxxxOR:SM9 , 2 , 1, 002240222402224022210098758765365431432121jxxxxxxxxxxxxxxxxxxxxxjOR:SM思索題：某人有思索題：某人有30萬元資金，在今后的三年內(nèi)有以下萬元資金，在今后的三年內(nèi)有以下4個個 投資工程可供參考，假設有錢就會用于投資。投資工程可供參考，假設有錢就會用于投資。 1.三年內(nèi)的每年年初均可投資，每年獲利為投資額的三年內(nèi)的每

21、年年初均可投資，每年獲利為投資額的20%，其本利可一同用于下一年的投資；，其本利可一同用于下一年的投資； 2.只允許第一年年初投入，第二年末可收回，本利合只允許第一年年初投入，第二年末可收回，本利合計為投資額的計為投資額的150%，但此類投資額不超越，但此類投資額不超越15萬元；萬元； 3.第二年初允許投資，可于第三年末收回，本利合計第二年初允許投資，可于第三年末收回，本利合計為投資額的為投資額的160%，這類投資限額，這類投資限額20萬元；萬元； 4. 第三年初允許投資，一年回收，可獲利第三年初允許投資，一年回收，可獲利40%，投資，投資限額為限額為10萬元。萬元。 試確定一個第三年末本利和

22、為最大的投資方案？試確定一個第三年末本利和為最大的投資方案？OR:SM 項目項目投資時間投資時間1234第第1年初年初x11x12第第2年初年初x21x23第第3年初年初x31x34OR:SM*166667 13333300X00200000010000000100000 *Z600000 OR:SMOR:SM第一節(jié)第一節(jié) 線性規(guī)劃的普通模型線性規(guī)劃的普通模型 用一組非負決策變量表示的一個決策問題；用一組非負決策變量表示的一個決策問題； 存在一組等式或不等式的線性約束條件；存在一組等式或不等式的線性約束條件； 有一個希望到達的目的，可表示成決策變量的極有一個希望到達的目的，可表示成決策變量的極

23、值線性函數(shù)。值線性函數(shù)。1 12211 11221121 1222221 12212max(min) Z( , )( , )s.t. ( , ),0 nnnnnnmmmnnmnc xc xc xa xa xa xba xa xa xba xaxaxbx xx為了書寫方便，上式也可簡寫：為了書寫方便，上式也可簡寫： 1 122111 11221111121 1222222211 1221max(min)( , )(, )( , )(, )( , )(, )0(1,2,nnnjjjnnnjjjnnnjjjnmmmnnmmjjmjjZc xc xc xc xa xa xa xba xba xa xa

24、 xba xba xaxaxba xbxjn 或或或)OR:SM11max(min)(, )1,2,0,1,2, njjjnijjijjZc xa xbimxjn或普通地，普通地，xj0，但有時，但有時xj0或或xj無符號限制。無符號限制。OR:SM線性規(guī)劃圖解法線性規(guī)劃圖解法 1、概念：、概念： 利用幾何圖形求解兩個變量線性規(guī)劃問題的方法。利用幾何圖形求解兩個變量線性規(guī)劃問題的方法。 3、求解步驟：、求解步驟： 第一步：建立平面直角坐標系；第一步：建立平面直角坐標系； 第三步：在可行域內(nèi)平移目的函數(shù)等值線，第三步：在可行域內(nèi)平移目的函數(shù)等值線， 確定最優(yōu)解及最優(yōu)目的函數(shù)值。確定最優(yōu)解及最優(yōu)目

25、的函數(shù)值。 2、特點：、特點： 簡單、直觀，但只適用于兩個變量的簡單、直觀，但只適用于兩個變量的LP問題。問題。 第二步：根據(jù)約束條件畫出可行域；第二步：根據(jù)約束條件畫出可行域；OR:SM1 1、線性規(guī)劃的可行域、線性規(guī)劃的可行域可行域：滿足一切約束條件的解的集合，可行域：滿足一切約束條件的解的集合，即由一切約束條件共同圍成的區(qū)域。即由一切約束條件共同圍成的區(qū)域。maxZ= 3x1 + 5x2 2x1 16 2x2 10 3x1+4x2 32 x10, x20s.t.2x1 =162x2 =103x1 +4 x2 =32x1x24810359OABCDOR:SM2x1 =162x2 =10 x

26、1x28103583x1 + 4x2 =320ABCD2 2、線性規(guī)劃的最優(yōu)解、線性規(guī)劃的最優(yōu)解目的函數(shù)目的函數(shù) Z = 3x1 + 5x2 代表以代表以 Z 為參數(shù)的一族平行線。為參數(shù)的一族平行線。Z=25Z=37Z=1521355Zxx (4, 5)X*=(4, 5)TZ*=37OR:SMx1x2O1020304010203040(15,10)最優(yōu)解最優(yōu)解 X* = (15,10)T最優(yōu)值最優(yōu)值 Z* = 8540221xx305 . 121xx0, 0305 .1402212121xxxxxx2143maxxxZOR:SM246x1x2246最優(yōu)解最優(yōu)解 X* = (3,1)T最優(yōu)值最優(yōu)

27、值 Z* = 5(3,1)121212123643600 xxxxxxxx, ,min Z = x1 + 2x2OR:SM3 3、線性規(guī)劃解的特性、線性規(guī)劃解的特性abcd 由線性不等式組成的可行域是凸多邊形由線性不等式組成的可行域是凸多邊形( (凸集凸集) ) 凸集：對于某一集合內(nèi)部恣意兩點連線上的點都屬于這凸集：對于某一集合內(nèi)部恣意兩點連線上的點都屬于這個集合，我們就稱這個集合為凸集。個集合，我們就稱這個集合為凸集。線性規(guī)劃問題的可行域具有有限個頂點。線性規(guī)劃問題的可行域具有有限個頂點。 目的函數(shù)最優(yōu)值一定在可行域的邊境目的函數(shù)最優(yōu)值一定在可行域的邊境( (頂點頂點) )到到達，而不能夠在

28、其區(qū)域的內(nèi)部。達，而不能夠在其區(qū)域的內(nèi)部。OR:SM凸集的概念凸集的概念 設設K K為為n n維歐氏空間的一個點集，假設維歐氏空間的一個點集，假設K K中恣意兩個點中恣意兩個點X1X1和和X2X2連線上的一切點都屬于連線上的一切點都屬于K K，那么稱，那么稱K K為凸集。為凸集。121XXXKX2X1X 設設X(x1,x2,xn); X1(u1,u2,un); X(x1,x2,xn); X1(u1,u2,un); X2(v1,v2,vn)X2(v1,v2,vn)212212212/01XXX XXXX XXXX X 21212111,2,iiiiiiiXXX XvxvuxuvXXXin OR:

29、SM四、線性規(guī)劃解的能夠性四、線性規(guī)劃解的能夠性1、獨一最優(yōu)解、獨一最優(yōu)解2、多重最優(yōu)解、多重最優(yōu)解/無窮多最優(yōu)解無窮多最優(yōu)解當乙產(chǎn)品市場價錢從當乙產(chǎn)品市場價錢從7575元下降到元下降到7474元時，模型變?yōu)椋涸獣r，模型變?yōu)椋?12121212max34216210s.t.3432,0Zxxxxxxx x2x1 =162x2 =103x1+4x2=32x1x24810258Z=24Z=32Z=12OR:SM246x1x2246X(2) (3, 1)TX(1) (1, 3)T(5,5)12121212364360,xxxxxxxx min Z=5x1+5x2具有無窮多最優(yōu)解，即多具有無窮多最優(yōu)解

30、，即多重最優(yōu)解重最優(yōu)解, 通解為：通解為： 01 ,)1 ()2() 1 (XXX例如：當=0.5時 = (x1,x2)T = 0.5(1,3)T + 0.5(3,1)T = (2,2)T OR:SM3、無界解、無界解可行域無界，目的值無限增大可行域無界，目的值無限增大(缺乏必要約束缺乏必要約束)12112max35216s.t.,0Zxxxx xOR:SM246x1x2246(1,2)121212123643600 xxxxxxxx , ,無界解無界解max Z=x1+2x2OR:SM4、無可行解：線性規(guī)劃問題的可行域是空集、無可行解：線性規(guī)劃問題的可行域是空集 (約束條件相互矛盾約束條件相

31、互矛盾)12121212max355s.t. 3424,0Zxxxxxxx xx1x2O2 4 6 8 2 4 6 8OR:SMx1x2O102030401020304050500,050305 .140221212121xxxxxxxx無可行解無可行解max Z=10 x1+4x2OR:SM12121212222000max,Zxxxxxxxx12121212222500max,Zxxxxxxxx20190312 作業(yè)：用圖解法求解以下問題作業(yè)：用圖解法求解以下問題12341212121232223120minZxxxxxxxx , ,121212121232223233340maxZxxx

32、xxxxxxx, ,OR:SM一、線性規(guī)劃的規(guī)范型一、線性規(guī)劃的規(guī)范型 1、規(guī)范型表達方式、規(guī)范型表達方式(1)代數(shù)式：代數(shù)式： 11max s.t. 0(1,2, ;1,2,) njjjnijjijjZc xa xbxjn im (2)向量式：向量式： CXpbnjjj 1jmax Zxs.t.x0 (3)矩陣式：矩陣式： max0Z CXAX = bXA：技術系數(shù)矩陣，簡稱系數(shù)矩陣；：技術系數(shù)矩陣，簡稱系數(shù)矩陣；b：可用的資源量，稱資源向量；：可用的資源量，稱資源向量；C：決策變量對目的的奉獻，稱價值向量；：決策變量對目的的奉獻，稱價值向量；X：決策變量。：決策變量。第二節(jié)第二節(jié) 線性規(guī)劃

33、問題模型線性規(guī)劃問題模型 OR:SM111211121222221212, ,)nnnmmmnnmaaaxbaaaxbAXbCc ccaaaxb ； = =( (通常通常X記為：記為： ，其中，為，其中，為約束方程的系數(shù)矩陣，約束方程的系數(shù)矩陣，m是約束方程的個數(shù)，是約束方程的個數(shù)，n是決策變量是決策變量的個數(shù)，普通情況的個數(shù)，普通情況mn，且，且r()m。T12,)nXxxx= =（max0ZCXAXbX 其中其中:OR:SM2、規(guī)范型轉換方法、規(guī)范型轉換方法(1) “目的函數(shù)求最大值。假設極小化原問題目的函數(shù)求最大值。假設極小化原問題minZ = CX，那么令，那么令 Z = Z，轉為求，

34、轉為求 maxZ = CX 。 留意：求解后復原。留意：求解后復原。 2 (2) “資源限量非負。假設某個資源限量非負。假設某個 bi 0，那么將該約束兩端同乘，那么將該約束兩端同乘 “1 ，以滿足非負性的要求。，以滿足非負性的要求。 4 (3) “約束條件為等式。對于約束條件為等式。對于 “型約束，那么在型約束，那么在“左端加上一左端加上一個非負松弛變量個非負松弛變量(slack variable) ，使其為等式。，使其為等式。 對于對于“型約束，那么在型約束，那么在“左端減去一個非負剩余變量左端減去一個非負剩余變量(Surplus variable) ，使其為等式。，使其為等式。 3 (4

35、) “決策變量非負。假設某決策變量決策變量非負。假設某決策變量 xk 為為“取值無約束取值無約束(無符無符號限制號限制)，令：，令：xk = xk xk ，(xk0, xk 0) 。 1 OR:SM【例】將以下線性規(guī)劃轉化為規(guī)范型【例】將以下線性規(guī)劃轉化為規(guī)范型(規(guī)范方式規(guī)范方式)？ 3213minxxxZ12312312312328132325300( )( )( )xxxxxxxxxxxx , , , 取取值值無無約約束束【解】【解】(1)決策變量取值決策變量取值 x3 無符號要求無符號要求(取值無約束取值無約束) ，即，即x3取正值也可取負值，規(guī)范取正值也可取負值，規(guī)范型中要求變量取值為

36、非負，所以可令：型中要求變量取值為非負，所以可令：0,33333 xxxxx其中OR:SM (3) 第二個約束條件是第二個約束條件是“號號，在，在“號左端減去剩余變量號左端減去剩余變量x5，x50， x5也稱松馳變量也稱松馳變量123123123123123min328(1)3(2)325(3)00Zxxxxxxxxxxxxxxx , , ,取取值值無無約約束束 (2) 第一個約束條件是第一個約束條件是“號號，在，在“左端參與松馳變量左端參與松馳變量 x4，x40，即化為等式；，即化為等式； (4) 第三個約束條件是第三個約束條件是“號且常數(shù)項為負數(shù)，因此在號且常數(shù)項為負數(shù)，因此在“左左邊參與

37、松馳變量邊參與松馳變量x6，x60，同時不等式兩端同乘以，同時不等式兩端同乘以“1。 (5) 目的函數(shù)是最小值，令目的函數(shù)是最小值，令Z=Z,得到得到max Z= max(Z)，即當即當Z到達最小值時到達最小值時Z到達最大值，反之亦然。到達最大值，反之亦然。 (1) x3 取值無約束取值無約束 ，令，令 x3 = x3 x3，x3, x3 0。OR:SM123123123123123min328332500Zxxxxxxxxxxxxxxx , , ,取取值值無無約約束束規(guī)范型為：規(guī)范型為： 1233456max3()000Zxxxxxxx12334123351233612334562()8()

38、332()50 xxxxxxxxxxxxxxxx xxxxxx ,OR:SM將例1.1的線性規(guī)劃問題的普通方式化為規(guī)范型？ 12121212max35216210. .3432,0Zxxxxstxxx x第二節(jié)第二節(jié) 線性規(guī)劃問題模型線性規(guī)劃問題模型 OR:SM第二節(jié)第二節(jié) 線性規(guī)劃問題模型線性規(guī)劃問題模型 12345123451234512345max350002000160200103400320,1,2,5jZxxxxxxxxxxxxxxxxxxxxxj201000201034001m nA353,510mnCOR:SM練習：將以下線性規(guī)劃模型轉練習：將以下線性規(guī)劃模型轉化為規(guī)范型？化為

39、規(guī)范型？ min Z = 3x1 x24x3 x1 2x2+ 5x3 0 2x1 + x2 3x3 450 3x1 x2 0 x10 , x20 , x3 無約束無約束解：解：令令Z= Z, x2 = x2, x3 = x3 x3, 其中：其中：x2, x3, x3 0， 約束引入剩余變量約束引入剩余變量 x4，約束，約束引入松弛變量引入松弛變量 x5，那么規(guī)范，那么規(guī)范型：型：max Z = 3x1 x2 4(x3 x3) + 0 x4 + 0 x5 x1 + 2x2 + 5(x3 x3 ) x4 = 0 2x1 x2 3(x3 3x3) + x5 = 450 3x1 + x2 = 0 x1

40、, x2, x3, x3, x4, x5 0作業(yè)：教材42頁,第8題 OR:SM二、線性規(guī)劃之解的概念二、線性規(guī)劃之解的概念 基矩陣：一個非奇特的子矩陣向量線性無關?；仃嚕阂粋€非奇特的子矩陣向量線性無關。矩陣矩陣A 中恣意一個中恣意一個 m 列的線性無關子矩陣列的線性無關子矩陣 B ，稱為一個基，稱為一個基(矩陣矩陣)。組成基的列向量稱為基向量，用組成基的列向量稱為基向量，用 Pj 表示表示 ( i = 1 , 2 , , m ) 。基變量：基變量：與基向量與基向量 Pj 相對應的變量相對應的變量 xj 稱為基變量。稱為基變量。其他的其他的 n m 個變量稱為非基變量個變量稱為非基變量(基矩

41、陣以外的列向量對應變量基矩陣以外的列向量對應變量)。1 1、線性規(guī)劃解之關系、線性規(guī)劃解之關系 基基( (本本) )解：令一切非基變量等于零，得出的獨一解。解：令一切非基變量等于零，得出的獨一解。100010001Bx3x4x5基變量是基變量是x3 , x4 , x5非基變量是非基變量是x1 , x2令非基變量令非基變量 x1 = x2 = 0，基變量取值獨，基變量取值獨一確定：一確定：x3= 16，x4= 10，x5= 32得到一個基解：得到一個基解： X = (0 , 0 , 16 , 10 , 32)T161032bOR:SM重要概念重要概念 可行解：滿足約束條件可行解：滿足約束條件AX

42、=bAX=b和和X0X0的解。的解?；? (本本) )解：令一切非基變量等于零，得出的獨一解。解：令一切非基變量等于零，得出的獨一解?；? (本本) )可行解：滿足可行解：滿足X0X0的基解。的基解?？尚谢夯尚薪鈱幕仃嚒？尚谢夯尚薪鈱幕仃?。最優(yōu)解：使目的函數(shù)最優(yōu)的基可行解，稱為最優(yōu)解。最優(yōu)解：使目的函數(shù)最優(yōu)的基可行解，稱為最優(yōu)解。最優(yōu)基：最優(yōu)解對應的基矩陣，稱為最優(yōu)基。最優(yōu)基：最優(yōu)解對應的基矩陣，稱為最優(yōu)基。OR:SM基的概念基的概念假設線性規(guī)劃問題模型系數(shù)矩陣為m行、n列(mn)，那么系數(shù)矩陣中秩為m的m行m列子矩陣，稱為基矩陣，簡稱基。 123412341234ma

43、x2322724130,1,2,3,4jZxxxxxxxxxxxxxj2 411211241A1x2x3x4x1234xxxx1234APPPP11112B1x2x21214B1x3x31111B1x4x41224B2x3x51121B2x4x62141B3x4x 基中的列向量對應的變量稱為基變量，決策變量中基變量以外的變量稱為非基變量。 OR:SM根本解根本解 對于某一確定的基，令一切非基變量為對于某一確定的基，令一切非基變量為0，由，由約束方程組約束方程組AX=b可解出可解出m個基變量的獨一解，稱個基變量的獨一解，稱為一個根本解。為一個根本解。 123412341234max2322724

44、130,1,2,3,4jZxxxxxxxxxxxxxj11112B1x2x12127213xxxx1216xx11,6,0,0TX 21214B1x3x131327413xxxx1313xx21,0,3,0TX 13410:3xBx 310,0,0, 3TX 25420/3:1/3xBx50,20/3,0,1/3TX 36410/3:1/3xBx60,0,10/3,1/3TX OR:SM根本可行解根本可行解 滿足非負條件的根本解，稱為根本可行解，根滿足非負條件的根本解，稱為根本可行解，根本可行解對應于凸多邊形的項點。本可行解對應于凸多邊形的項點。 123412341234max23227241

45、30,1,2,3,4jZxxxxxxxxxxxxxj11112B1x2x12127213xxxx1216xx11,2,0,0TX 21214B1x3x131327413xxxx1313xx21,0,3,0TX 13410:3xBx 310,0,0, 3TX 25420/3:1/3xBx50,20/3,0,1/3TX 36410/3:1/3xBx60,0,10/3,1/3TX OR:SM123412341234max2326. .2120,1,2,3,4jZxxxxxxxxstxxxxxj2,0,4,0TA6,0,3,3TB 3,2,3,2TC 0,6,0,0TD 0,6,0,0TD OR:SM

46、二、線性規(guī)劃之解的概念二、線性規(guī)劃之解的概念 2 2、線性規(guī)劃問題根本定理、線性規(guī)劃問題根本定理OR:SM二、線性規(guī)劃之解的概念二、線性規(guī)劃之解的概念 3 3、線性規(guī)劃問題的解題思緒、線性規(guī)劃問題的解題思緒 首先，找到一個初始基可行解，也就是找到一個初始首先，找到一個初始基可行解，也就是找到一個初始可行基，想方法判別這個基可行解是不是最優(yōu)解?？尚谢?，想方法判別這個基可行解是不是最優(yōu)解。 假設是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解；假設是最優(yōu)解，就得到這個線性規(guī)劃問題的最優(yōu)解； 假設判別出不是最優(yōu)解，就想法由這個可行基按一定假設判別出不是最優(yōu)解，就想法由這個可行基按一定規(guī)那么變化到下一個可行基

47、，然后再判別新得到的基可行解規(guī)那么變化到下一個可行基，然后再判別新得到的基可行解是不是最優(yōu)解；是不是最優(yōu)解； 假設還不是，再接著進展下一個可行基變化，直到得假設還不是，再接著進展下一個可行基變化，直到得到最優(yōu)解。到最優(yōu)解。 OR:SM求解線性規(guī)劃問題的思緒單純形法求解線性規(guī)劃問題的思緒單純形法求初始根本可行解求初始根本可行解判別該可行解能否最優(yōu)判別該可行解能否最優(yōu)尋覓新的根本可行解尋覓新的根本可行解終了終了是是否否OR:SM一、線性規(guī)劃問題的代數(shù)解法教材第一、線性規(guī)劃問題的代數(shù)解法教材第3232頁例題頁例題12121212max35216210. .34320,0Zxxxxstxxxx1234

48、51324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj20100A02010340011x2x3x4x5xOR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx20100A0201034001OR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx20100A02010340010002210523284x

49、xOR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx312451416215213234(5)2xxxxxxx(1)(2)(3)5141232xxx(1)(4)(5)OR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx312451416215213234(5)2xxxxxxx(1)(2)(3)5141232xxx(1)(4)(5)OR:SM123451

50、324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx(1)(4)(5)31245141621521232xxxxxxx0001111624123xxx(1)(6)(7)OR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx(1)(4)(5)31245141621521232xxxxxxx(8)(6)(7)345241454283315221433xxxxxxxx(1)14145

51、5325221433Zxxxxx2451237( )ZxxOR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj31425121621023234xxxxxxx(1)(4)(5)(8)(6)(7)345241454283315221433xxxxxxxx2451237( )ZxxOR:SM123451324125max35000216210. .34320,1,2,5jZxxxxxxxxxstxxxxj20100A02010340011x2x3x4x5x0100B0100013x4x5x1100B0200413x2x5x2

52、102B0200433x2x1xOR:SM 單純形法求解線性規(guī)劃問題的步驟：單純形法求解線性規(guī)劃問題的步驟：max0kjj (1)求出初始根本可行解求出初始根本可行解(規(guī)范化、單位基規(guī)范化、單位基)； (2)最優(yōu)性檢驗最優(yōu)性檢驗(非基變量檢驗數(shù)非正時停頓，否那么進入下一步非基變量檢驗數(shù)非正時停頓，否那么進入下一步)； (3)換基換基(迭代迭代)： 確定入基變量確定入基變量 確定出基變量確定出基變量 初等變換，求出新的根本可行解；初等變換，求出新的根本可行解；min/0liikikb aa (4)反復步驟反復步驟(2)、(3)，直到求出最優(yōu)解。，直到求出最優(yōu)解。OR:SM單純形法求解步驟舉例單純

53、形法求解步驟舉例 maxZ = 3x1 + 5x2 +0 x3 +0 x4+0 x5 2x1 + x3 = 16 2x2 + x4 = 10 3x1 +4x2 + x5 = 32 Cj比比值值CBXBb檢驗數(shù)檢驗數(shù) jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=81()imjjBijiCCaOR:SM162010050101/2012300-21x3x2x5050300-5/205-4Cj比比值值CBXBb檢驗數(shù)檢驗數(shù) jx1x2x3x4x535000檢驗數(shù)檢驗數(shù) j80014/3-2/350101/204100

54、-2/31/3x3x2x1053000-1/2-1最優(yōu)解最優(yōu)解: X*=(4,5,8,0,0)T，Z*=37OR:SM 單純形法的管理啟示單純形法的管理啟示2x1=162x2 =103x1 + 4x2 =32x1x2481259X0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T 在管理過程中，把現(xiàn)有方案作為初始方案，找到最急需求改良在管理過程中，把現(xiàn)有方案作為初始方案，找到最急需求改良的某個問題和改良方向，一次做好某個主要問題的處理與改良；一的某個問題和改良方向，一次做好某個主要問題的處理與改良；一次只處理和改良一個問題的難度最小；處理之后，再

55、尋求可以改良次只處理和改良一個問題的難度最?。惶幚碇?，再尋求可以改良的其它地方，再次改良，不斷地追求更優(yōu)。的其它地方，再次改良，不斷地追求更優(yōu)。OR:SM單純形法原理單純形法原理(1) 舉例闡明舉例闡明ppt52頁頁max. .0ZCXAXbstX121,mmnAPP PPP,AB N,TNBXXX,NBCCC,TBNBNAXB NXXBXNXb11BNXB NXB b11BNXB bB NX,TBNBNBBNNCXCCXXC XC XOR:SM單純形法原理單純形法原理(2),TBNBNBBNNZCXC CXXC XC X11BNXB bB NX11()BNNNZCB bB NXC X11(

56、)BNBNZC B bCC B N X1NNBCC B N非基變量檢驗數(shù)非基變量檢驗數(shù) 令非基變量等于令非基變量等于0，那么，那么0NX11,BZC B b XB bOR:SMCjCBCNCBXBb XBXN0XBbBNjCBCNCBXBb XBXNCBXBB-1bEB-1Nj0CN CBB-1N單純形法原理單純形法原理(單純形表單純形表)1NNBCC B N11,BZC B b XB bOR:SM12121212max2543. .28,0Zs txxxxxxx x解：引入松馳變量解：引入松馳變量x3, x4 , x5 ，化為規(guī)范方式：，化為規(guī)范方式：123451324125max25000

57、43. .280,1,2,5jZstjxxxxxxxxxxxxxOR:SM cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 0 x3 x4 x5 4 3 8 1 0 1 0 0 0 1 0 1 0 1 2 0 0 1 j 0 2 5 0 0 0 由于由于x1，x2的檢驗數(shù)均為正，且的檢驗數(shù)均為正，且x2的檢驗數(shù)的檢驗數(shù)k最大，選取最大，選取x2為為入基變量；再按最小比值入基變量；再按最小比值= min(-, 3/1, 8/2) = 3，選取，選取x4為出基變量為出基變量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 0 x3 x5

58、 4 3 1 0 1 0 0 0 1 0 1 0 j OR:SM cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 0 x3 x2 x5 4 3 2 1 0 1 0 0 0 1 0 1 0 1 0 0 -2 1 j 15 2 0 0 -5 0 由于由于x1檢驗數(shù)為正，選取檢驗數(shù)為正，選取x1為入基變量；再按最小比值為入基變量；再按最小比值 = min4/1, -, 2/1=2，選取，選取x5為出基變量。為出基變量。 cj 2 5 0 0 0 CB XB b x1 x2 x3 x4 x5 0 5 x3 x2 3 2 0 1 0 1 0 1 0 0 -2 1 j OR

59、:SM 初始根本可行解：初始根本可行解：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0 新的根本可行解：新的根本可行解：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15 新的根本可行解：新的根本可行解：X(2) = (2, 3, 2, 0, 0)T，Z(2) = 19 判別定理判別定理 1：在單純形表中目的函數(shù)求：在單純形表中目的函數(shù)求max，假設一切非，假設一切非基變量的檢驗數(shù)小于零，且基變量的檢驗數(shù)小于零，且XB取值非負，那么線性規(guī)劃問題具有取值非負，那么線性規(guī)劃問題具有獨一最優(yōu)解。獨一最優(yōu)解。OR:SM圖解法求解結果：圖解法求解結果：x1x1 = 4x

60、2 = 3x1 + 2x2 = 8x2(2, 3)x2 = -(2/5)x1 +Z/5 A (0, 0)A：X(0) = (0, 0, 4, 3, 8)T，Z(0) = 0 B (0, 3)B：X(1) = (0, 3, 4, 0, 2)T，Z(1) = 15 C C：X * = (2, 3, 2, 0, 0)T，Z* = 19 D (4, 2) E (4, 0) 0OR:SM1212121212max2424210. .2,0Zs txxxxxxxxx x解：引進松馳變量解：引進松馳變量x3, x4, x5，化為規(guī)范方式：，化為規(guī)范方式：12345123124125max2400024210