用LINGO軟件求解動(dòng)態(tài)規(guī)劃問(wèn)題ppt課件

1、用LINGO求解 ：n例例5.1.1 如圖如圖5.1.1，給定一個(gè)網(wǎng)絡(luò)，從點(diǎn)鋪設(shè)，給定一個(gè)網(wǎng)絡(luò)，從點(diǎn)鋪設(shè)一條煤氣管道到點(diǎn)，必需經(jīng)過(guò)五個(gè)中間站，第一條煤氣管道到點(diǎn)，必需經(jīng)過(guò)五個(gè)中間站，第一站可以在中選擇，其他類似。能用管道相連一站可以在中選擇，其他類似。能用管道相連的兩站之間的間隔曾經(jīng)給定；假設(shè)兩點(diǎn)之間沒(méi)的兩站之間的間隔曾經(jīng)給定；假設(shè)兩點(diǎn)之間沒(méi)有連線，那么表示這兩點(diǎn)之間不能鋪設(shè)管道。有連線，那么表示這兩點(diǎn)之間不能鋪設(shè)管道。要求選擇一條由到的管道鋪設(shè)道路，使總間隔要求選擇一條由到的管道鋪設(shè)道路，使總間隔最短。最短。n令令n表示由某點(diǎn)至終點(diǎn)表示由某點(diǎn)至終點(diǎn)A6之間的階段數(shù)。例如從之間的階段數(shù)。例如從

2、A0至至A6是是6個(gè)階段，從個(gè)階段，從A1至至A6是是5個(gè)階段。個(gè)階段。n令令s表示在任一階段所處的形狀，表示在任一階段所處的形狀， s稱為形狀變量。例稱為形狀變量。例如假設(shè)在第三階段的開(kāi)場(chǎng)點(diǎn)是如假設(shè)在第三階段的開(kāi)場(chǎng)點(diǎn)是A2那么稱所處的形狀為那么稱所處的形狀為A2 。0A1A1B2A2B2C2D3A3B3C4A4B4C5A5B6A5323687166835338422123335526643圖5.1.1n令令xn(s)為決策變量，它表示當(dāng)形狀處于為決策變量，它表示當(dāng)形狀處于s，還有，還有n個(gè)階個(gè)階段時(shí)所選擇的一個(gè)決策。在各個(gè)階段上選擇的決策組段時(shí)所選擇的一個(gè)決策。在各個(gè)階段上選擇的決策組成的總

3、體稱為一個(gè)戰(zhàn)略。成的總體稱為一個(gè)戰(zhàn)略。n令令fn(s)表示如今處在形狀表示如今處在形狀s(即在點(diǎn)即在點(diǎn)s上上)還有還有n個(gè)階段時(shí)，個(gè)階段時(shí)，由由s至終點(diǎn)至終點(diǎn)A6的最短間隔。的最短間隔。n令令d(s,xn)表示點(diǎn)表示點(diǎn)s到點(diǎn)到點(diǎn)xn的間隔。的間隔。n那么可構(gòu)造那么可構(gòu)造n階段的最優(yōu)值與階段的最優(yōu)值與n-1階段的最優(yōu)值之間的階段的最優(yōu)值之間的遞推關(guān)系如下：遞推關(guān)系如下： 1( )( )min( ,( )( ) ,2,3,6nnnnnxsfsd s x sfx sn),()(61Asdsfn設(shè)： ， ， ， ， ， ， ， ， ， ， ， ， ， ， ， 。10頂點(diǎn)A21A31B42A52B62C72D83A93B103C114A124B134C145A155B166A1.模型輸入模型輸入運(yùn)用運(yùn)用LINGO求解此動(dòng)態(tài)規(guī)劃問(wèn)題，求解此動(dòng)態(tài)規(guī)劃問(wèn)題，LINGO程程序如下序如下(參見(jiàn)圖參見(jiàn)圖5.4.1)：圖5.4.12.執(zhí)行 點(diǎn)擊LINGO菜單下的SOLVE鍵，或按CTRL+S鍵，即可求得問(wèn)題的解。此問(wèn)題的最優(yōu)值為：17。 當(dāng)運(yùn)用LINGO求解此問(wèn)題后，系統(tǒng)會(huì)彈出一個(gè)名