單純形算法（simplex algorithm）是2016年全國科學技術名詞審定委員會公布的管理科學技術名詞。
基本介紹
- 中文名：單純形算法
- 外文名：simplex algorithm
- 所屬學科：管理科學技術
- 公布時間：2016年
定義,出處,
相關詞條
- 單純形法
單純形法是求解線性規劃問題最常用、最有效的算法之一。單純形法最早由 George Dantzig於1947年提出，近70年來，雖有許多變形體已經開發，但卻保持著同樣的基本觀念。如果線性規劃問題的最優解存在，則一定可以在其可行區域的頂點中找到。...
- 單純形算法
單純形算法（simplex algorithm）是2016年全國科學技術名詞審定委員會公布的管理科學技術名詞。定義 根據問題的標準型，從可行域中一個基本可行解開始，轉換到另一個基本可行解，並且使目標函式值增大，當目標函式值達到最大時問題就得到了...
- 換入變數
解：單純形法求解過程的單純形表如下：在第一次疊代中，可以得到 ，一般選其中的 最大者的非基變數為換入變數，所以換入變數為 。特殊情況 1.對於求最大目標函式的問題，在某次疊代的單純形表中，如果存在著一個大於零的檢驗...
- 改進單純形法
首先，進行基本單純形法操作，快速得到局部極小值，再對極小值點在取值範圍內進行變異操作，並重新進行基本單純形法操作，直到得到最優解為止。該算法的計算步驟如下：1.選取初始單純形，初始步長L，最大變異次數m，計數器m=0；2....
- 內點算法
內點算法是一類重要的數學規劃問題。線性規劃是一類重要的數學規劃問題，求解線性規劃的常用算法是單純形算法。單純形算法的特點是從可行域的一個頂點出發，通過一次疊代挪動到臨近較優的另一頂點，直至到達最優點為止。單純形算法簡單、實用...
- 單純形加速
因此疊代過程是有限的，這就是線性規劃中單純形算法的根據。最適於等式約束。非線性規劃中的單純形法借用其“頂點尋優”的想法。但與線性規劃有很大不同。基本思路是：往最壞點的相反方向走，有可能找到較優點”。其基本步驟是對n個...
- 單純多面體
單純多面體是由一類多面體派生的另一類多面體，指除多面體P自身及空集外，P的所有面均為單純形的多面體。簡介 單純多面體是由一類多面體派生的另一類多面體，指除多面體P自身及空集外，P的所有面均為單純形的多面體。單純形 單純形是代數...
- 線性規劃一種改進的對偶單純形法
與原對偶單純形法相比,改進算法的存貯量和計算量大大減少.最後給出了方法的實算例子.引文格式 羅雁,簡金寶,吳志遠.線性規劃一種改進的對偶單純形法[J].桂林工學院學報,2005(02):263-266.
- 算法設計與分析基礎(第3版)
9.1 Prim算法 245 習題9.1 249 9.2 Kruskal算法 250 習題9.2 255 9.3 Dijkstra算法 256 習題9.3 259 9.4 哈夫曼樹及編碼 260 習題9.4 264 小結 265 第10章 疊代改進 266 10.1 單純形法 267 10.1.1線性規劃的...
- 算法導論(原書第3版)
29.3 單純形算法 507 29.4 對偶性 516 29.5 初始基本可行解 520 思考題 525 本章註記 526 第30章 多項式與快速傅立葉變換 527 30.1 多項式的表示 528 30.2 DFT與FFT 531 30.3 高效FFT實現 536 思考題 539 本章註記 ...
- 算法概論(2008年清華大學出版社出版的圖書)
7.2.3對算法的深入觀察 217 7.2.4最優性的保證 221 7.2.5算法的效率 222 7.3二部圖的匹配 222 7.4對偶 224 7.5零和博弈(遊戲) 228 7.6單純形算法 232 7.6.1n維空間中的頂點和鄰居 232 7.6.2算法 233 7.6.3...
- 單純分解
單純分解(simplicial decomposition)是圖的一種分解，單純樹分解是單純分解的一種。基本介紹 設 是一個圖， 為一個序數，對於任何 ，記B為G的導出子圖，一個圖族 若滿足下列三個條件，則稱為G的一個單純分解：1. ；2.對任何...
- 線性規劃問題
內點算法是針對單形法的“邊界趨近”觀念而改採“內部逼近”的路線，相對於只沿著可行域的邊沿進行移動的單純形算法，內點算法能夠在可行域內移動。1984年，貝爾實驗室印度裔數學家卡馬卡（Narendra Karmarkar）提出了投影尺度法（又名...
- 非線性方程組數值解法
另一種方法稱為不動點算法或稱單純形法，它對求解域進行單純形剖分，對剖分的頂點給一種恰當標號，並用一種有規則的搜尋方法找到全標號單純形,從而得到方程(1)的近似解。這種方法優點是，不要求f(□)的導數存在,也不用求逆，且...
- 線形規劃
單純形法的計算 單純形法的計算比較繁瑣，雖然現在已有多種實用軟體，使用起來仍不方便。因此，對於各種具體問題，又產生了一些較為簡單的算法。例如，對運輸模型，有表上作業法，圖上作業法等。這裡我們介紹指派問題的算法。設有n項任務...
- 運籌學基礎(清華大學出版社出版的圖書)
8.3 線性目標規劃的序貫式算法239 8.4 線性目標規劃的單純形算法245 習題8249 第3部分 非線性規劃 第9章 非線性規劃的基本概念與基本原理/255 9.1 非線性規劃的數學模型255 9.1.1 非線性規劃問題舉例255 9.1.2 非線性規劃...
- 數學規劃
3.2 單純形算法64 3.2.1 基本原理64 3.2.2 算法步驟與單純形表67 3.2.3 啟動機制70 3.3 線性規劃的最優性條件77 3.4 對偶理論79 3.4.1 對偶定理79 3.4.2 對偶單純形法84 3.5 單純形算法的改進與推廣88 3.5.1...
- 運籌學(2011年黃紅選編寫、清華大學出版社出版的圖書)
第3章主要介紹線性規劃的靈敏度分析方法與對偶理論,討論了求解線性規劃問題的對偶單純形算法、最優性條件以及線性規劃對偶與對策論的關係。第4章討論整數規劃的模型與基本性質,以及求解整數規劃問題的主要方法和軟體技術。第5章介紹了無...
- 內點法
1972年，V.Klee和G.Minty給出一個例子，他們構造一個線性規劃問題，用單純形方法求解，需要的計算時間為 。這個例子表明，單純形算法雖然在實際套用中非常有效，至今占有絕對優勢，但在理論上它還不是多項式算法。於是產生這樣的問題：...
- 直接搜尋法
一旦初始單純形構造好， Spendley et al 單純形算法的單個移動是鏡像的。這個移動首先在單純形中確定“最差”頂點（例如：最小期望目標值的），然後通過向對面映射最差單純形。如果映射後的點仍然是最差的，則選擇“次差”頂點繼續...
- 運籌學導論:初級篇(第8版)
3.3 單純形方法 83 3.3.1 單純形方法的疊代本質 83 3.3.2 單純形算法的計算細節 85 3.3.3 單純形法的總結 91 3.4 人工初始解 95 3.4.1 大$M$方法 95 3.4.2 兩階段法 99 3.5 單純形方法中的特殊...
- 最最佳化理論與方法(2008年國防工業出版社出版的圖書)
2.4 單純形法 2.4.1 準備工作 2.4.2 單純形算法 2.5 初始基可行解的確定法 2.6 單純形法的改進 2.6.1 避免循環 2.6.2 修正單純形法 習題 第3章 對偶線性規劃 3.1 對偶問題的提出 3.1.1 從經濟問題提出...
- 運籌學套用範例與解法(第4版)
第4章單純形算法和目標規劃 4.1如何將LP轉換成標準形式 4.2單純形算法概覽 4.2.1基變數和非基變數 4.2.2可行解 4.3無界方向 4.4為什麼LP有最優bfs 4.4.1相鄰基本可行解 4.4.2三維LP的幾何圖形 4.5單純形算法 4.5.1...
