Metode Grafis

 Banyak kasus empiris yang ditemui di lapangan untuk pemecahan persoalan-persoalan optimasi melibatkan lebih dari dua variabel keputusan. Untuk kasus kasus seperti ini jawaban dari persoalan dengan menggunakan metoda grafik mengalami kesulitan. Metoda grafik hanya bisa dipergunakan untuk memecahakan persoalan dengan dua variabel keputusan. Pemecahan dengan tiga variabel keputusan menggunakan ruang tiga dimensi yang pemecahannya sangat kompleks. Kasus-kasus dimana melibatkan empat atau lebih variabel keputusan penggunaan metoda grafik adalah tidak mungkin.

Metoda aljabar dapat dipergunakan untuk memecahkan perosalan-persoalan optimasi yang menggunakan lebih dari empat variabel keputusan atau lebih. Namun bagaimanapun juga, pemecahan persoalan optimasi dengan menggunakan metoda aljabat untuk kasus-kasus yang melibatkan empat variabel atau lebih membutuhkan penyelesaian yang panjang. Cara yang paling sederhana untuk pemecahan masalah-masalah optimasi yang melibatkan empat variabel keputusan atau lebih ialah dengan menggunakaan metoda simplex (simple linear example).

Metoda  simplex adalah suatu metoda pemecahan persoalan persamaan linier dalam hal mana suatu fungsi tujuan yang bersifat liner dioptimumkan (dimaksimumkan atau diminimumkan). Metoda simplex adalah suatu proses yang berulang (iterative) yang dimulai dari suatu pemecahan yang feasible ke suatu pemecahan feasible yang lebih baik sampai tidak ditemukan suatu pemecahan feasible yang lebih baik.

Untuk memberikan gambaran tentang prosedur penggunaan metoda simplex ini terlebih dahulu disajikan suatu kasus optimum dengan menggunakan pemecahan masalah metoda grafis.

Contoh 1.

Sebuah perusahaan furniture meproduksi kursi dan meja. Untuk memproduksi kursi dan meja harus melalui dua proses yakni proses perakitan dan penyelesaian akhir. Untuk menghasilkan satu unit meja diperlukan waktu  4 jam perakitan dan 3 jam penyelesaian akhir. Sementara untuk memproduksi satu unit kursi diperlukan waktu 2 jam perakitan dan 4 jam penyelesaian akhir. Perusahaan hanya mempunyai waktu yang tersedia dalam seminggu 60 jam perakitan dan 48 jam penyelesaian akhir. Dengan haarga jual satu unit meja seharga Rp.80.000 dan satu unit kursi Rp. 60.000, berapa jumlah kursi dan meja yang diproduksi untuk memaksimumkan penerimaan perusahaan?

Langkah-langkah penyelesaian dengan metoda LP

1.       Pernyataan verbal dari persoalan

Tentukan jumlah produksi dari meja dan kursi setiap minggu yang harus diproduksi untuk memaksimumkan keuntungan perusahaan

2.       Keputusan

a.       Pernyataan verbal

Jumlah unit produksi kursi dan meja yang diproduksi dalam seminggu

b.       Definisi matematis

X1 = Jumlah Meja yang dibuat dalam seminggu

X2 = Jumlah Kursi yang dibuat dalam seminggu

3.       Kriteria

a.       Pernyataan verbal

Maksimumkan keuntungan  perusahaan dari produksi meja dan kursi  dalam seminggu

b.       Pernyataan matematis

Z = 8X1 + 6X2

4.       Kedaaan Pembatas

a.       Pernyataan verbal

• Tidak lebih dari 60 jam proses perakitan dalam seminggu dapat dipergunakan
• Tidak lebih dari 48 jam proses penyelesaian akhir dalam seminggun dapat dipergunakan

     b.       Pernyataan matematis

(1)           4X1 + 2X2 ≥ 60

(2)           2X1 + 4X2 ≥ 48

5.   Model Matematis

      Model lengkap untuk Prgram linier pada kasus ini dapat ditulis kembali menjadi

     

      Maksimumkan

                        Z = 8X1 + 6X2

Dengan pembatas

4X1 + 2X2 ≥ 60                                                                         (1)

      2X1 + 4X2 ≥ 48                                                                         (2)

Jawaban-jawaban dari Kemungkinan Dasar (Basic Feasible)

Menggambarkan pemecahan yang optimal dari persoalan di atas memerlukan beberapa definisi. Jawaban yang mungkin  (Feasible Solution) adalah himpunan dari nilai-nilai n variabel yang memenuhi pembatas structural dan pembatasnonnegative. Jawaban dasar (Basic Solution)  adalah suatu jawaban yang diperoleh dengan cara membuat  n – m variabel menjadi nol dan kemudian mencari jawaban dari sistem persamaan yang tersisa dari m variabel. m variabel ini disebut dengan variabel basis (variabel dasar) yang membentuk suatu basis. Jumlah n-m variabel yang dibuat nilainya sama dengan nol dinamakan variabel nonbasic.  Di mana m adalah jumlah persamaan dan n adalah jumlah variabel.

Perlu untuk diingat bahwa untuk mencari jawaban suatu sistem persamaan yang berisikan jumlah variabel (n)  yang lebih banyak dari jumlah persamaan (m), perlu untuk dibuat seimbang antara jumlah persamaan (m) dengan jumlah variabel (n); yakni dengan cara mengurangi jumlah variabel sama dengan jumlah persmaan yakni m dan membuat jumlah variabel yang tersisa  (n–m)  sama dengan nol . Atau dengan perkataan lain, mencari jawaban dengan memilih m variabel dan n variabel dan membuat variabel yang tersisa (n-m) sama dengan nol.  Misalkan ada suatu sistem persamaan dengan 2 persamaan dan 5 variabel. Jawaban    dapat diperoleh dengan membuat nol (n-m) atau 5 – 2 = 3 nilai-nilai variabel dan menyisakan 2 variabel dan 2 persamaan.

Cara untuk memilih m variabel dari n variabel yang ada (m<n) ialah dengan menggunakan rumus kombinasi:

Langkah-langkah Pemecahan

1.  Tambahkan variabel pembantu yang sesuai untuk merubah pertidaksamaan menjadi persamaan
2.  Tentukan setiap pemecahan dasar (basic solution)  dengan cara membuat variabel-variabel nonbasic menjadi sama dengan nol dan cari jawaban dari sistem persamaan linier yang ada.
3.  Kenali himpunan dari jawaban dasar yang mungkin (basic feasible solutions) dengan cara mengabaikan semua jawaban dasar yang variabelnya mempunyai nilai yang negatif. (Secara geometris ini berarti sama dengan mengenali titik-titik ekstrim dari ruang jawabab/solution space).
4. Pilih jawaban yang optimal dari himpunan jawaban-jawaban dasar yang mungkin (basic feasible solution) dengan cara mengevaluasi fungsi tujuan (Z) dari setiap jawaban-jawaban dasar yang mungkin (Proses ini sama dengan menggambarkan fungsi tujuan kemmudian menggesernya sampai bersinggungan dengan titik ekstrim yang mempunyai nilai yang paling optimal)

Contoh 1

Model Matematis

Maksimumkan

                        Z = 8X1 + 6X2

Dengan pembatas

4X1 + 2X2 ≥ 60                                                                         (1)

                        2X1 + 4X2 ≥ 48                                                                         (2)

1.  menambahkan variabel pembantu yang sesuai untuk merubah pertidaksamaan menjadi  
     persamaan

      kaidah penambahan variabel pembantu

• untuk pertidaksamaan  ≤  pada ruas kiri pertidaksamaan ditambakan slack variabel (S)
• untuk pertidaksamaan ≥ pada ruas kiri pertidaksamaan dikurangkan surplus variabel (E) dan     tambahkan artificial variabel (A)
• untuk tanda = dari persmaan pada ruas kiri ditambakan artificial variabel (A)

Maksimumkan

      Z = 8X1 + 6X2 + 0S1 + 0S2

Dengan pembatas

4X1 + 2X2 + 1S1 + 0S2 = 60                                                      (1)

                        2X1 + 4X2 + 0S1 + 1S2 = 48                                                      (2)

2.  Menentukan setiap pemecahan dasar (basic solution)  dengan cara membuat variabel-
     variabel nonbasic menjadi sama dengan nol dan cari jawaban dari sistem persamaan  
     linier  yang ada.
    Jumlah kemungkinan dari memilih  2 variabel dari total 4 variabel (X1, X2, S1, S2) dalam   
    sistem persamaan dengan jumlah persmaan sebanyak adlah sebagai berikut :

Dengan demikian ada 6 enam jawaban dasr yakni kombinasi dari ([S1,S2],[S1,X1].[S1,X2],[S2,X1],[S2,X2],[X1,X2])

3. Mengidentifikasi himpunan dari jawaban dasar yang mungkin (basic feasible solutions) dengan cara mengabaikan semua jawaban dasar yang variabelnya mempunyai nilai yang negatif. (Secara geometris ini berarti sama dengan mengenali titik-titik ekstrim dari ruang jawabab/solution space).

Tabel 1. Hasil Perhitungan untuk semua titik kombinasi yang mungkin

No. Jawaban Dasar	Basis	Nilai untu variabel basis	Titik potong pada Gambar 1	Feasibel	Nilai dari Fungsi Tujuan
1	(S1,S2)	( 60;  48)	A	Ya	0
2	(X1;S1)	(24;  -36)	F	Tidak	-
3	(S1,X2)	( 36;  12)	B	Ya	72
4	(X1,S2)	( 15,  18)	D	Ya	120
5	(S2,X2)	(-72;  30)	E	Tidak	-
6	(X1,X2)	( 12;    6)	C	Ya	132

      Hasil perhitungan menunjukkan bahwa yang masuk dalam jawaban dasar  yang mungkin 
      adalah kombinasi dari himpunan titik-titik ([S1,S2], [S1,X2],[X1,S2],[X1,X2]).

4.   Memilih jawaban yang optimal dari himpunan jawaban-jawaban dasar yang mungkin (basic  
      feasible solution) dengan cara mengevaluasi fungsi tujuan (Z) dari setiap jawaban-jawaban  
      dasar yang mungkin (Proses ini sama dengan menggambarkan fungsi tujuan kemmudian 
      menggesernya sampai bersinggungan dengan titik ekstrim yang mempunyai nilai yang 
      paling optimal)

Jawaban yang paling optimal berdasrkan perhitungan ialah pada titik C yakni kombinasi produksi dari X1 (Meja) 12 unit dan X2 (kursi) sebanyak 6 unit dengan keuntungan maksimum dari hasil penjualan sama dengan 132.

Pemecahan persoalan dengan Metoda Simplex.

Contoh 1.

Maksimumkan

                        Z = 8X1 + 6X2

Dengan pembatas

4X1 + 2X2 ≥ 60                                                                         (1)

                        2X1 + 4X2 ≥ 48                                                                         (2)

Langkah-langkah pemecahan

1. Merubah perstidaksamaan menjadi persamaan dengan menambahkan variabel pembantu 
    yang sesuai

Maksimumkan

      Z = 8X1 + 6X2 + 0S1 + 0S2

Dengan pembatas

4X1 + 2X2 - 1S1 + 0S2 = 60                                                       (1)

                        2X1 + 4X2 + 0S1 - 1S2 = 48                                                       (2)

. Membuat table simplex