優(yōu)化模型與軟件工具數(shù)學(xué)規(guī)劃軟-wenkub
2023-05-29 22:14:51 本頁面
【正文】 件 清華大學(xué)經(jīng)濟(jì)管理學(xué)院 管理科學(xué)與工程系 2 數(shù)學(xué)規(guī)劃軟件 ? 線性規(guī)劃方法的簡單回顧 ? 線性規(guī)劃求解軟件 ? 整數(shù)規(guī)劃 3 線性規(guī)劃方法簡單回顧 4 線性規(guī)劃 ? 線性規(guī)劃是經(jīng)濟(jì)組織中 n 種經(jīng)濟(jì)活動 競爭使用 m種資源 的資源優(yōu)化配置問題； ? 典型的線性規(guī)劃可以表示如下 ? 求解方法：單純形方法、內(nèi)點(diǎn)法 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)是一個基本可行解。 ? 令 JNl表示在下界的非基變量的下標(biāo)集合， JNu表示在上界的非基變量的下標(biāo)集合。 4. 若 ? = + ?，該問題無界，停止計算； 若 ? = uk lk，轉(zhuǎn)到 6，否則轉(zhuǎn) 5； 5. 令 xk入基， xr出基，進(jìn)行旋轉(zhuǎn)迭代，轉(zhuǎn) 2； 6. 如果 xk 在下界，將其置于上界；如果 xk 在上界，將其置于下界，并計算基變量的相應(yīng)變化。 ?影子價格是對偶解十分形象的名稱，它既表明對偶解是對資源的一種客觀估價，又表明它是虛擬而不是真實(shí)的價格。 2. 影子價格是一種邊際值 ? 與經(jīng)濟(jì)學(xué)中邊際成本的概念相同； ? 在管理中有十分重要的應(yīng)有價值，管理者可根據(jù)資源影子價格的大小決定經(jīng)營策略 ； 影子價格的特點(diǎn) 16 3. 影子價格 cBB1與系統(tǒng)價值取向和狀態(tài)有關(guān) ? 影子價格與系統(tǒng)的價值取向有關(guān) (反映在 cB上 )； ? 影子價格受系統(tǒng)狀態(tài)影響 (反映在 B1上 ) ； ? 系統(tǒng)內(nèi)資源數(shù)量和價格的變化都會引起影子價格的變化，因此它是一種動態(tài)價格體系。 A 產(chǎn)品需消耗 2個單位的原料和 1 小時人工； B 產(chǎn)品需消耗 3 個單位的原料和 2 小時人工。問該企業(yè)如何組織生產(chǎn)才能使銷售利潤最大。 22 檢驗(yàn)數(shù)（遞減成本）的特點(diǎn) ? 變量的檢驗(yàn)數(shù) ? = cN cBB1N 與約束的影子價格相似，是系統(tǒng)達(dá)到最優(yōu)時的邊際值。 28 ? 80年代： ? 計算機(jī)硬件、軟件技術(shù)進(jìn)步加快，求解模型的規(guī)模又上升一個數(shù)量級 ? 內(nèi)點(diǎn)法問世，新軟件出現(xiàn)，如 CPLEX， OSL等； ? 出現(xiàn)較完整的模型求解系統(tǒng)： GAMS， AMPL等。 如果用窮舉法求解 ， 需要的時間如下： n 解的數(shù)量 求解時間 10 ?103 ?103 秒 20 ?106 秒 30 ?109 18 分鐘 40 ?1012 13 天 50 ?1015 36 年 100 ?1030 4 億億 年 整數(shù)規(guī)劃求解難度 39 整數(shù)規(guī)劃求解史： 1950－ 1998 ? 1954 Dantzig, Fulkerson, S. Johnson: 使用割平面方法求解有 42個城市的旅行推銷商問題（ TSP）； ? 割平面方法 : 1957年 Gomory完成了割平面方法的理論研究； ? 分支定界法（ Branchandbound） ： 1960 Land,
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1