Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
10
Problemprogramowanialiniowego
Zobowiązaniedostarczenia1000kgmąkiicukruoznaczaspełnieniewzoru
100x1+100x2≥1000
Zyskwłaścicielawynosi
z=8x1+10x2+25x3
x1jx2ix3musząbyćnieujemne.
Pouproszczeniachotrzymamywięcproblemprogramowaniamatematycznego:
f(x1jx2jx3)=8x1+10x2+25x3→maxj
wzbiorze
(
I
4
I
I
l
1j5x1+2x2+
x1+
x2
xj≥0dla
j=1j2j3
x1+
x2+
4x3
x3
≤
≤
≥
50
70
10
I
Problememprogramowanialiniowego(PPL)będziemynazywaćpro-
blemprogramowaniamatematycznegozdefiniowanynastępująco:
Niechcjorazaijdlaź=1j...jmjj=1j...jnbędąliczbamirzeczywistymi.
Znaleźćmaksimumfunkcjif(x1j...jxn)=Σ
n
j=1cjxjprzyograniczeniach:
{Σ
n
j=1aijxj
xj
≤
≥
bi(ź=1j...jm)
0
(j=1j..jn)
Częstowygodniebędzienampisać:
(1.1)
(
I
4
Σ
n
j=1aijxj
xj
≤bi
≥0
(ź=1j...jm)
(j=1j..jn)
(1.2)
I
l
f(x1j...jxn)=Σ
n
j=1cjxj
→max
f(x1j...jxn)=Σ
n
j=1cjxjnazywamyfunkcjącelu,zaśnierówności(1.2)ogra-
niczeniami.Zmiennex1j...jxnnazywamyzmiennymidecyzyjnymi.Za-
uważmy,żezarównofunkcjacelu,jakilewestronynierównościwewzorze(1.2)
sąfunkcjamiliniowymi.OPPL(1.2)powiemy,żejestwpostacikanonicznej.
Problemprogramowanialiniowegomożnatakżesformułowaćnastępująco:
(
4
l
zmaksymalizować
przywarunkach:
cx
Ax≤b
x≥Θn
(1.3)
gdzie:
A
c
x
=(c1j...jcn)j
=(xj)j=1,...,n∈Rnj
=(aij)i=1,...,m;j=1,...,n∈Rm×nj
b
=(bi)i=1,...,m∈Rmj
Θn=(0j...j0)T–wektorzerowyprzestrzeniRn.
