METODE SIMPLEX

Riset operasi atau sains manajemen merupakan aplikasi dari pendekatan multidisiplin atau ilmiah yang mengkonsentrasikan penyelesaian masalah-masalah manajerial dalam rangka membantu manajer untuk mengambil keputusan yang baik.
Pendekatan Operation Research yang digunakan untuk memecahkan masalah adalah sebagai berikut:

1.        Observasi, yaitu langkah awal yang dilakukan, dimana manajer mengenali dan mempelajari masalah-masalah yang ada dalam organisasi atau sistem

2.        Definisi Masalah, yaitu bagaimana masalah yang muncul tadi dapat dijabarkan dan dtegaskan secara singkat dan jelas. Definisi masalah harus meliputi batasan-batasan masalah dan tingkatan dimana masalah tersebut menyangkut unit organisasi lainnya.

3.        Konstruksi model, yaitu bagaimana suatu masalah yang telah teridentifikasi tadi harus dibuatkan suatu model, yang di dalam sains manajemen merupakan bentuk penyajian yang ringkas dari situasi masalah yang sedang berjalan. Penyajian dari model ini bisa berupa grafik, diagram dan biasanya mencakup suatu paket hubungan matematis.

4.        Solusi, yaitu setelah model matematik disusun maka permasalahan yang dihadapi tadi dapat diselesaikan dengan teknik-teknik yang terdapat dalam sains manajemen.

5.        Implementasi, merupakan hal yang menjadi tujuan akhir dari riset operasi, dimana teknik dari manajemen sains tadi memberikan jawaban pemecahan masalah, dan selanjutnya dapat diinformasikan kepada manajer untuk membantu pembuatan keputusan. Dalam mengambil keputusan, manajer tidak harus terpaku pada pemecahan tadi saja, tetapi bisa menggunakan pertimbangan lebih lanjut.

Program linier adalah salah satu teknik/metode matematik dalam OperationResearch dalam menyelesaikan persoalan pengalokasian sumber-sumber daya yang terbatas di antara aktivitas yang bersaing dengan cara terbaik yang mungkin dilakukan untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Pemrograman linier dapat diselesaikan dengan metode grafik dan metode simplex. Metode simplex merupakan metode yang digunakan untuk untuk mengatasi kelemahan pada metode grafik dimana pada metode simplex jumlah variabel yang digunakan bisa lebih dari 2 variabel. Metode simplex adalah prosedur algoritma yang digunakan untuk menghitung dan menyimpan banyak angka pada iterasi-iterasi yang sekarang dan untuk pengambilan keputusan pada iterasi berikutnya. Metode simplex secara eksplisit memakai manipulasi matriks maka masalah harus dinyatakan dalam notasi matriks. Maksud yang lebih jelas yaitu pada metode simplex model diubah ke dalam bentuk suatu tabel (matriks), kemudian dilakukan beberapa langkah matematis pada tabel tersebut. Langkah-langkah matematis ini pada dasarnya merupakan replikasi proses pemindahan dari suatu titik ke titik ekstrim batas solusi lainnya. Metode simplex bergerak dari satu solusi yang lebih baik sampai solusi yang terbaik didapatkan Model pemrograman linier ada 2 fungsi yaitu fungsi tujuan dan fungsi kendala (batasan). Semua kendala (batasan) dan fungsi tujuan dimasukan ke dalam tabel masukan dengan memasukkan koefisien setiap variabel, sebelum proses optimasi dilakukan. Optimasi ada 2 yaitu maksimasi dan minimasi sehingga pemakai harus terlebih dahulu memilih jenis optimasi yang diinginkan. Hasil akhir dari program ini adalah solusi optimal untuk setiap variabel batasan dan nilai optimal untuk fungsi sasaran.

Tahap paling awal yang diperhatikan dalam metode simplex ini adalah tiga tahap yang dilakukan pada linear programming yaitu

1.        Masalah harus dapat diidentifikasi sebagai sesuatu yang dapat diselesaikan dengan Linear Programming.

2.        Masalah yang tidak terstruktur harua dapat dirumuskan dalam model matematika, sehingga menjadi terstruktur.

3.        Model harus diselesaikan dengan teknik matematika yang dibuat

Tahap selanjutnya merupakan tahap teknis yang secara umum ada dalam program linier, sebagai berikut:

1.        Menentukan variabel keputusan, dimana maksud dari variabel keputusan ini merupakan simbol matematika yang menggambarkan tingkatan aktivitas perusahaan. Tahap ini sebenarnya untuk mempermudah dalam menggunakan metode matematik, dengan memutuskan memakai simbol matematik untuk hal yang ingin dihitung.

2.        Membuat fungsi tujuan, yang dimaksudkan dari fungsi tujuan ini adalah hubungan matematika linier yang menjelaskan tujuan perusahaan dalam terminologi variabel keputusan. Jadi setelah ditentukan variabel keputusan, kemudian digunakan dalam membuat fungsi (persamaan matematika) dari tujuan yang ingin dicapai perusahaan.

3.        Membuat batasan (kendala) model, dimana maksud dari fungsi batasan adalah hubungan linier dari variabel keputusan yang menunjukkan keterbatasan perusahaan dalam lingungan operasi perusahaan.

Dalam fungsi tujuan dan batasan model harus diberikan parameter, yaitu nilai numerik yang aktual dan biasanya merupakan koefisien dari variabel (simbol) dalam persamaan.

Langkah-langkah selanjutnya merupakan inti dari penyelesaian metode simplex, yaitu:

1.        Mengubah bentuk batasan model pertidakasamaan menjadi persamaan. Hal yang dilakukan bisa menggunakan variabel pengurang (slack variable), dimana ini digunakan untuk batasan kurang-dari-atau-sama-dengan (tanda “<” atau “<”) atau juga variabel penambah (surplus variable), dimana digunakan untuk batasan lebih-dari-atau-sama-dengan (tanda “>” atau “>”).

2.        Membentuk tabel awal untuk solusi fisibel dasar pada titik original dan menghitung nilai-nilai baris Zj dan Cj-Zj.

3.        Menentukan kolom pemutar (variabel non dasar yang masuk) dengan cara memilih kolom yang memiliki nilai positif tertinggi pada baris Cj-Zj.

4.        Menentukan baris pemutar (variabel dasar yang keluar) dengan cara membagi nilai pada kolom kuantitas dengan nilai-nilai pada kolom pemutar dan memilih baris dengan hasil bagi nonnegatif terkecil.

5.        Menhitung nilai baris pemutar yang baru dengan menggunkan formula:

Nilai Baris Pemutar Tabel Lama

Angka Pemutar

1.        Menghitung nilai baris lainnya dengan formula:

a.                        Menghitung baris-baris Zj dan Cj-Zj yang baru.

b.                       Menentukan apakah solusi telah optimal dengan mengecek baris Cj-Zj.

Jika semua nilai Cj-Zj nol atau negatif, maka solusi sudah optimal, Jika masih bernilai positif, dilakukan lagi mulai dari langkah ketiga dan seterusnya.

Dalam langkah pertama dari penyelesaian metode simplex, disebutkan bahwa pada batasan yang merupakan bentuk pertidaksamaan dibuat menjadi bentuk persamaan. Hal ini bisa digunakan dengan dua variabel yang sudah disebutkan sebelumnya, yaitu:

a) Variabel Pengurang (Slack Variable), merepresentasikan sumber daya yang mengganggur pada suatu fungsi kendala, variabel ini digunakan untuk ditambahkan dalam fungsi pertidaksamaan ≤, supaya dengan menambahkan variabel slack ini diperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik).

b) Variabel Penambah (Surplus Variable), merepresentasikan kekurangan sumber daya pada suatu fungsi kendala, variabel digunakan untuk dikurangkan dalam fungsi pertidaksamaan ≥, supaya dengan menambahkan variabel surplus ini diperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik).

Baik variabel slack maupun variabel surplus menggunakan simbol ‘s’. Untuk memperjelas variabel slack dan surplus dapat diberikan 2 contoh sebagai berikut:

1.        Minimumkan Z = 2 X₁ + 5.5 X₂

Kendala: X₁ + X₂ = 90

0.001X₁ + 0.002X₂ ≤ 0.9

0.09X₁ + 0.6X₂ ≥ 27

0.02X₁ + 0.06X₂ ≤ 4.5

X₁, X₂ ≥ 0

Bentuk bakunya adalah:

Minimumkan Z = 2 X₁ + 5.5 X₂ + 0S₁ + 0S₂ + 0S₃ + 0S₄

Terhadap:  X₁ + X₂ + S₁ = 90

0.001X₁ + 0.002X₂ + S₂ = 0.9

0.09X₁ + 0.6X₂ – S₃ = 27

0.02X₁ + 0.06X₂ + S₄ = 4.5

X₁, X₂, S₁, S₂, S₃, S₄ ≥ 0

2.        Maksimumkan Z = 2X1 + 3X2

Kendala:  10X1 + 5X2 ≤  600

6X1 + 20X2 ≤  600

8X1 + 15X2 ≤  600

X1, X2 ≥ 0

Bentuk Baku:

Maksimumkan Z = 2X1 + 3X2 + 0S1 + 0S2 + 0S3

Terhadap: 10X1 + 5X2 + S1 = 600

6X1 + 20X2 + S2 = 600

8X1 + 15X2 + S3 = 600

X1, X2, S1, S2, S3 ≥ 0

CONTOH SOAL: KASUS MAKSIMISASI

Suatu perusahaan yang bergerak pada bidang furniture akan memproduksi meja dan kursi dengan harga per unit masing-masing $7 dan $5. Dalam mengerjakan 1 unit meja membutuhkan 4 jam proses pemahatan dan 2 jam pengecatan dan finishing. Sedangkan untuk mengerjakan 1 unit kursi membutuhkan 3 jam proses pemahatan dan 1 jam pengecatan dan finishing. Waktu yang tersedia pada proses pemahatan adalah minimal 240 jam, dan waktu untuk pengecatan dan finishing minimal 100 jam. Berapakah profit yang bisa didapatkan pada tingkat maksimum? Dan pada jumlah berapa unitkah yang akan diproduksi untuk mencapai profit maksimum?

Tahap-tahap penyelesaian:

1.        Menentukan variabel keputusan:

= jumlah unit meja yang diproduksi

= jumlah unit kursi yang diproduksi

2.        Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL

Maksimumkan:       7+ 5

Dengan kendala : 4 + 3 £  240

2 +  £  100

,  ³ 0

3.        Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar

Kendala I: 4  + 3  £  240

4  + 3 +  = 240

Jika == 0 (titik origin pada grafik) maka   = 240

Kendala II: 2 +  £  100

2 + +  = 100

Jika == 0 (titik origin pada grafik) maka  = 100

Dengan demikian, formulasi dalam bentuk standar dari permasalahan yang dibahas:

Maksimumkan:      7 + 5 + 0+ 0

Dengan kendala :  4 + 3+  + 0 = 240

2  ++ 0 +  =100

, ,  ³ 0

Membuat Table Simpleks Awal

TABEL 1

Cj		7	5	0	0	Right Hand Side
	Basic Variable
0		4	3	1	0	240
0		2	1	0	1	100
	Zj	0	0	0	0	0
	Cj - Zj	7	5	0	0

·                     Pada dasarnya, semua angka pada formulasi diplotting dalam tabel simpleks awal.

·                     Ada dua macam variabel: Variabel Basis (Basic Variable) dan Variabel Non Basis (Non Basic Variable).

·                     C_j menotasikan profit per unit (untuk permasalahan maksimisasi) dari masing-masing variabel dalam formulasi.

·                     Baris Z_j berisikan angka gross profit (laba kotor). Untuk kolom j, Z_j ditentukan dari jumlah perkalian antara profit per unit variabel basis dan angka pada kolom j.

·                     Baris C_j - Z_j disebut baris net profit yang mengindikasikan besarnya net profit tambahan yang akan diperoleh jika variabel pada kolom menjadi variabel basis pada iterasi berikutnya.

d. Algoritma metode simpleks dengan mengaplikasikan lima langkah berikut ini:

·                     Langkah 1: menentukan variabel kolom yang akan masuk basis

Variabel kolom mana yang akan dipilih untuk menggantikan variabel basis pada iterasi berikutnya ditentukan berdasarkan nilai C_j - Z_j terbesar (untuk problem maksimisasi). Selanjutnya, kolom terpilih disebut dengan kolom pivot.

Cj		7	5	0	0	Right Hand Side
	Basic Variable
0		4	3	1	0	240
0		2	1	0	1	100
	Zj	0	0	0	0	0
	Cj - Zj	7	5	0	0

·                     Langkah 2: menentukan variabel yang akan keluar basis

variabel basis yang akan keluar basis pada iterasi berikutnya didasarkan pada nilaireplace row antara Right Hand Side dan angka pada kolom pivot pada Langkah 1.

Baris variabel basis yang memiliki nilai replace row dengan angka nonnegatif (positif) terkecil dipilih sebagai baris yang akan digantikan. Baris variabel basis ini disebutbaris pivot.

Variabel Basis					RHS	Replace Row
		4			240	240/4 = 60
		2			100	100/2 = 50
Cj	Basic Variable		7	5			0	0		Right Hand Side
	Basic Variable
0			4	3			1	0		240
0			2	1			0	1		100
	Zj		0	0			0	0		0
	Cj - Zj		7	5			0	0

Angka pada perpotongan antara kolom pivot dan baris pivot disebut dengan angka pivot.

·                     Langkah 3: menentukan angka baru untuk baris pivot

Perhitungan angka baru untuk baris pivot pada iterasi berikutnya:  membagi setiap angka pada baris pivot dengan angka pivot

Keterangan					RHS
Angka Lama (1)	2	1	0	1	100
Angka Pivot (2)	2	2	2	2	2
Angka Baru Untuk Baris Pivot (1:2)	1	½	0	½	50

·                     Langkah 4: menentukan angka baru untuk baris lainnya

Perhitungan angka baru pada baris selain baris pivot pada iterasi berikutnya:

Nilai baris tabel baru = Nilai baris tabel lama – [(angka diatas atau dibawah angka pivot) × (angka baru baris pivot)]

Nilai Baris Tabel Lama		Angka diatas angka pivot	Angka baru baris pivot		Angka baru
4	-	( 4	1)	=	0
3	-	( 4	½)	=	1
1	-	( 4	0)	=	1
0	-	( 4	½)	=	-2
240	-	( 4	50)	=	40

·                     Langkah 5: menghitung Z_j dan C_j - Z_j dan mengevaluasi apakah tabel simpleks memberikan solusi optimal

Perhitungan Z_j dan C_j - Z_j dilakukan dengan cara yang telah digunakan sebelumnya. Pada problem maksimisasi, jika semua C_j - Z_j bernilai nol atau negatif (atau C_j - Z_j ≤ 0) maka solusi optimal telah tercapai. Sebaliknya, jika masih ada kolom dengan C_j - Z_j ≥ 0 perhitungan masih harus dilanjutkan dan dimulai dari Langkah 1.

TABEL 2

Cj		7	5	0	0	Right Hand Side
	Basic Variable
0		0	1	1	-2	40
7		1	½	0	½	50
	Zj	7	7/2	0	7/2	350
	Cj - Zj	0	3/2	0	-7/2

Karena pada Tabel 2 nilai C_j - Z_j tidak semua bernilai nol atau negatif, maka dilanjutkan kembali ke Langkah 1 dan seterusnya.

·                     Langkah 1: menentukan variabel kolom yang akan masuk basis berdasarkan nilai C_j - Z_j terbesar (untuk problem maksimisasi). Selanjutnya, kolom terpilih disebut dengan kolom pivot.

Cj		7	5	0	0	Right Hand Side
	Basic Variable
0		0	1	1	-2	40
7		1	½	0	½	50
	Zj	7	7/2	0	7/2	350
	Cj - Zj	0	3/2	0	-7/2

·                     Langkah 2: menentukan variabel yang akan keluar basis

variabel basis yang akan keluar basis pada iterasi berikutnya didasarkan pada nilaireplace row antara Right Hand Side dan angka pada kolom pivot pada Langkah 1.

Baris variabel basis yang memiliki nilai replace row dengan angka nonnegatif (positif) terkecil dipilih sebagai baris yang akan digantikan. Baris variabel basis ini disebutbaris pivot.

Variabel Basis		RHS	Replace Row
	1	40	40/1 = 40
	½	50	50/(½) = 100

Cj	Basic Variable	7	5	0	0	Right Hand Side
	Basic Variable
0		0	1	1	-2	40
7		1	½	0	½	50
	Zj	7	7/2	0	7/2	350
	Cj - Zj	0	3/2	0	-7/2

Angka pada perpotongan antara kolom pivot dan baris pivot disebut dengan angka pivot.

·                     Langkah 3: menentukan angka baru untuk baris pivot

Perhitungan angka baru untuk baris pivot pada iterasi berikutnya:  membagi setiap angka pada baris pivot dengan angka pivot

Keterangan					RHS
Angka Lama (1)	0	1	1	-2	40
Angka Pivot (2)	1	1	1	1	1
Angka Baru Untuk Baris Pivot (1:2)	0	1	1	-2	40

·                     Langkah 4: menentukan angka baru untuk baris lainnya

Perhitungan angka baru pada baris selain baris pivot pada iterasi berikutnya:

Nilai baris tabel baru = Nilai baris tabel lama – [(angka diatas atau dibawah angka pivot) × (angka baru baris pivot)]

Nilai Baris Tabel Lama		Angka diatas angka pivot	Angka baru baris pivot		Angka baru
1	-	( ½	0 )	=	1
½	-	( ½	1 )	=	0
0	-	( ½	1 )	=	-½
½	-	( ½	-2 )	=	3/2
50	-	( ½	40 )	=	30

·                     Langkah 5: menghitung Z_j dan C_j - Z_j dan mengevaluasi apakah tabel simpleks memberikan solusi optimal

Perhitungan Z_j dan C_j - Z_j dilakukan dengan cara yang telah digunakan sebelumnya. Pada problem maksimisasi, jika semua C_j - Z_j bernilai nol atau negatif (atau C_j - Z_j ≤ 0) maka solusi optimal telah tercapai. Sebaliknya, jika masih ada kolom dengan C_j - Z_j ≥ 0 perhitungan masih harus dilanjutkan dan dimulai dari Langkah 1.

Karena pada tabel 3 nilai C_j - Z_j semua bernilai nol atau negatif, maka diperoleh tabel yang memberikan solusi yang optimal.

Interpretasi Tabel Optimal

Cj		7	5	0	0	Right Hand Side
	Basic Variable
0		0	1	1	-2	40
7		1	0	-1/2	3/2	30
	Zj	7	5	3/2	1/2	410
	Cj - Zj	0	0	-3/2	-1/2

Solusi Optimal

Interpretasi dari solusi optimal: fungsi tujuan akan optimal jika perusahaan memproduksi 30 unit meja dan 40 unit kursi dan besarnya total profit yang diperoleh dari aktivitas yang menghasilkan kombinasi meja-kursi tersebut adalah $410.

source: http://berbagidenganmahasiswa.blogspot.co.id/2014/08/metoda-simplex.html