Matematyczny elementarz optymalizacji liniowej

Opinie czytelników

Obecnie brak opinii czytelników. Ocena opiera się na 4 głosach.

Oryginalny tytuł:

A Mathematical Primer on Linear Optimization

Zawartość książki:

Książka stanowi samodzielne matematyczne wprowadzenie do optymalizacji liniowej dla studentów studiów licencjackich z matematyki. Książka ta jest również odpowiednia dla studentów nauk ścisłych, inżynierii i ekonomii, którzy są zainteresowani głębszym zrozumieniem matematycznych aspektów tego tematu.

Problem optymalizacji liniowej jest analizowany z różnych perspektyw: topologicznej, algebraicznej, geometrycznej, logicznej i algorytmicznej. Niemniej jednak, nie jest wymagana wcześniejsza znajomość tych zagadnień. Istotne szczegóły są zawsze podawane w specjalnej sekcji na końcu każdego rozdziału.

Materiał techniczny jest zilustrowany wieloma przykładami, problemami z w pełni opracowanymi rozwiązaniami oraz szeregiem proponowanych ćwiczeń.

W rozdziale 1 przedstawiono kilka sformułowań problemu optymalizacji liniowej i powiązano je w odniesieniu do dopuszczalnych wektorów i optymalizatorów. Następnie, w rozdziale 2 omówiono warunki wystarczające istnienia optymalizatorów oparte na technikach topologicznych.

Głównym celem rozdziału 3 jest przedstawienie sposobu decydowania o tym, czy dopuszczalny wektor jest optymalizatorem, opierając się na Lemacie Farkasa. W rozdziale 4 algebra liniowa jest używana do obliczania optymalizatorów za pomocą podstawowych wektorów dopuszczalnych. Geometryczna charakterystyka tych wektorów jest celem rozdziału 5.

Dualność jest omówiona w rozdziale 6, dając nową technikę znajdowania optymalizatorów. W rozdziale 7 przedstawiono wprowadzenie do złożoności obliczeniowej w celu analizy wydajności algorytmów optymalizacji liniowej. Wykazano, że złożoność algorytmu brute-force nie jest wielomianowa.

Rozdział 8 poświęcony jest algorytmowi Simplex. Zawiera dowód jego poprawności i kompletności oraz wyjaśnienie jego złożoności innej niż wielomianowa.

Wreszcie, rozdział 9 koncentruje się na problemie optymalizacji liczb całkowitych z naciskiem na całkowitą jednomodularność. Analizowany jest algorytm oparty na technice Branch and Bound.