Wybrane zagadnienia
badań operacyjnych
badań operacyjnych
Wykład 2a
Metoda simpleks rozwiązywania zadań
programowania liniowego
Prowadzący: dr inż. Zbigniew TARAPATA
dr inż. Zbigniew TARAPATA
dr inż. Zbigniew TARAPATA
Dane kontaktowe:
e-mail: [e-mail]
[e-mail]
WWW: http://tarapata.strefa.pl
tel. : 83-94-13, 83-94-73
1
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
LINIOWEGO - PRZYPOMNIENIE
LINIOWEGO - PRZYPOMNIENIE
Przypomnijmy : Postać kanoniczna zadania optymalizacji
liniowej definiowana jest następująco:
Wyznaczyć x=(x1, x2, x3,..., xn) takie, aby
Wyznaczyć x (x1, x2, x3,..., x ) takie, aby
min f (x) = min{c1x1 + c2x2 + c3x3 + ...+ cnxn}
przy ograniczeniach:
n-zmiennych
a11x1 + a12x2 + a13x3 + ...+ a1nxn = b1
a21x1 + a22x2 + a23x3 + ...+ a2nxn = b2
21 1 22 2 23 3 2n n 2
m-ograniczeń
am1x1 + am2x2 + am3x3 + ...+ amnxn = bm
x1, x2, x3,..., xn e" 0
2
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
POSTAĆ KANONICZNA ZADANIA PROGRAMOWANIA
LINIOWEGO - PRZYPOMNIENIE
LINIOWEGO - PRZYPOMNIENIE
W zapisie wektorowo-macierzowym otrzymamy następującą
postać:
min c, x
A�" x = b x e" 0
gdzie:
c = [c1 ... cn]
x b
x1 b1
�ł łł �ł łł
a11 a12 ... a1n �ł łł �ł łł
�ł łł
�ł łł
�łx śł �łb śł
�ła a22 ... a2n śł
2 2
21 �ł śł �ł śł
�ł śł x = b =
A =
�ł śł �ł śł
... ...
�ł śł
... ... ... ...
�łx śł �łb śł
�ł śł
�ł n �ł �ł m �ł
am2 ... amn �ł
�łam1
3
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład
Wyznaczyć x=(x1, x2, x3) takie, aby
min{f (x) = 2x1 + 4x2 - x3}
Mamy trzy zmienne decyzyjne,
przy ograniczeniach:
dwa ograniczenia (n=3, m=2),
2x1 + 3x2 - 4x3 = 10
jednak postać ta jest postacią
kanoniczną.
4x1 - 5x2 + x3 = 5
W tym przypadku na przykład
a 2 a 4 a 5 b 10 itd
a11 =2, a13 =-4, a22 =-5, b1 =10 itd.
x1, x2, x3 e" 0
e" 0
Wszystkie zadania optymalizacji liniowej sprowadzić musimy
przede wszystkim do postaci kanonicznej.
4
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Sprowadzanie zadań optymalizacji liniowej do postaci kanonicznej
Sprowadzanie zadań optymalizacji liniowej do postaci kanonicznej
a) Jeśli szukamy zmiennych maksymalizujących funkcję
kryterium, to zamieniamy ją na przemnożoną przez (-1)
i wtedy szukamy już zmiennych minimalizujących nową
i wtedy szukamy już zmiennych minimalizujących nową
funkcję, tzn. max f(x) = min  f(x) ;
max f(x) =  min  f(x)
b) Jeśli mamy ograniczenie typu  e" , to od lewej strony
odejmujemy nową zmienną (tzw.  sztuczną ) i zamieniamy
nierówność na równość; współczynnik tej nowej zmiennej w
współczynnik tej nowej zmiennej w
funkcji kryterium wynosi 0 (zero);
funkcji kryterium wynosi 0(zero);
c) Jeśli mamy ograniczenie typu  d" , to do lewej strony
c) Jeśli mamy ograniczenie typu  d" , to do lewej strony
dodajemy nową zmienną (tzw.  sztuczną ) i zamieniamy
nierówność na równość; współczynnik tej nowej zmiennej w
współczynnik tej nowej zmiennej w
funkcji kryterium wynosi również 0 (zero).
funkcji kryterium wynosi również 0(zero).
5
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (sprowadzanie zadania do postaci kanonicznej)
Załóżmy, że mamy zadanie optymalizacji postaci :
max f (x) = max{x1 + x2} c = (1,1)
przy ograniczeniach:
p y g
2x1 + x2 d" 2
2 1 2
�ł łł �ł łł
�ł1 �ł1śł
A = 2śł b =
x1 + 2x2 e" 1
�ł śł �ł śł
�ł śł �ł
�ł
�ł3 4�ł �ł4śł
3x1 + 4x2 = 4
x1, x2 e" 0 x1
�ł łł
x =
�łx śł
�ł 2 �ł
6
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (cd.)
Sprowadz
my zadanie do postaci kanonicznej.
Najpierw zamieniamy  max na  min mnożąc funkcję przez  1:
max{x1 + x2} = - min{-x1 - x2 + 0�" x3 + 0�" x4}
2
�ł łł
�ł łł
�ł1śł
Zmieniamy ograniczenia
b =
c = (-1,-1,0,0)
�ł śł
2x1 + x2 + x3 = 2
�ł
�ł4śł
�ł
2 1 1 0
�ł łł
x1 + 2x2 - x4 = 1
�ł1
x1
�ł łł
A = 2 0 -1śł
�ł śł
3x1 + 4x2 = 4
1 2 �łx śł
�ł śł
�ł
�ł śł
2
�ł3 4 0 0 śł
�ł
�ł śł
x =
x1, x2 e" 0
�ł śł
x3
�łx śł
min c, x
Zapis wektorowo-macierzowy �ł 4 �ł
A �" x = b x e" 0
7
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
ELEMENTY ANALIZY WYPUKA
EJ
ELEMENTY ANALIZY WYPUKA
EJ
Definicja
Zbiór &! nazywamy wypukłym jeśli dla każdych dwóch punktów
x,y"&! punkt z= ��"x+(1-�)y należy do &! dla każdego �"[0,1].
x z y x z y
&! &!
&! - zbiór wypukły &! - zbiór, który nie jest wypukły
Definicja
j
Hiperpłaszczyzną Hą w przestrzeni En nazywamy zbiór
Hą ={x " En : a, x = ą, a " En,ą " R}
gdzie - iloczyn skalarny wektorów a oraz x.
8
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Definicja
Hiperpłaszczyzna Hą generuje dwie półprzestrzenie domknięte
- +
Hą ={x " En : a, x d" ą} Hą ={x " En : a, x e" ą}
Definicja
Definicja
Zbiorem wielościennym (simpleksem) nazywamy zbiór &! postaci
m
&! = {x " En : ai, x d" bi}
)"
i=1
Definicja
Definicja
Funkcja rzeczywista f określona na wypukłym zbiorze &! nazywa
nazywa
się wypukłą
się wypukłą, jeśli dla każdego x,y"&! oraz dla każdego �"[0,1]
spełniona jest nierówność
f (� �" x + (1-� ) �" y) d" � �" f (x) + (1-� )�" f (y)
9
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Jeśli natomiast spełniona jest nierówność
f (� �" x + (1-� ) �" y) e" � �" f (x) + (1-� )�" f (y)
to funkcję f nazywamy wklęsłą.
wklęsłą
Uwaga: funkcja liniowa f(x)= j j yp
gj ( ) , jest jednocześnie wypukła i
wklęsła.
Twierdzenie
m
Funkcja postaci
F(x) =
" �" fi (x), i e" 0, i = 1,..., m
i
i=1
j t kł j śli f ( ) kł i 1
jest wypukła, jeśli fi(x) są wypukłe, i=1,...,m.
Wniosek
&! ={x " En : A�" x = b, x e" 0}
Zbiór postaci
gdzie A=[aij]mxn jest wypukły.
10
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Sformułujemy dwa zadania:
a. wyznaczyć x*"&!�"En takie, że
f (x*) = min f (x)
x"&!
gdzie &! - zbiór wypukły, f(" )  funkcja wypukła,
b. wyznaczyć x*"&!�"En takie, że
f (x*) = max f (x)
x"&!
gdzie &! yp y, ( ) j ę ,
g - zbiór wypukły, f(" )  funkcja wklęsła,
Oba zadania nazywane są w literaturze zadaniami wypukłymi.
Dalej zajmować się będziemy rozwiązywaniem zadań wypukłych.
11
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
METODY ROZWI
ZYWANIA ZADAC
LINIOWYCH
METODY ROZWI
ZYWANIA ZADAC
LINIOWYCH
Na wykładzie nr 2 poznaliśmy metodę geometryczną
metodę geometryczną
rozwiązywania zadań programowania liniowego. Metoda ta
miała pewne ograniczenia:
ż ć lk d ki h d ń k ó h li b i h i
" może zostać zastosowana tylko do takich zadań, w których liczba zmiennych wynosi
2 (ewentualnie liczba ograniczeń wynosi 2  wówczas możemy skonstruować
zadanie dualne i rozwiązać je metodą graficzną);
" nie nadaje się ona do algorytmizacji i komputerowej implementacji (stosujemy
wówczas najbardziej znaną metodę rozwiązywania zadań PL  tzw. algorytm
simpleks);
" pozwala w prosty sposób zidentyfikować tzw. zadania ze sprzecznymi
ograniczeniami oraz nieograniczoną wartością funkcji celu (o liczbie zmiennych
równej 2).
" Metodą, która nadaje się do automatyzacji (zatem można ją
algorytmizować i wykorzystywać komputer) oraz którą można
stosować przy wielu zmiennych i ograniczeniach jest
metoda (algorytm) simpleks
metoda (algorytm) simpleks.
12
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Twierdzenie (wykorzystywane przez algorytm simpleks)
Jeśli zadanie prymalne ma rozwiązanie optymalne x*"&! to
istnieje wierzchołek x"&! zbioru &! taki, że
c, x = c,x* = min c, x
, , ,
x"&!
przy czym &! oznacza zbiór rozwiązań dopuszczalnych.
Zatem, jeśli zadanie liniowe ma rozwiązanie optymalne, to
wystarczy przeglądać tylko wierzchołki zbioru
wystarczy przeglądać tylko wierzchołki zbioru &!, aby znalez
ć
rozwiązanie będące minimum globalnymnazbiorze &!.
Metody wyznaczania rozwiązań optymalnych zadań liniowych
polegają na ogół na konstrukcji algorytmów przeglądu
wierzchołków wielościanów wypukłych (simpleksów).
13
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
METODA SIMPLEKS - idea
METODA SIMPLEKS - idea
Idea metody simpleks opiera się o przeglądanie wierzchołków
zbioru ograniczeń według pewnej ustalonej reguły, tak, aby nie
pominąć istotnych wierzchołków (w których może być rozwiązanie
optymalne), a jednocześnie, aby nie przeglądać wszystkich
wierzchołków, gdyż byłoby to zbyt czasochłonne;
wierzchołków, gdyż byłoby to zbyt czasochłonne;
Ponieważ wierzchołkiem zbioru ograniczeń jest punkt, w którym
przecinają się hiperpłaszczyzny (w szczególnym przypadku - proste),
patrz slajd nr 9, więc metoda simpleks polega na rozwiązywaniu
metoda simpleks polega na rozwiązywaniu
układu równań,
układu równań który generowany jest przez ograniczenia;
Jest to metoda krokowa (iteracyjna);
W każdym kroku budowana jest tzw. tabela simpleksowa na
tabela simpleksowa,
podstawie której wnioskujemy, czy otrzymane do tej pory rozwiązanie
jest już optymalne, czy jeszcze nie;
Ogólną postać tabeli simpleksowej przedstawiono na następnym
slajdzie.
14
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
METODA SIMPLEKS  tablica metody simpleks
METODA SIMPLEKS  tablica metody simpleks
ci
c1 c2 ... cn
Pogrubioną
czerwoną linią
Zmienne
cB h0 h1 h2 ... hn zaznaczono ten
bazowe
fragment tabeli
simpleksowej
xB1
cB1 h10 h11 h12 ... h1n simpleksowej,
który podlega
wyliczaniu w
xB2
cB2 h20 h21 h22 ... h2n każdym kroku
algorytmu
w1 w2 ... wn
współczynniki
współczynniki funkcji kryterium (np. przy tzw. zmiennych bazowych)
ół iki f k ji k t i ( t i hb h)
wartości aktualne zmiennych bazowych (w tym przypadku dwóch)
obliczane współczynniki hij (pierwotnie macierz A)
obliczane współczynniki wi : ci  cB " hi
15
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
METODA SIMPLEKS  idea, c.d.  omówienie tabeli simpleksowej
METODA SIMPLEKS  idea, c.d.  omówienie tabeli simpleksowej
Wkażdym kroku wyprowadza się zmienną z bazy i wprowadza się
na jej miejsce nową; Warunki wejścia  nowej zmiennej do bazy
i wyjścia  starej z bazy przedstawiono na slajdzie 21;
Po dokonaniu operacji wprowadzania do bazy i wyprowadzania
zmiennych z bazy dokonuje się ponownego przeliczenia wartości
współczynników hij oraz wi;
Obliczanie wartości współczynników hij i wi przedstawiono na
slajdach 20 i 24;
Warunkiem zakończenia obliczeń jest aby w ostatnim wierszu tabeli
simpleksowej (współczynniki wi) wartości wszystkich współczynników
byływiększe lub równe zero;
W ostatniej tabeli simpleksowej (rozwiązania optymalnego) zmienne
bazowe, których wartości są równe wartościom w kolumnie h0
stanowią rozwiązanie optymalne zadania;
16
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (wykorzystanie metody simpleks)
2 1
�ł łł
A =
�ł śł
�ł1 2�ł
Załóżmy, że mamy zadanie optymalizacji postaci
c = (1,1)
2
�ł łł
max f (x) = max{x1 + x2}
b =
�ł
�ł2śł
�ł
przy ograniczeniach:
p y g
x2 Czyli rozwiązaniem
C li i i
2x1 + x2 d" 2
graficznym tego zadania
2
jest wektor x=(2/3,2/3)
x1 + 2x2 d" 2
x1, x2 e" 0
f (x)=(1,1)-gradient
Gradient funkcji:
Gradient funkcji:
1
1
df (x) d(x1 + x2) x=(x1, x2)=(2/3,2/3)
= =1
dx1 dx1
df (x) d(x1 + x2)
= =1
dx2 dx2
12
x1
17
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (cd.)
Sprowadz
my zadanie do postaci kanonicznej.
Najpierw zamieniamy  max na  min mnożąc funkcje przez  1:
max{x1 + x2} = - min{-x1 - x2 + 0�" x3 + 0�" x4}
Zmieniamy ograniczenia
c = (-1,-1,0,0) 2
�ł łł
b =
2x1 + x2 + x3 = 2
�ł
�ł2śł
�ł
2 1 1 0
�ł łł
A =
x1 + 2x2 + x4 = 2
�ł1 2 0 1śł
x1
�ł łł
�ł �ł
�łx2śł
x1, x2 e" 0
x1, x2 e" 0
sugestia rozwiązania
sugestia rozwiązania
x =
x =
�ł śł
�łx śł
bazowego
�łx3śł
�ł 4�ł
min c, x
Zapis wektorowo-macierzowy
A �" x = b x e" 0
18
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (cd.)
Szukamy pierwszego rozwiązania  bazowego , tzn. takiego,
które spełnia układ równań, ale niekoniecznie jest optymalnym.
Dla nas takim rozwiązaniem jest wektor x=(0,0,2,2)
2x + x + x = 2
2x1 + x2 + x3 = 2
pierwsze zmienne bazowe
x1 + 2x2 + x4 = 2
A
atwo zauważyć, że
x1 = 0, x2 = 0, x3 = 2, x4 = 2
jest rozwiązaniem dopuszczalnym, więc bazowym.
2 1 1 0
�ł łł
A =
�ł1 2 0 1śł
�ł �ł
sugestia rozwiązania
bazowego
19
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (cd.) (Metoda simpleks  pierwsza tablica metody simpleks)
Tabela 1
Tabela 1
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0
x4 0 2 1 2 0 1
-1 -1 0 0
współczynniki
współczynniki funkcji kryterium (np. przy zmiennych bazowych)
wartości aktualne zmiennych bazowych
współczynniki hij (w Tabeli 1 zawsze macierz A)
iloczyn wektorów
iloczyn wektorów
obliczane współczynniki wi : ci  cB " hi , np.
w1 = c1 - (c3 �" h11 + c4 �" h21) = -1- (0�" 2 + 0�"1) = -1
w4 = c4 - (c3 �"h14 + c4 �" h24) = 0 - (0�"0 + 0�"1) = 0
20
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Przykład (cd.) (Metoda simpleks  tablica metody simpleks (cd.))
Tabela 1
Tabela 1
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0 h10/h12=2/1=2
x4 0 2 1 2 0 1 h20/h22=2/2=1
min
-1 -1 0 0
Współczynniki wi
min
Warunek wejścia do bazy (nowej zmiennej): min{współczynnika wi}
Warunek wejścia do bazy ( j j) min{współczynnika wi}
j y { p y }
j y { p y }
i
i
(mógł być też pierwszy, wybieramy z równych  według woli ).
Kolumna (h2) teraz jest dla nas podstawą wyjścia zmiennej bazowej z
bazy, a numer zmiennej wchodzącej do bazy oznaczmy jako L=2
L=2.
Warunek wyjścia z bazy
Warunek wyjścia z bazy (starej zmiennej bazowej): dzielimy hi0/hiL (tylko dla
hiL>0) w każdym i-tym wierszu i szukamy wartości minimalnej.
21
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
ci
Tabela 1
Tabela 1
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
 Stara tabela:
x3 0 2 2 1 1 0
wi są ujemne,
zatem jeszcze
nie mamy
x4 0 2 1 2 0 1
rozwiązania
optymalnego
-1 -1 0 0
współczynniki
ci
Tabela 2
Tabela 2
-1 -1 0 0
 Nowa tabela:
Nadal istnieją
, zatem
Zmienne
cB h0 h1 h2 h3 h4 ujemne wimamy
B 0 1 2 3 4
bazowe nadal nie
bazowe nadal nie mamy
rozwiązania
optymalnego
x3 0 1 3/2 0 1 -1/2
x2 -1 1 1/2 1 0 1/2
-1/2 0 0 1/2
współczynniki
22
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
zamiana
Jak wyznaczyliśmy nowe współczynniki tabeli simpleks nr 2?
Jak wyznaczyliśmy nowe współczynniki tabeli simpleks nr 2?
Tabela 1
Tabela 1
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4
bazowe
x3 0 2 2 1 1 0
x4 0 2 1 2 0 1
-1 -1 0 0
współczynniki
W tym wierszu (odpowiadającym zmiennej wyprowadzanej z bazy)
wszystkie komórki (bez niebieskich) dzielimy przez wartość pola
wszystkie komórki (bez niebieskich) dzielimy przez wartość pola
czerwonego (w czarnej obwódce)
Wszystkie komórki (bez niebieskich) innych wierszy obliczamy następująco:
np. nowe h11= h11-(h12�"h21/ h22) = 2-(1 �" 1/2) = 3/2, ogólnie:
gdzie K  numer wiersza w tabeli, w którym znajduje się zmienna
nowe hij = hij - (hiL �" hKj / hKL )
wyprowadzana z bazy; L  numer zmiennej (kolumny) wprowadzanej do bazy.
obliczane współczynniki wi: ci  cB " hi 23
Szczegółowe obliczenia dla tabeli nr 2
Szczegółowe obliczenia dla tabeli nr 2
Współczynniki wi = ci  cB " hi :
Współczynniki h2j :
w1 = c1 - (c3 �" h11 + c2 �" h21) =
nowe h20= h20/ h22 = 2/2 = 1
= -1- (0�"3/ 2 + (-1)�"1/ 2) = -1/ 2
nowe h21= h21/ h22 = 1/2 = 1/2
w4 = c4 - (c3 �" h14 + c2 �" h24) =
( )
4 4 3 14 2 24
nowe h22= h22/ h22 = 2/2 = 1
= 0 - (0�"(-1/ 2) + (-1)�"1/ 2) = 1/ 2
nowe h23= h23/ h22 = 0/2 = 0
w2 = c2 - (c3 �" h12 + c2 �" h22) =
nowe h24= h24/ h22 = 1/2 = 1/2
= -1- (0�"0 + (-1)�"1) = 0
w3 = c3 - (c3 �" h13 + c2 �"h23) =
Współczynniki h1j :
= 0 - (0�"1+ (-1)�"0) = 0
nowe h10= h10-(h12 h20/ h22) = 2-(1�"2/2) = 1
h h (h h / h ) 2 (1 2/2) 1
ZAWSZE wyliczane na
podstawie  nowej tabeli (czyli
nowe h11= h11-(h12 h21/ h22) = 2-(1�"1/2) = 3/2
w tym kroku na podstawie
tabeli nr 2)
nowe h12= h12-(h12 h22/ h22) = 1-(1�"2/2) = 0
ZAWSZE wyliczane na
nowe h13= h13-(h12 h23/ h22) = 1-(1�"0/2) = 1 podstawie  starej tabeli (czyli
w tym kroku na podstawie
tabeli nr 1)
nowe h14= h14-(h12 h24/ h22) = 0-(1�"1/2) = -1/2
24
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
Tabela 2
Tabela 2
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4 Nadal istnieją
bazowe
ujemne wi,
zatem nadal
x3 0 1 3/2 0 1 -1/2
nie mamy
rozwiązania
rozwiązania
x2 -1 1 1/2 1 0 1/2
optymalnego
-1/2 0 0 1/2
współczynniki
Tabela 3
Tabela 3
ci
-1 -1 0 0
Zmienne
cB h0 h1 h2 h3 h4 Istnieją
B 0 1 2 3 4
bazowe
bazowe
Istnieją
jedynie
x1 -1 2/3 1 0 2/3 -1/3 nieujemne wi ,
zatem mamy
mamy
rozwiązanie
rozwiązanie
x2 -1 2/3 0 1 -1/3 2/3
optymalne
optymalne
0 0 1/3 1/3
współczynniki
25
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego
W ostatniej tabeli otrzymaliśmy:
x=(x1, x2, x3, x4)=(2/3, 2/3, 0, 0)
zatem szukane przez nas rozwiązanie bez zmiennych sztucznych:
x=(x1, x2)=(2/3, 2/3)
natomiast wartość funkcji kryterium f(x)= x1+x2=2/3 + 2/3=4/3.
Otrzymaliśmy to samo rozwiązanie co metodą graficzną (slajd nr 17).
26
Wybrane zagadnienia badań operacyjnych  Wykład nr 2a: Metoda simpleks rozwiązywania zadań programowania liniowego