Integer Programming

Model Programa Linier :

Integer programming (pemrograman integer) adalah sebuah model optimasi matematis atau program kelayakan di mana beberapa atau semua variabel dibatasi untuk bilangan bulat. Dalam banyak rangkaian istilah ini mengacu pada pemrograman linear integer, yang juga dikenal sebagai integer programming campuran.

            Maks. z = c₁x₁ + c₂x₂ + ……………. + c_nx_n

            d. k.           a₁₁x₁ + a₁₂x₂ + …………….a_1nx_n < b₁

                                         .

                                         .

                              a_m1x₁ + a_m2x₂ + …………….a_mnx_n < b_m

                                                            x₁; x₂; ………….x_n > 0

Semua variabel keputusan dari model di atas akan mempunyai nilai riel yang non negatif, seperti bilangan pecahan, bilangan desimal. Kadang-kadang variabel keputusan harus mengambil nilai bilangan bulat. Misalnya jumlah pekerja, mesin dls. Jika kita membulatkan nilai optimal yang diperoleh, penyelesaiannya belum tentu memberikan hasil yang optimal.

Contoh 1 :

Sebuah perusahaan akan membeli beberapa buah mesin dari dua macam mesin yang berbeda. Harga mesin pertama adalah $ 1.000.000 dan mesin kedua $ 4.000.000 per unit. Keuntungan mesin pertama adalah $ 30.000 dan mesin kedua adalah $ 130.000 per unit per bulan. Dana yang tersedia untuk membeli mesin adalah $ 11.000.000. Berapa buah mesin yang akan dibeli setiap jenisnya. Tujuan perusahaan tersebut  adalah memaksimalkan keuntungan setiap bulan.

Model Programa Liniernya adalah :

Maks. Z = 30X1 + 130X2

d. k.               X1 + 4X2     < 11

                        X1; X2 > 0 dan integer

Penyelesaian :

Jika kendala integer diabaikan, diperoleh hasil sebagai berikut :

            X1 = 0

            X2 = 2,75

            Z   = 357,5

Oleh karena variabel keputusan harus merupakan bilangan bulat, kita tetapkan X1 = 0 dan X2 = 2 (X2 = 3 adalah tidak layak), maka diperoleh Z = 260. Akan tetapi jika diteliti lebih lanjut  pada X1 = 5 dan X2 = 1 diperoleh Z = 280. Dengan demikian terlihat bahwa pembulatan hasil variabel keputusan dapat diperoleh nilai Z yang tidak optimal. Untuk itu perlu dicari cara penyelesaian yang memberikan hasil yang optimal.

JENIS-JENIS MODEL PROGRAMA INTEGER :

1.    Programa Integer Murni

2.    Programa Integer 0 – 1

3.    Programa Integer Campuran

FORMULASI PERSOALAN PROGRAMA INTEGER :

Contoh 2 (Programa Integer murni) :

PT. X membangun kapal layar fiber glass dengan ukuran panjang 30 ‘ dan 20’.  Keuntungan dari penjualan kapal tersebut adalah  $ 6.000 dan  $ 1.000 per unit. Setiap jenis kapal memerlukan waktu pembangunan masing-masing selama 1 minggu. Sumber yang terbatas adalah luas lantai dan tenaga kerja. Kapal ukuran 30’ memerlukan luas lantai dua unit dan 4 unit tenaga kerja, sedangkan kapal ukuran 20’ memerlukan  1 unit luas lantai dan 1 unit tenaga kerja. Luas lantai yang tersedia adalah 4 unit Dan tenaga kerja yang tersedia adalah 6 unit setiap minggu. Berapa unit kapal yang dibangun per minggu ? Buatlah model matematis dari persoalan di atas.

Penyelesaian :

Variabel keputusan :

            X1 = jumlah kapal ukuran 30’ yang dibangun

            X2 = jumlah kapal ukuran 20’ yang dibangun

Fungsi tujuan :

            Maks. Z = 6X1 + X2

Kendala :

                              4X1 + X2 < 6   (kebutuhan tenaga kerja)

                               2X1 + X2 < 4   (luas lantai)

                                        X1; X2 > 0 dan integer

Contoh 3 (Persoalan Programa Integer 0 – 1) :

Perusahaan X adalah sebuah perusahaan pengelola dana pensiun sedang mempertimbangkan lima buah usulan investasi tiga tahun. Perusahaan tersebut mengalokasikan dana sebesar $ 50 juta, $ 40 juta dan $ 30 juta untuk tahun I, II, dan III. Proyek tersebut harus selesai dalam tiga tahun dan menghasilkan untung. Aliran dana dari invesatasi diperlihatkan pada tabel berikut :

Proposal	Kebutuhan modal ( $ juta)			Net Present Value
investasi	Tahun I	Tahun II	Tahun III	(NPV - $ juta)
A B C D E	10 14 16 8 9	8 11 12 9 7	6 8 9 7 5	15 18 9 8 8

Buatlah model matematis dari persoalan di atas.

Penyelesaian :

                                     1 jika proposal j dipilih

Variabel : X_j =

                                     0 jika proposal j tidak dipilh

Model menjadi :

            Maks. Z = 15X1 + 18X2 +   9X3 +  8X4 + 8X5

            d. k.          10X1 + 14X2 + 16X3 +  8X4 + 9X5 < 50

                                8X1 + 11X2 + 12X3 +  9X4 + 7X5 < 40

                                6X1 +   8X2 +   9X3 +  7X4 + 5X5 < 30

                                       X_J = 0 atau 1       j = 1; 2; …….; 5

Model di atas disebut ‘knapsack model’. Nama tersebut berasal dari konsep seorang ‘hiker’ yang berharap membawa barangnya dalam ransel sebanyak mungkin. Setiap barang mempunyai berat, volume dan niali yang berbeda. Dia ingin memaksimalkan nilai barang bawaannya tanpa melanggar berat dan isi ranselnya.

Contoh 4 (Persoalan Programa Integer Campuran) :

Sebuah pabrik cat menghadapi persoalan jadual pengiriman barang dari gudang ke toko dengan jumlah persediaan di gudang, jumlah permintaan toko seperti terlihat pada tabel 1 dan 2. Untuk mengangkut cat, perusahaan menyewa truk. Tedapat dua komponen biaya pengiriman, yaitu biaya tetap (tabel 3) untuk pengiriman dari gudang ke toko yang tidak tergantung dari ukuran barang yang diangkut dan biaya variabel sebesar $ 5 untuk setiap 100 l (drum) (tanpa memper-hatian dari gudang ke toko mana cat tersebut diangkut). Buatlah model Programa Integer dari persoalan di atas.

Tabel 1			Tabel 2			Tabel 3 biaya tetap ( $ )
						Dari	Ke toko
Gudang	Tersedia		Toko	Permintaan		Gudang	1	2	3
A B C D	6000 l 7000 l 8000 l 9000 l		1 2 3	8000 l 8000 l 12000 l		A B C D	3800 2900 3650 4075	2750 3100 4020 1920	3400 2850 3840 3040

Penyelesaian :

Variabel : x_ij = jumlah cat (jumlah drum ukuran 100 l) yang diangkut

                         dari gudang I ke toko j

                 y_ij = 1 jika X_ij > 0 (terdapat cat yang diangkut)

                       = 0 jika X_ij = 0 (tidak ada cat yang diangkut)

Bentuk bersyarat di atas bukanlah bentuk yang linier à perlu dijadikan

linier

Bentuk di atas dapat diganti dengan bentuk :

            x_ij – My_ij < 0    dengan M = bilangan positif yang besar sekali

                                         1

                            y_ij =   

                                         0

Bukti :                                 x_ij  –  My_ij

Jika x_ij positif à y_ij = 1        pos. – pos. besar = negatif à memenuhi

                      à y_ij = 0         pos. – nol             = positif  à tidak memenuhi

                                 x_ij – My_ij < 0

Jika y_ij = 0 à          x_ij  - nol  < 0    à        x_ij < 0     à     x_ij = 0  terbukti!

                   Sebelumnya telah ditentukan x_ij > 0

Dengan demikian model adalah :

Fungsi tujuan :

Min. Z = (3800y₁₁ + 5x₁₁) + (2750y₁₂ + 5x₁₂) + (3400y₁₃ + 5x₁₃) + (2900y₂₁ + 5x₂₁) +

              (3100y₂₂ + 5x₂₂) + (2850y₂₃ + 5x₂₃)+ (3650y₃₁ + 5x₃₁) + (4020y₃₂ + 5x₃₂) +

              (3840y₃₃ + 5x₃₃) + (4075y₄₁ + 5x₄₁) + (1920y₄₂ + 5x₄₂) + (3040y₄₃ + 5x₄₃)

Dengan kendala :

Kendala sumber : x₁₁ + x₁₂ + x₁₃ = 60      

                                x₂₁ + x₂₂ + x₂₃ = 70       

                                x₃₁ + x₃₂ + x₃₃ = 80       

                                x₄₁ + x₄₂ + x₄₃ = 90

Kendala tujuan :      x₁₁ + x₂₁ + x₃₁ + x₄₁ = 90

                                x₁₃ + x₂₃ + x₃₃ + x₄₃ = 120

                                 x_ij – My_ij < 0       i = 1; 2; 3; 4     j = 1; 2; 3

                                 x_ij > 0                 i = 1; 2; 3; 4     j = 1; 2; 3

Pada persoalan ini M dapat ditentukan = 120 ( mengapa ?)

Model di atas bentuknya sama dengan persoalan transportasi dalam bentuk standar, kecuali kendala biaya tetap yaitu x_ij – My_ij < 0.

Bentuk ini disebut dengan persoalan biaya tetap (fixed charge problem), karena biaya tetap tersebut berkaitan dengan variabel x_ij. Variabel y_ij adalah untuk menyatakan apakah biaya tersebut dikenakan atau tidak.