字典序法

字典序法(dictionary ordered method)一種攝動法.由丹齊克(Dantzig,G. B.)於1954年提出，格莫理(Uomory, R. E.)在關於解整數線性規劃問題的文

簡介

字典序法(dictionary ordered method)一種攝動法.由丹齊克(Dantzig,G. B.)於1954年提出，格莫理(Uomory, R. E.)在關於解整數線性規劃問題的文章中又提到字典序法，且敘述得更加完整.設，一((v},vz}"..}v)是n維空間中一個向量.若v的第一個非零分量是正的，則稱它是字典式正的，記為v扮0.若兩個向量“，，，有，一“扮0，則稱向量“字典式大於“.關於向量序列{;‘}，若對所有的t都有，件‘-v`}0r.，則稱{ v`}是字典式增加的·若一個向量V滿足一，扮0，則稱，是字典式負的·記為，不0.若，一“不0，則稱，字典式小於“·記號，亨0，表示“一0或，扮0.在單純形法中，用v表示單純形表中與基變數二對應的行的係數向量.出基變數的選擇法則為:設}k>o，選定二k是人基變數，令sk= }z I b;k>o,t Es}，其中s為基變數指標集合，作“-vLl bik }Z } sk}.若“;是這些向量“中字典式最小的，即

u,=lex min u; (lex min代表字典式最小)i〔18則選二廠為出基變數.這樣選擇出基變數是不會產生循環的(參見“換基疊代”).

提出者

丹齊克，G.B.

George Bernard Dantzig (1914.11.8～ )

美國數學家，美國全國科學院院士。線性規劃的奠基人。

生平

1914年11月8日生於美國俄勒岡州波特蘭市。在馬里蘭大學獲數學和物理學學士學位。在密西根大學獲數學碩士學位。

1946年在伯克利加利福尼亞大學數學系獲哲學博士學位。

1974年丹齊克在總結前人工作的基礎上創立了線性規劃,確定了這一學科的範圍,並提出了解決線性規劃問題的單純形法。

1937～1939年任美國勞工統計局統計員。

1941～1952年任美國空軍司令部數學顧問、戰鬥分析部和統計管理部主任。

1952～1960年任美國蘭德公司數學研究員。

1960～1966年任伯克利加利福尼亞大學教授和運籌學中心主任。

1966年後任史丹福大學運籌學和計算機科學教授。

1971年當選為美國全國科學院院士。

1975年獲美國科學獎章和諾伊曼理論獎金。丹齊克還獲馬里蘭大學、耶魯大學、瑞典林雪平大學的以色列理工學院的名譽博士學位。丹齊克是美國運籌學會和國際運籌學會聯合會 (IFORS)的主席和美國數學規劃學會的創始人。他發表過100多篇關於數學規劃及其套用方面的論文。

1963年出版專著《線性規劃及其範圍》，這本著作至今仍是線性規劃方面的標準參考書。