Monday, January 20, 2020

Buku Pemrograman Matlab - Linear Programming

Linear Programming


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:

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

Syarat Linear Programming

Dari 4 ciri khusus diatas, maka Linear Programming harus mempunyai syarat seperti berikut
  1. Certainty (kepastian): fungsi tujuan dan fungsi kendala sudah diketahui dengan pasti dan tidak berubah selama periode analisa.
  2. Proportionality (proporsionalitas): proporsionalitas dalam fungsi tujuan dan fungsi kendala.
  3. Additivity (penambahan): aktivitas total sama dengan penjumlahan aktivitas individu.
  4. Divisibility (bisa dibagi-bagi) : solusi tidak harus merupakan bilangan integer (bilangan bulat), tetapi bisa juga berupa pecahan.
  5. Non-negative variable (variabel tidak negatif): Artinya bahwa semua nilai jawaban atau variabel tidak negatif.

Tahapan dari Linear Programming

  1. Fungsi Tujuan (objective function) Fungsi yang menyatakan tujuan yang akan dicapai, dapat berupa maksimal atau minimal. Misalkan maksimalkan laba/keuntungan ataupun minimalkan biaya.
  2. Fungsi Kendala (contrains or subject to) Fungsi yang menyatakan batasan atau kendala dari faktor produksi yang dimiliki  Simbol yang digunakan : <, >, =
  3. 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: http://www.softscients.web.id/2020/01/dasar-dasar-pemrograman-matlab-grafik.html

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
  1. Membuat variabel terlebih dahulu, misalkan X1 = kain sutera; X2 = kain wol
  2. Menentunkan fungsi tujuan yaitu maksimalkan laba dengan persamaan umum \(Z = 40X1 + 30X2\)
  3. 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
  1. Grafik digunakan hanya untuk 2 variabel saja yang terlibat
  2. Simplex
  3. 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:

Buku Pemrograman Matlab  - Linear Programming


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 ≤ 48$$
Berat bagasi :
$$60x + 20y ≤ 1440$$
disederhanakan menjadi
$$3x + y ≤ 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

No comments:

Post a Comment