Computational Techniques of the Simplex Method - 9781402073328

Programowanie liniowe (LP) jest prawdopodobnie najczęściej stosowaną techniką optymalizacji. Jednym z powodów jego szerokiego zastosowania jest to, że istnieją bardzo wydajne algorytmy rozwiązań do optymalizacji liniowej. Programy komputerowe oparte na metodzie simpleksowej lub punktowej wewnętrznej są w stanie rozwiązywać problemy o bardzo dużej skali z dużą niezawodnością i rozsądnym czasem. Konstruktorzy modeli są tego świadomi i często starają się formułować w tych ramach rzeczywiste problemy, aby mieć pewność, że można je skutecznie rozwiązać. Prawdą jest również, że wiele rzeczywistych problemów optymalizacyjnych można sformułować jako modele prawdziwie liniowe, a także wiele innych można z powodzeniem aproksymować za pomocą linearyzacji. Dwie główne metody rozwiązywania problemów LP to warianty metody sympleksowej i metody punktu wewnętrznego (IPM). Okazuje się, że oba warianty mają swoją rolę w rozwiązywaniu różnych problemów. Stwierdzono, że od czasu wprowadzenia IPM wydajność solwerów opartych na simpleksach wzrosła o dwa rzędy wielkości. Tę zwiększoną efektywność można przypisać następującym czynnikom: rozwojowi teoretycznemu podstawowych algorytmów, włączeniu wyników informatyki, zastosowaniu zasad inżynierii oprogramowania i uwzględnieniu najnowocześniejszego stanu techniki komputerowej. Książka ta oferuje systematyczne omówienie skupione na zagadnieniach obliczeniowych metody simplex. Celem jest przedstawienie wystarczających szczegółów na temat wszystkich aspektów niezbędnych do jego pomyślnego wdrożenia. Na podstawie systematycznego opracowania książki zaowocują wysokiej jakości wdrożeniami. Dodatkowo wiele z przedstawionych tutaj procedur i technik można wykorzystać także do efektywnej implementacji innych algorytmów optymalizacyjnych.