Masalah Minimasi Metode Simpleks

Masalah Minimasi Metode Simpleks

Masalah Minimasi

Pada topik sebelumnya tentang : Pemecahan Program Linear Metode Simpleks, contoh soal yang dibahas adalah masalah maksimasi. Bagaimana jika masalahnya adalah masalah minimasi?

Metode minimasi biasanya digunakan untuk mencari biaya minimum dalam suatu produksi perusahaan, sehingga didapatkan biaya terendah untuk memproduksi suatu produk atau jasa.

Untuk metode pemecahannya, kita dapat mengubah fungsi tujuan minimasi menjadi fungsi maksimasi dengan mengalikan fungsi tujuan minimasi tersebut dengan -1, karena maksimasi merupakan minimasi negatif.

Contoh, minimumkan Z = 3 X1 + 4X2, maka persamaan fungsi tujuan tersebut sama dengan : maksimumkan (-Z) = -3 X1 – 4 X2 dengan seluruh pembatas yang tidak berubah.

Cara lain dapat juga memodifikasi langkah ke 3 simpleks pada contoh diatas, yaitu memilih pada baris Z yang bernilai positif terbesar sebagai entering variabel atau kolom pivot. Jika pada baris sudah tidak ada lagi yang bernilai positif maka solusi sudah optimal.

Iklan

Persoalan Program Linear Dengan Pembatas Bertanda “≥” dan atau “=”

Dalam pembicaraan mengenai metode simpleks, variabel slack digunakan sebagai solusi basis awal, sehingga ruas kanan persamaan berharga positif. Berikut ini dibahas cara mengatasi penyimpangan-penyimpangan dari bentuk normal diatas agar bisa diselesaikan dengan metode simpleks. Penyimpangan tersebut dapat berupa tanda sama dengan (=), kendala bertanda lebih besar sama dengan (≥), atau ruas kanan bernilai negatif.

Contoh : 
Minimumkan : Z = 7 X1 + 3 X2
Kendala : 4 X1 + 6 X2 ≤ 36
7 X1 + 5 X2 = 35
8 X1 + 4 X2 ≥ 32
X1, X2 ≥ 0

Pada fungsi kendala yang pertama, untuk mengubah menjadi persamaan harus ditambah variabel slack, yang sekaligus digunakan sebagai basis pada tabel awal simpleks. Persamaan tersebut menjadi :
4 X1 + 6 X2 + S1 = 36.

Pada fungsi kendala yang kedua sudah dalam bentuk persamaan, karena belum ada variabel yang merupakan basis pada tabel awal, maka perlu ada variabel dummy (variabel buatan) yang disebut variabel artificial (lambang “R”). Dinamakan artificial karena tidak mempunyai arti nyata, artinya iterasi-iterasi metode simpleks akan secara otomatis menjadikan variabel artificial tidak muncul lagi (bernilai nol) yaitu apabila persoalan semula yang telah terselesaikan. Dengan kata lain variabel artificial ini digunakan hanya untuk memulai solusi dan harus menghilangkannya pada akhir solusi. Jika tidak demikian, maka solusi yang diperoleh akan tidak layak. Untuk itu persamaan pembatas kedua diatas akan menjadi :
7 X1 + 5 X2 + R1 = 35.

Sedangkan fungsi pembatas ketiga yang bertanda “≥”, maka harus diubah menjadi tanda “≤” dan akhirnya menjadi tanda “=” agar dapat diselesaikan dengan metode simpleks. Persamaan tersebut dikalikan (-1) akan menjadi : -8 X1 – 4 X2 ≤ -32. Kemudian, ubah ke tanda sama dengan seperti yang telah dibahas diatas maka menjadi : -8 X1 – 4 X2 + S2 = -32. Karena bagian kanan persamaan ini bertanda negatif (-32), maka harus menjadi 8 X1 + 4 X2 – S2 = 32, tetapi karena S1 bertanda negatif, hal ini tidak memungkinkan dalam metode simpleks karena tidak dapat digunakan sebagai basis pada tabel awal. Untuk itu harus ditambahkan variabel artificial R, sehingga persamaan pembatas ketiga tersebut menjadi :
8 X1 + 4 X2 – S2 + R2 = 32.

Iklan

Dari pembahasan mengenai variabel slack dan variabel artificial berkaitan dengan metode simpleks dapat disimpulkan bahwa :

  1. Apabila fungsi kendala bertanda ≤, maka tambahkan variabel slack.
  2. Apabila fungsi kendala bertanda =, maka tambahkan variabel artificial R.
  3. Apabila fungsi kendala bertanda ≥, maka kurangi dengan variabel slack dan tambahkan variabel artificial R.
  4. Apabila fungsi kendala adalah negatif, maka harus diubah menjadi positif dengan mengalikan (-1) dan sesuaikan dengan ketiga kesimpulan diatas.

Formulasi yang sudah mengalami modifikasi ini disebut formulasi dalam bentuk standar metode simpleks. Sehingga soal diatas bentuk standarnya adalah :

Minimumkan : Z = 7 X1 + 3 X2
Kendala :
4 X1 + 6 X2 + S1 = 36
7 X1 + 5 X2 + R1 = 35
8 X1 + 4 X2 – S2 + R2 = 32
X1, X2, S1, S2, R1, R2 ≥ 0

Penyelesaian persoalan yang mengandung variabel artificial ini dapat dilakukan dengan 2 cara yaitu : metode teknik the big M dan teknik dua fase.

1. Teknik The Big M (Metode Penalty)

Pada teknik ini, setiap variabel artificial dalam fungsi tujuan diberikan penalty M, dimana M merupakan bilangan positif yang sangat besar. Penalty bertanda negatif (-) apabila fungsi tujuan maksimasi dan bertanda positif (+) apabila fungsi tujuan minimasi.

Persamaan menurut contoh diatas menjadi :

Minimumkan : Z = 7 X1 + 3 X2 + 0 S1 + 0 S2 + MR1 + MR2
Kendala :
4 X1 + 6 X2 + S1 = 36
7 X1 + 5 X2 + R1 = 35
8 X1 + 4 X2 – S2 + R2 = 32
X1, X2, S1, S2, R1, R2 ≥ 0

Untuk memasukkan model matematis persoalan diatas dalam tabel simpleks, maka terlebih dahulu melakukan subtitusi nilai R1 dan R2 pada persamaan kendala dan pada persamaan fungsi tujuan Z diatas yaitu :

R1 = 35 – 7 X1 – 5 X2
R2 = 32 – 8 X1 – 4 X2 + S2

Kemudian R1 dan R2 tersebut dimasukkan ke dalam persamaan Z menjadi :

Z = 7 X1 + 3 X2 + MR1 + MR2
Z = 7 X1 + 3 X2 + M(35 – 7 X1 – 5 X2) + M(32 – 8 X1 – 4 X2 + S2)
Z = (7 – 7M – 8M) X1 + (3 – 5M – 4M) X2 + M S2 + (35M + 32M)
Z = (7 – 15M) X1 + (3 – 9M) X2 + M S2 + 67M
Z + (15M – 7) X1 + (9M -3) X2 – M S2 = 67 M

Berdasarkan persamaan terakhir ini maka dilakukan penyelesaian dengan metode simpleks seperti cara penyelesaian yang sudah diuraikan pada bagian sebelumnya tentang : pemecahan program linear metode simpleks.

Iterasi awal hingga iterasi akhir optimal penyelesaian persoalan diatas dapat dilihat pada tabel berikut :

IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
0Z1 (15M – 7)(9M -3)00-M067M
S10 46100036
R10 75010035
R20 8400-1132
IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
1Z1 0(3M + 1)/200(7M – 7)/8-(15M – 7)/87M + 28
S10 04101/2-1/220
R10 0 3/2017/8-7/87
X10 11/200-1/81/84
IterasiBasis Z X1 X2 S1 R1 S2 R2 Solusi
2Z1 000-M – 1/3-7/6-M + 7/677/3
S10 001-8/3-11/611/64/3
X20 0 102/37/12-7/1214/3
X10 100-1/3-5/125/125/3

Dari iterasi ke-2 pada tabel diatas merupakan tabel optimal sehingga diketahui nilai optimal untuk X1 = 5/3, X2 = 14/3, X3 = 0, S1 = 4/3, dan Z = 77/3.

2. Teknik Dua Fase

Sesuai dengan namanya teknik dua fase terdiri dari 2 fase pengerjaan, yaitu :

Fase Pertama

Pada fase ini tujuan semula diganti dengan meminimumkan jumlah variabel artificialnya, dan diuji apakah persoalan yang dihadapi memiliki solusi feasibel atau tidak. Jika nilai minimum fungsi tujuan baru (r) ini berharga nol (seluruh variabel artificial berharga nol), berarti persoalan memiliki solusi feasibel, yang berarti pengerjaan bisa dilanjutkan ke fase 2. Tetapi jika minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki solusi feasible. Berarti stop!.

Fase Kedua

Gunakan solusi basis optimum pada fase 1 sebagai solusi awal bagi persoalan sebenarnya. Dalam hal ini ubahlah bentuk fungsi tujuan pada fase 1 dengan mengembalikannya pada fungsi tujuan persoalan sebenarnya dan fungsi batasan diperoleh dari tabel optimal fase 1 tanpa memasukkan variabel R nya.

Contoh:

Minimumkan : Z = 7 X1 + 3 X2
Kendala :
4 X1 + 6 X2 ≤ 36
7 X1 + 5 X2 = 35
8 X1 + 4 X2 ≥ 32
X1, X2 ≥ 0

Bentuk diatas diubah menjadi :

Minimumkan : Z = 7 X1 + 3 X2 + 0 S1 + 0 S2 + MR1 + MR2
Kendala :
4 X1 + 6 X2 + S1 = 36
7 X1 + 5 X2 + R1 = 35
8 X1 + 4 X2 – S2 + R2 = 32
X1, X2, S1, S2, R1, R2 ≥ 0

Subtitusikan :
R1 = 35 – 7 X1 – 5 X2
R2 = 32 – 8 X1 – 4 X2 + S2

Fase 1:

Minimumkan : 
r = R1 + R2
r = (35 – 7 X1 – 5 X2) + (32 – 8 X1 – 4 X2 + S2)
r = 67 – 15 X1 – 9 X2 + S2
r + 15 X1 + 9 X2 – S2 = 67

Dengan kendala yang sama:
4 X1 + 6 X2 + S1 = 36
7 X1 + 5 X2 + R1 = 35
8 X1 + 4 X2 – S2 + R2 = 32
X1, X2, S1, S2, R1, R2 ≥ 0

Setelah itu lakukan persamaan simpleks dengan r sebagai fungsi tujuan baru menggantikan Z. Masukkanlah persamaan fungsi tujuan baru r tersebut dengan fungsi tujuan minimasi serta persamaan kendalanya dimasukkan dalam tabel simpleks sebagai berikut:

IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
0r1 15900-1067
S10 46100036
R10 75010035
R20 8400-1132
IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
1r1 03/2007/8-15/87
S10 04101/2-1/220
R10 0 3/2017/8-7/87
X10 11/200-1/81/84
IterasiBasis r X1 X2 S1 R1 S2 R2 Solusi
2r1 000-1-7/6-10
S10 001-8/3-11/611/64/3
X20 0 102/37/12-7/1214/3
X10 100-1/3-5/125/125/3

Pada iterasi ke-2 terlihat baris r sudah negatif semua dan r bernilai nol, maka persoalan diatas memiliki solusi feasibel. Selanjutnya dilanjutkan ke fase 2, tetapi R tidak diikutsertakan lagi.

Fase 2:

Berdasarkan tabel optimal fase 1 diatas, dapat dituliskan persamaan :

S1 – 11/6 S2 = 4/3
X2 + 7/12 S2 = 14/3 ⇒ X2 = 14/3 – 7/12 S2
X1 – 5/12 S2 = 5/3 ⇒ X1 = 5/3 + 5/12 S2

Berdasarkan model persoalan sebenarnya, dengan mensubtitusikan persamaan X1 dan X2 diatas diperoleh Z :

Minimumkan :
Z = 7 X1 + 3 X2
Z = 7(5/3 + 5/12 S2) + 3(14/3 – 7/12 S2
Z = 77/3 + 7/6 S2
Z – 7/6 S2 = 77/3

Dengan kendala :
S1 – 11/6 S2 = 4/3
X2 + 7/12 S2 = 14/3
X1 – 5/12 S2 = 5/3
X1, X2, S1, S2 ≥ 0

Tabel Simpleks fase 2 dengan fungsi tujuan minimasi sebagai berikut :

Basis Z X1 X2 S1S2 Solusi
Z10 00-7/677/3
S10 001-11/64/3
X20 0 107/1214/3
X10 100-5/125/3

Pada tabel diatas, baris Z tidak ada yang positif. Karena fungsi tujuan minimasi berarti telah tercapai kondisi optimal dengan nilai X1 = 5/3, X2 = 14/3, S1 = 4/3. Z = 77/3.

Alternatif pemecahan masalah minimasi simpleks ini juga dapat diselesaikan dengan menggunakan software komputer seperti TORA yang dapat memecahkan program linear. Selain untuk program linear TORA juga bisa dimanfaatkan untuk menyelesaikan jenis persamaan lainya seperti transportasi dan yang lainya.

Perlu anda ketahui sebelum mengakhiri materi simpleks ini, ada beberapa kasus khusus dalam penggunaan simpleks seperti degenerasi, solusi optimum banyak, solusi tak terbatas, dan tidak ada solusi layak. Untuk lebih jelasnya akan dibahas pada topik berikutnya tentang : Kasus Khusus Penggunaan Metode Simpleks

Pemecahan Program Linear Metode Simpleks

Program Linear Metode Simpleks

Metode simpleks adalah salah satu teknik pemecahan program linear selain metode grafik, Bedanya dengan metode grafik, metode simpleks dapat dimanfaatkan untuk persamaan yang memiliki variabel lebih dari 2 sedangkan grafik tidak.

Sama seperti metode grafik, diperlukan juga formulasi program linear agar dapat dipecahkan dengan metode grafiknya. Untuk lebih jelas tentang metode grafik dan program linear dapat dilihat pada :

Sebelum masuk ke cara pemecahan program linear dengan metode simpleks, perlu anda ketahui sebelumnya tentang bentuk standar model program linear.

Iklan

Bentuk Standar Program Linear

Seperti yang sudah diuraikan pada artikel sebelumnya pada program  linear, bahwa model program linear dapat memiliki pembatas-pembatas yang bertanda ≤, ≥, dan =. Demikian juga variabel-variabelnya yang dapat berupa variabel non-negatif, dapat pula berupa variabel-variabel yang tidak terbatas dalam tanda.   Dalam penyelesaian program linear dengan metode simpleks, bentuk dasar yang digunakan haruslah bentuk standar. Formulasi bentuk standar memiliki sifat-sifat sebagai berikut:

  1. Fungsi tujuannya dapat berupa maksimasi atau minimasi.
  2. Seluruh pembatas sudah dalam bentuk persamaan (tanda = ) dengan ruas kanan persamaan yang non-negatif.
  3. Seluruh variabelnya harus merupakan variabel non-negatif.

Untuk mengubah suatu bentuk formulasi yang belum standar ke dalam bentuk standar dapat dilakukan dengan cara berikut:

1. Pembatas

  • Pembatas yang bertanda ≤ atau ≥ dapat dijadikan suatu persamaan (tanda = ) dengan menambahkan suatu variabel slack (S) atau mengurangkan dengan suatu variabel surplus (S).

Contoh 1: X1 + X2 ≤ 8

Kita tambahkan slack S1 pada ruas kiri persamaan tersebut sehingga diperoleh persamaan: X1 + X2 + S1 = 8

Variabel slack menunjukkan banyaknya sumber daya yang tidak terpakai.

Contoh 2: X1 + 2 X2 ≥ 5

Karena bertanda ≥ maka harus dikurangi dengan variabel S2 pada ruas kiri persamaan sehingga diperoleh persamaan: X1 + 2X2 – S2 = 5

Variabel surplus menunjukkan kelebihan pemakaian sumber daya.

  • Ruas kanan dari suatu persamaan dapat dijadikan bilangan non-negatif dengan mengalikan kedua ruas dengan -1.

Contoh : X1 – 5 X2 = -7, secara matematis adalah sama dengan persamaan -X1 + 5 X2 = 7.

  • Arah ketidaksamaan dapat berubah apabila kedua ruas dikalikan -1.

Contoh :  X1 – X2 ≤ -8, adalah sama dengan -X1 + X2 ≥ 8.

2. Variabel

Suatu variabel Xi yang tidak terbatas oleh tanda dapat dinyatakan sebagai dua variabel non-negatif dengan menggunakan substitusi: Xi = Xi’ – Xi” dimana Xi’ dan Xi” ≥ 0. Substitusi seperti ini harus dilakukan pada seluruh pembatas dan fungsi tujuannya.

3. Fungsi Tujuan

Maksimasi dari sebuah fungsi adalah sama dengan minimasi dari negatif fungsi yang sama.

Contoh : Maksimumkan Z = X1 + 2 X2 secara matematis sama dengan : Minimumkan (-Z) = -X1 – 2 X2.

Iklan

Metode Simpleks

Pada topik sebelumnya tentang metode grafik, sudah dijelaskan pemecahan program linear yang digunakan untuk menyelesaikan masalah 2 variabel. Untuk menyelesaikan masalah program linear berdimensi lebih besar dari 2 dikenal metode yang lazim disebut metode simpleks.

Metode simpleks dikembangkan pertama kali oleh George dantzing pada tahun 1947, sifat dari metode ini adalah iterative, dimana penyelesaian masalah melalui tahapan perhitungan yang berulang-ulang sampai tercapai solusi optimum.

Untuk lebih jelasnya dapat dilihat dari contoh soal dibawah:

Contoh Metode Simpleks

Maksimumkan : Z = 15 X1 + 18 X2 + 12 X3
Kendala :
10 X1 + 12 X2 + 8 X3 ≤ 120
18 X1 + 15 X2 + 6 X3 ≤ 135
12 X1 + 16 X2 + 6 X3 ≤ 150
X1, X2, X3 ≥ 0

Langkah 1: Mengubah Fungsi Tujuan dan Fungsi Kendala

Fungsi tujuan diubah menjadi bentuk implisit dengan jalan menggeser fungsi tujuan ke Z, yaitu Z = 15 X1 + 18 X2 + 12X3 diubah menjadi Z – 15 X1 – 18 X2 – 12X3 = 0.

Sedangkan fungsi kendala (selain kendala non-negatif) diubah menjadi bentuk persamaan dengan menambahkan variabel slack, yaitu suatu variabel yang mewakili tingkat pengangguran kapasitas yang merupakan batasan.

Fungsi kendala pada soal tersebut diatas berubah menjadi :

10 X­­1 + 12 X­­­­­­­2 + 8 X3 + S1 =120
18 X­­1 + 15 X­­­­­­­2 + 6 X3 + S2 =135
12 X­­1 + 16 X­­­­­­­2 + 6 X3 + S3 =150
X1, X2, X3, S1, S2, S3 ≥ 0

Langkah 2: Mentabulasikan Persamaan-Persamaan Fungsi Tujuan dan Kendala yang Telah Diubah Seperti Pada Langkah 1 diatas

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z1 -15 -18 -12 0 0 0 0
S10 10 12 8 1 0 0 120
S20 18 15 6 0 1 0 135
S30 12 16 6 0 0 1 150

Kolom basis menunjukkan variabel yang sedang menjadi basis yaitu S1, S2, S3 yang nilainya ditunjukkan oleh kolom solusi. Secara tidak langsung ini menunjukkan bahwa variabel non-basis X1, X2, X3 (yang tidak masuk pada kolom basis) sama dengan nol.

Hal ini bisa dimengerti, karena belum ada kegiatan/produksi X1, X2, X3 masing-masing nilainya nol yang berarti juga kapasitas masih menganggur yang ditunjukkan oleh nilai S1, S2, S3.

Langkah 3: Menentukan Kolom Pivot

Setelah kita mentabulasikan persamaan menjadi bentuk tabel simpleks, langkah selanjutnya adalah memilih kolom pivot. Kolom pivot (entering variabel) dipilih dari baris Z dengan angka negatif terbesar untuk masalah maksimasi. Jadi sesuai soal diatas didapatkan bahwa kolom pivotnya adalah X2.

Sehingga jika digambarkan dalam tabel menjadi:

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z1 -15 -18 -12 0 0 0 0
S10 10 12 8 1 0 0 120
S20 18 15 6 0 1 0 135
S30 12 16 6 0 0 1 150

Pada tabel diatas kolom X2 adalah kolom yang dipilih karena memiliki nilai -18 (nilai negatif terbesar).

Langkah 4: Menentukan Baris Pivot

Setelah kita mendapatkan kolom pivot, langkah selanjutnya adalah menentukan baris pivot (leaving variabel). Untuk mengetahui baris mana yang pilih dapat dilakukan dengan membagi solusi dengan kolom pivot pada setiap baris.

Setelah itu dipilihlah angka dengan rasio terkecil, namun jika terdapat angka negatif dan tidak hingga kolom pivot maka tidak masuk dalam perhitungan rasio, jadi jika terdapat angka negatif atau tak hingga maka diberi tanda strip pada kolom rasio. Setelah mendapat rasio maka kita harus memindahkan variabel pada kolom pivot ke baris pivot.

Sehingga berdasarkan soal diatas menjadi :

Basis Z X1 X2 X3 S1 S2 S3 SolusiRasio
Z1 -15 -18 -12 0 0 0 0
S10 10 12 8 1 0 0 12010
X20 18 15 6 0 1 0 1359
S30 12 16 6 0 0 1 1509.375

Langkah 5: Menentukan Persamaan Pivot Baru

Rumus untuk menentukan persamaan pivot baru adalah = baris pivot lama/elemen pivot. Elemen pivot adalah perpotongan antara kolom dan baris pivot. Jadi setiap baris pivot yang telah ditentukan dibagi dengan elemen pivot sehingga dihasilkan persamaan pivot baru.

Sehingga dari berdasarkan soal diatas menjadi :

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z1
S10
X20 18/15 1 6/15 0 1/15 0 9
S30

Berdasarkan tabel diatas semua baris pivot dibagi dengan elemen pivot yaitu 15. Sehingga dihasilkan persamaan pivot yang baru.

Langkah 6: Menentukan Persamaan Baru Selain Persamaan Pivot Baru

Setelah mendapat persamaan pivot baru, langkah selanjutnya adalah mengisi persamaan lainya yang masih kosong. Rumus untuk menentukan persamaan baru selain persamaan pivot baru adalah sebagai berikut :

Persamaan baru = (persamaan lama) – (persamaan pivot baru x koefisien kolom pivot)

Jadi persamaan baru yang dicari dari persoalan diatas adalah persamaan baru untuk basis Z, S1, dan S3. Sedangkan S2 sudah diganti oleh persamaan pivot baru X2.

Persamaan Z baru :
(-15) – (18/15 x -18) = 33/5
(-18) – (1 x -18) = 0
(-12) – (6/15 x -18) = -24/5
(0) – (0 x -18) = 0
(0) – (1/15 x -18) = 6/5
(0) – (0 x -18) = 0
(0) – (9 x -18) = 162

Persamaan S1 baru :
(10) – (18/15 x 12) = -22/5
(12) – (1 x 12) = 0
(8) – (6/15 x 12) = 16/5
(1) – (0 x 12) = 1
(0) – (1/15 x 12) = -4/5
(0) – (0 x 12) = 0
(120) – (9 x 12) = 12  

Persamaan S3 baru :
(12) – (18/15 x 16) = -36/5
(16) – (1 x 16) = 0
(6) – (6/15 x 16) = -2/5
(0) – (0 x 16) = 0
(0) – (1/15 x 16) = -16/5
(1) – (0 x 16) = 1
(150) – (9 x 16) = 6

Persamaan pivot baru, Z baru, S1 baru, dan persamaan S3 baru yang sudah dicari nilainya kemudian ditabulasikan dalam tabel simpleks baru sebagai berikut :

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z1 33/50-24/506/50162
S10 -22/5016/51-4/5012
X20 18/15 1 6/15 0 1/15 0 9
S30 -36/50-2/50-16/516

Langkah 7: Lanjutkan Perbaikan-Perbaikan

Periksa kembali tabel simpleks anda, apakah pada baris Z angkanya sudah positif semua (≥ 0) untuk kasus maksimasi, jika sudah positif semua berarti solusi optimal sudah didapatkan.

Terlihat pada langkah 6 diatas baris Z masih ada yang negatif yaitu kolom X3. Maka perlu dilakukan perbaikan untuk mencapai nilai optimal.

Maka dari itu diperlukan perbaikan. Dalam perbaikan anda hanya perlu mengulangi kembali dari langkah 3 dari tabel yang sudah anda hitung. Lakukan secara terus menerus hingga baris Z bernilai positif semua.

Setelah dilakukan perbaikan, maka tabel optimal dari contoh diatas akan didapatkan sebagai berikut :

Basis Z X1 X2 X3 S1 S2 S3 Solusi
Z1 0003/200180
S10 -11/8015/16-1/4015/4
X20 7/410-1/81/6015/2
S30 -31/4001/8-7/6115/2

Berdasarkan tabel hasil perbaikan diatas dapat disimpulkan bahwa hasil iterasi ini telah mencapai kondisi optimal, karena nilai pada baris fungsi tujuan Z sudah tidak ada yang negatif.

Sehingga dari persoalan diatas untuk kasus maksimasi ini didapatkan nilai:

Z = 180,
X1 = 0 (tidak diproduksi),
X2 = 15/2,
X3 =15/4,
S3 = 15/2 (merupakan kapasitas yang menganggur dari batasan ke 3).

Pada soal berikut, sudah diketahui persamaan-persamaan yang ada. Tetapi, perlu anda ketahui, bentuk soal program linear ada juga yang berbentuk soal cerita, sehingga anda perlu melakukan formulasi terlebih dahulu untuk mendapatkan bentuk persamaan seperti di atas. Untuk lebih jelas tentang formulasi program linear dapat dilihat pada : Formulasi dan Bentuk Umum Program Linear

Untuk masalah minimasi dibahas pada topik berikutnya di : Masalah minimasi metode simpleks

Iklan

Menghitung Simpleks Dengan Mudah

Bagi anda yang malas untuk menggunakan metode simpleks, sekarang ini sudah ada software yang dapat anda gunakan untuk menyelesaikan persamaan simpleks dengan mudah.

Jadi kita hanya perlu menentukan fungsi tujuan dan kendala, setelah itu masukkan fungsi-fungsi tersebut ke program untuk diproses, maka secara otomatis anda dapat mengetahui langkah-langkah penyelesaian dan hasil dari solusi optimalnya.

Nama salah satu dari software yang cukup terkenal untuk menyelesaikan masalah simpleks adalah TORA. Selain untuk masalah simpleks, TORA juga bisa digunakan untuk menyelesaikan program program lainya yang berkaitan dengan riset operasi seperti transportasi, dan lain sebagainya.

Bahkan sekarang anda juga sudah bisa memecahkan masalah simpleks langsung di web dengan mudahnya. Ada 2 website yang biasa saya gunakan untuk memecahkan masalah simpleks ini yaitu :

Pemecahan Program Linear Metode Grafik

Program Linear Metode Grafik

Metode grafik merupakan salah satu teknik pemecahan program linear baik dalam masalah maksimasi maupun minimasi untuk persamaan linear 2 variabel.

Metode grafik ini merupakan metode yang dianggap paling simpel karena perhitungannya yang cenderung mudah dibandingkan metode program linear lainya. Untuk lebih jelasnya tentang program linear dapat dilihat pada: Program Linear

Iklan

Metode Grafik

Metode grafik dapat digunakan untuk pemecahan masalah program linear yang yang hanya memiliki 2 variabel.

Sesuai dengan namanya, pemecahan program linear ini dilakukan dengan membuat grafik dari persamaan program linear yang telah diformulasikan, sehingga akan didapatkan titik-titik dari perpotongan garis-garis dalam grafik tersebut untuk mengetahui outputnya.

Hanya saja, jika dalam suatu program linear terdapat lebih dari 2 variabel, misalnya X1, X2, dan X3. Maka metode grafik ini tidak dapat dipakai.

Oleh karena itu, diperlukan metode satu lagi yaitu metode simpleks yang efektif digunakan untuk menyelesaikan program linear yang memiliki 3 variabel atau lebih. Untuk lebih jelasnya tentang metode simpleks dapat dilihat pada : Pemecahan Program Linear Metode Simpleks


Langkah-Langkah Pemecahan Dengan Metode Grafik

Langkah-langkah penyelesaian dengan metode grafik adalah sebagai berikut :

  1. Gambarkan garis-garis kendala pada sumbu koordinat. Anggap kendalanya sebagai suatu persamaan.
  2. Tentukan daerah dalam bidang koordinat yang memenuhi semua kendala (daerah feasible), kemudian tentukan semua titik daerah feasible tersebut.
  3. Hitung nilai fungsi tujuan untuk semua titik sudut daerah layak. Untuk keputusannya, pilih koordinat titik yang memberikan nilai terbesar untuk fungsi tujuan maksimasi, dan nilai fungsi terkecil untuk tujuan minimasi.
Iklan

Contoh Program Linear Metode Grafik

PT. Dounkeys memproduksi 2 macam produk yang dikerjakan secara manual. Setiap unit produk I memerlukan waktu 20 menit pada proses 2 dan 24 menit pada proses 3, sedangkan setiap unit produk II memerlukan waktu 15 menit pada proses 1, 16 menit proses 2, dan 30 menit proses 3. Produk I memberikan keuntungan sebesar Rp.170/unit dan Rp.190/unit untuk produk II. Jam kerja per hari yang tersedia untuk proses 1, 2, dan proses 3 masing-masing 1050 menit, 1600 menit, dan 2400 menit. Berapakah jumlah produk I dan II harus diproduksi agar keuntungan maksimal?

Penyelesaian:

Persoalan tersebut dapat ditabulasikan sebagai berikut:

ProsesProduk IProduk IIKapasitas (Menit)
1151050
220161600
324302400
Keuntungan170190

Langkah 1: Formulasikan

Untuk lebih jelas tentang cara mengformulasikan program linear dapat dibaca di : Formulasi Program Linear

Hasil dari formulasi didapatkan persamaan sebagai berikut:

Maksimumkan : Z = 170 X1 + 190 X2
Dengan kendala :
15 X2 ≤ 1050 20
X1 + 16 X2 ≤ 1600
24 X1 + 30 X2 ≤ 2400
X1, X2 ≥ 0

Langkah 2: Buatlah Grafiknya

Untuk menggambarkan grafiknya, cara paling mudah adalah dengan menemukan nilai suatu variabel saat variabel lain bernilai nol.

Maksudnya, kita membuat 2 titik pada sumbu X (dimana nilai Y = 0) dan di sumbu Y (dimana nilai X = 0) kemudian menghubungkan 2 titik tersebut dengan garis. Sehingga didapatkan persamaan garis lurus suatu kendala. Jika terdapat 3 kendala, maka otomatis akan terdapat 3 garis juga.

Jadi persamaan yang didapat adalah :

15 X2 = 1050
X2 = 70

20 X1 + 16 X2 = 1600
X1 = 0 ⇾ X2 = 100 → F(0,100)
X2 = 0 ⇾ X1 = 80 → D(80,0)

24 X1 + 30 X2 = 2400
X1 = 0 ⇾ X2 = 80 → E(0,80)
X2 = 0 ⇾ X1 = 100 → H(100,0)

Jadi jika dinyatakan dalam grafik adalah sebagai berikut:

Setelah didapatkan garis-garisnya, untuk mengetahui daerah mana yang diarsir dari suatu persamaan dapat dilihat dari tanda persamaan, seperti :

  • Tanda ≤ berarti bagian sebelah kiri dari persamaan garis yang diarsir.
  • Tanda ≥ berarti bagian sebelah kanan dari persamaan garis yang diarsir.
  • Tanda = berarti hanya pada bagian persamaan garis (hanya garis)

Daerah yang memenuhi persyaratan adalah daerah yang terarsir oleh semua kendala yang ada.

Berdasarkan persamaan-persamaan kendala diatas, daerah yang bersamaan memenuhi ketiga kendala ditunjukkan oleh area gambar di atas yang di arsir yaitu O-ABCD. Bagian yang diarsir dinamakan daerah feasible. Bagian O-ABCD dinamakan daerah feasible karena memenuhi solusi dari semua pembatas yang ada.

Langkah 3: Tentukan Outputnya

Untuk mencari titik yang paling menguntungkan dari daerah feasible tersebut adalah titik yang terjauh dari sumbu O untuk masalah maksimasi. Sedangkan untuk kasus minimasi adalah yang paling dekat dengan titik sumbu O.

Pada gambar diatas sebagian titik koordinat dapat diketahui yaitu titik O(0;0), titik D(80;0), titik A(0;70). Sedangkan titik B dan titik C dapat dicari dengan mencari perpotongan antara 2 garis yang saling menyinggung dengan cara subtitusi maupun eliminasi.

Jadi koordinat dari titik B dapat didapat dengan mengsubtitusikan kendala (15 X2 = 1050) dengan kendala (20 X1 + 16 X2 = 1600) maka didapatkanlah koordinatnya adalah (12,5 ; 70).

Sedangkan untuk titik C dapat didapatkan dengan cara yang sama antara kendala (20 X1 + 16 X2 = 1600) dengan kendala (24 X1 + 30 X2 = 2400) maka didapatkanlah koordinatnya (400/9 ; 400/9).

Setelah itu lakukan pengujian dari semua koordinat di daerah feasible yang didapat ke persamaan tujuan seperti contoh di atas adalah (Z = 170 X1 + 190 X2) dan carilah hasil terbesar untuk masalah maksimasi dan hasil terkecil untuk masalah minimasi.

Karena dalam contoh diatas adalah kasus maksimasi, maka kita cari nilai Z terbesar sebagai outputnya. Sehingga didapatkan :

Titik A :
Z = 170 (0) + 190 (70) = 13.300

Titik D :
Z = 170 (80) + 190 (0) = 13.600

Titik B :
Z = 170 (12,5) + 190 (70) = 15.425

Titik C :
Z = 170 (400/9) + 190 (400/9) = 16.000

Dari hasil pengujian daerah feasible, maka yang memberikan nilai optimum adalah titik C. Jadi maksudnya jumlah produk 1 (X1) yang harus dibuat adalah 400/9 dan jumlah produk 2 (X2) yang harus dibuat adalah 400/9 agar produksi maksimal dengan nilai output sebesar 16.000

Program Linear: Metode Grafik dan Simpleks

Program Linear Metode Grafik dan Simpleks

Program linear merupakan teknik matematik untuk mendapatkan alternatif penggunaan terbaik atas sumber-sumber organisasi perusahaan. Kata sifat linear digunakan untuk menggambarkan hubungan antara dua atau lebih variabel, hubungan yang langsung dan persis proporsional.

Linear berarti bahwa semua fungsi matematis yang disajikan dalam model ini haruslah fungsi linear atau secara praktis dapat dikatakan bahwa persamaan tersebut bila digambarkan pada grafik akan membentuk garis lurus.

Dalam hubungan linear antara jumlah kerja dan output sebagai contoh, 10% perubahan jumlah jam produksi dalam beberapa operasi akan mengakibatkan 10% perubahan output. Sedangkan kata program menyatakan perencanaan dengan menggunakan teknik matematik tertentu untuk mendapatkan kemungkinan pemecahan terbaik atas persoalan yang melibatkan sumber yang serba terbatas.

Jadi program linear mencakup perencanaan aktivitas-aktivitas untuk memperoleh suatu hasil yang optimum berdasarkan model matematis diantara alternatif yang mungkin dengan menggunakan fungsi linear.

Iklan

Program linear sendiri memiliki 2 teknik pemecahan, yaitu dengan metode grafik dan simpleks :

Metode Grafik

Metode grafik dapat digunakan untuk pemecahan masalah program linear berdimensi 2 x n atau m x 2. Maksudnya adalah metode grafik hanya dapat digunakan untuk pemecahan persamaan yang memiliki dua variabel. Jika suatu persamaan memiliki 3 variabel atau lebih, maka metode grafik sudah tidak berlaku.

Misalnya :
2 X1 + 3 X2  ≤ 200.
Berdasarkan persamaan diatas metode grafik masih dapat digunakan.

2 X1 + 3 X2 + 4 X3  ≤ 200.
Sedangkan untuk persamaan tersebut, metode grafik sudah tidak dapat digunakan lagi, sehingga diperlukan metode lainya seperti metode simpleks.

Untuk lebih jelasnya tentang metode grafik dapat dilihat pada : Program Linear Metode Grafik

Metode Simpleks

Metode simpleks dikembangkan pertama kali oleh Goerge dantzing pada tahun 1947. Sifat dari metode ini adalah iterative, dimana penyelesaian masalah melalui tahapan perhitungan yang berulang-ulang sampai solusi optimum.

Metode simpleks ini dapat digunakan untuk pemecahan masalah berdimensi 2 x n atau m x 2 seperti metode grafis. Selain itu, metode simpleks dapat menyelesaikan masalah yang memiliki 3 variabel atau lebih.

Jadi, metode simpleks ini dapat digunakan untuk menyelesaikan semua masalah program linear. Hanya saja, karena metode ini cukup rumit, sangat disarankan jika dalam soal yang hanya memiliki 2 variabel, metode yang terbaik untuk digunakan adalah metode grafik. Sedangkan metode simpleks hanya digunakan untuk menyelesaikan persoalan yang memiliki 3 variabel atau lebih.

Untuk lebih jelasnya tentang metode simpleks dapat dilihat pada : Program Linear Metode Simpleks

Hanya saja, sebelum memecahkan soal baik dengan metode grafik atau metode simpleks, diperlukan formulasi dari program linear itu sendiri. Formulasi diperlukan sebagai langkah awal dalam perhitungan. Untuk lebih jelasnya tentang formulasi program linear, dapat dibaca di : Formulasi dan Bentuk Umum Program Linear

Iklan

Syarat Utama Persoalan Program Linear

Sebelum ke pemecahan persoalan linear, perlu diketahui syarat-syarat utama persoalan linear yaitu :

  1. Perusahaan harus mempunyai tujuan untuk dicapai. Tujuan perusahaan itu bisa memaksimumkan laba (pendapatan) atau meminimumkan resiko (biaya,waktu).
  2. Harus ada alternatif tindakan yang salah satu dasarnya akan mencapai tujuan. Sebagai contoh, apakah perusahaan harus mengalokasikan kapasitas industrinya untuk membuat produk A dan B dalam perbandingan misal 50:50?, 25:50?, 70:30?, dan sebagainya.
  3. Sumber harus merupakan persediaan terbatas. Misal perusahaan mempunyai jumlah jam mesin terbatas, sehingga jika harus membuat produk A dan B, maka semakin banyak waktu yang digunakan untuk membuat produk A, akan semakin sedikit B yang dapat dibuat.
  4. Harus dapat menyatakan tujuan dan segenap keterbatasannya sebagai kesamaan atau ketidaksamaan matematik.

Asumsi-Asumsi Dasar Program Linear

1. Asumsi Kesebandingan (Proporsional)

Kontribusi setiap variabel keputusan terhadap fungsi tujuan adalah sebanding dengan nilai variabel keputusan.

Contoh : kita memproduksi 10 unit produk jenis I dari contoh diatas, maka kontribusinya terhadap fungsi tujuan adalah 10 kali kontribusi setiap unit jenis I yaitu 10 x 2000 = Rp.20.000.

2. Asumsi Additivity (Penambahan)

Asumsi ini menyatakan bahwa nilai fungsi tujuan setiap kegiatan tidak saling mempengaruhi atau dalam program linear dianggap bahwa kenaikan nilai fungsi tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi nilai Z yang diperoleh dari kegiatan lain atau dapat dikatakan bahwa tidak ada korelasi antara satu kegiatan dengan kegiatan lain.

Misal : Z = 8 X1 + 10 X2, untuk X1 = 6 dan X2 = 8 maka Z = 128. Jika X1 bertambah atau berkurang, maka pertambahan atau pengurangan X1 dapat langsung ditambahkan atau dikurangi pada nilai Z, tanpa mempengaruhi bagian Z yang diperoleh dari X2.

3. Divisibility (Pembagian)

Asumsi ini menyatakan bahwa output yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan.

4. Asumsi Deterministik (Kepastian)

Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model program linear dapat diperkirakan dengan pasti. Dalam kenyataannya parameter model jarang bersifat deterministik, karena keadaan masa depan jarang diketahui dengan pasti. Untuk mengetahui ketidakpastian parameter maka dikembangkan teknik analisis sensitivitas, guna menguji nilai solusi bagaimana kepekaanya terhadap perubahan-perubahan parameter.

Iklan

Pengartian Dalam Program Linear

1. Feasible Solution

Suatu solusi yang memenuhi seluruh pembatas yang ada pada persoalan tersebut. Pada contoh diatas feasible solutionnya adalah O-ABCD.

2. Infeasible Solution

Suatu solusi dimana tidak ada titik-titik secara serentak memenuhi semua kendala dalam masalah tersebut.

3. Optimal Solution

Feasible solution yang memberikan nilai terbaik bagi fungsi tujuannya. Terbaik diartikan nilai terbesar untuk tujuan maksimasi dan nilai terkecil untuk tujuan minimasi. Pada contoh diatas titik C merupakan optimal solution.

4. Multiple Optimal Solution

Ini terjadi jika fungsi tujuan terletak pada lebih dari satu titik optimal. Multiple optimal solution akan memberikan keluwesan dalam memilih solusi bagi pengambil keputusan.

5. Boundary Equation

Ini terjadi apabila ada kendala dengan tanda “sama dengan”, dan terjadi daerah feasible yang terletak pada garis tersebut.

6. No Optimal Solution

Terjadi jika suatu masalah tidak mempunyai penyelesaian optimal, disebabkan oleh tidak ada feasible solution dan juga disebabkan oleh adanya batasan yang tidak membatasi besar nilai Z.