В математической оптимизации алгоритм Лемке — это процедура решения задач линейной дополнительности , и в более общем случае смешанных задач линейной дополнительности . Он назван в честь Карлтона Э. Лемке .
Алгоритм Лемке относится к типу поворота или базисного обмена . Аналогичные алгоритмы могут вычислять равновесия Нэша для двухсторонних матричных и биматричных игр .
Ссылки
- Коттл, Ричард В.; Панг, Джонг-Ши; Стоун, Ричард Э. (1992). Проблема линейной дополнительности . Компьютерные науки и научные вычисления. Бостон, Массачусетс: Academic Press, Inc. стр. xxiv+762 стр. ISBN 0-12-192350-9. МР 1150683.
- Murty, KG (1988). Линейная дополнительность, линейное и нелинейное программирование. Серия Sigma в прикладной математике. Том 3. Берлин: Heldermann Verlag. стр. xlviii+629 стр. ISBN 3-88538-403-5. Архивировано из оригинала 2010-04-01.(Доступно для скачивания на сайте профессора Катты Г. Мурти.) MR 949214
Внешние ссылки
- Руководство OMatrix по Lemke
- Презентация Криса Хеккера на GDC о MLCP и Лемке
- Линейная дополнительность и математическое (нелинейное) программирование
- Реализация алгоритма Лемке и других методов решения LCP и MLCP с открытым исходным кодом от Siconos /Numerics на языке C
