6.5線性規(guī)劃初步

6.5線性規(guī)劃初步一、線性規(guī)劃的數(shù)學(xué)模型二、兩個變量線性規(guī)劃問題的圖解法三、單純形法一、線性規(guī)劃的數(shù)學(xué)模型1．線性規(guī)劃問題實例例5．1

（配料問題）某工廠在計劃期內(nèi)要生產(chǎn)甲、乙兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需要的設(shè)備臺時，A、B兩種原材料的消耗以及每件產(chǎn)品可獲得的利潤見下表．問應(yīng)如何安排生產(chǎn)計劃使得該工廠獲得利潤最多？產(chǎn)品消耗材料甲乙資源限量設(shè)備１２8（臺時）原材料Ａ４０17(千克)原材料Ｂ０４12（千克）單位產(chǎn)品利潤（萬元）54解設(shè)、分別表示在計劃期內(nèi)產(chǎn)品甲、乙的產(chǎn)量，，表示利潤．由于資源的限制有利潤的最大化，受條件這就是該問題的線性規(guī)劃問題的數(shù)學(xué)模型．的限制．例5．2

（運輸問題）在A1、A2兩個糧庫里分別裝有6噸玉米和102噸玉米，要運到B1、B2、B3三個市場去出售．三個市場的需求量分別是34噸、75噸、49噸，各倉庫到各市場的運價（元/噸）見表6．3．如何調(diào)運，才能使總運費最??？表6．3倉庫到市場的運價表單位元/噸市場運價倉庫B1B2B3

A1607090

A2758070解以表示從倉庫運到市場的玉米數(shù)量，

顯然

根據(jù)分析，將其轉(zhuǎn)化為數(shù)學(xué)問題：就是求一組變量的值，使它滿足限制條件：

并使運費最小，即例5．3某商業(yè)銀行開展貸款業(yè)務(wù)，有兩種方案可供選擇．方案Ａ每一元貸款一年后可獲利潤0．7元；方案Ｂ每一元貸款兩年后可獲利潤２元．在方案Ｂ中，要求貸款的時間是兩年的倍數(shù)，要想在第三年年底所獲本利最多，應(yīng)該怎樣貸款1000000元？按方案Ａ進行投資，投資元到第三年年底的本利和為（元），按方案Ｂ進行投資，投資元到第二年年底的本利和為解設(shè)方案A的投資為元，方案Ｂ的投資元．（元），然后再把元按方案Ａ進行投資到第三年年底的本利和為，因此，到第三年年底商業(yè)銀行可獲得本利和為．由此題的條件可知，根據(jù)以上分析將其轉(zhuǎn)化為數(shù)學(xué)問題就是求滿足約束條件下，使的解．2．線性規(guī)劃問題的標(biāo)準(zhǔn)形式目標(biāo)函數(shù)為：約束條件為：在約束條件中，稱為決策變量．這種形式的線性規(guī)劃問題稱為線性規(guī)劃問題的標(biāo)準(zhǔn)形式．其特征為：（１）所有約束條件都由等式表示，且等式右端的常數(shù)非負(fù)；（２）決策變量非負(fù)；（３）求目標(biāo)函數(shù)的最大值．用矩陣形式表示為：

其中

例5.4

將下列線性規(guī)劃數(shù)學(xué)模型化成標(biāo)準(zhǔn)形式．設(shè)目標(biāo)函數(shù)約束條件解因為沒有非負(fù)限制，引入新變量

使；引入松弛變量則化成標(biāo)準(zhǔn)型為二、兩個變量線性規(guī)劃問題的圖解法例5．5

求的最大值，約束條件為．解以為橫坐標(biāo)軸，為縱坐標(biāo)軸，建立坐標(biāo)系

0C（1.5，1）即，．例５．6

用圖解法解線性規(guī)劃問題解步驟同前題，畫出可行域．0陰影部分是無界區(qū)域．因為可行域無界，所以找不到的最大值，故無最優(yōu)解．

三、單純形法1．線性規(guī)劃問題的基與解設(shè)線性規(guī)劃問題的標(biāo)準(zhǔn)形式用矩陣表示為：假設(shè)矩陣的秩為，則稱中任意一個階滿秩矩陣為該線性規(guī)劃問題的一個基．如果變量所對應(yīng)的列則稱為基變量。其余的個變量稱為非基變量．

例5.8

設(shè)有線性規(guī)劃問題，寫出它的一個基和該基對應(yīng)的基變量和非基變量．解約束方程組的系數(shù)矩陣顯然矩陣是該線性規(guī)劃問題的一個基它所對應(yīng)的基變量是非基變量是．

在標(biāo)準(zhǔn)形式的線性規(guī)劃中，非基變量取零值的可行解叫做線性規(guī)劃問題的基本可行解，相對應(yīng)的基叫做基本可行基．最優(yōu)的基本可行解叫最優(yōu)解，所對應(yīng)的基叫最優(yōu)基．2．單純形法例5.9

用單純形法求下面線性規(guī)劃問題的最優(yōu)解．解本題的約束條件的線性規(guī)劃問題已經(jīng)是標(biāo)準(zhǔn)形，約束方程組的系數(shù)矩陣為，，選可行基所對應(yīng)的基變量就是．1.

作出對應(yīng)的單純形表6．４

221001（2）01040001181230000

表中最左邊的列是基變量，第一行是所有變量，中間是系數(shù)矩陣，最右邊的列是常數(shù)列，最下邊行是目標(biāo)函數(shù)各變量相對應(yīng)的系數(shù)，叫做檢驗數(shù)，該行也叫做檢驗行．檢驗行與b列相交的數(shù)值為目標(biāo)函數(shù)值的相反數(shù)，即非基變量取零時的基本可行解．2．判定最優(yōu)解（1）若所有檢驗數(shù)均小于或等于零，則已求得的基本可行解就是最優(yōu)解；（2）若檢驗數(shù)中有正數(shù)，正數(shù)所對應(yīng)的列中均為非正數(shù)則問題無最優(yōu)解；（3）若檢驗數(shù)中有正數(shù)，且這些正數(shù)所在的列中的其他元素有正數(shù)則需要繼續(xù)改進來尋找更優(yōu)的解．在本例題中,因此不是最優(yōu)解．3．改進基本可行解（1）選主元當(dāng)表中有正檢驗數(shù)時，為了使目標(biāo)函數(shù)值盡可能的提高，一般選擇檢驗數(shù)大的所在列對應(yīng)的非基變量為進基變量，用該列上各正數(shù)去除同一行中b列上的元素，比值最小者所對應(yīng)的除數(shù)即為主元，用（）標(biāo)出．主元所對應(yīng)的變量即為出基變量．在本例題中，最大檢驗數(shù)，最小比值為所以為主元，進基，為出基變量．(2)換基迭代方法是：對單純形表施行初等行變換使主元變?yōu)?，主元所在的列上的其余元素全都化為零．得單純形表6．5

101-10?10?0(4)000144161/230-3/20-12由表６．5可知，基變量為，非基變量為基本可行解為檢驗數(shù)為，

所以不是最優(yōu)解，選進基，

由最小比值法選出基，

可得表6．6

001-1-1/4010?-1/810001/4024000-3/2-1/8

由于檢驗數(shù)均小于等于０，因此為最優(yōu)解．此時，最優(yōu)解為此時目標(biāo)函數(shù)的最優(yōu)值為例5．10

用單純形法解線性規(guī)劃問題解

為基變量，為非基變量．

列單純形表，在做題時將單純形表合并在一起，見下表6．7．

2-１１0023010

-1(1)0016184-330000

10１015001-1-1100111640000-3-12由表可知，最優(yōu)解為最優(yōu)解

例5．11用單純形法解線性規(guī)劃問題解引入松弛變量把原問題化成標(biāo)準(zhǔn)型則為基變量，為非基變量，可得單純形表

1-110-3（1）01