Pemrograman Linear menggunakan metode grafik
Tuesday, June 18, 2019
Add Comment
Pemrograman Linear
Pemograman Linier adalah suatu cara untuk menyelesaikan persoalan mengalokasikan sumber-sumber daya yang terbatas diantara beberapa aktivitas yang bersaing, dengan cara terbaik yang mungkin dilakukan. Pemrograman (programming) secara umum berkaitan dengan penggunaan atau pengalokasian sumberdaya yang terbatas seperti tenaga kerja, bahan, mesin dan modal dengan cara yang “terbaik” untuk memperoleh biaya yang minimum atau profit yang maksimum. Istilah “terbaik” mengimplikasikan bahwa terdapat satu himpunan alternatif tindakan yang tersedia bagi pengambilan keputusan.
Secara umum, keputusan terbaik diperoleh dengan memecahkan suatu masalah matematis. Pemrograman linear banyak digunakan dalam berbagai bidang, karena banyak masalah dapat dinyatakan atau didekati sebagai model program linear dan teknik-teknik yang tersedia untuk memecahkan masalah linear programming cukup efisien.
Secara umum, keputusan terbaik diperoleh dengan memecahkan suatu masalah matematis. Pemrograman linear banyak digunakan dalam berbagai bidang, karena banyak masalah dapat dinyatakan atau didekati sebagai model program linear dan teknik-teknik yang tersedia untuk memecahkan masalah linear programming cukup efisien.
Langkah-langkah dalam membangun model pemrograman linear.
- Mengidentifikasi variabel yang tak diketahui yang akan ditentukan nilainya (decision variable) dan menyatakannya dengan simbol-simbol matematis.
- Mengidentifikasi semua pembatas (constraint) dan menyatakannya dengan persamaan atau pertidaksamaan linier sebagai fungsi dari variabel keputusan.
- Mengidentifikasi tujuan atau kriteria dan menyatakannya sebagai suatu fungsi linier dari variabel keputusan yang hendak dimaksimumkan atau diminimumkan (fungsi tujuan).
Bentuk Umum Model Pemrograman Linear
Maksimumkan: \[Z=c_1x_1+c_2x_2+...+c_nx_n\]
dengan pembatas
\[\begin{matrix}
a_{11}x_1+a_{12}x_2+...+a_{1n}x_n & (\leq ,=,\geq )b_1\\
a_{21}x_1+a_{22}x_2+...+a_{2n}x_n & (\leq ,=,\geq )b_2\\
.\\
.\\
.\\
a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n & (\leq ,=,\geq )b_n\\
x_1\geq 0,x_2\geq 0,...,x_n\geq 0 &
\end{matrix}\]
Notasi dalam bentuk vektor
\[A=\left[ \begin{matrix}
a_{11} & a_{12} & ... &a_{1n}\\
a_{21} & a_{22} & ... &a_{2n}\\
.\\
.\\
a_{m1} & a_{m2} & ... &a_{mn}\\
\end{matrix}\right]
X=\left[ \begin{matrix}
x_{1}\\
x_{2}\\
.\\
.\\
x_{n}\\
\end{matrix}\right]
b=\left[ \begin{matrix}
b_{1}\\
b_{2}\\
.\\
.\\
b_{m}\\
\end{matrix}\right]
c=\left( \begin{matrix}
c_1 & c_2 & ... &c_n
\end{matrix}\right)
\]
A: matrix $(m\times n)$
X: vektor kolom $(n\times 1)$ ($X$ adalah variabel keputusan $x_j$)
b: veltor kolom $(m\times 1)$ (konstanta ruas kanan)
c: vektor baris $(1\times n)$(koefisien ongkos $c_j$)
atau
Maksimumkan \[z=\sum_{j=1}^{n}c_jx_j\]
dengan batasan
\[\begin{align*}
\sum_{j}^{n}a){ij}x_j(\leq ,=,\geq ) b_i& i=1,2,...,m\\
x_j\geq 0& j=1,2,...,n
\end{align*}\]
atau
Maksimumkan $Z=CX$
dengan batasan $AX (\leq ,=, \geq )b$ dan $X\geq 0$
Contoh
Tentukan model pemrograman linear dari masalah berikut:
Suatu perusahaan akan akan menjadwalkan produksi dari peralatan dapur yang membutuhkan dua jenis sumber yaitu tenaga buruh dan bahan baku. Perusahaan telah merencanakan tiga jenis model dan ketiganya membutuhkan sumber dan memberikan keuntungan seperti Tabel berikut:
Penyediaan bahan baku yang dapat dilakukan perhari adalah 200kg, sedangkan kapasitas tenaga kerja yang dimiliki adalah 150jam/hari. Bagaimana perumusan Pemograman Linier dari masalah di atas agar keuntungan totalnya maksimum.
Jawab
Model pemrograman linearnya:
Maksimalkan \[Z=40x_1+20x_2+30x_3\]
dengan batasan \[\begin{align*}
7x_1+3x_2+6x_3&\leq 150\\
4x_1+4x_2+5x_3 & \leq 200\\
x_1, x_2, x_3 & \geq 0
\end{align*}\]
Asumsi-asumsi Pemrograman Linear
Proporsionalitas
Kontribusi tiap variabel terhadap fungsi tujuan dan penggunaan sumber daya adalah proporsional terhadap level dari varibel tersebut.
Aditivitas
Fungsi tujuan adalah penjumlahan langsung dari kontribusi individual dari ariabel-variabel yang berbeda. Sisi kiri dari setiap batasan harus merupakan jumlah setiap variabel dari sumber daya yang bersesuaian.
Divisibilitas
Asumsi ini menjanjikan bahwa variabel keputusan dapat dibagi ke dalam pemecahan sehingga dapat diperoleh nilai-nilai non integer
Deterministik
Asumsi ini menjamin bahwa seluruh parameter modelnya adalah konstanta yang diketahui, kenyataan asumsi ini jarang dapat dipenuhi secara tepat.
Kepastian
Semua parameter dari model adalah diketahui dan deterministik.
Solusi Pemrograman Linear
Terdapat dua metode yang dapat digunakan untuk menyelesaikan persoalan-persoalan model pemograman linier yaitu:
- Metode grafik
- Metode Simplek (numerik)
Contoh
PT SERBACAT adalah perusahaan kecil pembuat cat yang memproduksi dua jenis cat, yaitu interior dan eksterior. Terdapat dua jenis bahan yang digunakan, yaitu bahan A dan B. Ketersediaan bahan maksimum per hari adalah 6 ton untuk A dan 8 ton untuk B. Kebutuhan bahan mentah per ton produk cat untuk kedua jenis cat, interior dan eksterior, adalah sebagai berikut:
Penelitian pasar menunjukkan bahwa:
- Permintaan harian cat interior dikurangi dengan jumlah permintaan cat eksterior tidak lebih dari satu ton.
- Permintaan maksimum cat interior adalah terbatas pada 2 ton per hari.
Harga jual produk cat adalah $\$$3 untuk cat eksterior dan $\$$2 untuk cat interior. Berapa banyak cat interior dan eksterior yang harus diproduksi per hari agar diperoleh pendapatan yang maksimum?
Jawab
Untuk membuat model matematisnya bisa menggunakan langkah-langkah seperti berikut:
- Tentukan variabel-ariabel (yang tidak diketahui/ yang akan dicari nilainya) dari masalah tersebut.
- Tentukan batasan yang harus dikenakan atas variabel.
- Tentukan tujuan yang harus dicapai untuk menentukan pemecahan optimum (terbaik) dari semua nilai yang layak dari variabel tersebut.
Variabel keputusan
$x_1$: jumlah cat eksterior yang diproduksi per hari
$x_2$: jumlah cat interior yang diproduksi per hari
Batasan
- Ketersediaan bahan:Bahan A: $x_1+2x_2\leq 6$Bahan B: $2x_1+x_2\leq 8$
- PermintaanSelisih permintaan: $x_1-x_2\leq 1$Permintaan cat interior: $x_2\leq 2$
- Pembatasan tak negatif:$x_1\geq 0$ dan $x_2\geq 0$
Fungsi tujuan
Maksimumkan pendapatan tital \[Z=3x_1+2x_2\]
Sehingga model Pemrograman Linearnya adalah
Maksimumkan \[Z=3x_1+2x_2\]
dengan batasan
\[\begin{align*}
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*}\]
Setelah kita dapatkan model LP nya, kemudian pertama kita gunakan metode grafik untuk mencari $x_1$ dan $x_2$ yang nantinya akan kita bandingkan dengan nilai $x_1$ dan $x_2$ yang menggunakan metode simpleks.
Metode grafik
Gambarkan grafik untuk setiap persamaan.
bisa menggunakan web secara online bisa menggunakan https://www.geogebra.org atau https://www.desmos.com. disini penulis menggunakan situs geogebra.
hasilnya seperti berikut.
Kemudian gambarkan grafik persamaan tujuan. Disini dimisalkan fungsi tujuan disamadengankan dengan 6, tapi boleh berapapun, ini digunakan hanya untuk memudahkan dalam menggeser garis persamaan tujuan saja. atau yang lebih mudah, masukkan titik-titik koordina ujung daerah hasil.
Sehingga didapat bahwa cat yang harus di produksi agar perusahaan cat mendapatkan untung yang besar adalah cat eksterior sebanyak $3\frac{1}{3}$ton dan cat interior sebanyak $1\frac{1}{3}$ dengan banyaknya cat sebanya $12\frac{2}{3}$
Kemudian gambarkan grafik persamaan tujuan. Disini dimisalkan fungsi tujuan disamadengankan dengan 6, tapi boleh berapapun, ini digunakan hanya untuk memudahkan dalam menggeser garis persamaan tujuan saja. atau yang lebih mudah, masukkan titik-titik koordina ujung daerah hasil.
Sehingga didapat bahwa cat yang harus di produksi agar perusahaan cat mendapatkan untung yang besar adalah cat eksterior sebanyak $3\frac{1}{3}$ton dan cat interior sebanyak $1\frac{1}{3}$ dengan banyaknya cat sebanya $12\frac{2}{3}$
Selanjutnya bagaimana jika menggunakan metode simpleks? nantikan artikel berikutnya
0 Response to "Pemrograman Linear menggunakan metode grafik"
Post a Comment