M1-1線性規(guī)劃問題的數(shù)學(xué)模型

第1章線性規(guī)劃模型及應(yīng)用1-1線性規(guī)劃問題的數(shù)學(xué)模型1-2

單純形方法1-3對(duì)偶線性規(guī)劃問題1-4運(yùn)輸問題1-5整數(shù)規(guī)劃Linearprogrammingmodelandapplication1-1線性規(guī)劃問題的數(shù)學(xué)模型及其解的性質(zhì)一、線性規(guī)劃問題的數(shù)學(xué)模型二、線性規(guī)劃問題的有關(guān)性質(zhì)三、計(jì)算機(jī)軟件

LINDO簡(jiǎn)介1.1合理下料問題1.0問題建模舉例1.2資源合理利用問題（資源的最優(yōu)配置）1.3配料問題(食譜問題)1.4運(yùn)輸問題1.5分派問題2.1兩個(gè)變量線性規(guī)劃問題的圖解法步驟2.2線性規(guī)劃解的匯總3.1軟件簡(jiǎn)介3.2舉例說明四、小結(jié)五、作業(yè)某工廠生產(chǎn)一種型號(hào)的機(jī)床，每臺(tái)機(jī)床上需要2.9米、2.1米和1.5米長(zhǎng)的三種軸各一根，這些軸需要用同一種圓鋼制作,圓鋼的長(zhǎng)度為7.4米。如果要生產(chǎn)100臺(tái)機(jī)床，應(yīng)如何下料，才能使得用料最省？

一、線性規(guī)劃問題的數(shù)學(xué)模型分析引例對(duì)于每一根長(zhǎng)為7.4米的圓鋼，截成2.9米、2.1米和1.5米長(zhǎng)的毛坯，可以有若干種下料方式，把它截成我們需要的長(zhǎng)度，有以下8種下料方式(表1-1)：表1-1

下料方式及每種類型的數(shù)目

下料方式長(zhǎng)度B1B2B3B4B5B6B7B8需要量2.9米211100001002.1米021032101001.5米10130234100余料0.10.30.901.10.20.81.41.0、問題建模舉例一、線性規(guī)劃問題的數(shù)學(xué)模型下料方式是從大到小、從長(zhǎng)到短的順序考慮的。⑴若只考慮用B3方式下料，需用料100根，沒優(yōu)化。⑵若采用木工師傅的下料方法：先下最長(zhǎng)的、再下次長(zhǎng)的、最后下短的(見表1-2),共需原料96根。下料方式下料根數(shù)2.9米根數(shù)2.1米根數(shù)1.5米根數(shù)B150100050B5330990B8120048B61022合計(jì)96100101100表1-2木工師傅的下料情況動(dòng)一下腦筋，就可以發(fā)現(xiàn)用此方式下料節(jié)約用料4根，降低成本，但這仍然不是最好的下料方法。一、線性規(guī)劃問題的數(shù)學(xué)模型⑶若要我們安排下料,暫不排除8種下料方式中的任何一種,通過建立數(shù)學(xué)模型進(jìn)行求解,尋找最好的下料方案。2.9米、2.1米和1.5米圓鋼的數(shù)量均不低于100根，即：因此，可以建立以下線性規(guī)劃數(shù)學(xué)模型:一、線性規(guī)劃問題的數(shù)學(xué)模型通過建立數(shù)學(xué)模型求解，得到的結(jié)果是最優(yōu)的。這個(gè)模型就是線性規(guī)劃模型。因此，可以建立以下線性規(guī)劃數(shù)學(xué)模型:用LINGO軟件求解，程序如下：Min=x1+x2+x3+x4+x5+x6+x7+x8;2*x1+x2+x3+x4>=100;2*x2+x3+3*x5+2*x6+x7>=100;x1+x3+3*x4+2*x6+3*x7+4*x8>=100;

Globaloptimalsolutionfoundatiteration:3Objectivevalue:90.00000VariableValueReducedCost

X140.000000.000000X220.000000.000000X30.0000000.1000000X40.0000000.000000X50.0000000.1000000X630.000000.000000X70.0000000.1000000X80.0000000.2000000RowSlackorSurplusDualPrice190.00000-1.00000020.000000-0.400000030.000000-0.300000040.000000-0.2000000一、線性規(guī)劃問題的數(shù)學(xué)模型即對(duì)模型求解得到結(jié)果如下：運(yùn)行結(jié)果如右所示:這就是最優(yōu)的下料方案。下料問題是在經(jīng)濟(jì)和管理中經(jīng)常遇到的問題，引例是條材下料問題、此外還有板材下料問題（如五金廠生產(chǎn)保險(xiǎn)柜的下料、服裝廠下料等）或者更復(fù)雜的下料問題。請(qǐng)考慮一下，下料方式能不能用計(jì)算機(jī)來設(shè)計(jì)更合理？本問題能不能將目標(biāo)函數(shù)確定為余料最少，為什么？這都是值得讀者思考的問題。在生產(chǎn)管理和經(jīng)營(yíng)活動(dòng)中，經(jīng)?？紤]這樣一類問題：如何合理地利用有限的人力、物力和財(cái)力等資源，以便得到最好的經(jīng)濟(jì)效果——成本最小或收益最大。下面分五個(gè)方面介紹典型的建立線性規(guī)劃模型的方法。一、線性規(guī)劃問題的數(shù)學(xué)模型說明一、線性規(guī)劃問題的數(shù)學(xué)模型例1.

某工廠生產(chǎn)一型號(hào)機(jī)床，每臺(tái)機(jī)床上需要2.9米、2.1米和1.5米長(zhǎng)的三種軸分別為1、2、1根，這些軸需要用同一種圓鋼制作,圓鋼的長(zhǎng)度為7.4米。如果要生產(chǎn)100臺(tái)機(jī)床，應(yīng)如何下料，才能使得用料最?。?/p>

解關(guān)于下料方式的分析如引例，下料方式見表1-1，可建模如下：用Lindo對(duì)模型求解,得1.1合理下料問題一、線性規(guī)劃問題的數(shù)學(xué)模型★一般下料問題:設(shè)用某種材料(條材或板材)下零件A1,A2,…,Am的毛坯，據(jù)過去的經(jīng)驗(yàn)，在一件原料上有B1,B2,…,Bn共n種不同的下料方式，每種合理的下料方式可得各種毛坯個(gè)數(shù)及每種零件的需要量如表1-3。問:怎樣安排下料方式,使得既滿足需要,又使得用料最省？表1-3

一般下料問題的基本數(shù)據(jù)

下料方式零件規(guī)格

B1B2

…Bn零件需要量A1A2…Amc11

c12

…

c1nc21

c22

…

c2n…………cm1

cm2

…

cmna1a2…am一、線性規(guī)劃問題的數(shù)學(xué)模型解則建立線性規(guī)劃問題數(shù)學(xué)模型：或者通過上述分析，建立線性規(guī)劃問題數(shù)學(xué)模型主要考慮以下幾個(gè)方面：一、線性規(guī)劃問題的數(shù)學(xué)模型從我們所建立的數(shù)學(xué)模型來看，目標(biāo)函數(shù)是決策變量的線性函數(shù)、約束條件是決策變量的線性等式或線性不等式,故我們稱此為線性規(guī)劃(LinearProgramming,簡(jiǎn)記為L(zhǎng)P)模型。③目標(biāo)函數(shù):明確解決問題的目的，并用決策變量的線性函數(shù)(稱為目標(biāo)函數(shù))表示，按問題的要求，求其最大值或最小值。②約束條件:明確問題所有限制條件(約束條件)且用決策變量的一些表達(dá)式(線性等式或線性不等式)來表示；①?zèng)Q策變量:明確問題中有待確定的未知變量(稱為決策變量)，并用數(shù)學(xué)符號(hào)來表示；建立線性規(guī)劃問題數(shù)學(xué)模型的三個(gè)基本要素:一、線性規(guī)劃問題的數(shù)學(xué)模型1.2資源合理利用(資源的最優(yōu)配置)問題例2.某工廠要安排一種產(chǎn)品的生產(chǎn),該產(chǎn)品有Ⅰ、Ⅱ、Ⅲ三種型號(hào)，生產(chǎn)這種產(chǎn)品均需要兩種主要資源：原材料和勞動(dòng)力。每件產(chǎn)品所需資源數(shù)、現(xiàn)有資源數(shù)量以及每件產(chǎn)品出售價(jià)格如表1-4。假定該產(chǎn)品生產(chǎn)出來即可銷售出去，試確定這三種產(chǎn)品的日產(chǎn)量使總產(chǎn)值最大。表1-4資源利用問題的數(shù)據(jù)產(chǎn)品資源ⅠⅡⅢ可利用資源原材料(公斤)436120公斤勞動(dòng)力(小時(shí))245100小時(shí)價(jià)格（元）453一、線性規(guī)劃問題的數(shù)學(xué)模型解：考慮三個(gè)要素①?zèng)Q策變量;②約束條件;③目標(biāo)函數(shù).設(shè)該廠計(jì)劃日產(chǎn)產(chǎn)品Ⅰ,Ⅱ,Ⅲ的數(shù)量分別為x1,x2,

x3件,則可建立線性規(guī)劃數(shù)學(xué)模型:用LINDO軟件求解，程序如下：max4x1+5x2+3x3st4x1+3x2+6x3<=1202x1+4x2+5x3<=100end對(duì)模型求解得到結(jié)果即得到最優(yōu)解：程序的運(yùn)行過程從略一、線性規(guī)劃問題的數(shù)學(xué)模型★一般地,用m種原料A1,A2,…,Am可以生產(chǎn)n種產(chǎn)品B1,B2,…,Bn.現(xiàn)有原料數(shù)ai

(可利用資源數(shù)量)、每單位產(chǎn)品所需原料數(shù)cij(消耗系數(shù))及每單位產(chǎn)品可得利潤(rùn)bj(i=1,2,…,m;j=1,2,…,n)如表1-5。問：應(yīng)如何組織生產(chǎn)才能使總利潤(rùn)最大？表1-5

一般資源利用問題的數(shù)據(jù)產(chǎn)品資源

B1B2

…Bn現(xiàn)有原料數(shù)A1A2…Amc11

c12

…

c1nc21

c22

…

c2n…………cm1

cm2

…

cmna1a2…am單位產(chǎn)品利潤(rùn)

b1b2…bn一、線性規(guī)劃問題的數(shù)學(xué)模型解:

設(shè)xj表示生產(chǎn)產(chǎn)品Bj的數(shù)量(j=1,2,…,n)，則可建立線性規(guī)劃數(shù)學(xué)模型：這種類型的資源利用(或者稱為資源配置)問題是最常見的，而且在經(jīng)濟(jì)分析中是最重要的。只要求出最優(yōu)解，最優(yōu)計(jì)劃即可作出，并且可以進(jìn)一步作經(jīng)濟(jì)分析和優(yōu)化分析。表1-6配料（食譜）問題的數(shù)據(jù)一、線性規(guī)劃問題的數(shù)學(xué)模型1.3配料問題(食譜問題)例3

某公司飼養(yǎng)實(shí)驗(yàn)用的動(dòng)物以供出售，已知這些動(dòng)物的生長(zhǎng)對(duì)飼料中3種營(yíng)養(yǎng)成分(蛋白質(zhì)、礦物質(zhì)和維生素)特別敏感，每個(gè)動(dòng)物每周至少需要蛋白質(zhì)70g，礦物質(zhì)3g，維生素10mg，該公司能買到5種不同的飼料，每種飼料1kg所含各種營(yíng)養(yǎng)成分和成本如下表所示，求既能滿足動(dòng)物生長(zhǎng)需要，又使總成本最低的飼料配方。營(yíng)養(yǎng)飼料A1

A2

A3

A4

A5

營(yíng)養(yǎng)最低要求蛋白質(zhì)(g)0.3210.61.870礦物質(zhì)(g)0.10.050.020.20.053維生素(mg)0.050.10.020.20.0810成本（元/kg）0.20.70.40.30.5min0.2x1+0.7x2+0.4x3+0.3x4+0.5x5st0.3x1+2x2+x3+0.6x4+1.8x5>=700.1x1+0.05x2+0.02x3+0.2x4+0.05x5>=30.05x1+0.1x2+0.02x3+0.2x4+0.08x5>=10end一、線性規(guī)劃問題的數(shù)學(xué)模型解：設(shè)需要5種飼料A1,A2,A3,A4,A5的數(shù)量分別為x1,x2,x3,x4,x5kg,則可建立線性規(guī)劃數(shù)學(xué)模型:用LINDO軟件求解，程序如下：求解,得：說明:該模型應(yīng)該還要增加約束(同學(xué)們思考一下,為什么？Why?)一、線性規(guī)劃問題的數(shù)學(xué)模型★一般地,用n種原料B1,B2,…,Bn

制成具有m種成分A1,A2,…,Am的產(chǎn)品,其所含各種成分分別不少于a1,a2,…,am,各種原料的單價(jià)bj以及各種原料所含成分的數(shù)量cij(i=1,2,…,m;j=1,2,…,n)如表1-7。問：應(yīng)如何配料才能使總成本最??？表1-7一般配料（食譜）問題的數(shù)據(jù)原料成分

B1B2

…Bn現(xiàn)有原料數(shù)A1A2…Am

c11

c12

…

c1nc21

c22

…

c2n…………cm1

cm2

…

cmna1a2…am單價(jià)

b1b2…bn一、線性規(guī)劃問題的數(shù)學(xué)模型解:

設(shè)需要原料Bj的數(shù)量為xj單位(j=1,2,…,n)，則可建立線性規(guī)劃數(shù)學(xué)模型：應(yīng)該還要增加一個(gè)約束條件：（進(jìn)行總量控制）表1-8運(yùn)輸問題的數(shù)據(jù)一、線性規(guī)劃問題的數(shù)學(xué)模型1.4運(yùn)輸問題例4.設(shè)有兩個(gè)磚廠A1、A2,其產(chǎn)量分別為23萬(wàn)塊與27萬(wàn)塊，它們生產(chǎn)的磚供應(yīng)B1、B2、B3三個(gè)工地，其需要量分別為17萬(wàn)塊、18萬(wàn)塊、15萬(wàn)塊。而自各產(chǎn)地Ai到各工地Bj

(i=1,2;j=1,2,3)運(yùn)價(jià)如表1-8(單位:元/萬(wàn)塊)。問應(yīng)如何調(diào)運(yùn)，才使總運(yùn)費(fèi)最??？平衡表(萬(wàn)塊)運(yùn)價(jià)表(元/萬(wàn)塊)產(chǎn)地銷地B1B2B3供應(yīng)量B1B2B3A123506070A2276011060需求量18171550一、線性規(guī)劃問題的數(shù)學(xué)模型解:

設(shè)磚廠Ai供應(yīng)建筑工地Bj磚塊的數(shù)量為xij

(i=1,2;j=1,2,3)

則可建立線性規(guī)劃數(shù)學(xué)模型：min50x11+60x12+70x13+60x21+110x22+60x23stx11+x12+x13=23x21+x22+x23=27x11+x21=18x12+x22=17x13+x23=15end用LINDO軟件求解，程序如下：通過求解,得：一、線性規(guī)劃問題的數(shù)學(xué)模型★一般地,某種物資有m個(gè)產(chǎn)地:A1,A2,…,Am

聯(lián)合供應(yīng)n個(gè)銷地

B1,B2,…,Bn

,各產(chǎn)地產(chǎn)量ai各銷地銷量bj以及各產(chǎn)地到各銷地的單位運(yùn)價(jià)cij(i=1,2,…,m;j=1,2,…,n)如表1-9。問：應(yīng)如何組織運(yùn)輸才能使得總運(yùn)費(fèi)最?。勘?-9一般運(yùn)輸問題的數(shù)據(jù)平衡表運(yùn)價(jià)表產(chǎn)地銷地B1B2…Bn產(chǎn)量B1B2…BnA1a1

c11c12…c1nA2a2c21c22…c2n………………Amam

cm1cm2…cmn銷量b1b2…bn一、線性規(guī)劃問題的數(shù)學(xué)模型解:

設(shè)xij表示產(chǎn)地Ai供應(yīng)銷地Bj的數(shù)量

(i=1,2,…,m;j=1,2,…,n)。一、線性規(guī)劃問題的數(shù)學(xué)模型★類似的模型還有農(nóng)作物布局問題：一、線性規(guī)劃問題的數(shù)學(xué)模型某農(nóng)場(chǎng)要在B1,B2,…,Bn這n塊土地上種植m種農(nóng)作物A1,A2,…,Am,各種土地面積bj、各種作物的計(jì)劃播種面積ai以及各種作物在各塊土地上的單產(chǎn)cij

(i=1,2,…,m;j=1,2,…,n)如表1-10。問:應(yīng)如何安排種植計(jì)劃,才使總產(chǎn)量最大？表1-10農(nóng)作物布局問題的數(shù)據(jù)平衡表產(chǎn)量表農(nóng)作物土地B1B2…Bn播種面積B1B2…BnA1a1

c11c12…c1nA2a2c21c22…c2n………………Amam

cm1cm2…cmn土地面積b1b2…bn一、線性規(guī)劃問題的數(shù)學(xué)模型解:

設(shè)xij表示土地Bj種植農(nóng)作物Ai的面積(i=1,2,…,m;j=1,2,…,n)。則數(shù)學(xué)模型為這個(gè)問題的數(shù)學(xué)模型與運(yùn)輸問題的數(shù)學(xué)模型相同，統(tǒng)稱為（經(jīng)典）運(yùn)輸問題，還有其它的問題也可以建立類似結(jié)構(gòu)的數(shù)學(xué)模型。這類數(shù)學(xué)模型稱為康——希問題。關(guān)于運(yùn)輸問題有專門的求解方法——運(yùn)輸問題的表上作業(yè)法將本章在第四節(jié)中專門介紹。康托洛維奇——希奇柯克一、線性規(guī)劃問題的數(shù)學(xué)模型1.5分派問題⑴最小指派問題的數(shù)學(xué)模型表1-11一般指派問題的效率數(shù)據(jù)例5.設(shè)有n件工作B1,B2,…,Bn分派給n個(gè)人A1,A2,…,An去做,每人只能做一件工作,且每一件工作只能分派給一個(gè)人去做。設(shè)Ai完成Bj的工時(shí)為cij(i,j=1,2,…,n),如表1-11,問:應(yīng)如何分派,才能使完成全部工作所需的總工時(shí)最少?工作人員

B1B2

…BnA1A2…An

c11

c12

…

c1nc21

c22

…

c2n…………cn1

cn2

…

cnn一、線性規(guī)劃問題的數(shù)學(xué)模型解:效率矩陣即由工作時(shí)間組成的矩陣設(shè)第i個(gè)人Ai完成工作Bj的情況為則有這是求最小指派問題的數(shù)學(xué)模型，還有求最大指派問題的數(shù)學(xué)模型。⑵最大指派問題的數(shù)學(xué)模型一、線性規(guī)劃問題的數(shù)學(xué)模型表1-11(改)一般指派問題的利潤(rùn)數(shù)據(jù)例6.設(shè)有n件工作B1,B2,…,Bn分派給n個(gè)人A1,A2,…,An去做,每人只能做一件工作,且每一件工作只能分派給一個(gè)人去做。設(shè)Ai完成Bj可得利潤(rùn)(或收益)為cij(i,j=1,2,…,n),如表1-11(改),問:應(yīng)如何分派,才能使完成全部工作后所獲利潤(rùn)最大?工作人員

B1B2

…BnA1A2…An

c11

c12

…

c1nc21

c22

…

c2n…………cn1

cn2

…

cnn一、線性規(guī)劃問題的數(shù)學(xué)模型解:利潤(rùn)矩陣即由利潤(rùn)組成的矩陣設(shè)第i個(gè)人Ai完成工作Bj的情況為則有注:關(guān)于指派問題,屬于整數(shù)線性規(guī)劃問題中的0-1規(guī)劃問題，求解指派問題有專門的方法—匈牙利方法,將在本章第五節(jié)介紹.這是求最大指派問題的數(shù)學(xué)模型。滿足所有約束條件的一、線性規(guī)劃問題的數(shù)學(xué)模型★一般地，線性規(guī)劃問題的數(shù)學(xué)模型具有形式：◎線性規(guī)劃問題的可行解:

◎線性規(guī)劃問題的最優(yōu)解:

使目標(biāo)函數(shù)取到最小值（或最大值，與模型的目標(biāo)函數(shù)要求一致）的可行解。線性規(guī)劃問題的數(shù)學(xué)模型是描述實(shí)際問題的抽象數(shù)學(xué)形式，它反映了客觀事物數(shù)量間的本質(zhì)規(guī)律。一、線性規(guī)劃問題的數(shù)學(xué)模型建立線性規(guī)劃數(shù)學(xué)模型，要具體問題具體分析，沒有統(tǒng)一的方法。主要是抓住問題的本質(zhì)，建立既簡(jiǎn)單又比較真實(shí)反映經(jīng)濟(jì)規(guī)律的模型。一般的線性規(guī)劃問題通過計(jì)算機(jī)軟件(LINDO或LINGO等)可以求出最優(yōu)解。下面先介紹一下線性規(guī)劃問題解的性質(zhì)及解的有關(guān)情況，以達(dá)到對(duì)線性規(guī)劃的解有一個(gè)直觀的認(rèn)識(shí)。二、線性規(guī)劃問題的解有關(guān)性質(zhì)2.1兩個(gè)變量線性規(guī)劃問題的圖解法步驟表1-12生產(chǎn)計(jì)劃問題的數(shù)據(jù)例7.某工廠在計(jì)劃期內(nèi)要安排生產(chǎn)A、B兩種產(chǎn)品，已知生產(chǎn)單位產(chǎn)品所需設(shè)備臺(tái)時(shí)及對(duì)甲、乙兩種原材料的消耗，有關(guān)數(shù)據(jù)如表1-12。問：應(yīng)如何安排計(jì)劃，使工廠獲利最大？產(chǎn)品資源

AB可利用資源設(shè)備甲乙

1240048臺(tái)時(shí)16kg12kg單位利潤(rùn)

2元3元二、線性規(guī)劃問題的解有關(guān)性質(zhì)解:設(shè)計(jì)劃生產(chǎn)A、B兩種產(chǎn)品的數(shù)量分別為x1、x2，則建立LP模型為：因只含2個(gè)變量，可用圖解法求解。圖解法求解兩變量線性規(guī)劃的步驟：⑶根據(jù)目標(biāo)函數(shù)求最大、最小值，求出問題的最優(yōu)解。⑴作出滿足5個(gè)不等式的公共部分OABCD(可行解區(qū)域);⑵作出目標(biāo)函數(shù)的等值線,并標(biāo)出等值線值增加的方向;本題在B點(diǎn)取到惟一最優(yōu)解(如圖1-1)x1+2x2=82x1+3x2=6圖1-1解得：B：二、線性規(guī)劃問題的解有關(guān)性質(zhì)例8

如果該問題是產(chǎn)品B的單位利潤(rùn)為4元，則該線性規(guī)劃問題的數(shù)學(xué)模型是：x1+2x2=82x1+4x2=8圖1-2可行解區(qū)域仍然是OABCD,由于目標(biāo)函數(shù)的等值線與可行解區(qū)域的邊界x1+2x2=8平行,該問題在線段BC上都是最優(yōu)解,所以有無窮多最優(yōu)解(如圖1-2)。例9、用圖解法求解線性規(guī)劃問題：解:

該問題的可行解區(qū)域?yàn)闊o界區(qū)域EABCD，當(dāng)目標(biāo)函數(shù)的等值線向右上方移動(dòng)時(shí)，目標(biāo)函數(shù)可無限增大(如圖1-3)。因此該問題無有界的最優(yōu)解。圖1-3注：

maxS=+∞

(只可能出現(xiàn)在可行解區(qū)域無界的情況)。二、線性規(guī)劃問題的解有關(guān)性質(zhì)例10、用圖解法求解線性規(guī)劃問題：解:該問題的可行解區(qū)域?yàn)闊o界區(qū)域EABCD，當(dāng)目標(biāo)函數(shù)的等值線向右上方移動(dòng)時(shí)，目標(biāo)函數(shù)可無限增大。但本題是求目標(biāo)函數(shù)的最小值，目標(biāo)函數(shù)的等值線向糟下方移動(dòng)時(shí)，（如圖1-3）在B點(diǎn)有惟一的最優(yōu)解：圖1-3二、線性規(guī)劃問題的解有關(guān)性質(zhì)二、線性規(guī)劃問題的解有關(guān)性質(zhì)例11、用圖解法求解線性規(guī)劃問題：圖1-4解:如圖1-4所示，滿足四個(gè)約束條件的公共部分不存在，故本題無可行解，當(dāng)然亦無最優(yōu)解。二、線性規(guī)劃問題的解有關(guān)性質(zhì)2.2線性規(guī)劃解的歸納三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介3.1軟件簡(jiǎn)介L(zhǎng)INDO和LINGO是美國(guó)LINDO系統(tǒng)公司開發(fā)的一套專門用于求解最優(yōu)化問題的軟件包。LINDO用于求解線性規(guī)劃和二次規(guī)劃，LINGO除了具有LINDO的全部功能外，還可以用于求解非線性規(guī)劃，也可以用于一些線性和非線性方程組的求解以及代數(shù)方程求根等。LINDO和LINGO軟件的最大特色在于可以允許優(yōu)化模型中的決策變量是整數(shù)（即整數(shù)規(guī)劃），而且執(zhí)行速度很快。LINGO實(shí)際上還是最優(yōu)化問題的一種建模語(yǔ)言，包括許多常用的函數(shù)可供使用者建立優(yōu)化模型時(shí)調(diào)用，并提供與其它數(shù)據(jù)文件（如文本文件、EXCEL電子表格文件、數(shù)據(jù)庫(kù)文件等）的接口，易于方便地輸入、求解和分析大規(guī)模最優(yōu)化問題。由于這些特點(diǎn)，LINDO和LINGO軟件在教學(xué)、科研和工業(yè)、商業(yè)、服務(wù)等領(lǐng)域得到廣泛應(yīng)用。⑴LINDO(LinearInteractiveand

DiscreteOptimizer):

一般用于解決線性規(guī)劃(LP—LinearProgramming)和整數(shù)規(guī)劃(IP—IntegerProgramming)問題。其LINDO6.0版至多可求解多達(dá)8000個(gè)變量和4000個(gè)約束的規(guī)劃問題.⑵LINGO:則用于求解非線性規(guī)劃(NLP—NON—LINEARPROGRAMMING)和二次規(guī)則(QP—QUARATICPROGRAMING)，不同版本的LINGO對(duì)求解規(guī)模有不同的限制。雖然LINDO和LINGO不能直接求解目標(biāo)規(guī)劃問題,但用序貫式算法可分解成一個(gè)個(gè)LINDO和LINGO能解決的規(guī)劃問題。要學(xué)好用這兩個(gè)軟件最好的辦法就是學(xué)習(xí)他們自帶的HELP文件。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介3.2舉例說明下面舉例說明這兩個(gè)軟件的最基本用法.以后在講述其他內(nèi)容時(shí)結(jié)合具體例子逐步介紹求解的步驟以及深入分析.例12

一種汽油的特性可用兩個(gè)指標(biāo)描述：其點(diǎn)火性用“辛烷數(shù)”描述，其揮發(fā)性用“蒸汽壓力”描述。某煉油廠有四種標(biāo)準(zhǔn)汽油，其標(biāo)號(hào)分別為1、2、3、4，其特性及庫(kù)存量列于表1-13中，將上述標(biāo)準(zhǔn)汽油適量混合，可得兩種飛機(jī)汽油，其標(biāo)號(hào)為1和2，這兩種飛機(jī)汽油的性能指標(biāo)及產(chǎn)量需求列于表1-14中。問應(yīng)如何根據(jù)庫(kù)存情況適量混合各種標(biāo)準(zhǔn)汽油，使既滿足飛機(jī)汽油的性能指標(biāo)，而產(chǎn)量又最高。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介表1-13各種標(biāo)號(hào)的標(biāo)準(zhǔn)汽油的特性與存量標(biāo)準(zhǔn)汽油辛烷數(shù)蒸汽壓力(g/cm2)庫(kù)存量1107.57.11×10-2380000293.011.38×10-2262200387.05.69×10-24081004108.028.45×10-2130100表1-14兩種飛機(jī)汽油的性能指標(biāo)及產(chǎn)量需求飛機(jī)汽油辛烷數(shù)蒸汽壓力(g/cm2)產(chǎn)量需求(L)1≥107.5≤9.96×10-2越多越好2≥93.0≤9.96×10-2≥250000三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介解:設(shè)標(biāo)準(zhǔn)汽油1、2、3、4用于混合飛機(jī)汽油1的數(shù)量分別為x1、x2、x3、x4，標(biāo)準(zhǔn)汽油1、2、3、4用于混合飛機(jī)汽油2的數(shù)量分別為x5、x6、x7、x8，則可建立線性規(guī)劃問題的數(shù)學(xué)模型：整理以后就是線性規(guī)劃模型。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介max(不區(qū)分大小寫，后面加一空格)x1+x2+x3+x4ST(大寫或?qū)憇ubjectto)x5+x6+x7+x8>=250000x1+x5<=380000x2+x6<=265200x3+x7<=408100x4+x8<=1301002.85x1-1.42x2+4.27x3-18.49x4>=02.85x5-1.42x6+4.27x7-18.49x8>=016.5x1+2.0x2-4.0x3+17x4>=07.5x5-7.0x6-13.0x7+8.0x8>=0end下面我們先用LINDO來解這一優(yōu)化問題。輸入語(yǔ)句：然后再按運(yùn)算符鍵即可得結(jié)果。LINDO是規(guī)定變量非負(fù)的，我們可發(fā)現(xiàn)輸入方式與我們的數(shù)學(xué)模型的書寫形式基本一致，運(yùn)算后，計(jì)算機(jī)會(huì)問您是否需要靈敏度分析，我們選擇“是”，結(jié)果如下：LPOPTIMUMFOUNDATSTEP6OBJECTIVEFUNCTIONVALUE1)933400.0VARIABLEVALUEREDUCEDCOST

X1161351.7343750.000000

X2265200.0000000.000000

X3408100.0000000.000000

X498748.2656250.000000

X5218648.2656250.000000

X60.0000000.000000

X70.0000000.000000

X831351.7343750.000000 三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介ROWSLACKORSURPLUSDUALPRICES

2)0.000000-1.0000003)0.0000001.0000004)0.0000001.0000005)0.0000001.0000006)0.0000001.0000007)0.0000000.0000008)43454.0000000.0000009)3239024.2500000.00000010)1890675.8750000.000000NO.ITERATIONS=6三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLE

COEFINCREASEDECREASE

x11.0000000.0000001.154137

x21.000000INFINITY0.000000

x31.000000INFINITY0.000000

x41.0000000.0000000.000000

x50.0000001.1541370.000000

x60.0000000.000000INFINITY

x70.0000000.000000INFINITY

x80.0000000.000000

0.000000

三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE2250000.000000186222.062500234752.9843753380000.000000234752.98437515247.0175784265200.00000030601.410156265200.0000005408100.000000156685.25000010176.5810556130100.000000235020703170.00000043454.000000669046.00000080.00000043454.000000INFINITY90.0000003239024.250000INFINITY100.0000001890675.875000INFINITY三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介下面給出其結(jié)果的一般解釋：⑴“LPOPTIMUMFOUNDATSTEP6”表示LINDO

在(用單純形法)6次迭代或旋轉(zhuǎn)后得到最優(yōu)解。⑵“OBJECTIVEFUNCTIONVALUE1)933400.0”

表示最優(yōu)目標(biāo)值為933400。⑶“VALUE”給出最優(yōu)解中各變量的值。⑷“SLACKORSURPLUS”

給出松弛變量的值.上例中SLK2=第二行松弛變量＝0(模型第一行表示目標(biāo)函數(shù)，所以第二行對(duì)應(yīng)第一個(gè)約束)。⑸“REDUCECOST”列出最優(yōu)單純形表中判別數(shù)所在行的變量的系數(shù),表示當(dāng)變量有微小變動(dòng)時(shí),目標(biāo)函數(shù)的變化率,其中基變量的reducecost值應(yīng)為0,對(duì)于非基變量xj相應(yīng)的reducecost值表示xj增加一個(gè)單位(此時(shí)假定其他非基變量保持不變)時(shí)目標(biāo)函數(shù)減小的量(max型問題)。上例x1對(duì)應(yīng)reducecost值為0,表x1變化,目標(biāo)函數(shù)值不變。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介⑹“DUALPRICE”（對(duì)偶價(jià)格）列出最優(yōu)單純形表中判別數(shù)所在行的松弛變量的系數(shù)，表示當(dāng)對(duì)應(yīng)約束有微小變動(dòng)時(shí)，目標(biāo)函數(shù)的變化率，輸出結(jié)果中對(duì)應(yīng)每一個(gè)約束有一個(gè)對(duì)偶價(jià)格。若其數(shù)值為x表示對(duì)應(yīng)約束中不等式右端項(xiàng)若增加一個(gè)單位，目標(biāo)函數(shù)將增加x個(gè)單位（max型問題）。上例中：第二行對(duì)應(yīng)的對(duì)偶價(jià)格值為-1,表示當(dāng)約束“x5+x6+x7+x8≥250000”變?yōu)椤皒5+x6+x7+x8≥250001”時(shí)，目標(biāo)函數(shù)值=933400-1=933399.當(dāng)REDUCECOST或DUALPRICE的值為0.表示當(dāng)微小擾動(dòng)不影響目標(biāo)函數(shù).有時(shí),通過分析DUALPRICE,也可對(duì)產(chǎn)生不可行問題的原因有所了解。⑺靈敏度分析：若作敏感性分析，則系統(tǒng)報(bào)告當(dāng)目標(biāo)函數(shù)的費(fèi)用系數(shù)和約束右端項(xiàng)在什么范圍變化(此時(shí)假定其他系數(shù)保持不變)時(shí)，最優(yōu)基保持不變。報(bào)告中INFINITY表示正無窮，如例12，目標(biāo)函數(shù)中x1

的變量系數(shù)為1，當(dāng)它在[1-1.154137,1-0]=[-0.154137,1]變化時(shí),最優(yōu)基保持不變。第一個(gè)約束右端項(xiàng)為250000,當(dāng)它在[250000-234752.98，250000+186222.06]=[15247.02,436222.062]范圍變化時(shí)，最優(yōu)基保持不變。當(dāng)您要判斷表達(dá)式輸入是否有錯(cuò)誤時(shí)，也可以使用菜單“Reports”的“Picture”選項(xiàng)。若想獲得靈敏度分析,可用“Reports”的“Rang”選項(xiàng)。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介若需顯示單純形表,可執(zhí)行“Reports”的“Tablean”選項(xiàng)。⑸一般LINDO中不能接受括號(hào)“()”和逗號(hào)“,”，例：400(x1+x2)需寫成400x1+400x2;10,000需寫成10000等；,

三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介用LINDO求解注意事項(xiàng)：⑹表達(dá)式應(yīng)當(dāng)已經(jīng)過簡(jiǎn)化,不能出現(xiàn)“2x1+3x2-4x1”而應(yīng)寫成-2x1+3x2；⑴目標(biāo)函數(shù)及各約束條件間要有“Subjectto(ST)”分開;⑵變量名不能超過８?jìng)€(gè)字符；⑶變量與其系數(shù)間可以有空格,但不能有任何運(yùn)算符號(hào)(如乘號(hào)“＊”等)；⑷要輸入≤或≥約束，相應(yīng)以<或>代替即可；⑺變量只能出現(xiàn)在等號(hào)(或不等號(hào))的左端，常數(shù)只能出現(xiàn)在右端，目標(biāo)函數(shù)中不能包含常數(shù)項(xiàng)。三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介L(zhǎng)INGO的主要功能特色為：⑴既能求解線性規(guī)劃問題，也有較強(qiáng)的求解非線性規(guī)劃問題的能力；⑵輸入模型簡(jiǎn)練直觀；⑶運(yùn)算速度快、計(jì)算能力強(qiáng)；⑷內(nèi)置建模語(yǔ)言，提供幾十個(gè)內(nèi)部函數(shù)，從而能以較少語(yǔ)句，較直觀的方式描述大規(guī)模的優(yōu)化模型；⑸將集合的概念引入編程語(yǔ)言，很容易將實(shí)際問題轉(zhuǎn)換為L(zhǎng)INGO模型；⑹能方便地與Excel、數(shù)據(jù)庫(kù)等其他軟件交換數(shù)據(jù)。max=x1+x2+x3+x4;x5+x6+x7+x8>=250000;x1+x5<=380000;x2+x6<=265200;x3+x7<=408100;x4+x8<=130100;2.85*x1-1.42*x2+4.27*x3-18.49*x4>=0;2.85*x5-1.42*x6+4.27*x7-18.49*x8>=0;16.5*x1+2.0*x2-4.0*x3+17*x4>=0;7.5*x5-7.0*x6-13.0*x7+8.0*x8>=0;如果用LINGO求解同一個(gè)問題，輸入為三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介Globaloptimalsolutionfoundatiteration:8Objectivevalue:933400.0VariableValueReducedCostX1264937.90.000000X2135702.10.000000X3408100.00.000000X4124660.00.000000X5115062.10.000000X6129497.90.000000X70.0000000.000000X85440.0110.000000 三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介輸出結(jié)果：RowSlackorSurplusDualPrice1933400.01.00000020.000000-1.00000030.0000001.00000040.0000001.00000050.0000001.00000060.0000001.00000070.0000000.000000843454.000.00000095129700.0.000000100.0000000.000000三、計(jì)算機(jī)軟件LINDO簡(jiǎn)介如果要看靈敏度分析結(jié)果,必須激活靈敏度計(jì)算功能才會(huì)在求解時(shí)給出靈敏度分析結(jié)果,默認(rèn)情況下這項(xiàng)功能是關(guān)閉的。想要激活它,必須運(yùn)行LINGO|Options…命令,選擇GengralSolver,在DualComputation列表框中,選擇PricesandRanges選項(xiàng)并確定。結(jié)果如下：Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX11.0000000.00.0X21.0000000.00.0X31.000000INFINITY0.0X41.00000015.131860.0X50.00.0

0.0X60.00.0

0.0X70.00.0INFINITYX80.00.01.162

RighthandSideRan