Uniwersytet Kardynała Stefana Wyszyńskiego

Wydział Matematyczno-Przyrodniczy

Szkoła Nauk Ścisłych

Badania Operacyjne

Kolokwium

17-01-2007

Zadania

Należy rozwiązać podane niżej zadania. Rozwiązania powinny być poparte uzasadnieniem (albo algorytmicz-
nym albo słownym). Podanie samego rozwiązania (albo odpowiedzi np „tak” lub „nie”) nie będzie punktowane.
Wszystkie zadania powinny być rozwiązane w sposób schludny i przejrzysty i kończyć się odpowiedzią.

Zadanie 1

(20 pkt.)

Rozwiązać następujące zadanie programowania nieliniowego

max

x∈R

2

f (x) =

3

2

x

2
1

+ 2x

1

x

2

+ 2x

2
2

+ 6

przy ograniczeniach:

x

1

+ 2x

2

¬ 8

x

1

¬ 5

Zadanie 2

(15 pkt.)

Znaleźć przepływ maksymalny i przekrój minimalny dla następującego grafu (możliwy przepływ w obie strony,
na każdej gałęzi zaznaczono przepustowość maksymalną) od węzłów S

1

oraz S

2

do węzła T

S1

A

B

C

D

T

2

8

7

2

2

3

7

1

S1

2

Zadanie 3

(15 pkt.)

Znaleźć najkrótszą ścieżkę od węzła S do węzła T w poniższym grafie (oraz podać jej koszt)

S

B

E

A

F

T

3

6

11

5

7

4

5

3

C

D

3

2

2

4

Badania Operacyjne, kolokwium, 17-01-2007

1