其次章習(xí)題運(yùn)籌學(xué)

本文格式為Word版，下載可任意編輯——其次章習(xí)題運(yùn)籌學(xué)其次章習(xí)題

12、對于下面的線性規(guī)劃問題，以B??A2,A3,A6?為基寫出相對應(yīng)的典式。

?minx1?2x2?x3??s.t.3x1?x2?2x3?x4?7???2x1?4x2?x5?12??4x?3x?8x?x?101236??xj?0,j?1?6?解：由題可以知：

?3?12100??TA???240010??C??1?21000?

???438001??取一個(gè)基B??A4A5??120??3?12?A6?，即：B??400?且N???240?

???????381????438??TTCB???210?CN??100?

在matlab中可以計(jì)算得到：

1??00??4?1?1T?1B??0?b?B?1b??35?39?

8?2?7??4?1???4???5TT?1TCBb??1CBBN?CN???4TT?1T由Z?CBb?CBBN?CNxN可得典式的目標(biāo)函數(shù)：

123???8???513Z??1?x1?x4?x5

428由xB?B?1NxN?b可得：

1?1?x?x?x5?3?2124?11?5x?x?x?x5?5?13428?47?25?x?4x?x5?x6??394?214?由此與題中線性規(guī)劃問題相對應(yīng)的典式為：

513?minZ??1?x?x?x514?428??s.t.?11?x1?x2?x5?3??24?511?x1?x3?x4?x5?5?428?257??x1?4x4?x5?x6??3924??xj?0,j?1,?,6?

14、用單純形法求解線面的線性規(guī)劃問題，并在平面上畫出迭代點(diǎn)走過的路線。

?min?s.t.?????????z??2x1?x22x1?5x2?60x1?x2?183x1?x2?44x2?10x1,x2?0?minz??2x1?x2?s.t.2x?5x?x?60123??x1?x2?x4?18??3x?x?x?44125??x2?x6?10?xj?0,j?1,?,6??解：由題先將題中線性規(guī)劃問題化為標(biāo)準(zhǔn)形：

?2?1由此可寫出A，即為：A???3??051111000010000100?0??0??1?則可以得出B??A3A4A5A6?是一個(gè)單位矩陣，且b??60184410?＞0，

T所以基B是可行基，x3,x4,x5,x6為基變量，x1,x2為非基變量?；鵅對應(yīng)的基本可

T行解為：x??0060184410?，其目標(biāo)函數(shù)值z0?0。方程組Ax?b已是

典式，得到一張單純形表如下：

xxx

210x251x110x3*10x010

123x4

x5

x6

RHS

3456001000001000001060184410由題可知，N??A1TA2?，cB??0000?cT?1?N???2T?1T檢驗(yàn)數(shù)可由?k?cBBN?cN可得：?1?2不是負(fù)數(shù)，則當(dāng)前解不是最優(yōu)解，A1列

中有三個(gè)元素大于零，?。?/p>

?bbb??601844?44min?1,2,3??min?,,???213?3?a11a21a31?故轉(zhuǎn)軸元為a31，x1為進(jìn)基變量，x5為出基變量。

???A目前的新基為B3

x3x1A4x2A1

A6?,進(jìn)行旋轉(zhuǎn)變換后得下表：

xxxx

3456RHS000130100000100?232300001?88313323??923103443x41?3131x0x56131010

9210?44?它對應(yīng)的基本可行解為:x??0010?,其目標(biāo)函數(shù)值為

33?3?z0??881。但?2?為正數(shù)，仍不是最優(yōu)解，此時(shí)以a22為轉(zhuǎn)軸元，x2為進(jìn)基變33T量，x4為出基變量，進(jìn)行旋轉(zhuǎn)變化得下表：

3x1

x2

x3

x4

12x5

12x6

RHS00010001000??00001?1816x013?2323?23?21212119652x4010x51?2?32836152x6

11915??835它對應(yīng)的基本可行解為：x???00?，目標(biāo)函數(shù)值為

62??62z0??181，此時(shí)檢驗(yàn)數(shù)向量?為負(fù)數(shù)，故為最優(yōu)解。6T

16、用單純形法求解以下線性規(guī)劃問題：

?min??s.t.??（1）、????z??2x1?x2?x33x1?x2?x3?60x1?x2?2x3?10x1?x2?x3?20xj?0,j?1,2,3

解：由題先將題中線性規(guī)劃問題化為標(biāo)準(zhǔn)形：

?min??s.t.??????

z??2x1?x2?x33x1?x2?x3?x4x1?x2?2x3x1?x2?x3?x5?60?10?x6?20

xj?0,j?1,2,3,4,5,6?311100??1?12023由此可以得到矩陣A??????11?1001??

則可以得出B??A4A5且b??601020?＞0，所以基BA6?是一個(gè)單位矩陣，

T是可行基，x4,x5,x6為基變量，x1,x2,x3為非基變量?；鵅對應(yīng)的基本可行解為：

Tx??00061020?，其目標(biāo)函數(shù)值z0?0。

由此寫出最初的單純性表：

xx

21x31x1*-1x11

124x3

x4

x5

x6

RHS

56-11210100001000010601020由題可知，N??A1A2TA3?，cB??000?cT?11?N???2T?1T檢驗(yàn)數(shù)可由?k?cBBN?cN可得：?1?2不是負(fù)數(shù)，則當(dāng)前解不是最優(yōu)解，A1列

中有三個(gè)元素大于零，取：

?bbb??601020?min?1,2,3??min?,,??10

?311??a11a21a31?故轉(zhuǎn)軸元為a21，x1為進(jìn)基變量，x5為出基變量。進(jìn)行旋轉(zhuǎn)變換后得下表：

xx

03x04x1-1x02*

1241x3

x4

x5

x6

RHS

6-5-52-3T0100-2-31-10001-20301010它對應(yīng)的基