線性規劃的多項式算法

《線性規劃的多項式算法》，線性規劃內點法開創性著作。Л.Г.哈奇安著。發表於蘇聯科學院報告1979年244。中譯文載於《應用數學與計算數學》1980年第2期。

內容簡介

本文被認為是線性規划算法研究上的一個重大的理論突破，開創了線性規劃內點算法的研究領域。本文以70年代由蓄爾創造的橢球方法的思想為基礎，構造了一系列橢球以搜索一線性不等式組的解。這一算法的運算次數為O(n3(n2+m)L)，所需精度為O(nL)，所需內存為O(nm+n2)個數的數組，而數組內的數的長度為O(nL)。這裡L是整個問題m輸入長度，又因一個線性規劃問題利用對偶理論很容易將多項式等價地化為一個線性不等式組的相容性問題，從而該算法提供了一個解線性規劃的多項式算法。算法的理論價值是重大的，但由於其要求精度過高而不太實用。針對這一問題刺激起了對線性規劃內點法的研究，具有重大實用價值的卡麥卡算法即為其中的重要成果。哈奇安由於本文的成果曾獲國際運籌學獎。

作者簡介

Л.Г.哈奇安(Л.Г.Хациян)，蘇聯數學家。

工具書指南

工具書品種和數量的日益增多，使人們面臨着一個如何選擇的問題，首先要知道有哪些關於解決該問題的工具書可利用，這些工具書以哪本為善，這就需要有工具書的工具書（也稱工具書指南）^[1]——工具書指南大體分為三類：

1.以教學為目的：以培養學生的情報意識，提高他們在學習和科學研究活動中利用工具書解答疑難和獨立檢索文獻的能力為主要目標。結合教學要點介紹常用的、重要的和最新出版的工具書，如：《中文工具書使用法》等。

2.以普及工具書知識為目的：既給讀者提供有關文獻和工具書的基礎知識，同時，或以工具書類型為綱重點介紹重要的工具書，或以問題為線索，重點介紹常用的工具書^[2]，如：《參考工作與參考工具書》等。

3.工具書的工具書：讀者按它的指引，知道解決某一門有什麼工具書可供查考，從而開拓視野，提高學習與科研的效率，如《中國工具書大辭典》等。

視頻