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

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

2

3

4

56

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