Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
EiT III r
.
.
Sub
Sub
-
-
kier
kier
. EKA
. EKA
Teoria dualności dla zadania programowania liniowego PL
x
c
T
x
=
0
max
0
≥
≤
x
b
x
A
0
≥
≥
v
c
v
A
T
b
v
v
T
=
0
min
Twierdzenie 7.1 :
Jeśli wektor x jest rozwiązaniem dopuszczalnym dla zadania prymalnego i
wektor v jest rozwiązaniem dopuszczalnym dla zadania dualnego, to wartość
funkcji celu w zadaniu dualnym nie może być mniejsza od wartości funkcji
celu w zadaniu prymalnym.
x
c
b
v
T
T
≥
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
EiT III r
.
.
Sub
Sub
-
-
kier
kier
. EKA
. EKA
Teoria dualności dla zadania PL cd.
∧
∧
v
i
x
∧
∧
=
v
b
x
c
T
T
0
=
∧
∧
v
x
T
Twierdzenie 7.2
Dla pary rozwiązań optymalnych zadania prymalnego PL i zadania
dualnego PL zachodzi warunek:
Twierdzenie 7.3
Niech (x
r
,x
s
) i ( v
r
, v
s
) będą odpowiednio rozwiązaniami dopuszczalnymi zadania
prymalnego i dualnego, przy czym x
s
i v
s
są wektorami zmiennych dopełniających
do postaci kanonicznej zadania w wektorach rozwiązań.
Wtedy i będą odpowiednio rozwiązaniami optymalnymi pary zadań
prymalnego i dualnego, jeśli zachodzi warunek komplementarności zmiennych:
tzn.
0
=
+
∧
∧
∧
∧
r
T
s
s
T
r
v
x
v
x
)
,
(
s
x
x
r
∧
∧
)
,
(
s
v
v
r
∧
∧
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
EiT III r
.
.
Sub
Sub
-
-
kier
kier
. EKA
. EKA
Twierdzenie 7.3
Jeśli zadanie dualne jest nieograniczone, to zadanie prymalne jest sprzeczne.
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
EiT III r
.
.
Sub
Sub
-
-
kier
kier
. EKA
. EKA
Przykład I zadanie prymalne
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
≥
≥
+
+
≥
+
−
=
0
,
,
1
2
2
6
:
3
2
1
3
2
1
3
2
1
v
v
v
v
v
v
v
v
v
x
V
3
2
1
0
21
0
5
min
v
v
v
v
V
v
+
+
=
∈
Przykład II System cięcia dłużyc
3
2
1
0
2
.
0
6
.
0
3
.
0
min
v
v
v
v
+
+
=
0
,
,
1200
2
1
0
2100
0
3
7
3
2
1
3
2
1
3
2
1
≥
≥
+
+
≥
+
+
v
v
v
v
v
v
v
v
v
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
≤
+
=
0
,
2
.
0
2
0
6
.
0
1
3
3
.
0
0
7
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
Postać wektora rozwiązań:
[
] [
]
5
4
3
2
1
,
,
,
,
v
v
v
v
v
v
v
v
s
r
=
=
[
] [
]
5
4
3
2
1
,
,
,
,
x
x
x
x
x
x
x
x
s
r
=
=
[
] [
]
0
,
,
0
=
⇒
=
r
s
T
s
r
T
v
v
x
x
v
x
zadanie dualne
Technika optymalizacji
Dr inż. Ewa Szlachcic
Wydział Elektroniki
EiT III r
.
.
Sub
Sub
-
-
kier
kier
. EKA
. EKA
Teoria dualności dla zadania PL
cd.
2
1
0
1
2
max
x
x
X
x
+
=
∈
x
≥
≤
+
≤
+
−
≤
+
=
0
,
21
2
6
0
5
1
1
:
2
1
2
1
2
1
x
x
x
x
x
x
x
x
X
2
6
21
x
5
1
-1
0
x
4
1
1
5
x
3
-1
-2
0
x
0
x
2
x
1
Zadanie dualne:
I. Rozwiązanie zadania dualnego metodą simpleks
Rozwiązanie optymalne:
a)
Zadanie dualne
b)
Zadanie prymalne
Wartość optymalna funkcji celu:
1/3
1/6
7/2
x
1
4/3
1/6
7/2
x
4
2/3
-1/6
3/2
x
3
-1/3
1/3
7
x
0
x
2
x
5
-1/2
1/4
11/4
x
1
-2
1/2
1/2
x
4
3/2
-1/4
9/4
x
2
1/2
1/4
31/4
x
0
x
3
x
5
[
]
[
]
3
2
1
5
4
5
4
3
2
1
,
,
,
,
,
,
,
,
v
v
v
v
v
v
x
x
x
x
x
x
↑
=
↑
=
∧
∧
↑
=
↑
=
∧
∧
4
1
,
0
,
2
1
,
0
,
0
0
,
2
1
,
0
,
4
9
,
4
11
v
x
4
31
0
0
=
=
∧
∧
v
x
Wyszukiwarka
Podobne podstrony:
7w to wlasnosci 2011
Introduction to VHDL
Biopreparaty co to
Co to za owoc
Let´s go to England Interm
Wykład 7w
Przemyśl to
CHCESZ SIĘ ODCHUDZIĆ TO NIE OGLĄDAJ TEGO !!!!!!!!!!
Klastry turystyczne, pochodzenie nazwy, co to
higiena to nie tylko czystośc ciała
EDoc 6 Co to jest podpis elektroniczny slajdy
więcej podobnych podstron