TEORI DAN LATIHAN METODE OPTIMASI : LINEAR PROGRAMMING

Yuhka Sundaya

Artikel ini Saya tulis ketika memelajari riset operasi. 

'Cites :

Sundaya, Y. 2005. Teori dan Latihan Metode Optimasi : Linear Programming. Perpustakaan Pribadi. Cimahi.

Meskipun saat ini solusi masalah optimasi telah disupport oleh banyak perangkat, namun logika dibalik cara kerja perangkat tersebut perlu dipahami logikanya. Artikel ini semoga bisa membantu memahami logika atau cara kerja optimasi tersebut. Materi pada artikel ini disadur dari :

Taha, H. 1997. Operations Research an Introduction Sixth Edition. Prentice-Hall International. London.

1. Pendahuluan

Tiga komponen pokok situasi yang dibutuhkan oleh pengambil keputusan untuk mengidentifikasi solusi atau pemecahan masalah :

[1] Alternatif keputusan;

[2] Di bawah batasan atau restriksi apa keputusan itu dibuat; dan

[3] Kriteria objektif apa yang tepat untuk mengevaluasi alternative keputusan tersebut.

Hasil akhirnya adalah model matematis yang terkait dengan variable keputusan, kendala, dan fungsi tujuan. Solusi atas model kemudian menghasilkan nilai variable keputusan yang mengoptimisasi (maksimisasi atau minimisasi) nilai fungsi tujuan yang memenuhi seluruh kendala. Hasil daripada solusi disebut dengan solusi optimum fisibel (optimum feasible solution).

Model matematika RO berbentuk sebagai berikut :

• Maksimisasi atau minimisasi ⇢ fungsi tujuan
• Syarat ikatan⇢kendala

Menentukan model matematik adalah pekerjaan utama di dalam RO.

1.1. Teknik Riset Operasi

Dalam model matematika RO, variable keputusan dapat bersifat bilangan bulat (integer) atau kontinyu (discreate), dan fungsi tujuan serta kendala dapat berbentuk linear atau non linear. Masalah optimisasi dihadapkan pada fitur model ini yang memunculkan keragaman metode/teknik solusi yang masing-masing didesain untuk menghitung sifat matematis khusus dari model. Teknik-teknik tersebut antara lain :

[1] Linear Programming;
[2] Dynamic Programming;
[3] Integer Programming;
[4] Non Linear Programming;
[5] Goal Programming;
[6] Network Programming;

Dan masih banyak lagi teknik-teknik lainnya untuk mencari pemecahan optimum. Diantara teknik-teknik tersebut Linear Programming lebih menonjol, yang mana seluruh fungsi tujuan dan kendala bersifat linear dan seluruh variable bersifat kontinyu.

Masalah RO diselesaikan secara iterative dengan menggunakan program computer khusus.

1.2. Model Simulasi

Sebuah pendekatan alternative untuk pemodelan system yang komplek adalah simulasi. Model simuasi dapat mengamati sebuah system yang nyata.

1.3. Seni Pemodelan

Sebuah kajian RO harus didasarkan pada kerja tim, dimana masing-masing analisis RO dan rekan mengerjakan sisi demi sisi. Analisis RO membutuhkan pengalaman dan kerjasama dari rekan untuk siapa kajian ini ditujukan.

Sebagai sebuah alat pengambilan keputusan, RO harus dipandang sebagai ilmu dan seni. Sebagai ilmu melekat dengan teknik matematika yang digunakan, sedangkan sebagai seni, kesuksesan seluruh tahapannnya bergantung pada kreatifitas dan pengalaman dari tim kerja RO.

Prinsip tahapan/langkah yang diterapkan dalam praktek RO mencakup :

[1] Definisi masalah;
[2] Konstruksi/membangun model;
[3] Solusi model;
[4] Validasi model; dan
[5] Penerapan/implementasi solusi.

Tahapan [1] s.d [3] terkait dengan teori matematika, sedangkan kedua tahapan berikutnya terkait dengan seni.

Definisi masalah mencakup definisi ruang lingkup masalah yang diselidiki. Ini adalah fungsi yang harusnya dibatasi oleh tim RO. Hasil akhir dari penyelidikan adalah mengidentifiasi tiga komponen utama dari pengambil keputusan.

Konstruksi model menterjemahkan definisi masalah ke dalam hubungan matematis, sehingga tim RO dapat menentukan jenis teknik pemecahan yang tepat.

Solusi model adalah tahapan yang mudah dalam seluruh tahapan RO sebab tahapan ini dibantu oleh optimisasi aljabar dan program komputasi computer. Aspek penting dalam tahapan ini adalah analisis sensitifitas. Hal ini terkait dengan tambahan informasi tentang perilaku solusi optimum. Analisis sensitifitas dibutuhkan ketika parameter dari model tidak dapat diestimasi secara akurat.

Validitas model menguji apakah model menyajikan prediksi yang reasonable atas perilaku system yang dikaji. Apakah hasilnya dapat diterima secara intuitif. Validitas model dapat dibandingkan dengan data histories.

Akhirnya, pada tahap akhir, penerapan solusi dari model yang valid adalah menterjemahkan hasil model ke dalam perintah operatif dalam bentuk yang dapat dipahami.

2. Linear Programming Dasar

LP adalah teknik pemodelan matematika yang didesain untuk mengoptimisasi penggunaan sumberdaya yang terbatas. Asumsi yang digunakan LP adalah :

[1] Proporsionalitas, dan
[2] Aditivitas

2.1. Konstruksi Model LP

Dalam sub bab ini dikemukakan contoh kasus sederhana untuk membangun model LP. Diketahui Reddy Mikks memproduksi cat interior dan cat exterior dari dua bahan baku, M1 dan M2. Tabel 2.1 menyajikan beberapa data dari permasalahan dasarnya. 

Tabel 2.1. Alokasi dan Ketersediaan Bahan Baku Cat Exterior dan Interior

	Bahan Baku per ton dari :		Ketersediaan Maksimum per hari (ton)
	Cat Exterior	Cat Interior
M1	6	4	24
M2	1	2	6
Keuntungan per ton ($1000)	5	4

Dari survey pasar diketahui ada batasan bahwa permintaan maksimum harian “cat interior” sebesar 2 ton. Dengan tambahan informasi, bahwa permintaan harian “cat interior” tidak lebih dari “cat exterior” dengan lebih dari 1 ton.

Reddy Mikks ingin menentukan kombinasi produk optimum (terbaik) dari kedua produk tersebut yang memaksimumkan keuntungan total per hari.

Model LP mencakup 3 elemen dasar, yaitu :
Variabel keputusan;
Tujuan (objective), yang akan dioptimasi; dan
Kendala (constraints), yang perlu dipenuhi.

Untuk masalah Reddy Mikks, kita perlu menentukan jumlah produksi cat exterior dan cat interior. Dimana :
x1 = produksi harian cat exterior;
x2 = produksi harian cat interior.

Definisi itu digunakan untuk mengkonstruksi fungsi tujuan, yang diekspresikan sebagai berikut :

Maximisasi : Z = 5x1 + 4x2

Elemen terakhir dari model, terkait dengan kendala yang membatasi penggunaan dan permintaan bahan baku. Batasan bahan baku diekspresikan secara verbal sebagai berikut :

(Penggunaan bahan baku untuk masing - masing cat ) ≤ (Ketersediaan maksimum bahan baku)

Dari informasi yang telah ditabulasi sebelumnya, dapat dinyatakan bahwa :
Penggunaan bahan baku, M1 = 6x1 + 4x2 ≤ 24
Penggunaan bahan baku, M2 = x1 + 2x2 ≤ 6

Karena ketersediaan harian, M1 dan M2 dibatasi masing-masing dengan 24 ton dan 6 ton, kendala yang terkait dinyatakan sebagai berikut :

6x1 + 4x2 ≤ 24 …bahan baku M1
x1 + 2x2 ≤ 6 …bahan baku M2

Tedapat dua bentuk kendala permintaan, yaitu [1] permintaan harian maksimum cat interior (x2) dibatasi 2 ton, dan [2] kelebihan produksi harian cat interior (x2) terhadap cat exterior (x1) tidak lebih dari 1 ton. Kendala pertama dapat dinyatakan x2 ≤ 2, sedangkan kendala kedua dinyatakan x2 – x1 ≤  1.

Selain itu, terdapat kendala yang bersifat implicit atas model, yakni varibel x1 dan x2 bukan bilangan negatif (non negativity) yang dinyatakan x1, x2 ³ 0.

Berdasarkan uraian di atas, model Reddy Mikks selengkapnya adalah :

Maximisasi : Z = 5x1 + 4x2
Syarat ikatan :
6x1 + 4x2      ≤ 24
  x1 + 2x2      ≤ 6
 -x1 +   x2     £ 1
             x2     £ 2
  x1, x2          ³ 0

Banyak cara untuk menentukan besarnya x1 dan x2 dalam model Reddy Mikks. Namun terdapat dua langkah yang dipandang efisien, yaitu :

[1] Menentukan ruang solusi yang fisibel, dan
[2] Menentukan solusi optimum.

Kita dapat mengilustrasikan model Reddy Mikks dalam sebuh grafik. Untuk langkah pertama, kita gambarkan semua Kendala dalam model Reddy Mikks dalam grafik 1 berikut.

 

2.3.2 Solusi Model Minimisasi

Contoh 2.3-2 (Masalah Diet)

Pertanian Ozark menggunakan sekurang-kurangnya 800 lb makanan khusus harian. Makanan khusus tersebut adalah kombinasi dari jagung dan sayuran dengan komposisi berikut :

 

	Lb per lb of feedstuff		Cost ($/lb)
Feedstuf	Protein	Fiber
Corn	0.09	0.02	0.30
Soybean meal	0.60	0.06	0.90

Kebutuhan diet dari makanan khusus itu ditentukan sekurang-kurangnya 30% protein dan sebesar-besarnya 5% fiber. Pertaniaan Ozark ingin menentukan biaya minimum per hari dari kombinasi makanan itu.

Karena kombinasi makanan terkait dengan jagung dan sayuran, variable keputusan dari model didefinisikan sebagai berikut :

X1 = lb jagung dalam kombinasi harian

X2 = lb sayuran dalam kombinasi harian

Fungsi tujuan adalah meminimisasi biaya total harian (dalam dollar) dari kombinasi makanan yang diekspresikan sebagai berikut : 

Minimisasi : z = 0.3x1 + 0.9x2

Kendala dari model harus merefleksikan jumlah harian yang diperlukan dan kebutuhan diet. Karena petani Ozark butuh 800 lb dari makanan per hari, kendala yang terkait dapat diekspresikan sebagai berikut :

x1 + x2 ≤ 800 

Kendala kebutuhan diet protein dikembangkan kemudian. Jumlah protein yang ada dalam x1 lb jagung dan x2 lb sayuran adalah (0.09x1 + 0.6x2) lb. Jumlah ini seharusnya sama sekurang-kurangnya 30% dari total kombinasi makanan (x1 + x2) lb, yang kemudian :

0.09x₁ + 0.6x₂ ≥ 0.3(x₁ + x₂)     Û   0.09x₁ + 0.06x₂ ≥ 0.3x₁ + 0.3x₂

                                                            (0.09x₁-0.3x₁)+( 0.6x₂-0.3x₂) ≥ 0

                                                            -0.21x₁+ 0.3 x₂ ≥ 0

                                                             0.21x₁ – 0.3 x₂ ≤ 0                             

Dengan cara yang serupa, kendala fiber dibangun sebagai berikut :

0.02 x₁ + 0.06x₂ ≤ 0.05(x₁ + x₂) Û      0.02 x₁ + 0.06x₂ ≤ 0.05x₁ + 0.05x₂

                                                                (0.02x₁ – 0.05x₁)+( 0.06x₂ – 0.05x₂) ≤ 0

                                                                 -0.03 x₁ + 0.01x₂ ≤ 0

                                                                  0.03 x₁ – 0.01x₂ ≥ 0

Model diet selengkapnya adalah :

Minimisasi : z = 0.3x1 + 0.9x2
Dengan kendala :
x1 + x2 ≤ 800
0.03x1 – 0.01x2 ≥ 0
0.21x1 – 0.3x2 ≤ 0
x1, x2 ≥ 0

3. Metode Aljabar Simplex : Teknik Menentukan Nilai Optimum

Dalam model matematika yang lebih komplek, nilai optimum variable keputusan ditentukan dengan bantuan program komputasi computer. Beberapa diantaranya adalah LINDO, ABQM, dan TORA. Namun bagaimanapun diperlukan pengetahuan bagaimana cara kerja program-program komputasi tersebut. Metode simplex dengan model matematika sederhana berikut ini dapat memberikan gambaran bagaimana program komputasi itu bekerja.

Jika diketahui model matematis RO sebagai berikut :

Maksimisasi         :               Z = 5x₁ + 4x₂

Syarat ikatan        :               6x₁ + 4x₂ £ 24

                                               x₁ + 2x₂ £ 6

                                             -x₁ +   x₂ £ 1

                                                        x₂ £ 2

                                                x₁, x₂ ³ 0

Dalam bentuk standar yang mencerminkan kesamaan dinyatakan sebagai berikut :

Maksimisasi         :               Z = 5x₁ + 4x₂ + 0S₁ + 0S₂ + 0S₃ + 0S₄

Syarat ikatan        :               6x₁ + 4x₂        + S₁                                              = 24

                                                  x₁ + 2x₂                  + S₂                                    = 6

                                                 -x₁ +   x₂                           + S₃                         = 1

                                                            x₂                                     + S₄              = 2

                                                x₁, x_2,  S_1, S_2, S_3, S₄ ³ 0

Dalam bentuk table bentuk standar tersebut dinyatakan dalam table 1 berikut :

Tabel 1 Simplex

Basic	Z	x1	x2	S1	S2	S3	S4	Solution	Rasio [9]:[3]
[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]
Z	1	-5	-4	0	0	0	0	0
S1	0	6	4	1	0	0	0	24	4
S2	0	1	2	0	1	0	0	6	6
S3	0	-1	1	0	0	1	0	1	-1
S4	0	0	1	0	0	0	1	2	¥

        

Beberapa hal penting sebelum melakukan operasi aljabar simplex adalah :
[1] Menentukan entering variable untuk menetukan kolom pivot;
[2] Menentukan leaving variable untuk menentukan baris pivot;
[3] Menentukan elemen pivot untuk menentukan table simplex lebih lanjut

Variable x1 dapat dinyatakan sebagai entering variabel. Karena, dalam persamaan keuntungan (z), variable x1 memiliki kontribusi paling besar terhadap keuntungan dibandingkan variable x2. Keuntungan akan meningkat sebesar $5 dengan

kenaikan x1 per satu satuan, sedangkan kenaikan x2 sebesar satu satuan hanya akan meningkatkan keuntungan sebesar $4. Dengan demikian vector kolom x1 dinyatakan sebagai kolom pivot.

Untuk menentukan leaving variable, kita buat dulu kolom rasio dalam table sebelumnya. Rasio diperoleh dari hasil bagi antara vector kolom solusi dengan vector kolom entering variable. Kriteria yang digunakan untuk menentukan leaving variable adalah nilai rasio yang paling kecil tetapi bukan nilai negative (non negativity value). Berdasarkan criteria ini kita dapat menyatakan bahwa baris variable slack S1 sebagai baris pivot yang akan di replace oleh variable x1 dalam table simplex lebih lanjut.

Langkah pertama setelah kita mengidentifikasi baris dan kolom pivot adalah membuat table 2.1. Karena baris S1 memiliki nilai rasio positif yang paling kecil (non negativity value), maka dalam table 2 vektor baris variabel S1 di replace dengan vector baris variable x1 yang baru. Vaktor baris variable x1 yang baru dalam table 2.1 ditentukan dengan cara membagi setiap komponen vector baris pivot dengan elemen pivot. Elemen pivot dalam table 1 terletak pada koordinat antara S1 dengan x1 (entering variable), yakni 6.[1] Dengan demikian vaktor baris x1 yang baru berisi bilangan yang secara berurutan adalah [0/6, 6/6, 4/6, 1/6, 0/6, 0/6, 0/6 dan 24/6].

Tabel 2.1. Simplex 

	Basic	Z	x1	x2	S1	S2	S3	S4	Solution
Langkah 2	Z
Langkah 1	x1	0	1	4/6	1/6	0	0	0	4
Langkah 3	S2
Langkah 4	S3
Langkah 5	S4

Langkah kedua, ketiga, keempat dan kelima secara bertahap adalah mengisi elemen-elemen dalam vector baris Z, S2, S3, dan S4 yang baru dalam table 2.1 simplex yang sumbernya berasal dari table 1. Langkah-langkah ini mengikuti prosedur Gauss-Jordan dalam operasi matriks.

· Vektor baris Z = [vector baris Z table 1] – [EP(Z:X1)*vector baris X1 tabel 2]
· Vektor baris S2 = [vector baris S2 table 1] – [EP(S2:X1)*vector baris X1 tabel 2]
· Vektor baris S3 = [vector baris S2 table 1] – [EP(S3:X1)*vector baris X1 tabel 2]
· Vektor baris S4 = [vector baris S2 table 1] – [EP(S4:X1)*vector baris X1 tabel 2] 

Hasil selengkapnya dari langkah pertama sampai dengan langkah kelima ditampilkan dalam table 2.2 simplex berikut : 

Tabel 2.2. Simplex :

Basic	Z	x1	X2	S1	S2	S3	S4	Solution	Rasio
[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[9]:[4]
Z	1	0	-2/3	5/6	0	0	0	20
x1	0	1	2/3	1/6	0	0	0	4	6
S2	0	0	4/3	-1/6	1	0	0	2	3/2
S3	0	0	5/3	1/6	0	1	0	5	3
S4	0	0	1	0	0	0	1	2	2

Hasil dalam table 2.2 simplex belum optimum, karena variable keputusan x2 belum ditentukan. Selanjutnya dilakukan proses serupa untuk menetukan nilai x2 tersebut. Entering variable selanjutya berdasarkan table 2.2 tersebut adalah x2. Dalam table itu, hanya x2 yang dapat meningkatkan keuntungan (Z).

Untuk menentukan leaving variable lebih lanjut, lihat dulu rasio mana yang paling kecil namun positif. Dalam table 2.2 rasio ditentukan dengan cara membagi nilai solusi dengan vector kolom entering variable (x2), yang hasilnya dapat dilihat dalam table tersebut. Hasilnya, dapat ditentukan bahwa vector baris S2 dinyatakan sebagai leaving variable, karena nilai rasionya paling rendah.

Selanjutnya, dengan proses yang sama seperti dalam langkah pertama hingga kelima di dalam mengisi table 2.2. simplex, hasil selengkapnya ditampilkan dalam table 3. simplex berikut: 

Tabel 3. Simplex :

Basic	Z	X1	X2	S1	S2	S3	S4	Solution
Z	0	0	0	3/4	1/2	0	0	21
X1	0	1	0	1/4	-1/2	0	0	3
X2	0	0	1	-1/8	3/4	0	0	3/2
S3	0	0	0	3/8	-5/4	1	0	5/2
S4	0	0	0	1/8	-3/4	0	1	½

Keterangan :

· Vektor baris Z = [vector baris Z table 1] – [EP(Z:x2) * vector baris X2 tabel 3]
· Vektor baris x1 = [vector baris S2 table 1] – [EP(S2:x2) * vector baris X2 tabel 3]
· Vektor baris S3 = [vector baris S2 table 1] – [EP(S3:x2) * vector baris X2 tabel 3]
· Vektor baris S4 = [vector baris S2 table 1] – [EP(S4:x2) * vector baris X2 tabel 3]

Ketika dalam vector kolom Z tidak nampak lagi variable slack S1 dan S2, maka table 3 itu telah mencapai nilai optimal. Nilai optimal dari x1, x2 dan Z terdapat dalam kolom solusi table 3 simplex.

Interpretasi hasil ini adalah bahwa untuk mencapai keuntungan (Z) sebesar $21, maka X1 dan X2 yang diproduksi masing-masing harus sebesar 3 dan 1.5 satu satuan.

Analisis optimasi model linear ini lebih dari penentuan nilai tujuan yang optimum dan variabel keputusan yang optimal untuk digunakan. Dalam permasalahan Reddy Mix sebelumnya, berarti analisisnya lebih dari menentukan keuntungan optimum dan penentuan besarnya cat interior dan eksterior yang memaksimumkan keuntungan. Informasi selanjutnya yang perlu dikaji oleh perencana adalah reduced cost, shadow price serta analisis sensitivitas. Analisis sensitivitas dibahas dalam sub bab 3.1.

Dari Tabel 3, dapat dimunculkan dua informasi penting mengenai reduced cost (unit worth of resource) dan shadow price (dual price atau simplex multiplier). Reduced cost dalam table itu ditunjukan oleh nilai dalam koordinat Z dengan X1 dan Z dengan X2, dimana keduanya bernilai nol (0) yang menunjukkan bahwa biaya per unit penggunaan M1 dan M2 sama dengan penerimaan per unit penggunaan M1 dan M2.

[1] Elemen pivot ini selanjutnya didenotasikan dengan EP(Z:X1), yang artinya elemen pivot yang terletak pada koordinat atau pertemuan antara baris Z dengan kolom X1.