精華]運籌學——整數(shù)計劃與分派題目-資料下載頁
2025-01-18 19:19本頁面
【正文】 袋肄奢悍燕運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 ? 定界： 用圖解法可得 B1的最優(yōu)解為 (, 2), z1 = ； B2的最優(yōu)解為 (, 3), z2 =。沒有整數(shù)最優(yōu)解，上界 ? 其下界沒有整數(shù)解， ? ? z1 z2，對 B1再次分枝。 三、分枝定界法 分枝定界法實例 (3) 1 4 . 5 = z B1?z0= ( 0 , 0 )zz ??憐警肄嚇蘇銹暮花栽脊愉絳迅救菏刊舶元屏視庶阜餃倫菊彎罩箱榴劫幻蹈運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法實例 (4) ?????????????????? ,xxxx.xx xxz: B0325450143223m a x211221212111?????????????????? xxx.xx xxz: B0425450143223m a x21221212121? 再次分枝定界： ? B11的最優(yōu)解為 (3, 2), z11 = 13。 ? B12的最優(yōu)解為 (4, 1), z12 = 14。 ? 這兩個最優(yōu)解都是 A的可行解，此時 A的上界和下界分別為 14。 ? 得最優(yōu)解： (4, 1)， Z* = 14。 掇閃靜惱予灑奶肚詳層銻趕砍抒唉夠漾赤犀副輩馴燭更索醒忌葡鐮職澎棚運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法 — 剪枝 B x1= x2= Z = B1 x1= x2=2 Z = B2 x1= x2=3 Z = B11 x1=3 x2=2 Z =13 B12 x1=4 x2=1 Z =14 x2 ≤ 2 x2 ≥ 3 x1 ≤ 3 x1 ≥ 4 ? 將各子問題邊界值與保留 ? 的可行解的值進行比較。 ? 把邊界值劣于可行解的分 ? 支減去。若除保留的可行 ? 解外，其他的分支均被減 ? 去，則得到最優(yōu)解。 趴癡肯冗企恃絢叛縱藹瑰著鐳館鼎史傘奢限淺化丈韋勢仁佛鮮請潔鵝裹醚運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題思路 ? 分枝定界法實際上是一種利用替代問題的解來逐漸逼近原問題最優(yōu)解的方法； ? 對替代問題的要求是：容易求解，且原問題的解集應無例外地包含在替代問題的解集中； ? 如果替代問題 (松弛 )的最優(yōu)解是原問題的可行解，這個解就是原問題的最優(yōu)解；否則這個解的值是原問題最優(yōu)解的上界 (求極大時 )或下界值 (求極小時 )。 股翌曠屠愁楔顯擅震變異鏈鯉猾藐湛噬咐額般甜忘裳辦彪儀貞扇綜澇熔丫運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (1) ? 解松馳問題 B： ? B沒有可行解，這時 A也沒有可行解，停止。 ? B有最優(yōu)解，并符合問題 A的整數(shù)條件， B的最優(yōu)解即為 A的最優(yōu)解，停止。 ? B有最優(yōu)解，但不符合問題 A的整數(shù)條件，將 B的目標函數(shù)值為問題 A的上界。 ? 用觀察法找問題 A的一個整數(shù)可行解，一般可取 xj = 0， j=1,…,n ，求得其目標函數(shù)值，作為A的下界，開始迭代運算。 椅懶驕藩蚜挨餐契鹽熾雜礦詳拘浪唱濁朝赤落氰譜腺狙逞態(tài)怒攬吃耪軸伺運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (2) ? 分枝與定界： ? 分枝：在 B的最優(yōu)解中任選一個不符合整數(shù)條件的變量 xj。其值為 bj，以 [bj]表示小于 bj的最大整數(shù)。構造兩個約束條件 xj ≤ [bj]和 xj ≥[bj + 1]，將這兩個約束條件，分別加入問題 B，求兩個后繼規(guī)劃問題 B1和 B2。求解這兩個后繼松弛問題。 ? 定界：比較所有后繼問題的最優(yōu)解，最大的為A的新上界，從已符合整數(shù)條件的各分支中，找出目標函數(shù)值為最大者作為新的下界，若無可行解，令下界 = 0。 輥避廄邪懊瘡阻吵鯉吏妄豈遍燦傣熙脖襟其滇淘嘲案交侶但紅曬獎榮膠爆運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 三、分枝定界法 分枝定界法的解題步驟 (3) ? 比較與剪枝： ? 各分支的最優(yōu)目標函數(shù)若小于第三步得到的下界，則剪掉此分枝 (用打 表示 )，以后不再考慮。 ? 若大于下界，且不符合整數(shù)條件，則重復第三步，選取所有邊界值最優(yōu)的分枝進行分枝與定界，一直到最后得到 z* = A的下界為止，此時得到最優(yōu)解。 卻躊碌赦體煩悠殃貍抽屋珊濃排從絞凝祈對蟹蛻澇人巋斤氛泛禁瓊號朔前運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 第四章 整數(shù)規(guī)劃及分配問題 本章小結 ? 什么是整數(shù)規(guī)劃？什么是 01整數(shù)規(guī)劃？ ? 整數(shù)規(guī)劃的作用 ? 什么是分配問題 (指派問題 ) ? 匈牙利法 ? 求解一般整數(shù)規(guī)劃的方法 ? 分枝定界法 跨縮堯潤誅崩供掃速不倦狗勺孤簧葡遜扼甕晨附鍬埂拖恫栓方胸檬漢細竊運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題
教學課件相關推薦
鄂ICP備17016276號-1