Metode Simplex Dictionaries pada Linear programming

Metode Simplex Dengan Dictionaries

Metode simplex dictionaries

Pada kesempatan kali ini aka dibahas penyelesaian masalah program linear menggunakan metode simplex denga dictionaries. Sebelumnya sudah dibahas mengenai penggunaan metode simplex dalam bentuk tabular. Bagi yang belum membacanya, disarankan untuk membacanya terlebih dahulu disini.
Pembahasan kali ini akan dibuat dalam bentuk penyelesaian soal. Supaya lebih cepat dimengerti. Sebagai pendahuluan, bahwa secara umum masalah linear programming dirumuskan sebagai berikut: \[\begin{align*} Maximize\hspace{1cm} & \Sigma_{j=1}^{n}c_jx_j\\ subject\hspace{0.2cm}to\hspace{1cm} & \Sigma_{j=1}^{n}a_{ij}x_j\leq b_i\hspace{1cm}(i=1,2,...,m)\\ & x_j\geq 0 \hspace{1cm}(j=1,2,...,n) \end{align*}\] Untuk menggunakan metode simplex dengan dictionaries, hal pertama yang harus dilakukan adalah mendefinisikan slack variabel yaitu sebagai berikut: \[\begin{align*} x_{n+i} &=b_i-\Sigma_{j=1}^{n}a_{ij}x_j\hspace{1cm}(i=1,2,...,m)\\ z &= \Sigma_{j=1}^{n}c_jx_j \end{align*}\] Selanjutnya dipilih entering variabel dan leaving variabel. Untuk lebih jelasnya, langsung saja kita aplikasikan kedalam soal.

Soal Penerapan Metode Simplex Dictionaries

  1. Tentukan solusi dari masalah program linear berikut \[\begin{align*} Maksimumkan\hspace{1cm} & 5x_1+4x_2+3x_3\\ s.t \hspace{1cm} & 2x_1+3x_2+x_3\leq 5\\ & 4x_1+x_2+2x_3\leq 11\\ & 3x_1+4x_2+2x_3\leq 8\\ & x_1,x_2,x_3\geq 0 \end{align*}\]

    Jawab

    Pertama, kita definisikan terlebih dahulu variabel slack untuk masalah ini: \[\begin{align*} x_4 &= 5-2x_1-3x_2-x_3\\ x_5 &= 11-4x_1-x_2-2x_3\\ x_6 &= 8-3x_1-4x_2-2x_3\\ z &= 5x_1+4x_2+3x_3 \end{align*}\] Tentunya permasalahannya adalah Maksimumkan $z$ dengan kendala $x_1,x_2,x_3,x_4,x_5,x_6\geq 0$.

    Iterasi pertama

    Dari persamaan berikut, \[\begin{align*} x_4 &= 5-2x_1-3x_2-x_3\\ x_5 &= 11-4x_1-x_2-2x_3\\ x_6 &= 8-3x_1-4x_2-2x_3\\ z &= 5x_1+4x_2+3x_3 \end{align*}\] pilih entering variabel, caranya yaitu cari $x_i$ (variabel non basis) di persamaan $z$ yang jika dinaikkan akan menambah nilai $z$. Maka terlihat yang akan menjadi entering variabel pertama adalah $x_1$ dan anggap variabel non basis lain sama dengan 0. Kemudian setelah entering variabel terpilih, langkah selanjutnya adalah memilih leaving variabel, Caranya yaitu pilih variabel basis (yang ada di ruas kiri) yang nonnegativitasnya memaksakan batas atas paling kecil pada kenaikkan variabel yang masuk. Jadi ($x_2$ dan $x_3$ dianggap sama dengan 0)
    • $x_4\geq 0$ maksimal nilai $x_1=\frac{5}{2}$.
    • $x_5\geq 0$ maksimal nilai $x_1=\frac{11}{4}$.
    • $x_6\geq 0$ maksimal nilai $x_1=\frac{8}{3}$.
    Terlihat bahwa batas atas $x_1$ yang paling kecil berada pada $x_4$ dengan nilai $x_1=\frac{5}{2}$. Maka $x_4$ menjadi leaving variabel.
    Yang dimaksud entering variable adalah variable non basic yang masuk ke variable basic. Sedangkan yang dimaksud leaving variable adalah variable non basic yang keluar dari variable basic dan masuk ke variable non basic.
    Sehingga persamaan $x_4$ diubah yang asalnya \[x_4 = 5-2x_1-3x_2-x_3\] menjadi \[x_1=\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4\]. Selanjutnya substitusikan persamaan $x_1$ pada persamaan basic lainnya dan $z$. Sehingga didapat \[\begin{align*} x_5 &= 11-4(\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4)-x_2-2x_3\\ & = 1+5x_2+2x_4\\ x_6 &= 8-3(\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4)-4x_2-2x_3\\ & =\frac{1}{2}+\frac{1}{2}x_2-\frac{1}{2}x_3+\frac{3}{2}x_4\\ z &= 5(\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4)+4x_2+3x_3\\ & = \frac{25}{2}-\frac{7}{2}x_2+\frac{1}{2}x_3-\frac{5}{2}x_4 \end{align*}\] Sehinga kita punya sistem baru, yaitu

    Iterasi kedua

    \[\begin{align*} x_1 &=\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}x_3-\frac{1}{2}x_4\\ x_5 &= 1+5x_2+2x_4\\ x_6 &= \frac{1}{2}+\frac{1}{2}x_2-\frac{1}{2}x_3+\frac{3}{2}x_4\\ z &= \frac{25}{2}-\frac{7}{2}x_2+\frac{1}{2}x_3-\frac{5}{2}x_4 \end{align*}\] Dari sistem baru ini, pilih entering variable dan leaving variable sesuai dengan langkah-langkah yang sudah dilakukan sebelumnya. Entering variable yang dipilih adalah $x_3$ dan variable non basic yang lain disamadengankan nol (lihat dari persamaan $z$). Kemudian pilih leaving variable.
    • $x_1\geq 0$ maksimal nilai $x_3=5$
    • $x_5\geq 0$ tidak dipengaruhi nilai $x_3$
    • $x_6\geq 0$ maksimal nilai $x_3=1$
    Maka yang dipilih sebagai leaving variable adalah $x_6$. Sehingga persamaan $x_6$ diubah yang asalnya \[x_6 = \frac{1}{2}+\frac{1}{2}x_2-\frac{1}{2}x_3+\frac{3}{2}x_4\] menjadi \[x_3=1+x_2+3x_4-2x_6\] Kemudian substitusikan persamaan $x_3$ pada persamaan $x_1,x_5$ dan $z$. \[\begin{align*} x_1 &=\frac{5}{2}-\frac{3}{2}x_2-\frac{1}{2}(1+x_2+3x_4-2x_6)-\frac{1}{2}x_4\\ &=2-2x_2-2x_4+x_6\\ x_5 &= 1+5x_2+2x_4\\ z &= \frac{25}{2}-\frac{7}{2}x_2+\frac{1}{2}(1+x_2+3x_4-2x_6)-\frac{5}{2}x_4\\ &= 13-3x_2-x_4-x_6 \end{align*}\] Sehingga didapat sistem baru yaitu: \[ \begin{align*} x_3 &=1+x_2+3x_4-2x_6\\ x_1 &=2-2x_2-2x_4+x_6\\ x_5 &= 1+5x_2+2x_4\\ z &= 13-3x_2-x_4-x_6 \end{align*}\] Terlihat bahwa tidak ada variable no basic di $z$ yang bisa dinaikkan kembali. Ini berarti kita sudah mendapatkan solusi optimal dengan $z=13$, $x_3=1$, $x_1=2$, dan $x_2=0$. Untuk lebih meyakinkan jawaban kita, kita bandingkan dengan hasil di aplikasi Lingo, berikut hasilnya
    metode simplex dictionaries

  2. Tentukan solusi dari masalah program linear berikut \[\begin{align*} Maksimumkan \hspace{1cm}& 5x_1+5x_2+3x_2\\ s.t \hspace{1cm}& x_1+3x_2+x_3\leq 3\\ & -x_1 + 3x_3\leq 2\\ & 2x_1 - x_2+2x_3\leq 4\\ & 2x_1+3x_2-x_3\leq 2\\ & x_1,x_2,x_3\geq 0 \end{align*}\]

    Jawab

    Sama seperti soal no 1. Definisikan terlebih dahulu \[\begin{align*} x_4 &= 3-x_1-3x_2-x_3\\ x_5 &= 2+x_1-3x_3\\ x_6 &= 4-2x_1 + x_2-2x_3\\ x_7 &= 2-2x_1-3x_2+x_3\\ z & = 5x_1+5x_2+3x_2\\ \end{align*}\] dimana $x_1,x_2,x_3,x_4,x_5,x_6,x_7\geq 0$.

    Iterasi pertama

    Pilih entering variable. Untuk memeilih enterng variable, lihat persamaan di $z$ dan pilih variable non basic $x$ yang mana yang akan menaikkan nilai $z$ lebih cepat(lebih besar). Tentunya $x_1$ atau $x_2$. Boleh memilih $x_1$ atau $x_2$ yang dipilih menjadi entering variable. Disini saya pilih $x_1$ yang menjadi entering variable. Setelah itu, langkah selanjutnya yang harus dilakukan adalah memilih leaving variable.
    • $x_4\geq 0$ maksimal nilai $x_1=3$.
    • $x_5\geq 0$ maksimal nilai $x_1=\infty$.
    • $x_6\geq 0$ maksimal nilai $x_1=2$.
    • $x_7\geq 0$ maksimal nilai $x_1=1$.
    Sehingga yang dipilih leaving variable adalah $x_7$. Selanjutnya ubah persamaan $x_7$ yang asalnya $x_7 = 2-2x_1-3x_2+x_3$ menjadi $x_1=1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7$. Kemudian substitusikan persamaan $x_1$ ke persamaan $x_4,x_5,x_6$ dan $z$. \[\begin{align*} x_4 &= 3-(1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7)-3x_2-x_3\\ & =2-\frac{3}{2}x_2-\frac{3}{2}x_3+\frac{1}{2}x_7\\ x_5 &= 2+(1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7)-3x_3\\ & =3-\frac{3}{2}x_2-\frac{5}{2}x_3-\frac{1}{2}x_7\\ x_6 &= 4-2(1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7) + x_2-2x_3\\ & =2+4x_2-3x_3+x_7\\ z & = 5(1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7)+5x_2+3x_2\\ & =5-\frac{5}{2}x_2+\frac{11}{2}x_3-\frac{5}{2}x_7\\ \end{align*}\] Sehingga didapat persamaan baru yaitu \[\begin{align*} x_1 &=1-\frac{3}{2}x_2+\frac{1}{2}x_3-\frac{1}{2}x_7\\   x_4 &=2-\frac{3}{2}x_2-\frac{3}{2}x_3+\frac{1}{2}x_7\\ x_5 &=3-\frac{3}{2}x_2-\frac{5}{2}x_3-\frac{1}{2}x_7\\ x_6 & =2+4x_2-3x_3+x_7\\ z & =5-\frac{5}{2}x_2+\frac{11}{2}x_3-\frac{5}{2}x_7\\ \end{align*}\]

    Iterasi kedua

    Pilih entering variable dan leaving variable. Entering variable yang dipilih adalah (lihat persamaan $z$) $x_3$. Kemudian untuk leaving variable adalah
    • $x_1\geq 0$ maksimal nilai $x_3=\infty$
    • $x_4\geq 0$ maksimal nilai $x_3=\frac{4}{3}$
    • $x_5\geq 0$ maksimal nilai $x_3=\frac{6}{5}$
    • $x_6\geq 0$ maksimal nilai $x_3=\frac{2}{3}$
    Maka leaving variable yang dipilih adalah $x_6$. Maka ubah persamaan $x_6$ yang asalanya $x_6=2+4x_2-3x_3+x_7$ menjadi $x_3=\frac{2}{3}+\frac{4}{3}x_2+\frac{1}{3}x_7-\frac{1}{3}x_6$. Kemudian substitusikan $x_3$ ke persamaan $x_1,x_4,x_5$, dan $z$. Sehingga didapat \[\begin{align*} x_3 &=\frac{2}{3}+\frac{4}{3}x_2+\frac{1}{3}x_7-\frac{1}{3}x_6\\ x_1 &= \frac{4}{3}-\frac{5}{6}x_2-\frac{1}{3}x_7-\frac{1}{6}x_6\\ x_4 & =1-\frac{7}{2}x_2+\frac{1}{2}x_6\\ x_5 & =\frac{4}{3}-\frac{29}{6}x_2-\frac{4}{3}x_7+\frac{5}{6}x_6\\ z & =\frac{26}{3}+\frac{29}{6}x_2-\frac{2}{3}x_7-\frac{11}{6}x_6 \end{align*}\]

    Iterasi ketiga

    Entering variabel adalah $x_2$. Leaving variabelnya adalah
    • $x_3\geq 0$, maksimal nilai $x_2=\infty$
    • $x_1\geq 0$, maksimal nilai $x_2=\frac{8}{5}$
    • $x_4\geq 0$, maksimal nilai $x_2=\frac{2}{7}$
    • $x_5\geq 0$, maksimal nilai $x_2=\frac{8}{29}$
    Maka leaving variable adalah $x_5$. Sehingga didapat persamaan $x_2=\frac{8}{29}-\frac{8}{29}x_7+\frac{5}{29}x_6-\frac{6}{29}x_5$. Maka didapat persamaan baru yaitu \[\begin{align*} x_2 &=\frac{8}{29}-\frac{8}{29}x_7+\frac{5}{29}x_6-\frac{6}{29}x_5\\ x_3 &=\frac{30}{29}-\frac{1}{29}x_7-\frac{3}{29}x_6-\frac{8}{29}x_5\\ x_1 &=\frac{32}{29}-\frac{3}{29}x_7-\frac{9}{29}x_6+\frac{5}{29}x_5\\ x_4 &=\frac{1}{29}+\frac{28}{29}x_7-\frac{3}{29}x_6+\frac{21}{29}x_5\\ z &=10-2x_7-x_6-x_5 \end{align*}\] Karena tidak ada variable non basic yang bisa di naikkan lagi yang mengakibatkan nilai $z$ semakin besar, maka kita sudah mendapatkan solusi optimal. $z=10$ dengan $x_1=\frac{32}{29},x_2=\frac{8}{29}$, dan $x_3=\frac{30}{29}$. Kita bandingkan dengan hasil menggunakan aplikasi Lingo. Berikut jawabannya.
    metode simplex dictionaries

Cukup sekian dulu pembahasannya. Bagi teman-teman yang ingin membaca artikel tentang kesehatan, bisa baca disini. Atau baca stikel lainnya disini.

Berlangganan update artikel terbaru via email:

0 Response to "Metode Simplex Dictionaries pada Linear programming"

Post a Comment

Iklan Atas Artikel

Iklan Tengah Artikel 1

Iklan Tengah Artikel 2

Iklan Bawah Artikel