第二講 線性規(guī)劃模型

第二講線性規(guī)劃模型統(tǒng)計與應用數(shù)學系張耀峰Themodeloflinearprogramming1/31/20231第二講線性規(guī)劃模型1.1優(yōu)化的思想1.2什么是線性規(guī)劃模型1.3如何使用Lingo軟件求解線性規(guī)劃問題1.4案例解析1/31/202321.1優(yōu)化的思想1/31/20233燒水小明同學，燒一壺水要8分鐘，灌開水要1分鐘，取牛奶和報紙要5分鐘（不能間斷），整理書包要6分鐘（可間斷），為了盡快做完這些事，怎樣安排才能使時間最少？最少需要幾分鐘？例1、如何安排早上的時間？取牛奶和報紙收拾書包灌水收拾書包5891201/31/20234例2、怎么排隊才合理呢？

碼頭上現(xiàn)在同時有3艘貨船需要卸貨，但是只能一條一條地卸貨，并且每艘船卸貨所需的時間各不相同，分別為4小時、8小時和1小時。按照怎樣的順序卸貨能使3艘貨船等候的總時間最少呢？

1/31/20235方案卸貨順序船1的等候時間船2的等候時間船3的等候時間總的等候時間1船1—船2—船388+48+4+1332船1—船3—船288+1+48+1303船2—船1—船34+844+8+1294船2—船3—船14+1+844+1225船3—船1—船21+81+8+41236船3—船2—船11+4+81+41191/31/202361.2什么是線性規(guī)劃模型1/31/20237例3運輸問題1/31/20238解：設A1,A2調(diào)運到三個糧站的大米分別為x11，x12，

x13，

x21，

x22，

x23噸。題設量可總到下表：84庫存量x23x22x21A2542需要量x13x12x11A1B3B2B1糧庫糧站距離及運量121224308241/31/20239結(jié)合存量限制和需量限制得數(shù)學模型：目標函數(shù)約束條件決策變量1/31/2023101.3如何使用Lingo軟件求解線性規(guī)劃問題1/31/202311程序編寫１model:min=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23;x11+x12+x13<4;x21+x22+x23<8;x11+x21>2;x12+x22>4;x13+x23>5;end1/31/202312運行結(jié)果

Globaloptimalsolutionfound.Objectivevalue:160.0000Totalsolveriterations:5VariableValueReducedCostX112.0000000.000000X120.00000028.00000X132.0000000.000000X210.0000002.000000X224.0000000.000000X233.0000000.000000RowSlackorSurplusDualPrice1160.0000-1.00000020.00000016.0000031.0000000.00000040.000000-28.0000050.000000-12.0000060.000000-24.000001/31/202313

例4生產(chǎn)計劃問題某工廠計劃安排生產(chǎn)Ⅰ，Ⅱ兩種產(chǎn)品，已知每種單位產(chǎn)品的利潤，生產(chǎn)單位產(chǎn)品所需設備臺時及A,B兩種原材料的消耗，現(xiàn)有原材料和設備臺時的定額如表所示，問：１）怎么安排生產(chǎn)使得工廠獲利最大？２）產(chǎn)品Ⅰ的單位利潤降低到1.8萬元，要不要改變生產(chǎn)計劃，如果降低到1萬元呢？３）產(chǎn)品Ⅱ的單位利潤增大到5萬，要不要改變生產(chǎn)計劃４）如果產(chǎn)品Ⅰ，Ⅱ的單位利潤同時降低了1萬元，要不要改變生產(chǎn)計劃？產(chǎn)品Ⅰ產(chǎn)品Ⅱ最大資源量設備128臺時原材料A4016kg原材料B0412kg單位產(chǎn)品利潤231/31/2023141/31/202315程序編寫model:title生產(chǎn)計劃問題;[maxf]max=2*x1+3*x2;[A]x1+2*x2<8;[B]4*x1<16;[TIME]4*x2<12;END1/31/202316運行結(jié)果ModelTitle:生產(chǎn)計劃問題VariableValueReducedCostX14.0000000.000000X22.0000000.000000RowSlackorSurplusDualPriceMAXF14.000001.000000A0.0000001.500000B0.0000000.1250000TIME4.0000000.000000

對問題1，安排是生產(chǎn)產(chǎn)品Ⅰ4單位，產(chǎn)品Ⅱ2單位，最大盈利為14萬元。1/31/202317線性模型－敏感性分析要使用敏感性分析必須要在這里選擇Prices&Ranges然后保存退出路徑：LINGO︱Options︱GeneralSolver(通用求解程序)選項卡1/31/202318要調(diào)出敏感性分析的結(jié)果，必須先求解后再在程序窗口下點擊LINGO｜Range，1/31/202319Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRanges

CurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12.000000INFINITY0.5000000X23.0000001.0000003.000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8.0000002.0000004.000000B16.0000016.000008.000000TIME12.00000INFINITY4.000000

當前變量系數(shù)允許增加量允許減少量1/31/202320對問題4，因為兩個系數(shù)同時改變了，所以只有更改程序的數(shù)據(jù)，重新運行得：不改變生產(chǎn)計劃，但是最大利潤降低到6萬元.

對問題2，產(chǎn)品Ⅰ的單位利潤降低到1.8萬元，在（1.5，∞）之間，所以不改變生產(chǎn)計劃。如果降低到1萬元，不在（1.5，∞）內(nèi)，要改變生產(chǎn)計劃。在程序中將目標函數(shù)的系數(shù)“2”改為“1”，可得新的計劃為安排是生產(chǎn)產(chǎn)品Ⅰ2單位，產(chǎn)品Ⅱ3單位，最大盈利為11萬元.對問題3，要改變生產(chǎn)計劃，更改程序得新計劃為生產(chǎn)產(chǎn)品Ⅰ2單位，產(chǎn)品Ⅱ3單位，最大盈利為19萬元.1/31/202321例5加工奶制品的生產(chǎn)計劃1桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤50桶牛奶時間480小時至多加工100公斤A1

制訂生產(chǎn)計劃，使每天獲利最大

35元可買到1桶牛奶，買嗎？若買，每天最多買多少?可聘用臨時工人，付出的工資最多是每小時幾元?

A1的獲利增加到30元/公斤，應否改變生產(chǎn)計劃？每天：1/31/2023221桶牛奶3公斤A1

12小時8小時4公斤A2

或獲利24元/公斤獲利16元/公斤x1桶牛奶生產(chǎn)A1

x2桶牛奶生產(chǎn)A2

獲利24×3x1

獲利16×4x2

原料供應

勞動時間

加工能力

決策變量

目標函數(shù)

每天獲利約束條件非負約束

線性規(guī)劃模型(LP)時間480小時至多加工100公斤A1

50桶牛奶每天1/31/202323模型求解

OBJECTIVEFUNCTIONVALUE

1)3360.000

VARIABLEVALUEREDUCEDCOST

X120.0000000.000000

X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=220桶牛奶生產(chǎn)A1,30桶生產(chǎn)A2，利潤3360元。max=72*x1+64*x2;x1+x2<50;12*x1+8*x2<480;3*x1<100;1/31/202324模型求解

reducedcost值表示當該非基變量增加一個單位時（其他非基變量保持不變）目標函數(shù)減少的量(對max型問題)

OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=21/31/202325OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000

ROW

SLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.0000004)40.0000000.000000原料無剩余時間無剩余加工能力剩余40max72x1+64x2st2）x1+x2<503）12x1+8x2<4804）3x1<100end三種資源結(jié)果解釋

1/31/202326OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES

2)0.00000048.000000

3)0.0000002.000000

4)40.0000000.000000結(jié)果解釋

最優(yōu)解下“資源”增加1單位時“效益”的增量原料增1單位,利潤增48時間加1單位,利潤增2能力增減不影響利潤影子價格

35元可買到1桶牛奶，要買嗎？35<48,應該買！聘用臨時工人付出的工資最多每小時幾元？2元！1/31/202327RANGESINWHICHTHEBASISISUNCHANGED:

OBJCOEFFICIENTRANGES

VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASE

X172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000最優(yōu)解不變時目標系數(shù)允許變化范圍DORANGE(SENSITIVITY)ANALYSIS?

Yesx1系數(shù)范圍(64,96)

x2系數(shù)范圍(48,72)

A1獲利增加到30元/千克，應否改變生產(chǎn)計劃x1系數(shù)由243=72增加為303=90，在允許范圍內(nèi)不變！(約束條件不變)結(jié)果解釋

1/31/202328結(jié)果解釋

RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000

RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000影子價格有意義時約束右端的允許變化范圍原料最多增加10時間最多增加53

35元可買到1桶牛奶，每天最多買多少？最多買10桶？(目標函數(shù)不變)1/31/2023291.4案例分析1/31/202330例6階段生產(chǎn)問題某公司生產(chǎn)某產(chǎn)品,最大生產(chǎn)能力為10000單位,每單位存儲費2元,預定的銷售量與單位成本如下:月份單位成本(元)銷售量12347060007170008012000766000求一生產(chǎn)計劃,使1)滿足需求;2)不超過生產(chǎn)能力;3)成本(生產(chǎn)成本與存儲費之和)最低.1/31/202331解:假定1月初無庫存,4月底賣完,當月生產(chǎn)的不庫存,庫存量無限制.第j+1個月的庫存量第j+1個月的庫存費共3個月的庫存費到本月總生產(chǎn)量大于等于銷售量4個月總生產(chǎn)量等于總銷售量4個月總生產(chǎn)成本1/31/202332model:title生產(chǎn)計劃程序1;Sets:yuefen/1..4/:c,x,e,d;endsetsdata:c=70718076;d=60007000120006000;e=2222;a=10000;enddatamin=@sum(yuefen:c*x)+

@sum(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x-d)*e(j+1));@for(yuefen(j)|j#lt#4:

@sum(yuefen(i)|i#le#j:x)>@sum(yuefen(i)|i#le#j:d));@sum(yuefen:x)=@sum(yuefen:d);@for(yuefen:x<a);end

1/31/202333露天礦里鏟位已分成礦石和巖石:平均鐵含量不低于25%的為礦石，否則為巖石。每個鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。每個鏟位至多安置一臺電鏟，電鏟平均裝車時間5分鐘卡車在等待時所耗費的能量也是相當可觀的，原則上在安排時不應發(fā)生卡車等待的情況。例7、露天礦生產(chǎn)的車輛安排(CUMCM-2003B)

礦石卸點需要的鐵含量要求都為29.5%1%(品位限制），搭配量在一個班次（8小時）內(nèi)滿足品位限制即可。卸點在一個班次內(nèi)不變?？ㄜ囕d重量為154噸，平均時速28km,平均卸車時間為3分鐘。問題：出動幾臺電鏟，分別在哪些鏟位上；出動幾輛卡車，分別在哪些路線上各運輸多少次?1/31/202334平面示意圖1/31/202335問題數(shù)據(jù)距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.265.194.214.002.952.742.461.900.641.27倒裝Ⅰ1.900.991.901.131.272.251.482.043.093.51巖場5.895.615.614.563.513.652.462.461.060.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝Ⅱ4.423.863.723.162.252.810.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量0．951．051．001．051．101．251．051．301．351．25巖石量1．251．101．351．051．151．351．051．151．351．25鐵含量30%28%29%32%31%33%32%31%33%31%1/31/202336問題分析與典型的運輸問題明顯有以下不同：這是運輸?shù)V石與巖石兩種物資的問題；屬于產(chǎn)量大于銷量的不平衡運輸問題；為了完成品位約束，礦石要搭配運輸；產(chǎn)地、銷地均有單位時間的流量限制；運輸車輛只有一種，每次滿載運輸，154噸/車次；鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個產(chǎn)地作為最后結(jié)果中的產(chǎn)地；最后求出各條路線上的派出車輛數(shù)及安排。近似處理：先求出產(chǎn)位、卸點每條線路上的運輸量(MIP模型)然后求出各條路線上的派出車輛數(shù)及安排1/31/202337模型假設卡車在一個班次中不應發(fā)生等待或熄火后再啟動的情況；在鏟位或卸點處由兩條路線以上造成的沖突問題面前，我們認為只要平均時間能完成任務，就認為不沖突。我們不排時地進行討論；空載與重載的速度都是28km/h，耗油相差很大；卡車可提前退出系統(tǒng)，等等。如理解為嚴格不等待，難以用數(shù)學規(guī)劃模型來解個