Belajar Riset Operasi Bagian 2 - Linear Programming

2,007 Views

Linear Programming – Pemrograman linier adalah teknik untuk memecahkan masalah pengoptimalan yang kendala dan hasil diwakili oleh hubungan linier, jadi didalam persamaan matematikanya tidak akan melibatkan pangkat atau orde.

Sederhananya, pemrograman linier memungkinkan untuk memecahkan masalah jenis berikut:

Maksimalkan / minimalkan $C^T X$
Di bawah batasan $A X \leq B$ , dan
batasan $X \geq 0$

Seringkali kita perlu membuat keputusan berdasarkan batasan yang secara umum ada banyak kendala lain yang perlu kita perhitungkan. Contoh sederhananya adalah:

Kita ingin mengubah sistem pemanas untuk meminimalkan biaya sistem dan tagihan, sistem pemanas seperti apa yang harus kita pasang? Kompor pelet? Radiator listrik?
Kita ingin mendapatkan keuntungan yang maksimal dari penjualan kedua produk yang saya hasilkan ini. Berapa jumlah yang harus kita produksi setiap produk?

Pemrograman linier dapat membantu kalian dengan jenis keputusan ini di mana: Fungsi yang kita coba optimalkan adalah kombinasi linier dari variabel keputusan (mungkin tidak selalu demikian). Serta batasan/constraint yang kita miliki adalah kombinasi linier dari variabel keputusan

Contoh pengoptimalan linier

Contents

1 Contoh pengoptimalan linier
2 Definisi Masalah Linear Programming dengan R lpSolve
3 R implementasi dan solusi Linear Programming
4 Contoh lain Kasus Linear Programming
- 4.1 Kendala dari LP ini adalah:

Berikut contoh soal dari sebuah perusahaan pak jokowi yang memproduksi kursi kayu. Setiap kursi kayu mempunyai 3 bahan pokok yaitu bagian kaki, dudukan, dan sandaran. Perusahaan pak jokowi mempunyai beberapa model kursi yaitu 4P dan 3P. Berikut permasalahan yang sedang ingin dipecahkan oleh pak jokowi .

Sebuah perusahaan memproduksi dua model kursi: 4P dan 3P.

Model 4P membutuhkan 4 kaki, 1 dudukan dan 1 sandaran. Di sisi lain,

model 3P membutuhkan 3 kaki dan 1 sandaran.

Perusahaan memiliki stok awal

200 kaki,

500 dudukan, dan

100 sandaran.

Jika perusahaan membutuhkan lebih banyak kaki, jok dan punggung, ia dapat membeli balok kayu standar, yang biayanya 80 euro per balok. Perusahaan dapat memproduksi 20 kaki, 10 dudukan dan 2 sandaran dari balok kayu standar.

Biaya pembuatan

model 4P adalah 30 euro / kursi,

sedangkan untuk model 3P adalah 40 euro / kursi.

Terakhir, perusahaan menginformasikan bahwa jumlah minimal kursi yang akan diproduksi adalah 1000 unit per bulan. Tentukan model program linier, yang meminimalkan biaya total (biaya produksi dua kursi, ditambah pembelian balok kayu baru).

Definisi Masalah Linear Programming dengan R lpSolve

Pertama, kita perlu menerjemahkan masalah secara matematis. Mari tentukan variabel berikut

$x_ {4p}$ adalah jumlah kursi 4P yang akan diproduksi.
$x_ {3p}$ adalah jumlah kursi 3P yang akan diproduksi.
$x_w$ adalah jumlah balok kayu yang akan dibeli.

Bikin tabel saja biar mudah

keterangan	kaki-kaki	dudukan	sandaran	biaya
model 4P	4	1	1	30
model 3P	3	1	–	40
stok	200	500	100	–
balok kayu	20	10	2	80

Sekarang kita dapat mendefinisikan

$X = \begin{pmatrix} x_ {4p} \\ x_ {3p} \\ x_w \end{pmatrix}$

sebagai vektor variabel keputusan. Perhatikan bahwa itu harus $X \geq 0$ artinya semua tidak boleh negatif!

Kami ingin meminimalkan biaya total sehingga kami harus menetapkan fungsi tujuan kami sebagai berikut

$cost(x_{4p}, x_{3p}, x_w) = 30 x_{4p} + 40 x_{3p} + 80 x_w = MIN(cost)$

yang artinya

$C = \begin{pmatrix} 30 \\ 40 \\ 80 \end{pmatrix}$

Batasan dapat diatur dengan cara berikut

Untuk kaki-kaki: $4 x_{4p} + 3 x_{3p} \leq 200 + 20 x_w$
Untuk dudukan: $x_{4p} + x_{3p} \leq 500 + 10 x_w$
Untuk sandaran: $x_{4p} \leq 100 + 2 x_w$
Jumlah minimum kursi yang diproduksi $x_{4p} + x_{3p} \geq 1000$

Sekarang kita dapat mendefinisikan matriks koefisien

$A = \begin{pmatrix} 1 & 1 & -10 & \\ 4 & 3 & -20 & \\ 1 & 0 & -2 & \\ - 1 & - 1 & 0 & \end{pmatrix}$

dan

$B = \begin{pmatrix} 500 \\ 200 \\ 100 \\ -1000 \end{pmatrix}$

R implementasi dan solusi Linear Programming

Ada beberapa solver/library yang tersedia untuk menyelesaikan model pemrograman linier. Beberapa dari solver/library ini dapat dimasukkan ke dalam program yang lebih besar untuk mengembangkan masalah pengoptimalan. Beberapa dari mereka ditulis sebagai perpustakaan yang dapat dipanggil C, dan juga diimplementasikan dalam paket R. Paket berikut mungkin menarik untuk pengguna R.

lp_solve adalah library MILP, yang bekerja dalam berbagai macam bahasa. Model dapat dikirimkan melalui file input, API (antarmuka pemrograman aplikasi) atau IDE (lingkungan pengembangan terintegrasi). lp_solve saat ini tersedia R melalui paket lp_solve dan lp_solveAPI.
GLPK adalah singkatan dari GNU Linear Programming Kit. Ini adalah satu set pustaka yang dapat dipanggil yang ditulis dalam C yang dimaksudkan untuk menyelesaikan model LP, ILP dan MILP skala besar. Ini dikembangkan oleh Andrei Makhorin, dari Moscow Aviation Institute. GLPK berisi standalone solveri, glpsol, yang dapat dipanggil dari baris perintah. GLPK dapat membaca model yang ditulis dalam berbagai bahasa, di antaranya CPLEX, GNU MathProg, standar berdasarkan format AMPL yang memadai untuk menulis model besar dengan struktur biasa. GLPK dapat digunakan di R melalui paket Rglpk. Untuk pengguna windows tersedia GUSEK, IDE yang menjalankan perpustakaan GLPK.
Symphony adalah solver open source dari masalah MILP yang ditulis dalam C. Ini adalah inisiatif dari proyek COIN-OR. Dapat membaca soal yang ditulis dalam format MPS dan MathProg. Ini juga diimplementasikan di R melalui paket Rsymphony
linprog Perpustakaan untuk memecahkan model pemrograman linier, cukup populer di MATLAB. Ada juga paket R yang tersedia. Pustaka ini tidak menyelesaikan model ILP / MILP.

Semua solver diimplementasikan sebagai fungsi R, dan parameter dapat dilewatkan untuk fungsi ini sebagai matriks dan vektor R. Ini juga memungkinkan untuk menanamkan pemecah ini ke dalam program yang lebih besar. Beberapa dari paket ini memiliki fungsi yang dapat membaca program LP dan MILP dari file, yang ditulis dalam format standar seperti CPLEX, MPS atau AMPL / MathProg

Yuk kita mengimplementasikan linear programming di R. Ada banyak paket berbeda yang dapat memecahkan masalah semacam ini tetapi favorit saya adalah lpSolve. Seperti biasa kalau kalian belum install packages di R, silahkan saja buka RStudio dan ketikan kode berikut

install.packages("lpSolve")

Fitur bagus tentang paket lpSolve adalah kalian dapat menentukan arah pembatas seperti <; <=; >= dan >. Memang dalam kasus kami kendala terakhir jumlah minimum kursi yang diproduksi tidak sesuai dengan definisi matematis dari masalah yang saya berikan di paragraf sebelumnya. Di sini kita dapat mengubah tanda (dan oleh karena itu arah pertidaksamaan) atau menentukan arah pertidaksamaan di lpSolve. Berikut kode yang kita gunakan untuk menghitung linear programming di R

# Load lpSolve
library(lpSolve)

## koefisien variabel / fungsi objectif
C <- c(30, 40, 80)

# Buat matrix sebelah kiri
A <- matrix(c(1, 1, -10,
              4, 3, -20,
              1, 0, -2,
              1, 1, 0), nrow=4, byrow=TRUE)

# Buat matrix sebelah kanan
B <- c(500, 200, 100, 1000)

# set operator perbandingannya
constranints_direction  <- c("<=", "<=", "<=", ">=")

# panggil fungsi linear programming
optimum <-  lp(direction="min", #minimalkan biaya
               objective.in = C,
               const.mat = A,
               const.dir = constranints_direction,
               const.rhs = B,
               all.int = T)
# jika menghasilkan 0 maka feasible!
print(optimum$status)
# nilai optimal dari x_4p, x_3p and x_w
best_sol <- optimum$solution
names(best_sol) <- c("x_4p", "x_3p", "x_w") 
print(best_sol)

#fungsi biaya
print(paste("Total cost: ", optimum$objval, sep=""))

hasil

> print(optimum$status)
[1] 0
> print(best_sol)
x_4p x_3p  x_w 
 420  580  161 
> print(paste("Total cost: ", optimum$objval, sep=""))
[1] "Total cost: 48680"

dari informasi diatas dapat disimpulkan bahwa hasil nya feasible dengan jumlah 4P yang diproduksi sebesar 420 dan 3P sebesar 580 = 1000 kursi. Perusahaan beli balok balok kayu standar sebesar 161 sehingga biaya yang dikeluarkan yaitu

$(420 \times 30) + (580 \times 40) + (161 \times 80) = 48680$

Contoh lain Kasus Linear Programming

Mari pertimbangkan situasi berikut:

Sebuah bisnis kecil menjual dua produk, bernama Produk 1 dan Produk 2.

Setiap ton Produk 1 menghabiskan 30 jam kerja/ton Produk 2 menghabiskan 20 jam kerja/ton. Bisnis memiliki maksimal 2.700 jam kerja (working Hours / WH)
Adapun mesin tersedia 850 mesin, setiap Produk 1 dan 2 butuh 5 dan 10 mesin (Machine Hours/ MH)

Setiap ton Produk 1 menghasilkan keuntungan $20 , sedangkan Produk 2 menghasilkan $60 untuk setiap ton yang terjual. Untuk alasan teknis, perusahaan harus menghasilkan total minimal 95 ton antara kedua produk tersebut (Production Machine/PM). Kita butuh untuk mengetahui berapa ton Produk 1 dan 2 harus diproduksi memaksimalkan keuntungan total.

Pertama, kita perlu tentukan variabel keputusan. Dalam hal ini kami memiliki:

• P1 ton yang diproduksi dan dijual dari Produk 1
• P2 ton yang diproduksi dan dijual dari Produk 2

Koefisien biaya variabel ini masing-masing adalah 20 dan 60. Oleh karena itu, fungsi tujuan didefinisikan dengan mengalikan setiap variabel dengan variabelnya koefisien biaya yang sesuai.

Kendala dari LP ini adalah:

Kendala WH membuat jumlah total jam kerja tersebut digunakan dalam Produk 1 dan Produk 2, yang sama dengan 30P1 + 20P2, adalah kurang atau sama dari 2.700 jam. $30P1+20P2 \leq 2700$
Kendala serupa yang membuat MH membuat total jam mesin 5P1 + 10P2 kurang dari atau sama dengan 850. $5P1 +10P2 \leq 850$
Suatu kendala PM yang menyebabkan jumlah unit yang diproduksi dan dijual P1 + P2 lebih besar atau sama dari 95. $P1+p2 \leq 95$