Optymalizacja

Ewa Skubalska-Rafajłowicz

Wrocław 2010

George

Dantzig

1914 - 2005



Twórca metody SIMPLEX
1947

Linear programming is viewed as a revolutionary
development giving man the ability to state
general objectives and to find, by means of the
simplex method, optimal policy decisions for a
broad class of practical decision problems of
great complexity. In the real world, planning
tends to be ad hoc because of the many special-
interest groups with their multiple objectives.

Programowanie liniowe

Postać standardowa

Przykład:

Aproksymacja

Chebysheva

Przepływy



Maksymalny przepływ



Przepływ minmalnokosztowy



Zagadnienie transportowo-kosztowe



Rozwiązania całkowitoliczbowe-



Macierz ograniczeń A totalnie
unimodularna (b całkowitoliczbowe)

Minimum Fuel Problem:

Zadeh Whalen 1962

Istnienie rozwiazania

Ax=b:



Twierdzenie Kronecera-Cappelli



rząd(A)=rząd(Ab)

Niedookreślony układ

równań



A macierz m x n, m< n



Istnieje nieskończenie wiele
rozwiązań



Zbiór rozwiązań dopuszczalnych



= Simplex

–

Rozwiązanie optymalne LP, jeśli

istnieje, leży w wierzchołku simplexu.

Transformacja Ax (m<n)



Nie jest różnowartościowe



Przestrzeń Rn przekształca na całą

przestrzeń Rm



Rozwiązanie minimalizujące normę



Rozwiązanie bazowe dla kryterium cx

Przedstawienie bazowe

Rozwiązanie bazowe

Ax=[B I ]x=b

I iteracja Simplex

X1 – w5

optimum

Brak ograniczenia na

zmienną

(nieograniczone

rozwiązanie)