運籌學(xué)復(fù)習(xí)參考資料(編輯修改稿)
2025-05-14 12:13 本頁面
【文章內(nèi)容簡介】 6－5M－6MMM－M－M5M－46M－3↑－M－M00－3x241/21－1/401/404/1/2=8－Mx64（2）01/2－1－1/214/2=2－2M－3/2－33/4－M/2MM/2－3/4－M2M－5/2↑0M/2－3/4－M3/4－3M/20－3x2301－3/81/43/8－1/4－4x12101/4－1/2－1/41/2－17－4－31/85/4－1/8－5/400－1/8－5/4－M＋1/8－M＋5/4∴X*=（2，3，0，0）T∴min z =－max z/ =－（－17）=17四、對偶問題的解法：什么是對偶問題？在資源一定的條件下，作出最大的貢獻；完成給定的工作，所消耗的資源最少。引例（與本資料P2例1 “圖解法”、P7例1 “單純形法”同）：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，這些產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工時需要不同的工時，這些產(chǎn)品售后所能獲得的利潤值以及這三種加工設(shè)備因各種條件下所能使用的有效總工時數(shù)如下表：品產(chǎn)耗消備設(shè) A B C利潤（萬元）甲乙3 5 99 5 37030有效總工時540 450 720——問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤為最大？解：原問題——設(shè)xx2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。max z = 70x1+30x2.將這個原問題化為它的對偶問題——設(shè)yyy2分別為設(shè)備A、B、C單位工時數(shù)的加工費。min w = 540y1+450y2+720y3.用大M法，先化為等效的標準模型：max w/ =－540y1－450y2－720y3.增加人工變量yy7，得到：max z/ =－540y1－450y2－720y3－My6－My7大M法單純形表求解過程如下：CBXBb－540－450－72000－M－MθLy1y2y3y4y5y6y7－My670359－101070/3－My730（9）530－10130/9=10/3－12M－10M－12MMM－M－M12M－540↑10M－45012M－720－M－M00－My660010/3（8）－11/31－1/360/8=－540y110/315/91/30－1/901/910/3/1/3=10300+10/3M8M－180－M－M/3+60－MM/3－600150+10/3M8M540↑MM/3－600－M/3+60－720y315/205/121－1/81/241/8－1/2415/2/5/12=18－540y15/61（5/12）01/24－1/8－1/241/85/6/5/12=2－540－572－720－135/2475/12－135/2－75/20125↑0135/2－475/12135/2－M75/2－M－720－450y320/3－1011/61/61/6－1/6y2212/5101/10－3/10－1/103/10－5700－360－450－7207515－75－15－18000－75－1575－M15－M∴該對偶問題的最優(yōu)解是y*=（0，2，0，0）T最優(yōu)目標函數(shù)值min w =－（－5700）=5700五、運輸規(guī)劃問題：運輸規(guī)劃問題的特殊解法——“表上作業(yè)法”解題步驟：找出初始調(diào)運方案。即在(mn)產(chǎn)銷平衡表上給出m+n1個數(shù)字格。（最小元素法）（對空格）求檢驗數(shù)。判別是否達到最優(yōu)解。如已是最優(yōu)解，則停止計算，否則轉(zhuǎn)到下一步。（閉回路法）對方案進行改善，找出新的調(diào)運方案。（根據(jù)檢驗結(jié)果選擇入基變量，用表上閉回路法調(diào)整——即迭代計算，得新的基本可行解）重復(fù)3，再檢驗、再迭代，直到求得最優(yōu)調(diào)運方案。類型一：供求平衡的運輸規(guī)劃問題（又稱“供需平衡”、“產(chǎn)銷平衡”）引例：某鋼鐵公司有三個鐵礦和四個煉鐵廠，鐵礦的年產(chǎn)礦石量分別為100萬噸、80萬噸和50萬噸，煉鐵廠年需礦石量分別為50萬噸、70萬噸、80萬噸和30萬噸，這三個鐵礦與四個煉鐵廠的距離如下：礦鐵廠鐵離距煉 B1 B2 B3 B4A1A2A315 20 3 3070 8 14 2012
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號-1