運籌學 北京郵電大學 課件ch5-3學習資料_第1頁
運籌學 北京郵電大學 課件ch5-3學習資料_第2頁
運籌學 北京郵電大學 課件ch5-3學習資料_第3頁
運籌學 北京郵電大學 課件ch5-3學習資料_第4頁
運籌學 北京郵電大學 課件ch5-3學習資料_第5頁
已閱讀5頁，還剩6頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

設純整數規劃松弛問題的最優解設xi不為整數，4/8/2025將分離成一個整數與一個非負真分數之和：則有等式兩邊都為整數并且有4/8/2025加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面，或分數切割式，或R.E.Gomory(高莫雷)約束方程。將Gomory約束加入到松弛問題的最優表中，用對偶單純形法計算，若最優解中還有非整數解，再繼續切割，直到全部為整數解。則4/8/2025例如，x1行：移項：令加入松弛變量s1得同理，對于x2行有：4/8/2025如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割?！纠恳阎麛狄巹潯窘狻坎豢紤]整數約束，松弛問題的最優表如下4/8/2025cj3200bCBXBx1x2x3x42x2011/2－1/25/23x110－1/43/413/4λj00－1/4－5/4最優表最優解X=(－1/2，3/4，0，0)T，x1、x2不滿足整數要求，選擇x2行進行分割：得到Gomory約束添加到最優表中，得4/8/2025cj32000bCBXBx1x2x3x4x52x2011/2－1/205/23x110－1/43/4013/40x500－1/2－1/21－1/2λj00－1/4－5/402x2010－1?23x11001－1/27/20x30011－21λj000－1－1/2x1行：Gomory約束添加到最優表中，得4/8/2025cj320000bCBXBx1x2x3x4x5x62x2010－1?023x11001－1/407/30x30011－1010x60000－1/21－1/2λj000－1－1/202x2010－10213x110010－140x300110－430x600001－21λj000－10－14/8/2025得到整數最優解：X＝(4，1)，Z＝14注1：Gomory約束可寫為注2：Gomory約束只是割去線性規劃可行域的一部分，保留了全部整數解。用圖解法表示：4/8/202513/4,5/2松弛問題第一次切割4,1第二次切割x1+x2≤54/8/2025作業：教材P134T5.30—1規劃指派問題Exit1.領會

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論