LINEAR PROGRAMMING: SIMPLEX METHOD
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:
- Observasi, yaitu langkah awal yang dilakukan, dimana manajer mengenali dan mempelajari masalah-masalah yang ada dalam organisasi atau sistem
- 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.
- 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.
- Solusi, yaitu setelah model matematik disusun maka permasalahan yang dihadapi tadi dapat diselesaikan dengan teknik-teknik yang terdapat dalam sains manajemen.
- 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
- Masalah harus dapat diidentifikasi sebagai sesuatu yang dapat diselesaikan dengan Linear Programming.
- Masalah yang tidak terstruktur harua dapat dirumuskan dalam model matematika, sehingga menjadi terstruktur.
- Model harus diselesaikan dengan teknik matematika yang dibuat
Tahap selanjutnya merupakan tahap teknis yang secara umum ada dalam program linier, sebagai berikut:
- 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.
- 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.
- 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:
- 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 “>”).
- Membentuk tabel awal untuk solusi fisibel dasar pada titik original dan menghitung nilai-nilai baris Zj dan Cj-Zj.
- Menentukan kolom pemutar (variabel non dasar yang masuk) dengan cara memilih kolom yang memiliki nilai positif tertinggi pada baris Cj-Zj.
- 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.
- Menhitung nilai baris pemutar yang baru dengan menggunkan formula:
Nilai Baris Pemutar Tabel Lama
Angka Pemutar
- Menghitung nilai baris lainnya dengan formula:
- Menghitung baris-baris Zj dan Cj-Zj yang baru.
- 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:
- Minimumkan Z = 2 X1 + 5.5 X2
Kendala: X1 + X2 = 90
0.001X1 + 0.002X2 ≤ 0.9
0.09X1 + 0.6X2 ≥ 27
0.02X1 + 0.06X2 ≤ 4.5
X1, X2 ≥ 0
Bentuk bakunya adalah:
Minimumkan Z = 2 X1 + 5.5 X2 + 0S1 + 0S2 + 0S3 + 0S4
Terhadap: X1 + X2 + S1 = 90
0.001X1 + 0.002X2 + S2 = 0.9
0.09X1 + 0.6X2 – S3 = 27
0.02X1 + 0.06X2 + S4 = 4.5
X1, X2, S1, S2, S3, S4 ≥ 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
SOAL 1:
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:
- Menentukan variabel keputusan:
= jumlah unit meja yang diproduksi
= jumlah unit kursi yang diproduksi
- Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
Maksimumkan: 7+ 5
Dengan kendala : 4 + 3 £ 240
2 + £ 100
, ³ 0
- 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
c. Membuat Table Simpleks Awal
TABLE 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).
- Cj menotasikan profit per unit (untuk permasalahan maksimisasi) dari masing-masing variabel dalam formulasi.
- Baris Zj berisikan angka gross profit (laba kotor). Untuk kolom j, Zj ditentukan dari jumlah perkalian antara profit per unit variabel basis dan angka pada kolom j.
- Baris Cj - Zj 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 Cj - Zj 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 Zj dan Cj - Zj dan mengevaluasi apakah tabel simpleks memberikan solusi optimal
Perhitungan Zj dan Cj - Zj dilakukan dengan cara yang telah digunakan sebelumnya. Pada problem maksimisasi, jika semua Cj - Zj bernilai nol atau negatif (atau Cj - Zj ≤ 0) maka solusi optimal telah tercapai. Sebaliknya, jika masih ada kolom dengan Cj - Zj ≥ 0 perhitungan masih harus dilanjutkan dan dimulai dari Langkah 1.
TABLE 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 Cj - Zj 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 Cj - Zj 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 Zj dan Cj - Zj dan mengevaluasi apakah tabel simpleks memberikan solusi optimal
Perhitungan Zj dan Cj - Zj dilakukan dengan cara yang telah digunakan sebelumnya. Pada problem maksimisasi, jika semua Cj - Zj bernilai nol atau negatif (atau Cj - Zj ≤ 0) maka solusi optimal telah tercapai. Sebaliknya, jika masih ada kolom dengan Cj - Zj ≥ 0 perhitungan masih harus dilanjutkan dan dimulai dari Langkah 1.
Karena pada tabel 3 nilai Cj - Zj 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.
CONTOH SOAL 2
Perusahaan Mebel Ais memproduksi lemari jenis A, B, dan C. Produk tersebut diproses melalui tiga departemen: pertukangan, pengecatan, dan penyelesaian. Setiap unit lemari A membutuhkan 3 jam tenaga kerja di departemen pertukangan, 2 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Setiap unit lemari B membutuhkan 4 jam tenaga kerja di departemen pertukangan, 5 jam tenaga kerja di departemen pengecatan, dan 2 jam tenaga kerja di departemen penyelesaian. Dan, setiap unit lemari C membutuhkan 3½ jam tenaga kerja di departemen pertukangan, 1 jam tenaga kerja di departemen pengecatan, dan 1 jam tenaga kerja di departemen penyelesaian. Kapasitas yang tersedia pada departemen pertukangan, departemen pengecatan, dan departemen penyelesaian adalah 400 jam, 360 jam, dan 250 jam, masing-masing. Harga jual masing-masing produk adalah Rp 10 (lemari A), Rp 15 (lemari B), dan Rp 12 (lemari C).
Penyelesaian
v Definisi variabel keputusan:
- X1 = Jumlah lemari A yang dijual (diproduksi)
- X2 = Jumlah lemari B yang dijual (diproduksi)
- X3 = Jumlah lemari C yang dijual (diproduksi)
v Fungsi Tujuan:
Maks: Zj = 10 X1 + 15 X2 + 12 X3
v Batasan:
3 X1 + 4 X2 + 3 ½ X3 > 400
2 X1 + 5 X2 + 1 X3 > 360
1 X1 + 2 X2 + 1 X3 ≥ 250
X1, X2, X3 ≥ 0
v Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar
- 3 X1 + 4 X2 + 3 ½ X3 + S1 = 400
- 2 X1 + 5 X2 + 1 X3 + S2 = 360
- 1 X1 + 2 X2 + 1 X3 + S3 = 250
- X1, X2, X3 ≥ 0
| Basic
Variable
| 10 | 15 | 12 | 0 | 0 | 0 | Right Hand Side | |
| X1 | X2 | X3 | S1 | S2 | S3 | |||
| 0 | S1 | 3 | 4 | 3 ½ | 1 | 0 | 0 | 400 |
| 0 | S2 | 2 | 5 | 1 | 0 | 1 | 0 | 360 |
| 0 | S3 | 1 | 2 | 1 | 0 | 0 | 1 | 250 |
| Zj | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| Cj -Zj | 10 | 15 | 12 | 0 | 0 | 0 | ||
Tidak ada komentar:
Posting Komentar