wzbo-wyklad nr 2, MATERIAŁY DYDAKTYCZNE, WYBRANE ZAGADNIENIA BADAŃ OPERACYJNYCH
[ Pobierz całość w formacie PDF ]
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2: Postacie zadań programowania liniowego, graficzna metoda rozwiązywania zadań PL
__________________________________________________________________________________________
POSTACIE ZADAŃ PROGRAMOWANIA LINIOWEGO
Zadanie decyzyjne, w którym wszystkie relacje są
liniowe
oraz wszystkie zmienne są
ciągłe
, nazywamy
zadaniem
programowania liniowego (PL)
.
Ogólna postać zadania PL jest następująca:
∑
=
n
c
j
x
→
max
(min),
j
( . )
j
1
∑
=
n
(
)
a
x
≤
b
i
=
1
2
…
,
m
ij
j
i
( . )
j
1
∑
=
n
(
)
a
x
≥
b
i
=
m
+
1
…
,
p
ij
j
i
( . )
j
1
∑
=
n
(
)
a
ij
x
j
=
b
i
i
=
p
+
1
…
,
r
( . )
j
1
(
)
x
j
≥
0
j
=
1
2
…
,
n
1
( . )
gdzie
1
nn
≤
.
Każdy wektor zmiennych decyzyjnych
x
=
(
x
1
,
x
2
,
…
,
x
n
)
spełniających warunki ograniczające (2.2) – (2.5) nazywamy
rozwiązaniem dopuszczalnym
zadania PL. Rozwiązanie
dopuszczalne, dla którego funkcja celu (2.1) osiąga maksimum
(minimum), nazywamy
rozwiązaniem optymalnym
.
Parametrami w tym zadaniu są
c
j
,
b
i
oraz
a
ij
)
i
1
2
…
=
,
r
;
j
1
2
…
,
n
38
=
. Parametr
c
j
nazywamy
j
-tą
wagą
funkcji celu
, parametr
b
i
-
i
-tym
wyrazem wolnym
, a parametr
a
ij
–
współczynnikiem macierzy ograniczeń
stojącym w
i
-tym wierszu
i
j
-tej kolumnie.
(
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2: Postacie zadań programowania liniowego, graficzna metoda rozwiązywania zadań PL
__________________________________________________________________________________________
POSTACIE ZADAŃ PROGRAMOWANIA LINIOWEGO, c.d.
Zadaniem PL o
postaci standardowej
nazywamy zadanie,
w którym wszystkie ograniczenia są nierównościami typu
≤
dla
zadań na maksimum bądź nierównościami typu
≥
dla zadań na
minimum oraz wszystkie zmienne muszą być nieujemne.
Zadaniem PL o
postaci kanonicznej
nazywamy zadanie, w
którym wszystkie warunki ograniczające są równaniami oraz na
wszystkie zmienne nałożone są warunki dotyczące ich
nieujemności.
Zadaniami PL o postaci standardowej są więc:
∑
=
n
∑
=
c
j
x
→
max,
c
j
x
→
min,
j
j
j
1
j
1
∑
=
n
(
)
∑
=
(
)
a
x
≤
b
i
=
1
2
…
,
m
a
x
≥
b
i
=
1
…
2
,
m
ij
j
i
,
ij
j
i
,
j
1
j
1
(
)
)
x
j
≥
0
…
j
=
2
,
n
.
x
j
≥
0
…
(
j
=
2
,
n
. (2.6)
UWAGA !
Nierówność
≤
dla zadania na maksimum oraz nierówność
≥
dla zadania na minimum nazywamy
nierównościami typowymi
, a
samo zadanie będziemy oznaczali: PL(max) lub PL(min).
39
n
n
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2: Postacie zadań programowania liniowego, graficzna metoda rozwiązywania zadań PL
__________________________________________________________________________________________
DUALNOŚĆ, REGUŁY TWORZENIA ZADANIA DUALNEGO
Z każdym zadaniem PL (zwanym pierwotnym lub
prymalnym) sprzężone jest pewne inne zadanie PL zwane
zadaniem dualnym (ZD)
.
Jeżeli
zadaniem pierwotnym
(ZP)
jest zadanie:
∑
n
c
x
→
max,
j
j
j
=
1
n
∑
(
)
a
x
≤
b
i
=
1
2
…
,
m
,
ij
j
i
j
=
1
( . )
(
)
x
j
≥
0
j
=
1
2
…
,
n
,
to
zadaniem dualnym (ZD)
będzie zadanie:
∑
m
by
→
min,
ii
i
=
1
∑
m
(
)
ay c j
≥ =
1, 2, , ,
…
n
ji i
j
i
=
1
( . )
(
)
y
i
≥ =
0
i
1, 2, , .
…
m
Z relacji zachodzących między zadaniem pierwotnym a zadaniem
dualnym wynika, że:
1.
w zadaniu dualnym jest tyle zmiennych, ile nierówności w zadaniu
pierwotnym (każdemu warunkowi ZP odpowiada jedna zmienna ZD),
2.
w zadaniu dualnym jest tyle warunków, ile zmiennych w zadaniu
pierwotnym,
3.
wagi funkcji celu zadania pierwotnego są wyrazami wolnymi
w zadaniu dualnym,
4.
wyrazy wolne zadanie pierwotnego są wagami funkcji celu
w zadaniu dualnym,
5.
macierz współczynników zadania dualnego jest transpozycją macierzy
współczynników zadania pierwotnego,
6.
jeżeli zadanie jest na maksimum, to dualne jest na minimum
i odwrotnie.
40
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2: Postacie zadań programowania liniowego, graficzna metoda rozwiązywania zadań PL
__________________________________________________________________________________________
REGUŁY TWORZENIA ZADANIA DUALNEGO, c.d.
W przypadku ogólnym stosujemy ponadto następujące,
dodatkowe reguły tworzenia zadania dualnego
:
1.
jeżeli w ZP
i
-ty warunek jest równością, to odpowiadająca mu
zmienna
y
i
nie ma ograniczeń,
2.
jeżeli w ZP
i
-ty warunek jest nietypową nierównością, to w ZD
zmienna
y
i
≤
0,
3.
jeżeli w ZP na zmienną
x
i
nie nałożono ograniczeń, to
i
-ty
warunek ZD jest równością,
4.
jeżeli w ZP zmienna
x
i
≤
0, to w ZD
i
-ty warunek jest nietypową
nierównością.
PRZYKŁAD 2.1
Mamy następujące zadanie pierwotne o postaci standardowej:
2
x
1
+
3
x
2
+
x
3
→
min,
zmienne dualne:
4
x
1
−
6
x
2
+
5
x
3
≥
4
y
1
,
Å
(ZP)
y
2
x
+
2
x
+
4
x
≥
7
1
2
3
x
1
,
x
2
,
x
3
≥
0
W zadaniu dualnym będą oczywiście dwie zmienne
y
1
,
y
2
, gdyż
w ZP występują dwa ograniczenia (co zaznaczono przy ZP),
a samo zadanie dualne do rozważanego zadania ZP ma postać:
4
y
1
+
7
y
2
→
max,
4
y
1
+
y
2
≤
2
−
6
y
1
+
2
y
2
≤
3
(ZD)
5
y
+
4
y
≤
1
1
2
y
1
,
y
2
≥
0
.
41
Wybrane zagadnienia badań operacyjnych
dr inż. Zbigniew Tarapata
Wykład nr 2: Postacie zadań programowania liniowego, graficzna metoda rozwiązywania zadań PL
__________________________________________________________________________________________
REGUŁY TWORZENIA ZADANIA DUALNEGO, c.d.2
PRZYKŁAD 2.2
Należy utworzyć zadanie dualne do następującego zadania
pierwotnego:
6
x
1
+
8
x
2
→
max,
zmienne dualne:
4
x
1
+
6
x
2
≤
10
,
y
1
≥ 0,
3
x
1
+
x
2
=
4
Å
(ZP)
y
2
– dowolne,
2
x
1
+
2
x
2
≥
2
y
3
≤ 0.
x
1
−
dowolne,
x
2
≥
0
,
Zadanie dualne będzie miało trzy zmienne (bo w ZP występują
trzy ograniczenia) i
d
w
a
w
a
r
u
n
k
i
o
g
r
a
n
i
c
z
a
j
ą
ą
c
e
(bo w ZP
występują
d
w
i
e
z
m
i
e
n
n
e
):
10
y
1
+
4
y
2
+
2
y
3
→
min,
4
y
1
+
3
y
2
+
2
y
3
=
6
6
y
1
+
y
2
+
2
y
3
≥
8
(ZD)
y
1
≥
0
y
2
−
dowolne
,
y
3
≤
0
.
42
[ Pobierz całość w formacie PDF ]