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

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

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

一、一般的數(shù)學規(guī)劃模型二、數(shù)學規(guī)劃常見模型：1.運輸問題（例1，2）

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

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

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

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

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

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

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

為到的車流量，則流量守恒條件弧容量限制去掉去掉若不設v,則模型有四處需修改①②③④⑤⑥⑦如果源、匯不止一個時，建模方法類似?？稍黾右粋€虛擬源、虛擬匯化成單源單匯的問題。

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

、為流入、的量，

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

定義：（Euler跡、Euler環(huán)游、Euler圖）解：1。模擬圖：以頂點表陸地，以邊表橋，得4個頂點的模擬圖。2。問題等價于：能否有一條閉跡包含模擬圖的所有邊，即：模擬圖是Euler圖嗎？3。求解：假設圖G是Euler圖。因為閉跡是連通的，所以圖G也連通。又因為每個頂點既能到達也能離開，所以圖G的每個頂點度都是偶數(shù)。所以，歐拉在1736年得出結論：“七橋問題”是不可能的，同時開創(chuàng)了圖論的研究。含圖G的所有邊的跡，稱為Euler跡（如果此跡是閉跡，也叫Euler環(huán)游），把含有Euler閉跡（環(huán)游）的圖稱為Euler圖。如果一個圖G含有Euler閉跡，我們如何找到它呢？下面介紹一種尋找Euler圖中Euler閉跡的算法－Fleury算法Fleury算法（1）任取一個頂點，置；（2）假定跡已經(jīng)選出，則用下列方法從中選出：a）與關聯(lián)；b）除非沒有其它的邊可選擇，不是

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

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

Hamilton圈和旅行售貨商問題

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

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

甲乙丙丁戊仰泳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)結果如下四、生產(chǎn)活動問題(分段函數(shù)、矛盾約束等的處理方法)資源產(chǎn)品單耗資源量單位利潤例6問如何安排生產(chǎn)使總利潤最大。解設表示第種產(chǎn)品的產(chǎn)量，則資源分配問題分段函數(shù)問題（有關的收益問題）假設例中＝單位收益－單位成本（可變成本）若還要考慮固定成本（如：機器、廠房等）于是，需要引入0—1變量：設Lj

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

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

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

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

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

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

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

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

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

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

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

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

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

同前例

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

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

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

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

先修課要求微積分

線性代數(shù)

最優(yōu)化

微積分；線代

數(shù)據(jù)結構

計算機編程

應用統(tǒng)計

微積分；線代

計算機模擬

計算機編程7計算機編程

預測理論

應用統(tǒng)計9數(shù)學實驗

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

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

為目標權重或偏好系數(shù)。

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

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

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

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

P1:工資總額不超過60000元

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

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