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)