Pemrograman Linear menggunakan metode grafik

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.

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:

1. Metode grafik
2. 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:

1. Tentukan variabel-ariabel (yang tidak diketahui/ yang akan dicari nilainya) dari masalah tersebut.
2. Tentukan batasan yang harus dikenakan atas variabel.
3. 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

1. Ketersediaan bahan:
   Bahan A: $x_1+2x_2\leq 6$
   Bahan B: $2x_1+x_2\leq 8$
2. Permintaan
   Selisih permintaan: $x_1-x_2\leq 1$
   Permintaan cat interior: $x_2\leq 2$
3. 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}$

Selanjutnya bagaimana jika menggunakan metode simpleks? nantikan artikel berikutnya

Share this post

Berlangganan update artikel terbaru via email: