平板車裝貨問題

兩輛鐵路平板車裝貨問題的討論摘要本文將鐵路平板車的裝貨問題抽象簡化為整數(shù)線性規(guī)劃問題，經(jīng)過合理假設(shè)，建立了優(yōu)化問題模型，然后利用matlab軟件求出一組最優(yōu)解，考慮到變量較多以及變量權(quán)值的特殊（如C2、C6長度相等）我們猜想可能存在多組解，我們再參考matlab求出的一組最優(yōu)解，根據(jù)C語言編譯程序求得所有符合條件的60組最優(yōu)解，經(jīng)過去重后最終得到30組最優(yōu)解。本文鑒于題中給出的C5,C6,C7類的包裝箱的總數(shù)的限制條件“這類箱子所占的空間厚度）不能超過302.7cm”存在兩種理解方式，對該問題分兩種情況討論，分別建立模型得出最優(yōu)方案。第一種理解認(rèn)為對每輛平板車而言C5,C6,C7類的包裝箱所占的空間（厚度）不能超過302.7cm。對此我們建立了整數(shù)線性規(guī)劃模型一并用matlab求得最優(yōu)解為C1,C2……C6,C7類包裝箱的數(shù)量為得到了包裝箱所浪費的最小空間為0.6cm,參考此最優(yōu)解進而用C語言求出最終6組最優(yōu)解（詳見表一）。第二種理解認(rèn)為兩輛平板車C5,C6,C7類的包裝箱所占的空間（厚度）累計不能超過302.7cm。對此我們建立了整數(shù)線性規(guī)劃模型二并用matlab求得最優(yōu)解為C1,C2……C6,C7類包裝箱的數(shù)量為（3，5，0，5，2，3，0，5，2，9，1，1，0，0），得到了包裝箱所浪費最小空間為0cm，參考此最優(yōu)解進而用C語言求出最終30組最優(yōu)解（詳見表二）關(guān)鍵詞：整數(shù)線性規(guī)劃分類討論最優(yōu)解一、問題重述有七種規(guī)格的包裝箱要裝到兩輛鐵路平板車上去。包裝箱的寬和高是一樣的，但厚度（t，以厘米計）及重量（w，以公斤計）是不同的。下表給出了每種包裝箱的厚度、重量以及數(shù)量。每輛平板車有1020cm的地方可用來裝包裝箱（像面包片那樣），載重為40噸。由于當(dāng)?shù)刎涍\的限制，對C5,C6,C7類的包裝箱的總數(shù)有一個特別的限制：這類箱子所占的空間（厚度）不能超過302.7cm（分兩輛車和一輛車兩種情況討論。試把包裝箱裝到平板車上去使得浪費的空間最小。C1C2C3C4C5C6C7t(cm)48.75261.372.048.752.064.0w(kg)2000300010005000400020001000x件數(shù)8796648問題分析對于本題目，由于包裝箱的寬和高是一樣，但厚度（t,cm）及重量（w,kg）是不同的，所以在解決此問題時暫時忽略包裝箱的寬和高，而僅僅慮包裝箱厚度、重量以及數(shù)量。題中對每輛平板車的容量（10.2m），載重量（40t）以及C5,C6,C7類的包裝箱的總數(shù)有限制（厚度不能超過302.7cm）從而得出約束條件。并在此約束條件限制下使得浪費的空間最小即求目標(biāo)函數(shù)的的最小值，并且平板車上裝的包裝箱件數(shù)為整數(shù)，所以本問題為線性規(guī)劃中的整數(shù)規(guī)劃問題。對題中C5,C6,C7類的包裝箱的總數(shù)的限制“這類箱子所占的空間（厚度）不能超過302.7cm”，我們認(rèn)為此處題目存在歧義可以有兩種理解方式：（1）對每輛平板車而言C5,C6,C7類的包裝箱所占的空間（厚度）不能超過302.7cm；（2）對一次貨運而言，即兩輛平板車C5,C6,C7類的包裝箱所占的空間（厚度）累計不能超過302.7cm。所以對該問題我們分兩種情況討論，分別建立模型，并利用matlab軟件求出最優(yōu)解?？紤]到變量較多以及變量權(quán)值的特殊（如C2、C6長度相等）我們猜想可能存在多組解。我們參考matlab求出的一組最優(yōu)解，根據(jù)C語言編譯程序求得所有符合條件的60組最優(yōu)解，經(jīng)過去重后最終得到30組最優(yōu)解。三、模型假設(shè)假設(shè)包裝箱之間空隙可忽略不計

假設(shè)鐵路平板車只能放一排包裝箱，不可疊加兩輛平板車完全相同，不考慮平板車前后次序不考慮在同一平板車上相同規(guī)格包裝箱排列次序四、符號系統(tǒng)f浪費的空間cijcij第i種包裝箱裝在第j輛平板車上數(shù)目ti第i種包裝箱的厚度Wi第i種包裝箱的質(zhì)量第i種包裝箱的數(shù)目五、模型建立與求解對本題中C5,C6,C7類的包裝箱的總數(shù)的限制“這類箱子所占的空間（厚度）不能超過302.7cm,我們認(rèn)為此處題目存在歧義可以有兩種理解方式：對每輛平板車而言C5,C6,C7類的包裝箱所占的空間（厚度）不能超過302.7cm；對一次貨運而言，即兩輛平板車C5,C6,C7類的包裝箱所占的空間（厚度）累計不能超過302.7cm。對此我們分別建立了兩種整數(shù)規(guī)劃模型。5.1模型一的建立與求解假設(shè)包裝箱之間空隙可忽略不計，鐵路平板車只能放一排包裝箱，不可疊加，且不考慮平板車前后次序和同一平板車上相同規(guī)格包裝箱排列次序。此時，設(shè)第i種包裝箱裝在第j輛平板車上數(shù)目Ci,則平板車?yán)速M的空間minf=2040-僉7Ct。ijijij=1i=1由于兩輛平板車長度均為1020cm，每輛平板車上的包裝箱總厚度不應(yīng)超過1020cm,據(jù)此建立第一個約束條件：1020-工Ct>0j=1,2ijii=1由于當(dāng)?shù)刎涍\的限制，對C5,C6,C7類的包裝箱的總數(shù)有一個特別的限制：對每輛平板車而言C5,C6,C7類的包裝箱所占的空間（厚度）不能超過302.7cm。據(jù)此建立第二個約束條件：工Ct<302.7j=1,2ijii=5由于兩輛平板車載重均為40000Kg，每輛平板車上包裝箱總重量不應(yīng)超過40000kg，據(jù)此建立第三個約束條件：工CW<40000j=1,2ijii=1由于七種包裝箱的數(shù)目在提供的包裝箱件數(shù)xi的容許的范圍內(nèi)，并且包裝箱在每輛平板車上的數(shù)目為非負(fù)整數(shù)，據(jù)此建立第四個約束條件0<￡C..<x.j=1,2ijij=1根據(jù)以上分析可建立以下整數(shù)線性規(guī)劃數(shù)學(xué)模型：

minf=2040-昱藝minf=2040-昱藝Cijxij=1i=11020-工Cx>0ijiji=1工C.W.<302.7ijis.t.<i=5工C.W.<40000jii=10<昱C..<x.iji.=15.1.2模型一的求解根據(jù)整數(shù)規(guī)劃模型一，我們用matlab求得最優(yōu)解為兩輛車裝運C1,C2,...,C7類包裝箱的數(shù)量分別為（6，2，6，0，0，0，4；1，5，2，5，1，1，2），剩余厚度為0.6cm?？紤]到matlab求解整數(shù)規(guī)劃只能求出一組最優(yōu)解的局限性，我們進而用C語言編程求出了所有符合條件的12組最優(yōu)解。因為不考慮兩車先后次序，我們又用對結(jié)果去重，最終得到6組最優(yōu)解（詳見下表）。表一：序號C11C21C31C41C51C61C71C12C22C32C42C52C62C721052521262600042152511262600043152511262600044242502262600045242512262600046232503262600045.2模型二的建立與求解5.2.1模型二的建立

模型二中，除了第二條約束條件變?yōu)閮奢v平板車C5,C6,C7類的包裝箱所占的空間（厚度）累計不能超過302.7cm，其它均和模型一相同。約束條件二為：茫7Ct<302.7。ijij=1i=5可以建立如下整數(shù)線性規(guī)劃模型：minf=minf=2040―》為Cijtij=1ij=1i=11020-工Ct>0ijii=1昱藝Ct<302.7ijis.t.<j=1i=1工C.W.<40000jii=10<》C..<x.ijij=1,2j=1,2i=1,2...,7j=15.2.2模型二的求解根據(jù)整數(shù)規(guī)劃模型二，用matlab求得最優(yōu)解為兩輛車裝運C1,C2,...,C7類包裝箱的數(shù)量分別為（3,2,9,1,3,0,0;5,5,0,5,0,3,0）,剩余厚度為0.6cm。參考matlab求得的一組最優(yōu)解，我們又用C語言編程求得所有符合條件的54組最優(yōu)解，經(jīng)過去重后最終得到20組最優(yōu)解（詳見下表）。表二：序號C11C21C31C41C51C61C71C12C22C32C42C52C62C72105640208232310206640108132320306900308106300407640008032330507900208006310

614433307353000715433207253010816433107153020924432306353100102505330629100011254322062531101226432106153120132743200605313014309132057050101531913105605020163291300550503017344313053532001835052305291100193543120525321020360522051911102136431105153220223705210509112023374310050532302440533304743000254091220470511026415332046430102741912104605120284253310454302029429120045051303043533004443030六、模型分析本文針對兩輛鐵路平板車裝運包裝箱的問題，在合理假設(shè)后建立裝貨建立整數(shù)規(guī)劃模型，通過matlab分析得出一組最優(yōu)分配方式，利用C語言編程得到第一種情況下所有滿足最小浪費空間為0.6m的分配方式共6組、第二種情況下所有滿足最小浪費空間為0m的分配方式共30組。（程序及數(shù)據(jù)輸出見附錄1、2）七、模型推廣面考慮實際生活中貨車的安全問題，實際生活中還有其他因素比如兩輛貨車在不同情況下的載重、浪費空間之差