Linear Programming - Softscients

4,395 Views

sinopsis

Contents

1 sinopsis

Linear Programming dibangun atas model SPL / Sistem Persamaan Linear dengan kumpulan dari lebih dari satu persamaan linear yang dapat membentuk terhingga banyaknya solusi, tak hingga banyaknya solusi atau tidak mempunyai solusi.

Berikut Linear Programming dengan 2 variabel $a_1x+b_1y=c_2$ dan $a_2x+b_2y=c_2$ Program linear adalah suatu metode yang digunakan untuk memecahkan masalah yang berkaitan dengan optimasi linear (nilai maksimum dan nilai minimum). Misalkan sebuah perusahaan mempunyai tujuan umum seperti memaksimalkan keuntungan dan meminimalkan biaya karena ada batasan berupa sumber daya seperti SDM, waktu, ataupun material/peralatan.

Ciri Khusus Linier Programming:

Masalah mengarah pada pencapaian tujuan maksimisasi atau minimisasi
Kendala yang ada membatasi tingkat pencapaian tujuan
Ada beberapa alternatif penyelesaian
Hubungan bersifat linear

Syarat Linear Programming

Dari 4 ciri khusus diatas, maka Linear Programming harus mempunyai syarat seperti berikut

Certainty (kepastian): fungsi tujuan dan fungsi kendala sudah diketahui dengan pasti dan tidak berubah selama periode analisa.
Proportionality (proporsionalitas): proporsionalitas dalam fungsi tujuan dan fungsi kendala.
Additivity (penambahan): aktivitas total sama dengan penjumlahan aktivitas individu.
Divisibility (bisa dibagi-bagi) : solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan.
Non-negative variable (variabel tidak negatif): Artinya bahwa semua nilai jawaban atau variabel tidak negatif.

Tahapan dari Linear Programming

Fungsi Tujuan (objective function) Fungsi yang menyatakan tujuan yang akan dicapai, dapat berupa maksimal atau minimal. Misalkan maksimalkan laba/keuntungan ataupun minimalkan biaya.
Fungsi Kendala (contrains or subject to) Fungsi yang menyatakan batasan atau kendala dari faktor produksi yang dimiliki Simbol yang digunakan : <, >, =
Fungsi Status (status function) Fungsi yang menyatakan bahwa setiap variabel yang terdapat di dalam model programasi linear tidak boleh negatif.

Setelah kalian pahami Tahapan dari Linear Programming, kalian bisa selesaikan persoalan berikut menggunakan function built in di Matlab:

Untuk menggambar persamaan SPL (Sistem Persamaan Linear) kalian bisa kunjungi link: dasar-dasar-pemrograman-matlab-grafik

Soal 1 Linear Programming

PT. SRIL memiliki sebuah pabrik yang akan memproduksi 2 jenis produk, yaitu kain sutera dan kain wol. Untuk memproduksi kedua produk diperlukan bahan baku benang sutera, bahan baku benang wol dan tenaga kerja. Maksimum penyediaan benang sutera adalah 60 kg per hari, benang wol 30 kg per hari dan tenaga kerja 40 jam per hari. Kebutuhan setiap unit produk akan bahan baku dan jam tenaga kerja dapat dilihat dalam tabel berikut:

Maka langkah Pemodelan Linear Programming yaitu

Membuat variabel terlebih dahulu, misalkan X1 = kain sutera; X2 = kain wol
Menentunkan fungsi tujuan yaitu maksimalkan laba dengan persamaan umum $Z = 40X1 + 30X2$
Menentukan fungsi kendala yaitu untuk memproduksi kain sutera dan kain wol dibutuhkan 3 hal yaitu benang sutera, benang wol, dan tenaga kerja.

benang sutera

$2X_1+3X_2\leq60$

benang wol

$2X_2\leq30$

tenaga kerja

$2X_1+1X_2\leq40$

Kedua jenis produk memberikan keuntungan sebesar Rp 40 juta untuk kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal?

Pemecahan LP ada beberapa cara yaitu

Grafik digunakan hanya untuk 2 variabel saja yang terlibat
Simplex
Dualitas: Digunakan bila terjadi perubahan kapasitas.

Di Matlab untuk memecahkan permasalahan diatas menggunakan function linprog(). Persamaan umum linear programming yaitu

min $f'*x$ subject to: $A*x <=b$

dengan $linprog(f,A,b,Aeq,beq,LB,UB)$ , untuk kasus diatas bisa kita terapkan kode seperti berikut dengan

f : sebagai fungsi tujuan

A : sebagai fungsi batasan

B: konstanta batasan

LB : lower bound dan UB: upper bound

Kalian bisa buat variabel berikut sesuai dengan persamaan diatas

$f= \begin{pmatrix} 40\\ 30\\ \end{pmatrix}$

$A= \begin{pmatrix} 2 & 3\\ 0 & 2\\ 2 & 1\\ \end{pmatrix}$

$b= \begin{pmatrix} 60\\ 30\\ 40\\ \end{pmatrix}$

clc;clear all;close all;
f = [40;
    30];
A = [2,3;
    0,2;
    2,1];
b =[60;
    30;
    40];
 
[x,fval,flag]= linprog(-f,A,b);
if flag
    disp('Solusi Optimal yaitu')
    optimal = dot(f,x)    
end

hasil

Optimal solution found.

x =
   15.0000
   10.0000
Solusi Optimal yaitu
optimal =
   900
>>

Dengan X1 sebanyak 15 dan X2 sebanyak 10 akan menghasilkan laba sebesar 900.

Soal 2 Linear Programming

Sebuah area parkir dengan luas 3.750 m2, maksimal hanya dapat ditempati 300 kendaraan yang terdiri atas sedan dan bus. Jika luas parkir untuk sedan 5 m2 dan bus 15 m2, tentukanlah model matematikanya!

Jawab:

Misalkan:

x = banyaknya sedan

y = banyaknya bus

Jadi berdasarkan pertidaksamaan tersebut, model matematikanya adalah:

Untuk banyaknya kendaraan :

$x + y \leq300$

Untuk luas kendaraan :

$5x + 15y\leq 3750$

disederhanakan menjadi

$x + 3y\leq 750$

Banyaknya sedan $(x)$ tidak mungkin negatif: x ≥ 0

Banyaknya Bus $(y)$ tidak mungkin negatif : y ≥ 0

Soal 3 Linear Programming

Sebuah pesawat udara berkapasitas tempat duduk tidak lebih dari 48 penumpang. Setiap penumpang kelas utama boleh membawa bagasi 60 kg dan kelas ekonomi hanya 20 kg. Pesawat hanya dapat menampung bagasi 1.440 kg. Jika harga tiket kelas utama Rp600.000,00 dan kelas ekonomi Rp400.000,00, pendapatan maksimum yang diperoleh adalah….

Jawab:

Misalkan:

x = banyaknya penumpang kelas utama

y = banyaknya penumpang kelas ekonomi

Jadi berdasarkan pertidaksamaan tersebut, model matematikanya adalah:

Total penumpang :

$x + y \le 48$

Berat bagasi :

$60x + 20y \le 1440$

disederhanakan menjadi

$3x + y \le 72$

Banyaknya penumpang di kelas utama $(x)$ tidak mungkin negatif : x ≥ 0

Banyaknya penumpang di kelas ekonomi $(y)$ tidak mungkin negatif : y ≥ 0

clc;clear all;close all;
f = [600000;
     400000];
A = [1,1;
    3,1];
b =[48;
    72];
 
[x,fval,flag]= linprog(-f,A,b);
if flag
    x
    disp('Solusi Optimal yaitu')
    optimal = dot(f,x)    
end

hasil

Optimal solution found.

x =
   12.0000
   36.0000
Solusi Optimal yaitu
optimal =
   2.1600e+07

Dengan demikian pendapatan maksimum diperoleh jika banyaknya penumpang pada kelas utama adalah 12 dan banyaknya penumpang pada kelas ekonomi adalah 36 dengan keuntungan: Rp. 21.600.000