運(yùn)籌學(xué)例題集錦

1、1.1線性規(guī)劃標(biāo)準(zhǔn)型線性規(guī)劃標(biāo)準(zhǔn)型maxZ=c1x1c2x2…cnxns.t.a11x1a12x2…a1nxn=b1a21x1a22x2…a2nxn=b2am1x1am2x2….amnxn=bmx1x2….xn?0用兩個(gè)變量的差值代替無(wú)約束變量，左邊加一個(gè)變量將＜變=，左邊減一個(gè)變量將＞變=。目標(biāo)函數(shù)左邊乘1將minZ變maxZ1用對(duì)偶單純形法對(duì)偶單純形法解下列線性規(guī)劃問(wèn)題minS=x14x23x4s.t.x12x2x3x4?32x1x

2、24x3x4?2x1，x2，x3，x4?0解：此題可用人工變量方法求，但也可用對(duì)偶單純形法。maxS’=x14x23x4s.t.x12x2x3x4x5=32x1x24x3x4x6=2x1，x2，x3，x4，x5，x6?0Cj140300CBXBx1x2x3x4x5x6b0x512111030x62141012σ1403000常數(shù)項(xiàng)是負(fù)數(shù)且最小，確定出基變量x5。用出基變量x5行的所有負(fù)數(shù)分別去除對(duì)應(yīng)的檢驗(yàn)數(shù)，最小值對(duì)應(yīng)的為進(jìn)基變量x1，

3、交叉元素為主元（1）主元運(yùn)算：第一行乘（1）【提示:表格同上，x5行對(duì)應(yīng)數(shù)字乘1，這里不抄】主元運(yùn)算：第二行加上第一行乘（2）【提示：是對(duì)應(yīng)第二張表的，繼續(xù)畫(huà)出表3】計(jì)算檢驗(yàn)數(shù)確定出基變量X6確定進(jìn)基變量X3，主元（2）Cj140300CBXBx1x2x3x4x5x6b0x112111030x60323218σ0212103主元運(yùn)算：第一行加第二行乘（12）【根據(jù)上表繼續(xù)畫(huà)表5，σ行不填】計(jì)算檢驗(yàn)數(shù)：全為非正。但此時(shí)常數(shù)b已全大于零，最

4、優(yōu)解=（7，0，4，0）最優(yōu)值S’=7S=7Cj140300CBXBx1x2x3x4x5x6b1x11720121270x3032131124σ01201221274某石油公司四廠七售區(qū)某石油公司四廠七售區(qū)煉油廠1234日產(chǎn)量35251540解：解：平衡問(wèn)題，用最小元素法求初始方案。計(jì)算檢驗(yàn)數(shù)。閉合回路。最優(yōu)方案如下，最小運(yùn)費(fèi)=元有非基變量的檢驗(yàn)數(shù)=0，有無(wú)窮多組解，另外一個(gè)解如下：5鐵路列車編組站鐵路列車編組站MM1??排隊(duì)問(wèn)題。其中