9.1整数线性规划模式的类型.ppt

條件性與同時要求之限制式 第9章 整數線性規劃 第399頁 假設艾思可冰箱公司除非擴建工廠，否則不 考慮擴建倉庫。以 P 代表工廠擴建，W 代表倉庫擴建，以下條件限制式(conditional constraint) 能夠滿足這個要求： 如果接受工廠擴建計畫，也要接受倉庫擴建計畫，反之亦然，則我們稱 P 與 W表示共同要求限制式(corequisite constraint)。只要將前述的限制式改為等式即可： 條件性與同時要求之限制式 第9章 整數線性規劃 第400頁 敏感度分析的注意事項 第9章 整數線性規劃 第400-401頁 整數線性規劃的敏感度分析比線性規劃問題更重要。限制式係數非常小的改變就可能使最佳解的值產生很大變化。考慮以下整數線性規劃模式： 最佳解為 x1 = 1、x2 = 1、x3 = 1 及 x4 = 0，目標函數值為 170 美元。但是如果可用資金增加 1 美元（從 100 美元到 101 美元），最佳解將變成 x1 = 1、x2 = 0、x3 = 0 及 x4 = 1，目標函數值為 200 美元，也就是預算增加 1 美元將使報酬增加 30 美元。 敏感度分析的注意事項 第9章 整數線性規劃 第401頁 由於最佳解的目標值對限制式的係數非常敏感，因此建議在選定最佳解之前，先將係數稍作變化，然後再解整數線性規劃數次。 固定成本 第9章 整數線性規劃 第383頁 燃料添加劑每噸利潤 40 美元、溶劑基劑每噸 30 美元及地毯清潔劑每噸 50 美元。 每噸燃料添加劑含 0.4 噸原料 1 及 0.6 噸原料 3；每噸溶劑基劑含 0.5 噸原料 1、0.2 噸原料 2 及 0.3 噸原料 3；每噸地毯清潔劑含 0.6 噸原料 1、0.1 噸原料 2 及 0.3 噸原料 3。 RMC 公司有 20 噸的原料 1、5 噸的原料 2 及 21 噸的原料 3。 固定成本 第9章 整數線性規劃 第383-384頁 RMC 問題的線性規劃模式如下： 最佳解是 27.5 噸的燃料添加劑、0 噸的溶劑基劑及 15 噸的地毯清潔劑，最大利潤為 1850 美元，見圖 9.5。 固定成本 第9章 整數線性規劃 第384頁 固定成本 第9章 整數線性規劃 第384-385頁 重寫目標函數式，加入整備成本。淨利的目標函數變成： 重寫產能限制式，以便整備變數為 0 時，不允許生產該產品； 固定成本 第9章 整數線性規劃 第385頁 RMC 問題的固定成本模式如下： 固定成本 第9章 整數線性規劃 第385頁 如圖 9.6。最佳解為 25 噸的燃料添加劑及 20 噸的溶劑基劑。減去整備成本後的目標函數值為 1350 美元。 固定成本 第9章 整數線性規劃 第386頁 建立固定成本模式的關鍵，在於為每項固定成本引入0-1 變數，並且為該項產品確立其產量上限。 對產量 x，可以使用型如 x ≤ My 的限制式，當 y = 1 時表示可以生產；當整備變數 y = 0 時則表示不生產。 配銷系統設計 第9章 整數線性規劃 第373頁 馬丁貝克公司計畫在底特律、拖利多、丹佛或堪薩斯市增設工廠以增加產量。估計四個候選地點的年固定成本及產能估計值如下： 配銷系統設計 第9章 整數線性規劃 第386頁 公司的長程規劃小組預估各配銷中心的年需求量如下： 配銷系統設計 第9章 整數線性規劃 第386頁 從各工廠到各配銷中心的單位運輸成本如表 9.2。 可能的配銷系統網路模式如圖 9.7，產能及需求皆以千為單位。興建工廠的地點尚未決定。 配銷系統設計 第9章 整數線性規劃 第387頁 配銷系統設計 第9章 整數線性規劃 第387-388頁 配銷系統設計問題(distribution system design problem)利用 0-1 變數建立模式，以選擇最佳的工廠設置地點，並決定每一家工廠至各配銷點的運輸量。我們可使用以下的 0-1 變數代表設廠的決定。 工廠至配銷點的運輸量變數，定義方式和運輸問題一樣。 配銷系統設計 第9章 整數線性規劃 第388頁 新工廠每年營運的固定成本，以千美元為單位表示成： 配銷系統設計 第9章 整數線性規劃 第388-389頁 馬丁貝克配銷系統設計問題的完整模式如下： 配銷系統設計 第9章 整數線性規劃 第389頁 馬丁貝克問題的最佳解如圖9.8。 在堪薩斯市設置新廠(y4 = 1)；將從堪薩斯市運送20,000 個產品到亞特蘭大(x42 = 20)，另外 20,000 個從堪薩斯市運往休士頓(x43 = 20)，以及從聖路易市運送 30,000 個產品往波士頓(x51 = 30)。總成本為 860,000美元 可擴充此基本模式。利用 0-1 變數的特殊性質，此模式修改後也可以適應各