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

下載本文檔

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

設(shè)純整數(shù)規(guī)劃松弛問題的最優(yōu)解設(shè)xi不為整數(shù)，4/8/2025將分離成一個整數(shù)與一個非負真分數(shù)之和：則有等式兩邊都為整數(shù)并且有4/8/2025加入松弛變量si得此式稱為以xi行為源行（來源行）的割平面，或分數(shù)切割式，或R.E.Gomory(高莫雷)約束方程。將Gomory約束加入到松弛問題的最優(yōu)表中，用對偶單純形法計算，若最優(yōu)解中還有非整數(shù)解，再繼續(xù)切割，直到全部為整數(shù)解。則4/8/2025例如，x1行：移項：令加入松弛變量s1得同理，對于x2行有：4/8/2025如果在對偶單純形法中原切割方程的松弛變量仍為基變量，則此松弛變量所在列化為單位向量后就可以去掉該行該列，再切割。【例】已知整數(shù)規(guī)劃【解】不考慮整數(shù)約束，松弛問題的最優(yōu)表如下4/8/2025cj3200bCBXBx1x2x3x42x2011/2－1/25/23x110－1/43/413/4λj00－1/4－5/4最優(yōu)表最優(yōu)解X=(－1/2，3/4，0，0)T，x1、x2不滿足整數(shù)要求，選擇x2行進行分割：得到Gomory約束添加到最優(yōu)表中，得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約束添加到最優(yōu)表中，得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得到整數(shù)最優(yōu)解：X＝(4，1)，Z＝14注1：Gomory約束可寫為注2：Gomory約束只是割去線性規(guī)劃可行域的一部分，保留了全部整數(shù)解。用圖解法表示：4/8/202513/4,5/2松弛問題第一次切割4,1第二次切割x1+x2≤54/8/2025作業(yè)：教材P134T5.30—1規(guī)劃指派問題Exit1.領(lǐng)會

溫馨提示

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

評論

0/150

提交評論