Wprowadzenie do badań operacyjnych – przedmiot 

BO

Podstawowym przedmiotem badań operacyjnych są 

decyzje

Decydent – jednostka podejmująca decyzje – zawsze 

działa w sytuacji decyzyjnej, co znaczy, że ma 

możliwość podjęcia decyzji z pewnego zbioru decyzji. 
Mamy więc do czynienia z problemem decyzyjnym

Decyzja, która zostanie podjęta, musi być zgodna z 

warunkami ograniczającymi. Taką decyzję nazywamy 

decyzją dopuszczalną. Inne decyzje są niemożliwe do 

realizacji; takie decyzje będą nazywane 

niedopuszczalnymi

 

To, czy dana decyzja jest dopuszczalna czy jest 

niedopuszczalna, zależy od warunków 

ograniczających narzuconych decydentowi przez 

sytuację decyzyjną

Wprowadzenie do badań operacyjnych – przedmiot 

BO

Które decyzje, ze zbioru decyzji dopuszczalnych są 

lepsze, a które gorsze, zależy od celu działania 

decydenta. Musi on dokonać wyboru najlepszej (z 

punktu widzenia przyjętego celu) decyzji 

dopuszczalnej – czyli decyzji optymalnej

Z punktu widzenia celu, jaki stawia sobie decydent, 

decyzje są porównywalne w tym sensie, że jeśli dane są 

dowolne dwie decyzje dopuszczalne, to można wskazać 

decyzję lepszą, decyzję gorszą albo stwierdzić, że obie 

decyzje są równoważne. Kryterium, według którego 

decydent ocenia decyzje nosi nazwę kryterium 

wyboru

Wprowadzenie do badań operacyjnych – zadanie 

decyzyjne

Wiele decyzji ekonomicznych ma charakter ilościowy. W 

związku z tym problem wyboru decyzji najlepszej 

można opisać w języku matematycznym, tzn. można 

sformułować model matematyczny danej sytuacji 

decyzyjnej, mówiąc inaczej: zadanie decyzyjne

Model matematyczny, w najogólniejszym pojęciu, jest 

abstrakcyjnym przedstawieniem rzeczywistych 

zależności. Rozwiązanie modelu matematycznego 

sprowadza się do wyznaczenia rozwiązania optymalnego 

 

Model matematyczny problemu decyzyjnego nazywa się 

modelem (zadaniem) decyzyjnym lub modelem 

(zadaniem) optymalizacyjnym

 

Reasumując możemy powiedzieć, że badania operacyjne dostarczają metod 

rozwiązywania zadań decyzyjnych, czyli metod pozwalających wyznaczyć 

optymalne decyzje ekonomiczne w różnych sytuacjach praktyki 

gospodarczej 

Wprowadzenie do badań operacyjnych – 

rozwiązywanie ZD

Rozwiązanie problemu decyzyjnego za pomocą badań 

operacyjnych jest procedurą składającą się z kilku 

etapów:

1. Rozpoznanie sytuacji decyzyjnej i wynikającego z 

niej problemu decyzyjnego,

2. Budowa modelu decyzyjnego,
3. Rozwiązanie zadania decyzyjnego,
4. Ocena poprawności i realności uzyskanych 

rozwiązań oraz ewentualna weryfikacja modelu
decyzyjnego,

5. Przedstawienie rozwiązań i ostateczne 

przygotowanie decyzji 

Podjęta decyzja musi być decyzją dopuszczalną - 

należeć do zbioru decyzji dopuszczalnych (D), tzn.:

 

x

1

, 

x

2

, x

3

    D



Wprowadzenie do badań operacyjnych – 

budowanie MD

Podjęcie decyzji, z matematycznego punktu widzenia, 

można utożsamiać z wyznaczeniem n wielkości:

x

1

, x

2

, …, x

n

.

Wielkości te, opisujące sytuację decyzyjną, nazywane są 

zmiennymi decyzyjnymi

Na przykład, jeśli zadanie decyzyjne dotyczy ustalenia 

asortymentu produkcji pewnego zakładu produkującego 

trzy typy wyrobów. A, B i C, to znaczy że mamy trzy 

wielkości niewiadome: x

1

, x

2

, x

3

 (trzy zmienne 

decyzyjne).

W wyniku rozwiązania zadania możemy uzyskać:
x

1

 = 10 - tzn. produkować 10 jednostek wyrobu A,

x

2

 = 5

- tzn. produkować 5 jednostek wyrobu B,

x

3

 = 12 - tzn. produkować 12 jednostek wyrobu C. 

Wprowadzenie do badań operacyjnych – zmienna 

decyzyjna

Wprowadzenie do badań operacyjnych – funkcja 

celu

Zbiór D wyznacza się po określeniu warunków 

ograniczających.

Warunki ograniczające zapisuje się w postaci układu 

równań i nierówności, w których występują zmienne 

decyzyjne, pewne parametry techniczno-

ekonomiczne i wielkości zwane limitami.

Np. nierówność: x

1

 + x

2

 ≥ 14

w zadaniu o omawianym zakładzie produkcyjnym 

oznaczałaby, że łączna produkcja wyrobów typu A i B 

musi wynieść co najmniej 14 jednostek. 

Wyznaczenie najlepszej decyzji ze zbioru D jest możliwe po 

sformułowaniu tzn. funkcji celu (funkcji kryterium). Stanowi ona 

ilościowe odzwierciedlenie przyjętego celu działania decydenta: f 

(x

1

, x

2

, …, x

n

) → optimum

Rozwiązanie modelu (czyli znalezienie rozwiązania optymalnego) 

sprowadza się do wyznaczenia takich wartości: x

1

, x

2

, …, x

n

, dla 

których funkcja celu osiąga wartość optymalną (maksymalną lub 

minimalną, w zależności od przyjętego kryterium celu), oczywiście 

przy spełnieniu warunków ograniczających 

Wprowadzenie do badań operacyjnych – składowe 

MD

Na model matematyczny sytuacji decyzyjnej składają 

się następujące elementy:

1)

Warunki  ograniczające – najczęściej   zapisywane  za  

pomocą układu  równań   i nierówności.  W równaniach tych 

(nierównościach) występują pewne wielkości dane zwane 

parametrami,  oraz  wielkości,  które  należy ustalić,  tzw.  

zmienne decyzyjne. Warunki ograniczające niekiedy nazywa 

się warunkami nieelementarnymi,

2)

Warunki brzegowe – najczęściej są to warunki dotyczące 

znaku zmiennych (np. warunki nieujemności) lub typu 

zmiennych (np. warunki całkowitoliczbowości). Warunki 

brzegowe niekiedy nazywa się warunkami elementarnymi,

3)

Funkcja celu (funkcja kryterium) – pewna funkcja 

zmiennych decyzyjnych będąca formalnym odzwierciedleniem 

celu działania decydenta (funkcja celu pełni rolę kryterium 

wyboru)

Wyznaczenie decyzji dopuszczalnej sprowadza się do 
wyznaczenia takiego układu wartości zmiennych, który to układ 
spełnia wszystkie warunki ograniczające i brzegowe opisujące 
badaną sytuację.
Wyznaczenie decyzji optymalnej polega na ustaleniu takiej 
decyzji dopuszczalnej, dla której funkcja celu osiąga wartość 
maksymalną lub minimalną - w zależności od badanej sytuacji.

 

Wprowadzenie do badań operacyjnych – etapy 

budowy MD

Schemat postępowania przy budowie modelu 

konkretnej sytuacji decyzyjnej:

1.Zdefiniowanie zmiennych decyzyjnych.

Należy  ustalić  jakie  wielkości  mają  być  wyznaczone  i 

odpowiednio 

je 

oznaczyć. 

Zbiór 

zmiennych 

decyzyjnych,  w  praktyce,  utożsamiamy  ze  zbiorem 

alternatywnych 

działalności, 

jakie 

zamierzamy 

prowadzić  (np.  działalnością  alternatywną  jest: 

produkcja  wyrobu  A,  produkcja  wyrobu  B,  produkcja 

wyrobu C).

2.Ustalenie parametrów zadania.

Należy  zebrać  wszystkie  interesujące  wielkości  dane  w 

zadaniu:  w  tym  wartości  parametrów  techniczno-

ekonomicznych i wielkości limitów, których nie należy 

przekroczyć.  Parametrem  techniczno-ekonomicznym 

jest  np.  ilość  zużytego  surowca  na  jednostkę 

produkowanego wyrobu (inaczej nakłady jednostkowe) 

lub  normy  żywienia  (ludzi  lub  zwierząt).  Limitem  jest 

np.  zasób  posiadanego  surowca  do  produkcji, 

minimalna  lub  maksymalna  wielkość  produkcji 

pewnego  wyrobu,  minimalna  lub  maksymalna 

wielkość  składnika  odżywczego  dostarczanego  w 

pożywieniu, itd.

Wprowadzenie do badań operacyjnych – etapy 

budowy MD

3.Określenie postaci warunków ograniczających i 

warunków brzegowych.

Należy  sformułować  układ    równań    i    nierówności  jaki   

muszą spełniać zmienne decyzyjne.

Np.  sformułowany  wcześniej  warunek  ograniczający 

opisujący problem decyzyjny w omawianym zakładzie 

produkcyjnym  jest  następujący:  x

1

  +  x

2

  ≥  14. 

Nierówność  oznacza,  że  łączna  produkcja  wyrobów 

typu A i B musi wynieść co najmniej 14 jednostek.

Nierówność: x

3

 ≤ 20 oznacza, że produkcja wyrobu typu 

C nie może przekroczyć 20 jednostek.

Warunki brzegowe  to  warunki  nakładane  na zmienne  

decyzyjne    (w    szczególności  warunki  o  nieujemności 

zmiennych decyzyjnych):

x

1

 ≥ 0, x

2

 ≥ 0, x

3

 ≥ 0.

Warunki  te  są  oczywistą  informacją  mówiącą,  że 

wielkość produkcji nic może być liczbą ujemną

Wprowadzenie do badań operacyjnych – etapy 

budowy MD

4.   Określenie postaci funkcji celu i kryterium 

optymalizacji (maksimum czy minimum).

Np. jeśli kryterium optymalizacji jest maksymalizacja zysku i 

posiadamy następujące

informacje:

 zysk z produkcji jednostki wyrobu A (zysk jednostkowy) 

wynosi 20 zł.

 zysk z produkcji jednostki wyrobu B wynosi 25 zł.

 zysk z produkcji jednostki wyrobu C wynosi 20 zł.

wówczas postać funkcji celu jest następująca:

f(x

1

, x

2

, x

3

) = 20x

1

 + 25x

2

 + 20x

3

 → max

Wielkości: 20, 25, 20, oznaczające tutaj zyski jednostkowe z 

produkcji poszczególnych wyrobów, nazywają się 
parametrami funkcji celu (inaczej wagami funkcji celu).

Wprowadzenie do badań operacyjnych – model 

liniowy

Opisane w powyższy sposób zagadnienie nazywa się 

zadaniem programowania matematycznego 

(ZPM).

Szczególnym 

rodzajem 

programowania 

matematycznego jest programowanie liniowe (PL). W 

programowaniu  liniowym  model  matematyczny,  na 

podstawie którego wyznacza się decyzję optymalną, jest 

tzw.  modelem  liniowym,  czyli  liniowym  zadaniem 

decyzyjnym (LZD).
Liniowe  zadanie  decyzyjne,  inaczej  mówiąc  –  zadanie 

programowania  liniowego  (ZPL),  to  takie  zadanie 

decyzyjne,  w  którym  wszystkie  relacje  są  liniowe,  tzn. 

liniowe  są  zarówno  warunki  ograniczające  jak  i  funkcja 

celu.

Wprowadzenie do badań operacyjnych – ogólna 

postać ZPL

Ogólna postać liniowego zadania decyzyjnego jest 
następująca:

(1a) 

f(x) = c

1

x

1

 + c

2

x

2

 + ... + c

n

x

n

  opt 

(opt = 

max albo opt = min)

(1b) a

i1

x

1

 + a

i2

x

2

 + ... + a

in

x

n

  b

i

,

(1c) a

i1

x

1

 + a

i2

x

2

 + ... + a

in

x

n

  b

i

,

(1d) a

i1

x

1

 + a

i2

x

2

 + ... + a

in

x

n

 = b

i

,

(1e)  x

1

, x

2

, ..., x

n

  0.

Symbole c

j

, b

i

, a

ij

 (i = 1, 2, ..., m; j = 1, 2, ..., n) 

oznaczają parametry zadania:

 c

j

 jest wagą (współczynnikiem) funkcji celu przy j–tej 

zmiennej decyzyjnej,

 b

i

 jest wyrazem wolnym i–tego warunku 

ograniczającego,

 a

ij

 jest współczynnikiem przy j–tej zmiennej 

decyzyjnej w i–tym warunku ograniczającym.

Wprowadzenie do badań operacyjnych – ogólna 

postać ZPL

Rozwiązaniem przedstawionego powyżej układu 
warunków 1b-1e jest wektor x:

x = [

x

1

, x

2

, ..., x

n

]

T

gdzie: x

1

, x

2

, ..., x

n

 – to współrzędne wektora x.

Każdy wektor x, który spełnia warunki 1b-1e nazywa się 

rozwiązaniem dopuszczalnym zadania programowania 

liniowego.

Rozwiązaniem  optymalnym  jest  takie  rozwiązanie 

dopuszczalne,  dla  którego  funkcja  celu  (1a)  osiąga 

maksimum (lub minimum).

Wprowadzenie do badań operacyjnych – przykład

Firma  papiernicza  „Blokpol''  produkuje  trzy  rodzaje 
bloków  rysunkowych:  małe,  duże  i  średnie.  Na 
wyprodukowanie  jednego  bloku  małego  zużywa  się 
0,2  kg  tektury,  średniego  0,25  kg,  dużego  0,3  kg. 
Ponadto wiadomo, że wyprodukowanie jednego bloku 
małego wymaga 30 minut pracy maszyny, natomiast 
średniego  i  dużego  -  40  minut.  Firma  może 
przeznaczyć  na  wyprodukowanie  bloków  240  kg 
tektury  miesięcznie,  natomiast  łączny  czas  pracy 
maszyny  w  ciągu  miesiąca  nie  może  przekroczyć  30 
000  minut.  Należy  ustalić  plan  produkcji  bloków 
rysunkowych na najbliższy miesiąc, tak, aby osiągnąć 
możliwie  najwyższy  przychód  ze  sprzedaży.  Ceny 
sprzedaży poszczególnych bloków wynoszą: małego 8 
zł, średniego 10 zł, dużego 11 zł. 

Wprowadzenie do badań operacyjnych – przykład

Rozwiązanie:
Mamy ustalić plan produkcji, tzn. odpowiedzieć na 
pytanie: ile bloków rysunkowych każdego rodzaju 
powinna produkować firma. Mamy zatem trzy 
wielkości „szukane".

Oznaczmy zmienne decyzyjne: 
x

1 

– ilość produkowanych bloków małych,

x

2 

–

 

ilość produkowanych bloków średnich,

x

3

 – ilość produkowanych bloków dużych.

Formułujemy teraz warunki ograniczające i brzegowe.

Model będzie zawierał dwa warunki ograniczające:
1-szy dotyczący zużycia tektury,
2-gi dotyczący zużycia czasu pracy maszyn. 

Wprowadzenie do badań operacyjnych – przykład

0,20x

1 

+ 0,25x

2

 + 0,30x

3

 ≤ 240

Nierówność informuje, iż zasoby tektury wynoszą 240 
kg, natomiast wielkości 0,20, 0,25 i 0,30 oznaczają 
jednostkowe zużycie tektury na produkcję 
poszczególnych rodzajów bloku

30x

1 

+ 40x

2

 + 40x

3

 ≤ 30000

Nierówność informuje, że możliwy do wykorzystania 
czas pracy maszyn wynosi 30000 minut. 30, 40 i 40 to 
jednostkowe zużycie czasu pracy maszyn na 
poszczególne typy bloków.

Obok  warunków  ograniczających  konieczne  jest 

zapisanie warunków brzegowych.

x

1

 ≥ 0, x

2

 ≥ 0, x

3

 ≥ 0.

Funkcja celu ma następującą postać:

F(x

1

, x

2

, x

3

) = 8x

1

 + 10x

2

 + 11x

3

 → max

Wprowadzenie do badań operacyjnych – przykład

Model matematyczny danej sytuacji decyzyjnej jest 

następujący:

 

F(x

1

, x

2

, x

3

) = 8x

1

 + 10x

2

 + 11x

3

 → max

0,20x

1

 + 0,25x

2

 + 0,30x

3

 ≤ 240,

30x

1

 + 40x

2

 + 40x

3

 ≤ 30000

x

1

 ≥ 0, x

2

 ≥ 0, x

3

 ≥ 0.

Po zbudowaniu modelu można przystąpić do 

jego rozwiązania, czyli znalezienia 

rozwiązania optymalnego.

Wprowadzenie do badań operacyjnych – typy problemów 

decyzyjnych

Sytuacje decyzyjne możemy podzielić na trzy zasadnicze 

grupy:

1) zagadnienie wyboru asortymentu produkcji,

2) zagadnienie składu mieszanin,

3) zagadnienie wyboru procesu technologicznego.

 Zagadnienie wyboru asortymentu 

produkcji

W  zagadnieniu  tym  problem  polega  na  określeniu, 

które  wyroby  i  w  jakich  ilościach  powinno 

przedsiębiorstwo  produkować,  aby  nie  przekraczając 

dostępnych  środków  produkcji  oraz  spełniając  inne, 

dodatkowe  ograniczenia  zrealizować  założony  cel 

działalności.  Do  środków  produkcji  należą:  surowce, 

które  są  limitowane,  praca  ludzka,  praca  maszyn, 

energia.  Celem  w  zagadnieniach  tego  typu  jest 

najczęściej  maksymalizacja  zysku  lub  przychodu  ze 

sprzedaży.

 

Wprowadzenie do badań operacyjnych – typy problemów 

decyzyjnych

Zagadnienie składu mieszanin

Z  problemem  tego  typu  mamy  do  czynienia  w  branżach 
takich  jak  np.  chemiczna,  metalurgiczna,  spożywcza, 
przetwórstwo  rolne.  Wyroby  tych  branż  często  są 
mieszaninami  (stopami)  pewnych  surowców.  W  zagadnieniu 
składu  mieszanin  należy  określić,  jakie  ilości  podstawowych 
surowców należy zmieszać (zakupić), aby otrzymać produkt o 
pożądanym składzie, przy możliwie najniższych kosztach.
Szczególnym przypadkiem zagadnienia składu mieszanin jest 
tzw.  problem  diety.  Problem  pojawiać  się  może  w 
odniesieniu  do  jednego  człowieka,  grupy  ludzi  (np.  przy 
organizowaniu  wyżywienia  w  stołówkach,  w  wojsku,  w 
szpitalach),  bądź  też  zwierząt  (w  przedsiębiorstwach 
rolniczych).
W  zagadnieniu  diety  należy  ustalić,  jakie  ilości  produktów 
żywnościowych  powinno  się  zakupić,  aby  przy  pełnym 
zaspokojeniu potrzeb organizmu obniżyć do minimum koszty 
wyżywienia.  A  zatem  chodzi  o  to,  aby  „mieszanka 
żywieniowa” zaspokajała potrzeby organizmu (tj. dostarczała 
odpowiednie  ilości  składników  odżywczych  takich  jak 
witaminy,  białko,  węglowodany,  tłuszcze,  kalorie,  i  inne)  i 
jednocześnie - była możliwie najtańsza.

Wprowadzenie do badań operacyjnych – typy problemów 

decyzyjnych

Zagadnienie wyboru procesu 

technologicznego

Najogólniej  rzecz  biorąc,  problem  tego  typu  wynika  z 

faktu, że produkcja wyrobów (wyrobu) może odbywać 
się 

przy 

zastosowaniu 

różnych 

technologii. 

Zagadnienie  polega  na  określeniu,  w  jakiej  skali 
(ilości, intensywności) stosować poszczególne rodzaje 
procesów technologicznych, aby wytworzyć określone 
ilości  produktów  przy  możliwie  najniższych  kosztach. 
Kryterium  celu  może  być  również  maksymalizacja 
zysku.

Wprowadzenie do badań operacyjnych – uwagi 

końcowe

Po  skonstruowaniu  modelu  należy  przejść  do  kolejnego 

etapu,  mianowicie  przystąpić  do  rozwiązania 
modelu. 

Celem 

naszym 

będzie 

wyznaczenie 

rozwiązania 

optymalnego. 

Znalezienie  rozwiązania  optymalnego  (jako  najlepszego 

z 

dopuszczalnych) 

musi 

być 

poprzedzone 

znalezieniem 

zbioru 

D 

(zbioru 

rozwiązań 

dopuszczalnych).

Okazuje  się,  że  nie  zawsze  rozwiązania  dopuszczalne 

istnieją.  Układ  wielu  równań  i  nierówności  może  nie 
mieć rozwiązania.

Tak więc mogą wystąpić dwie sytuacje:
I) zadanie PL ma rozwiązania dopuszczalne, tzn. zbiór D 

nie jest zbiorem pustym (D ≠ 0). Zadanie nazywa się 
wtedy zadaniem wewnętrznie zgodnym,

II)  zadanie  PL  nie  ma  rozwiązania  dopuszczalnego,  tzn. 

zbiór  D  jest  zbiorem  pustym  (D  =  0).  Zadanie 
nazywa się wtedy zadaniem sprzecznym.

Metoda geometryczna

Metodą  geometryczną  można  rozwiązywać  liniowe 

zadania decyzyjne o dwóch zmiennych decyzyjnych. 

 

Liczba zmiennych decyzyjnych wyznacza wymiar 

przestrzeni, w której znajduje się zbiór rozwiązań 

dopuszczalnych i rozwiązanie optymalne. W naszych 

rozważaniach ograniczymy się do zadania o dwóch 

zmiennych decyzyjnych (tzn. ograniczymy się do 

przestrzeni dwuwymiarowej). 

Rozwiązanie  linowego  zadania  decyzyjnego  polega  na 
wyszukaniu  -  w  skonstruowanym  graficzne  zbiorze 
rozwiązań dopuszczalnych - punktu, dla którego funkcja 
celu przyjmuje wartość najkorzystniejszą. Taki punkt nosi 
nazwę punktu optymalnego. 

Metoda geometryczna - przypomnienie

W przestrzeni dwuwymiarowej:

•

prosta jest miejscem geometrycznym 
punktów, których współrzędne spełniają 
równanie,

•

półpłaszczyzna, razem z prostą będącą jej 
brzegiem, jest miejscem geometrycznym 
punktów, których współrzędne spełniają 
nierówność słabą,

•

półpłaszczyzna, bez prostej będącej jej 
brzegiem, jest miejscem geometrycznym 
punktów, których współrzędne spełniają 
nierówność ostrą.

Metoda geometryczna

Metoda geometryczna sprowadza się do graficznego 

rozwiązania układu nierówności.

 

Interpretacją graficzną nierówności w układzie 

współrzędnych jest półpłaszczyzna, natomiast układu 

nierówności jest część wspólna odpowiednich 

półpłaszczyzn.   

Część wspólna oznacza zbiór punktów spełniających 

wszystkie warunki ograniczające i brzegowe. Są to 

rozwiązania dopuszczalne. 

Przy wyznaczaniu punktu optymalnego pomocna jest 

izokwanta funkcji celu, tzn. prosta odpowiadająca 

pewnej zadanej wartości funkcji celu. Izokwanta ma 

następujące właściwości:

1) punkty na izokwancie odpowiadają tej samej wartości 

funkcji celu,

2) izokwanty odpowiadające różnym wartościom funkcji 

celu są równoległe.

 

Metoda geometryczna

Jeżeli linowe zadanie decyzyjne ma rozwiązanie 

optymalne, to znajduje się ono w punkcie, w którym 

izokwanta dla najkorzystniejszej wartości funkcji celu 

jest styczna do zbioru rozwiązań dopuszczalnych. 

1.   Jeżeli  jest  to  jeden  punkt,  to  jest  to  wierzchołek 

zbioru  rozwiązań  dopuszczalnych,  zadanie  ma  wtedy 
jedno rozwiązanie optymalne.

2.   Jeżeli  jest  to  wiele  punktów,  to  w  przestrzeni 

dwuwymiarowej  jest  to  odcinek,  liniowe  zadanie 
decyzyjne  ma  wtedy  wiele  (nieskończenie  wiele) 
rozwiązań optymalnych.

Jeżeli liniowe zadanie decyzyjne ma rozwiązanie 

optymalne, to znajduje się ono w co najmniej jednym 

wierzchołku zbioru rozwiązań dopuszczalnych. 

Metoda geometryczna - przykład

Przedsiębiorstwo  wytwarza  dwa  wyroby,  używając 

dwóch surowców, których ilości są limitowane. 

wyroby

surowce

ceny

I

II

A

8

6

18

B

4

9

15

limity

52

69

 

Jaka powinna być struktura produkcji, aby 

przedsiębiorstwo osiągało maksymalny przychód ? 

Metoda geometryczna - przykład

Liniowe zadanie decyzyjne dla wyboru asortymentu 

maksymalizującego wartość produkcji ma 

następującą postać:

0

,

0

69

9

6

)

52

4

8

)

max

15

18

)

(

2

1

2

1

2

1

2

1



















x

x

x

x

b

x

x

a

warunkach

przy

x

x

x

F

Ponieważ zadanie zawiera dwie zmienne decyzyjne, 

można je rozwiązać metodą geometryczną. Obie 

zmienne decyzyjne są nieujemne, a więc zbiór rozwiązań 

dopuszczalnych będzie zawarty w pierwszej ćwiartce 

układu współrzędnych.

Metoda geometryczna - przykład

Rozwiązywanie  zadania  rozpoczynamy  od  wyznaczenia 

zbioru  rozwiązań  dopuszczalnych.  Wyznaczenie 
półpłaszczyzn,  której  punkty  spełniają  daną 
nierówność wymaga wykonania dwóch kroków:

1)   wykreślenia  prostej,  której  punkty  spełniają 

równanie odpowiadające danej nierówności,

2)   rozstrzygnięcie,  po  której  stronie  prostej  znajdują 

się punkty spełniające tę nierówność.

 Weźmy pod uwagę nierówność: (a) 8x

1

 + 4x

2

  52. 

Odpowiadające jej równanie ma następującą postać: 

8x

1

 + 4x

2

 = 52

Wyznaczamy punkty konieczne do wykreślenia prostej:

jeśli x

2

 = 0     =>    x

1

 = 52/8 = 6,5   (6,5;0)

jeśli x

1

 = 0     =>    x

2

 = 52/4 = 13    (0;13)

Metoda geometryczna - przykład

x

2

x

1

D

C

A

B

(1)

13

6,5

(2)

11,5

3

2

7

f (celu)

F(x) = 
67,5

Metoda geometryczna - przykład

Punktem  optymalnym  jest  punkt  C.  Jest  to  wierzchołek 

zbioru  rozwiązań  dopuszczalnych  będący  punktem 
przecięcia  prostych  (1)  i  (2).  Jego  współrzędne 
wyznaczamy rozwiązując układ równań:

(1) 8x

1

 + 4x

2

 = 52

(2) 6x

1

 + 9x

2

 = 69

Rozwiązaniem jest x

1

 = 4, x

2

 = 5. 

Aby osiągnąć maksymalny przychód ze sprzedaży 

wyrobów,  przedsiębiorstwo  powinno  produkować  4 
jednostki wyrobu 1 oraz 5 jednostek wyrobu 2. 

Dzięki  temu  przedsiębiorstwo  osiągnie  maksymalny 

przychód w wysokości:

F(x

1

,x

2

) = 18x4 + 15x5 = 147

Metoda simpleks

Zadanie 

programowania 

liniowego

Dopuszczalne 

rozwiązanie bazowe

Zmiana 

rozwiązania

Sprawdzenie, czy 

rozwiązanie jest 

optymalne

Koniec 

postępowa

nia

NIE

TAK

Rys. 1. Ogólny schemat metody simpleks.

Metoda simpleks

Algorytm  simpleks  polega  na  badaniu  rozwiązań 

bazowych  programu  o  postaci  kanonicznej  (tzn.  taki,  w 
którym  wszystkie  warunki  ograniczające  mają  postać 
równości),  a  zatem  przed  przystąpieniem  do  budowy 
pierwszej  tablicy  simpleks  należy  zmienić  wszystkie 
nierówności  na  równania  przez  wprowadzenie  pewnych 
nowych zmiennych. 

W przypadku nierówności typu „≤” do ich lewych stron 

dodajemy  tzw.  zmienne  swobodne,  które  stanowią 
pierwsze 

rozwiązanie 

bazowe 

(pierwsza 

tablica 

simpleksowa).

W  przypadku  nierówności  typu  „≥”  od  lewych  stron 

odejmujemy zmienne swobodne i dodajemy tzw. zmienne 
sztuczne.  W  tym  przypadku  zmienne  sztuczne  wchodzą 
do pierwszej bazy.

Również 

do 

warunków 

równościowych 

wprowadzamy zmienne sztuczne, które wchodzą do 
pierwszej bazy. 

Metoda simpleks

W  najogólniejszym  zarysie  metoda  simpleks 
polega  na  tym,  że  wychodząc  od  pewnego 
rozwiązania  początkowego  (dopuszczalnego  i 
bazowego)  wyznacza  się  kolejne  rozwiązania 
(dopuszczalne  i  bazowe)  w  taki  sposób,  aby 
wartość  funkcji  celu  w  każdym  rozwiązaniu  była 
nie gorsza od wartości funkcji celu w rozwiązaniu 
poprzednim.  Metoda  simpleks  jest  metodą 
iteracyjną.  Po  wykonaniu  pewnej  liczby  kroków 
(iteracji)  otrzymuje  się  rozwiązanie  optymalne 
(lub stwierdza się, że ono nie istnieje). 

Metoda simpleks

Odwołując 

się 

do 

interpretacji 

geometrycznej 

(graficznej),  metoda  simpleks  polega  na  poszukiwaniu 
rozwiązania  optymalnego  wśród  wierzchołków  zbioru 
rozwiązań  dopuszczalnych.  Postępowanie  to  prowadzi  do 
uporządkowanych,  racjonalny  sposób.  Poszukiwanie 
rozwiązania 

optymalnego 

metodą 

simpleks 

jest 

„wędrowaniem”  po  wierzchołkach  zbioru  D,  przy  czym 
każdy  kolejny  wierzchołek  zbliża  nas  do  celu  tj. 
rozwiązania  optymalnego,  w  najgorszym  razie  –  nie 
oddala.

Program  liniowy  sprowadza  się  do  postaci  kanonicznej 

w celu znalezienia jego rozwiązania optymalnego. Okazuje 
się  bowiem,  że  optymalnego  rozwiązania  zadania 
programowania  liniowego  należy  szukać  wśród  tzw. 
bazowych rozwiązań układu równań.

Metoda simpleks - przykład

Zakład  może  wytwarzać  trzy  rodzaje  wyrobów:  A,  B  i  C. 
Przy  produkcji  tych  wyrobów  zużywane  są  trzy  różne 
surowce:  S1,  S2  i  S3,  których  zasoby  są  limitowane  i 
wynoszą odpowiednio: 2000, 800 i 1600 kg. Jednostkowe 
normy 

zużycia 

tych 

surowców 

przy 

produkcji 

poszczególnych wyrobów podane są w tablicy:

Zysk  jednostkowy  zrealizowany  ze  sprzedaży  wyrobu  A 
wynosi  4  zł,  wyrobu  B  –  3  zł,  wyrobu  C  –  5  zł.  Należy 
wyznaczyć  takie  wielkości  produkcji  poszczególnych 
wyrobów aby przy podanych ograniczeniach surowcowych 
globalny  zysk  osiągnięty  ze  sprzedaży  produkowanych 
wyrobów był możliwie największy. 

Metoda simpleks

Przyjmujemy zatem następujące oznaczenia zmiennych 

decyzyjnych rozważanego zagadnienia:

x

1

 – wielkość produkcji wyrobu A,

x

2

 – wielkość produkcji wyrobu B,

x

3

 – wielkość produkcji wyrobu C.

Zadanie programowania liniowego rozważanej sytuacji 

decyzyjnej przedstawia się następująco:

wyznaczyć maksimum funkcji 

f(x

1

, x

2

, x

3

) = 4x

1

 + 3x

2

 + 5x

3

  max

przy ograniczeniach:
3x

1

 + 4x

2

 + x

3

 ≤ 2000,

x

1

 + 2x

2

        ≤ 800,

x

1

 + 2x

2

 + 2x

3

 ≤ 1600,

x

1

, x

2

, x

3

 ≥ 0.

Metoda simpleks - przykład

Ponieważ w powyższym modelu ograniczenia mają 

postać nierówności typu „mniejsze lub równe”, dlatego 

też wprowadzamy trzy zmienne swobodne x

4

, x

5

 i x

6

 

celem sprowadzenia zadania do postaci kanonicznej. 

Otrzymamy więc: 

f(x

1

, x

2

, x

3

, x

4

, x

5

, x

6

) = 4x

1

 + 3x

2

 + 5x

3

 + 0x

4

 + 0x

5

 

+ 0x

6

  max

przy ograniczeniach:

3x

1

 + 4x

2

 + x

3

 + x

4

             = 2000,

x

1

 + 2x

2

               + x

5

       = 800,

x

1

 + 2x

2

 + 2x

3

             + x

6

 = 1600,

x

1

, x

2

, x

3

, x

4

, x

5

, x

6

 ≥ 0.

Zmienne swobodne x

4

, x

5

 i x

6

 interpretuje się w tym 

przypadku jako niewykorzystane ilości poszczególnych 

surowców: x

4

 - surowca S

1

, x

5

 - surowca S

2

, x

6

 - surowca 

S

3

. Wyjściowe rozwiązanie bazowe rozważanego programu 

jest więc następujące:

x

1

 = 0, x

2

 = 0, x

3

 = 0,

x

4

 = 2000, x

5

 = 800, x

6

 = 1600.

Metoda simpleks - przykład

Zmienne  swobodne  x

4

,  x

5

  i  x

6

  są  w  tym  rozwiązaniu 

zmiennymi  bazowymi,  natomiast  zmienne  decyzyjne  x

1

, 

x

2

  i  x

3

  stanowią  zmienne  niebazowe.  Pierwsza  tablica 

simpleksowa  dla  wyjściowego  rozwiązania  bazowego 
przedstawia się następująco:

Metoda simpleks - przykład

Sprawdzamy teraz, czy rozważane wyjściowe rozwiązanie 
jest  rozwiązaniem  optymalnym.  Najpierw  dla  wszystkich 
zmiennych  obliczamy  wskaźniki  z

j

,  np.  z

1

  =  0x3 +  0x1  + 

0x1  =  0,  z

2

  =  0x4  +  0x2  +  0x2  =  0,  itd.  Wskaźniki  z

j

  w 

tym  przypadku  są  zerami.  Stąd  też  wskaźniki 
optymalności  c

j

  –  z

j

,  zawarte  w  ostatnim  wierszu  tablicy 

simpleksowej,  równe  są  współczynnikom  wagowym 
zmiennych decyzyjnych z funkcji celu.

Metoda simpleks - przykład

Z kolei przystępujemy do wyznaczenia zmiennej, którą 

należy z bazy wyeliminować. W tym celu obliczamy 
ilorazy wyrazów wolnych i współczynników (dodatnich) 
znajdujących się w kolumnie odpowiadającej zmiennej x

3

. 

Otrzymujemy:

.

800

2

1600

,

2000

1

2000





Metoda simpleks - przykład

Teraz  przystępujemy  do  zmodyfikowania  macierzy 
współczynników  z  ograniczeń.  Wyniki  tej  modyfikacji 
zawieramy w kolejnej tablicy simpleksowej.

Metoda simpleks - przykład

Każdy element trzeciego wiersz macierzy współczynników 
wyjściowej  tablicy  simpleksowej  dzielimy  przez  element 
centralny, czyli przez 2.

Metoda simpleks - przykład

Przystępujemy do przeliczenia pierwszego wiersza 
macierzy współczynników zawartych w wyjściowej tablicy 
simpleksowej. W tym celu od każdego elementu tego 
wiersza odejmujemy, pomnożone przez 1, odpowiednie 
elementy trzeciego wiersza macierzy współczynników 
drugiej tablicy simpleksowej  zgodnie ze wzorem:

a

ij

 - a

ik

rk

rj

a

a

 

i otrzymujemy:

 a

ik

 =1, to

3 – 1x 0,5 = 2,5; 4 – 1x 1 = 3; 1 – 1x 1 = 0; 1 – 1x 0 = 

1; 0 – 1x 0 = 0; 

0 – 1x 0,5 = -0,5

Wyniki wpisujemy do pierwszego wiersza macierzy 

współczynników drugiej tablicy simpleksowej.

Metoda simpleks - przykład

Podobnie postępujemy przy przeliczeniu drugiego wiersza 
macierzy współczynników zawartych w wyjściowej tablicy 
simpleksowej. W tym celu od każdego elementu tego 
wiersza odejmujemy, pomnożone przez 0, odpowiednie 
elementy trzeciego wiersza macierzy współczynników 
drugiej tablicy simpleksowej. 

a

ik

 =0, to 1 – 0x 0,5 = 1; 2 – 0x 1 = 2; 0 – 0x 1 = 0; 0 – 0x 0 = 0; 1 – 

0x 0 = 1; 
0 – 0x 0,5 = 0. Jak łatwo zauważyć wiersz drugi przepisujemy bez 
zmian, ponieważ w trzeciej kolumnie macierzy współczynników 
odpowiadający temu wierszowi element wynosi 0.

1 -

0 x 0,5 = 1

1

Metoda simpleks - przykład

W podobny sposób przekształcamy wyrazy wolne 

zawarte w tablicy simpleksowej, zgodnie z formułą:

rk

r

a

b

2000 – 1

x

800 = 1200 i 800 – 0

x

800 = 800 .

Otrzymaliśmy w ten sposób  nowe rozwiązanie bazowe 

o  wartościach  zmiennych  decyzyjnych  bazowych:  x

4

  = 

1200, x

5

 = 800, x

3

 = 800.

b

i 

- a

ik

Metoda simpleks - przykład

Zmienne niebazowe x

1

, x

2

 i x

6

 przyjmują wartości zerowe, 

wartość  funkcji  celu  dla  tego  rozwiązania  wynosi 
natomiast 

4000 

zł, 

bo  f(x)  =  4x0  +  3x0  +  5x800  +  0x1200  +  0x800  + 
0x0 = 4000

Metoda simpleks - przykład

Należy zatem zbadać, czy otrzymane rozwiązanie 

bazowe jest już rozwiązaniem optymalnym. Obliczamy 

więc wskaźniki z

j

. Przykładowo z

1

 wynosi:

z

1 

= 0x2,5 + 0x1 + 5x0,5 = 2,5

Metoda simpleks - przykład

Odejmując  od  wagowych  współczynników  zmiennych 
decyzyjnych 

obliczone 

wskaźniki 

z

j

 

otrzymujemy 

wskaźniki 

optymalności, 

np. c

1

 – z

1

 = 1,5

Ponieważ  jeden  z  nich  jest  dodatni,  otrzymane  rozwiązanie  bazowe 
nie jest optymalne. Można więc skonstruować następne rozwiązanie, 
lepsze od poprzedniego, co też dalej uczynimy. Ponieważ tylko jeden 
ze  wskaźników  optymalności  (odpowiadający  zmiennej  x

1

)  jest 

dodatni c

1

 – z

1

 = 1,5 dlatego też zmienną x

1

 wprowadzamy do nowej 

bazy.  Pierwszą  kolumnę  macierzy  współczynników  odpowiadającą  tej 
zmiennej w drugiej tablicy simpleksowaj wyróżniamy.

Metoda simpleks - przykład

Aby ustalić, którą ze zmiennych x

4

, x

5

 i x

3

 należy 

wyeliminować z bazy, obliczamy wskaźniki stanowiące 
kryterium wyjścia, które w tym przypadku są ilorazami 
odpowiednich elementów kolumny wyrazów wolnych b

i

 i 

pierwszej kolumny macierzy współczynników:

 

.

1600

5

,

0

800

,

800

1

800

,

480

5

,

2

1200







Ponieważ  minimalny  z  tych  wskaźników  odpowiada 
zmiennej x

4

, dlatego też zmienną tę eliminujemy z bazy a 

na jej miejsce wprowadzamy zmienną x

1

. 

Współczynnik a

11

 = 2,5 jest tu elementem centralnym. 

Metoda simpleks - przykład

W kolumnie tablicy simpleksowej w miejsce zmiennej x

4

 

wpisujemy zmienną x

1

. Podobnie zmieniamy 

współczynniki wagowe tych zmiennych z 0 na 4. Każdy 
element pierwszego wiersza macierzy współczynników 
tablicy simpleksowej dzielimy przez element centralny, 
czyli przez 2,5. 

Metoda simpleks - przykład

Przystępujemy do przeliczenia drugiego wiersza macierzy 
współczynników zawartych w wyjściowej tablicy 
simpleksowej. W tym celu od każdego elementu tego 
wiersza odejmujemy, pomnożone przez 1, odpowiednie 
elementy pierwszego wiersza macierzy współczynników 
trzeciej tablicy simpleksowej. 

Metoda simpleks - przykład

Podobnie postępujemy przy przeliczeniu trzeciego wiersza 
macierzy współczynników zawartych w wyjściowej tablicy 
simpleksowej. W tym celu od każdego elementu tego 
wiersza odejmujemy, pomnożone przez 0,5, odpowiednie 
elementy pierwszego wiersza macierzy współczynników 
trzeciej tablicy simpleksowej.

Metoda simpleks - przykład

Jak łatwo zauważyć, macierz współczynników 

odpowiadających zmiennym bazowym x

1

, x

3

 i x

5

 zawarto 

w trzeciej tablicy simpleksowej jest macierzą 

jednostkową.

W podobny sposób przekształcamy wyrazy wolne zawarte 

w tablicy simpleksowej

.

Metoda simpleks - przykład

Otrzymaliśmy  w  ten  sposób  nowe  rozwiązanie  bazowe  o 
wartościach zmiennych decyzyjnych bazowych: x

1

 = 480, 

x

5

 = 320, x

3

 = 560.

Metoda simpleks - przykład

Zmienne niebazowe x

2

, x

4

 i x

6

 przyjmują wartości zerowe, 

wartość funkcji celu dla tego rozwiązania wynosi 
natomiast 4720 zł, 
bo f(x) = 4x480 + 3x0 + 5x560 + 0x0 + 0x320 + 0x0 
= 4720 

Należy zatem zbadać, czy otrzymane rozwiązanie bazowe 

jest już rozwiązaniem optymalnym. Obliczamy więc 

wskaźniki z

j

. 

Przykładowo z

1

 wynosi:

z

1

 = 4x1 + 0x0 + 5x0 = 4 

Metoda simpleks - przykład

Ponieważ nie ma wśród nich wskaźników o wartościach dodatnich, więc 

otrzymane rozwiązanie bazowe jest rozwiązaniem optymalny. Rozwiązanie to 

tworzą zmienne:

x

1

 = 480, x

3

 = 560, x

5

 = 320. 

Pozostałe zmienne, to zmienne niebazowe o wartościach zerowych:

x

2

 = x

4

 = x

6

 = 0.

Wartość funkcji celu wynosi 4720.

Otrzymany wynik oznacza, że przy produkcji wynoszącej 480 jednostek 

wyrobu A, 560 jednostek wyrobu C i jednoczesnym zaniechaniu produkcji 

wyrobu B, przy zachowaniu podanych ograniczeń surowcowych, łączny zysk 

osiągnięty ze sprzedaży wyrobów będzie maksymalny i będzie wynosił 4720 

zł. Jednocześnie zasoby surowca S

2

, zostaną niewykorzystane w ilości 320 kg.

Metoda simpleks - przykład

Ponieważ nie ma wśród nich wskaźników o wartościach dodatnich, więc 

otrzymane rozwiązanie bazowe jest rozwiązaniem optymalny. Rozwiązanie to 

tworzą zmienne:

x

1

 = 480, x

3

 = 560, x

5

 = 320. 

Pozostałe zmienne, to zmienne niebazowe o wartościach zerowych:

x

2

 = x

4

 = x

6

 = 0.

Wartość funkcji celu wynosi 4720.

Otrzymany wynik oznacza, że przy produkcji wynoszącej 480 jednostek 

wyrobu A, 560 jednostek wyrobu C i jednoczesnym zaniechaniu produkcji 

wyrobu B, przy zachowaniu podanych ograniczeń surowcowych, łączny zysk 

osiągnięty ze sprzedaży wyrobów będzie maksymalny i będzie wynosił 4720 

zł. Jednocześnie zasoby surowca S

2

, zostaną niewykorzystane w ilości 320 kg.

Metoda simpleks

Metoda simpleks – analiza wrażliwości

Rozwiązanie programu liniowego jest 
dopiero 

początkiem 

analizy 

problemu  decyzyjnego.  Decydent 
obok 

rozwiązania 

optymalnego 

powinien  wiedzieć,  jak  wrażliwe  jest 
uzyskane  rozwiązanie  optymalne  na 
zmian  w  założeniach  modelu  lub 
zmiany  czynników  zewnętrznych 
(parametrów  modelu).  Odpowiedzi 
na  te  pytania  udziela  analiza 
wrażliwości 

rozwiązania 

optymalnego  na  zmiany  niektórych 
parametrów modelu.