Wyk lad 9- sem II 2012/2013

Parametryczna optymalizacja liniowa Rozważamy standardowa pare zadań du-

֒

֒

alnych

cT x → max

bT y → max

przy ograniczeniach

(P )

(D) przy ograniczeniach A · x = b

AT · y ≤ c

x ≥ 0

Za lożenia:

A, m × n, m ≤ n A - pe lnego rzedu,

֒

x ∈ Rn, c ∈ Rn, b ∈ Rm

zbiór rozwiazań dopuszczalnych zadania

֒

dualnego (D) jest niepusty Rozwiazania i wartość optymalna zależa

֒

֒

od danych zadania: A, b, c

Analiza parametryczna: jak zmienia sie֒

zbiór rozwiazań optymalnych oraz wartość

֒

optymalna jako funkcje danych A, b, c 1

1

I. Zależ ność wartości optymalnej i rozwiazań

֒

od wektora prawych stron

Zak ladamy, że A i c sa ustalone, zmienia

֒

sie b

֒

Zbiór dopuszczalny zadania (P ) zależy od b:

P (b) := {x ∈ Rn : Ax = b, x ≥ 0}

wartość optymalna (P ) zależy od b: V P

min(b) := min{cT x

: x ∈ P (b)}, zbiór rozwiazań optymalnych zależy od b:

֒

S(b) := {x ∈ P (b) : cT x = Vmin(b)}.

TRZY ODWZOROWANIA:

1. Odwzorowanie wielowartościowe zbioru dopuszczalnego: P : Rm ⇒ Rn P(b) := P (b) 2. Funkcja V P :

min

Rm → R ∪ {±∞}

3. Odwzorowanie wielowartościowe zbioru optymalnego: S : Rm ⇒ Rn

S(b) := S(b) 2

Dziedzina odwzorowania wielowartościowego P:

domP := {b ∈ Rm : P(b) = P (b) 6= ∅}

domP

= {b ∈ Rm : ∃ x ∈ Rn x ≥ 0 Ax = b}

= {Ax, |x ≥ 0}

= {b ∈ Rm : V D > −∞}

max

Twierdzenie 1.1 Mamy nastepujace w lasności

֒

֒

1. domP jest zbiorem wypuk lym

2. Funkcja V P

jest funkcja wypuk la.

min

֒

֒

3