整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃(專業(yè)版)
【正文】 證明：略 清華算法的 基本思路 ： ? 根據(jù) 定理 1 變換效率矩陣，使矩陣中有足夠多的零。回到 b 重新標(biāo)記； (2) 少于 m條直線，到 第三步 ； 12 清華算法的步驟：例 第三步： 進(jìn)一步變換； ? 在未劃線的元素中找 最小者 ，設(shè)為 ? ? 對(duì)未被直線覆蓋的各元素減去 ? ? 對(duì)兩條直線交叉點(diǎn)覆蓋的元素加上 ? ? 只有一條直線覆蓋的元素保持不變 以上步驟實(shí)際上仍是利用 定理 1 ??????????????221*0*02)0(1123)0(*0)0(23????????????????11000202012000241?第四步： 抹除所有標(biāo)記，回到 第二步 ，重新標(biāo)記； 13 解優(yōu)最列逐行逐記標(biāo)???????????????11)0(*0)0(2*02*012)0(*0)0(24 清華算法的步驟：例 ????????????????11000202012000241?答：最優(yōu)分配方案為 x13= x21= x34 = x42 =1，其余為 0， 即甲 ?C，乙 ?A，丙 ?D，丁 ?B， OBJ=20 ???????????????10002020120*0)(24記標(biāo)列???????????????110*00202*012)0(*0)0(2局僵破打??????????????221*0*02)0(1123)0(*0)0(2314 ???????????????6 0 2 0 5 0 4 0 0 3 0 1 0 2 0 0 局僵破打 關(guān)于清華算法的適用條件 ? 要求所有 aij ?0 – 若某些 aij 0 ，則利用定理 1 進(jìn)行變換，使所有 bij ? 0 ? 目標(biāo)函數(shù)為 min型 – 對(duì)于 max型目標(biāo)函數(shù)，將效率矩陣中所有 aij 反號(hào)，則等效于求 min型問(wèn)題；再利用定理 1 進(jìn)行變換，使所有 bij ? 0，則可采用清華算法 打破僵局時(shí)選擇不當(dāng)?shù)慕Y(jié)果：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1