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)