數(shù)學(xué)規(guī)劃模型2014

數(shù)學(xué)規(guī)劃模型I引言

一個(gè)復(fù)雜系統(tǒng)往往要受諸多因素的影響，而這些因素又要受到一定的限制。最優(yōu)化就是研究在一定約束下，如何選取這些因素的值，使某項(xiàng)（或某些）指標(biāo)達(dá)到最優(yōu)的一門學(xué)科。數(shù)學(xué)規(guī)劃是最優(yōu)化中的重要部分。它包括線性規(guī)劃、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、動(dòng)態(tài)規(guī)劃、非線性規(guī)劃等。數(shù)學(xué)規(guī)劃方法在經(jīng)濟(jì)、軍事、科技等領(lǐng)域內(nèi)都有廣泛的應(yīng)用。內(nèi)容提要

一、一般的數(shù)學(xué)規(guī)劃模型二、數(shù)學(xué)規(guī)劃常見(jiàn)模型：1.運(yùn)輸問(wèn)題（例1，2）

2.網(wǎng)絡(luò)（規(guī)劃）問(wèn)題（例3，4）3.分派問(wèn)題

（例5）4.生產(chǎn)活動(dòng)問(wèn)題（例6，7，8，9）5.選址問(wèn)題

（例10，11，12，13，14）

6.線性多目標(biāo)規(guī)劃問(wèn)題（例15）7.線性目標(biāo)規(guī)劃問(wèn)題（例15）一、一般的數(shù)學(xué)規(guī)劃模型數(shù)學(xué)規(guī)劃模型的一般形式：例如：maxs.t.若能寫出描述S的數(shù)學(xué)式子，則可直接寫出。這里目標(biāo)函數(shù)可行域可行解決策變量描述S的數(shù)學(xué)式子約束條件S問(wèn)題可行問(wèn)題不可行最優(yōu)解最優(yōu)目標(biāo)值幾個(gè)概念：特別：(或max)或線性規(guī)劃模型（LP）或等約束的LP模型的矩陣形式LP模型的向量形式注：M是常數(shù)與有相同的最優(yōu)解1.2.與有相同的最優(yōu)解另外：1.取整數(shù)，稱模型為整數(shù)規(guī)劃模型2.中部分取整數(shù)，稱模型為混合整數(shù)規(guī)劃模型3.只取0或1兩個(gè)值，稱為0—1規(guī)劃模型目標(biāo)函數(shù)或約束條件是非線性的，稱為非線性規(guī)劃模型若目標(biāo)函數(shù)只有一個(gè)，稱為單目標(biāo)規(guī)劃模型；若目標(biāo)函數(shù)不只一個(gè)，稱為多目標(biāo)規(guī)劃模型。產(chǎn)地銷地運(yùn)價(jià)例1求使總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。試建模。產(chǎn)量需求量42一、運(yùn)輸問(wèn)題解則產(chǎn)銷平衡注：若產(chǎn)大于銷，則若產(chǎn)小于銷，則線性規(guī)劃模型

重要結(jié)論：當(dāng)供應(yīng)量與需求量均為整數(shù)時(shí)，模型的最優(yōu)解是整數(shù)解。求解運(yùn)輸問(wèn)題可采用表上作業(yè)法，或忽略掉運(yùn)輸問(wèn)題的特殊性，直接使用求解一般線性規(guī)劃的單純形法實(shí)際問(wèn)題中產(chǎn)銷不平衡時(shí)，也可在分析問(wèn)題階段將其化為產(chǎn)銷平衡問(wèn)題，舉例如下例：化肥供應(yīng)問(wèn)題：設(shè)由三個(gè)化肥場(chǎng)供應(yīng)四個(gè)地區(qū)的農(nóng)用化肥，假定等量的化肥在這些地區(qū)使用效果相同。已知各化肥廠年產(chǎn)量，各地區(qū)年需要量及從各化肥廠到各地區(qū)的單位運(yùn)價(jià)表，試決定使得總運(yùn)費(fèi)最省的化肥調(diào)撥方案。IIIIIIIV產(chǎn)量A1613221750B1413191560C192023－50最低需求3070010最高需求507030不限I’I’’IIIIIIV’IV’’產(chǎn)量A16161322171750B14141319151560C1919202350D000銷量7030解：分析實(shí)際問(wèn)題，得產(chǎn)銷平衡表例2

自來(lái)水輸送問(wèn)題某市有甲、乙、丙、丁四個(gè)居民區(qū)，自來(lái)水由A、B、C三個(gè)水庫(kù)供應(yīng)。四個(gè)區(qū)每天必須的基本生活用水分別為30、70、10、10千噸，但三個(gè)水庫(kù)每天最多只能分別供應(yīng)50、60、50千噸自來(lái)水。由于地理位置的差別，自來(lái)水公司從各水庫(kù)向各區(qū)送水所付出的引水管理費(fèi)不同（如表，其中C水庫(kù)與丁區(qū)間無(wú)輸水管道），引水管理費(fèi)(元/千噸)其它各種管理費(fèi)均為450元/千噸。各區(qū)用戶向自來(lái)水公司繳納900元/千噸的水費(fèi)。此外，各區(qū)用戶都向公司申請(qǐng)了額外用水量，分別為每天50、70、20、40千噸。問(wèn)公司應(yīng)如何分配供水量，才能獲利最多？引水管理費(fèi)(元/千噸)將有關(guān)數(shù)據(jù)整理列表：水庫(kù)居民區(qū)供應(yīng)量生活用水額外用水成水輸本問(wèn)題分析：…可看成是“產(chǎn)小于銷”的運(yùn)輸問(wèn)題。解設(shè)xij

分別表示水庫(kù)A,B,C(i=1,2,3)向居民區(qū)甲,乙,丙,丁(j=1,2,3,4)的供水量。其中X34=0.模型建立由題意目標(biāo)函數(shù)為：可轉(zhuǎn)化為：一般問(wèn)題中：供給限制用“”需求限制用“”“”引水管理費(fèi)因供小于需，所以，160千噸水須全部輸出居民繳納的買完160千噸的水費(fèi)供給限制需求限制另：為了增加供水，公司考慮改造水庫(kù)，使三個(gè)水庫(kù)的供水能力提高一倍，問(wèn)模型將作何改動(dòng)？分析：由于總供水能力為320千噸，總需求量為300千噸，水不能全部賣出，所以不能將獲利最多轉(zhuǎn)化為引水管理費(fèi)最少。須算出每千噸凈利潤(rùn)。每千噸凈利潤(rùn)＝用戶交的900元－其它管理費(fèi)450元－引水管理費(fèi)凈利潤(rùn)(元/千噸)模型改為：其它同前例3①②③④⑤⑥⑦圖中弧上的數(shù)字表示每小時(shí)兩結(jié)點(diǎn)沿箭頭方向的最大車流量，求①到⑦每小時(shí)的最大車流量。二、網(wǎng)絡(luò)（規(guī)劃）問(wèn)題之一-----最大流問(wèn)題設(shè)v為從出發(fā)的車流量，

為到的車流量，則流量守恒條件弧容量限制去掉去掉若不設(shè)v,則模型有四處需修改①②③④⑤⑥⑦如果源、匯不止一個(gè)時(shí)，建模方法類似。可增加一個(gè)虛擬源、虛擬匯化成單源單匯的問(wèn)題。

圖中的結(jié)點(diǎn)稱為源（發(fā)點(diǎn)），結(jié)點(diǎn)稱為匯（收點(diǎn)）。圖是單源單匯的情形。例42求從流出，到的最大流量。解設(shè)為到的流量，

、為流入、的量，

、、為流入、、的量。例：多端網(wǎng)絡(luò)問(wèn)題設(shè)有5位待業(yè)者，5項(xiàng)工作，他們各自能勝任工作的情況如圖所示，要求設(shè)計(jì)一個(gè)就業(yè)方案，使盡量多的人能就業(yè)。其中表示工人。表示工作。這本身是個(gè)最大匹配問(wèn)題，可以轉(zhuǎn)化為最大流問(wèn)題求解。在二部圖中增加兩個(gè)新點(diǎn)分別作為發(fā)點(diǎn)，收點(diǎn)。并用有向邊把它們與原二部圖中頂點(diǎn)相連，令全部邊上的容量均為1。當(dāng)網(wǎng)絡(luò)流達(dá)到最大時(shí)，如果上的流量為1，就讓作工作，此即為最大匹配方案。例：某河流中有幾個(gè)島嶼，從兩岸至各島嶼及各島嶼之間的橋梁編號(hào)如圖，在一次敵對(duì)的軍事行動(dòng)中，問(wèn)至少應(yīng)炸斷幾座橋，才能完全切斷兩岸的交通。二、網(wǎng)絡(luò)（規(guī)劃）問(wèn)題之二-----中國(guó)郵路問(wèn)題、最優(yōu)Hamilton圈（TSP）問(wèn)題18世紀(jì)，在德國(guó)東普魯士哥尼斯堡有七座橋，連接這七座橋的陸地有四塊，如下圖，一個(gè)散步者能否從四塊陸地中的任意一塊開(kāi)始，通過(guò)每座橋恰好一次，最后回到出發(fā)點(diǎn)？BCD七橋問(wèn)題

定義：（Euler跡、Euler環(huán)游、Euler圖）解：1。模擬圖：以頂點(diǎn)表陸地，以邊表橋，得4個(gè)頂點(diǎn)的模擬圖。2。問(wèn)題等價(jià)于：能否有一條閉跡包含模擬圖的所有邊，即：模擬圖是Euler圖嗎？3。求解：假設(shè)圖G是Euler圖。因?yàn)殚]跡是連通的，所以圖G也連通。又因?yàn)槊總€(gè)頂點(diǎn)既能到達(dá)也能離開(kāi)，所以圖G的每個(gè)頂點(diǎn)度都是偶數(shù)。所以，歐拉在1736年得出結(jié)論：“七橋問(wèn)題”是不可能的，同時(shí)開(kāi)創(chuàng)了圖論的研究。含圖G的所有邊的跡，稱為Euler跡（如果此跡是閉跡，也叫Euler環(huán)游），把含有Euler閉跡（環(huán)游）的圖稱為Euler圖。如果一個(gè)圖G含有Euler閉跡，我們?nèi)绾握业剿兀肯旅娼榻B一種尋找Euler圖中Euler閉跡的算法－Fleury算法Fleury算法（1）任取一個(gè)頂點(diǎn)，置；（2）假定跡已經(jīng)選出，則用下列方法從中選出：a）與關(guān)聯(lián)；b）除非沒(méi)有其它的邊可選擇，不是

c)當(dāng)(2)不能執(zhí)行時(shí)，停止，否則，令i+1i,轉(zhuǎn)(2)的割邊。割邊：連通圖G中不在任何圈中的邊。兩個(gè)定理定理：若G是Euler圖，則G的任何用Fleury算法構(gòu)成的跡都是Euler環(huán)游（閉跡）。定理：圖G含Euler閉跡（環(huán)游）的充要條件是G連通且沒(méi)有奇頂點(diǎn)。若一個(gè)郵遞員在下圖所示的街道上投遞郵件，問(wèn)如何投遞才使得他走遍每一條街道，再返回郵局，且總路程最短？11111111中國(guó)郵路問(wèn)題這是由中國(guó)數(shù)學(xué)家管梅谷教授于1960年提出并求解的。問(wèn)題分析：據(jù)上面定理知，若街道圖中沒(méi)有奇點(diǎn)，則他就可以從郵局出發(fā)，走過(guò)每條街道一次，且僅一次，最后回到郵局，如此他所走的路程即是最短路程。而對(duì)于有奇點(diǎn)的圖，必須在某些街道上重復(fù)走一次或多次。（假定N1為郵局）這樣，路線可有多種，例：總權(quán)為12總權(quán)為11可見(jiàn)，按第一條路線，在邊上各重復(fù)走了一次，而按第二條路線，在邊上各重復(fù)走了一次。因此，我們想到，可在一個(gè)有奇點(diǎn)的圖中，增加一些重復(fù)邊，使得新圖不含奇點(diǎn)，且要求重復(fù)邊的總權(quán)最小。注釋：增加重復(fù)邊使圖無(wú)奇點(diǎn)的過(guò)程稱為可行方案。使總權(quán)最小的可行方案稱為最小方案第一步（找初始可行方案）：找到圖中的奇點(diǎn)，把奇點(diǎn)兩兩相連，（因?yàn)椋谌魏螆D中奇點(diǎn)個(gè)數(shù)必為偶數(shù)）。第二步（調(diào)整可行方案）：調(diào)整時(shí)遵循兩個(gè)原則：（a）在最優(yōu)方案中，圖的每一條邊上最多有一條重復(fù)邊；（b）在最優(yōu)方案中，圖的每一個(gè)圈上重復(fù)邊的總權(quán)不大于該圈總權(quán)的一半。（若把圖中某個(gè)圈上的重復(fù)邊去掉，而給原來(lái)沒(méi)有重復(fù)邊的的邊上加上重復(fù)邊，圖中仍沒(méi)有奇點(diǎn)）第三步（判斷最優(yōu)方案）：檢查條件（a），（b）是否滿足，若是，則為最優(yōu)。得求解步驟：例：求解下面問(wèn)題。255964343444解：奇點(diǎn)有：連接且連接得：255964343444因?yàn)槿Φ目倷?quán)為24，但重復(fù)邊的總權(quán)為14，大于該圈總權(quán)的一半，故需要調(diào)整，以上的重復(fù)邊代替上的重復(fù)邊，使重復(fù)邊總長(zhǎng)下降為17，255964343444同理，調(diào)整圈

后，得最優(yōu)方案：255964343444注1：此法稱為奇偶點(diǎn)圖上作業(yè)法，由管梅谷給出。注2：最優(yōu)方案就是一個(gè)Euler圖了，再對(duì)它使用Fleury算法就能找到郵遞員的滿足要求的投遞路線了。255964343444例：對(duì)上面的結(jié)果用Fleury算法給出一個(gè)Euler環(huán)游

Hamilton圈和旅行售貨商問(wèn)題

1859年，數(shù)學(xué)家Hamilton發(fā)明了一種周游世界的游戲。把一個(gè)12面體的20個(gè)頂點(diǎn)分別標(biāo)上北京、東京、華盛頓等20個(gè)大都市的名字，要求玩的人從某城市出發(fā)，沿著12面體的棱通過(guò)每一個(gè)城市恰好一次，再回到出發(fā)的城市。這種游戲在歐洲曾經(jīng)風(fēng)靡一時(shí)，Hamilton以25個(gè)金幣的高價(jià)把該項(xiàng)專利賣給了一個(gè)玩具商。用圖論的語(yǔ)言來(lái)講，此游戲本質(zhì)就是在一個(gè)12面體上尋找經(jīng)過(guò)每一個(gè)頂點(diǎn)一次且恰好一次的特殊的圈，即Hamilton回路。此問(wèn)題后面會(huì)進(jìn)一步詳述。例5

設(shè)有工作件，人員個(gè)，且一人做一件工作，第人作第件工作的時(shí)間（或費(fèi)用）為，問(wèn)：如何分派可使總時(shí)間（或總費(fèi)用）最少。解本題需確定：第人做或不做第件工作，這是定性變量，首先將其定量化。設(shè)0—1規(guī)劃模型則注：若表示效益，則目標(biāo)函數(shù)應(yīng)極大化若人數(shù)“>”工作件數(shù)三、分派問(wèn)題、指派問(wèn)題對(duì)于指派問(wèn)題，除了可以使用一般的整數(shù)規(guī)劃的方法求解之外，還可以結(jié)合問(wèn)題自身的特點(diǎn)，使用此問(wèn)題專門的求解方法--------匈牙利法求解人數(shù)工作數(shù)不等的情況可以通過(guò)變化，變成相等的情況，即完美指派，舉例如下甲乙丙丁戊仰泳37.732.933.83735.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1解：該問(wèn)題可看作指派問(wèn)題。添加一個(gè)虛擬項(xiàng)目，得到如下效率矩陣

甲乙丙丁戊仰泳37.732.933.83735.4蛙泳43.433.142.234.741.8蝶泳33.328.538.930.433.6自由泳29.226.429.628.531.1虛擬00000甲乙丙丁戊仰泳3.91.904.11.6蛙泳7.80.36.606.2蝶泳207.602.3自由泳000.40.21.9虛擬02.800.90最優(yōu)結(jié)果如下四、生產(chǎn)活動(dòng)問(wèn)題(分段函數(shù)、矛盾約束等的處理方法)資源產(chǎn)品單耗資源量單位利潤(rùn)例6問(wèn)如何安排生產(chǎn)使總利潤(rùn)最大。解設(shè)表示第種產(chǎn)品的產(chǎn)量，則資源分配問(wèn)題分段函數(shù)問(wèn)題（有關(guān)的收益問(wèn)題）假設(shè)例中＝單位收益－單位成本（可變成本）若還要考慮固定成本（如：機(jī)器、廠房等）于是，需要引入0—1變量：設(shè)Lj

是xj的上界，則模型改寫為：假設(shè)第j種產(chǎn)品的固定成本是，第j種產(chǎn)品產(chǎn)量的上界為，混合整數(shù)規(guī)劃模型等價(jià)性：（1）由Z的極大化（2）由當(dāng)然，固定成本一般都是指機(jī)器、廠房等帶來(lái)的成本，在某個(gè)固定的時(shí)期內(nèi)，它們往往是一個(gè)相對(duì)固定的值，所以一般可以在整個(gè)收益函數(shù)的后面減去此值即可?？刹挥绊懺Ｐ偷淖顑?yōu)解。注：將目標(biāo)函數(shù)變成則為非線性的。若不考慮固定成本，則不引入0-1變量。

更復(fù)雜的分段函數(shù)的處理方法*設(shè)B1是某種原料（單位：噸），還可以從市場(chǎng)上購(gòu)買到不超過(guò)1500噸的原料。若購(gòu)買量不超過(guò)500噸，其價(jià)格為10千元/噸；購(gòu)買量多于500噸但不超過(guò)1000噸時(shí)，超過(guò)500噸的部分8千元/噸；購(gòu)買量超過(guò)1000噸時(shí)，超過(guò)1000噸的部分6千元/噸。問(wèn)怎樣安排生產(chǎn)和采購(gòu)？增設(shè)y為采購(gòu)量，則可得采購(gòu)支出（千元）：這時(shí)，目標(biāo)函數(shù)為:處理方法：設(shè)三種價(jià)格的采購(gòu)量分別為：則目標(biāo)函數(shù)為：約束條件增加：只有當(dāng)

y1=500時(shí)，才能以每噸8千元的價(jià)格購(gòu)買y2(>0)非線性規(guī)劃模型！注：當(dāng)然，此時(shí)還得考慮B1這種資源的擁有量也要跟著調(diào)整，此時(shí)的b1應(yīng)該改為：產(chǎn)品種類限制問(wèn)題（不考慮固定成本）n種產(chǎn)品中只生產(chǎn)其中k種設(shè)則若加入要求：產(chǎn)量不小于80單位如果產(chǎn)量沒(méi)有上限，此時(shí)可取Lj為較大的正數(shù)Lj是產(chǎn)量上限矛盾約束問(wèn)題如果、是機(jī)器1、2的可用工時(shí)（資源），

且假定n種產(chǎn)品只能在其中一臺(tái)機(jī)器上加工，則以下兩個(gè)約束條件此時(shí)，若引入0—1變量：設(shè)M是充分大的常數(shù)，則兩個(gè)矛盾約束可統(tǒng)一在一個(gè)模型中：是矛盾的，不能同時(shí)出現(xiàn)在一個(gè)模型中，即，要在達(dá)到最優(yōu)的過(guò)程中讓其中一個(gè)約束無(wú)效一般，若m種資源中只用其中k種資源，則令約束條件改為：若yi=1，則約束無(wú)效例7

生產(chǎn)存儲(chǔ)問(wèn)題（多階段問(wèn)題）某公司生產(chǎn)一種產(chǎn)品，最大生產(chǎn)能力為100單位，第月的單位存儲(chǔ)費(fèi)為元，預(yù)定的銷售量和單位成本如表。求使生產(chǎn)成本與存儲(chǔ)費(fèi)之和最低的生產(chǎn)計(jì)劃。解先作合理假設(shè)?1月初無(wú)庫(kù)存；?4月底賣完；?當(dāng)月生產(chǎn)的不入庫(kù)；?庫(kù)存量無(wú)限制。假設(shè)：月份單位成本(元)銷售量(件)模型一且為整數(shù)，第j+1月初的庫(kù)存量整數(shù)規(guī)劃模型設(shè)為第月的產(chǎn)量，為單位存儲(chǔ)費(fèi)，則銷售量限制最后庫(kù)存為0限制最大生產(chǎn)能力限制模型二若設(shè)為第月初的庫(kù)存量，則且為整數(shù)，增加了決策變量，但模型簡(jiǎn)潔了。本問(wèn)題還可建立動(dòng)態(tài)規(guī)劃模型幾點(diǎn)說(shuō)明：1.增加投資擴(kuò)大生產(chǎn)能力若每投資k元可增加一個(gè)單位的生產(chǎn)能力。設(shè)表示第月的投資，則第月的產(chǎn)量限制條件變?yōu)椋旱谠虑暗耐顿Y在第月仍起作用，生產(chǎn)投資問(wèn)題。2.均衡生產(chǎn)問(wèn)題如果前面求出的各月最優(yōu)生產(chǎn)量彼此差別較大，這表示生產(chǎn)不均衡（可使得生產(chǎn)資料（如：人力）的分配不均衡），為使生產(chǎn)盡量均衡，可增加相繼兩個(gè)月產(chǎn)量差的限制：同時(shí)希望非負(fù)變量、越小越好。則目標(biāo)函數(shù)增加以下兩項(xiàng)：其中a

為第月比第月增加一個(gè)產(chǎn)品要支付的費(fèi)用，b

為減少一個(gè)產(chǎn)品支付的費(fèi)用。且或分別各增加一項(xiàng)：或不希望減少不希望增加例8

：求生產(chǎn)、存儲(chǔ)、維修計(jì)劃（多階段資源分配問(wèn)題）某機(jī)械廠計(jì)劃在1－6月份生產(chǎn)7種產(chǎn)品。該廠有5種機(jī)床，其數(shù)量如下表。已知第j種產(chǎn)品在第t種機(jī)床上所需加工臺(tái)時(shí)為第j種產(chǎn)品的單位利潤(rùn)為，第i月第j種產(chǎn)品的銷售限量為。每種產(chǎn)品一次至多儲(chǔ)存100件，每件月存儲(chǔ)費(fèi)a元，1月初無(wú)存儲(chǔ)，6月底每種產(chǎn)品要求余50件。生產(chǎn)每天兩班，每班8小時(shí)，一個(gè)月平均工作21天。工廠規(guī)定，在半年內(nèi)每臺(tái)機(jī)床在某月必須停車維修一次，維修時(shí)間為10天。為使利潤(rùn)最大，工廠應(yīng)該如何安排生產(chǎn)？機(jī)床類型12345數(shù)量42311機(jī)床類型12345月臺(tái)時(shí)13446721008336336解：將有關(guān)數(shù)據(jù)整理列表：機(jī)床單耗產(chǎn)品臺(tái)數(shù)月臺(tái)時(shí)單位利潤(rùn)月臺(tái)時(shí)＝臺(tái)數(shù)小時(shí)天數(shù)。1344＝41621如一臺(tái)機(jī)床維修一次需160(臺(tái)時(shí))＝10(天)16(小時(shí))19假定：?沒(méi)有輪到維修的和維修后的機(jī)床在使用期間能正常工作；?維修一臺(tái)機(jī)床是在某月內(nèi)完成，不會(huì)跨入下一月。設(shè)

—第月初、第種產(chǎn)品的庫(kù)存量，

—第月、第種產(chǎn)品的產(chǎn)量，

—第月、第種機(jī)床的維修量。需求限制資源限制維修限制?第月維修哪幾臺(tái)機(jī)床可由人安排，只安排未維修的；例9（下料問(wèn)題）某廠要做100套鋼架，每套由長(zhǎng)為2.9米，2.1米和1.5米的圓鋼各一根組成。已知原料長(zhǎng)7.4米。問(wèn)如何下料使原料最省。試建模。問(wèn)題分析：“最節(jié)省”可以是“所用原料根數(shù)最少”，也可以是“余料最少”。基于前者建模。一根原料鋼管有不同的切割組合…..。找出每一種組合用去多少根原料鋼管。所以首先列出所有可能組合即“模式”。解將8種下料方案列表:方案根數(shù)長(zhǎng)度合計(jì)6.06.67.26.37.46.57.17.3余料1.40.80.21.100.90.30.1需求量若希望余料最少，則?余料超過(guò)1.5米?約束條件取“＝100”?設(shè)需根原料，第根下第種圓鋼根，n是決策變量，而線性規(guī)劃模型中是定數(shù)！該模型不易計(jì)算！以下幾種作法欠妥：客戶擬定的設(shè)施地址（1）離散型選址問(wèn)題（2）連續(xù)型選址問(wèn)題設(shè)施的地址未擬定，可選在所給區(qū)域（很大）的任何地方。五、選址問(wèn)題在區(qū)域內(nèi)事先擬定了有限個(gè)供選擇的位置，且客戶到達(dá)這些位置的費(fèi)用已知問(wèn)題：第個(gè)設(shè)施是否需修建？若要修建，應(yīng)為周圍哪些客戶服務(wù)選址—分配問(wèn)題還可根據(jù)需選設(shè)施的個(gè)數(shù)分為：?jiǎn)卧催x址和多源選址多源選址中不僅要確定新設(shè)施的位置，還要確定哪個(gè)設(shè)施應(yīng)為哪些客戶服務(wù)。多源選址需提出的問(wèn)題如下：例10（離散型）施工點(diǎn)j對(duì)某材料的需求量為第i個(gè)料場(chǎng)的容量為的單位運(yùn)費(fèi)

(元/噸).求使總費(fèi)用最少的場(chǎng)址?？苫趦煞N考慮建模：2°施工點(diǎn)只能在某一料場(chǎng)獲取全部所需材料。1°施工點(diǎn)可在任何料場(chǎng)獲取部分材料，以滿足需求；建場(chǎng)費(fèi)為di

元,解1°假定：?任何施工點(diǎn)到任何料場(chǎng)的道路是通的；?施工點(diǎn)可在任何料場(chǎng)獲取部分材料，以滿足需求；擬定m個(gè)地方建料場(chǎng)，為地址到施工點(diǎn)一個(gè)大型工程有n個(gè)施工點(diǎn)，則總費(fèi)用需求限制容量限制非負(fù)限制mins.t.混合整數(shù)規(guī)劃模型2°假定：?任何施工點(diǎn)到任何料場(chǎng)的道路是通的；?施工點(diǎn)只能在某一料場(chǎng)獲取全部所需材料。設(shè)則總費(fèi)用需求限制容量限制mins.t.非負(fù)限制0—1規(guī)劃模型由于區(qū)域很大，所以施工點(diǎn)到料場(chǎng)間的距離視為直線距離例11（連續(xù)型）設(shè)工程所涉及的區(qū)域很大，第j個(gè)施工點(diǎn)的坐標(biāo)為：?jiǎn)挝贿\(yùn)費(fèi)為c(元/噸/公里),欲建的m個(gè)料場(chǎng)地址未擬定，其余條件與例10相同。求使總費(fèi)用最少的場(chǎng)址。解此處僅基于第二種考慮建模設(shè)料場(chǎng)的坐標(biāo)為mins.t.

同前例

對(duì)可不作非負(fù)限制，稱為自由變量非線性規(guī)劃模型注：(1)若m個(gè)料場(chǎng)都要修建，則不設(shè)0—1變量（3）若區(qū)域小，且道路呈網(wǎng)狀，則使用矩形距離（2）指標(biāo)不一定是“費(fèi)用”，可以是“客戶”到“設(shè)施”的最大距離最小等。相當(dāng)于將取成1。目標(biāo)函數(shù)中的常數(shù)項(xiàng)應(yīng)去掉。如下例12若希望用戶到中心的最大距離越小越好，則??也可以是用戶到中心的距離之和最小建模。均在第一象限內(nèi)，例12

設(shè)某城市的街道成縱橫交叉的網(wǎng)狀，今欲建一物資供應(yīng)中心，供n個(gè)用戶。問(wèn)該中心建在什么位置合適。試建模。),,(yx處，坐標(biāo)為供應(yīng)中心建在街道拐角以下幾種作法不妥：?用直線距離?沒(méi)設(shè)“中心”建在街道拐角處?將“中心”取在坐標(biāo)原點(diǎn)，本應(yīng)該是用戶坐標(biāo)的常量卻成為了決策變量，這樣不對(duì)例13某公司有工廠A1,A2生產(chǎn)某種產(chǎn)品，生產(chǎn)能力分別為Q1,Q2,有四個(gè)容量為Mk的倉(cāng)庫(kù)Bk(k=1,2,3,4)存放該產(chǎn)品，工廠和倉(cāng)庫(kù)均可向n個(gè)客戶Cj(j=6,7,…n+5)供貨，客戶需求量為qj(j=6,7,…n+5).現(xiàn)公司打算：擴(kuò)建倉(cāng)庫(kù)B1,其費(fèi)用為e1，庫(kù)容量增加M；新建倉(cāng)庫(kù)B5,費(fèi)用為e5，庫(kù)容量為M5;關(guān)閉倉(cāng)庫(kù)B2或B3,關(guān)閉后可節(jié)約費(fèi)用e2或e3;并要求總的倉(cāng)庫(kù)數(shù)不得超過(guò)4個(gè)。已知工廠Ai向倉(cāng)庫(kù)或客戶供貨的運(yùn)費(fèi)每單位為cij(i=1,2;j=1,2,3,4,5為向倉(cāng)庫(kù)供貨的運(yùn)費(fèi)，j=6,7,…,n+5為向客戶供貨的運(yùn)費(fèi))。第k個(gè)倉(cāng)庫(kù)向第j個(gè)客戶供貨的單位運(yùn)費(fèi)dkj(k=1,2,3,4,5;j=6,7,…,n+5)。以上費(fèi)用均由公司負(fù)擔(dān)。問(wèn)公司該作何選擇可使總費(fèi)用最少。解為便于理解，先作網(wǎng)絡(luò)圖。工廠倉(cāng)庫(kù)客戶費(fèi)用來(lái)自兩部分：運(yùn)費(fèi)+建設(shè)費(fèi)用?？煞逻\(yùn)輸問(wèn)題，將有關(guān)數(shù)據(jù)列表。產(chǎn)地銷地運(yùn)價(jià)總量其中產(chǎn)地運(yùn)送到倉(cāng)庫(kù)的量

產(chǎn)量限制客戶需求限制倉(cāng)庫(kù)數(shù)量限制倉(cāng)庫(kù)容量限制變量取值范圍例14

（選課策略）某校規(guī)定，運(yùn)籌學(xué)專業(yè)的學(xué)生畢業(yè)時(shí)必須至少學(xué)習(xí)過(guò)兩門數(shù)學(xué)課、三門運(yùn)籌學(xué)課和兩門計(jì)算機(jī)課。這些課程的編號(hào)、名稱、學(xué)分、所屬類別和先修課程要求如下表。問(wèn)：畢業(yè)時(shí)，學(xué)生最少可以學(xué)習(xí)哪些課程？編號(hào)名稱學(xué)分所屬類別先修課要求微積分5數(shù)學(xué)線性代數(shù)4數(shù)學(xué)最優(yōu)化4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線代數(shù)據(jù)結(jié)構(gòu)3數(shù)學(xué)；計(jì)算機(jī)計(jì)算機(jī)編程應(yīng)用統(tǒng)計(jì)4數(shù)學(xué)；運(yùn)籌學(xué)微積分；線代計(jì)算機(jī)模擬3計(jì)算機(jī)；運(yùn)籌學(xué)計(jì)算機(jī)編程7計(jì)算機(jī)編程2計(jì)算機(jī)預(yù)測(cè)理論2運(yùn)籌學(xué)應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)3運(yùn)籌學(xué)；計(jì)算機(jī)微積分；線代課程情況表建立課程與課程類別的關(guān)聯(lián)表：類別數(shù)學(xué)計(jì)算機(jī)運(yùn)籌學(xué)課程微積分線代優(yōu)化結(jié)構(gòu)統(tǒng)計(jì)模擬編程預(yù)測(cè)實(shí)驗(yàn)需求量則得0－1規(guī)劃模型：但要注意某些課程需要其它的先修課程，需使用表達(dá)式表達(dá)解編號(hào)名稱

先修課要求微積分

線性代數(shù)

最優(yōu)化

微積分；線代

數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)編程

應(yīng)用統(tǒng)計(jì)

微積分；線代

計(jì)算機(jī)模擬

計(jì)算機(jī)編程7計(jì)算機(jī)編程

預(yù)測(cè)理論

應(yīng)用統(tǒng)計(jì)9數(shù)學(xué)實(shí)驗(yàn)

微積分；線代課程情況表即：若x3=1，則必須有x1=x2=1課程總數(shù)類別（需求）限制先修要求注意表述方法！例15

一個(gè)生產(chǎn)問(wèn)題，有關(guān)數(shù)據(jù)如表。問(wèn)如何安排生產(chǎn)可使總利潤(rùn)最大，產(chǎn)量之和最小。要求第二種原料用完。單位利潤(rùn)產(chǎn)品原料單耗甲乙總量解設(shè)為甲，乙的產(chǎn)量則雙目標(biāo)規(guī)劃模型一般形式：矛盾的六、線性多目標(biāo)規(guī)劃模型化成單目標(biāo)規(guī)劃模型化法一或化法二

為目標(biāo)權(quán)重或偏好系數(shù)。

均可看成參數(shù)，對(duì)不同的參數(shù)值求出最優(yōu)解，然后加以討論，選出滿意解。例15中，要求利潤(rùn)最大，同時(shí)產(chǎn)量之和最小，這種目標(biāo)稱為理想目標(biāo)。這些目標(biāo)往往是相互矛盾的，不可能同時(shí)達(dá)到最優(yōu)。更現(xiàn)實(shí)的做法是：給出目標(biāo)值，將理想目標(biāo)轉(zhuǎn)化為現(xiàn)實(shí)目標(biāo)，求出盡量達(dá)到目標(biāo)值的生產(chǎn)方案。如要求：總利潤(rùn)產(chǎn)量之和把目標(biāo)函數(shù)轉(zhuǎn)化成了約束條件引入正負(fù)偏差變量、，將多目標(biāo)規(guī)劃模型轉(zhuǎn)化為目標(biāo)規(guī)劃模型。七、線性目標(biāo)規(guī)劃模型Min

要“”成立，只需min要“＝”成立，需min目標(biāo)規(guī)劃模型達(dá)成函數(shù)一般方法：目標(biāo)類型目標(biāo)規(guī)劃格式極小化注：1.對(duì)于硬約束“”,可不設(shè)正偏差變量，即直接取。對(duì)于“”，可直接取。2.關(guān)于優(yōu)先級(jí)問(wèn)題例如：上例中，目標(biāo)的重要性依次為：1°A,B兩種原料一定不能超過(guò)限量；2°原料B盡量用完；3°利潤(rùn)超過(guò)1000；4°產(chǎn)量之和盡量少。于是，達(dá)成函數(shù)可寫為：Min

???其中為優(yōu)先因子或Min

例某單位領(lǐng)導(dǎo)在考慮本單位職工的升級(jí)調(diào)資方案時(shí)，依次遵守以下規(guī)定：(1)不超過(guò)工資總額60000元；(2)每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)；(3)Ⅱ，Ⅲ級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%，且無(wú)越級(jí)提升；(4)Ⅲ級(jí)不足編制的人數(shù)可錄用新職工，又Ⅰ級(jí)的職工中有10%要退休。有關(guān)資料匯總于表1中，問(wèn)該領(lǐng)導(dǎo)應(yīng)如何擬訂一個(gè)滿意的方案。表1月解設(shè)x1、x2、x3分別表示提升到Ⅰ、Ⅱ級(jí)和錄用到Ⅲ級(jí)的新職工人數(shù)。對(duì)各目標(biāo)確定的優(yōu)先因子為：P1——不超過(guò)工資總額60000元；P2——每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)；P3——Ⅱ、Ⅲ級(jí)的升級(jí)面盡可能達(dá)到現(xiàn)有人數(shù)的20%。先分別建立各目標(biāo)約束。

P1:工資總額不超過(guò)60000元

2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d1—-d1+

=60000minP1d1+P2：每級(jí)的人數(shù)不超過(guò)定編規(guī)定的人數(shù)：對(duì)Ⅰ級(jí)有10(1-0.1)