Uniwersytet Kardynała Stefana Wyszyńskiego

Wydział Matematyczno-Przyrodniczy

Szkoła Nauk Ścisłych

Badania Operacyjne

Kolokwium

30-05-2006

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 zagadnienie programowania nieliniowego wykorzystując warunki konieczne Kuhna-
Tuckera

min −x

1

− x

2

− x

3

+

1

2

x

2
1

+ x

2
2

+ x

2
3

(1)

przy ograniczeniach

x

1

+ x

2

+ x

3

¬

2

(2)

4x

1

+ 2x

2

¬

8

3

(3)

Zadanie 2

(15 pkt.)

Znaleźć przepływ maksymalny oraz przekrój minimalny dla następującego grafu (możliwy jest przepływ w
obie strony)

S

a

b

c

d

e

f

t

10

6

8

8

2

5

3

3

2

3

7

5

Zadanie 3

(15 pkt.)

Znaleźć najkrótszą drogę od węzła s do węzła t. Możliwy jest przejazd w obie strony po zaznaczonych na
poniższym grafie ścieżkach.

S

a

c

d

b

e

t

2

4

4

6

2

7

3

1

1

4

6

13

7

Badania Operacyjne, kolokwium, 30-05-2006

1