數(shù)學(xué)建模-投資收益、加工次序及其他

第二講投資收益、加工次序及其他§1投資收益問題問題的提出一個(gè)公司有22億元資金可用來(lái)投資，現(xiàn)有6個(gè)項(xiàng)目可供選擇，各項(xiàng)目所需投資金額和預(yù)計(jì)年收益如下表所示：表1項(xiàng)目123456投資（億元）526468收益（億元）0.50.40.60.50.91問應(yīng)選擇那幾個(gè)項(xiàng)目投資，使公司收益最大？2、模型的建立記顯然，投資總金額滿足而預(yù)計(jì)年總收益滿足從而數(shù)學(xué)模型為：3、模型的求解由于共有個(gè)項(xiàng)目，對(duì)每一項(xiàng)目都有投資和不投資兩種選擇，因此總共有種選擇。窮舉法分枝定界法*1計(jì)算每個(gè)項(xiàng)目的收益率：項(xiàng)目1

2

3

4

56

投資（億元）526468收益（億元）0.50.40.60.50.91收益率0.10.20.10.1250.150.125放寬約束條件，允許取正實(shí)數(shù)值，優(yōu)先選擇收益率高的項(xiàng)目，得到兩組最優(yōu)解：對(duì)應(yīng)的年收益為，對(duì)應(yīng)的年收益為由于我們放寬了必須取值的約束，所以上述最優(yōu)收益超過實(shí)際的最優(yōu)收益。1）先松弛，求得最優(yōu)解；2）分支定界在分支求解的過程中，會(huì)出現(xiàn)各變量均取值的可行解，這些解對(duì)應(yīng)的收益值之最大者，可定為原問題最優(yōu)收益的一個(gè)候選者，同時(shí)，分支求得的最優(yōu)解（不管變量是否取分?jǐn)?shù)值）表明：該最優(yōu)值是分支所含有的一切可行解的收益的上界。這一過程稱為定界。3）當(dāng)分支進(jìn)行到某一步時(shí)發(fā)現(xiàn)某一分支的上界不大于已發(fā)現(xiàn)的候選者，或繼續(xù)進(jìn)行找不到可行解時(shí)，這一支的分支可不必進(jìn)行下去，這一過程叫做剪支。分支定界法就是不斷采用分支、定界、剪支的過程，最終得到最優(yōu)解?！?加工次序問題1、問題的提出有10個(gè)工件在一臺(tái)機(jī)床上加工。在這10個(gè)工件中，有些工件必須在另一些工件加工完畢之后才能加工，這些必須加工的工件稱為緊前工件。按規(guī)定，在工件運(yùn)抵后266小時(shí)內(nèi)應(yīng)加工完畢，否則要支付一定的賠款，賠款數(shù)正比于延誤的時(shí)間，各工件每延誤1小時(shí)的賠款額不同。表2列出了各工件所需的加工時(shí)間、加工次序要求和每延誤1小時(shí)的賠款額。表2工件號(hào)12345678910加工時(shí)間20282545161260102030緊前工件387/1,2,6843591小時(shí)賠款12141510101112867設(shè)由于機(jī)床的故障，10個(gè)工件運(yùn)抵之后T小時(shí)才開始加工。要求安排一個(gè)加工次序，使得支付的賠款最少。模型的建立繪制網(wǎng)絡(luò)圖用圓圈表示加工一個(gè)工件；用箭頭表示加工的次序要求，即箭頭指向的圓圈內(nèi)的工件必須在箭尾圓圈內(nèi)的工件加工完畢之后方能開始加工。ii)優(yōu)化目標(biāo)假設(shè)兩個(gè)工件加工之間，機(jī)床做準(zhǔn)備的時(shí)間可以忽略。第個(gè)工件的加工時(shí)間，第個(gè)工件延誤1小時(shí)的賠款數(shù)，設(shè)是的一個(gè)排列，滿足網(wǎng)絡(luò)圖描述的加工次序，稱為可行的加工次序。由于開工延誤了小時(shí)，第個(gè)工件的完工時(shí)間為則對(duì)于可行的加工次序，賠款總額為Total=問題歸結(jié)為求可行的加工次序，使得賠款總額Total達(dá)到最小。§3兩輛平板車的裝載問題問題的提出有兩輛長(zhǎng)，載重的鐵路平板車，要裝載7種不同規(guī)格的貨物箱。這7種箱子的厚度、重量、庫(kù)存量如表3所示。表3箱類型厚度48.75261.37248.75264重量2310.5421庫(kù)存量（個(gè)）8796648若各種箱子的高度和寬度均符合鐵路運(yùn)輸?shù)臉?biāo)準(zhǔn)（不妨設(shè)它們的寬度和高度均為相同的），在每輛車上裝載的貨物箱的厚度和不超出，總重量不超過的前提下，應(yīng)如何裝載，使得平板車?yán)速M(fèi)的空間最??？當(dāng)?shù)罔F路部門還有一個(gè)附加的規(guī)定：第三種箱子裝車的厚度和不得超過模型的建立假設(shè)裝載時(shí)相鄰兩箱貨物之間的間隙可以忽略。記第種貨物箱的厚度，第種貨物箱的重量，第種貨物箱的庫(kù)存量，分別表示第種貨物箱在兩輛平板車上的裝載數(shù)。車輛浪費(fèi)的空間最小，等價(jià)于使裝載貨物箱的厚度和達(dá)到最大。記裝載在兩輛車上貨物箱的厚度和，則目標(biāo)函數(shù)依據(jù)題目的要求，應(yīng)滿足如下約束條件：裝載空間的限制為載重量的限制為貨物箱庫(kù)存量的限制為第三種貨物箱的限制可表述為綜上所述，兩輛平板車的裝載問題，可以歸結(jié)為如下的整數(shù)規(guī)劃模型：其中為非負(fù)整數(shù)?！?截?cái)嗲懈?、問題的提出某些工業(yè)部門（如貴重石材加工等）采用截?cái)嗲懈畹募庸し绞?。這里“截?cái)嗲懈睢笔侵笇⑽矬w沿某個(gè)切割平面分成兩部分。從一個(gè)長(zhǎng)方體中加工出一個(gè)已知尺寸、位置預(yù)定的長(zhǎng)方體（這兩個(gè)長(zhǎng)方體的對(duì)應(yīng)表面是平行的），通常要經(jīng)過6次截?cái)嗲懈?。設(shè)水平切割單位面積的費(fèi)用是垂直切割單位面積費(fèi)用的r倍，且當(dāng)先后兩次垂直切割的平面(不管它們之間是否穿插水平切割)不平行時(shí)，因調(diào)整刀具需額外費(fèi)用e。試為這些部門設(shè)計(jì)一種安排各面加工次序（稱“切割方式”）的方法，使加工費(fèi)用最少。（由工藝要求，與水平工作臺(tái)接觸的長(zhǎng)方體底面是事先指定的）詳細(xì)要求如下：（1）需考慮的不同切割方式的總數(shù)。（2）給出上述問題的數(shù)學(xué)模型和求解方法。（3）試對(duì)某部門用的如下準(zhǔn)則作出評(píng)價(jià)：每次選擇一個(gè)加工費(fèi)用最少的待切割面進(jìn)行切割。（4）對(duì)于e=0的情形有無(wú)簡(jiǎn)明的優(yōu)化準(zhǔn)則。（5）用以下實(shí)例驗(yàn)證你的方法：待加工長(zhǎng)方體和成品長(zhǎng)方體的長(zhǎng)、寬、高分別為10、14.5、19和3、2、4，二者左側(cè)面、正面、底面之間的距離分別為6、7、9（單位均為厘米）。垂直切割費(fèi)用為每平方厘米1元，r和e的數(shù)據(jù)有以下4組：a.r=1,e=0;b.r=1.5,e=0;c.r=8,e=0;d.r=1.5;2<=e<=15.2、模型的假設(shè)及說(shuō)明⒈每次切割將物體分成兩部分，并把切除部分立即拿走。⒉切割加工具有水平切割和垂直切割兩種專用刀具。⒊第一次垂直切割時(shí)，無(wú)需調(diào)整刀具。⒋假設(shè)最后一次切割底面。⒌在切割過程中物體不能翻轉(zhuǎn)、旋轉(zhuǎn)，否則否則垂直切割與水平切割可以互相轉(zhuǎn)化。3、基本符號(hào)及有關(guān)概念的說(shuō)明表示成品長(zhǎng)方形的左、右、前、后、上、下表面；:表示對(duì)第面進(jìn)行操作；:表示成品長(zhǎng)方體面i與原長(zhǎng)方體相應(yīng)面之間的距離(單位：cm)；A、B、C:分別表示原長(zhǎng)方體的長(zhǎng)、寬、高(單位：cm)；:垂直切割單位面積的費(fèi)用(單位：元/)；:水平切割單位面積與垂直切割單位面積費(fèi)用的比值；:垂直切割每調(diào)整一次刀具所花的費(fèi)用(單位：元/次)；:當(dāng)時(shí)，采用最優(yōu)切割方式進(jìn)行切割所需費(fèi)用；:當(dāng)e=0時(shí)，采用最優(yōu)切割方式調(diào)整刀具的次數(shù)。4、模型的建立因最后一次切割是切割底面，當(dāng)把不同的切割方式當(dāng)把不同的切割方式僅僅理解為的不同排列方式時(shí)，則切割方式總數(shù)為。i)刀具調(diào)整費(fèi)用e=0的情形 在e=0的情形下，由于調(diào)整刀具的費(fèi)用為0，因此若能找到一種切割方式，使各個(gè)切面的有效切割面積之和最小(此時(shí)費(fèi)用最小)，則此方式即為最優(yōu)切割。定理1當(dāng)采取最優(yōu)切割方式進(jìn)行切割時(shí)，⑴若滿足且時(shí)，切割優(yōu)于的充要條件為；⑵若滿足而時(shí)，切割優(yōu)于的充要條件為；證明：設(shè)X表示截?cái)嗲懈詈笏Ｏ碌拈L(zhǎng)方體待切割面的集合，a,b,c表示截?cái)嗲懈詈笫Ｏ碌拈L(zhǎng)方體的長(zhǎng)、寬、高，設(shè)f(X,a,b,c)出發(fā)，對(duì)待切割的表面采取最優(yōu)的切割方式，將X中所有面切割完畢所需費(fèi)用，f(X,a,b,c,i)表示由狀態(tài)(X,a,b,c)出發(fā)，先進(jìn)行切割，再以最優(yōu)的切割方式將中所有面切割完畢的費(fèi)用，其中表示由狀態(tài)出發(fā)，相繼進(jìn)行切割，切割，再以最優(yōu)切割方式對(duì)中所有面切割完畢的費(fèi)用，則 ⑴當(dāng)時(shí)故從而得到對(duì)左、右兩側(cè)進(jìn)行連續(xù)切割時(shí)，與先后順序無(wú)關(guān)。同理可得出對(duì)前后兩面進(jìn)行連續(xù)切割亦與先后順序無(wú)關(guān)。⑵當(dāng)i=1,2且j=3,4時(shí)同理，于是 故優(yōu)于的充分必要條件為⑶當(dāng)i=1,2且j=5時(shí)而故故優(yōu)于的充分必要條件為，即同理，i=3,4且j=5時(shí)，優(yōu)于的充分必要條件為綜合⑴⑵⑶知定理1得證。利用定理1，我們得到如下的簡(jiǎn)明優(yōu)化準(zhǔn)則：優(yōu)化準(zhǔn)則：設(shè)分別表示成品長(zhǎng)方體與原材料長(zhǎng)方體對(duì)應(yīng)的左側(cè)面、右側(cè)面、前面、后面、上面、下面之間的距離。將記成，再將它們按由小到大的順序排成：則最優(yōu)切割方式為：ii)、調(diào)整刀具費(fèi)用情形當(dāng)時(shí)，由優(yōu)化準(zhǔn)則可以很容易地找出最優(yōu)切割方式，計(jì)算出最優(yōu)切割方式的費(fèi)用及調(diào)整刀具次數(shù)K，顯然調(diào)整刀具次數(shù)K只可能為1，2，3中的某一個(gè)。下面，我們根據(jù)K的取值情況利用e=0時(shí)優(yōu)化準(zhǔn)則，來(lái)建立的優(yōu)化數(shù)學(xué)模型。首先，根據(jù)調(diào)整刀具次數(shù)來(lái)把所有切割方式分成三類，對(duì)同一類，我們把切割方式的費(fèi)用分別進(jìn)行排序。用表示e=0時(shí)調(diào)整刀具次數(shù)為i的切割費(fèi)用的排序結(jié)果，其中i=1，2，3。即于是，當(dāng)時(shí)，問題轉(zhuǎn)化為計(jì)算，此時(shí)最優(yōu)切割方式的費(fèi)用為，如何尋找成為問題的焦點(diǎn)。定理2：若e=0時(shí)最優(yōu)切割方式的調(diào)整刀具次數(shù)為K=1，則當(dāng)時(shí)最優(yōu)切割方式的費(fèi)用為。證明：當(dāng)K=1時(shí)，有，從而對(duì)所有i,j均有，i=1,2,3;j=1,2,…,ki.當(dāng)e0時(shí)，顯然有故最優(yōu)切割方式的費(fèi)用為，可見當(dāng)K=1時(shí)，e0時(shí)的最優(yōu)切割方式與e=0時(shí)的最優(yōu)切割方式相同。證畢。定理3：⑴若e=0時(shí)，最優(yōu)切割方式的調(diào)整刀具次數(shù)為K=2，則當(dāng)時(shí)，最優(yōu)切割方式的費(fèi)用為。⑵若e=0時(shí)，最優(yōu)切割方式的調(diào)整刀具次數(shù)為K=3，則當(dāng)時(shí)，最優(yōu)切割方式的費(fèi)用為。證明：⑴當(dāng)K=2時(shí)，由的定義有，從而故最優(yōu)方式切割費(fèi)用為=⑵當(dāng)K=3時(shí)，同理可證。證畢推論：⑴無(wú)論K為何值，要求出最優(yōu)切割方式的費(fèi)用，最多只需計(jì)算和⑵當(dāng)K=2時(shí)若，則最優(yōu)切割方式的費(fèi)用為若，則最優(yōu)切割方式的費(fèi)用為⑶當(dāng)K=3時(shí)若，則最優(yōu)切割方式的費(fèi)用為若，則最優(yōu)切割方式的費(fèi)用為若，則最優(yōu)切割方式的費(fèi)用為定理4：（最優(yōu)切割方式的必要條件）設(shè)分別表示原材料長(zhǎng)方體與成品長(zhǎng)方體左側(cè)面、右側(cè)面之間的距離，表示切割左、右側(cè)面，則在任何最優(yōu)切割方式中，（或）一定是按（或）從大到小的順序進(jìn)行切割，換句話說(shuō)，若（或），則最優(yōu)切割方式一定是以（或）的形式出現(xiàn)。證明：我們不考慮為相鄰切割方式的情形，因?yàn)楫?dāng)以相鄰形式出現(xiàn)時(shí)，由于切割平行，所以對(duì)換所得到的切割方式與對(duì)換前的切割方式是同一種切割方式。（反證法）假設(shè)存在某個(gè)最優(yōu)切割方式，其中，對(duì)換得到切割方式顯然的調(diào)整刀具的次數(shù)相同。用表示采用切割方式所需的費(fèi)用，為了證明方便，不妨設(shè)之間穿插了一個(gè)切割（i=3,4）設(shè)按方式T進(jìn)行到時(shí)的狀態(tài)為(X,a,b,c)（符號(hào)定義見定理1的證明）則同理由題設(shè)知，，即當(dāng)之間穿插或進(jìn)行幾個(gè)切割時(shí)，同理可證仍然成立，這說(shuō)明切割方式優(yōu)于切割方式，與假設(shè)切割方式T為最優(yōu)的切割方式相矛盾。證畢。下面，我們利用前面的結(jié)果，通過建立定理5和定理6，可顯著地減少搜索次數(shù)，事實(shí)上，在最壞的情形，也只需進(jìn)行6次搜索，有時(shí)，可一次得到。設(shè)對(duì)應(yīng)于的面的切割，i=1，2，3，4令對(duì)應(yīng)于的面的切割，即對(duì)應(yīng)于的面的切割，即定理5：當(dāng)時(shí)（即K=2），在從切割方式中抽去和的情況下：i)若則所對(duì)應(yīng)的切割方余下切割的排列為ii)若則所對(duì)應(yīng)的切割方余下切割的排列為iii)若則所對(duì)應(yīng)的切割方余下切割的排列為或證明：因?yàn)樗鶎?duì)應(yīng)的切割方式的調(diào)整刀具的次數(shù)為1，而水平切割不影響刀具調(diào)整的次數(shù)，所以在抽去后，所對(duì)應(yīng)的切割方式余下切割的排列，其調(diào)整刀具次數(shù)仍然為1，從而只可能為⑴⑵用表示按進(jìn)行切割所需費(fèi)用，則若即當(dāng)時(shí)，將優(yōu)于，i)得證。同理可證得ii),iii)。證畢。定理6：若時(shí)（即K=3），在從所有切割方式中抽去和的情況下：i)若則所對(duì)應(yīng)的切割方余下切割的排列為ii)若則所對(duì)應(yīng)的切割方余下切割的排列為iii)若則所對(duì)應(yīng)的切割方余下切割的排列為或仿定理5，同樣可證明之。由定理1-6，我們歸納出如下算法：由e=0的優(yōu)化準(zhǔn)則得到最優(yōu)切割方式；計(jì)算K值，賦初值,,若K=1：計(jì)算，轉(zhuǎn)向第6步；若K=2：轉(zhuǎn)向第4步；3．⑴計(jì)算，若1-a)若則按切割方式計(jì)算，轉(zhuǎn)向第4步；1-b)若則按切割方式計(jì)算，轉(zhuǎn)向第4步；1-c)比較：i)ii)iii)取，轉(zhuǎn)向第4步⑵2-a)若則按切割方式計(jì)算，轉(zhuǎn)向第4步；2-b)若