1
METODA ANALITYCZNA
Postać klasyczna:
z =
5 x
1
+ 6x
2
→
→
→
→
MAX
0,2 x
1
+ 0,3x
2
< 18
0,6 x
1
+ 0,6x
2
< 48
x
1
, x
2
> 0
cx
→
→
→
→
MAX
Ax < b
x > 0
Postać standardowa (kanoniczna):
z =
5 x
1
+ 6x
2
+ 0x
3
+ 0x
4
→
→
→
→
MAX
0,2 x
1
+ 0,3x
2
= 18
- x
3
0,6 x
1
+ 0,6x
2
= 48
- x
4
x
3
, x
4
– zmienne swobodne (niewykorzystane
moce produkcyjne przy produkcji frytek x
3
oraz przy produkcji puree x
4
)
z =
5 x
1
+ 6x
2
+ 0x
3
+ 0x
4
→
→
→
→
MAX
0,2 x
1
+ 0,3x
2
+ x
3
= 18
0,6 x
1
+ 0,6x
2
+ x
4
= 48
x
1
, x
2
, x
3
, x
4
> 0
2
cx
→
→
→
→
MAX
Ax = b
x > 0
A
–
macierz współczynników o wymiarach
(
m
×
n
),
x
–
n
-wymiarowy wektor zmiennych,
b
–
m
-wymiarowy wektor wyrazów wolnych,
c
–
n
-wymiarowy wektor wag funkcji celu.
B
– macierz kwadratowa
m
-tego stopnia,
składająca się z
m
liniowo niezależnych
kolumn macierzy
A
.
det (
B
)
≠
0
Macierz
B
–
baza
,
kolumny macierzy
B
–
kolumny
bazowe
,
pozostałe
kolumny
macierzy
A
–
kolumny niebazowe
.
Zmienne związane z kolumnami bazowymi
–
zmienne bazowe
,
pozostałe zmienne
–
zmienne niebazowe
.
Z każdą bazą
B
układu
Ax = b
jest związane
rozwiązanie bazowe.
3
Jeżeli układ
Ax = b
jest niesprzeczny oraz
n > m
to układ ten ma nieskończenie wiele
rozwiązań, ale skończoną liczbę rozwiązań
bazowych.
Układ
m
równań z
n
zmiennymi ma
co
najwyżej
m
n
rozwiązań bazowych, czyli:
)!
m
n
(
!
m
!
n
−
Rozwiązanie bazowe układu
Ax = b
:
- wybieramy
m
liniowo niezależnych kolumn
macierzy
A
, czyli bazę
B
,
- zmienne niebazowe przyjmują wartości
zerowe (
x
n
= 0
),
- wartości zmiennych bazowych ustalamy
rozwiązując
układ
m
równań
z
m
niewiadomymi:
Bx
b
= b.
Jeżeli każda zmienna bazowa jest różna od
zera, to takie rozwiązanie bazowe jest
niezdegenerowane.
Jeżeli zadanie programowania liniowego ma
rozwiązanie
optymalne,
to
ma
także
rozwiązanie optymalne bazowe
.
4
Rozwiązania optymalnego wystarczy szukać
wśród rozwiązań bazowych, których liczba
jest skończona
.
Można
znaleźć
rozwiązanie
optymalne
dokonując
przeglądu
zupełnego
zbioru
wszystkich rozwiązań bazowych.
Przykład:
z =
5 x
1
+ 6x
2
+ 0x
3
+ 0x
4
→
→
→
→
MAX
0,2 x
1
+ 0,3x
2
+ x
3
= 18
0,6 x
1
+ 0,6x
2
+ x
4
= 48
x
1
x
2
x
3
x
4
Macierz
A
:
0,2 0,3
1
0
0,6 0,6
0
1
m=2, n=4
mamy zatem co najwyżej:
n
4
n!
4!
6
m
m!(n m)!
2
2!2!
=
=
=
=
−
rozwiązań bazowych.
x
1,
x
2
x
1,
x
3
x
1,
x
4
x
2,
x
3
x
2,
x
4
x
3,
x
4
7
Przykład:
Firma
produkująca
3
rodzaje
soków
owocowych (wieloowocowe, pomarańczowe i
jabłkowe) dostała zamówienie na dokładnie 40
tys. kartonów 1-litrowych. Zleceniodawca
miał określone preferencje co do struktury
asortymentowej
zamówienia.
Soków
wieloowocowych ma być w partii co najmniej
5 tys. kartonów, zaś soków jabłkowych nie
więcej niż 16 tys. kartonów. Zysk netto przy
produkcji każdego rodzaju z soków wynosi
odpowiednio 8, 9 i 10 groszy/karton. Ile
soków każdego rodzaju należy wyprodukować
aby zmaksymalizować całkowity zysk netto ze
sprzedaży?
Jak
kształtuje
się
struktura
8
asortymentowa zrealizowanego zamówienia?
Zastosować
w
rozwiązaniu
metodę
analityczną.
x
1
– wielkość dostawy soków wieloowocowych,
x
2
– wielkość dostawy soków pomarańczowych,
x
3
– wielkość dostawy soków jabłkowych.
Postać klasyczna:
z =
8x
1
+ 9x
2
+10 x
3
→
→
→
→
MAX
x
1
+ x
2
+ x
3
= 40
x
1
> 5
x
3
< 16
x
1
, x
2
, x
3
> 0
Postać standardowa:
z =
8x
1
+ 9x
2
+10x
3
+0x
4
+ 0x
5
→
→
→
→
MAX
x
1
+ x
2
+ x
3
= 40
x
1
= 5
+ x
4
x
3
= 16
- x
5
x
4
– nadwyżka dostawy soków wieloowocowych
ponad minimalny limit,
x
5
– niedobór dostawy soków jabłkowych w
stosunku do maksymalnego limitu.
11
x
2
+x
3
=40
wektory
liniowo
zależne
x
3
+ x
5
=16
x
2
x
3
x
5
mnożymy
x
3
przez (-1)
x
2
x
3
x
5
suma
1
1
0
1
-1
0
0
0
0
0
0
0
0
0
0
1
1
0
-1
1
0
9)
x
2
, x
4
, x
5
10)
x
3
, x
4
, x
5
mamy
więc
dokładnie
8
rozwiązań
bazowych:
Zmienne
Zmienne bazowe
1
3
4
5
6
7
9
10
x
1
5
5
24
5
40
0
0
0
x
2
19
35
0
0
0
24
40
0
x
3
16
0
16
35
0
16
0
40
x
4
0
0
19
0
35
-5
-5
-5
x
5
0
16
0
-19 16
0
0
16
z
371
MAX
355 352 sprz. 320 sprz. sprz. sprz.
z =
8x
1
+ 9x
2
+10 x
3
→
→
→
→
MAX
x
1
+ x
2
+ x
3
= 40
x
1
> 5
x
3
< 16
x
1
, x
2
, x
3
> 0
12
Zadania do rozwiązania
Zadanie 1:
z=
1,2x
1
+1,8x
2
→
MIN
2 x
1
+ x
2
> 40
x
1
+3x
2
> 60
x
1
+x
2
> 30
x
1,
x
2
> 0
Rozwiązać przykład metodą graficzną i
analityczną. Sprawdzić rozwiązanie w winqsb.
Rozwiązanie:
x
1
=15, x
2
=15, x
3
=5, x
4
=0, x
5
=0, z
MIN
=45
Zadanie 2:
z=
2x
1
+3x
2
+0x
3
+0x
4
→
MAX
x
1
+2x
2
+x
3
= 4
x
1
-x
4
= 2
x
1,
x
2
,x
3
, x
4
> 0
Rozwiązać przykład metodą analityczną.
Sprawdzić rozwiązanie w winqsb.
Rozwiązanie:
x
1
=4, x
2
=0, x
3
=0, x
4
=2, z
MAX
=8
