線性規(guī)劃與單純形法

1、一、線性規(guī)劃問題及其數(shù)學(xué)模型一、線性規(guī)劃問題及其數(shù)學(xué)模型線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)重要分支。線性規(guī)劃在理論上比較成熟，在實(shí)用中的應(yīng)用日益廣泛與深入。特別是在電子計(jì)算機(jī)能處理成千上萬個(gè)約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了。從解決技術(shù)問題的最優(yōu)化設(shè)計(jì)到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)、軍事、經(jīng)濟(jì)計(jì)劃和管理決策等領(lǐng)域都可以發(fā)揮作用。它已是現(xiàn)代科學(xué)管理的重要手段之一。例例1.1 生產(chǎn)計(jì)劃問題（資源利用問題）生產(chǎn)計(jì)劃問題（資源利用問題） 某家具廠生產(chǎn)某家具廠生產(chǎn)桌子桌子和和椅子椅子兩種家具。兩種家具。 桌子桌子售價(jià)售價(jià)50元元/個(gè)，個(gè)，椅子椅子銷售價(jià)格銷售價(jià)格30元元/個(gè)。個(gè)。 需

2、要木工和油漆工兩種工種。需要木工和油漆工兩種工種。 生產(chǎn)一個(gè)桌子需要木工生產(chǎn)一個(gè)桌子需要木工4小時(shí)，油漆工小時(shí)，油漆工2小時(shí)。小時(shí)。 生產(chǎn)一個(gè)椅子需要木工生產(chǎn)一個(gè)椅子需要木工3小時(shí)，油漆工小時(shí)，油漆工1小時(shí)。小時(shí)。 該廠每個(gè)月可用木工工時(shí)為該廠每個(gè)月可用木工工時(shí)為120小時(shí)，小時(shí)， 油漆工工時(shí)為油漆工工時(shí)為50小時(shí)。小時(shí)。 問如何組織生產(chǎn)才能使每月的銷售收入最大？問如何組織生產(chǎn)才能使每月的銷售收入最大？1 1、問題的提出、問題的提出x1x2是問題中要確定的未知量是問題中要確定的未知量，表明規(guī)劃中的用數(shù)量表，表明規(guī)劃中的用數(shù)量表示的方案、措施，可由決示的方案、措施，可由決策者決定和控制。策者決定

3、和控制。第第1步步 -確定決策變量確定決策變量x1x2z設(shè)設(shè) 桌子的產(chǎn)量桌子的產(chǎn)量 椅子的產(chǎn)量椅子的產(chǎn)量 利潤(rùn)利潤(rùn)第第2步步 -定義目標(biāo)函數(shù)定義目標(biāo)函數(shù) Max Z = 50 x1 + 30 x2第第2步步 -定義目標(biāo)函數(shù)定義目標(biāo)函數(shù) Max Z = 50 x1 + 30 x2第第3步步 -表示約束條件表示約束條件 4x1+3x2 120（木工工時(shí)限制）（木工工時(shí)限制） 2x1+x2 50 （油漆工工時(shí)限制）（油漆工工時(shí)限制） x1，x20 （變量取非負(fù)值限制）（變量取非負(fù)值限制） 該計(jì)劃的數(shù)學(xué)模型該計(jì)劃的數(shù)學(xué)模型 max Z=50 x1+30 x2 4x1+3x2 120 2x1+ x2 5

4、0 x1, x2 0s.t.線性函數(shù)線性函數(shù)線性等式線性等式線性不等式線性不等式線性規(guī)劃線性規(guī)劃+例例1.2 簡(jiǎn)化的環(huán)境保護(hù)問簡(jiǎn)化的環(huán)境保護(hù)問題題 靠近某河流有兩個(gè)化工廠靠近某河流有兩個(gè)化工廠(見下圖見下圖)，流經(jīng)第一化，流經(jīng)第一化工廠的河流流量為每天工廠的河流流量為每天500萬立方米，在兩個(gè)工廠萬立方米，在兩個(gè)工廠之間有一條流量為每天之間有一條流量為每天200萬立方米的支流。萬立方米的支流。 第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水第一化工廠每天排放含有某種有害物質(zhì)的工業(yè)污水2萬立方米，第二化工廠每天排放這種工業(yè)污水萬立方米，第二化工廠每天排放這種工業(yè)污水1.4萬立方米。從第一化工廠排出

5、的工業(yè)污水流到第二萬立方米。從第一化工廠排出的工業(yè)污水流到第二化工廠以前，有化工廠以前，有20%可自然凈化。根據(jù)環(huán)保要求，可自然凈化。根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應(yīng)不大于河流中工業(yè)污水的含量應(yīng)不大于0.2%。 這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化這兩個(gè)工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是工廠處理工業(yè)污水的成本是1000元元/萬立方米。第萬立方米。第二化工廠處理工業(yè)污水的成本是二化工廠處理工業(yè)污水的成本是800元元/萬立方米。萬立方米。 現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理現(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應(yīng)處理多少工業(yè)污水，使這兩個(gè)工廠總的處

6、理工業(yè)污水費(fèi)多少工業(yè)污水，使這兩個(gè)工廠總的處理工業(yè)污水費(fèi)用最小。用最小。建模型之前的分析和計(jì)算建模型之前的分析和計(jì)算設(shè)：設(shè)：第一化工廠每天處理工業(yè)污水量為第一化工廠每天處理工業(yè)污水量為x1萬立方米，萬立方米，第二化工廠每天處理工業(yè)污水量為第二化工廠每天處理工業(yè)污水量為x2萬立方米萬立方米 1000200)4 .1 ()2(8 .0210002500)2(21120051xxx：工工廠廠投投污污水水的的水水質(zhì)質(zhì)要要求求第第：工工廠廠投投污污水水的的水水質(zhì)質(zhì)要要求求第第數(shù)學(xué)模型 0,4 . 126 . 18 . 018001000min212121121xxxxxxxxxz約約束束條條件件目目標(biāo)標(biāo)

7、函函數(shù)數(shù)線性規(guī)模解決的問題線性規(guī)模解決的問題 給定一定數(shù)量的人力、物力、財(cái)力等資源，給定一定數(shù)量的人力、物力、財(cái)力等資源，研究如何充分利用，以發(fā)揮其最大效果研究如何充分利用，以發(fā)揮其最大效果 已給定計(jì)劃任務(wù)，研究如何統(tǒng)籌安排，用最已給定計(jì)劃任務(wù)，研究如何統(tǒng)籌安排，用最少的人力、物力、財(cái)力去完成少的人力、物力、財(cái)力去完成線性規(guī)劃數(shù)學(xué)模型三要素：線性規(guī)劃數(shù)學(xué)模型三要素： 決策變量決策變量、目標(biāo)函數(shù)目標(biāo)函數(shù)、約束條件約束條件 每一個(gè)線性規(guī)劃問題都有一組每一個(gè)線性規(guī)劃問題都有一組決策變量決策變量 (x1, x2, , xn) , 這組決策變量的值就代表這組決策變量的值就代表 一個(gè)具體方案一個(gè)具體方案。

8、 有使用各種資源的有使用各種資源的約束條件，用等式或不等式約束條件，用等式或不等式表示表示。 有一個(gè)要達(dá)到的有一個(gè)要達(dá)到的目標(biāo)，是決策變量的線性函數(shù)目標(biāo)，是決策變量的線性函數(shù)，實(shí)現(xiàn)最大化或最小化實(shí)現(xiàn)最大化或最小化。2 2、線性規(guī)劃問題的數(shù)學(xué)模型、線性規(guī)劃問題的數(shù)學(xué)模型 一般形式一般形式線性規(guī)劃模型的表示形式線性規(guī)劃模型的表示形式 矩陣形式矩陣形式 標(biāo)準(zhǔn)形式標(biāo)準(zhǔn)形式 將一般線性規(guī)劃化成標(biāo)準(zhǔn)形將一般線性規(guī)劃化成標(biāo)準(zhǔn)形 簡(jiǎn)寫形式簡(jiǎn)寫形式max(min) Z = c1x1+c2x2+.+cnxn a11x1+a12x2+.+a1nxn (=, )b1 a21x1+a22x2+.+a2nxn (=, )

9、b2 . am1x1+am2x2+.+amnxn (=, )bm x1, x2, ., xn 0s.t.線性規(guī)劃問題的一般形式線性規(guī)劃問題的一般形式 線性規(guī)劃問題的簡(jiǎn)寫形式線性規(guī)劃問題的簡(jiǎn)寫形式njxmibxaxcZjinjjijnjjj,., ,., max2102111 max Z = CTX s.t. AX=b X 0CC價(jià)值向量?jī)r(jià)值向量bb資源向量資源向量XX決策變量向量決策變量向量線性規(guī)劃的矩陣形式線性規(guī)劃的矩陣形式a11 a12 . a1n b1 A = a21 a22 . a2n b = b2 . am1 am2 . amn bmc1 x1 0 c2 x2 0C = X = 0

10、= . cn xn 0線性規(guī)劃問題的標(biāo)準(zhǔn)形式線性規(guī)劃問題的標(biāo)準(zhǔn)形式max Z = c1x1+c2x2+.+cnxns.t. a11x1+a12x2+.+a1nxn = b1 a21x1+a22x2+.+a2nxn = b2 . am1x1+am2x2+.+amnxn = bm x1, x2, ., xn 0其中：其中：bi 0, i=1, 2,., m.四點(diǎn)要求四點(diǎn)要求:將一般線性規(guī)劃化成標(biāo)準(zhǔn)型將一般線性規(guī)劃化成標(biāo)準(zhǔn)型 求求max 等式約束等式約束 bi 0 xi 0(1) 若目標(biāo)函數(shù)是求最小值若目標(biāo)函數(shù)是求最小值: min Z = CTX 令令 Z = Z, 則則化成化成 max Z= CT

11、X注意注意: 因?yàn)橐驗(yàn)?min Z = max( Z ) 所以變換后的最優(yōu)解不變，最優(yōu)值變號(hào)。所以變換后的最優(yōu)解不變，最優(yōu)值變號(hào)。(2) 若約束條件是不等式若約束條件是不等式1)若約束條件是若約束條件是“ ” 不等式，不等式， 則不等式左邊則不等式左邊 “加上加上” 非負(fù)的非負(fù)的松馳變量松馳變量；如：如：2X1+2X212 令令X3=12-2X1-2X2 則有則有2X1+2X2+X3=12 2)若約束條件是若約束條件是“ ” 不等式，不等式， 則不等式左邊則不等式左邊 “減去減去” 非負(fù)的非負(fù)的松馳變量松馳變量。如：如：10X1+12X218 令令X4=10X1+12X2-18則有則有10X1

12、+12X2-X4 =18 為了使添加松馳變量不影響原來的目標(biāo)，添為了使添加松馳變量不影響原來的目標(biāo)，添加松馳變量在目標(biāo)函數(shù)中的系數(shù)為加松馳變量在目標(biāo)函數(shù)中的系數(shù)為0。(3) 若約束條件右面的某一常數(shù)項(xiàng)若約束條件右面的某一常數(shù)項(xiàng) bi0, 這時(shí)只要在這時(shí)只要在 bi 相對(duì)應(yīng)的約束方程兩邊乘相對(duì)應(yīng)的約束方程兩邊乘 1。(4) 若變量若變量 xj 無非負(fù)限制無非負(fù)限制 引進(jìn)兩個(gè)非負(fù)變量引進(jìn)兩個(gè)非負(fù)變量 xj xj” 0 令令 xj= xj xj ” （可正可負(fù)）（可正可負(fù)）任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型任何形式的線性規(guī)劃總可以化成標(biāo)準(zhǔn)型例例1.3 將下列問題化成標(biāo)準(zhǔn)型將下列問題化成標(biāo)準(zhǔn)型: mi

13、n Z = x1+ 2x2 3x3 s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無限制無限制例例1.3 將下列問題化成標(biāo)準(zhǔn)型將下列問題化成標(biāo)準(zhǔn)型: min Z = x1+ 2x2 3x3 s.t. x1+ x2 + x3 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無限制無限制min x3 無限制無限制例例1.3 將下列問題化成標(biāo)準(zhǔn)型將下列問題化成標(biāo)準(zhǔn)型: max Z = x1 2x2 + 3x3 s.t. x1+ x2 + x3 7 x1 x2 + x

14、3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無限制無限制例例 將下列問題化成標(biāo)準(zhǔn)型將下列問題化成標(biāo)準(zhǔn)型: max Z = x1 2x2 + 3x3+0 x4 s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 2 3x1 + x2 + 2x3 = 5 x1 0, x2 0, x3 無限制，無限制，x4 0例例 將下列問題化成標(biāo)準(zhǔn)型將下列問題化成標(biāo)準(zhǔn)型: max Z = x1 2x2 + 3x3 +0 x4+0 x5 s.t. x1+ x2 + x3 + x4 = 7 x1 x2 + x3 x5 = 2 3x1 + x2 + 2x3 = 5

15、x1 0, x2 0, x3 無限制無限制， x4 0， x5 0max Z = x1 2x2 + 3x3 3x3 +0 x4+0 x5 s.t. x1+ x2 + x3 x3 + x4 = 7 x1 x2 + x3 x3 x5 = 2 3x1 + x2 + 2x3 2x3 = 5 x1 0, x2 0, x3 0, x3 0， x4 0， x5 0令令 x3 = x3 x3例例 將下列一般形式劃為標(biāo)準(zhǔn)形式：將下列一般形式劃為標(biāo)準(zhǔn)形式：020040065300432423213321321321321xxxxxxxxxxxxtsxxxxf, ,.)(min無限制無限制0200400653004

16、32423213321321321321xxxxxxxxxxxxtsxxxxf, ,.)(min無限制無限制非標(biāo)準(zhǔn)形式：非標(biāo)準(zhǔn)形式： 02004006653004432000442365433216332153321433216543321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxf,.)(max標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)形式：標(biāo)準(zhǔn)型習(xí)題標(biāo)準(zhǔn)型習(xí)題P55-2.2（1）劃為標(biāo)準(zhǔn)形式）劃為標(biāo)準(zhǔn)形式二、二、LP問題的圖解法問題的圖解法 max Z = 50 x1+30 x2 s.t. 4x1+3x2 120 2x1+x2 50 x1, x2 01.例例 x240302010102030 x

17、1 由由 4x1+3x2 120 x1 0, x2 0 圍成的區(qū)域圍成的區(qū)域50 由由 2x1+x2 50 x1 0, x2 0 圍成的區(qū)域圍成的區(qū)域0, 050212034. .3050max21212121xxxxxxtsxxZx240302010102030 x1 由由 4x1+3x2 120 2x1+x2 50 x1 0, x2 0 圍成的區(qū)域圍成的區(qū)域 (可行域可行域)50可行域可行域滿足約束條件的解稱為滿足約束條件的解稱為可行可行解解，全部可行解的集合稱為，全部可行解的集合稱為可行域可行域。x240302010102030 x1 該問題的可行域是由該問題的可行域是由 Q1，Q2，Q

18、3，Q4 作為頂點(diǎn)的作為頂點(diǎn)的凸多邊形凸多邊形50可行域可行域Q1(0, 0)Q2(25, 0)Q4(0, 40)Q3(15, 20)x240302010102030 x1 目標(biāo)函數(shù)目標(biāo)函數(shù) Z = 50 x1+30 x2 是一組平行線是一組平行線50可行域可行域x240302010102030 x1 此組平行線沿其此組平行線沿其 法線方向法線方向 (50, 30) 右上方右上方 函數(shù)值函數(shù)值 Z 增加增加50可行域可行域x240302010102030 x1當(dāng)該直線移到當(dāng)該直線移到 Q3(15, 20)點(diǎn)時(shí)，點(diǎn)時(shí)，Z 值達(dá)到最大：值達(dá)到最大： max Z=50 15+30 20=1350此時(shí)

19、最優(yōu)解此時(shí)最優(yōu)解 X*=（15，20）50Q3(15, 20)二個(gè)重要結(jié)論：二個(gè)重要結(jié)論： 可行域是一個(gè)凸多邊形?？尚杏蚴且粋€(gè)凸多邊形。 最優(yōu)解必定能在某一個(gè)頂點(diǎn)上取得。最優(yōu)解必定能在某一個(gè)頂點(diǎn)上取得。2.LP問題的解問題的解 可行解：可行解：滿足約束條件（包括非負(fù)條件）的滿足約束條件（包括非負(fù)條件）的一組變量值，稱可行解。一組變量值，稱可行解。 可行域：可行域：可行解的全體?？尚薪獾娜w。 最優(yōu)最優(yōu)解解：使目標(biāo)函數(shù)達(dá)到最大的可行解。使目標(biāo)函數(shù)達(dá)到最大的可行解。 最優(yōu)最優(yōu)值值：將最優(yōu)解代入目標(biāo)函數(shù)得到的值。將最優(yōu)解代入目標(biāo)函數(shù)得到的值。 可行域?yàn)榭占尚杏驗(yàn)榭占療o可行解無可行解 可行域非空，則

20、有三種情況：可行域非空，則有三種情況：(1) 有唯一解有唯一解 (頂點(diǎn)頂點(diǎn))(2) 有無窮多個(gè)解有無窮多個(gè)解 (兩個(gè)頂點(diǎn)間的連線兩個(gè)頂點(diǎn)間的連線)(3) 無最優(yōu)解無最優(yōu)解 (無界解無界解)無最優(yōu)解無最優(yōu)解 0,6321 23min21212121xxxxxxxxZx1x2 無可行解無可行解x240302010102030 x1 當(dāng)目標(biāo)函數(shù)由當(dāng)目標(biāo)函數(shù)由 max Z=50 x1+30 x2 變成變成 max Z=40 x1+30 x2 目標(biāo)函數(shù)是同約束條件目標(biāo)函數(shù)是同約束條件 4x1+3x2 120 平行的直線平行的直線 Q2與與Q3之間都是最優(yōu)解之間都是最優(yōu)解50Q3(15, 20)Q2(25

21、, 0) 0,122max21212121xxxxxxxxZ無界解無界解x1x2 無界解無界解若可行域無界，若可行域無界， 且目標(biāo)函數(shù)值可增加且目標(biāo)函數(shù)值可增加(減少減少)到正無窮到正無窮(負(fù)無窮負(fù)無窮)， 稱這種無最優(yōu)解的情況為稱這種無最優(yōu)解的情況為無界解無界解。注意注意 可行域無界，不一定無最優(yōu)解可行域無界，不一定無最優(yōu)解； 可行域非空有界，則必定有最優(yōu)解?？尚杏蚍强沼薪?，則必定有最優(yōu)解。LPLP問題解的類型習(xí)題問題解的類型習(xí)題P55-2.1三、單純形法的基本思路和原理三、單純形法的基本思路和原理（一）單純形法的（一）單純形法的基本思路基本思路 從可行域中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)從可行域

22、中某一個(gè)頂點(diǎn)開始，判斷此頂點(diǎn)是否是最優(yōu)，如不是，則再找另一個(gè)使得其是否是最優(yōu)，如不是，則再找另一個(gè)使得其目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判目標(biāo)函數(shù)值更優(yōu)的頂點(diǎn)，稱之為迭代，再判斷此點(diǎn)是否是最優(yōu)解，直到找到一個(gè)頂點(diǎn)為斷此點(diǎn)是否是最優(yōu)解，直到找到一個(gè)頂點(diǎn)為其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，其最優(yōu)解，就是使得其目標(biāo)函數(shù)值最優(yōu)的解，或者能判斷出線性規(guī)劃問題無最優(yōu)解為止?；蛘吣芘袛喑鼍€性規(guī)劃問題無最優(yōu)解為止。找出一個(gè)初始可行解找出一個(gè)初始可行解是否最優(yōu)是否最優(yōu)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)轉(zhuǎn)移到另一個(gè)目標(biāo)函數(shù)（找更大的基本可行解）（找更大的基本可行解）最優(yōu)解最優(yōu)解是是否否循循環(huán)環(huán)直到找出為止，直到找出為

23、止，核心是：變量迭代核心是：變量迭代結(jié)束結(jié)束 例例 max Z = 2x1+3x2 s.t. x1+2x2 4 4x1 8 4x2 6 x1, x2 01.1.基本概念基本概念劃為標(biāo)準(zhǔn)型：劃為標(biāo)準(zhǔn)型： max Z = 2x1+3x2 +0 x3 +0 x4+0 x5 s.t. x1+2x2 +x3 = 4 4x1 +x4 = 8 4x2 +x5 = 6 x1, x2, x3, x4, x5 0100400100400121約束方程的系數(shù)矩陣約束方程的系數(shù)矩陣A =P1P2P3P4P5單位矩陣單位矩陣A中存在一個(gè)不為零的中存在一個(gè)不為零的三階子式，三階子式，A的秩為的秩為3A是約束條件的是約束條

24、件的mn階系數(shù)矩陣，設(shè)階系數(shù)矩陣，設(shè) r(A) = m, 且且B是是A的的m 階非奇異的子矩陣（階非奇異的子矩陣（det(B) 0), 則稱矩陣則稱矩陣B為線性規(guī)劃問題的一個(gè)基為線性規(guī)劃問題的一個(gè)基(陣陣)。（1）基）基(陣陣)B =100010001040004121或或( m n) r(A)=m，至少有一個(gè)，至少有一個(gè)m階子式不為階子式不為0。a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnp1 pm pm+1 pnBN基基B中的一列即稱為一個(gè)基向量，基中的一列即稱為一個(gè)基向量，基B中共有中共有m個(gè)基向量。個(gè)基向量。（2）基向量與非基

25、向量）基向量與非基向量B =100010001P3P4P5基向量基向量A= ( p1 pm pm+1 pn ) = ( B, N ) 基向量基向量 非基向量非基向量（3 3）基變量與非基變量）基變量與非基變量設(shè)設(shè) A=( p1, p2, , pn )，若若B=( pi1, pi2, , pim )為為 A的基陣，的基陣，則稱則稱x1, x2, , xn 中的中的xi1, xi2, , xim 為對(duì)應(yīng)于為對(duì)應(yīng)于B的的基變量基變量，其余的稱為，其余的稱為非基變非基變量量。B =100010001P3P4P5x3, x4, x5是基變量是基變量x1, x2,是非基變量是非基變量基向量基向量X= (

26、x1 xm xm+1 xn )T = ( XB XN)T 基變量基變量 非基變量非基變量A= ( p1 pm pm+1 pn ) = ( B, N ) 基向量基向量 非基向量非基向量（4 4）基）基( (本本) )解解令非基變量取值為零令非基變量取值為零, 則基變量的取值可從則基變量的取值可從 AX=b 中唯一解得。中唯一解得。如此的一組解稱為對(duì)應(yīng)于如此的一組解稱為對(duì)應(yīng)于B的一個(gè)的一個(gè)基（本）基（本）解解。（5）基可行解）基可行解若若X0是一個(gè)基解，而且又是一個(gè)可行解，是一個(gè)基解，而且又是一個(gè)可行解，則稱則稱X0是一個(gè)是一個(gè)基可行解基可行解?；尚薪饣尚薪鈱?duì)應(yīng)于可行域的頂點(diǎn)。對(duì)應(yīng)于可行域的頂

27、點(diǎn)。退化的基可行解退化的基可行解問題問題: 在基可行解中在基可行解中,非基變量的取值必非基變量的取值必定為零定為零, 基變量的取值是否必定大于零基變量的取值是否必定大于零?若若X0是一個(gè)基可行解是一個(gè)基可行解, 其基變量的取值全其基變量的取值全部大于零，則稱部大于零，則稱X0是非退化的是非退化的; 否則稱為否則稱為退化的退化的。解的關(guān)系解的關(guān)系可行解可行解基解基解基可行解基可行解最優(yōu)解最優(yōu)解代數(shù)概念幾何概念滿足一個(gè)等式約束的解滿足一個(gè)不等式約束的解滿足一組不等式約束的解基解基可行解目標(biāo)函數(shù)值等于一個(gè)常數(shù)的解組約束直線約束半平面約束半平面的交集：凸多邊形約束直線的交點(diǎn)可行域頂點(diǎn)目標(biāo)函數(shù)等值線：一

28、組平行線舉例舉例36620781024621212212121)(max,:,.)(maxxfxxxxxxxxxtsxxxf最優(yōu)解最優(yōu)解1187654322x1876543O109x2A BCEDFGH123化為標(biāo)準(zhǔn)型化為標(biāo)準(zhǔn)型07810200046543215242132154321xxxxxxxxxxxxxtsxxxxxxf,.)(max可行解、基解和基可行解舉例可行解、基解和基可行解舉例1187654322x1876543O109x2A BCEDFGH123f(x)=36K2.2.最優(yōu)解的判斷最優(yōu)解的判斷檢驗(yàn)數(shù)公式檢驗(yàn)數(shù)公式0 0:maxz jjjjjijijjjczzcaczc或或最優(yōu)

29、解檢驗(yàn)的依據(jù)是計(jì)算檢驗(yàn)數(shù)最優(yōu)解檢驗(yàn)的依據(jù)是計(jì)算檢驗(yàn)數(shù)j檢驗(yàn)數(shù)的判別規(guī)則檢驗(yàn)數(shù)的判別規(guī)則(max)(max)若所有的若所有的 ，則基，則基B所對(duì)應(yīng)的基可行解就所對(duì)應(yīng)的基可行解就是最優(yōu)解。是最優(yōu)解。若所有的若所有的 ，而非基變量的檢驗(yàn)數(shù)滿足，而非基變量的檢驗(yàn)數(shù)滿足條件條件 ，則該線性規(guī)劃問題有唯一最優(yōu)解。，則該線性規(guī)劃問題有唯一最優(yōu)解。若所有的若所有的 ，又有某個(gè)非基變量的檢驗(yàn)，又有某個(gè)非基變量的檢驗(yàn)數(shù)數(shù) ，則該線性規(guī)劃問題有無窮多最優(yōu)解。，則該線性規(guī)劃問題有無窮多最優(yōu)解。 若存在某個(gè)若存在某個(gè) ，又其對(duì)應(yīng)的向量的所有，又其對(duì)應(yīng)的向量的所有分量分量 ，則該線性規(guī)劃問題存在無界解。，則該線性規(guī)劃問題

30、存在無界解。0j0j0j0j0ija0j0j3.3.單純形表單純形表jcnmmcccc11BcBXbmcc 1mxx 1mbb 1nmmxxxx 11im 1mnmmnmaaaa1,11, 11001jjjzc iibc0 0 ijijjacc )min(0kjkjiaab （二）單純形法的內(nèi)容（二）單純形法的內(nèi)容1.初始基可行解的確定（假定基陣初始基可行解的確定（假定基陣B為單位陣）為單位陣）2.最優(yōu)解的判斷最優(yōu)解的判斷3.換基可行解的方法換基可行解的方法例例 max Z = 2x1+3x2 +0 x3 +0 x4+0 x5 s.t. x1+2x2 +x3 = 4 4x1 +x4 = 8 4

31、x2 +x5 = 6 x1, x2, x3, x4, x5 0 cj2 3 0 0 0 x1 x2 x3 x4 x5 1 2 1 0 0 4 0 0 1 0 0 4 0 0 1cBxBbx3x4x5000486 max Z = 2x1+3x2 +0 x3 +0 x4+0 x5 s.t. x1+2x2 +x3 = 4 4x1 +x4 = 8 4x2 +x5 = 6 x1, x2, x3, x4, x5 0cj 2 3 0 0 0cBxBb x1 x2 x3 x4 x5 000 x3x4x5486 1 2 1 0 0 4 0 0 1 0 0 4 0 0 10 i2 3 0 0 04/26/4cj

32、2 3 0 0 0 cBxBb x1 x2 x3 x4 x5 00 x3x484 0 0 1 0 9/2i3x23/2010011010-1/21/42 0 -2 0 -3/41/18/4jjjzc jjjzc cj 2 3 0 0 0 cBxBb x1 x2 x3 x4 x5 20 x1x440 0 -4 1 2 13/2i3x23/2010011010-1/21/40 0 -2 0 1/464/2cj 2 3 0 0 0 cBxBb x1 x2 x3 x4 x5 20 x1x520 0 -2 1/2 1 73x21011/2-1/821001/4000 0 -3/2 -1/4 0jjjzc

33、 jjjzc 0, 12 4 16 4 8 2 21 22000032max6543216251421321654321xxxxxxxxxxxxxxxxxxxxxxZ例例cj 2 3 0 0 0 0cBxBb x1 x2 x3 x4 x5 x60000 x3x4x5x61281612 2 2 1 0 0 0 1 2 0 1 0 0 4 0 0 0 1 0 0 4 0 0 0 10 i2 3 0 0 0 012/28/212/4000 x3x4x516 4 0 0 0 1 0 3x23010001/42620100-1/210010 0-1/2jjjzc cj 2 3 0 0 0 0cBxBb

34、x1 x2 x3 x4 x5 x60003x3x4x5x262163 2 0 1 0 0 -1/2 1 0 0 1 0 -1/2 4 0 0 0 1 0 0 1 0 0 0 1/49 i2 0 0 0 0 -3/46/2216/40203x3 x1x5x22283 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4441213 0 0 0 -2 0 1/4jjjzc jjjzc 0203x6 x1x5x2 4402 0 0 2 -4 0 1 1 0 1 -1 0 0 0 0 -4 4 1 0 0 1 -1/2 1 0 014 0 0

35、 -1/2 -1 0 0 0 0 0 -2 0 1/4134412 0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjijjjzc jjjzc 0203x3 x1x6 x2 0442 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 014 0 0 0 -3/2 -1/8 0 0 0 0 -2 0 1/4134412 0 0 1 -2 0 1/2 1 0 0

36、 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/42283x3 x1x5x20203 x1 x2 x3 x4 x5 x6bxBcB 2 3 0 0 0 0cjijjjzc jjjzc 例例 求線性規(guī)劃問題求線性規(guī)劃問題0,24261553221212121xxxxxxxxMaxZ 0,24261553221212121 xxxxxxxxMaxZ 0,24 2615 532432142132121 xxxxxxxxxxxxMaxZ 0 0 -1/12 -7/2433/4 x2x112 x1 x2 x3 x4bxBcB 2 1 0 0cji15/43/4011/4-1/810

37、 -1/125/24jjjzc 單純形法解線性規(guī)劃問題習(xí)題單純形法解線性規(guī)劃問題習(xí)題P55-2.21.無法給出初始基可行解無法給出初始基可行解四、大四、大M法法2.添加人工變量添加人工變量3.修改目標(biāo)函數(shù)修改目標(biāo)函數(shù)例例0,10527532max321321321321xxxxxxxxxxxxZbxpbxpbxpjjjjjj先減去先減去 再加上再加上axaxsxsx加入松弛變量加入松弛變量加入人工變量加入人工變量 加入人工變量后，目的是找到一個(gè)單位向量。其加入人工變量后，目的是找到一個(gè)單位向量。其目標(biāo)價(jià)值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。目標(biāo)價(jià)值系數(shù)要確定，但不能影響目標(biāo)函數(shù)的取值。一般可

38、采用兩種方法處理：一般可采用兩種方法處理：大大M法法和和兩階段法兩階段法。 即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為即假定人工變量在目標(biāo)函數(shù)中的系數(shù)為-M（任意大正數(shù)。如基變量中還存在（任意大正數(shù)。如基變量中還存在M，就不能實(shí)，就不能實(shí)現(xiàn)極值?，F(xiàn)極值。 6543210532max MxxMxxxxZ大大M法：法： 0,105270532max654321653214321654321xxxxxxxxxxxxxxxMxxMxxxxZ0-M0-5+2M3-4M2+3M-17M51-101-5210 x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cjijjjzc -M

39、+1/7-1/7-M-16/7-50/700102/71/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cjjjjzc 一般而言，一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下一般而言，一個(gè)經(jīng)濟(jì)、管理問題凡是滿足以下條件時(shí)，才能建立線性規(guī)劃模型。條件時(shí)，才能建立線性規(guī)劃模型。 要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，要求解問題的目標(biāo)函數(shù)能用數(shù)值指標(biāo)來反映，且為線性函數(shù)；且為線性函數(shù)； 存在著多種方案；存在著多種方案； 要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些要求達(dá)到的目標(biāo)是在一定條件下實(shí)現(xiàn)的，這些約束可用線性等式或不等式描

40、述。約束可用線性等式或不等式描述。五、線性規(guī)劃在工商管理中的應(yīng)用五、線性規(guī)劃在工商管理中的應(yīng)用1.1.人力資源分配的問題；人力資源分配的問題；2.2.生產(chǎn)計(jì)劃的問題；生產(chǎn)計(jì)劃的問題；3.3.套裁下料問題；套裁下料問題；4.4.配料問題；配料問題；5.5.投資問題。投資問題。應(yīng)用舉例應(yīng)用舉例1.1.人力資源分配的問題人力資源分配的問題 例例1：某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需：某晝夜服務(wù)的公交線路每天各時(shí)間段內(nèi)所需司機(jī)和乘務(wù)人員數(shù)如下：司機(jī)和乘務(wù)人員數(shù)如下： 設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，設(shè)司機(jī)和乘務(wù)人員分別在各時(shí)間段一開始時(shí)上班，并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和

41、并連續(xù)工作八小時(shí)，問該公交線路怎樣安排司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員，既能滿足工作需要，又配備最少司機(jī)和乘務(wù)人員乘務(wù)人員?分析：不同上班班次時(shí)段的司機(jī)和乘務(wù)人員數(shù)分析：不同上班班次時(shí)段的司機(jī)和乘務(wù)人員數(shù).,.6210302050607060655443322161654321jxxxxxxxxxxxxxtsxxxxxxminZj且為整數(shù)且為整數(shù)設(shè)設(shè) xi 表示第表示第i班次時(shí)開始班次時(shí)開始上班的司機(jī)和乘務(wù)人員數(shù)上班的司機(jī)和乘務(wù)人員數(shù)例例2：一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過：一家中型的百貨商場(chǎng)，它對(duì)售貨員的需求經(jīng)過統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，

42、統(tǒng)計(jì)分析如下表所示。為了保證售貨人員充分休息，售貨人員每周工作售貨人員每周工作5天，休息兩天，并要求休息的兩天，休息兩天，并要求休息的兩天是連續(xù)的。問應(yīng)該如何安排售貨人員的作息，既天是連續(xù)的。問應(yīng)該如何安排售貨人員的作息，既滿足工作需要，又使配備的售貨人員的人數(shù)最少？滿足工作需要，又使配備的售貨人員的人數(shù)最少？設(shè)設(shè)xi ( i = 1,2,7)表示星期一至日開始工作的人數(shù)。表示星期一至日開始工作的人數(shù)。7 , 6 , 2 , 1028311925241528.432173217643217321762176517654765437654321jxxxxxxxxxxxxxxxxxxxxxxxxx

43、xxxxxxxxxxxtsxxxxxxxminZj且為整數(shù)約束條件：目標(biāo)函數(shù)：2.2.生產(chǎn)計(jì)劃的問題生產(chǎn)計(jì)劃的問題例例3 3：某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題。：某公司面臨一個(gè)是外包協(xié)作還是自行生產(chǎn)的問題。該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)該公司生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要經(jīng)過鑄造、機(jī)加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包加工和裝配三個(gè)車間。甲、乙兩種產(chǎn)品的鑄件可以外包協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保協(xié)作，亦可以自行生產(chǎn)，但產(chǎn)品丙必須本廠鑄造才能保證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤(rùn)，甲、證質(zhì)量。數(shù)據(jù)如表。問：公司為了獲得最大利潤(rùn)，甲、

44、乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造乙、丙三種產(chǎn)品各生產(chǎn)多少件？甲、乙兩種產(chǎn)品的鑄造中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？中，由本公司鑄造和由外包協(xié)作各應(yīng)多少件？解：設(shè)解：設(shè) x1，x2，x3 分別為三道工序都由本公司加工的甲、分別為三道工序都由本公司加工的甲、乙、丙三種產(chǎn)品的件數(shù)，乙、丙三種產(chǎn)品的件數(shù)，x4，x5 分別為由外協(xié)鑄造再由分別為由外協(xié)鑄造再由本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。本公司加工和裝配的甲、乙兩種產(chǎn)品的件數(shù)。 求求 xi 的利潤(rùn)：利潤(rùn)的利潤(rùn)：利潤(rùn) = 售價(jià)售價(jià) - 各成本之和各成本之和 產(chǎn)品甲全部自制的利潤(rùn)產(chǎn)品甲全部自制的利潤(rùn) =23-(3+2+3)=1

45、5 產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn)產(chǎn)品甲鑄造外協(xié)，其余自制的利潤(rùn) =23-(5+2+3)=13 產(chǎn)品乙全部自制的利潤(rùn)產(chǎn)品乙全部自制的利潤(rùn) =18-(5+1+2)=10 產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn)產(chǎn)品乙鑄造外協(xié)，其余自制的利潤(rùn) =18-(6+1+2)=9 產(chǎn)品丙的利潤(rùn)產(chǎn)品丙的利潤(rùn) =16-(4+3+2)=7可得到可得到 xi （i = 1,2,3,4,5） 的利潤(rùn)分別為的利潤(rùn)分別為 15、10、7、13、9 元。元。通過以上分析通過以上分析,可建立如下的數(shù)學(xué)模型可建立如下的數(shù)學(xué)模型:目標(biāo)函數(shù)：目標(biāo)函數(shù)： Max 15x1 + 10 x2 + 7x3 + 13x4 + 9x5 約束條件：約束條

46、件： 5x1 + 10 x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0例例5：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)：現(xiàn)有一批某種型號(hào)的圓鋼長(zhǎng)8米，需要截取米，需要截取2.5米長(zhǎng)米長(zhǎng)的毛坯的毛坯100根，長(zhǎng)根，長(zhǎng)1.3米的毛坯米的毛坯200根。問如何才能既滿足根。問如何才能既滿足需要，又能使總的用料最少？需要，又能使總的用料最少？100200 3 2 1 0 0 2 4 62.5米米1.3米米需要需要根數(shù)根數(shù) 一一 二二 三三 四四下料下料 下料下料毛毛 件數(shù)

47、件數(shù) 方式方式坯型號(hào)坯型號(hào) )4 . 3 . 2 . 1(020064210023min4323214321jxxxxxxxxxxxZj設(shè)變量為設(shè)變量為 第第 j 種方法的所有種方法的所有原料件數(shù)原料件數(shù)jx3.3.套裁下料問題套裁下料問題 例例6：某工廠要做：某工廠要做100套鋼架，每套用長(zhǎng)為套鋼架，每套用長(zhǎng)為2.9m,2.1m,1.5m的圓的圓鋼各一根。已知原料每根長(zhǎng)鋼各一根。已知原料每根長(zhǎng)7.4m，問：應(yīng)如何下料，可使所，問：應(yīng)如何下料，可使所用原料最??？用原料最??？ 解：解： 共可設(shè)計(jì)下列共可設(shè)計(jì)下列 5 種下料方案，見下表種下料方案，見下表 設(shè)設(shè) x1,x2,x3,x4,x5 分別為

48、上面分別為上面 5 種方案下料的原材料根數(shù)。這樣我種方案下料的原材料根數(shù)。這樣我們建立如下的數(shù)學(xué)模型。們建立如下的數(shù)學(xué)模型。 目標(biāo)函數(shù)：目標(biāo)函數(shù)： Min x1 + x2 + x3 + x4 + x5 約束條件：約束條件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0 用軟件計(jì)算得出最優(yōu)下料方案：按方案用軟件計(jì)算得出最優(yōu)下料方案：按方案1下料下料30根；按方案根；按方案2下料下料10根；按方案根；按方案4下料下料50根。根。 即即 x1=30; x2=10； x3=0； x

49、4=50； x5=0； 只需只需90根原材料就可制造出根原材料就可制造出100套鋼架。套鋼架。 注意：在建立此類型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)注意：在建立此類型數(shù)學(xué)模型時(shí)，約束條件用大于等于號(hào)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)比用等于號(hào)要好。因?yàn)橛袝r(shí)在套用一些下料方案時(shí)可能會(huì)多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用多出一根某種規(guī)格的圓鋼，但它可能是最優(yōu)方案。如果用等于號(hào)，這一方案就不是可行解了。等于號(hào)，這一方案就不是可行解了。例例7：根據(jù)對(duì)：根據(jù)對(duì)77種食物所含的九種營(yíng)養(yǎng)物：熱量種食物所含的九種營(yíng)養(yǎng)物：熱量(糖與脂肪糖與脂肪)、蛋白質(zhì)、鈣、鐵、維生素蛋白質(zhì)、鈣、鐵

50、、維生素A、維生素、維生素B1、維生素、維生素B2、草酸、草酸與維生素與維生素C的成份及食物的市場(chǎng)價(jià)格調(diào)查，按照醫(yī)生所提出的成份及食物的市場(chǎng)價(jià)格調(diào)查，按照醫(yī)生所提出的對(duì)每個(gè)人每天所需的營(yíng)養(yǎng)要求。的對(duì)每個(gè)人每天所需的營(yíng)養(yǎng)要求。問怎樣采購食物才能在保證營(yíng)養(yǎng)要求的前提下花費(fèi)最省？這問怎樣采購食物才能在保證營(yíng)養(yǎng)要求的前提下花費(fèi)最??？這就是營(yíng)養(yǎng)問題或飲食問題，配料問題就是由此而推廣來的。就是營(yíng)養(yǎng)問題或飲食問題，配料問題就是由此而推廣來的。4.4.配料問題配料問題解：設(shè)每天購買甲，乙，丙，丁四種食物的數(shù)量分解：設(shè)每天購買甲，乙，丙，丁四種食物的數(shù)量分別為別為x1，x2，x3，x4，即可列出如下的線性規(guī)劃模型：，即可列出如下的線性規(guī)劃模型： 例例8：某工廠要用三種：某工廠要用三種原料原料1、2、3混合調(diào)配混合調(diào)配出三種不同規(guī)格的產(chǎn)品出三種不同規(guī)格的產(chǎn)品甲、乙、丙，數(shù)據(jù)如右甲、乙、丙，數(shù)據(jù)如右表。問：該廠應(yīng)如何安表。問：該廠應(yīng)如何安排生產(chǎn)，使利潤(rùn)收入為排生產(chǎn)，使利潤(rùn)收入為最大？最大？ 解：設(shè)解：設(shè) xij 表示第表示第 i 種（甲、乙、丙）產(chǎn)品中原料種（甲、乙、丙）產(chǎn)品中原料 j 的含量。這樣的含量。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮：我們建立數(shù)學(xué)模型時(shí)，要考慮： 對(duì)于甲：對(duì)于甲： x11，x12，x13； 對(duì)于乙：對(duì)于乙： x21，x22，x23； 對(duì)于丙：對(duì)于丙： x31，x32，x33