整數(shù)規(guī)劃問題及分配問題(編輯修改稿)
2024-11-15 19:51 本頁面
【文章內(nèi)容簡介】 a x b i p????令 yi為 01變量，如果第 i個約束條件是 k個約束條件中的一個，就令 yi=1，否則取 0；對 p個約束條件中的每一個約束條件都增加 yi，變?yōu)椋? 11( 1 ) ( 1 , 2. ... )01ni j i j i ijpiiia x b y M i py k y??? ? ? ???? 且 取 值 或關(guān)于固定費用的問題 引例 1： 今有 4輛裝載不同貨物的待卸車，派班員要分派給 4個裝卸班組，每個班組卸 1輛。由于各個班組的技術(shù)特長不同，各個班組卸不同車輛所需時間如下表。問：派班員應(yīng)如何分配卸車任務(wù)，可以使卸車所花費的總車輛小時最??？ i j P1 P2 P3 P4 甲 4 3 4 1 乙 2 3 6 5 丙 4 3 5 4 丁 3 2 6 6 一、指派問題及其模型特征 167。 74 指派問題 引例 2：一份中文說明書需要譯成英、日、德、俄四種文字（E， J， G， R），現(xiàn)有甲、乙、丙、丁四人可以完成上述任務(wù)，他們將說明書翻譯成不同語種的文字所需時間如下表，且一項任務(wù)只能由一人去完成，每人只能完成一項任務(wù)。問：指派何人完成何工作，可使總花費時間最少？ i j E J G R 甲 2 15 13 4 乙 10 4 14 15 丙 9 14 16 13 丁 7 8 11 9 （ 1） n項工作怎樣分配給 n個工作人員去完成， 可以使總花費時間最省； （ 2） n項加工任務(wù)怎樣分配給 n臺機床去完成， 可以使總費用最低； （ 3） n條航線，怎樣指定 n艘班輪去完成航行任 務(wù)，可以使總運輸費用最低； 。 —— 該類問題是運輸問題的特殊形式，稱為 指派問題。 （一）指派問題 （二）指派問題的基本特征 性質(zhì) ：特殊的運輸問題、特殊 01規(guī)劃問題。 特征 ：（ 1）決策變量為 01變量； (2) 發(fā)點數(shù) m = 收點數(shù) n； （ 3） ai=bj=1 i,j=1,2,…,n 。 ???????mjijijix ij,2,1,01?項任務(wù)個工人未分配去做第當?shù)陧椚蝿?wù)個工人分配去做第當?shù)?????????????????? ???? ?1,0,2,1 1,2,1 1)(m in111 1ijmiijmjijmimjijijxmjxmixxaxf??（三）指派問題的基本模型 ? 運輸問題是任務(wù)分配問題的松弛問題 ? 任務(wù)分配問題不但是整數(shù)規(guī)劃，而且是 0?1規(guī)劃 ? 任務(wù)分配問題有 2m個約束條件，但有且只有 m個非零解，是自然 高度退化 的 ?任務(wù)分配是 匹配問題 ，有著名的 匈牙利算法 任務(wù)分配問題模型特征： 二、匈牙利法 １、基本思想 ： （ 1） 匈牙利法基于任務(wù)分配問題的標準型，應(yīng)滿足三個條件 ： ?目標函數(shù)要求 min； ?效率矩陣｛ aij｝為方陣 。 ?效率陣中所有元素 aij≥ ０且為常數(shù) 定理 1（構(gòu)造等效矩陣） 如果從效率矩陣 {aij}m?m中每行元素分別減去一個常數(shù) ui，從每列元素分別減去一個常數(shù) vj ， 所得新的效率矩陣 {bij}m?m的任務(wù)分配問題的最優(yōu)解等價于原問題的最優(yōu)解。 證明： 定理 2 若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個數(shù)。 證明：略 （３） 基本思路： 根據(jù) 定理 1 變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在 m 個不同行不同列的零，就找到了最優(yōu)解 若覆蓋變換后的效率矩陣零元素的直線少于 m 條，就尚未找到最優(yōu)解，設(shè)法進一步變換矩陣，增加新的零 （２）匈牙利定理 最優(yōu)解不變?????????? ???? ?KZZxxKxaZmjijmjiijmimjijij39。 139。11)(1 1?引例： 有四個熟練工人，他們都是多面手，有四項任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項任務(wù)，而每人完成每項任務(wù)的工時耗費如下表，問如何分配任務(wù)使完成四項任務(wù)的總工時耗費最少？ 任務(wù) 工時 A B C D 人員人員甲 10 9 7 8 1乙 5 8 7 7 1丙 5 4 6 5 1丁 2 3 4 5 1任務(wù) 1 1 1 1２、計算步驟 ????????????????????????????????????????????2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910換變列換變行 第一步 建立等效矩陣 (行變換和列變換 ) 使等效矩陣每一行和每一列都至少有 1個 0 ??????????????????????????????221*0*02)0(1123)0(*0)0(23221*00201123)0(0023查檢列逐查檢行逐 第二步 （ 最優(yōu)解檢驗）檢查覆蓋所有零元素的直線是否為 m條 劃線規(guī)則 （ 1）逐行檢查 ，若該行只有一個未標記的零，對其加 ( )標記，將 ( )標記元素同列上其它的零打上 *標記。若該行沒有或有二個以上未標記的零，暫不標記，轉(zhuǎn)下一行檢查，直到所有
教學課件相關(guān)推薦
鄂ICP備17016276號-1