整數(shù)線性規(guī)劃ppt課件(編輯修改稿)
2025-02-17 23:17 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 01整數(shù)規(guī)劃分支時(shí)49分枝問(wèn)題解可能出現(xiàn)的情況情況 2, 4, 5 找到最優(yōu)解情況 3 在縮減的域上繼續(xù)分枝定界法情況 6 問(wèn)題 1 的整數(shù)解作為 界 被保留，用于以后與問(wèn)題 2 的后續(xù)分枝所得到的解進(jìn)行比較，結(jié)論如情況 4 或 550分枝定界法舉例 例 4解 ：松弛問(wèn)題的最優(yōu)解為 x1=, x2=2, OBJ=23 由 x1= 得到兩個(gè)分枝如下：51 表 分枝問(wèn)題的松弛解問(wèn)題 II的解即原整數(shù)問(wèn)題的最優(yōu)解 可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過(guò)程 當(dāng)存在很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解 一般整數(shù)規(guī)劃問(wèn)題屬于一類(lèi)未解決的難題， NPplete，只有少數(shù)特殊問(wèn)題有好的算法，如 任務(wù)分配問(wèn)題 、 匹配問(wèn)題52n 算法思想n 算法步驟n 算例割平面算法53算 法 思 想n 由放松問(wèn)題的可行域向整數(shù)規(guī)劃的可行域逼近n 方法 — 利用超平面切除n 要求 整數(shù)解保留 放松問(wèn)題最優(yōu)值增加54割平面生成方法n 條件 保留整數(shù)解刪除最優(yōu)解55整數(shù)可行解 最優(yōu)基可行解565758596061正則解62算 法 步 驟求放松問(wèn)題的最優(yōu)基可行解判斷是否為整數(shù)解是停止得到最優(yōu)解否在單純性表中加入一列利用對(duì)偶單純性算法求最優(yōu)解63算 例(1,)64656667686970計(jì) 算 軟 件n 整數(shù)變量定義 LinDo 一般整數(shù)變量 :GIN Variable 01整數(shù)變量 : INT Variable LinGo 一般整數(shù)變量 : @GIN( variable_name)。 01整數(shù)變量： @BIN( variable_name)。n 算例71算 例 max 3 x1+5 x2+4 x3 subject to 2 x1+3 x2=1500 2 x2+4 x3=800 3 x1+2 x2 +5 x3=2022endgin x1gin x372 任務(wù)分配問(wèn)題例 有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表 ，問(wèn)如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？73 任務(wù)分配問(wèn)題的數(shù)學(xué)模型模型中： xij 為第 i 個(gè)工人分配去做第 j 項(xiàng)任務(wù)； aij 為第 i 個(gè)工人為完成第 j 項(xiàng)任務(wù)時(shí)的工時(shí)消耗； {a
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1