13
LAMPIRAN
14
Lampiran 1 Contoh penyelesaian suatu LP dengan metode branch and bound Dari LP pada Contoh 2 Misalkan diberikan integer programming berikut: Maksimumkan z = 7 x + 5 x …(1) 1 2 Terhadap : x + 2 x ≤ 13 …(2) 1 2 9 x + 5 x ≤ 41 …(3) 1 2 x , x ≥ 0 dan integer ...(4) 1 2 Penyelesaian : Daerah fisibel untuk masalah IP di atas diberikan pada gambar berikut : x2
Solusi Optimal Subproblem 1
8
x1= 1,31 x2= 5,85
6 4 2
x1 2
4
6
8
10
12
14
Gambar 1. Daerah Fisibel IP
LP tersebut anggap sebagai Subproblem 1. 1. Cari solusi LP-Relaksasi dari subproblem 1 Dengan mengeliminasi persamaan (2) dan (3) didapat x1 = 1,31, x2 = 5,85. Substitusikan hasil tersebut ke dalam persamaan (1) didapat z = 38,42. Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu: Subproblem 2 : Subproblem 1 + kendala ( x2 ≥ 6 ) Subproblem 3 : Subproblem 1 + kendala ( x2
≤5
)
Daerah fisibel untuk subproblem 2 dan subproblem 3 diberikan pada gambar berikut : x2 8 6 4 2
x1
x1
2
4
6
8
10
12
14
Gambar 2. Daerah Fisibel untuk Subproblem 2 dan Subproblem 3 2.
Cari solusi LP-Relaksasi dari subproblem 2 x =6 2 Substitusikan x2 = 6 ke persamaan x1 + 2 x2 = 13 …(5)
15
Sehingga didapatkan x1 = 1 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 37. 3.
Cari solusi LP-Relaksasi dari subproblem 3 x2 = 5 Substitusikan x2 = 5 ke persamaan (3) Sehingga didapatkan x1 = 1, 7778 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 37,4446. Karena solusi yang didapat belum memenuhi kendala integer maka harus dibuat subproblem baru, yaitu:
( ) Subproblem 5 : Subproblem 3 + kendala ( x1 ≥ 2 ) Subproblem 4 : Subproblem 3 + kendala x1 ≤ 1
Daerah fisibel untuk subproblem 4 dan subproblem 5 diberikan pada gambar berikut : x2 8 6 4 2
x1 2
Subproblem 4
4
6
8
10
12
x1
14
Subproblem 5
Gambar 4. Daerah Fisibel untuk subproblem 4 dan subproblem 5 4.
Cari solusi LP-Relaksasi dari subproblem 4 x1 = 1 Substitusikan x1 = 1 ke persamaan (5) Sehingga didapatkan x2 = 6 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z =37. Karena titik (1,31;5,85) tidak berada di daerah fisibel subproblem 4, maka subproblem 4 tidak memiliki solusi fisibel.
5.
Cari solusi LP-Relaksasi dari subproblem 5 x1 = 2 Substitusikan x1 = 2 ke persamaan 9 x + 5 x = 41 …(6) 1 2 Sehingga didapatkan x2 = 4, 6 . Substitusikan nilai x1 dan x2 yang didapat ke persamaan (1) sehingga diperoleh z = 37.
Dari subproblem-subproblem di atas terlihat bahwa subproblem 2 dan subproblem 5 yang memenuhi kendala integer. Karena nilai fungsi objektik dari kedua subproblem tersebut sama, maka solusi optimal dari LP tersebut terdapat pada titik x1 = 1 dan x2 = 6 serta x1 = 2 dan
x2 = 4, 6 dengan nilai fungsi objektif 37.
16
Lampiran 2 Program untuk menyelesaikan masalah MIP (mixed integer programming) dengan menggunakan Lingo 8.0. MODEL: SETS: PRODUKi/PROD1,PROD2/; PABRIKj/PAB1/; GROSIRm/GROS1,GROS2,GROS3/; PENGECERn/ECER1,ECER2,ECER3,ECER4,ECER5,ECER6,ECER7,ECER8/; PRODUKPABRIK(PRODUKi,PABRIKj):P; PRODUKPENGECER(PRODUKi,PENGECERn):D; PRODUKPABRIKGROSIR(PRODUKPABRIK,GROSIRm):C1,X1; PRODUKGROSIR(PRODUKi,GROSIRm):F,II,Y,C2,K; PRODUKGROSIRPENGECER(PRODUKGROSIR,PENGECERn):C3,X2; ENDSETS MIN = @SUM(PRODUKPABRIKGROSIR(I,J,M):C1(I,J,M)*X1(I,J,M))+ @SUM(PRODUKGROSIR(I,M):Y(I,M)*(F(I,M)+C2(I,M)*II(I,M)))+ @SUM(PRODUKGROSIRPENGECER(I,M,N):C3(I,M,N)*X2(I,M,N)); !KENDALA; @FOR(PRODUKPABRIK(I,J):P(I,J)>=@SUM(GROSIRm(M):X1(I,J,M))); @FOR(PRODUKGROSIR(I,M):K(I,M)>=@SUM(PENGECERn(N):X2(I,M,N))); @FOR(PRODUKGROSIR(I,M):@SUM(PABRIKj(J):X1(I,J,M))>=@SUM(PENGECERn( N):X2(I,M,N))); @FOR(PRODUKPENGECER(I,N):D(I,N)=@SUM(GROSIRm(M):X2(I,M,N))); @FOR(PRODUKGROSIRPENGECER(I,M,N):X2(I,M,N)>=0); @FOR(PRODUKPABRIKGROSIR(I,J,M):X1(I,J,M)>=0); @FOR(PRODUKGROSIR(I,M):@BIN(Y(I,M))); DATA: P = 705 811; D = 72 25 44 89 40 12 52 65 52 10 100 79 32 93 60 32; C1 = 31 18 44 74 38 98; F = 86 61 75 66 21 50; II = 155 235 330 170 396 290; C2 = 73 82 12 53 57 91; K = 246 389 422 253 494 312; C3 =50 79 63 36 99 34 58 51 23 43 82 64 39 52 94 61 91 92 77 72 11 69 98 100 89 44 19 53 70 67 85 57 63 18 87 21 71 78 88 37 49 60 40 71 25 55 10 27; ENDDATA
Global optimal solution found at iteration: Objective value:
Variable P( PROD1, PAB1) P( PROD2, PAB1) D( PROD1, ECER1) D( PROD1, ECER2) D( PROD1, ECER3) D( PROD1, ECER4) D( PROD1, ECER5)
Value 705.0000 811.0000 72.00000 25.00000 44.00000 89.00000 40.00000
9 70248.00
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
17
D( PROD1, D( PROD1, D( PROD1, D( PROD2, D( PROD2, D( PROD2, D( PROD2, D( PROD2, D( PROD2, D( PROD2, D( PROD2, C1( PROD1, PAB1, C1( PROD1, PAB1, C1( PROD1, PAB1, C1( PROD2, PAB1, C1( PROD2, PAB1, C1( PROD2, PAB1, X1( PROD1, PAB1, X1( PROD1, PAB1, X1( PROD1, PAB1, X1( PROD2, PAB1, X1( PROD2, PAB1, X1( PROD2, PAB1, F( PROD1, F( PROD1, F( PROD1, F( PROD2, F( PROD2, F( PROD2, II( PROD1, II( PROD1, II( PROD1, II( PROD2, II( PROD2, II( PROD2, Y( PROD1, Y( PROD1, Y( PROD1, Y( PROD2, Y( PROD2, Y( PROD2, C2( PROD1, C2( PROD1, C2( PROD1, C2( PROD2, C2( PROD2, C2( PROD2, K( PROD1, K( PROD1, K( PROD1, K( PROD2, K( PROD2, K( PROD2, C3( PROD1, GROS1, C3( PROD1, GROS1, C3( PROD1, GROS1, C3( PROD1, GROS1, C3( PROD1, GROS1, C3( PROD1, GROS1,
ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) GROS1) GROS2) GROS3) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6)
12.00000 52.00000 65.00000 52.00000 10.00000 100.0000 79.00000 32.00000 93.00000 60.00000 32.00000 31.00000 18.00000 44.00000 74.00000 38.00000 98.00000 197.0000 162.0000 40.00000 100.0000 298.0000 60.00000 86.00000 61.00000 75.00000 66.00000 21.00000 50.00000 24.00000 31.00000 91.00000 96.00000 25.00000 97.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 73.00000 82.00000 12.00000 53.00000 57.00000 91.00000 246.0000 389.0000 422.0000 253.0000 494.0000 312.0000 50.00000 79.00000 63.00000 36.00000 99.00000 34.00000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 1838.000 2603.000 1167.000 5154.000 1446.000 8877.000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
18
C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( C3( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2(
PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1,
GROS1, GROS1, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS3,
ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1)
58.00000 51.00000 23.00000 43.00000 82.00000 64.00000 39.00000 52.00000 94.00000 61.00000 91.00000 92.00000 77.00000 72.00000 11.00000 69.00000 98.00000 100.0000 89.00000 44.00000 19.00000 53.00000 70.00000 67.00000 85.00000 57.00000 63.00000 18.00000 87.00000 21.00000 71.00000 78.00000 88.00000 37.00000 49.00000 60.00000 40.00000 71.00000 25.00000 55.00000 10.00000 27.00000 0.000000 0.000000 44.00000 89.00000 0.000000 12.00000 52.00000 0.000000 72.00000 25.00000 0.000000 0.000000 0.000000 0.000000 0.000000 65.00000 0.000000
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 40.00000 49.00000 0.000000 0.000000 75.00000 0.000000 0.000000 3.000000 0.000000 0.000000 6.000000 15.00000 2.000000 5.000000 23.00000 0.000000 94.00000
19
X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2( X2(
PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD1, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2, PROD2,
GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS1, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS2, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3, GROS3,
ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) ECER1) ECER2) ECER3) ECER4) ECER5) ECER6) ECER7) ECER8) Row 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 100.0000 0.000000 0.000000 0.000000 0.000000 0.000000 52.00000 10.00000 0.000000 79.00000 32.00000 93.00000 0.000000 32.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 60.00000 0.000000 Slack or Surplus 70248.00 306.0000 353.0000 49.00000 227.0000 382.0000 153.0000 196.0000 252.0000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
75.00000 27.00000 49.00000 0.000000 48.00000 53.00000 65.00000 62.00000 62.00000 0.000000 68.00000 35.00000 25.00000 51.00000 56.00000 0.000000 0.000000 32.00000 0.000000 0.000000 0.000000 18.00000 0.000000 46.00000 102.0000 45.00000 110.0000 14.00000 37.00000 0.000000 50.00000 Dual Price -1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -31.00000 -18.00000 -44.00000 -74.00000 -38.00000 -98.00000 41.00000 61.00000 94.00000 67.00000 55.00000 65.00000 89.00000 79.00000 101.0000 56.00000 93.00000
20
27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85
0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 44.00000 89.00000 0.000000 12.00000 52.00000 0.000000 72.00000 25.00000 0.000000 0.000000 0.000000 0.000000 0.000000 65.00000 0.000000 0.000000 0.000000 0.000000 40.00000 0.000000 0.000000 0.000000 0.000000 0.000000 100.0000 0.000000 0.000000 0.000000 0.000000 0.000000 52.00000 10.00000 0.000000 79.00000 32.00000 93.00000 0.000000 32.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 60.00000 0.000000 197.0000 162.0000 40.00000 100.0000 298.0000 60.00000
59.00000 109.0000 116.0000 108.0000 75.00000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
