Tugas Optimasi

Week 4

Email             : dsciencelabs@outlook.com
RPubs            : https://rpubs.com/vanessasupit/
Github           : https://github.com/vanessasupit/
Jurusan          : Statistika
Address         : ARA Center, Matana University Tower
                         Jl. CBD Barat Kav, RT.1, Curug Sangereng, Kelapa Dua, Tangerang, Banten 15810.

---

1 SOAL

Sebuah perusahaan memproduksi dua model kursi: A dan B. Model A membutuhkan 4 balok, 1 dudukan kursi, dan 1 sandaran kursi. Sedangkan model B membutuhkan 3 balok dan 1 dudukan kursi. Perusahaan memiliki stok awal 200 balok, 500 dudukan kursi, dan 100 sandaran kursi. Jika perusahaan membutuhkan lebih banyak balok, dudukan kursi, dan sandaran kursi, mereka dapat membeli kayu balok standar, yang harganya 80 euro per balok. Perusahaan dapat memproduksi 20 balok, 10 dudukan kursi, dan 2 sandaran kursi dari balok kayu standar. Biaya produksi model A adalah 30 euro/kursi, sedangkan biaya model B adalah 40 euro/kursi. Jika perusahaan menginformasikan bahwa jumlah minimum kursi yang harus diproduksi adalah 1000 unit per bulan. Tentukan model program linier, yang dapat meminimalkan total biaya.

Selesaiakan permasalahan optimasi diatas dengan cara:

• Grafik
• Manual
• Menggunakan R
• Menggunakan Python

2 Solutions

Kita konversi soal sebelumnya dalam bentuk tabel terlebih dahulu.

Keterangan :

• x = Model A
• y = Model B
• z = Balok

	Balok	dudukan kursi	sandaran	Biaya
x	4	1	1	30
y	3	1		40
z	20	10	2	80
Ketersediaan	200	500	100

Fungsi Tujuan :

Dengan memperhatikan biaya produksi model A adalah 30 euro/kursi, biaya model B adalah 40 euro/kursi, dan biaya balok 80 euro/kursi

\[ Min(30x_x+40x_y+80x_z) \]

Fungsi Batasan :

• Untuk produksi balok perusahaan memiliki stok awal 200 dan dapat memproduksi 20 balok lagi

\[ 4x_x+3x_y \le 200+20x_z\\ 4x_x+3x_y-20x_z \le 200 \]

• Untuk produksi dudukan kursi perusahaan memiliki stok awal 500 dan dapat memproduksi 10 dudukan lagi

\[ x_x+x_y \le 500+10x_z\\ x_x+x_y-10x_z \le 500 \]

• Untuk produksi sandaran kursi perusahaan memiliki stok awal 100 dan dapat memproduksi 2 sandaran lagi

\[ x_x \le 100 +2x_z \\ x_x -2x_z \le 100 \]

• jumlah minimum model a dan b yang diproduksi

\[ x_x+x_y \ge 1000 \]

2.1 Grafis

x	y	z	arah kendala	Ketersediaan
1	1	-10	<=	500
4	3	-20	<=	200
1	0	-2	<=	100
1	1	0	=>	1000

\[ 4x_x+3x_y-20x_z \le 200\\ x_x+x_y-10x_z \le 500\\ x_x -2x_z \le 100\\ x_x+x_y \ge 1000\\ x_x \ge 0\\ x_y \ge o\\ x_z \ge 0 \]

Grafiknya dapat dicek disini

2.2 Manual

Kita dapat menggunakan metode simplex untuk mengerjakan solusi manualnya.

Langkah-langkah :

• Mengubah semua kendala ke Bentuk Kanonik Simpleks (yang semula menggunakan tanda pertidaksamaanmen jadi persamaan) dengan menambah perubah (variabel) SlackS. Perubah-perubah slack yang ada dimasukkan(ditambahkan) kefungsi sasaran dan diberikoefisien 0.
• Tabel yang kita miliki sudah minimum jika semua \(Z_j-C_j \le 0\)
• Jika ada \(Z_j-C_j > 0\) (positif) maka dibuat tabel baru dengan cara sebagai berikut :
  • Menentukan kolom kunci yaitu memilih nilai \(Z_j- C_j\) yang terbesar. Sebut dengan \(Z_k-C_k\) maka kolom ke-k disebut kolom kunci.
  • Pada kolom ke-k dilakukan pemeriksaan terhadap nilai \(a_{ik}\).
• Menentukan baris kunci, yaitu nilai Ri yang terkecil, selanjutnya baris yg memuat Ri terkecil disebut baris kunci.
• Kemudian disusun tabel baru sebagai berikut (dimulai dari baris kunci baru):
  • elemen baris kunci baru = elemen baris kunci lama dibagi \(a_{ik}\)
  • elemen baris baru = elemen baris lama - (\(a_{ik}\) x elemen baris r baru)
• Kemudian tentukan lagi nilai Xi, Ci, Zj , Zj - Cj

Keterangan : * Baris Cj diisi dengan para koefisien Fungsi Tujuan (sasaran) * Baris Xj diisi dengan nama-nama perubah (variabel) yang ada. * Kolom B diisi dengan nama-nama perubah yang menjadi basis (variabel yang menyusun matriks Identitas) . * Kolom Cb diisi dengan para koefisien perubah yang menjadi basis * Kolom Xb diisi dengan para konstanta fungsi kendala (Nilai Sebelah Kanan/NSK). * Baris Zj diisi dengan rumus:\(\sum_{i=1}^m C_ba_{ij}\), j=1,…,n. * Kolom Ri diisi dengan rumus \(Ri = Xb/a_{ik}\) (aik = elemen elemen yang berada dalam kolom kunci, dan Ri dihitung hanya untuk aik ≥ 0)

\[ Z_{min}=30x_x+40x_y+80x_z+0S_1+0S_2+0s_3+0s_4+MV\\ 4x_x+3x_y-20x_z + S_1= 200\\ x_x+x_y-10x_z +S_2= 500\\ x_x -2x_z+S_3= 100\\ x_x+x_y -S_4+V= 1000 \] \[ Z= 48666.67 \\ x = 422\\ y = 578\\ z = 161 \]

Kita dapat nilai minimum costnya yaitu 48666.67 dengan memproduksi model A 422, model B 578 dan balok 161.

2.3 R

2.3.1 lpsolve

require(lpSolve)

## Loading required package: lpSolve

C <- c(30, 40, 80)

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


B <- c(500, 200, 100, 1000)


constranints_direction  <- c("<=", "<=", "<=", ">=")

optimum <-  lp(direction="min",
               objective.in = C,
               const.mat = A,
               const.dir = constranints_direction,
               const.rhs = B,
               all.int = T)

# Print status: 0 = success, 2 = no feasible solution
print(optimum$status)

## [1] 0

# menunjukkan nilai X_x, X_y dan X_z
best_sol <- optimum$solution
names(best_sol) <- c("x_x", "x_y", "x_z") 
print(best_sol)

## x_x x_y x_z 
## 420 580 161

yang diproduksi oleh perusahaan yaitu : * Model A = 420 * Model B = 580 * Balok = 161

# Cek nilai biaya pada solusi optimal
print(paste("Total Biaya minimum: ", optimum$objval, sep=""))

## [1] "Total Biaya minimum: 48680"

rm(optimum, constranints_direction, best_sol)

2.3.2 lpSolveAPI

require(lpSolveAPI)

## Loading required package: lpSolveAPI

lprec <- make.lp(nrow = 4, ncol = 3)

lp.control(lprec, sense="min")

## $anti.degen
## [1] "fixedvars" "stalling" 
## 
## $basis.crash
## [1] "none"
## 
## $bb.depthlimit
## [1] -50
## 
## $bb.floorfirst
## [1] "automatic"
## 
## $bb.rule
## [1] "pseudononint" "greedy"       "dynamic"      "rcostfixing" 
## 
## $break.at.first
## [1] FALSE
## 
## $break.at.value
## [1] -1e+30
## 
## $epsilon
##       epsb       epsd      epsel     epsint epsperturb   epspivot 
##      1e-10      1e-09      1e-12      1e-07      1e-05      2e-07 
## 
## $improve
## [1] "dualfeas" "thetagap"
## 
## $infinite
## [1] 1e+30
## 
## $maxpivot
## [1] 250
## 
## $mip.gap
## absolute relative 
##    1e-11    1e-11 
## 
## $negrange
## [1] -1e+06
## 
## $obj.in.basis
## [1] TRUE
## 
## $pivoting
## [1] "devex"    "adaptive"
## 
## $presolve
## [1] "none"
## 
## $scalelimit
## [1] 5
## 
## $scaling
## [1] "geometric"   "equilibrate" "integers"   
## 
## $sense
## [1] "minimize"
## 
## $simplextype
## [1] "dual"   "primal"
## 
## $timeout
## [1] 0
## 
## $verbose
## [1] "neutral"

set.type(lprec, 1:3, type=c("integer"))

set.objfn(lprec, C)

# Tambahkan kendala
add.constraint(lprec, A[1, ], "<=", B[1])
add.constraint(lprec, A[2, ], "<=", B[2])
add.constraint(lprec, A[3, ], "<=", B[3])
add.constraint(lprec, A[4, ], ">=", B[4])

lprec

## Model name: 
##            C1   C2   C3            
## Minimize   30   40   80            
## R1          0    0    0  free     0
## R2          0    0    0  free     0
## R3          0    0    0  free     0
## R4          0    0    0  free     0
## R5          1    1  -10    <=   500
## R6          4    3  -20    <=   200
## R7          1    0   -2    <=   100
## R8          1    1    0    >=  1000
## Kind      Std  Std  Std            
## Type      Int  Int  Int            
## Upper     Inf  Inf  Inf            
## Lower       0    0    0

solve(lprec)

## [1] 0

Nilai \(x_x, x_y , x_z\)

get.variables(lprec)

## [1] 420 580 161

Nilai fungsi tujuan

get.objective(lprec)

## [1] 48680

2.4 Python

Pengerjaan python saya lakukan di colabs