運(yùn)籌學(xué)資料3多目標(biāo)規(guī)劃2ppt課件

1、多目的規(guī)劃的單純形算法 多目的規(guī)劃問題與線性規(guī)劃問題類似，可用單純形算法求解。留意：在比較檢驗(yàn)數(shù)大小時(shí)，要先比較較高級(jí)別的系數(shù)，再比較較低級(jí)別的系數(shù)。例4-9例4-6目的函數(shù)：Min S=P1d1-+P2(5d2+d3+)約束方程： 6X1+4X2+ d1- d1+=280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+=120 X1,X2,di-, di+ 0(i=1,2,3)規(guī)范型目的函數(shù)：Max S=-P1d1-P2(5d2+d3+)約束方程： 6X1+4X2+ d1- d1+=280 2X1+3X2+ d2- d2+=100 4X1+2X2+ d3- d3+

2、=120 X1,X2,di-, di+ 0(i=1,2,3)初始單純形表首先滿足第一目的P1進(jìn)基變量X1，出基變量y3- 主元4主元運(yùn)算：第三行除以4主元運(yùn)算：第一行加上第三行-6倍主元運(yùn)算：第二行加上第三行-2倍重新計(jì)算檢驗(yàn)數(shù)第二行除以2第一行加上第二行-1第三行加上第二行-1/2計(jì)算檢驗(yàn)數(shù)計(jì)算檢驗(yàn)數(shù)第一行乘上4/5第三行加上第一行3/8計(jì)算檢驗(yàn)數(shù)最后變量 y1-的檢驗(yàn)數(shù)為-P1+(4/5)P2由于假定P1P2，所以此檢驗(yàn)數(shù)也小于零。 該問題的最優(yōu)方案為消費(fèi)A產(chǎn)品44個(gè)單位，B產(chǎn)品4個(gè)單位，利潤為280百元。此時(shí)，原料正好用了100噸，工時(shí)比原方案超了64小時(shí)。例4-10 設(shè)某工廠消費(fèi)兩種產(chǎn)

3、品，都要經(jīng)過兩道工序，有關(guān)資料如下表。假設(shè)工序1，2都允許加班，使得利潤不少于1000元作為目的。又以：第1，2工序的加班工時(shí)之和盡能夠在160之內(nèi)為第一目的；產(chǎn)品乙必需嚴(yán)厲控制在70公斤之內(nèi)為第二目的；該廠的利潤越高越好為第三目的；盡量減少工序1，2加班工時(shí)為第四目的.試問：在上述條件下，該廠應(yīng)如何消費(fèi)？小時(shí)/公斤甲乙能提供的工時(shí)工序121100工序21180產(chǎn)量上界(kg)不限70利潤（元/kg)64解：設(shè)X1，X2為甲，乙兩種產(chǎn)品的消費(fèi)公斤數(shù)， d1-， d1+分別為低于或超越利潤1000元的偏向d2-， d2+分別為第1道工序剩余和加班的工時(shí)數(shù)d3-， d3+分別為第2道工序剩余和加班

4、的工時(shí)數(shù)d4-， d4+為加班工時(shí)之和低于或超越160工時(shí)數(shù)由于產(chǎn)品X2必需嚴(yán)厲控制在70公斤之內(nèi)為第一目的，那么可取d5-為實(shí)踐公斤數(shù)不到70的偏向，且 d5+=0。目的函數(shù)：Min Z=P1d4+ P2d5- + P3d1- + P4( d2+d3+)約束方程： 6X1+4X2+ d1- d1+=1000 2X1+ X2+ d2- d2+=100 X1+X2+ d3- d3+=80 d2+ + d3+ + d4 -d4+=160 X2 + d5 =70 X1,X2,di-, di+ , d5 0(i=1,2,3,4)目的函數(shù)：Max s= -P1d4+-P2d5- - P3d1- - P4

5、( d2+d3+)約束方程： 6X1+4X2+ d1- d1+=1000 2X1+ X2+ d2- d2+=100 X1+X2+ d3- d3+=80 d2+ + d3+ + d4 d4+=160 X2 + d5 =70 X1,X2,di-, di+ , d5 0(i=1,2,3,4)表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-641-1000000010000d2-21001-1000001000d3-1100001-1000800d4-000001011-10160-p2d5-0100000000170

6、p400000-10-10000p3640-100000001000p20100000000070p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-641-1000000010000d2-21001-1000001000d3-1100001-1000800d4-000001011-10160-p2d5-0100000000170p400000-10-10000p3640-100000001000p20100000000070p1000000000-100表1C00-p300-p40-

7、p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-641-1000000010000d2-21001-1000001000d3-1100001-1000800d4-000001011-10160-p2d5-0100000000170p400000-10-10000p3640-100000001000p20100000000070p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-601-1000000-47200d2-21001-10

8、00001000d3-1100001-1000800d4-000001011-10160-p2d5-0100000000170p400000-10-10000p3640-10000000720p20100000000070p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-601-1000000-47200d2-20001-10000-1300d3-1100001-1000800d4-000001011-10160-p2d5-0100000000170p400000-10-10000p

9、3640-10000000720p20100000000070p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-601-1000000-47200d2-20001-10000-1300d3-1000001-100-1100d4-000001011-101600X20100000000170p400000-10-10000p3600-1000000-4720p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-

10、d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-100-660026600d2-20001-10000-1300d3-1000001-100-1100d4-000001011-101600X20100000000170p400000-10-10000p3600-1000000-4660p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-100-660026600d2-00001-1-22001100X11000001-100-

11、1100d4-000001011-101600X20100000000170p400000-10-10000p3600-1000000-4660p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-100-660026600d2-00001-1-22001100X11000001-100-1100d4-000001011-101600X20100000000170p400000-10-10000p3000-100-66002660p200000000

12、00-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-100-660026600d2-00001-1-22001100X11000001-100-1100d4-000001011-101600X20100000000170p400000-10-10000p3000-100-66002660p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p

13、3d1-001-100-660026600d2-00001/2-1/2-11001/250X11000001-100-1100d4-000001011-101600X20100000000170p400000-10-10000p3000-100-66002660p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-330000-16300d2-00001/2-1/2-11001/250X11000001-100-1100d4-000001011-

14、101600X20100000000170p400000-10-10000p3000-100-66002630p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-330000-16300d2-00001/2-1/2-11001/250X110001/2-1/2-1000-1/2150d4-000001011-101600X20100000000170p400000-10-10000p3000-100-66002630p20000000000-1

15、0p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-330000-1630-p4d3+00001/2-1/2-11001/250X110001/2-1/2-1000-1/2150d4-0000-1/23/2101-1-1/21550X20100000000170p400001/2-3/2-10001/25p3000-1-330000-1630p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d

16、1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-330000-1630-p4d3+00001/2-1/2-11001/250X110001/2-1/2-1000-1/2150d4-0000-1/23/2101-1-1/21550X20100000000170p400001/2-3/2-10001/25p3000-1-330000-1630p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-330000-1630-p4d3

17、+00001/2-1/2-11001/250X110001/2-1/2-1000-1/215-p4d2+0000-1/312/302/3-2/3-1/31030X20100000000170p400001/2-3/2-10001/2108p3000-1-330000-1630p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-20-20-220320-p4d3+00001/2-1/2-11001/250X110001/2-1/2-1000-1/

18、215-p4d2+0000-1/312/302/3-2/3-1/31030X20100000000170p400001/2-3/2-10001/2108p3000-1-330000-1320p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-20-20-220320-p4d3+00001/30-2/311/3-1/31/3570X110001/2-1/2-1000-1/215-p4d2+0000-1/312/302/3-2/3-1/31030X

19、20100000000170p400001/2-3/2-10001/2160p3000-1-330000-1320p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-20-20-220320-p4d3+00001/30-2/311/3-1/31/3570X110001/2-1/2-1000-1/215-p4d2+0000-1/312/302/3-2/3-1/31030X20100000000170p400001/2-3/2-10001/2160

20、p3000-1-330000-1320p20000000000-10p1000000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-20-20-220320-p4d3+00001/30-2/311/3-1/31/3570X110001/30-2/301/3-1/3-2/3200/3-p4d2+0000-1/312/302/3-2/3-1/31030X20100000000170p4000000001-10160p3000-1-20-20-220320p20000000000-10p10

21、00000000-100表1C00-p300-p40-p40-p1-p2CBXBX1X2d1-d1+d2-d2+d3-d3+d4-d4+d5-b-p3d1-001-1-20-20-220320-p4d3+00001/30-2/311/3-1/31/3570X110001/30-2/301/3-1/3-2/3200/3-p4d2+0000-1/312/302/3-2/3-1/31030X20100000000170p4000000001-10160p3000-1-20-20-220320p20000000000-10p1000000000-100到目前為止，曾經(jīng)不能再進(jìn)展下去，21否那么會(huì)破壞曾經(jīng)滿足的條件。該題的解答：X1=200/3 ，X2=70， d1- =320， d2+=310/3， d3+=170/3 d4+= d4- = d5- =0即該廠消費(fèi)方案：消費(fèi)產(chǎn)品甲200/3公斤，產(chǎn)品乙70公斤，第1道工序加班310/3工時(shí)，第2道工序加班170/3工時(shí)，才干獲利1000- d1- =1000-320=680元。投資規(guī)劃實(shí)例某經(jīng)濟(jì)區(qū)預(yù)備籌集資金，在下個(gè)方案期內(nèi)投資