優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟(已修改)
2025-06-11 22:14 本頁面
【正文】 1 優(yōu)化模型與軟件工具 數(shù)學(xué)規(guī)劃軟件 清華大學(xué)經(jīng)濟管理學(xué)院 管理科學(xué)與工程系 2 數(shù)學(xué)規(guī)劃軟件 ? 線性規(guī)劃方法的簡單回顧 ? 線性規(guī)劃求解軟件 ? 整數(shù)規(guī)劃 3 線性規(guī)劃方法簡單回顧 4 線性規(guī)劃 ? 線性規(guī)劃是經(jīng)濟組織中 n 種經(jīng)濟活動 競爭使用 m種資源 的資源優(yōu)化配置問題； ? 典型的線性規(guī)劃可以表示如下 ? 求解方法：單純形方法、內(nèi)點法 uxlbAxtoS u b j ec txcM i n i m i z eT???5 單純形方法理論發(fā)展歷史 主要研究者 時間1 原始單純形算法 D an t z i g 19472 對偶理論和對偶單純形算法 L e m k e 1954線性規(guī)劃的退化與循環(huán) B e al e 1955防止循環(huán)的字典規(guī)則 D an t z i g, O r d e n , Wol f e 1955B l an d 規(guī)則 B l an d 1977對偶分解方法 D an t z i g Wol f 1961原始分解方法 B e n d e r s 1962單純形算法復(fù)雜性研究與最壞情況研究K l e e , M i n t y 1972單純形算法概率意義上的算法復(fù)雜性B or gw ar d t , S m al e 19823456 單純形方法回顧 考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題： P： max: z = cx . Ax = b x ? 0 令 A = (B, N)，問題 P可改寫為： max z = cB xB + cN xN . BxB + NxN = b xB, xN ? 0 因 B有逆 ： xB = B1(b NxN) = B1b B1NxN 代入目標(biāo)： z = cBB1b + (cN – cB B1N) xN 7 單純形方法回顧 因而，線性規(guī)劃 P的典則形式為 max z = cBB1b + (cN cBB1N) xN . xB = B1b B1N xN xB， xN ? 0 令 xN= 0 有 : xB = B1b， z = cBB1b，若 xB = B1b?0， x = (B1b, 0)是一個基本可行解。 cN cBB1N 被稱為檢驗向量。檢驗向量中的一個分量為 ?j = cj cBB1pj ，被稱為 檢驗數(shù) 或 遞減成本 (Reduced cost)。 8 變量有上下界的單純形方法 考慮下述線性規(guī)劃問題： max: z = cx . Ax = b l ? x ? u ? 非基變量有在下界和上界兩種狀態(tài)， ? A矩陣可分為： A = (B, Nl, Nu)， Nl對應(yīng)非基變量在下界的矩陣， Nu對應(yīng)非基變量在上界部分。 ? 令 JNl表示在下界的非基變量的下標(biāo)集合， JNu表示在上界的非基變量的下標(biāo)集合。 9 變量有上下界的典則方程 ? 變量有上下界的典則方程可以寫為： max z = cBB1b + (cNlcBB1Nl)xNl + (cNu cBB1Nu)xNu . xB = B1b B1Nl xNl B1Nu xNu xNl = l, xNu = u ? 典則方程有以下一些變化： 1. 非基變量不在為零，而是在其上下界上； 2. 最優(yōu)檢驗要分兩部分討論，分別對應(yīng)在下界和在上界的非基變量； 3. 目標(biāo)函數(shù)的表達(dá)要比以前復(fù)雜，不再是簡單的cBB1b。 10 變量有界的單純形算法 1. 將問題轉(zhuǎn)化為標(biāo)準(zhǔn)型，找一個初始可行基 B； 2. 最優(yōu)性檢驗：計算 ?j = cj cBB1pj ? jJN} 若滿足 已找到最優(yōu)解，停止計算。 否則計算 令變量 xk 入基，轉(zhuǎn)到 3； 3. 確定出基變量： i) 若 k?JNl，計算： ?????????NujNljJjJj 0 0??? ? ? ?? ? jJjjJjkNuNlm a xm a xm a x ??? ?? ?? ,?????????? ??????? 0 jkjkjjJjlaalbm i nB??????????? ??????? 0 jkjkjjJjuaaubm i nB?11 變量有界的單純形算法 ii) 若 k?JNu，計算： ? = min{? l, ? u, uk lk }
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1