整數(shù)規(guī)劃學(xué)時ppt課件-在線瀏覽
2025-06-17 18:15本頁面
【正文】 第 i 組條件不起作用 則i=1,2x1? 4＋ (1y1) M x2? 1－ (1y1) MM—— 充分大正數(shù)x1? 4－ (1y2) M x2? 3＋ (1y2) My1＋ y2=1 y1， y2=0或 115第 4章 整數(shù)規(guī)劃 5. 分段函數(shù)線性表示設(shè)有 f(xj)= Kj+cjxj 當(dāng) xj0 0 當(dāng) xj=0，將 min f (xj) 表示成線性函數(shù)。② 令所有變量 xj=0， 計算邊界目標(biāo)函數(shù)值 z， 檢查是否滿足所有約 束條件，若滿足，即為最優(yōu)解；否則，分枝計算。④ 剪枝：在得到一個可行解后，分枝過程中要進(jìn)行剪枝工作。 17第 4章 整數(shù)規(guī)劃 例：求解下述 01規(guī)劃問題：Max z=8x1+2x24x37x45x5 st. 3x1+3x2+x3+2x4+3x5 ?4 5x1+3x2 2x3 x4+ x5 ?4 xj=0或 1 (j=1,2,3,4,5)1) 目標(biāo)函數(shù)極小化 : min z?=8x12x2+4x3+7x4+5x5① 化標(biāo)準(zhǔn)形：2) 約束條件 ?： 3x13x2x32x43x5 ?4 5x13x2+ 2x3 + x4 x5 ?4 xj=0或 1 (j=1,2,3,4,5)18第 4章 整數(shù)規(guī)劃 3) 使目標(biāo)函數(shù)系數(shù)皆為正： 令 x1=1x1? ， x2=1x2? min z?=8+8 x1? 2+2 x2? +4x3+7x4+5x5st. 3+3 x1? 3+3 x2? x32x43x5 ?4 5+5 x1? 3+3 x2? + 2x3 + x4 x5 ?4x1? , x2? ,xj=0或 1 (j=3,4,5)4) 變量按順序排列：min z?= 2 x2? +4x3 +5x5 +7x4+8 x1? 10st. 3 x2? x3 3x5 2x4 +3 x1? ?23 x2? + 2x3 x5 + x4+5 x1? ?4x1? , x2? ,xj=0或 1 (j=3,4,5)19第 4章 整數(shù)規(guī)劃 求解圖示：1234567891011z?=10z? =8z?=4z?=6z?=5z?=1z?=1z?=5z?=3z?=6x2?=1x2?=0x3=1x3=0x3=1x3=1x5=1x5=0x5=1x5=0z?=3√20第 4章 整數(shù)規(guī)劃 分配問題及匈牙利算法 (Assignment Problem)一、問題的提出和數(shù)學(xué)模型例：有一份說明書，要分別譯成英、日、德、俄四種文字，交與甲、乙、丙、丁四個人去完成，因各人專長不同，他們完成翻譯不同文字所需要的時間（小時）如表所示。 問：如何分配，能使所需的總時間最少？甲 乙 丙 丁工作 人譯英文譯日文譯德文譯俄文2 10 9 715 4 14 813 14 16 114 15 13 9 21第 4章 整數(shù)規(guī)劃 建立模型：設(shè) xij=10譯英文： x11+ x12 + x13 + x14 =1譯日文： x21+ x22 + x23 + x24 =1譯德文： x31+ x32 + x33 + x34 =1譯俄文： x41+ x42 + x43 + x44 =1甲： x11+ x21 + x31 + x41 =1乙： x12+ x22 + x32 + x42 =1丙： x13+ x23 + x33 + x43 =1?。?x14+ x24 + x34 + x44 =1xij =0或 1 (i=1,2,3,4。 規(guī)定每項工作只能交與其中的一個人完成，而每個人只能完成其中的一項工作。,m。,m)(i=1,2,m)23第 4章 整數(shù)規(guī)劃 二、匈牙利法：基本思想：4 (0) 5 6 5 4 (0) 5 7 6 3 (0) (0) 5 6 2 克尼格定理 (konig)： 如果從效率矩陣 [aij]的每一行元素中分別減去 (或加上 )一個常數(shù) ui,從每列中分別減去 (或加上 )一個常數(shù) vj,得到一個新的效率矩陣 [bij],其中 bij=aijuivj,則以 [bij]為效率矩陣的最優(yōu)解等價于以[aij]為效率矩陣的最優(yōu)解 .24第 4章 整數(shù)規(guī)劃 證明 :以 [aij]為效率矩陣的目標(biāo)函數(shù)值： z0=?? aijxij以 [bij]為效率矩陣的目標(biāo)函數(shù)值： z?=??bijxij m mi=1j=1i=1j=1 m m∵ bij=aijuivj∴ z?=?? (aijuivj)xij = ?? aijxij ?? uixij ?? vjxij =z0 ?ui?xij ?vj?xijm m m m m mm m m m =z0 ?ui ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1