整數規(guī)劃的難度遠大于一般線性規(guī)劃-wenkub
2023-02-17 19:32:12 本頁面
【正文】 ， 所得新的效率矩陣 {bij}m?m的任務分配問題的最優(yōu)解等價于原問題的最優(yōu)解。 證明：略 定理 2 若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內所有零元素的最少直線數等于位于不同行、不同列的零元素的最多個數。若該列有二個以上未標記的零，暫不標記，轉下一列檢查，直到所有列檢查完； ??????????????????????????????221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查檢列逐查檢行逐重復 2后，可能出現三種情況； a. 每行都有一個 (0)，顯然已找到最優(yōu)解，令對應 (0)位置的 xij=1； b. 仍有零元素未標記，此時，一定存在某些行和列同時有多個零，稱為 僵局狀態(tài) ，因為無法采用 1. 2 中的方法繼續(xù)標記?；氐? b 重新標記； (2) 少于 m條直線，到 第三步 ； 12 清華算法的步驟：例 第三步： 進一步變換； ? 在未劃線的元素中找 最小者 ，設為 ? ? 對未被直線覆蓋的各元素減去 ? ? 對兩條直線交叉點覆蓋的元素加上 ? ? 只有一條直線覆蓋的元素保持不變 以上步驟實際上仍是利用 定理 1 ??????????????221*0*02)0(1123)0(*0)0(23????????????????11000202012000241?第四步： 抹除所有標記，回到 第二步 ，重新標記； 13 解優(yōu)最列逐行逐記標???????????????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記標列???????????????110*00202*012)0(*0)0(2局僵破打?
教學課件相關推薦
鄂ICP備17016276號-1