pengantar integer programming

7/25/2019 Pengantar Integer Programming

http://slidepdf.com/reader/full/pengantar-integer-programming 1/34

Pengantar Integer Programming

Dian Pratiwi Sahar

Institut Teknologi Kalimantan

1



Model integer programming Permasalahan integer programming (IP) adalah suatu Program Linear (LP) yang

beberapa atau seluruh variabel yang digunakan merupakan bilangan integer positif

Jenis-jenis permasalahan IP: Pure IP problem: jika semua variabel harus bernilai integer

Maximie ! "x# $ %x&

subje't to x# $ x& * &%

x#+ x& , + x# dan x& integer

Mixed IP problem: jika hanya beberapa variabel yang bernilai integer

Maximie ! "x# $ %x&


x#+ x& , + x# integer

0-1 IP problem: jika semua variabel harus bernilai atau #

Maximie ! "x# $ %x&


x#+ x& ! or #

2



Integer programming dan LP relaxation

Permasalahan IP biasanya lebih sulit untuk diselesaikandibandingkan dengan permasalahan LP.

LP relaxation dari IP adalah LP yang diperoleh denganmenghilangkan pembatas semua bilangan integer atau pembatas.

/ontoh Pure IP problem :Maximie ! "x# $ %x&


x#+ x& , + x# dan x& integer /ontoh Pure IP problem yang telah di-longgarkan (relax):

Maximie ! "x# $ %x&


x#+ x& ,

3



Pendekatan sederhana solusi IP

Pendekatan #:/ari seluruh kemungkinan solusi

0entukan nilai 1ungsi tujuannya

Pilih nilai maksimum (atau minimum)

Pendekatan &:

2elesaikan LP relaxation

3ulatkan pada solusi integer yang 1easibel terdekat

x x xx

x1

x2

1 2 3

1

3

2

7x1 + 4x2= 13

4



Solusi integerprogramming

Contoh Problem:

Max 1200 x 1 + 2000 x 2

ST:

2 x 1 + 6 x 2 27

x 2 2

3 x 1 + x 2 19

x 1 , x 2 0 and Integer

xx

LP Optimal

x1 = 5 7 / 16

x = 11 / 16

5



xx

IP Optimal x 1 = 4

x 2 = 3

"nt! MAX problem:

nilai o#timal dari IP $ nilai o#timal dari LP relaxation

7



Pemodelan Integer Programming

Dian Pratiwi Sahar


8



/ontoh #: Problem investasi

9

Perusahaan 2to'k'o mempertimbangkan empat jenis investasi

Modal yang tersedia untuk investasi sebesar 9 #%+

ormulasikan model integer programming ini untuk memaksimumkan ;P<

dari investasi-investasi berikut:

2=L>2I:

xi ! banyaknya modal yang diinvestasikan pada jenis ke-i

Maximie

! #6 x#$ && x $ #& x" $ x%

?endala:

x# $ 7 x& $ % x" $ " x% * #%

x#+ x&+ x"+ x% ! + #



Pengembangan Problem investasi

Perusahaan 2to'k'o mempertimbangkan batasan-batasan @logisA berikut ini:

#. 0epat " investasi yang terpilih.

&. Jika investasi ke-& terpilih+ maka investasi ke- # juga terpilih.

". Jika investasi ke- # terpilih+ maka investasi ke- " tidak terpilih.

%. 2alah satu dari investasi ke- " atau ke-% harus terpilih+ tetapi tidak dapat kedua-duanya.

0ambahan pembatas:

. 0epat " investasi yang terpilih

x#$ x&$ x"$ x% !"

&. Jika investasi ke-& terpilih+ maka investasi ke- # juga terpilih x# , x&

". Jika investasi ke- # terpilih+ maka investasi ke- " tidak terpilihx# $ x" * #

%. 2alah satu dari investasi ke- " atau ke-% harus terpilih+ tetapi tidak dapat kedua-duanya

x" $ x% ! #



/ontoh &: Pemilihan pemain bola basket

11

Perkumpulan bola basket @Pasti MenangA sedangmenghadapi kompetisi tingkat nasional. 2ang pelatih hendak

memilih dari 7 pemain yang akan diturunkan dalam

pertandingan malam nanti. Bata-data pemain seperti terlihat

pada tabel diba5ah ini:



Pemilihan pemain bola basket

Pembatas yang dialami pelatih adalah sebagai berikut:#. Carus ada tepat lima pemain+ dengan syarat:

2edikitnya empat pemain sebagai penyerang.

2edikitnya dua pemain sebagai pemain depan.

2edikitnya satu pemain sebagai pemain tengah.

&. Data-Data tingkat ketrampilan pemain paling sedikit &.

". 2alah satu dari pemain ke-& atau pemain ke-" harus

bermain.

%. Jika pemain ke-" bermain+ maka pemain ke-6 tidak bisa bermain.

. Jika pemain ke-# bermain+ maka pemain ke-% dan ke-

harus bermain juga.



2olusi : Pemilihan pemain bola basket (#)

<ariabel ?eputusan

Ei ! #+ jika pemain ke-i diturunkan ke lapangan.

! + jika pemain ke-i tidak diturunkan

ungsi tujuan:

Max 6 x# $ % x& $ x" $ % x% $ 6 x $ x6 $ x7

Pembatas :

(#a) Carus ada tepat lima pemain turun ke lapangan

x# $ x& $ x" $ x% $ x $ x6 $ x7 !

(#b) Paling sedikit terdapat empat pemain penyerang (guard).

x# $ x" $ x $ x7 ≥ %

(#') Paling sedikit terdapat dua pemain depan (1or5ard).

x" $ x% $ x $ x6 $ x7 ≥ &

(#d) Paling sedikit terdapat satu pemain tengah.

x& $ x% $ x6 ≥ #



2olusi : Pemilihan pemain bola basket (&)&. Data-Data tingkat ketrampilan pemain paling sedikit &

(a) Data-rata ketrampilan pemain menggiring bola lebih dari dua.

(" x# $ x& $ x" $ x% $ & x $ x6 $ x7)F ≥ &

" x# $ x& $ x" $ x% $ & x $ x6 $ x7 ≥ #

(b) Data-rata ketrampilan pemain menembak bola lebih dari dua.

x# $ & x& $ " x" $ & x% $ x $ " x6 $ & x7 ≥ #

(') Data-rata ketrampilan pemain menghadang lebih dari dua.

& x# $ x& $ x" $ x% $ " x $ x6 $ & x7 ≥ #

". 2alah satu dari pemain ke-& atau pemain ke-" harus bermain

x& $ x" ≥ #

<ariabel kemungkinan yang terjadi:x& ! # G x" ! easible

x& ! G x" ! # easible

x& ! # G x" ! # easible

x& ! G x" ! Infeasible



2olusi : Pemilihan pemain bola basket (")

15

%. Jika pemain ke-" bermain+ maka pemain ke-6 tidak bisa bermain

x" $ x6 ≤ #

<ariabel kemungkinan yang terjadi: Pemain " bermain+ tetapi pemain 6 tidak bermain.

x" ! #+ x6 ! easible

Pemain 6 bermain+ tetapi pemain " tidak bermain.

x" ! + x6 ! # easible

?edua-duanya bermainx" ! #+ x6 ! # Infeasible

?edua-duanya tidak dapat bermain.

x" ! + x6 ! easible



2olusi : Pemilihan pemain bola basket (%)

. Jika pemain ke-# bermain+ maka pemain ke-% dan ke-harus bermain juga

x# ≤ x%

x# ≤ x

Jika x# ! #+ maka x% ! # dan x !#.

<ariabel kemungkinan yang terjadi:



/ontoh " : Pengeboran Minyak

#. Pemilihan paling sedikit lokasi dari # lokasi pengeboran minyak yang telah diren'anakan+ dengan

variabel keputusan E#+ E&+H+ E# dan biaya

pengeboran /#+ /&+H+ dan /#.

&. 3atasan: Paling banyak dua dari lokasi E+ E6+ E7 dan E yang dapat

dipilih

Memilih lokasi E" atau lokasi E% akan men'egah untuk

memilih lokasi E.

Memilih kombinasi lokasi E# dan E7 akan men'egah untuk

memilih lokasi E.



2olusi Pengeboran Minyak (#)

%ariabel &e#!t!'an:

Ei ! #+ jika lokasi ke-i dilakukan pengeboran.

! + jika lokasi ke-i tidak dilakukan pengeboran.

(!ng'i t!)!an:

Min /# x# $ /& x& $ /" x" $ /% x% $/ x $

/6 x6 $ /7 x7 $ / x $ /8 x8 $ /# x#

&endala:

(#) Pemilihan paling sedikit lokasi dari # lokasi pengeboran

x# $ x& $ x" $ x% $ x $ x6 $ x7 $ x $ x8 $ x# !

(&a) Paling banyak dua dari lokasi E+ E6+ E7 dan E yang dapat

dipilih

x $ x6 $ x7 $ x ≤ &



2olusi Pengeboran Minyak (&)

(&b) Memilih lokasi E" atau lokasi E% akan men'egah

untuk memilih lokasi E

x" $ x ≤ #

x% $ x ≤ #

x"!# atau x%!#+ maka harus x! (jika memilih lokasi

E" atau lokasi E%+ lokasi E tidak boleh dipilih).

x!#+ maka nilai x"! dan x%! (jika memilih lokasi

E+ maka lokasi E" dan lokasi E% tidak boleh dipilih).



2olusi Pengeboran Minyak (")

20

(&') Memilih kombinasi lokasi E# dan E7 akan men'egah

untuk

memilih lokasi E

x# $ x7 $ x ≤ &

?asus #: tidak memilih lokasi E

x ! + maka x# $ x7 ≤ & (dapat memilih lokasi 2#+ 27+

atau kedua-duanya+ atau tidak keduanya).



2olusi Pengeboran Minyak (%)

21

(&') Memilih kombinasi lokasi E# dan E7 akan men'egah

untuk memilih lokasi E

x# $ x7 $ x ≤ &

?asus &: Menyelidiki lokasi 2x ! #+ maka x# $ x7 ≤ # (dapat memilih lokasi x#atau

x7+ tetapi tidak kedua-duanya)



/ontoh % : Problem @esternA

22

Penerbangan 5estern memutuskan untuk memiliki beberapa kota transit di >2.

Jalur penerbangan yang dimiliki men'akup kota-kota berikut: tlanta+ 3oston+

/hi'ago+ Benver+ Couston+ Los ngeles+ ;e5 =rleans+ ;e5 Kork+ Pittsburgh+ 2alt

Lake /ity+ 2an ran'is'o+ dan 2eattle.

estern menginginkan untuk mempunyai kota transit dalam # mil dari tiap

kota-kota ini.

Citunglah jumlah minimum dari kota transit.



Formulasi Set Covering Problems

23

Variabel keputusan:

Xi = 1 jika transit berlokasi di kota ke-i

0 jika transit tidak berlokasi di kota ke-

!un"si tujuan:

#ini#i$e X%& ' X() ' X*+ ' X, ' X+) ' X.% '

X/) ' X/ ' X ' X. ' X! ' X

endala: 0 3= /C B C= L ;= ;K PI 2L 2 2 Deuired

0 # # # # # # x0 N! #

3= # # # x3= N! #

/C # # # # # x/C N! #

B # # xB N! #

C= # # # xC= N! #L # # # xL N! #

;= # # # # x;= N! #

;K # # # # # x;K N! #

PI # # # # # xPI N! #

2L # # # # # x2L N! #

2 # # # # x2 N! #

2 # # # x2 N! #



Metode Penyelesaian IntegerProgramming

Dian Pratiwi Sahar




Pendekatan untuk menyelesaikan IP

25

1 nu#eration &aapanna: +itun" se#ua solusi an" #un"kin

&entukan #asin"-#asin"-#asin" un"situjuanna

ili solusi den"an nilai #aksi#u# atau#ini#u#

2 (ran and (ound &aapanna:

. elesaikan . rela;ation

. (ulatkan solusi an" #endekati solusieasible inte"er



Telfa Corporation

26

&ela *orporation #akes tables and airs

% table re<uires one our o labor and 9 s<uare board eet oood

% air re<uires one our o labor and 5 s<uare board eet oood

a table ontributes >8 to pro?t and ea air ontributes >5

to pro?t 6 ours o labor and 45 s<uare board eet is a@ailable

!ind a produt #i; to #a;i#i$e te pro?tA

olution:

Ba;i#i$e $ = 8X1 ' 5X2

ubjet to:X1 ' X2 C 6

9X1 ' 5X2 C 45

X1 D 0E X2 D 0 and X1E X2 inte"er



Feasibleregional forTelfa’s problem

ubproble# 1: &e

rela;ation o re"ional

)pti#al . solution:

X1 = 375F X2 = 225F

and G = 4125

ubproble# 2:

ubproble# 1 '

onstraint X1 D 4

ubproble# 3:

ubproble# 1 '

onstraint X1 C 3

27



Feasibleregional ofsubproblems

(ranin": te proess

o deo#posin" a

subproble#s

)pti#al solution o

subproble# 2:

X1 = 4F X2 = 9H8 =

18F and $ = 41

ubproble# 4:

subproble# 2 '

onstraint X2 D 2

ubproble# 5:

ubproble# 2 '

onstraint X1 C 1

28



Feasible regiona for subproblem 4 & 5

29



The branch and bound tree

30

)pti#al solution o ubproble# 5:$ = 4056F X1 = 444F X2 = 1

ubproble# 6: ubproble# 5 ' onstraint X1 D 5ubproble# 7: ubproble# 5 ' onstraint X1 C 4

ubproble# 1

G = 4125X1 = 375X2 = 225

ubproble# 4

neasible

ubproble# 5

ubproble# 2G = 41X1 = 4

X2 = 18

ubproble# 3

1

2

3 4

X1 D 4 X1 C 3

X2 D 2 X2 C 1



regional forSubproblems 6& 7

)pti#al solution o

ubproble# 7:

G = 37F X1 = 4F X2 = 1

)pti#al solution o

ubproble# 8:

G = 40F X1 = 5F X2 = 0

31



The branch and bound

32

ubproble# 1

G = 4125X1 = 375X2 = 225

ubproble# 4

neasible

ubproble# 5G = 4056X1 = 444

X2 = 1


X2 = 18


X2 = 3E .( =

39


X2 = 0E .( =37

ubproble# 7G = 37X1 = 4X2 = 1

1

2

3 4

X1 D 4 X1 C 3

X2 D 2 X2 C 1

X1 D 5 X1 C 4

5 6



Solving knapsack problems

33

Ba; $ = 16X1 ' 22 X2 ' 12 X3 ' X4

ubjet to: 5X1 ' 7X2 ' 4X3 ' 3X4 C 14

Xi = 0 or 1 or all i = 1E2E3E4

. rela;ation:

Ba; $ = 16X1 ' 22 X2 ' 12 X3 ' X4 ubjet to: 5X1 ' 7X2 ' 4X3 ' 3X4 C 14

0 C Xi C 1 or all i = 1E2E3E4

ol@in" te . rela;ation:

)rder XiIs in te dereasin" order o iHai ere i are te ostoeJients and aiIs are te oeJients in te onstrain

elet ite#s in tis order until te onstraint is satis?ed ite<ualit



The branch and bound

34

ubproble# 1

G = 44X1 = X2 = 1X3 = 5F X4 =

0

ubproble# 2G = 387

X1 = X2 = 1X3 = 0F X4 =

67

ubproble# 3G = 437

X1 = X3 = 1X2 = 7F X4 =

0

ubproble# 6G = 35

X2 = X3 = 1X1 = 0F X4 = 1

1

2

3 4

X3 = 0 X3 = 1

X1 C 4

5 6

ubproble# 5G = 436F .( =

29X2 = X3 = 1

X1 = 6F X4 =

0

ubproble# 7

neasible

ubproble# 4G = 29

X1 = X3 = 1X2 = 0F X4 = 1

ubproble# 9G = 359

X1 = X4 = 1X3 = 0F X2 =

86

ubproble# 8G = 38

X1 = X2 = 1X3 = X4 = 0

7

8 9

X2 = 0 X2 = 1

X1 = 0 X1 = 1

X4 = 0 X4 = 1

pengantar integer programming

Documents