1、第3章 線性規(guī)劃1第第3 3章章 線性規(guī)劃線性規(guī)劃 線性規(guī)劃問題屬于靜態(tài)最優(yōu)化問題。靜態(tài)，是指線性規(guī)劃問題屬于靜態(tài)最優(yōu)化問題。靜態(tài)，是指系統(tǒng)處于穩(wěn)定的工作狀態(tài)，其數(shù)學模型是代數(shù)方程。系統(tǒng)處于穩(wěn)定的工作狀態(tài)，其數(shù)學模型是代數(shù)方程。因此，靜態(tài)最優(yōu)化問題，就是不考慮時間因素情況下，因此，靜態(tài)最優(yōu)化問題，就是不考慮時間因素情況下，選擇系統(tǒng)參數(shù)，使其處于最優(yōu)狀態(tài)下工作。所謂最優(yōu)選擇系統(tǒng)參數(shù)，使其處于最優(yōu)狀態(tài)下工作。所謂最優(yōu)是用一個能反映控制效果的目標函數(shù)來衡量的。而目是用一個能反映控制效果的目標函數(shù)來衡量的。而目標函數(shù)的確定要從經(jīng)濟效果、設備性能、政策界限等標函數(shù)的確定要從經(jīng)濟效果、設備性能、政策界限等

2、方面綜合考察來求得。線性規(guī)劃問題的目標函數(shù)和約方面綜合考察來求得。線性規(guī)劃問題的目標函數(shù)和約束條件都是線性函數(shù)，是最優(yōu)化問題中最簡單，又重束條件都是線性函數(shù)，是最優(yōu)化問題中最簡單，又重要，而且實用上具有普遍意義的問題。要，而且實用上具有普遍意義的問題。第3章 線性規(guī)劃23.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型3.2 圖解法圖解法3.3 線性規(guī)劃的數(shù)學基礎線性規(guī)劃的數(shù)學基礎3.4 線性規(guī)劃的單純形法線性規(guī)劃的單純形法3.5 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題第3章 線性規(guī)劃33.1 線性規(guī)劃的數(shù)學模型線性規(guī)劃的數(shù)學模型例例3-2 (最低成本問題最低成本問題)（）：）：某種飼料要求由某種飼料

3、要求由y1，y2，y3和和y4四種原料組成，這些原料中可消四種原料組成，這些原料中可消化成分的比率對應為化成分的比率對應為a11，a12，a13和和a14，粗蛋白，粗蛋白含量比為含量比為a21，a22，a23和和a24，粗纖維含量比為，粗纖維含量比為a31，a32，a33和和a34，原料單位價格為，原料單位價格為c1，c2，c3和和c4。要求每公斤飼料中可消化成分的含量不得小于要求每公斤飼料中可消化成分的含量不得小于b1，粗蛋白的含量不得小于，粗蛋白的含量不得小于b2，粗纖維的含量不，粗纖維的含量不得大于得大于b3。問每公斤飼料中各種原料用量是多。問每公斤飼料中各種原料用量是多少時成本最低。少

4、時成本最低。第3章 線性規(guī)劃4解：解：設在每公斤飼料中設在每公斤飼料中y1，y2，y3和和y4四種原料用量四種原料用量依次為依次為x1，x2，x3和和x4。每公斤飼料的成本為。每公斤飼料的成本為f (x)。該問題的數(shù)學表達式如下：該問題的數(shù)學表達式如下：目標函數(shù)：目標函數(shù)：約束條件：約束條件：變量約束：變量約束：1 1223344min( )f xc xc xc xc x11 1122133144121 1222233244231 xa xa xa xba xa xa xa xba xa xa xa xb0,14ixi 第3章 線性規(guī)劃5一、線性規(guī)劃問題的標準形式一、

5、線性規(guī)劃問題的標準形式（）1. 標準形式標準形式目標函數(shù)：目標函數(shù)：約束條件：約束條件：變量約束：變量約束：1maxnjjjzc x001,1,2, (0)nijjiija xbimb0,1,2,jxjn 通常把上述三個式子描述的問題稱為標準線通常把上述三個式子描述的問題稱為標準線性規(guī)劃問題，簡稱性規(guī)劃問題，簡稱標準線性規(guī)劃標準線性規(guī)劃。第3章 線性規(guī)劃6標準線性規(guī)劃的矩陣形式：標準線性規(guī)劃的矩陣形式：目標函數(shù)：目標函數(shù)：約束條件：約束條件：變量約束：變量約束：maxTz c x00(0)Axbb0 x其中：其中：12nxxxx111212122212nnmmmnaaaaaaaaaA01020

6、0mbbbb12ncccc第3章 線性規(guī)劃72. 將一般線性規(guī)劃轉(zhuǎn)換為標準形式將一般線性規(guī)劃轉(zhuǎn)換為標準形式（） 線性規(guī)劃標準數(shù)學模型要點線性規(guī)劃標準數(shù)學模型要點（1）目標函數(shù)求極大值：）目標函數(shù)求極大值：maxTz c x（2）所有變量約束均為非負約束：）所有變量約束均為非負約束：0jx （3）約束條件均為等式約束：）約束條件均為等式約束：0Ax = b（4）等式約束右側(cè)向量）等式約束右側(cè)向量b0的各元素值均為非負：的各元素值均為非負：00ib 第3章 線性規(guī)劃8 轉(zhuǎn)換方法轉(zhuǎn)換方法（）(1) 如果是目標函數(shù)求極小值問題，只需將原目標如果是目標函數(shù)求極小值問題，只需將原目標 函數(shù)反號，即函數(shù)反號

7、，即 等價為等價為 ；min()Tc xmax()Tc x(0,0)bcxx(2) 關于變量的非負限制：關于變量的非負限制： 若若xa為自由變量（即為自由變量（即xa 的符號不定），則可令的符號不定），則可令xa等等于兩個新的非負變量于兩個新的非負變量xb ，xc之差，即之差，即 xa = xb - - xc 非正變量用它的反號變量來代替，即若非正變量用它的反號變量來代替，即若 ，則，則可令可令xa 等于一個非負變量等于一個非負變量xb的相反數(shù)，即的相反數(shù)，即 xa = - -xb 0ax (0)bx 第3章 線性規(guī)劃9(3) 如果約束等式右側(cè)常數(shù)如果約束等式右側(cè)常數(shù) 為負值，為負值，則要化為

8、正值。方法是表達式兩邊同時反號，若此則要化為正值。方法是表達式兩邊同時反號，若此時約束為不等式約束，則不等號改變方向。時約束為不等式約束，則不等號改變方向。0(1,2,)ibim01nijjija xb010nijjn iijn ia xxbx(4) 若約束條件為不等式約束若約束條件為不等式約束,需轉(zhuǎn)化為等式約束。需轉(zhuǎn)化為等式約束。 若第若第i個約束條件為個約束條件為 則在約束中則在約束中添加添加一個非負變量一個非負變量xn+i，等價地考慮，等價地考慮這里這里xn+i稱為稱為松弛變量松弛變量。第3章 線性規(guī)劃10 若第若第i個約束條件為個約束條件為 則在約束中則在約束中減去減去一個非負變量一個

9、非負變量xn+i，等價地考慮，等價地考慮這里這里xn+i 稱為稱為剩余變量剩余變量。01nijjija xb010nijjn iijn ia xxbx第3章 線性規(guī)劃11例例3-3() 將給出的線性規(guī)劃問題的數(shù)學模型規(guī)范將給出的線性規(guī)劃問題的數(shù)學模型規(guī)范成標準形式成標準形式1231212123min345214100zxxxxxxxxxx自由，解解: 245624572458max4335214102,4,5,6,7,8izxxxxxxxxxxxxxi ，第3章 線性規(guī)劃123.2 圖解法圖解法 求解線性規(guī)劃問題的圖解法反映了線性求解線性規(guī)劃問題的圖解法反映了線性規(guī)劃的幾何意義。對于簡單的規(guī)劃

10、的幾何意義。對于簡單的二變量的線性二變量的線性規(guī)劃問題規(guī)劃問題可以用圖解法（二維圖形）來求解，可以用圖解法（二維圖形）來求解，且用圖解法求解時且用圖解法求解時不用將數(shù)學模型規(guī)范成標不用將數(shù)學模型規(guī)范成標準形式準形式。第3章 線性規(guī)劃13注：注：如果線性規(guī)劃問題有最優(yōu)解如果線性規(guī)劃問題有最優(yōu)解x*，那么，那么x*一定屬一定屬于所有滿足各項約束條件的點于所有滿足各項約束條件的點x的集合，該集合稱的集合，該集合稱為解的為解的可行域可行域。變量作為坐標軸構(gòu)成直角坐標系變量作為坐標軸構(gòu)成直角坐標系;不等式約束條件用坐標系中的半平面表示；不等式約束條件用坐標系中的半平面表示；可行域是一個凸多邊形；可行域是

11、一個凸多邊形；目標函數(shù)用一組等值線表示，沿著增加或減少的方目標函數(shù)用一組等值線表示，沿著增加或減少的方 向移動，與可行域最后的交點就是最優(yōu)解。向移動，與可行域最后的交點就是最優(yōu)解。 圖解法的主要思路：圖解法的主要思路：第3章 線性規(guī)劃14例例3-4 用圖解法求解下列線性規(guī)劃問題用圖解法求解下列線性規(guī)劃問題121212212max50100( )300( )2400( )250( )0,0( )zxxaxxbxxcxdxxe*50,250 x 解：解：最優(yōu)解在可行域的最優(yōu)解在可行域的一個頂點一個頂點 上，最優(yōu)值為上，最優(yōu)值為z=27500.第3章 線性規(guī)劃15結(jié)合例結(jié)合例3-4，直觀認識線性規(guī)劃

12、問題解的四種形式：，直觀認識線性規(guī)劃問題解的四種形式：1. 唯一解。唯一解。如本例如本例3-4所示。所示。2. 無窮多個解。無窮多個解。若若把例把例3-4的目標函數(shù)的目標函數(shù)改為改為則凸多邊形的邊則凸多邊形的邊AB上的所有點都是問上的所有點都是問題的解。因此，解題的解。因此，解是無窮多個。是無窮多個。12max zxx第3章 線性規(guī)劃163. 無最優(yōu)解無最優(yōu)解(目標函數(shù)值目標函數(shù)值為無窮大或無窮小為無窮大或無窮小)。若例若例3-4中式中式(b),(c)的約的約束條件不存在，則解的束條件不存在，則解的可行域是開區(qū)域，不能可行域是開區(qū)域，不能限制目標函數(shù)取值，目限制目標函數(shù)取值，目標函數(shù)值為無窮大

13、。標函數(shù)值為無窮大。4. 無解。無解。若例若例3-4中式中式(c)的約束條件改為的約束條件改為則約束條件則約束條件(b)和和(c)沖突，不存在同時滿足約束沖突，不存在同時滿足約束條件的區(qū)域，即無可行域，故問題無解。條件的區(qū)域，即無可行域，故問題無解。12400 xx第3章 線性規(guī)劃17簡而言之，可能出現(xiàn)的情況簡而言之，可能出現(xiàn)的情況： 可行域是空集，無解；可行域是空集，無解； 可行域無界，無最優(yōu)解；可行域無界，無最優(yōu)解； 最優(yōu)解存在且唯一，則一定在可行域頂點上最優(yōu)解存在且唯一，則一定在可行域頂點上達到；達到； 最優(yōu)解存在且不唯一，一定存在可行域的頂最優(yōu)解存在且不唯一，一定存在可行域的頂點是最優(yōu)

14、解。點是最優(yōu)解。第3章 線性規(guī)劃183.3 線性規(guī)劃的數(shù)學基礎線性規(guī)劃的數(shù)學基礎一一. 基本定義基本定義1. 凸集：凸集：設設D是是n維空間的一個點集，若集合維空間的一個點集，若集合D中任意兩點中任意兩點x1和和x2連線上的所有點都屬于集合連線上的所有點都屬于集合D，則稱集合則稱集合D是是n維空間的一個維空間的一個凸集凸集。任意兩點連。任意兩點連線上的點線上的點x，可表示為，可表示為稱稱x是是x1和和x2的的凸組合凸組合。12(1),01xxx(a)凸集凸集 (b)凸集凸集 (c) 非凸集非凸集 (d) 非凸集非凸集 (e) 非凸集非凸集第3章 線性規(guī)劃192. 極點：極點：設集合設集合D為凸

15、集，為凸集， ，如果對于，如果對于x找找不到不到 ，使得，使得成立成立,則稱則稱x為凸集為凸集D的的極點極點。即在凸集上不能表。即在凸集上不能表示成相異兩點凸組合的點，稱為示成相異兩點凸組合的點，稱為極點極點；在線性；在線性規(guī)劃問題的凸集上的極點稱之為規(guī)劃問題的凸集上的極點稱之為頂點頂點。xD1212,()x xDxx12(1),(01)xxx第3章 線性規(guī)劃203. 基本解：基本解：對于有對于有n個變量、個變量、m個約束方程的標個約束方程的標準線性規(guī)劃問題，取其準線性規(guī)劃問題，取其m個變量，若這些變量在個變量，若這些變量在約束方程中的系數(shù)列向量線性無關，則它們組約束方程中的系數(shù)列向量線性無關

16、，則它們組成一組成一組基本變量基本變量。確定了一組基本變量后，其。確定了一組基本變量后，其它它n-m個變量稱為個變量稱為非基本變量非基本變量。 令非基本變量都為令非基本變量都為 0 ，解約束方程，可，解約束方程，可唯一得到基本變量的值，從而得到一個滿足約唯一得到基本變量的值，從而得到一個滿足約束方程的解，稱為束方程的解，稱為基本解基本解。注：注：1. 基本解的個數(shù)最多有基本解的個數(shù)最多有 個。個。 2. 基本解不一定滿足變量約束條件。基本解不一定滿足變量約束條件。!()!mnnCm nm第3章 線性規(guī)劃214. 可行解：可行解：滿足約束條件滿足約束條件 和變量約束和變量約束 的一組變量值稱為的

17、一組變量值稱為可行解可行解。0, (1)jxjn0Ax = b5. 基本可行解：基本可行解：如果基本解中的每一個變量都是非如果基本解中的每一個變量都是非負的，即滿足變量約束負的，即滿足變量約束 的基本解稱的基本解稱為為基本可行解基本可行解。如果在基本可行解中至少有一個基。如果在基本可行解中至少有一個基本變量為零，則該解稱為本變量為零，則該解稱為退化的基本可行解退化的基本可行解，反之，反之，稱為稱為非退化的基本可行解非退化的基本可行解。注：注：基本可行解既是基本解、又是可行解，它對應基本可行解既是基本解、又是可行解，它對應于標準線性規(guī)劃問題可行域的頂點。于標準線性規(guī)劃問題可行域的頂點。6. 最優(yōu)

18、解最優(yōu)解:使目標函數(shù)達到最優(yōu)值的可行解稱為使目標函數(shù)達到最優(yōu)值的可行解稱為最優(yōu)解最優(yōu)解.0, (1)jxjn第3章 線性規(guī)劃22例：例：已知約束條件：已知約束條件：123124230218xxxxxx0,14ixi 變量約束：變量約束：1234562930000140018150,02106030004203182xxxxxx分析分析: (1) 可行域上有無窮多個可行解。可行域上有無窮多個可行解。(2)有有6個基本解：個基本解：(3)這這6個基本解中只有個基本解中只有x1, x2, x5, x6是基本可行解。是基本可行解。第3章 線性規(guī)劃23二二. 基本定理基本定理1.定理定理3-1：線性規(guī)劃

19、問題所有可行解的集合是凸集線性規(guī)劃問題所有可行解的集合是凸集.2.定理定理3-2：線性規(guī)劃問題若存在最優(yōu)解，則最優(yōu)解線性規(guī)劃問題若存在最優(yōu)解，則最優(yōu)解必然會出現(xiàn)在可行域的一個頂點上必然會出現(xiàn)在可行域的一個頂點上.3.定理定理3-3：設設A是秩為是秩為m的的mn矩陣，矩陣，b0是是m維向量。維向量。約束約束的可行域為的可行域為D，則上式的基本可行解，則上式的基本可行解x一定是一定是D的頂?shù)捻旤c。點。0, 0Ax = bx第3章 線性規(guī)劃244.結(jié)論：結(jié)論：如果標準線性規(guī)劃問題存在最優(yōu)解，則如果標準線性規(guī)劃問題存在最優(yōu)解，則可以先找出所有基本可行解，并計算相應的目標可以先找出所有基本可行解，并計算

20、相應的目標函數(shù)值，比較它們的值，與目標函數(shù)最大值相對函數(shù)值，比較它們的值，與目標函數(shù)最大值相對應的基本可行解就是最優(yōu)解。應的基本可行解就是最優(yōu)解。第3章 線性規(guī)劃25例例3-5：求解線性規(guī)劃問題求解線性規(guī)劃問題121212112max230240250,0zxxxxxxxxx解解： (1) 將上述將上述LP問題化為規(guī)范形式，即問題化為規(guī)范形式，即121231241512345max230240250,0,0,0,0zxxxxxxxxxxxxxxx第3章 線性規(guī)劃26約束條件的矩陣形式為：約束條件的矩陣形式為：12345111003012010401000150 xxxxx 最優(yōu)解在頂點最優(yōu)解在

21、頂點上，最優(yōu)值為上，最優(yōu)值為z=55。*255Tx 第3章 線性規(guī)劃27補充題補充題() ： 某項工程需成套橫截面相同而長度不同的某項工程需成套橫截面相同而長度不同的鋼梁，每一套由鋼梁，每一套由1根根2.9米長、米長、1根根2.1米長和米長和1根根1.5米長的鋼梁組成。這些鋼梁是由米長的鋼梁組成。這些鋼梁是由7.4米長的米長的鋼坯截成的，現(xiàn)要生產(chǎn)鋼坯截成的，現(xiàn)要生產(chǎn)100套鋼梁，問應如何套鋼梁，問應如何下料使用料最省，建立這一問題的數(shù)學模型，下料使用料最省，建立這一問題的數(shù)學模型，并給出線性規(guī)劃的標準形式。并給出線性規(guī)劃的標準形式。 第3章 線性規(guī)劃28123123123min233461zx

22、xxxxxxxx 120,0,xx3x補充題補充題() ：給出下列線性規(guī)劃問題的標準形式給出下列線性規(guī)劃問題的標準形式自由變量自由變量第3章 線性規(guī)劃293.4 線性規(guī)劃的單純形法線性規(guī)劃的單純形法() 圖解法只適用于求解二變量線性規(guī)劃問題，對于多變圖解法只適用于求解二變量線性規(guī)劃問題，對于多變量的線性規(guī)劃問題，則無法應用圖解法求解。標準線性規(guī)劃量的線性規(guī)劃問題，則無法應用圖解法求解。標準線性規(guī)劃問題如果存在最優(yōu)解，更通用的求解思路為：可以先找出基問題如果存在最優(yōu)解，更通用的求解思路為：可以先找出基本可行解（最多為本可行解（最多為 個），計算相應的目標函數(shù)值并進行比個），計算相應的目標函數(shù)值并

23、進行比較，與目標函數(shù)最大值相對應的基本可行解就是最優(yōu)解。較，與目標函數(shù)最大值相對應的基本可行解就是最優(yōu)解。 然而，當線性規(guī)劃問題的基本可行解的數(shù)目很多時，一然而，當線性規(guī)劃問題的基本可行解的數(shù)目很多時，一一求解并不現(xiàn)實，因此必須尋求一種更有效的方法。單純形一求解并不現(xiàn)實，因此必須尋求一種更有效的方法。單純形法是線性規(guī)劃中最主要、最基本的一種方法。法是線性規(guī)劃中最主要、最基本的一種方法。它的基本思路它的基本思路是：從線性規(guī)劃問題的一個基本可行解開始，是：從線性規(guī)劃問題的一個基本可行解開始，轉(zhuǎn)換到另一個轉(zhuǎn)換到另一個使目標函數(shù)值增大的基本可行解使目標函數(shù)值增大的基本可行解。反復迭代，直到目標函數(shù)。反

24、復迭代，直到目標函數(shù)值達到最大時，就得到了最優(yōu)解。值達到最大時，就得到了最優(yōu)解。mnC第3章 線性規(guī)劃30 對于標準線性規(guī)劃問題對于標準線性規(guī)劃問題maxTz c x00(0)Axbb0 x解題的基本步驟如下：解題的基本步驟如下：(1) 選取選取基本變量基本變量，計算，計算基本解基本解，從中找出滿足變量，從中找出滿足變量約束的基本可行解；約束的基本可行解；(2) 計算基本可行解對應的計算基本可行解對應的目標函數(shù)值目標函數(shù)值；(3) 比較目標函數(shù)值的大小，與目標函數(shù)最大值相對比較目標函數(shù)值的大小，與目標函數(shù)最大值相對應的基本可行解就是最優(yōu)解。應的基本可行解就是最優(yōu)解。第3章 線性規(guī)劃31預備知識

25、：預備知識：基本變量、基本解、目標函數(shù)值及其基本變量、基本解、目標函數(shù)值及其相互關系的數(shù)學表達相互關系的數(shù)學表達 已知已知 ，即，即,m nARnmrankAm12jnAaaaa12imBbbbbm mBR從從A中任選中任選m個線性無關的列組成基底個線性無關的列組成基底 ，即，即其中：矩陣其中：矩陣B中的列中的列bi就是就是A中的某一列中的某一列aj，下標下標j表表示示A中的列在矩陣中的列在矩陣A中的序號，下標中的序號，下標i表示表示A的列在矩的列在矩陣陣B中的序號中的序號。第3章 線性規(guī)劃32例例3-5：求解線性規(guī)劃問題求解線性規(guī)劃問題121212112max230240250,0zxxxx

26、xxxxx解解： (1) 將上述將上述LP問題化為規(guī)范形式，即問題化為規(guī)范形式，即121231241512345max230240250,0,0,0,0zxxxxxxxxxxxxxxx第3章 線性規(guī)劃33約束條件的矩陣形式為：約束條件的矩陣形式為：123011121001Bbbb12345111003012010401000125xxxxx (n=5,m=3)421aaa第3章 線性規(guī)劃34（1）系數(shù)向量）系數(shù)向量Bjy(1,2,)Bjiimy11221mBjBjBjBjBjjmmiiiy by by by baBy 由于由于B是一組基底，矩陣是一組基底，矩陣A中的任一列都可以寫中的任一列都可

27、以寫成成B的線性組合，設組合系數(shù)為的線性組合，設組合系數(shù)為 ，則有則有112TBjBjBjBjjmyB ayyy即即式中：上標表示系數(shù)值與基底式中：上標表示系數(shù)值與基底B及及A中列的序號中列的序號j有關。有關。第3章 線性規(guī)劃35（2）基本變量解）基本變量解Bx對應基底對應基底 B 的基本變量解的基本變量解 為：為：Bx1120TBBBBmxxxxB bBix式中：式中： 是對應基底是對應基底B的的bi列的變量。列的變量。第3章 線性規(guī)劃36（3）Bc 標準線性規(guī)劃問題的目標函數(shù)為：標準線性規(guī)劃問題的目標函數(shù)為：即即 是目標函數(shù)的系數(shù)向量，其中是目標函數(shù)的系數(shù)向量，其中ci是變量是變量xi的加

28、權(quán)系數(shù)。的加權(quán)系數(shù)。1 122Tjjnnc xc xc xc xzc x12TBBBBmcccc1122BTBBBBBBBmmc xc xc xz = cxBic12Tncccc 在基本可行解中，由于在基本可行解中，由于(n-m)個非基本變量為個非基本變量為0，故對應于基本可行解的目標函數(shù)值就等于基本變量故對應于基本可行解的目標函數(shù)值就等于基本變量解解 的目標函數(shù)值，記為的目標函數(shù)值，記為Bx其中：其中： ， 不是新的系數(shù)。不是新的系數(shù)。第3章 線性規(guī)劃37（4）Bjz定義新的變量定義新的變量 為：為：Bjz1122BjBBjBBjBBjBTBjmmzc yc yc ycyBjzBjjzcBj

29、zA中每一列中每一列aj都對應一個都對應一個yBj，相應的也就都對應一，相應的也就都對應一個個 ， 隨隨B的變化而變化。的變化而變化。 如果如果aj是是B中的第中的第k列向量，則必有列向量，則必有Bjz即即如果如果aj是組成基底是組成基底B的列向量，則的列向量，則 就是變量就是變量xj的加權(quán)系數(shù)的加權(quán)系數(shù)cj 。第3章 線性規(guī)劃38例例3-6 線性規(guī)劃問題線性規(guī)劃問題12312341235max3532833160,15izxxxxxxxxxxxxi 1321,ba ba (1) 設設 ，求相應的基本變量解，求相應的基本變量解xB及及 yB2, yB4, yB1, zB2, zB4, zB1；

30、第3章 線性規(guī)劃393.4.1 單純形法的基本算法單純形法的基本算法 單純形法是一種迭代求解方法，它的基本觀單純形法是一種迭代求解方法，它的基本觀點是：從可行域的某個頂點（初始基本可行解點是：從可行域的某個頂點（初始基本可行解)出發(fā)，向鄰近頂點運動，其目標函數(shù)值至少比前出發(fā)，向鄰近頂點運動，其目標函數(shù)值至少比前一個頂點更好。由于：一個頂點更好。由于：1. 頂點數(shù)是有限的頂點數(shù)是有限的; 2. 最最優(yōu)解一定在頂點上，所以迭代過程是有限的。這優(yōu)解一定在頂點上，所以迭代過程是有限的。這兩條是單純形法的依據(jù)。幾何上從一個頂點到另兩條是單純形法的依據(jù)。幾何上從一個頂點到另一個頂點的有限次迭代，在代數(shù)上即

31、為從一個基一個頂點的有限次迭代，在代數(shù)上即為從一個基本可行解到另一個基本可行解的迭代。本可行解到另一個基本可行解的迭代。第3章 線性規(guī)劃40一一. 單純形法的基本思路單純形法的基本思路 從一個已知基本可行解出發(fā)，尋找使目標函從一個已知基本可行解出發(fā)，尋找使目標函數(shù)有較大增加的下一個基本可行解。按照此方法數(shù)有較大增加的下一個基本可行解。按照此方法繼續(xù)，每一步都使目標函數(shù)值增加，經(jīng)過有限次繼續(xù)，每一步都使目標函數(shù)值增加，經(jīng)過有限次迭代后，就能得到最優(yōu)解。迭代后，就能得到最優(yōu)解。二、實現(xiàn)手段二、實現(xiàn)手段問題問題1：如何從一個基本可行解出發(fā)求出使目標函如何從一個基本可行解出發(fā)求出使目標函數(shù)有較大增加的

32、另一個基本可行解？數(shù)有較大增加的另一個基本可行解？問題問題2：如何判斷一個基本可行解是否是最優(yōu)解？如何判斷一個基本可行解是否是最優(yōu)解？第3章 線性規(guī)劃41問題問題1：如何從一個基本可行解出發(fā)求出使目標函如何從一個基本可行解出發(fā)求出使目標函數(shù)有較大增加的另一個基本可行解？數(shù)有較大增加的另一個基本可行解？(1)如何選取退出列如何選取退出列br才能保證新的基本解是可行的才能保證新的基本解是可行的?按式按式1min0BBBjiriBjBji mrixxyyy Brx選取退出變量選取退出變量 (退出列退出列br) 能保證得到新的基本可行解。能保證得到新的基本可行解。(2)如何選取進入變量如何選取進入變量

33、xj（進入列進入列aj ）使新的基本可行解）使新的基本可行解所對應的目標函數(shù)值增大所對應的目標函數(shù)值增大?選擇使目標函數(shù)值增大的進入變量選擇使目標函數(shù)值增大的進入變量xj的原則是：的原則是：判別數(shù)判別數(shù) 且且0Bjry()0Bjjjzc第3章 線性規(guī)劃42例例3-7 線性規(guī)劃問題線性規(guī)劃問題12312341235max3532833160,15izxxxxxxxxxxxxi （2）繼續(xù)例）繼續(xù)例3-6的討論，求出使變量的討論，求出使變量x2成為基本變成為基本變量的基本可行解；量的基本可行解；（3）繼續(xù)例）繼續(xù)例3-6的討論，找出使目標函數(shù)值增大的的討論，找出使目標函數(shù)值增大的進入變量；進入變量

34、；第3章 線性規(guī)劃43注意：注意：1. 如果同時有幾個判別數(shù)如果同時有幾個判別數(shù) ，它們當中任何一，它們當中任何一個對應的變量都可以作為進入變量。但選取最小個對應的變量都可以作為進入變量。但選取最小判別數(shù)對應的變量會使目標函數(shù)增值較大。判別數(shù)對應的變量會使目標函數(shù)增值較大。0j1min0BBBjiriBjBji mrixxyyy 2. 如果由如果由確定的最小值不唯一，則可以任選最小值對應的確定的最小值不唯一，則可以任選最小值對應的幾個變量中的一個作為退出變量，而由此得到的幾個變量中的一個作為退出變量，而由此得到的新的基本可行解是退化的。新的基本可行解是退化的。第3章 線性規(guī)劃443. 若原基本

35、可行解是退化的，則經(jīng)過變量的退出、若原基本可行解是退化的，則經(jīng)過變量的退出、進入之后得到的新的基本可行解也是退化的。進入之后得到的新的基本可行解也是退化的。4. 與基底與基底B中各列相對應的變量中各列相對應的變量xj的判別數(shù)均為的判別數(shù)均為0。問題問題2：如何判斷一個基本可行解是否是最優(yōu)解？如何判斷一個基本可行解是否是最優(yōu)解？最優(yōu)性判據(jù)：對于一個基本可行解，如果所有的最優(yōu)性判據(jù)：對于一個基本可行解，如果所有的判別數(shù)判別數(shù) ，則該解是最優(yōu)解，則該解是最優(yōu)解x*，目，目標函數(shù)取得最大值標函數(shù)取得最大值z*。0Bjjjzc第3章 線性規(guī)劃45例例3-9 線性規(guī)劃問題線性規(guī)劃問題12312412512

36、3max2323133172130,15izxxxxxxxxxxxxxi 檢驗檢驗 ，是否是該線性規(guī)劃問，是否是該線性規(guī)劃問題的最優(yōu)解。題的最優(yōu)解。23500Tx 第3章 線性規(guī)劃46單純形法基本算法的計算步驟：單純形法基本算法的計算步驟：1）把一般的線性規(guī)劃問題化為標準形式；）把一般的線性規(guī)劃問題化為標準形式；2）從）從A中選擇線性無關的列向量構(gòu)成基底中選擇線性無關的列向量構(gòu)成基底B，在此，在此基礎上求出一個初始的基本可行解；基礎上求出一個初始的基本可行解；3）若該基本可行解所對應的所有判別數(shù)）若該基本可行解所對應的所有判別數(shù) ，則得到了一個最優(yōu)解，計算結(jié)束；否則繼續(xù)則得到了一個最優(yōu)解，計算

37、結(jié)束；否則繼續(xù)4）；）；0Bjjjzcmin0kjjj 4）當該基本可行解所對應的判別數(shù)中存在某些）當該基本可行解所對應的判別數(shù)中存在某些 時，可選擇其中一個列向量時，可選擇其中一個列向量ak為進入為進入列，通常的做法是使列，通常的做法是使 所對應的向所對應的向量量ak作為進入列，即作為進入列，即xk作為進入變量作為進入變量 ； 0Bjjjzc第3章 線性規(guī)劃476）對那些）對那些 ，計算，計算 ，在，在B中，滿足中，滿足的的br是退出列，轉(zhuǎn)是退出列，轉(zhuǎn)7）；）；0BkiyBiBkixy1min0BBBkiriBkBki mrixxyyy 0Bkiy7）讓）讓ak進入基底進入基底B，構(gòu)成一個新

38、的基底，求出新，構(gòu)成一個新的基底，求出新的基本可行解，返回的基本可行解，返回3）。）。5）當所有）當所有 時，則線性規(guī)劃問題的目標函數(shù)時，則線性規(guī)劃問題的目標函數(shù)值為無窮大，計算結(jié)束；否則繼續(xù)值為無窮大，計算結(jié)束；否則繼續(xù)6）第3章 線性規(guī)劃483.4.2 單純形表格法單純形表格法() 由由Hoffman 等提出的單純形表格法，十分適等提出的單純形表格法，十分適于單純形法的手算。這種算法在單純形法基本算法于單純形法的手算。這種算法在單純形法基本算法的基礎上，利用目標函數(shù)和約束條件構(gòu)成初始表，的基礎上，利用目標函數(shù)和約束條件構(gòu)成初始表，再利用矩陣的初等變換來表示基底選擇、基本可行再利用矩陣的初等

39、變換來表示基底選擇、基本可行解、判別數(shù)和目標函數(shù)值等中間計算數(shù)據(jù)，每次迭解、判別數(shù)和目標函數(shù)值等中間計算數(shù)據(jù)，每次迭代構(gòu)成新的表格，直至滿足最優(yōu)性判據(jù)。代構(gòu)成新的表格，直至滿足最優(yōu)性判據(jù)。第3章 線性規(guī)劃49一、一、所有約束條件均為所有約束條件均為“”形式時形式時考慮如下的線性規(guī)劃問題考慮如下的線性規(guī)劃問題00max(0)0 (1,2, )Tizxinc xAxbb其中：其中：rankA=m。引入非負輔助變量（即松弛引入非負輔助變量（即松弛變量）變量）xn+1 , , xn+m , 把上述不等式約束化為等把上述不等式約束化為等式約束，即式約束，即注：注：此時可直接采用附加的所有松弛變量作為基此

40、時可直接采用附加的所有松弛變量作為基本變量，極易得到初始基本可行解。本變量，極易得到初始基本可行解。第3章 線性規(guī)劃5011 1122110121 122222021 1220nnnnnnmmmnnn mma xa xa xxba xa xa xxba xaxaxxb這樣就將上述線性規(guī)劃問題化為標準型了。由上述這樣就將上述線性規(guī)劃問題化為標準型了。由上述約束條件可見，若我們選擇所有松弛變量約束條件可見，若我們選擇所有松弛變量xn + j (j=1,m)為基本變量，則基底為基本變量，則基底B=Imm，極易得到極易得到一個初始基本可行解一個初始基本可行解x=0, 0, ,0, b01, b02,

41、, b0mT.第3章 線性規(guī)劃51單純型表格法的步驟：單純型表格法的步驟：（1）設置初始表格：）設置初始表格：根據(jù)目標函數(shù)和等式約束列出根據(jù)目標函數(shù)和等式約束列出初始單純形表。初始單純形表。初始基本變量初始基本變量表表3-2 單純形初始表格單純形初始表格初始基底初始基底B=Imm基本變基本變量解量解xB判別數(shù)判別數(shù)j對應對應xB的目標函數(shù)值的目標函數(shù)值第3章 線性規(guī)劃52（2）最優(yōu)性檢驗）最優(yōu)性檢驗 由最優(yōu)性判據(jù)知：對于一個基本可行解，如果由最優(yōu)性判據(jù)知：對于一個基本可行解，如果所有的判別數(shù)所有的判別數(shù) ，則該解是最優(yōu)解，則該解是最優(yōu)解x*。而表格中最后一行中第而表格中最后一行中第1個到第個到

42、第n+m個數(shù)據(jù)表示相個數(shù)據(jù)表示相應的判別數(shù)，最后一個數(shù)據(jù)表示目標函數(shù)值，所以應的判別數(shù)，最后一個數(shù)據(jù)表示目標函數(shù)值，所以若最后一行中第若最后一行中第1個到第個到第n+m個數(shù)據(jù)均大于等于零，個數(shù)據(jù)均大于等于零，就得到了最優(yōu)解，此時該行最后一個數(shù)據(jù)就是目標就得到了最優(yōu)解，此時該行最后一個數(shù)據(jù)就是目標函數(shù)最大值。如不滿足最優(yōu)性判據(jù)，就要更換基底，函數(shù)最大值。如不滿足最優(yōu)性判據(jù)，就要更換基底，即選擇進入變量（對應表格中的列選擇）和退出變即選擇進入變量（對應表格中的列選擇）和退出變量（對應表格中的行選擇）。量（對應表格中的行選擇）。0Bjjjzc第3章 線性規(guī)劃53（3）選擇進入列）選擇進入列 在所有小

43、于在所有小于0的判別數(shù)的判別數(shù)j 0中找最小的中找最小的k , 它所它所在的列在的列ak作為進入列。進入列作為進入列。進入列ak對應的變量為進入變對應的變量為進入變量量xk，在標題欄變量名左邊加標記在標題欄變量名左邊加標記“ xk”注明。注明。（4）選擇退出變量）選擇退出變量 選取滿足選取滿足的退出變量的退出變量xr，并在表格第，并在表格第1列的變量名左邊加標列的變量名左邊加標記記“ xr”注明。注明。min0oroiikirkikbbaaa第3章 線性規(guī)劃54（5）計算基本變量解）計算基本變量解主元：主元：進入變量進入變量“ xk”所在的列和退出變量所在的列和退出變量“ xr”所在行的相交元

44、所在行的相交元ark稱為主元。稱為主元。1. 將表格中的數(shù)據(jù)看作是一個擴展矩陣的元素，將表格中的數(shù)據(jù)看作是一個擴展矩陣的元素，即矩陣即矩陣A向右擴展一列向右擴展一列(b0列列)，向下擴展一行，向下擴展一行(z行行)，右下角元素就是目標函數(shù)值。，右下角元素就是目標函數(shù)值。注意：注意：計算基本變量解就是要把計算基本變量解就是要把ark化為化為1，并用，并用初等變換（高斯消去法）把進入變量初等變換（高斯消去法）把進入變量“ xk”所在所在列中的其它元素全部化為列中的其它元素全部化為0。第3章 線性規(guī)劃552. 計算基本變量的操作是：將擴展矩陣計算基本變量的操作是：將擴展矩陣r行所有行所有數(shù)據(jù)均除以數(shù)

45、據(jù)均除以ark，將表中第，將表中第1列中的列中的“ xr”換為換為 “xk”，第，第r行與第行與第k列相交處的主元列相交處的主元ark轉(zhuǎn)化為轉(zhuǎn)化為1了，了，即表示新的基本變量即表示新的基本變量xk=b0r。再用行初等變換將。再用行初等變換將擴展矩陣擴展矩陣k列的其余元素化為列的其余元素化為0，為下一次迭代準，為下一次迭代準備合格的備合格的“初始表初始表”。3. 在上述計算操作過程中在上述計算操作過程中(即初等變換過程中即初等變換過程中)，同，同時完成了判別數(shù)時完成了判別數(shù)j的計算，數(shù)據(jù)保存在擴展矩陣的的計算，數(shù)據(jù)保存在擴展矩陣的最后一行中；完成了目標函數(shù)值的計算，將數(shù)值保最后一行中；完成了目標

46、函數(shù)值的計算，將數(shù)值保存在擴展矩陣右下角。存在擴展矩陣右下角。（6）在步驟）在步驟(5)完成后，返回步驟完成后，返回步驟(2)繼續(xù)迭代，直繼續(xù)迭代，直到獲得最優(yōu)解。到獲得最優(yōu)解。第3章 線性規(guī)劃56例：例： () （補充）用單純形表格法求下列線性規(guī)劃問（補充）用單純形表格法求下列線性規(guī)劃問題：題：121212112max230240250,0zxxxxxxxxx解解： 將上述將上述LP問題化為規(guī)范形式，即問題化為規(guī)范形式，即121231241512345max230240250,0,0,0,0zxxxxxxxxxxxxxxx第3章 線性規(guī)劃57表表1 初始表初始表表表2 中間數(shù)據(jù)中間數(shù)據(jù)25第

47、3章 線性規(guī)劃58表表3 最終結(jié)果最終結(jié)果最優(yōu)解：最優(yōu)解：x*=25 5 0 5 0 T, 最優(yōu)值：最優(yōu)值：z*=55第3章 線性規(guī)劃59說明：說明：1）在每個計算表格中，對應每組基本變量的判別）在每個計算表格中，對應每組基本變量的判別數(shù)數(shù)j 應該均為零，這可作為驗證計算是否正確的一應該均為零，這可作為驗證計算是否正確的一個依據(jù)。個依據(jù)。2）在每個計算表格中，）在每個計算表格中，b0列各元素始終為非負，列各元素始終為非負，因為各表中因為各表中b0列存放的數(shù)據(jù)就是基本變量解，它們列存放的數(shù)據(jù)就是基本變量解，它們滿足變量約束才能保證相應的基本解是可行的，所滿足變量約束才能保證相應的基本解是可行的，

48、所以若以若b0出現(xiàn)負數(shù)則不成功，需換變量。出現(xiàn)負數(shù)則不成功，需換變量。3）注意表格中的目標函數(shù)值）注意表格中的目標函數(shù)值一般來說一般來說應逐漸增大應逐漸增大（也有前后（也有前后2次目標函數(shù)值相等的特例），這可作次目標函數(shù)值相等的特例），這可作為驗證計算是否正確的一個依據(jù)。為驗證計算是否正確的一個依據(jù)。第3章 線性規(guī)劃60二、約束條件為二、約束條件為“”和和“ = ”形式共存時形式共存時例例3-10 ()求解線性規(guī)劃問題求解線性規(guī)劃問題1231231212123max4321224610,0,0zxxxxxxxxxxxxx 這里通過一個例題來說明：當引入的輔助變量這里通過一個例題來說明：當引入的

49、輔助變量均為松弛變量，但個數(shù)少于約束條件的個數(shù)均為松弛變量，但個數(shù)少于約束條件的個數(shù)m時時（即約束條件為（即約束條件為“”和和“ = ”形式共存時），此時形式共存時），此時初始基本變量應該由松弛變量和題中的非輔助變量初始基本變量應該由松弛變量和題中的非輔助變量組成。由目標函數(shù)和約束條件確定組成。由目標函數(shù)和約束條件確定原始原始表格，再由表格，再由原始表格設法設置初始表格。原始表格設法設置初始表格。第3章 線性規(guī)劃61解：解：化為標準線性規(guī)劃化為標準線性規(guī)劃12312312412512345max4321224610,0,0,0,0zxxxxxxxxxxxxxxxxx分析：分析：該題中約束條件中

50、含有一個等式約束，所該題中約束條件中含有一個等式約束，所以引入的松弛變量個數(shù)為以引入的松弛變量個數(shù)為2m=3，此時初始基本，此時初始基本變量應該由松弛變量變量應該由松弛變量x4，x5和題中的一個非輔助變和題中的一個非輔助變量組成。由目標函數(shù)和約束條件確定原始表格，量組成。由目標函數(shù)和約束條件確定原始表格，再由原始表格設法設置初始表格。再由原始表格設法設置初始表格。第3章 線性規(guī)劃62表表3-3 原始表原始表表表3-4 初始表初始表第3章 線性規(guī)劃63表表3-5 中間數(shù)據(jù)中間數(shù)據(jù)表表3-6 最終結(jié)果最終結(jié)果最優(yōu)解：最優(yōu)解：x*=8, 6, 0, 0, 29 T, 最優(yōu)值：最優(yōu)值：z*=38第3章

51、 線性規(guī)劃64三、當約束條件中含有三、當約束條件中含有“” 形式時形式時 這里通過一個例題來說明：當約束條件既有這里通過一個例題來說明：當約束條件既有“”形式，又有形式，又有“” 形式時，形式時，引入的剩余變量不引入的剩余變量不能直接拿來作為初始基本變量能直接拿來作為初始基本變量，同樣由所有的松弛，同樣由所有的松弛變量和非輔助變量組成初始基本變量。變量和非輔助變量組成初始基本變量。例例3-11 ()求解線性規(guī)劃問題求解線性規(guī)劃問題1212121212max43341222240,0zxxxxxxxxxx第3章 線性規(guī)劃65解：解：化為標準線性規(guī)劃化為標準線性規(guī)劃1212312412512345

52、max43341224220,0,0,0,0zxxxxxxxxxxxxxxxx表表3-7 原始表原始表第3章 線性規(guī)劃66表表3-8 初始表初始表表表3-9 中間數(shù)據(jù)中間數(shù)據(jù)第3章 線性規(guī)劃67表表3-10 最終結(jié)果最終結(jié)果最優(yōu)解：最優(yōu)解： 最優(yōu)值：最優(yōu)值：*4121800555Tx*525z 第3章 線性規(guī)劃68123123123min233461zxxxxxxxxx120,0,xx3x補充題補充題() ：利用單純形表格法求解下列線性規(guī)劃利用單純形表格法求解下列線性規(guī)劃問題問題自由變量自由變量要求至少要有線性規(guī)劃的標準形式和最終表格。要求至少要有線性規(guī)劃的標準形式和最終表格。第3章 線性規(guī)劃

53、693.4.3 兩階段法兩階段法 當線性規(guī)劃問題的所有約束條件均具有當線性規(guī)劃問題的所有約束條件均具有“”形形式時，將該問題化為標準線性規(guī)劃時引入的所有式時，將該問題化為標準線性規(guī)劃時引入的所有松弛變量可以作為初始基本變量，這樣極易得到松弛變量可以作為初始基本變量，這樣極易得到初始基本可行解。但當約束條件中出現(xiàn)初始基本可行解。但當約束條件中出現(xiàn)“=”和和“”形式時，初始基本可行解不能直觀得到，這形式時，初始基本可行解不能直觀得到，這時可像時可像3.4.2節(jié)中例節(jié)中例3-10，3-11那樣處理，也可用那樣處理，也可用兩階段法處理。兩階段法處理。第3章 線性規(guī)劃70兩階段法將線性規(guī)劃的求解分為兩步

54、完成：兩階段法將線性規(guī)劃的求解分為兩步完成：（1）準備階段：）準備階段：將原線性規(guī)劃問題化為標準型后，將原線性規(guī)劃問題化為標準型后，再引入所謂的暫用變量再引入所謂的暫用變量y，構(gòu)造一個尋找原問題初，構(gòu)造一個尋找原問題初始可行解的線性規(guī)劃問題，其目標函數(shù)為所有引始可行解的線性規(guī)劃問題，其目標函數(shù)為所有引入變量之和相反數(shù)的極大值，在求解該問題的基入變量之和相反數(shù)的極大值，在求解該問題的基礎上判斷原線性規(guī)劃問題無解，或者得到一個初礎上判斷原線性規(guī)劃問題無解，或者得到一個初始基本可行解，為原問題準備初始表格；始基本可行解，為原問題準備初始表格；（2）計算階段：）計算階段：在得到的一個初始基本可行解的在

55、得到的一個初始基本可行解的基礎上，用單純形（表格）法求最優(yōu)解。基礎上，用單純形（表格）法求最優(yōu)解。第3章 線性規(guī)劃713.5 線性規(guī)劃的對偶問題線性規(guī)劃的對偶問題()一、線性規(guī)劃的對偶問題定義一、線性規(guī)劃的對偶問題定義 在線性規(guī)劃問題中，約束條件的數(shù)目直接影在線性規(guī)劃問題中，約束條件的數(shù)目直接影響著基底的維數(shù)，在每次迭代過程中，基底的維響著基底的維數(shù)，在每次迭代過程中，基底的維數(shù)越高則行初等變換等計算量越大。因此，約束數(shù)越高則行初等變換等計算量越大。因此，約束條件數(shù)目比變量數(shù)目更能影響求解時間。在不等條件數(shù)目比變量數(shù)目更能影響求解時間。在不等式約束中，有時會遇到約束條件數(shù)目比變量數(shù)目式約束中，

56、有時會遇到約束條件數(shù)目比變量數(shù)目多的情況，為了更好地解決這類具有較多約束條多的情況，為了更好地解決這類具有較多約束條件的線性規(guī)劃問題，加快計算速度，必須設法減件的線性規(guī)劃問題，加快計算速度，必須設法減少約束條件數(shù)目。少約束條件數(shù)目。第3章 線性規(guī)劃72 例如在解題過程中，可將約束條件數(shù)目與變例如在解題過程中，可將約束條件數(shù)目與變量數(shù)目對調(diào)，根據(jù)原問題構(gòu)造出有較少約束數(shù)目量數(shù)目對調(diào)，根據(jù)原問題構(gòu)造出有較少約束數(shù)目的新問題，在解新問題的過程中得到原問題的最的新問題，在解新問題的過程中得到原問題的最優(yōu)解，這就是線性規(guī)劃的對偶問題。優(yōu)解，這就是線性規(guī)劃的對偶問題。 “對偶對偶”是線性規(guī)劃中最重要的概念

57、之一，是線性規(guī)劃中最重要的概念之一，對于每一線性規(guī)劃問題（稱為原始問題）都有另對于每一線性規(guī)劃問題（稱為原始問題）都有另一個線性規(guī)劃問題（稱為對偶問題）與之對應，一個線性規(guī)劃問題（稱為對偶問題）與之對應，原始問題與對偶問題之間有密切的聯(lián)系，它們是原始問題與對偶問題之間有密切的聯(lián)系，它們是從不同的角度來描述實質(zhì)上相同的問題。從不同的角度來描述實質(zhì)上相同的問題。第3章 線性規(guī)劃73對偶問題的定義對偶問題的定義 原始問題原始問題 對偶問題對偶問題maxminminTTTTzss00或c xb ww bAxbA wcxw由原問題給出對偶問題的原則由原問題給出對偶問題的原則（）（1）目標函數(shù)的對偶關系是

58、）目標函數(shù)的對偶關系是“極大極大”對對“極小極小”；變量變量x用用w替換；向量替換；向量b和和c對調(diào)位置；對調(diào)位置；（3-23）第3章 線性規(guī)劃74（2）約束條件）約束條件“”對對“”；系數(shù)矩陣；系數(shù)矩陣“A”變?yōu)樽優(yōu)椤癆T ”；（3）對偶前后變量都是非負的；）對偶前后變量都是非負的；（4）原問題各約束條件的形式不統(tǒng)一時，必須統(tǒng)一）原問題各約束條件的形式不統(tǒng)一時，必須統(tǒng)一為為“”或或“” （此時不必考慮右側(cè)向量中的元素是（此時不必考慮右側(cè)向量中的元素是否為正），約束形式統(tǒng)一后再確定對偶問題形式；否為正），約束形式統(tǒng)一后再確定對偶問題形式；（5）如果原問題有等式約束，需將該條件用等價）如果原問題

59、有等式約束，需將該條件用等價的兩個不等式約束條件替換，即的兩個不等式約束條件替換，即f (x)=k 可以改寫可以改寫成兩個不等式約束條件成兩個不等式約束條件 f (x)k ， - -f (x) - -k 。注：注：原問題對偶的對偶仍是原問題原問題對偶的對偶仍是原問題. 這種性質(zhì)稱為對偶這種性質(zhì)稱為對偶關系的關系的“對合對合”性質(zhì)性質(zhì).一對相互對偶的線性規(guī)劃問題一對相互對偶的線性規(guī)劃問題,其其中任一個都可以稱作原問題中任一個都可以稱作原問題,而另一個稱為它的對偶問而另一個稱為它的對偶問題題.第3章 線性規(guī)劃75例例3-14 () ：給出以下線性規(guī)劃問題的對偶問題給出以下線性規(guī)劃問題的對偶問題12

60、12121212max2312541620zxxxxxxxxxx解：解：該題約束條件形式不統(tǒng)一，需統(tǒng)一后再求對偶問題該題約束條件形式不統(tǒng)一，需統(tǒng)一后再求對偶問題.1212121212112max23124165520,0zxxxxxxxxxxxxx 統(tǒng)一約束條件形式統(tǒng)一約束條件形式第3章 線性規(guī)劃76原問題的對偶問題：原問題的對偶問題：12345123451234min121655231420(15)iswwwwwwwwwwwwwwwi 化為標準型化為標準型1234512345612347max121655231420(17)iswwwwwwwwwwwwwwwwwi 第3章 線性規(guī)劃77二、線