1. Sekolah Dasar
  2. Sekolah Menengah Pertama
  3. Sekolah Menengah Atas
  4. Mata Pelajaran
  5. Programming

Tuliskan dual untuk masing-masing masalah simpleks primal berikut ini: Maksimumkan

Berikut ini adalah pertanyaan dari Brody102 pada mata pelajaran Matematika untuk jenjang Sekolah Menengah Atas

Tuliskan dual untuk masing-masing masalah simpleks primal berikut ini:Maksimumkan z=7x_1+x_2+4x_3
dengan batasan
x1+3x2-8x3≤44
2x1+8x2+5x3≤20
x1,x2,x3≥0
Minimumkan z=9x_1-11x_2+13x_3
dengan batasan
5x1+2x2-x3≥40
8x1+x3≥15
x1,x2,x3≥0

Jawaban dan Penjelasan

Berikut ini adalah pilihan jawaban terbaik dari pertanyaan diatas.

  1. Dual untuk masalah pada soal nomor 1 adalah:
    \boxed{\,\begin{aligned}&\sf Minimumkan\\&\quad\begin{aligned}v&=44y_1+20y_2\\\end{aligned}\\&\textsf{dengan batasan}\\&\begin{array}{rl}y_1+2y_2 \!\!\!& \ge 7,\\3y_1+8y_2 \!\!\!& \ge 1,\\5y_2-8y_1 \!\!\!& \ge 4,\\y_1,\,y_2 \!\!\!& \ge 0.\end{array}\end{aligned}\,}
  2. Dual untuk masalah pada soal nomor 2 adalah:
    \boxed{\,\begin{aligned}&\sf Maksimumkan\\&\quad\begin{aligned}v&=40y_1+15y_2\\\end{aligned}\\&\textsf{dengan batasan}\\&\begin{array}{rl}5y_1+8y_2 \!\!\!& \le 9,\\2y_1 \!\!\!& \le -11,\\y_2-y_1\!\!\!& \le 13,\\y_1,\,y_2 \!\!\!& \ge 0.\end{array}\end{aligned}\,}

 

Penjelasan

Primal-Dual Masalah Simpleks

Nomor 1

Diberikan masalah simpleks primal:

\begin{aligned}&\sf Maksimumkan\\&\quad\ z=7x_1+x_2+4x_3\\&\sf dengan\:batasan\\&\begin{array}{rl}x_1+3x_2-8x_3 \!\!\!& \le 44,\\2x_1+8x_2+5x_3 \!\!\!& \le 20,\\x_1,\,x_2,\,x_3 \!\!\!& \ge 0.\end{array}\end{aligned}

Dari masalah primal tersebut, kita mempunyai:

\begin{aligned}&\bullet&c&=\begin{pmatrix}7&1&4\end{pmatrix}\\&\bullet&x&=\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}\\&\bullet&A&=\begin{pmatrix}1&3&-8\\2&8&5\end{pmatrix}\\&\bullet&b&=\begin{pmatrix}44\\20\end{pmatrix}\\\end{aligned}

sehingga batasan/kendalanya dinyatakan dengan

\begin{aligned}A\cdot x \le b\ .\end{aligned}

Dual dari masalah simpleks tersebut dibeirkan oleh:

\begin{aligned}&\sf Minimumkan\\&\quad\begin{aligned}v&=b\cdot y\\&=\begin{pmatrix}44\\20\end{pmatrix}\cdot\begin{pmatrix}y_1&y_2\end{pmatrix}\\&=44y_1+20y_2\\\end{aligned}\end{aligned}

\begin{aligned}&\textsf{dengan batasan}\\&\quad\begin{aligned}A^Ty^T& \ge c^T,\ y \ge 0\\\begin{pmatrix}1&2\\3&8\\-8&5\end{pmatrix}\cdot\binom{y_1}{y_2}& \ge \begin{pmatrix}7\\1\\4\end{pmatrix},\ y_1,y_2 \ge 0\\\begin{pmatrix}y_1+2y_2\\3y_1+8y_2\\5y_2-8y_1\end{pmatrix}& \ge \begin{pmatrix}7\\1\\4\end{pmatrix},\ y_1,y_2 \ge 0\\\end{aligned}\end{aligned}

∴ Jadi, dual untuk masalah tersebut adalah

\boxed{\,\begin{aligned}&\sf Minimumkan\\&\quad\begin{aligned}v&=44x+20y\\\end{aligned}\\&\textsf{dengan batasan}\\&\begin{array}{rl}y_1+2y_2 \!\!\!& \ge 7,\\3y_1+8y_2 \!\!\!& \ge 1,\\-8y_1+5y_2 \!\!\!& \ge 4,\\y_1,\,y_2 \!\!\!& \ge 0.\end{array}\end{aligned}\,}
 

Nomor 2

Diberikan masalah simpleks primal:

\begin{aligned}&\sf Minimumkan\\&\quad\ z=9x_1-11x_2+13x_3\\&\sf dengan\:batasan\\&\begin{array}{rl}5x_1+2x_2-x_3 \!\!\!& \ge 40,\\8x_1+x_3 \!\!\!& \ge 15,\\x_1,x_2,x_3 \!\!\!& \ge 0.\end{array}\end{aligned}

Dari masalah primal tersebut, kita mempunyai:

\begin{aligned}&\bullet&c&=\begin{pmatrix}9&-11&13\end{pmatrix}\\&\bullet&x&=\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix}\\&\bullet&A&=\begin{pmatrix}5&2&-1\\8&0&1\end{pmatrix}\\&\bullet&b&=\begin{pmatrix}40\\15\end{pmatrix}\\\end{aligned}

sehingga batasan/kendalanya dinyatakan dengan

\begin{aligned}A\cdot x \le b\ .\end{aligned}

Dual dari masalah simpleks tersebut dibeirkan oleh:

\begin{aligned}&\sf Maksimumkan\\&\quad\begin{aligned}v&=b\cdot y\\&=\begin{pmatrix}40\\15\end{pmatrix}\cdot\begin{pmatrix}y_1&y_2\end{pmatrix}\\&=40y_1+15y_2\\\end{aligned}\end{aligned}

\begin{aligned}&\textsf{dengan batasan}\\&\quad\begin{aligned}A^Ty^T& \ge c^T,\ y \ge 0\\\begin{pmatrix}5&8\\2&0\\-1&1\end{pmatrix}\cdot\binom{y_1}{y_2}& \le \begin{pmatrix}9\\-11\\13\end{pmatrix},\ y_1,y_2 \ge 0\\\begin{pmatrix}5y_1+8y_2\\2y_1\\y_2-y_1\end{pmatrix}& \le \begin{pmatrix}9\\-11\\13\end{pmatrix},\ y_1,y_2 \ge 0\\\end{aligned}\end{aligned}

∴ Jadi, dual untuk masalah tersebut adalah

\boxed{\,\begin{aligned}&\sf Maksimumkan\\&\quad\begin{aligned}v&=40y_1+15y_2\\\end{aligned}\\&\textsf{dengan batasan}\\&\begin{array}{rl}5y_1+8y_2 \!\!\!& \le 9,\\2y_1 \!\!\!& \le -11,\\y_2-y_1\!\!\!& \le 13,\\y_1,\,y_2 \!\!\!& \ge 0.\end{array}\end{aligned}\,}
 
 
\overline{\begin{array}{l}\small\textsf{Duc In Altum}\\\small\text{bertolaklah\;ke\;tempat}\\\small\text{yang\;lebih\;dalam}\end{array}}

Semoga dengan pertanyaan yang sudah terjawab oleh DucInAltum dapat membantu memudahkan mengerjakan soal, tugas dan PR sekolah kalian.

Apabila terdapat kesalahan dalam mengerjakan soal, silahkan koreksi jawaban dengan mengirimkan email ke yomemimo.com melalui halaman Contact

Last Update: Fri, 02 Jun 23
<< Previous Post
Next Post >>