運籌學-第三節-單純形法_第1頁
運籌學-第三節-單純形法_第2頁
運籌學-第三節-單純形法_第3頁
運籌學-第三節-單純形法_第4頁
運籌學-第三節-單純形法_第5頁
已閱讀5頁，還剩17頁未讀， 繼續免費閱讀

下載本文檔

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

文檔簡介

1、第三節 單純形法一、單純形法的步驟單純形法的步驟：（1）尋找可行域的一個基本可行解（一個極點），第一個基本可行解稱為初始基本可行解（2）檢查現行的基本可行解是否最優，如果目標函數達到最優，就停止迭代，已找到最優解，否則，轉一步 （3）移至目標函數值有所改善的另一個基本可行解。然后轉到步驟（2）。 以此類推，由于基本可行解（極點）數目有限，如果線性規劃有最優解的話，就一定能在有限步內就一定能找到最優解。1.確定初始的基本可行解二、判斷現行的基本可行解是否最優Max z = c1x1 + c2x2 + + cnxna11x1 + a12x2 + + a1nxn = b1a21x1 + a22x2

2、+ + a2nxn = b2 . . .am1x1 + am2x2 + + amnxn = bm x1 ，x2 ， ，xn 0B=（p1,p2, ,pm） 可行基m個基變量： x1,x2, ,xmn-m個非基變量： xm+1,xm+2, ,xn基 B相應的目標函數典式稱為非基變量xj的系數為檢驗數（1）對某個基本可行解，如果對所有j ，則這 個基本可行解就是最優解。 (2) 對某個基本可行解，如果對所有j ，但有 一個檢驗數 ，則該該線性規劃模型具有無窮多解。 最優解判別定理無窮多最優解判別定理例2.11 用單純形法的思路解下列線性規劃問題三.基本可行解的改進若 0，則相應的非基變量xj的值從當前值增加時，目標函數值隨之增加。這個選定的非基變量xj 稱為“進基變量”。確定基變量的值在進基變量增加過程中首先減少到0的變量r，滿足 這個基變量xr稱為“出基變量”。當進基變量的值增加到 時，出基變量xr的值降為0，基本可行解就移到了相鄰的基本可行解（極點）如果進基變量的值增加時，所有基變量的值都不減少，即所有aij非正，則表示可行域是非封閉的，目標函數值隨進基變量的增加可以無限增加，此時，不存在有限最優解，計算結束無有限最優解判別定理若X是一個基本可行解，有一個檢驗數 0,但是B-1

溫馨提示

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

評論

0/150

提交評論