數(shù)學(xué)模型設(shè)計(jì)——汽車分派問(wèn)題

1、一、汽車分派問(wèn)題摘要：在運(yùn)輸問(wèn)題中，如何獲取最大利潤(rùn)是商家一直探究的問(wèn)題，本文就這一問(wèn)題運(yùn)用了系數(shù)矩陣，線性規(guī)劃等方法進(jìn)行分析，得出了最佳分派方案問(wèn)題重述：某貨物運(yùn)輸公司有， 種型號(hào)的汽車. 由于運(yùn)輸條件，當(dāng)?shù)刎浽吹雀鞣N因素，每種型號(hào)的汽車運(yùn)輸貨物到不同城市所得的利潤(rùn)如表1.設(shè)一種汽車只能到一個(gè)城市，每個(gè)城市都只能要一種型號(hào)的汽車，應(yīng)如何安排發(fā)貨？表1城市1城市2城市3城市4城市53214571673425432156364394問(wèn)題分析：一種汽車只能到一個(gè)城市，每個(gè)城市都只能要一種型號(hào)的汽車（約束條件），分派后要使所得利潤(rùn)最大（決策目標(biāo)）模型假設(shè)：設(shè)變量Cij（i,j=1、2、3、4、5）表

2、示派第i號(hào)車到第j座城市的利潤(rùn)，引入變量Xij，其取值只能是0或1并令Xij=1(當(dāng)指派第i號(hào)車到第j座城市)，Xij=0（當(dāng)不指派第i號(hào)車到第j座城市），當(dāng)問(wèn)題要求極大時(shí)的數(shù)學(xué)模型是：Max=i j CijXiji Xij=1(j=1、2、3、4、5)j Xij=1(i=1、2、3、4、5)四、模型求解：第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素1、從系數(shù)矩陣的每一行減去該行的最大元素-2 -3 -4 -1 0 0 -6 -1 0 -4 -1 -3 0 -1 -2 -4 -5 -1 0 -3 -3 -5 -6 0 -52在從所得系數(shù)矩陣的每列元素中減去該列的最大元素3某行已

3、有0元素，不必再減-2 0 -4 -1 0 0 -3 -1 0 -4 -1 0 0 -1 -2 -4 -2 -1 0 -3 -3 -2 -6 0 -5第二步： 進(jìn)行試指派，以尋求最優(yōu)解。1從只有一個(gè)0元素的行或列開(kāi)始， 給這個(gè)0元素記為Y，這表示對(duì) 這行所代表的車，只有一種地方可去，然后劃去圈所在列的其他0元素記為K，這表示這列所代表的地方也指派完-2 0 -4 -1 0 0 -3 -1 K -4 -1 0 0 -1 -2 -4 -2 -1 K -3 -3 -2 -6 Y -5 2給只有一個(gè)0元素列的0元素記為Y，然后劃去Y所在的0元素記為K，并反復(fù)進(jìn)行上述兩步：-2 K -4 -1 Y Y -3 -1 K -4 -1 K Y -1 -2 -4 -2 -1 K -3 -3 -2 -6 Y -5得到最優(yōu)解矩陣： 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 結(jié)論：上述矩陣表示： 派A到第五座城市，派B到第一座城市，派C到第三座城市