Wł. Filipowicz

Problemy optymalizacyjne

1

Podstawy informatyki

Wykład

Problemy optymalizacyjne

Wł. Filipowicz

Problemy optymalizacyjne

2

Problemy optymalizacyjne

Zagadnienia programowania matematycznego
dotyczą efektywnego wykorzystania środków
lub zasobów i w taki sposób aby spełnione były
określone wymagania. Zagadnienia takie
posiadają, najczęściej, bardzo dużo rozwiązań
spełniających stawiane warunki. Wybór jednego
z nich zależy od celu i stawianych wymagań.
Rozwiązanie które spełnia warunki
ograniczające jak i postawiony cel jest
rozwiązaniem optymalnym.

Wł. Filipowicz

Problemy optymalizacyjne

3

Problemy optymalizacyjne

Typowym przykładem jest maksymalizacja
dochodu w procesie produkcyjnym w
którym dostępne siły i środki są w określony
sposób ograniczone. Specjalną klasę
zagadnień tego typu stanowią zagadnienia
programowania liniowego. Matematyczny
model takiego problemu wykorzystuje tylko
zależności liniowe.

Wł. Filipowicz

Problemy optymalizacyjne

4

Przykładowy problem (1)

Rozpatrzmy problem ekstremalizacji funkcji:

f(x,y) = y + x

w obszarze ograniczonym nierównościami:

y - x - 3 <= 0

y - x >= 0
x - 2 <= 0
y + 1 >= 0

Wł. Filipowicz

Problemy optymalizacyjne

5

In

te

rp

re

ta

cj

a

y-x0

y-x  3

x  2

y -1

1

3

1

4

5

6

7

2

3

4

5

-1

-2

-3

-4

-5

2

3

w tym punkcie

funkcja f=y+x

osiąga warość

największą

w tym punkcie

funkcja f=y+x

osiąga wartość

najmniejszą

Wł. Filipowicz

Problemy optymalizacyjne

6

Przykładowy problem (2)

Zakład produkcyjny wytwarza cztery rodzaje sprzętu
radiowego. W ciągu miesiąca zakład, w warunkach
normalnej pracy, dysponuje 150000 roboczogodzinami z
tym, że pierwszy rodzaj sprzętu wymaga do
wyprodukowania 80 roboczogodzin, drugi 130, trzeci 110,
a czwarty 140.
Łącznie zakład może wyprodukować 2000 sztuk różnego
sprzętu. Dysponuje on 850 kilogramami materiału
specjalnego używanego w procesie produkcji z tego na
wyprodukowanie jednostki sprzętu pierwszego rodzaju
potrzeba 0.76 kg, drugiego 1 kg, trzeciego 0.72 kg, a
czwartego 1.55 kg.

Wł. Filipowicz

Problemy optymalizacyjne

7

Przykładowy problem (2)

Wiemy również że minimalne zamówienia wynoszą na
każdy rodzaj 50 sztuk, a na podstawie badań rynku
można liczyć się ze sprzedażą co najwyżej odpowiednio
800, 800, 700, 100 sztuk poszczególnych rodzajów.
Zaplanować produkcję, przynoszącą największy zysk,
jeśli ze sprzedaży jednej sztuki uzyskujemy odpowiednio
600, 700, 800, 1000 jednostek płatniczych.

Wł. Filipowicz

Problemy optymalizacyjne

8

Rozwiązanie

B

C

D

E

F

G

1

800

800

700

100

2

50

50

50

50

3

287.5

50

700

50

4
5

150000

113500

80

130

110

140

6

2000

1087.5

1

1

1

1

7

850

850

0.76

1

0.72

1.55

8
9

172500

35000

560000

50000

10
11

817500

współczynniki

ograniczeń

ograniczenia

wartości zmiennych

decyzyjnych

optymalne wartości

zmiennych

decyzyjnych

optymalne wartości dla

poszczególnych

zmiennych

wartości ograniczeń dla rozwiązania

optymalnego

optymalna (największa) wartość funkcji celu

Wł. Filipowicz

Problemy optymalizacyjne

9

Raport wrażliwości

Wartość

Przyrost

Komórka

Nazwa

końcowa

marginalny

$E$7

287.50

0.00

$F$7

50.00

-89.47

$G$7

700.00

231.58

$H$7

50.00

-223.68

Wartość

Mnożnik

Komórka

Nazwa

końcowa

Lagrange'a

$D$9

113500.0

0

$D$10

1087.5

0

$D$11

850.0

789.47