Dosen Pengampu: Prof. Dr. Suhartono, M.Kom

Mata Kuliah: Linear Algebra

Prodi: Teknik Informatika

Lembaga: Universitas Islam Negeri Maulana Malik Ibrahim Malang

1 Pengertian Linear Programming

Dalam hal penetapan jumlah dan jenis produksinya yang harus dihasilkan perusahaan untuk periode tertentu dapat menggunakan metode linier programming. Dengan metode linier programming perusahaan dapat menentukan kombinasi produk yang akan dihasilkan perusahaan dengan kapasitas produksi yang dimiliki perusahaan. Untuk itu perlu diketahui bersama apa yang dimaksud dengan linier programming

pengertian linear Programing merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan kombinasi-kombinasi produk yang terbaik dalam menyusun alokasi sumber daya yang terbatas guna mencapai tujuan yang digunakan secara optimal.

Secara lebih formal, program linear adalah sebuah teknik optimisasi untuk fungsi objektif linear, dengan kendala (beberapa) persamaan linear dan pertidaksamaan linear. Daerah feasibel dari kendala berupa sebuah politop konveks yakni sebuah himpunan yang didefinisikan dari perpotongan banyak (namun terhingga) half spaces. Sedangkan fungsi objektif berupa fungsi (linear) bernilai real yang terdefinisi pada politop tersebut. Sebuah algoritme program linear akan mencari sebuah titik pada politop, yang menyebabkan fungsi objektif akan menghasilkan nilai terkecil (atau terbesar); jika titik tersebut ada. Berikut contoh penerapan linear programming menggunakan masalah maksimisasi pada bahasa pemrograman R.

2 Pernyataan Masalah Maksimisasi

Contoh

PT. HARAPAN TEKSTIL 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:

Kedua jenis produk memberikan keuntungan sebesar Rp.40.000.000,- untuk kain sutera dan Rp.30.000.000,- untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal.

3 Tahapan Penyelesaian

menentukan variabelnya terlebih dahulu

X1=kain sutera

X2=kain wol

Fungsi Tujuan

Zmax= 40X1 + 30X2

library (lpSolve)
# Memasukkan koefisien dari fungsi tujuan pada f.obj
f.obj <- c(40, 30)

Fungsi Kendala/Batasan

  1. 2X1 + 3X2 ≤ 60 (benang sutera)

  2. 2X2 ≤ 30 (benang wol)

  3. 2X1 + X2 ≤ 40 (tenaga kerja)

# Memasukkan koefiesian fungsi kendala dalam bentuk matriks 
# Dengan nrow menunjukkan banyaknya kendala yaitu 3 dan angka yang 
# diinput disusun perbaris sehingga byrow = TRUE
f.con <- matrix(c(2, 3,
                  0, 2,
                  2, 1), nrow = 3, byrow = TRUE)
# Memasukkan tanda pertidaksamaan pada setiap kendala
f.dir <- c("<=",
           "<=",
           "<=")
# Memasukkan koefisien ruas kanan
f.rhs <- c(60,
           30,
           40)

Mendapatkan Solusi Optimal

# Keuntungan Maksimum
lp("max", f.obj, f.con, f.dir, f.rhs)
## Success: the objective function is 900
# Nilai Variabel agar mencapai keuntungan maksimum
lp("max", f.obj, f.con, f.dir, f.rhs)$solution
## [1] 15 10
# Koefisien sensitivitas
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
## [1] 20 20
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
## [1] 60 60
# Bayangan/harga ganda dari kendala dan variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
## [1]  5  0 15  0  0
# Batas bawah batasan harga bayangan/ganda dan masing masing variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
## [1]  4e+01 -1e+30  3e+01 -1e+30 -1e+30
# Batas atas batasan harga bayangan/ganda dan masing masing variabel keputusan
lp("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
## [1] 7e+01 1e+30 6e+01 1e+30 1e+30

4 Kesimpulan

Nilai z maksimum yang dapat diperoleh saat memenuhi kendala yang diberikan adalah 900 ( keuntungan sebesar Rp 900 juta), di mana X1=15 X2=10. Koefisien sensitivitas berubah dari 20 dan 20 menjadi 60 dan 60. Bayangan/harga ganda dari kendala adalah 5, 0 dan 15, sedangkan untuk variabel keputusan masing-masing adalah 0 dan 0. Batas bawah harga bayangan adalah 4e+01, -1e+30, dan 3e+01, sedangkan untuk variabel keputusan berturut-turut adalah -1e+30 dan -1e+30. Terakhir, batas atas harga bayangan adalah 17e+01, 1e+30, dan 6e+01, sedangkan untuk variabel keputusan masing-masing adalah 1e+30 dan 1e+30.