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)