P

ro

g

ra

m

o

w

a

n

ie

 l

in

io

w

e

 

P

ro

g

ra

m

o

w

a

n

ie

 l

in

io

w

e

 

–

–

za

g

a

d

n

ie

n

ia

 d

u

a

ln

e

za

g

a

d

n

ie

n

ia

 d

u

a

ln

e

Z

 k

a

Ŝ

d

y

m

 z

a

d

a

n

ie

m

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 w

 p

o

st

a

ci

 k

la

sy

cz

n

e

j 

(

za

d

a

n

ie

 

p

ry

m

a

rn

e

P

L

),

 m

o

Ŝ

n

a

 z

w

ią

za

ć

o

d

p

o

w

ia

d

a

ją

ce

 m

u

 

za

d

a

n

ie

 d

u

a

ln

e

R

o

zp

a

tr

zm

y

, 

zn

a

n

y

 j

u

Ŝ

p

rz

y

k

ła

d

 z

a

d

a

n

ia

 P

L

: 

w

 p

o

st

a

ci

 k

la

sy

cz

n

e

j:

max

3

2

2

1

→

+

x

x

0

,

16

 
4

8  

 

2

 

14

2

2

2

1

1

2

1

2

1

≥

≤

≤

+

≤

+

x
x

x

x

x

x

x

w

 p

o

st

a

ci

 k

la

sy

cz

n

e

j

w

 p

o

st

a

ci

 k

la

sy

cz

n

e

j:

c

x

 →

m

a

x

A

x

 ≤

b

x

  

≥

0

w

 p

o

st

a

ci

 m

a

ci

e

rz

o

w

e

j:

w

 p

o

st

a

ci

 m

a

ci

e

rz

o

w

e

j:

[

]

  

3

2

c

=





















=

0

4

2

2

2

2

A





















=

16

8

14

b

 



 



=

2

1

x

x

x

O

zn

a

cz

m

y

 p

rz

e

z 

:

3

2

1

  ,
  ,

y

y

y

ce

n

y

 w

y

k

o

rz

y

st

y

w

a

n

y

ch

 s

u

ro

w

có

w

 

S

1

, 

S

2

,

i 

S

3

i 

p

o

tr

a

k

tu

jm

y

 j

e

 j

a

k

o

 z

m

ie

n

n

e

 d

e

cy

zy

jn

e

M

o

Ŝ

e

m

y

 z

a

te

m

 z

b

u

d

o

w

a

ć

n

o

w

y

 m

o

d

e

l 

m

a

te

m

a

ty

cz

n

y

, 

k

tó

re

g

o

 r

o

zw

ią

za

n

ie

 p

o

zw

o

li 

o

k

re

ś

lić

, 

ja

k

ie

 p

o

w

in

n

y

 b

y

ć

w

a

rt

o

ś

c

i

ty

ch

 z

m

ie

n

n

y

ch

 a

b

y

 z

m

in

im

a

li

z

o

w

a

ć

w

a

rt

o

ś

ci

 p

o

si

a

d

a

n

y

ch

 ś

ro

d

k

ó

w

.

Z

a

ło

Ŝ

e

n

ie

m

 o

cz

y

w

is

ty

m

 j

e

st

, 

Ŝ

e

 w

a

rt

o

ść

su

ro

w

có

w

 w

y

k

o

rz

y

st

a

n

y

ch

 d

o

 

w

y

tw

o

rz

e

n

ia

 j

e

d

n

e

j 

je

d

n

o

st

k

i 

p

ro

d

u

k

tu

 P

1

i 

p

ro

d

u

k

tu

 P

2

są

n

ie

 m

n

ie

js

ze

 o

d

 z

y

sk

u

 

o

si

ą

g

n

ię

te

g

o

 z

 w

y

tw

o

rz

e

n

ia

 j

e

d

n

o

st

k

i 

p

ro

d

u

k

tó

w

 (

o

d

p

o

w

ie

d

n

io

 P

1

i 

P

2

)

3

2

Z

Y

S

K

1

6

0

4

S

3

8

2

1

S

2

1

4

2

2

S

1

Z

A

S

O

B

Y

P

2

P

1

O

g

ó

ln

a

 w

a

rt

o

ś

ć

p

o

si

a

d

a

n

y

ch

 s

u

ro

w

có

w

:

3

2

1

16

8

14

y

y

y

+

+

W

a

rt

o

ść

su

ro

w

có

w

 p

o

tr

ze

b

n

a

 d

o

 w

y

tw

o

rz

e

n

ia

:

p

ro

d

u

k

tu

 

P

1

3

2

1

4

2

y

y

y

+

+

p

ro

d

u

k

tu

 

P

2

2

1

2

2

y

y

+

Z

a

d

a

n

ie

 m

in

im

a

liz

a

cj

i 

w

a

rt

o

ś

ci

 z

a

st

o

so

w

a

n

y

ch

 s

u

ro

w

có

w

 d

o

 p

ro

d

u

k

cj

i 

w

y

ro

b

ó

w

 P

1

i 

P

2

p

rz

y

 o

g

ra

n

ic

ze

n

ia

ch

 n

a

 w

a

rt

o

ś

ci

 t

y

ch

 s

u

ro

w

có

w

 z

a

p

is

ze

m

y

 

n

a

st

ę

p

u

ją

co

:

min

16

8

14

3

2

1

→

+

+

y

y

y

2

4

2

3

2

1

≥

+

+

y

y

y

3

2

2

2

1

≥

+

y

y

0

,
,

3

2

1

≥
y
y
y

Z

a

d

a

n

ie

 t

o

 m

o

Ŝ

n

a

 z

a

p

is

a

ć

w

 p

o

s

ta

c

i 

m

a

c

ie

rz

o

w

e

j:

O

k

re

ś

la

ją

c 

w

e

k

to

r 

zm

ie

n

n

y

ch

 d

e

cy

zy

jn

y

ch

 j

a

k

o

 y

=

 [

y

1

, 

y

2

, 

y

3

]

o

tr

zy

m

a

m

y

:

y

b

 →

m

in

y

A

 ≥

c

y

≥

0

je

st

 t

o

 

za

d

n

ie

n

ie

 d

u

a

ln

e

za

d

n

ie

n

ie

 d

u

a

ln

e

d

o

 u

p

rz

e

d

n

io

 p

rz

e

d

st

a

w

io

n

e

g

o

 

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

Z

a

d

a

n

ia

 p

ry

m

a

rn

e

i 

d

u

a

ln

e

p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 c

h

a

ra

k

te

ry

zu

ją

si

ę

n

a

st

ę

p

u

ją

cy

m

i 

w

ła

sn

o

ś

ci

a

m

i:

1

.

K

a

Ŝ

d

e

m

u

 w

a

ru

n

k

o

w

i 

o

g

ra

n

ic

za

ją

ce

m

u

 j

e

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

zm

ie

n

n

a

 d

e

cy

zy

jn

a

 d

ru

g

ie

g

o

 Z

m

ie

n

n

a

 t

ę

n

a

zy

w

a

m

y

 

zm

ie

n

n

zm

ie

n

n

ą

ą

k

o

m

p

le

m

e

n

ta

rn

k

o

m

p

le

m

e

n

ta

rn

ą

ą

d

o

 d

a

n

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

Z

a

d

a

n

ia

 p

ry

m

a

rn

e

i 

d

u

a

ln

e

p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 c

h

a

ra

k

te

ry

zu

ją

si

ę

n

a

st

ę

p

u

ją

cy

m

i 

w

ła

sn

o

ś

ci

a

m

i:

1

.

K

a

Ŝ

d

e

m

u

 w

a

ru

n

k

o

w

i 

o

g

ra

n

ic

za

ją

ce

m

u

 j

e

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

zm

ie

n

n

a

 d

e

cy

zy

jn

a

 d

ru

g

ie

g

o

 Z

m

ie

n

n

a

 t

ę

n

a

zy

w

a

m

y

 

zm

ie

n

n

zm

ie

n

n

ą

ą

k

o

m

p

le

m

e

n

ta

rn

k

o

m

p

le

m

e

n

ta

rn

ą

ą

d

o

 d

a

n

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

W

 z

a

d

a

n

iu

 d

u

a

ln

y

m

 z

m

ie

n

n

y

m

i 

k

o

m

p

le

m

e

n

ta

rn

y

m

i 

d

o

 p

ie

rw

sz

e

g

o

, 

d

ru

g

ie

g

o

 i

 

tr

ze

ci

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 s

ą

, 

o

d

p

o

w

ie

d

n

io

, 

zm

ie

n

n

e

n

a

to

m

ia

st

 w

 z

a

d

a

n

iu

 p

ry

m

a

rn

y

m

 z

m

ie

n

n

y

m

i 

k

o

m

p

le

m

e

n

ta

rn

y

m

i 

d

o

 

p

ie

rw

sz

e

g

o

 i

 d

ru

g

ie

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

 z

a

d

a

n

iu

 d

u

a

ln

e

g

o

 s

ą

, 

o

d

p

o

w

ie

d

n

io

, 

zm

ie

n

n

e

  

  

  

  

  

  

3

2

1

  ,
  ,

y

y

y

2

1

  i 

x

x

Z

a

d

a

n

ia

 p

ry

m

a

rn

e

i 

d

u

a

ln

e

p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 c

h

a

ra

k

te

ry

zu

ją

si

ę

n

a

st

ę

p

u

ją

cy

m

i 

w

ła

sn

o

ś

ci

a

m

i:

1

.

K

a

Ŝ

d

e

m

u

 w

a

ru

n

k

o

w

i 

o

g

ra

n

ic

za

ją

ce

m

u

 j

e

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

zm

ie

n

n

a

 d

e

cy

zy

jn

a

 d

ru

g

ie

g

o

 Z

m

ie

n

n

a

 t

ę

n

a

zy

w

a

m

y

 

zm

ie

n

n

zm

ie

n

n

ą

ą

k

o

m

p

le

m

e

n

ta

rn

k

o

m

p

le

m

e

n

ta

rn

ą

ą

d

o

 d

a

n

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

2

.

K

a

Ŝ

d

e

j 

n

ie

u

je

m

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j 

je

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

 d

ru

g

ie

g

o

. 

W

a

ru

n

e

k

 t

e

n

 n

a

zy

w

a

m

y

 

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

d

o

 d

a

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j

Z

a

d

a

n

ia

 p

ry

m

a

rn

e

i 

d

u

a

ln

e

p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 c

h

a

ra

k

te

ry

zu

ją

si

ę

n

a

st

ę

p

u

ją

cy

m

i 

w

ła

sn

o

ś

ci

a

m

i:

1

.

K

a

Ŝ

d

e

m

u

 w

a

ru

n

k

o

w

i 

o

g

ra

n

ic

za

ją

ce

m

u

 j

e

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

zm

ie

n

n

a

 d

e

cy

zy

jn

a

 d

ru

g

ie

g

o

 Z

m

ie

n

n

a

 t

ę

n

a

zy

w

a

m

y

 

zm

ie

n

n

zm

ie

n

n

ą

ą

k

o

m

p

le

m

e

n

ta

rn

k

o

m

p

le

m

e

n

ta

rn

ą

ą

d

o

 d

a

n

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

2

.

K

a

Ŝ

d

e

j 

n

ie

u

je

m

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j 

je

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

 d

ru

g

ie

g

o

. 

W

a

ru

n

e

k

 t

e

n

 n

a

zy

w

a

m

y

 

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

d

o

 d

a

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j

W

 r

o

zp

a

tr

y

w

a

n

y

m

 z

a

d

a

n

iu

 p

ry

m

a

rn

y

m

 z

m

ie

n

n

y

m

  

  

  

  

  

  

 o

d

p

o

w

ia

d

a

ją

k

o

m

p

le

m

e

n

ta

rn

e

 

w

a

ru

n

k

i 

o

g

ra

n

ic

za

ją

ce

: 

p

ie

rw

sz

y

 i

 d

ru

g

i 

za

d

a

n

ia

 d

u

a

ln

e

g

o

, 

n

a

to

m

ia

st

 z

m

ie

n

n

y

m

  

  

  

 

w

 z

a

d

a

n

iu

 d

u

a

ln

y

m

 o

d

p

o

w

ia

d

a

ją

k

o

m

p

le

m

e

n

ta

rn

e

 w

a

ru

n

k

i 

o

g

ra

n

ic

za

ją

ce

: 

p

ie

rw

sz

y

, 

d

ru

g

i 

i 

tr

ze

ci

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

  

  

3

2

1

  ,
  ,

y

y

y

2

1

  i 

x

x

Z

a

d

a

n

ia

 p

ry

m

a

rn

e

i 

d

u

a

ln

e

p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 c

h

a

ra

k

te

ry

zu

ją

si

ę

n

a

st

ę

p

u

ją

cy

m

i 

w

ła

sn

o

ś

ci

a

m

i:

1

.

K

a

Ŝ

d

e

m

u

 w

a

ru

n

k

o

w

i 

o

g

ra

n

ic

za

ją

ce

m

u

 j

e

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

zm

ie

n

n

a

 d

e

cy

zy

jn

a

 d

ru

g

ie

g

o

 Z

m

ie

n

n

a

 t

ę

n

a

zy

w

a

m

y

 

zm

ie

n

n

zm

ie

n

n

ą

ą

k

o

m

p

le

m

e

n

ta

rn

k

o

m

p

le

m

e

n

ta

rn

ą

ą

d

o

 d

a

n

e

g

o

 w

a

ru

n

k

u

 o

g

ra

n

ic

za

ją

ce

g

o

2

.

K

a

Ŝ

d

e

j 

n

ie

u

je

m

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j 

je

d

n

e

g

o

 z

 p

ro

b

le

m

ó

w

 o

d

p

o

w

ia

d

a

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

 d

ru

g

ie

g

o

. 

W

a

ru

n

e

k

 t

e

n

 n

a

zy

w

a

m

y

 

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

w

a

ru

n

k

ie

m

 k

o

m

p

le

m

e

n

ta

rn

y

m

d

o

 d

a

n

e

j 

zm

ie

n

n

e

j 

d

e

cy

zy

jn

e

j

3

.

W

e

k

to

r 

w

sp

ó

łc

zy

n

n

ik

ó

w

 p

rz

y

 f

u

n

k

cj

i 

ce

lu

 w

 j

e

d

n

y

m

 z

a

d

a

n

iu

 s

ta

je

 s

ię

w

e

k

to

re

m

 w

y

ra

zó

w

 w

o

ln

y

ch

 w

 d

ru

g

im

, 

i 

o

d

w

ro

tn

ie

, 

w

e

k

to

r 

w

y

ra

zó

w

 

w

o

ln

y

ch

 w

 j

e

d

n

y

m

 z

a

d

a

n

iu

 j

e

st

 w

e

k

to

re

m

 w

sp

ó

łc

zy

n

n

ik

ó

w

 p

rz

y

 f

u

n

k

cj

i 

ce

lu

 w

 d

ru

g

i.

4

.

K

ie

ru

n

k

i 

o

p

ty

m

a

liz

a

cj

i 

d

la

 z

a

d

a

ń

d

u

a

ln

y

ch

 s

ą

p

rz

e

ci

w

n

e

.

O

 i

le

 z

a

d

a

n

ie

 p

ry

m

a

rn

e

 j

e

st

 z

a

d

a

n

ie

m

 m

a

k

sy

m

a

liz

a

cj

i,

 t

o

 w

 o

d

p

o

w

ia

d

a

ją

cy

m

 m

u

 

za

d

a

n

iu

 d

u

a

ln

y

m

 f

u

n

k

cj

e

 c

e

lu

 m

in

im

a

liz

u

je

m

y

.

5

.

Z

w

ro

ty

 n

ie

ró

w

n

o

ś

ci

 w

 w

a

ru

n

k

a

ch

 o

g

ra

n

ic

za

ją

cy

ch

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 s

ą

p

rz

e

ci

w

n

e

 d

o

 z

w

ro

tó

w

 n

ie

ró

w

n

o

ś

ci

 w

a

ru

n

k

ó

w

 o

g

ra

n

ic

za

ją

cy

ch

 z

a

d

a

n

iu

 

d

u

a

ln

e

g

o

.

P

o

d

st

a

w

o

w

e

 t

w

ie

rd

ze

n

ia

 o

 d

u

a

ln

o

P

o

d

st

a

w

o

w

e

 t

w

ie

rd

ze

n

ia

 o

 d

u

a

ln

o

ś

ś

ci

ci

T

W

I

E

R

D

Z

E

N

I

E

1

Je

Ŝ

e

li 

x

i 

y

s

ą

d

o

w

o

ln

ym

i 

ro

zw

i

ą

za

n

ia

m

i 

d

o

p

u

sz

cz

a

ln

ym

i,

 o

d

p

o

w

ie

d

n

io

, 

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 i

 d

u

a

ln

e

g

o

, 

to

 w

a

rt

o

ś

ci

 f

u

n

kc

ji 

ce

lu

 w

 t

yc

h

 z

a

d

a

n

ia

ch

 

sp

e

ł

n

ia

j

ą

za

le

Ŝ

n

o

ść

:

c

x

 

≤

y

b

T

W

I

E

R

D

Z

E

N

I

E

2

( 

o

 k

o

m

p

le

m

e

n

ta

rn

o

ś

ci

)

Je

Ŝ

e

li 

x

i 

y

s

ą

ro

zw

i

ą

za

n

ia

m

i 

o

p

ty

m

a

ln

ym

i,

 o

d

p

o

w

ie

d

n

io

, 

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 

i 

d

u

a

ln

e

g

o

, 

to

 z

a

ch

o

d

z

ą

zw

i

ą

zk

i:

y

 (

 b

 –

A

x

 )

 =

 0

  

 z

w

ią

ze

k

 (

1

)

x

 (

y

A

  

-

c

 )

 =

 0

  

 z

w

ią

ze

k

 (

2

)

T

W

I

E

R

D

Z

E

N

I

E

3

D

la

 r

o

zw

i

ą

za

ń

o

p

ty

m

a

ln

yc

h

 x

i 

y

o

d

p

o

w

ie

d

n

io

, 

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 i

 

d

u

a

ln

e

g

o

 z

a

ch

o

d

zi

 z

w

i

ą

ze

k:

c

 x

  

=

 y

 b

P

rz

y

k

ła

d

 z

a

s

to

s

o

w

a

n

ia

 

tw

ie

rd

z

e

n

ia

 o

 k

o

m

p

le

m

e

n

ta

rn

o

tw

ie

rd

z

e

n

ia

 o

 k

o

m

p

le

m

e

n

ta

rn

o

ś

ś

c

i

c

i

ro

zp

is

zm

y

 z

w

ią

ze

k

  

(1

)

y

 (

 b

 –

A

x

 )

 

=









































−

−

−

−

−

=





















 



 

 ⋅





















−





















=

1

2

1

2

1

2

1

3

2

1

4

16

2

8

2

2

14

0

4

2

1

2

2

16

8

14

]
,
,
[

x

x

x

x

x

x

x

y
y
y

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

=

x

y

x

x

y

x

x

y

ro

zp

is

zm

y

 z

w

ią

ze

k

  

(2

)

(y

A

  

-

c

 )

 x

 

[

]

=

 



 

 ⋅

 



 



 



 



−

+

−

+

+

=

 



 

 ⋅





















 



 



−





















⋅

=

2

1

2

1

3

2

1

2

1

3

2

1

3

2

2

2

4

2

3

2

0

4

2

1

2

2

,
,

x

x

y

y

y

y

y

x

x

y
y
y

0

)

3

2

2(

)

2

4

2(

2

2

1

1

3

2

1

=

−

+

+

−

+

+

=

x

y

y

x

y

y

y

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

x

y

x

x

y

x

x

y

ze

 z

w

ią

zk

u

 (

1

)

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

x

y

x

x

y

x

x

y

1

 s

k

ła

d

n

ik

2

 s

k

ła

d

n

ik

3

 s

k

ła

d

n

ik

ze

 z

w

ią

zk

u

 (

1

)

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

x

y

x

x

y

x

x

y

1

 s

k

ła

d

n

ik

2

 s

k

ła

d

n

ik

3

 s

k

ła

d

n

ik

su

m

a

 t

y

ch

 s

k

ła

d

n

ik

ó

w

 m

a

 d

a

ć

w

a

rt

o

ś

ć

ze

ro

+

+

ze

 z

w

ią

zk

u

 (

1

)

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

x

y

x

x

y

x

x

y

1

 s

k

ła

d

n

ik

2

 s

k

ła

d

n

ik

3

 s

k

ła

d

n

ik

su

m

a

 t

y

ch

 s

k

ła

d

n

ik

ó

w

 m

a

 d

a

ć

w

a

rt

o

ś

ć

ze

ro

+

+

W

y

n

ik

a

 s

tą

d

, 

Ŝ

e

 k

a

Ŝ

d

y

 s

k

ła

d

n

ik

 t

e

j 

su

m

y

 m

u

si

 b

y

ć

ró

w

n

y

 z

e

ru

.

ze

 z

w

ią

zk

u

 (

1

)

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−
−

+

−

−

x

y

x

x

y

x

x

y

1

 s

k

ła

d

n

ik

2

 s

k

ła

d

n

ik

3

 s

k

ła

d

n

ik

su

m

a

 t

y

ch

 s

k

ła

d

n

ik

ó

w

 m

a

 d

a

ć

w

a

rt

o

ś

ć

ze

ro

+

+

W

y

n

ik

a

 s

tą

d

, 

Ŝ

e

 k

a

Ŝ

d

y

 s

k

ła

d

n

ik

 t

e

j 

su

m

y

 m

u

si

 b

y

ć

ró

w

n

y

 z

e

ru

.

b

o

 g

d

yb

y 

ch

o

ć

je

d

e

n

 z

 t

yc

h

 s

k

ł

a

d

n

ik

ó

w

 b

y

ł

d

o

d

a

tn

i,

 t

o

 

p

rz

yn

a

jm

n

ie

j 

je

d

e

n

 m

u

si

a

ł

b

y 

p

rz

yj

ą

ć

w

a

rt

o

ś

ć

u

je

m

n

ą

a

 t

o

 

n

ie

 j

e

st

 m

o

Ŝ

liw

e

ze

 z

w

ią

zk

u

 (

1

)

o

tr

zy

m

a

m

y

 z

a

le

Ŝ

n

o

ś

ci

:

z

a

le

Ŝ

n

o

ś

ć

(1

a

)

0
)

2

2

14(

2

1

1

=

−

−

x

x

y

z

a

le

Ŝ

n

o

ś

ć

(1

b

)

0
)

2

8(

2

1

2

=

−
−

x

x

y

z

a

le

Ŝ

n

o

ś

ć

(1

c

)

0
)
4

16(

1

3

=

−

x

y

(

)

(

)

(

)

0

4

16

2

8

2

2

14

1

3

2

1

2

2

1

1

=

−

+

−

−

+

−

−

x

y

x

x

y

x

x

y

z 

r

z 

r

ó

ó

w

n

a

n

ia

 (

1

)

w

n

a

n

ia

 (

1

)

→

→

→

→

W

a

ru

n

e

k

 (

1

a

)

Je

Ŝ

e

li,

  

  

  

  

  

  

 t

o

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

O

zn

a

cz

a

 t

o

, 

Ŝ

e

 p

rz

y

 z

a

d

a

n

iu

 p

ry

m

a

rn

y

m

 

p

ie

rw

s

z

y

 w

a

ru

n

e

k

 o

g

ra

n

ic

z

a

ją

c

y

, 

k

o

m

p

le

m

e

n

ta

rn

y

 d

o

 z

m

ie

n

n

e

j 

  

  

  

  

  

  

  

, 

m

u

si

 b

y

ć

sp

e

łn

io

n

y

 j

a

k

o

 r

ó

w

n

a

n

ie

.

Je

Ŝ

e

li 

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

(c

zy

li 

w

 z

a

d

a

n

iu

 p

ry

m

a

rn

y

m

 p

ie

rw

s

z

y

 w

a

ru

n

e

k

 

o

g

ra

n

ic

z

a

ją

c

y

je

st

 s

p

e

łn

io

n

y

 j

a

k

o

 

n

ie

ró

w

n

o

ść

o

st

ra

) 

–

to

 z

m

ie

n

n

a

 k

o

m

p

le

m

e

n

ta

rn

a

 

0

1

>
y

0

2

2

14

2

1

=

−

−

x

x

0

1

>
y

0

2

2

14

2

1

>

−

−

x

x

0

1

=
y

o

tr

zy

m

a

m

y

 z

a

le

Ŝ

n

o

ś

ci

:

z

a

le

Ŝ

n

o

ś

ć

(2

a

)

0

)

2

4

2(

1

3

2

1

=

−

+

+

x

y

y

y

z

a

le

Ŝ

n

o

ś

ć

(2

b

)

0

)

3

2

2(

2

2

1

=

−

+

x

y

y

→

→

→

W

a

ru

n

e

k

 (

2

a

)

Je

Ŝ

e

li,

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

co

 o

zn

a

cz

a

 Ŝ

e

 p

ie

rw

sz

y

 w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

w

 

z

a

d

a

n

iu

 d

u

a

ln

y

m

 j

e

st

 s

p

e

łn

io

n

y

 j

a

k

o

o

s

tr

a

 n

ie

ró

w

n

o

ś

ć

),

 t

o

 z

m

ie

n

n

a

 

k

o

m

p

le

m

e

n

ta

rn

a

 

Je

Ŝ

e

li 

  

  

  

  

  

  

  

  

 t

o

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

  

 

O

zn

a

cz

a

 t

o

, 

Ŝ

e

 p

ie

rw

sz

y

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

 w

 z

a

d

a

n

iu

 d

u

a

ln

y

m

, 

k

o

m

p

le

m

e

n

ta

rn

y

 d

o

 z

m

ie

n

n

e

j 

  

  

  

  

m

u

si

 b

y

ć

sp

e

łn

io

n

y

 j

a

k

o

ró

w

n

a

n

ie

0

2

4

2

3

2

1

>
−

+

+

y

y

y

0

1

=
x

0

2

4

2

3

2

1

=
−

+

+

y

y

y

0

1

>
x

0

)

3

2

2(

)

2

4

2(

2

2

1

1

3

2

1

=

−

+

+

−

+

+

x

y

y

x

y

y

y

z 

r

z 

r

ó

ó

w

n

a

n

ia

 (

2

)

w

n

a

n

ia

 (

2

)

=

0

=

0

U

o

g

ó

ln

ie

n

ie

 p

rz

e

d

s

ta

w

io

n

y

c

h

 w

a

ru

n

k

ó

w

1

.

Je

Ŝ

e

li 

d

o

w

o

ln

a

 z

m

ie

n

n

a

w

 r

o

zw

ią

za

n

iu

 o

p

ty

m

a

ln

y

m

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 

lu

b

 d

u

a

ln

e

g

o

 j

e

st

 

d

o

d

a

tn

ia

d

o

d

a

tn

ia

, 

to

 o

d

p

o

w

ia

d

a

ją

cy

 j

e

j 

k

o

m

p

le

m

e

n

ta

rn

y

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

sp

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

r

r

ó

ó

w

n

a

n

ie

w

n

a

n

ie

2

.

Je

Ŝ

e

li 

d

o

w

o

ln

y

 w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

d

la

 r

o

zw

ią

za

n

ia

 o

p

ty

m

a

ln

e

g

o

 z

a

d

a

n

ia

 

p

ry

m

a

rn

e

g

o

 l

u

b

 d

u

a

ln

e

g

o

 s

p

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

o

st

ra

 n

ie

r

o

st

ra

 n

ie

r

ó

ó

w

n

o

w

n

o

ść

ść

, 

to

 

o

d

p

o

w

ia

d

a

ją

ca

 t

e

m

u

 w

a

ru

n

k

o

w

i 

zm

ie

n

n

a

 k

o

m

p

le

m

e

n

ta

rn

a

p

rz

y

jm

u

je

 

w

a

rt

o

ść

ze

ro

ze

ro

.

P

rz

y

k

ła

d

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 –

z

a

g

a

d

n

ie

n

ia

 d

u

a

ln

e

max

3

2
)
,
(

2

1

2

1

→

+

=

x

x

x
x
f

14

2

2

2

1

≤

+

x

x

8

2

2

1

≤

+

x

x

16

4

1

≤
x

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

2

      ,

4

2

1

=

=

x

x

min

16

8

14
)
,
,
(

3

2

1

3

2

1

*

→

+

+

=

y

y

y

y
y
y
f

2

4

2

3

2

1

≥

+

+

y

y

y

3

          

2

2

2

1

≥

+

y

y

0

,

2

1

≥
x
x

0

y,
,

3

2

1

≥

y
y

P

rz

y

k

ła

d

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 –

z

a

g

a

d

n

ie

n

ia

 d

u

a

ln

e

max

3

2
)
,
(

2

1

2

1

→

+

=

x

x

x
x
f

14

2

2

2

1

≤

+

x

x

8

2

2

1

≤

+

x

x

16

4

1

≤
x

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

2

      ,

4

2

1

=

=

x

x

min

16

8

14
)
,
,
(

3

2

1

3

2

1

*

→

+

+

=

y

y

y

y
y
y
f

2

4

2

3

2

1

≥

+

+

y

y

y

3

          

2

2

2

1

≥

+

y

y

0

,

2

1

≥
x
x

0

y,
,

3

2

1

≥

y
y

P

o

n

ie

w

a

Ŝ

zm

ie

n

n

e

 

0

,

2

1

≥
x
x

w

ię

c 

o

d

p

o

w

ia

d

a

ją

ce

 i

m

 w

a

ru

n

k

i 

k

o

m

p

le

m

e

n

ta

rn

e

 

m

u

sz

ą

b

y

ć

sp

e

łn

io

n

e

 j

a

k

o

 r

ó

w

n

a

n

ia

2

4

2

3

2

1

=

+

+

y

y

y

3

        

2

2

2

1

=

+

y

y

U

o

g

ó

ln

ie

n

ie

 p

rz

e

d

s

ta

w

io

n

y

c

h

 w

a

ru

n

k

ó

w

1

.

Je

Ŝ

e

li 

d

o

w

o

ln

a

 z

m

ie

n

n

a

w

 r

o

zw

ią

za

n

iu

 o

p

ty

m

a

ln

y

m

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 

lu

b

 d

u

a

ln

e

g

o

 j

e

st

 

d

o

d

a

tn

ia

d

o

d

a

tn

ia

, 

to

 o

d

p

o

w

ia

d

a

ją

cy

 j

e

j 

k

o

m

p

le

m

e

n

ta

rn

y

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

sp

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

r

r

ó

ó

w

n

a

n

ie

w

n

a

n

ie

2

.

Je

Ŝ

e

li 

d

o

w

o

ln

y

 w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

d

la

 r

o

zw

ią

za

n

ia

 o

p

ty

m

a

ln

e

g

o

 z

a

d

a

n

ia

 

p

ry

m

a

rn

e

g

o

 l

u

b

 d

u

a

ln

e

g

o

 s

p

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

o

st

ra

 n

ie

r

o

st

ra

 n

ie

r

ó

ó

w

n

o

w

n

o

ść

ść

, 

to

 

o

d

p

o

w

ia

d

a

ją

ca

 t

e

m

u

 w

a

ru

n

k

o

w

i 

zm

ie

n

n

a

 k

o

m

p

le

m

e

n

ta

rn

a

p

rz

y

jm

u

je

 

w

a

rt

o

ść

ze

ro

ze

ro

.

P

rz

y

k

ła

d

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 –

z

a

g

a

d

n

ie

n

ia

 d

u

a

ln

e

max

3

2
)
,
(

2

1

2

1

→

+

=

x

x

x
x
f

14

2

2

2

1

≤

+

x

x

8

2

2

1

≤

+

x

x

16

4

1

≤
x

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

2

      ,

4

2

1

=

=

x

x

min

16

8

14
)
,
,
(

3

2

1

3

2

1

*

→

+

+

=

y

y

y

y
y
y
f

2

4

2

3

2

1

≥

+

+

y

y

y

3

          

2

2

2

1

≥

+

y

y

0

,

2

1

≥
x
x

0

y,
,

3

2

1

≥

y
y

P

o

n

ie

w

a

Ŝ

zm

ie

n

n

e

 

0

,

2

1

≥
x
x

w

ię

c 

o

d

p

o

w

ia

d

a

ją

ce

 i

m

 w

a

ru

n

k

i 

k

o

m

p

le

m

e

n

ta

rn

e

 

m

u

sz

ą

b

y

ć

sp

e

łn

io

n

e

 j

a

k

o

 r

ó

w

n

a

n

ia

2

4

2

3

2

1

=

+

+

y

y

y

3

        

2

2

2

1

=

+

y

y

P

rz

y

k

ła

d

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 –

z

a

g

a

d

n

ie

n

ia

 d

u

a

ln

e

max

3

2
)
,
(

2

1

2

1

→

+

=

x

x

x
x
f

14

2

2

2

1

≤

+

x

x

8

2

2

1

≤

+

x

x

16

4

1

≤
x

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

2

      ,

4

2

1

=

=

x

x

min

16

8

14
)
,
,
(

3

2

1

3

2

1

*

→

+

+

=

y

y

y

y
y
y
f

2

4

2

3

2

1

≥

+

+

y

y

y

3

          

2

2

2

1

≥

+

y

y

0

,

2

1

≥
x
x

0

y,
,

3

2

1

≥

y
y

2

4

2

3

2

1

=

+

+

y

y

y

3

        

2

2

2

1

=

+

y

y

S

p

ra

w

d

ź

m

y

 t

e

ra

z,

 k

tó

re

 z

 w

a

ru

n

k

ó

w

 o

g

ra

n

ic

za

ją

cy

ch

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 s

ą

sp

e

łn

io

n

e

 j

a

k

o

 

n

ie

ró

w

n

o

ś

c

i 

o

s

tr

e

. 

U

o

g

ó

ln

ie

n

ie

 p

rz

e

d

s

ta

w

io

n

y

c

h

 w

a

ru

n

k

ó

w

1

.

Je

Ŝ

e

li 

d

o

w

o

ln

a

 z

m

ie

n

n

a

w

 r

o

zw

ią

za

n

iu

 o

p

ty

m

a

ln

y

m

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 

lu

b

 d

u

a

ln

e

g

o

 j

e

st

 

d

o

d

a

tn

ia

d

o

d

a

tn

ia

, 

to

 o

d

p

o

w

ia

d

a

ją

cy

 j

e

j 

k

o

m

p

le

m

e

n

ta

rn

y

 

w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

sp

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

r

r

ó

ó

w

n

a

n

ie

w

n

a

n

ie

2

.

Je

Ŝ

e

li 

d

o

w

o

ln

y

 w

a

ru

n

e

k

 o

g

ra

n

ic

za

ją

cy

d

la

 r

o

zw

ią

za

n

ia

 o

p

ty

m

a

ln

e

g

o

 

za

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 l

u

b

 d

u

a

ln

e

g

o

 s

p

e

łn

io

n

y

 j

e

st

 j

a

k

o

 

o

st

ra

 n

ie

r

o

st

ra

 n

ie

r

ó

ó

w

n

o

w

n

o

ść

ść

, 

to

 

o

d

p

o

w

ia

d

a

ją

ca

 t

e

m

u

 w

a

ru

n

k

o

w

i 

zm

ie

n

n

a

 k

o

m

p

le

m

e

n

ta

rn

a

p

rz

y

jm

u

je

 

w

a

rt

o

ść

ze

ro

ze

ro

.

P

rz

y

k

ła

d

 p

ro

g

ra

m

o

w

a

n

ia

 l

in

io

w

e

g

o

 –

z

a

g

a

d

n

ie

n

ia

 d

u

a

ln

e

max

3

2
)
,
(

2

1

2

1

→

+

=

x

x

x
x
f

14

2

2

2

1

≤

+

x

x

8

2

2

1

≤

+

x

x

16

4

1

≤
x

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 p

ry

m

a

rn

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

za

g

a

d

n

ie

n

ie

 d

u

a

ln

e

2

      ,

4

2

1

=

=

x

x

min

16

8

14
)
,
,
(

3

2

1

3

2

1

*

→

+

+

=

y

y

y

y
y
y
f

2

4

2

3

2

1

≥

+

+

y

y

y

3

          

2

2

2

1

≥

+

y

y

0

,

2

1

≥
x
x

0

y,
,

3

2

1

≥

y
y

2

4

2

3

2

1

=

+

+

y

y

y

3

        

2

2

2

1

=

+

y

y

S

p

ra

w

d

ź

m

y

 t

e

ra

z,

 k

tó

re

 z

 w

a

ru

n

k

ó

w

 o

g

ra

n

ic

za

ją

cy

ch

 z

a

d

a

n

ia

 p

ry

m

a

rn

e

g

o

 s

ą

sp

e

łn

io

n

e

 j

a

k

o

 

n

ie

ró

w

n

o

ś

c

i 

o

s

tr

e

. 

P

o

d

st

a

w

ia

ją

c 

  

  

  

  

  

  

  

  

  

  

  

  

 o

tr

zy

m

a

m

y

:

2

 ,

4

2

1

=

=

x

x

14

2
2

4
2
    
14

2

2

2

1

<

⋅
+

⋅

≤

+

x

x

8

2
2

4
     8

2

2

1

=

⋅
+

≤

+

x

x

16

4
4
     
16

4

1

=

⋅

≤
x

n

ie

ró

w

n

o

ść

o

st

ra