Metode Simplex Tabular Pemrograman Linear

Metode Simplex Dalam Bentuk Tabular Pada Pemrograman Linear

Metode SImplex

Untuk kesempatan kali ini, akan dijelaskan tentang Metode Simplex dalam bentuk modular. Karena ada juga dengan dictionaries. Disini akan dipaparkan cara menggunakan metode ini dengan dua contoh yaitu pada masalah maksimasi dan minimasi. Berikut contohnya.

Contoh metode simplex dalam masalah makasimasi

\[\begin{align*} Maksimumkan \hspace{1cm}& Z=3x_1+2x_2\\ s.t \hspace{1cm} & x_1+2x_2\leq 6\\ & 2x_1+x_2\leq 8\\ & -x_1+x_2\leq 1\\ & x_2\leq 2\\ & x_1\geq 0\\ & x_2\geq 0 \end{align*}\] Jawab
Untuk menggunakan metode simplex, terlebih dahulu kita ubah persamaan pada kendala kedalam persamaan kanonik, yaitu dengan menambahkan variable slack. modelnya menjadi. \[\begin{align*} Maksimumkan \hspace{1cm} & Z=3x_1+2x_2\\ s.t \hspace{1cm} & x_1+2x_2 + x_3 = 6\\ & 2x_1+x_2 +x_4 = 8\\ & -x_1+x_2 +x_5 = 1\\ & x_2 +x_6 = 2\\ & x_1\geq 0\\ & x_2\geq 0\\ & x_3\geq 0\\ & x_4\geq 0\\ & x_5\geq 0\\ & x_6\geq 0\\ \end{align*}\] Catatan:
  • Jika persamaan dalam kendala dalam bentuk $\geq$ maka persamaan tersebut ditambah variabel slack
    Contoh: $x_1+x_2\geq 6$ maka persamaan kanoniknya menjadi $x_1+x_2+x_3= 6$ dengan $x_3$ merupakan variabel slack
  • Jika persamaan dalam kendala dalam bentuk $\leq$ maka persamaan tersebut dikurangi variabel slack
    Contoh: $2x_1+x_2\leq 6$ maka persamaan kanoniknya menjadi $2x_1+x_2-x_3= 6$ dengan $x_3$ merupakan variabel slack
  • Jika bentuknya persamaan, maka diubah variabel yang paling belakang.
    contoh: $x_1+x_2= 6$ maka $x_2$ diubah menjadi $x_2=x_3-x_4$. Sehingga persamaan kanoniknya menjadi $x_1+x_3-x_4= 6$ dengan $x_3$ dan $x_4$ merupakan variabel slack

Selanjutnya kita masuk ke tabularnya.

Metode SImplex
Tabel 1

Tabel 1 adalah tabel persiapan untuk pengerjaan metode simplex pada masalah atau soal diatas. Isikan terlebih dahulu nilai-nilai yang sudah ada, seperti koefisi $x_1$ sampai $x_6$, kemudian konstanta dan $C_j$. Selanjutnya kolom $C_b$ semuanya bernilai nol terlebih dahulu karena belum ada entering dan leaving variable. Selanjutnnya nilai $Z$ dihitung dari perkalian $C_b$ dengan konstanta, rumusnya $Z$ seperti ini: \[Z=(C_b)(Konstanta)=(\begin{matrix}0 & 0& 0& 0\end{matrix}) \left(\begin{matrix}6\\ 8\\ 1\\ 2 \end{matrix}\right)\] Baris $\hat{C}_j$ adalah $C_j$ dikurangi dengan $C_b$ dan kolom yang berkaitan dengan $x_j$. Jadiperhitungan untuk $\hat{C}_j$ adalah
  • Untuk $\hat{C}_1$ \[\hat{C}_1=C_1-[(C_b)(x_1)]=3-[(\begin{matrix}0 & 0& 0& 0\end{matrix}) \left(\begin{matrix}1\\ 2\\ -1\\ 0 \end{matrix}\right)]=3\] 
  • Untuk $\hat{C}_2$ \[\hat{C}_2=C_2-[(C_b)(x_2)]=2-[(\begin{matrix}0 & 0& 0& 0\end{matrix}) \left(\begin{matrix}2\\ 1\\ 1\\ 1 \end{matrix}\right)]=2\]
  • dan seterusnya perhitungan sampai $\hat{C}_6$ sama seperti perhitungan $\hat{C}_1$.

Untuk menentukan Entering variabel (kolom yang berwarna kuning)
  • Untuk masalah Maksimasi. Pilih baris $\hat{C}_j$ yang berada pada variable non basis ($x_1$ dan $x_2$) yang paling besar.
  • Untuk masalah Minimasi.  Pilih baris $\hat{C}_j$ yang berada pada variable non basis ($x_1$ dan $x_2$) yang paling kecil.
Untuk menentukan Leaving variable (baris yang berwarna biru tua), Gunakan aturan rasio.
  • Untuk masalah Maksimasi. Pilih rasio positif  yang paling kecil.
  • Untuk masalah Minimasi. Pilih rasio positif  yang paling besar.
dimana rumus untuk menentukan rasio adalah \[Rasio-ke-j=konstanta-ke-j\times nilai-ke-j-pada-kolom-entering-variabel\] Misalkan kita hitung rasio untuk baris $x_3$ yaitu $\frac{6}{1}=6$ dan seterusnya. Karena rasio positif yang paling kecil berada pada baris $x_4$, maka baris tersebut menjadi leaving variabel. Lihat Tabel 2.


Metode SImplex
Tabel 2
Sehingga terlihat pada Tabel 2 bahwa variabel yang dipilih adalah $x_1$. Ganti $x_4$ pada basis dengan $x_1$, nilai $C_b$ pada baris tersebut diganti dengannilai $C_j$ yang bersesuaian dan bagi semua nilai yang ada pada baris tersebut dengan 2. Kenapa 2? Karena perpotongan antara entering variabel dan leaving variabel adalah 2 sehingga didapat nilai baru.

Metode SImplex

Selanjutnya, jadikan samadengan nol semua nilai yang berada pada kolom entering variabel (lihat kolom $x_1$ pada Tabel 2), bagaimana caranya? yaitu dengan mengeliminasi baris tersebut dengan baris huruf berwarna merah pada. Misalkan
baris $x_3$ pada Tabel 3 didapat dari baris_pertama_$x_3$_Tabel_2 dikurangi baris_kedua_$x_1$_yang_berwarna_merah.

Metode SImplex

Begitupun dengan baris-baris berikutnya.sehingga didapat
Metode SImplex
Selanjutnya menghitung nilai $Z$, Baris $\hat{C}_j$.
\[Z=(C_b)(Konstanta)=(\begin{matrix} 0 & 3& 0& 0 \end{matrix})  \left( \begin{matrix} 2\\ 4\\ 5\\ 2 \end{matrix}\right)=12\]
Baris $\hat{C}_j$
  • Untuk $\hat{C}_1$ \[\hat{C}_1=C_1-[(C_b)(x_1)]=3-[(\begin{matrix}0 & 3& 0& 0\end{matrix}) \left(\begin{matrix}0\\ 1\\ 0\\ 0 \end{matrix}\right)]=0\] 
  • Untuk $\hat{C}_2$ \[\hat{C}_2=C_2-[(C_b)(x_2)]=2-[(\begin{matrix}0 & 3& 0& 0\end{matrix}) \left(\begin{matrix}1.5\\ 0.5\\ 1.5\\ 1 \end{matrix}\right)]=0.5\]
  • dan seterusnya perhitungan sampai $\hat{C}_6$ sama seperti perhitungan $\hat{C}_1$.
Sehingga didapat 
Metode SImplex

Langkah selanjutnya adalah memilih entering variabel dan leaving variabel dengan cara yang sama dengan cara sebelumnya. Sehingga didapat (Kolol kuning adalah entering variabel, baris biru tua adalah leaving variabel)

Metode SImplex
Tabel 3
Pada Tabel 3 terlihat bahwa $x_2$ yang masuk ke basis dan $x_3$ yang keluar dari basis. Kemudian untuk menentukan nilai yang ada di tabel 4, bisa mengikuti langkah-langkah sebelumnya yang bersesuaian.
Metode SImplex
Tabel 4
Karena tidak adalagi entering variabel yang bisa dipilih, maka kita sudah mendapatkan solusi yang optimal yaitu $Z=12.67$ dengan $x_1=3.33$ dan $x_2=1.33$. Sebagi pembanding, kita cek jawaban yang didapat dengan jawaban pada aplikasi Lingo. Lihat gambar berikut:

Metode SImplex


Contoh metode simplex dalam masalah minimasi

\[\begin{align*} Minimumkan \hspace{1cm} & Z = 4x_1+x_2\\ s.t \hspace{1cm} & 3x_1+x_2\geq 3\\ & 4x_1+3x_2\geq 6\\ & x_1+2x_2\leq 4\\ &x_1\geq 0\\ &x_2\geq 0 \end{align*}\] Jawab
Untuk menggunakan metode simplex, terlebih dahulu kita ubah persamaan pada kendala kedalam persamaan kanonik, yaitu dengan menambahkan variable slack. modelnya menjadi. \[\begin{align*} Minimumkan \hspace{1cm} & Z = 4x_1+x_2\\ s.t \hspace{1cm} & 3x_1+x_2 - x_3 = 3\\ & 4x_1+3x_2 - x_4 = 6\\ & x_1+2x_2+x_5 = 4\\ &x_1\geq 0\\ &x_2\geq 0\\ &x_3\geq 0\\ &x_4\geq 0\\ &x_5\geq 0 \end{align*}\]
Kemudian kita siapkan Tabelnya karena kita akan menggunakan metode simplex dalam bentuk tabel.
Berikut tabelnya

Metode SImplex
Tabel 5
Sama seperti pada masalah Maksimasi, isikan terlebih dahulu semua nilai yang ada. Kemudian nilai $Z$, $C_b$ dan Baris $\hat{C}_j$ sama caranya dengan yang ada pada masalah makasimasi. Nilai yang didapat seperti berikut:

Metode SImplex

Langkah selanjutnya yaitu menentukan entering variabel. Karena ini masalah Minimasi, maka lihat pada Baris $\hat{C}_j$ yang nilainya yang paling kecil. Jadi yang dipilih adalah kolom $x_2$. Kemudian untuk menentukan leaving variabel, hitung terlebih dahulu rasionya. Rumus menghitung rasio, sama dengan menhitung rasio pada masalah Maksimasi.Tetapi pada masalah Minimasi, pilihlah rasio yang paling besar. Sehingga didapat seperti berikut

Metode SImplex
Tabel 6
Langkah salanjutnya sama dengan langkah yang ada pada masalah maksimasi. Sehingga didapat
Metode SImplex
Tabel 7

Metode SImplex
Tabel 8
Dari tabel8 terlihat bahwa $Z=3.4$ dengan $x_1=0.4$ dan $x_2=1.8$. Kita cek dengan aplikasi lingo jawaban yang telah kita dapat.
Metode SImplex

Cukup sekian dulu artikel ini. Semoga bermanfaat. Terimakasih telah membaca. Bagi teman-teman yang ingin membaca artikel yang berhubungan dengan kesehatan, bisa baca disini.

Berlangganan update artikel terbaru via email:

0 Response to "Metode Simplex Tabular Pemrograman Linear"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel