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.