第1章運籌學(xué)基礎(chǔ)與應(yīng)用-第六版

第1章運籌學(xué)基礎(chǔ)與應(yīng)用-第六版第一頁，共138頁。2023/3/102第一章線性規(guī)劃及單純形法

(LinearProgramming&SimplexMethod)§1一般線性規(guī)劃問題的數(shù)學(xué)模型§2圖解法§3單純形法原理§4單純形法的計算步驟§5單純形法的進一步討論§6數(shù)據(jù)包絡(luò)分析(DEA)§7應(yīng)用舉例第二頁，共138頁。例2(教材第9頁)生產(chǎn)計劃問題常山機器加工廠，利用A、B、C三種不同設(shè)備加工生產(chǎn)Ⅰ、Ⅱ兩種產(chǎn)品。按工藝要求，每生產(chǎn)一個單位的Ⅰ產(chǎn)品，需要占用三種設(shè)備2、4、0小時；每生產(chǎn)一個單位的Ⅱ產(chǎn)品，需要占用三種設(shè)備2、0、5小時。已知三種設(shè)備加工能力分別為12、16、15小時。且每生產(chǎn)一個單位的Ⅰ產(chǎn)品可獲取2單位的利潤；每生產(chǎn)一個單位的Ⅱ產(chǎn)品可獲取2單位的利潤。問應(yīng)當如何安排加工，可使獲取的總利潤最大？2023/3/103第三頁，共138頁。2023/3/104§1一般線性規(guī)劃問題的數(shù)學(xué)模型

1.1引例例1、生產(chǎn)計劃問題

Ⅰ

Ⅱ設(shè)備能力（小時）設(shè)備A2212設(shè)備B4

016設(shè)備C0515利潤（元）23問：Ⅰ，Ⅱ兩種產(chǎn)品各加工多少單位,可獲最大利潤?第四頁，共138頁。2023/3/105

2x1+2x2

12

s.t.

4x1

16

5x2

15

x1，x2

0注意模型特點

maxZ=2x1+3x2解:設(shè)產(chǎn)品Ⅰ,Ⅱ產(chǎn)量分別為變量x1，x2防災(zāi)科技學(xué)院第五頁，共138頁。附例

營養(yǎng)配餐問題假定一個成年人每天需要從食物中獲得3000千卡的熱量、55克蛋白質(zhì)和800毫克的鈣。如果市場上只有四種食品可供選擇，它們每千克所含的熱量和營養(yǎng)成分和市場價格見下表。問如何選擇才能在滿足營養(yǎng)的前提下使購買食品的費用最?。康诹?，共138頁。各種食物的營養(yǎng)成分表每天需要300055800第七頁，共138頁。各種食物的營養(yǎng)成分表每天需要300055800x1x2x3x4第八頁，共138頁。解：設(shè)xj為第j種食品每天的購入量，則配餐問題的線性規(guī)劃模型為：第九頁，共138頁。2023/3/1010線性規(guī)劃模型的特點決策變量：向量X=(x1…xn)T決策人要考慮和控制的因素，非負約束條件：關(guān)于X的線性等式或不等式目標函數(shù)：Z=?(x1

…xn)為關(guān)于X的線性函數(shù)，求Z極大或極小第十頁，共138頁。防災(zāi)科技學(xué)院11LP問題一般可整理為：決策變量及各類系數(shù)之間的對應(yīng)關(guān)系第十一頁，共138頁。防災(zāi)科技學(xué)院12上述模型的共同特征：每一個線性規(guī)劃問題都用一組決策變量表示某一方案，這組決策變量的值代表一個具體方案。一般這些變量的取值是非負且連續(xù)的；都有關(guān)于各種資源和資源使用情況的技術(shù)數(shù)據(jù)，創(chuàng)造新價值的數(shù)據(jù)；存在可以量化的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示;都有一個達到某一目標的要求，可用決策變量的線性函數(shù)(稱為目標函數(shù))來表示。按問題的要求不同，要求目標函數(shù)實現(xiàn)最大化或最小化。第十二頁，共138頁。2023/3/10131.2線性規(guī)劃問題的數(shù)學(xué)模型三個組成要素：1.決策變量:是決策者為實現(xiàn)規(guī)劃目標采取的方案、措施，是問題中要確定的未知量。2.目標函數(shù):指問題要達到的目的要求，表示為決策變量的函數(shù)。3.約束條件:指決策變量取值時受到的各種可用資源的限制，表示為含決策變量的等式或不等式。第十三頁，共138頁。線性規(guī)劃的數(shù)學(xué)模型由三個要素構(gòu)成

決策變量Decisionvariables目標函數(shù)Objectivefunction約束條件Constraints其特征是：（1）問題的目標函數(shù)是多個決策變量的線性函數(shù)，通常是求最大值或最小值；（2）問題的約束條件是一組多個決策變量的線性不等式或等式。

怎樣辨別一個模型是線性規(guī)劃模型？

第十四頁，共138頁。2023/3/1015一般線性規(guī)劃問題的數(shù)學(xué)模型：目標函數(shù)：約束條件：第十五頁，共138頁。線性規(guī)劃模型的簡寫形式(求和符號)第十六頁，共138頁。一般線性規(guī)劃(LP)問題模型向量形式其中：第十七頁，共138頁。一般線性規(guī)劃(LP)問題模型矩陣形式其中：第十八頁，共138頁。2023/3/10191.3線性規(guī)劃問題的標準形式標準形式：標準形式特點：4.決策變量取值非負。1.目標函數(shù)為求極大值；2.約束條件全為等式；3.約束條件右端常數(shù)項全為非負；第十九頁，共138頁。2023/3/1020一般線性規(guī)劃問題如何化為標準型：1.目標函數(shù)求極小值：令：，即化為：第二十頁，共138頁。2023/3/10212.約束條件為不等式：（1）當約束條件為“≤”時如：可令：，顯然（2）當約束條件為“≥”時如：可令：，顯然稱為松弛變量。稱為剩余變量。第二十一頁，共138頁。2023/3/1022松弛變量和剩余變量統(tǒng)稱為松弛變量（3）目標函數(shù)中松弛變量的系數(shù)由于松弛變量和剩余變量分別表示未被充分利用的資源以及超用的資源，都沒有轉(zhuǎn)化為價值和利潤，因此在目標函數(shù)中系數(shù)為零。第二十二頁，共138頁。2023/3/10233.取值無約束的變量如果變量xj

代表某產(chǎn)品當年計劃數(shù)與上一年計劃數(shù)之差，顯然xj

的取值可能是正也可能是負，這時可令：其中：令4.變量xj≤0，顯然第二十三頁，共138頁。2023/3/1024例3(教材15頁)

將下述LP模型化為標準型第二十四頁，共138頁。2023/3/1025解：令得標準形式為：第二十五頁，共138頁。2023/3/1026第二十六頁，共138頁。線性規(guī)劃問題及數(shù)學(xué)模型線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）第二十七頁，共138頁。線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simplex）第二十八頁，共138頁。線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simplex）1963年Dantzig寫成“LinearProgrammingandExtension”第二十九頁，共138頁。線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simplex）1963年Dantzig寫成“LinearProgrammingandExtension”1979年蘇聯(lián)的Khachian提出“橢球法”第三十頁，共138頁。線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzig）1951年提出單純形算法（Simplex）1963年Dantzig寫成“LinearProgrammingandExtension”1979年蘇聯(lián)的Khachian提出“橢球法”1984年印度的Karmarkar提出“投影梯度法”,又稱多項式時間算法

第三十一頁，共138頁。線性規(guī)劃（LinearProgramming)創(chuàng)始人：1947年美國人G.B.丹齊克（Dantzing）1951年提出單純形算法（Simplex）1963年Dantzing寫成“LinearProgrammingandExtension”1979年蘇聯(lián)的Khachian提出“橢球法”1984年印度的Karmarkar提出“投影梯度法”

線性規(guī)劃是研究線性不等式組的理論，或者說是研究（高維空間中）凸多面體的理論，是線性代數(shù)的應(yīng)用和發(fā)展。第三十二頁，共138頁。2023/3/1033求解線性規(guī)劃問題：就是從滿足約束方程組和約束不等式的決策變量取值中，找出使得目標函數(shù)達到最大的值。1.4線性規(guī)劃問題的解的概念第三十三頁，共138頁。2023/3/1034可行解：滿足所有約束條件的解稱為可行解，所有可行解的集合稱為可行域。最優(yōu)解：使目標函數(shù)達到最大值的可行解。基：約束方程組的一個滿秩子矩陣稱為規(guī)劃問題的一個基，基中的每一個列向量稱為基向量，與基向量對應(yīng)的變量稱為基變量，其他變量稱為非基變量?；猓涸诩s束方程組中，令所有非基變量為0，可以解出基變量的唯一解，這組解與非基變量的0共同構(gòu)成基解?；尚薪猓簼M足變量非負的基解稱為基可行解可行基：對應(yīng)于基可行解的基稱為可行基第三十四頁，共138頁。2023/3/1035例：考察下述線性規(guī)劃問題：第三十五頁，共138頁。2023/3/1036（1）可行解，如或滿足約束條件，所以是可行解。（2）基系數(shù)矩陣A：其中或都構(gòu)成基。而不構(gòu)成基。第三十六頁，共138頁。2023/3/1037（3）基向量、基變量是對應(yīng)于基的三個基向量，而是對應(yīng)于這三個基向量的基變量。（4）基解、基可行解、可行基是對應(yīng)于基的一個基解、基可行解。是對應(yīng)于基的一個基解、基可行解。均是可行基。練習：P14，例4第三十七頁，共138頁。2023/3/1038

為了便于建立n維空間中線性規(guī)劃問題的概念及便于理解求解一般線性規(guī)劃問題的單純形法的思路，先介紹圖解法。求解下述線性規(guī)劃問題：§2線性規(guī)劃問題的圖解法第三十八頁，共138頁。2023/3/1039畫出線性規(guī)劃問題的可行域：目標函數(shù)等值線第三十九頁，共138頁。2023/3/10401、可行域：約束條件所圍成的區(qū)域。2、基可行解：對應(yīng)可行域的頂點。3、目標函數(shù)等值線：4、目標函數(shù)最優(yōu)值:最大截距所對應(yīng)的。

目標函數(shù)等值線有無數(shù)條，且平行。（觀察規(guī)律)第四十頁，共138頁。2023/3/1041解的幾種情況：(2)無窮多最優(yōu)解(1)唯一最優(yōu)解若目標函數(shù)改為：約束條件不變，則:目標函數(shù)等值線此時，線段上所有點都是最優(yōu)值點。第四十一頁，共138頁。2023/3/1042解的幾種情況：(4)無界解(3)無可行解：當可行域為空集時，無可行解。若目標函數(shù)不變，將約束條件1和3去掉，則可行域及解的情況見下圖。目標函數(shù)等值線此時，目標函數(shù)等值線可以向上無窮遠處平移，Z值無界。第四十二頁，共138頁。2023/3/1043幾點說明：1、圖解法只能用來求解含有兩個決策變量的線性規(guī)劃問題。2、若最優(yōu)解存在，則必在可行域的某個頂點處取得。3、線性規(guī)劃問題的解可能是：唯一最優(yōu)解、無窮多最優(yōu)解、無最優(yōu)解、無界解。第四十三頁，共138頁。2023/3/1044§3．單純形法原理凸集：如果集合C中任意兩個點，其連線上的所有點也都是集合C中的點。上圖中（1）（2）是凸集，（3）（4）不是凸集頂點：如果對于凸集C中的點X，不存在C中的任意其它兩個不同的點，使得X在它們的連線上，這時稱X為凸集的頂點。3.1預(yù)備知識第四十四頁，共138頁。2023/3/10453.2線性規(guī)劃問題基本定理定理1:若線性規(guī)劃問題存在可行解，則問題的可行域是凸集。證明:設(shè)是線性規(guī)劃的任意兩個可行解，則于是對于任意的，設(shè)，則所以也是問題的可行解，即可行域是凸集。

第四十五頁，共138頁。2023/3/1046引理:

線性規(guī)劃問題的可行解X為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)。證明:設(shè)（1）必要性顯然。（2）設(shè)A的秩為m。可行解X的前k個分量為正，且它們對應(yīng)的系數(shù)列向量線性無關(guān)，則。當時，恰好構(gòu)成一組基，而就是這組基對應(yīng)的基可行解。

當時，在基礎(chǔ)上從其余列向量中可以找出個線性無關(guān)的向量，恰好構(gòu)成一組基，而X就是這組基對應(yīng)的基可行解。第四十六頁，共138頁。2023/3/1047定理2:

線性規(guī)劃問題的基可行解X對應(yīng)線性規(guī)劃問題可行域（凸集）的頂點。證明:問題即是要證明:X是基可行解X是可行域頂點，也即要證明其逆否命題：X不是基可行解X不是可行域頂點。（1）X不是基可行解X不是可行域頂點。假設(shè)X是可行解，但不是基可行解，

X的前k個分量為正,其余分量為0，則有又X不是基可行解，所以由引理知，正分量對應(yīng)的列向量線性相關(guān)。即存在一組不全為零的數(shù)，使得第四十七頁，共138頁。2023/3/1048用非零常數(shù)乘以上式得：（1）+（3）得：（1）-（3）得：令選擇合適的，使得所有的于是均是可行解，并且，所以X不是可行域頂點。第四十八頁，共138頁。2023/3/1049（2）X不是可行域頂點X不是基可行解。設(shè)不是可行域的頂點，因而可以找到可行域內(nèi)另兩個不同的點，使得，用分量表示即為：

易知，當時，必有所以所以于是（1）-（2）得而不全為零，于是知線性相關(guān)，X不是基可行解。第四十九頁，共138頁。2023/3/1050定理3:

若線性規(guī)劃問題有最優(yōu)解，一定存在一個基可行解是最優(yōu)解。引理：

有界

凸集中的任何一點均可表示成頂點的凸組合。證明:假設(shè)是可行域頂點，不是可行域頂點，且目標函數(shù)在處達到最優(yōu)，即。由引理知：可表示為的凸組合，即因此假設(shè)是所有中最大者，則第五十頁，共138頁。2023/3/1051而是目標函數(shù)的最大值，所以也是最大值，也即，目標函數(shù)在可行域的某個頂點達到了最優(yōu)。從上述三個定理可以看出，要求線性規(guī)劃問題的最優(yōu)解，只要比較可行域（凸集）各個頂點對應(yīng)的目標函數(shù)值即可，最大的就是我們所要求的最優(yōu)解。第五十一頁，共138頁。2023/3/10523.3確定初始基可行解尋求最優(yōu)解的思路：線性規(guī)劃問題的最優(yōu)解一定會在基可行解中取得，我們先找到一個初始基可行解。然后設(shè)法轉(zhuǎn)換到另一個基可行解，并使得目標函數(shù)值不斷增大，直到找到最優(yōu)解為止。設(shè)給定線性規(guī)劃問題：第五十二頁，共138頁。2023/3/1053因此約束方程組的系數(shù)矩陣為：添加松弛變量得其標準形為：第五十三頁，共138頁。2023/3/1054由于該矩陣含有一個單位子矩陣，因此，這個單位陣就是一組基，就可以求出一個基可行解：說明：如果約束條件不全是形式，如含所有形式，則無法找到一個單位陣做為一組基，這時需要添加人工變量。后面的內(nèi)容介紹。稱其為初始基可行解。第五十四頁，共138頁。2023/3/10553.4從初始基可行解轉(zhuǎn)換為另一個基可行解

思路：對初始基可行解的系數(shù)矩陣進行初等行變換，構(gòu)造出一個新的單位矩陣，其各列所對應(yīng)的變量即為一組新的基變量，求出其數(shù)值，就是一個新的基可行解。

設(shè)有初始基可行解，并可設(shè)前m個分量非零，即，于是第五十五頁，共138頁。2023/3/1056

由構(gòu)造初始可行基的方法知前m個基向量恰好是一個單位陣，所以約束方程組的增廣矩陣為由于任意系數(shù)列向量均可由基向量組線性表示，則非基向量中的用基向量組線性表示為：第五十六頁，共138頁。2023/3/1057設(shè)有，則（1）+（2）得：由此式可知，我們找到了滿足約束方程組的另一個解，要使其成為可行解，只要對所有i=1,2,…m，下式成立要使其成為基可行解，上面m個式中至少有一個取零。（基可行解中非零分量的個數(shù)不超過m個。）（與比較）第五十七頁，共138頁。2023/3/1058只要取于是前m個分量中的第l個變?yōu)榱悖溆喾秦?，第j個分量為正，于是非零分量的個數(shù)，并可證得線性無關(guān)，所以是新的基可行解。第五十八頁，共138頁。2023/3/10593.4最優(yōu)性檢驗和解的判別設(shè)有基可行解比較兩者對應(yīng)的目標函數(shù)值，哪一個更優(yōu)？第五十九頁，共138頁。2023/3/10602）若對所有的，則，

就是最優(yōu)解。是判斷是否達到最優(yōu)解的標準，稱為檢驗數(shù)。1）當時，，目標函數(shù)值得到了改進，

不是最優(yōu)解，需要繼續(xù)迭代。易知第六十頁，共138頁。2023/3/1061當所有時，現(xiàn)有頂點對應(yīng)的基可行解即為最優(yōu)解。當所有時，又對某個非基變量有則該線性規(guī)劃問題有無窮多最優(yōu)解。3.如果存在某個，又向量的所有分量，對任意，恒有，則存在無界解。結(jié)論第六十一頁，共138頁。2023/3/1062§4單純形法的計算步驟

Max(min)Z=c1x1+c2x2+…+cnxna11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2………am1x1+am2x2+…+amnxn=bmxj0(j=1,…,n)設(shè)有線性規(guī)劃問題：第六十二頁，共138頁。2023/3/1063(1)找到初始可行基，建立初始單純形表.(4)重復(fù)二、三兩步，直至找到最優(yōu)解?！?單純形法的計算步驟

(2)進行最優(yōu)性檢驗。計算檢驗數(shù)，若所有≤0

則得最優(yōu)解，結(jié)束.否則轉(zhuǎn)下步.若某≥0而≤0，則最優(yōu)解無界，結(jié)束.否則轉(zhuǎn)下步.(3)從一個可行解轉(zhuǎn)換到另一個目標函數(shù)值更大的基可行解。由最大增加原則確定進基變量；由最小比值原則選擇出基變量；以為主元素進行換基迭代。第六十三頁，共138頁。2023/3/1064……(1)找到初始可行基，建立初始單純形表.00…………………是初始基。第六十四頁，共138頁。2023/3/1065(2)進行最優(yōu)性檢驗計算檢驗數(shù)，若所有≤0

則得最優(yōu)解，結(jié)束.否則轉(zhuǎn)下步.若某≥0而≤0，則最優(yōu)解無界，結(jié)束.否則轉(zhuǎn)下步.檢驗數(shù)的計算方法：基變量的檢驗數(shù)一定為0。判斷是否達到最優(yōu)時，只要考慮非基變量檢驗數(shù)。第六十五頁，共138頁。2023/3/1066(3)從一個可行解轉(zhuǎn)換到另一個目標函數(shù)值更大的基可行解。由最小比值原則選擇出基變量；進基變量由最大增加原則確定進基變量：

當某些非基變量的檢驗數(shù)時，為使目標函數(shù)值增加地更快，一般選擇正檢驗數(shù)中最大者對應(yīng)的非基變量進基

，成為新的基變量。

為確保新的基可行解的非零分量非負，按下述規(guī)則求得最小比值，其所對應(yīng)的原基變量中的出基。于是，新的一組基是：第六十六頁，共138頁。2023/3/1067以為主元素進行換基迭代：即利用初等行變換將進基變量

所在的系數(shù)列變?yōu)閱挝涣邢蛄?，而變?yōu)?。這樣原來基矩陣中的就不再是單位向量，取而代之的是，這樣就找到了一組新的基。(4)重復(fù)二、三兩步，直至找到最優(yōu)解。說明：若目標函數(shù)是求最小，可以不必將其轉(zhuǎn)變?yōu)榍笞畲螅谑褂脝渭冃畏ㄇ蠼鈺r，確定進基變量，應(yīng)找負檢驗數(shù)中最小者，并應(yīng)以檢驗數(shù)全部為正作為判別最優(yōu)的條件。第六十七頁，共138頁。2023/3/1068解將模型標準化附例第六十八頁，共138頁。1202010Cj比值CBXBb檢驗數(shù)j2023/3/1069x1x2x3x4x5350008101003634001x3x4x5000035000-12/2=636/4=9作出初始單純形表，進行迭代檢驗數(shù)最大比值最小第六十九頁，共138頁。12300-21810100檢驗數(shù)j2023/3/107060101/20x3x2x5050-30300-5/208-4Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=9第七十頁，共138頁。2023/3/1071Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4檢驗數(shù)j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1唯一最優(yōu)解:X*=(4,6,4,0,0)T，Z*=42第七十一頁，共138頁。2023/3/1072特殊情況：（1）出現(xiàn)兩個或兩個以上相同的最大，此時可任選一個所對應(yīng)的變量作為進基變量。

（2）利用規(guī)則決定出基變量時，出現(xiàn)兩個或兩個以上的最小比值，則迭代后，會出現(xiàn)一個或幾個基變量等于零的情況，我們稱此為退化現(xiàn)象。進而可能會出現(xiàn)迭代過程的循環(huán)，致使永遠達不到最優(yōu)解。出現(xiàn)退化現(xiàn)象時，可考慮采用“勃蘭特”規(guī)則決定進基變量和出基變量的選擇。第七十二頁，共138頁。2023/3/10735.1人工變量

用單純形法解題時，需要有一個單位陣作為初始基。當約束條件都是“≤”時，加入松弛變量就形成了初始基。但實際存在“≥”或“＝”型的約束，沒有現(xiàn)成的單位矩陣。采用人造基的辦法：添加人工變量，構(gòu)造單位矩陣§5單純形法的進一步討論

第七十三頁，共138頁。2023/3/1074

人工單位矩陣的構(gòu)造方法在“

”的不等式約束中減去一個剩余變量后可變?yōu)榈仁郊s束，但此剩余變量的系數(shù)是（-1），所以再加入一個人工變量，其系數(shù)是（+1），因而在系數(shù)矩陣中可得到一個相應(yīng)的單位向量，以便構(gòu)成初始單位陣，即初始基矩陣。在原本就是“

=”的約束中可直接添加一個人工變量，以便得到初始基矩陣。注意：人工變量是在等式中人為加進的，只有它等于0時，約束條件才是它本來的意義。求解帶人工變量的線性規(guī)劃有兩種方法：☆大M法☆兩階段法第七十四頁，共138頁。2023/3/10755.2大M法△沒有單位矩陣，不符合構(gòu)造初始基的條件，需加入人工變量?！魅斯ぷ兞孔罱K必須等于0才能保持原問題性質(zhì)不變。為保證人工變量為0，在目標函數(shù)中令其系數(shù)為（-M）。（求最小值問題中，人工變量系數(shù)取M）△M為無限大的正數(shù)，這是一個懲罰項，倘若人工變量不為零，則目標函數(shù)就永遠達不到最優(yōu)，所以必須將人工變量逐步從基變量中替換出去?！魅缛舻阶罱K表中人工變量仍沒有置換出去，那么這個問題就沒有可行解，當然亦無最優(yōu)解。第七十五頁，共138頁。2023/3/1076例解線性規(guī)劃解化為標準型此時無單位矩陣作為初始基。第七十六頁，共138頁。2023/3/1077添加人工變量，構(gòu)造初始基：注意：若求最小值問題，則目標函數(shù)中人工變量系數(shù)取M。第七十七頁，共138頁。2023/3/1078-30100-M-Mx1x2x3x4x5x6x71111000-21-10-1100310001初始單純形表：CCBXBb0x44-Mx61-Mx79-3-2M4M10-M0041330211-10-21-10-11060403-311-10x430x21-Mx76-3+6M01+4M03M-3M0第七十八頁，共138頁。2023/3/1079-30100-M-Mx1x2x3x4x5x6x7CCBXBb00303/2-M-3/2-M+1/2-33/20001-1/21/2-1/2011/30001/3102/301/2-1/21/60x400x23-3x11-3/2000-3/4-M+3/4-M-1/40x400x25/21x33/20001-1/21/2-1/2-1/2100-1/41/41/43/20103/4-3/41/4第七十九頁，共138頁。2023/3/1080此時人工變量全部出基，并已達最優(yōu)條件。最優(yōu)解為，最優(yōu)值為注意：計算機上使用大M法時，需要用機器最大字長的數(shù)字代替M，但當某些系數(shù)與之較接近時，還是可能會出錯。另外一種求解帶人工變量的線性規(guī)劃問題的方法不會出現(xiàn)這種問題-------兩階段法。第八十頁，共138頁。2023/3/1081例解線性規(guī)劃解按大M法構(gòu)造人造基，引入人工變量x4,x5的輔助問題如下：第八十一頁，共138頁。2023/3/1082作出單純形表，進行迭代Cj比值CBXBb檢驗數(shù)jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24檢驗數(shù)j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M第八十二頁，共138頁。2023/3/1083檢驗數(shù)j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1檢驗數(shù)j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-2最優(yōu)解:X*=(3,0,1)T，Z*=7第八十三頁，共138頁。2023/3/10845.3兩階段法

第一階段：構(gòu)造目標函數(shù)只含人工變量的線性規(guī)劃問題，求解后判斷原線性規(guī)劃問題是否有基本可行解，若有，則進行第二階段；第二階段：將第一階段的最終單純形表所對應(yīng)的解，去掉人工變量，作為第二階段的初始單純形表的初始基可行解，進行單純形法的迭代。第八十四頁，共138頁。2023/3/1085解（1）化標準型、并添加人工變量得：

（此處未將目標變?yōu)镸AX）例：

第八十五頁，共138頁。2023/3/1086（2）構(gòu)造第一階段問題：

說明：原問題目標函數(shù)無論是求MAX還是求MIN，構(gòu)造的第一階段問題目標函數(shù)都是求最小MIN。第八十六頁，共138頁。2023/3/1087求解第一階段問題：第八十七頁，共138頁。2023/3/1088此時所得可行解目標函數(shù)值為0，故原規(guī)劃問題有基可行解。轉(zhuǎn)入第二步。第八十八頁，共138頁。2023/3/1089（3）去掉人工變量，得到第二階段的單純形表，在此基礎(chǔ)上繼續(xù)求解。最優(yōu)解為：第八十九頁，共138頁。2023/3/10905.4關(guān)于解的不同情況的判別1、無窮多最優(yōu)解例：解：將問題化為標準型：第九十頁，共138頁。2023/3/1091第九十一頁，共138頁。2023/3/1092從上表中可知，已達最優(yōu)解，為，而，若將選為進基變量迭代后，可得另一最優(yōu)解。上述兩最優(yōu)解分別對應(yīng)兩個頂點，而兩點連線上的點均是最優(yōu)解，故有無窮多最優(yōu)解。判別無窮多最優(yōu)解的方法：單純形表的檢驗數(shù)行已達最優(yōu)性條件（全部小于或等于零），且有一個非基變量的檢驗數(shù)為零，此時有無窮多最優(yōu)解。第九十二頁，共138頁。2023/3/1093

2、無可行解

例用單純形表求解下列線性規(guī)劃問題解：化為標準型：第九十三頁，共138頁。2023/3/1094基變量CB2030000-Mbx1x2s1s2s3

a1s1s2a100-M31010001001001100-11150304015—40cj-zj20+M30+M00-M0-40M單純形表求解線性規(guī)劃問題第九十四頁，共138頁。2023/3/10951x2s2a1300-M3/1011/100001001007/100-1/100-111530255030250/7cj-zj11+7/10M0-3-M/100-M02x2x1a13020-M011/10-3/100010010000-1/10-7/10-116304cj-zj00-3-M/10-11-7M/10-M0迭代次數(shù)基變量CBx1x2s1s2s3a1b比值2030000-M單純形法的最終表里有人工變量大于零，則此線性規(guī)劃無可行解。第九十五頁，共138頁。2023/3/1096

3、無界解例用單純形表求解下面線性規(guī)劃問題。解第九十六頁，共138頁。2023/3/1097

迭代次數(shù)基變量CBx1x2s1s2b比值11000s1s2001-110-3201161—cj-zj110001x1s2101-1100-13119cj-zj02-101此時的檢驗數(shù)仍為正，但系數(shù)列全為負，此時可判斷這個線性規(guī)劃問題是無界的，即目標函數(shù)值可以取得無限大。第九十七頁，共138頁。2023/3/1098

事實上，此從1次迭代的單純形表中，得到約束方程：

移項可得：由此可知，目標函數(shù)可以任意大，即無界。第九十八頁，共138頁。2023/3/1099練習：用大M法求解下列線性規(guī)劃問題1、2、第九十九頁，共138頁。2023/3/10100解1：將模型化為標準型得：建立單純形表并計算如下第一百頁，共138頁。2023/3/10101顯然，檢驗數(shù)已全部非正，已達最優(yōu)解，但非基變量X2的檢驗數(shù)為0，故知此問題有無窮多最優(yōu)解。第一百零一頁，共138頁。2023/3/10102解2：將模型化為標準型得：建立單純形表并計算如下第一百零二頁，共138頁。2023/3/10103第一百零三頁，共138頁。2023/3/10104最優(yōu)解為（4，4）第一百零四頁，共138頁。第一章線性規(guī)劃及單純形法LinearProgramming（LP）

線性規(guī)劃問題及其數(shù)學(xué)模型

線性規(guī)劃的圖解法

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

線性規(guī)劃問題的應(yīng)用

線性規(guī)劃問題的求解方法第一百零五頁，共138頁。單純形法的求解思路是否循環(huán)第一百零六頁，共138頁。⑥以alk為主元素進行迭代，利用初等行變換將xk所在列化為單位向量，即alk化為1，其它元素化為0，得到改進的可行基，轉(zhuǎn)入第③步。計算步驟總結(jié)（有可行解時）①將線性規(guī)劃問題化成標準形式;②找出一個m階單位矩陣作初始可行基，得到初始基可行解;③計算各非基變量xj的檢驗數(shù)j，若所有j≤0，則問題已得到最優(yōu)解，停止計算，否則轉(zhuǎn)入下步;④若存在某個s>0，且對應(yīng)的所有系數(shù)ais≤0，則此問題是無界解，停止計算，否則轉(zhuǎn)入下步;⑤根據(jù)max{j|j＞0}=k原則，確定xk為入基變量，再按=min{bi/aik|aik＞0}=bl/alk規(guī)則，確定xl為出基變量，得到改進的基可行解。第一百零七頁，共138頁。單純形表迭代次數(shù)基變量CBx1x2x3x4x5b比值ithZj目標系數(shù)區(qū)約束條件系數(shù)區(qū)右端系數(shù)檢驗系數(shù)區(qū)基變量區(qū)第一百零八頁，共138頁?；兞康南禂?shù)目標函數(shù)中變量的系數(shù)決策變量約束方程組的系數(shù)矩陣出基變量判斷參數(shù)方程右端常數(shù)項各變量的檢驗數(shù)基變量CB基bcj→cj－zj單純形表第一百零九頁，共138頁。由單純形表判別解的類別無可行解唯一最優(yōu)解所有無窮多最優(yōu)解無界解（無最優(yōu)解）存在某個，且所對應(yīng)的系數(shù)最優(yōu)解所有非基變量的檢驗數(shù)*第一百一十頁，共138頁。由單純形表判別解的類別無可行解唯一最優(yōu)解所有無窮多最優(yōu)解無界解（無最優(yōu)解）存在某個，且所對應(yīng)的系數(shù)最優(yōu)解某非基變量至少一個且所有非基變量的檢驗數(shù)*第一百一十一頁，共138頁?！?保證當前的基可行解是最優(yōu)解

至少有一個等于0，如

至少有一個大于0，如

＞0

存在，保證當xp入基時有xl出基兩個最優(yōu)解連線上的所有點都是最優(yōu)解≤0說明能得到另一個最優(yōu)基可行解第一百一十二頁，共138頁。無窮多最優(yōu)解示例：s.t.標準化s.t.第一百一十三頁，共138頁。第一百一十四頁，共138頁。此時所有檢驗數(shù)得到最優(yōu)解最優(yōu)值為第一百一十五頁，共138頁。此時所有檢驗數(shù)得另一最優(yōu)解

最優(yōu)值為第一百一十六頁，共138頁。A第一百一十七頁，共138頁。1課后題：P481.80024-235235-3/2第一百一十八頁，共138頁。練習題：求a～g的值，并判斷表中解是否最優(yōu)解單純形法計算時某一步的表格

，約束形式為，已知目標函數(shù)為松弛變量，表中解代入目標函數(shù)后得第一百一十九頁，共138頁。2023/3/10120小結(jié)表格單純形表的使用（1）化線性規(guī)劃模型為標準型，建立初始單純形表。（2）根據(jù)單純形表按照最大增加原則選擇進基變量；（3）按照最小比值原則選擇換出變量；（4）實施矩陣的初等變換進行換基迭代；（5）建立新的單純形表；（6）重復(fù)上述過程直到求得最優(yōu)表格為止。第一百二十頁，共138頁。防災(zāi)科技學(xué)院121一般地講，一個經(jīng)濟、管理問題凡滿足以下條件時，才能建立線性規(guī)劃模型。

(1)要求解問題的目標函數(shù)能用數(shù)值指標來表示，且為線性函數(shù)；

(2)存在著多種方案及有關(guān)數(shù)據(jù)；

(3)要求達到的目標是在一定約束條件下實現(xiàn)的，這些約束條件可用線性等式或不等式來描述?！?線性規(guī)劃應(yīng)用舉例

第一百二十一頁，共138頁。防災(zāi)科技學(xué)院122例合理利用線材問題。現(xiàn)要做100套鋼架，每套需用長為2.9m，2.1m和1.5m的元鋼各一根。已知原料長7.4m，問應(yīng)如何下料，使用的原材料最省?！痉治觥孔詈唵巫龇ㄊ牵诿恳桓牧仙辖厝?.9m，2.1m和1.5m的元鋼各一根組成一套，每根原材料剩下料頭0.9m（7.4-2.9-2.1-1.5=0.9)。為了做100套鋼架，需用原材料100根，共有90m料頭。若改為用套裁，這可以節(jié)約原材料。下面有幾種套裁方案，都可以考慮采用。見表2-12。表§7線性規(guī)劃應(yīng)用舉例

第一百二十二頁，共138頁。所有可能的裁截方案①②