Operasi Riset
MIDTERM Operasi Riset Kelompok 2
Karen natalie (20204920015)
March 18, 2022
Email : brigita.melantika@student.matanauniversity.ac.id
RPubs : https://rpubs.com/brigitatiaraem/
Jurusan : Statistika
Address : ARA Center, Matana University Tower
Jl. CBD Barat Kav, RT.1, Curug Sangereng, Kelapa Dua, Tangerang, Banten 15810.
Anggota :
Brigita Tiara EM / 20204920001
Karen Natalie / 20204920015
Muhammad Naufal A. / 20204920017
1 PENYELESAIAN DENGAN R
Soal no.2
Sebuah toko menyediakan dua merk pupuk, yaitu Standard dan Super. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertentu.Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Standar dan Super masing-masing $3 dan $6. Petani tersebut ingin mengetahui berapa sak masing-masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi. Buatlah fungsi tujuan, kendala, penyelesaian manual, visualisasikan permasalan dengan grafik, dan penyelesaian dengan R.
1.1 CARA 1
library(lpSolve)
fungsi_tujuan<-c(3,6)
LHS<- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
arah_kendala<-c(">=", ">=")
RHS<-c(16, 24)
# penyelesaian
model3<-lp(direction = "min",
objective.in=fungsi_tujuan,
const.mat=LHS,
const.dir=arah_kendala,
const.rhs=RHS,
all.int = T,
compute.sens = TRUE)
print(model3)
## Success: the objective function is 24
str(model3)
## List of 28
## $ direction : int 0
## $ x.count : int 2
## $ objective : num [1:2] 3 6
## $ const.count : int 2
## $ constraints : num [1:4, 1:2] 2 4 2 16 4 3 2 24
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
## .. ..$ : NULL
## $ int.count : int 2
## $ int.vec : int [1:2] 1 2
## $ bin.count : int 0
## $ binary.vec : int 0
## $ num.bin.solns : int 1
## $ objval : num 24
## $ solution : num [1:2] 6 1
## $ presolve : int 0
## $ compute.sens : int 1
## $ sens.coef.from : num [1:2] 3e+00 -1e+30
## $ sens.coef.to : num [1:2] 1e+30 6e+00
## $ duals : num [1:4] 1.5 0 0 0
## $ duals.from : num [1:4] 1.45e+01 -1.00e+30 -1.00e+30 -1.00e+30
## $ duals.to : num [1:4] 1.0e+30 1.0e+30 1.0e+30 1.5
## $ scale : int 196
## $ use.dense : int 0
## $ dense.col : int 0
## $ dense.val : num 0
## $ dense.const.nrow: int 0
## $ dense.ctr : num 0
## $ use.rw : int 0
## $ tmp : chr "Nobody will ever look at this"
## $ status : int 0
## - attr(*, "class")= chr "lp"
# jika 0 berarti penyelesaiannya berhasil
print(model3$status)
## [1] 0
# nilai optimal pada variabel x_A dan x_B
nilop<-model3$solution
names(nilop)<-c("x_A","x_B")
nilop
## x_A x_B
## 6 1
# nilai fungsi tujuan pada titik optimum
print(paste("Biaya Minimum :", model3$objval, sep=""))
## [1] "Biaya Minimum :24"
library(ggplot2)
ggplot(data.frame(x = c(0, 100
)), aes(x = x)) +
stat_function(fun = function(x) {((16-2*x)/4)}, aes(color = "Function 1")) +
stat_function(fun = function(x) {((24-4*x)/4)} , aes(color = "Function 2")) +
theme_bw() +
scale_color_discrete(name = "Function") +
geom_polygon(
data = data_frame(
x = c(0, 0, 100, Inf),
y = c(0, 50, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 1"
),
inherit.aes = FALSE, alpha = 0.4
) +
geom_polygon(
data = data.frame(
x = c(0, 0, 25, Inf),
y = c(0, 75, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 2"
),
inherit.aes = FALSE, alpha = 0.4
) +
scale_fill_discrete(name = "Constraint Set") +
scale_y_continuous(limits = c(0, 100))
1.2 CARA 2
# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c(3, 6)
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
# Set unequality signs
f.dir <- c(">=",
">=")
# Set right hand side coefficients
f.rhs <- c(16,
24)
# Final value (z)
lp("min", f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp("min", f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
# Duals lower and upper limits
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
2 METODE SIMPLEX
Selesaikan linear program berikut ini dengan metode Simplex maksimumkan:
\[Z = 2X_1 + 3X_2 + X_3 \]
Dengan fungsi kendala:
\[1) X_1 + X_2 + X_3 ≤ 9 \]
\[ 2) 2X_1 + 3X_2 ≤ 25 \]
\[3) X_2 + 2X_3 ≤ 10 \]
\[4) X_1, X_2, X_3 ≥ 0\]
Maka Fungsi objektif akan berubah menjadi :
\[Max Z = 2 x_1 + 3 x_2 + x_3 + 0 S_1 + 0 S_2 + 0 S_3\]
Dan untuk contraints akan menjadi :
\[x_1 + x_2 + x_3 + S_1 = 9\]
\[2 x_1 + 3 x_2 + S_2 = 25\]
\[x_2 + 2 x_3 + S_3 = 10\]
\[ x_1,x_2,x_3,S_1,S_2,S_3≥0\]
\[x_1=0, x_2=253,x_3=23, Max Z=77/3\]
3 PRIMAL DAN DUAL
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual. Berikan penjelasan mengenai perbedaan Primal dan Dual (berikan juga contoh soal dan penyelesaiannya).
Bentuk Primal : bentuk asli dari persamaan program linear.
Bentuk Dual : bentuk duplikat atau rangkap dari persamaan program linear.
Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan sebagai berikut:
Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi koefisien fungsi tujuan dual.
Tanda pertidaksamaan pembatas dibalik (pada primal “<=”, pada dual “>=”)
Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada dual.
Setiap kolom pada prima berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya dengan variabel keputusan primal.
Setiap baris (pembatas) padaprimal berhubungan dengan suatu kolom dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan dual.
Bentuk dual dari dual adalah primal.
Contoh :
Masalah Primal
\[Max; Z=3a+5b\]
contraints :
\[2a<=6\]
\[3b<=15\]
\[6a+4b<=24\]
\[a,c>=0\]
Masalah Dual
\[ Min; W=6y_1+15y_2+24y_3\]
contraints:
\[2y_1+6y_3>=3\]
\[3y_2+4y_3>=5\]
\[y_1,y_2,y_3>=0\]
3.1 penyelesaian optimal dual dengan tablo simplex optimal primal
Pada tablo simpleks permasalahan di atas variabel basis awalnya adalah S1, S2, dan S3 dengan koefisien-koefisien persamaan optimal Z berturut-turut adalah 0, 1, dan 1/2. Sedangkan fungsi batasan pada masalah dual yang berkaitan dengan S_1, S_2, dan S_3 berturut-turut adalah y_1 >= 0, y_2 >= 0 , dan y_3 >= 0.
Dari hal tersebut maka diperoleh informasi sebagai berikut.
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[y_1 - 0 = 0 -> y_1 = 0\] \[y_2 - 0 =1 -> y_2 =1\]
\[y_3 -0 = 1/2 -> y_3 = 1/2\]
Jadi, penyelesaian optimal masalah dual tercapai di
\[(y_1,y_2,y_3)=(1,0,1/2)\]
nilai optimal
\[W_- =6(0)=15(1)+24(1/2)=27\]
3.2 penyelesaian optimal dual dengan tablo simplex optimal dual
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[a-M=(4/6) -M -> a=4/6\]
\[b-M=5-M -> b=5\]
Jadi, penyelesaian optimal masalah primal tercapai di
\[(a,b)=(4/6,5\]
dengan nilai optimal
\[Z_+ = 3(4/6)+5(5)=27\]
Perhitungan program linier lebih tergantung pada banyaknya fungsi batasan dari pada banyaknya variabel. Jadi, apabila masalah dual diharapkan mempunyai fungsi batasan yang sedikit dibandingkan masalah primalnya, secara umum akan lebih efisien menggunakan permasalahan dual untuk memperoleh penyelesaian masalah primalnya.
Dari uraian di atas dapat disimpulkan bahwa:
- Untuk sebarang pasangan, penyelesaian awal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan lebih kecil sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
- Untuk sebarang pasangan, penyelesaian optimal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
Brigita Tiara EM / 20204920001
Karen Natalie / 20204920015
Muhammad Naufal A. / 20204920017
1 PENYELESAIAN DENGAN R
Soal no.2
Sebuah toko menyediakan dua merk pupuk, yaitu Standard dan Super. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertentu.Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Standar dan Super masing-masing $3 dan $6. Petani tersebut ingin mengetahui berapa sak masing-masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi. Buatlah fungsi tujuan, kendala, penyelesaian manual, visualisasikan permasalan dengan grafik, dan penyelesaian dengan R.
1.1 CARA 1
library(lpSolve)
fungsi_tujuan<-c(3,6)
LHS<- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
arah_kendala<-c(">=", ">=")
RHS<-c(16, 24)
# penyelesaian
model3<-lp(direction = "min",
objective.in=fungsi_tujuan,
const.mat=LHS,
const.dir=arah_kendala,
const.rhs=RHS,
all.int = T,
compute.sens = TRUE)
print(model3)
## Success: the objective function is 24
str(model3)
## List of 28
## $ direction : int 0
## $ x.count : int 2
## $ objective : num [1:2] 3 6
## $ const.count : int 2
## $ constraints : num [1:4, 1:2] 2 4 2 16 4 3 2 24
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
## .. ..$ : NULL
## $ int.count : int 2
## $ int.vec : int [1:2] 1 2
## $ bin.count : int 0
## $ binary.vec : int 0
## $ num.bin.solns : int 1
## $ objval : num 24
## $ solution : num [1:2] 6 1
## $ presolve : int 0
## $ compute.sens : int 1
## $ sens.coef.from : num [1:2] 3e+00 -1e+30
## $ sens.coef.to : num [1:2] 1e+30 6e+00
## $ duals : num [1:4] 1.5 0 0 0
## $ duals.from : num [1:4] 1.45e+01 -1.00e+30 -1.00e+30 -1.00e+30
## $ duals.to : num [1:4] 1.0e+30 1.0e+30 1.0e+30 1.5
## $ scale : int 196
## $ use.dense : int 0
## $ dense.col : int 0
## $ dense.val : num 0
## $ dense.const.nrow: int 0
## $ dense.ctr : num 0
## $ use.rw : int 0
## $ tmp : chr "Nobody will ever look at this"
## $ status : int 0
## - attr(*, "class")= chr "lp"
# jika 0 berarti penyelesaiannya berhasil
print(model3$status)
## [1] 0
# nilai optimal pada variabel x_A dan x_B
nilop<-model3$solution
names(nilop)<-c("x_A","x_B")
nilop
## x_A x_B
## 6 1
# nilai fungsi tujuan pada titik optimum
print(paste("Biaya Minimum :", model3$objval, sep=""))
## [1] "Biaya Minimum :24"
library(ggplot2)
ggplot(data.frame(x = c(0, 100
)), aes(x = x)) +
stat_function(fun = function(x) {((16-2*x)/4)}, aes(color = "Function 1")) +
stat_function(fun = function(x) {((24-4*x)/4)} , aes(color = "Function 2")) +
theme_bw() +
scale_color_discrete(name = "Function") +
geom_polygon(
data = data_frame(
x = c(0, 0, 100, Inf),
y = c(0, 50, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 1"
),
inherit.aes = FALSE, alpha = 0.4
) +
geom_polygon(
data = data.frame(
x = c(0, 0, 25, Inf),
y = c(0, 75, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 2"
),
inherit.aes = FALSE, alpha = 0.4
) +
scale_fill_discrete(name = "Constraint Set") +
scale_y_continuous(limits = c(0, 100))
1.2 CARA 2
# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c(3, 6)
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
# Set unequality signs
f.dir <- c(">=",
">=")
# Set right hand side coefficients
f.rhs <- c(16,
24)
# Final value (z)
lp("min", f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp("min", f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
# Duals lower and upper limits
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
2 METODE SIMPLEX
Selesaikan linear program berikut ini dengan metode Simplex maksimumkan:
\[Z = 2X_1 + 3X_2 + X_3 \]
Dengan fungsi kendala:
\[1) X_1 + X_2 + X_3 ≤ 9 \]
\[ 2) 2X_1 + 3X_2 ≤ 25 \]
\[3) X_2 + 2X_3 ≤ 10 \]
\[4) X_1, X_2, X_3 ≥ 0\]
Maka Fungsi objektif akan berubah menjadi :
\[Max Z = 2 x_1 + 3 x_2 + x_3 + 0 S_1 + 0 S_2 + 0 S_3\]
Dan untuk contraints akan menjadi :
\[x_1 + x_2 + x_3 + S_1 = 9\]
\[2 x_1 + 3 x_2 + S_2 = 25\]
\[x_2 + 2 x_3 + S_3 = 10\]
\[ x_1,x_2,x_3,S_1,S_2,S_3≥0\]
\[x_1=0, x_2=253,x_3=23, Max Z=77/3\]
3 PRIMAL DAN DUAL
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual. Berikan penjelasan mengenai perbedaan Primal dan Dual (berikan juga contoh soal dan penyelesaiannya).
Bentuk Primal : bentuk asli dari persamaan program linear.
Bentuk Dual : bentuk duplikat atau rangkap dari persamaan program linear.
Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan sebagai berikut:
Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi koefisien fungsi tujuan dual.
Tanda pertidaksamaan pembatas dibalik (pada primal “<=”, pada dual “>=”)
Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada dual.
Setiap kolom pada prima berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya dengan variabel keputusan primal.
Setiap baris (pembatas) padaprimal berhubungan dengan suatu kolom dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan dual.
Bentuk dual dari dual adalah primal.
Contoh :
Masalah Primal
\[Max; Z=3a+5b\]
contraints :
\[2a<=6\]
\[3b<=15\]
\[6a+4b<=24\]
\[a,c>=0\]
Masalah Dual
\[ Min; W=6y_1+15y_2+24y_3\]
contraints:
\[2y_1+6y_3>=3\]
\[3y_2+4y_3>=5\]
\[y_1,y_2,y_3>=0\]
3.1 penyelesaian optimal dual dengan tablo simplex optimal primal
Pada tablo simpleks permasalahan di atas variabel basis awalnya adalah S1, S2, dan S3 dengan koefisien-koefisien persamaan optimal Z berturut-turut adalah 0, 1, dan 1/2. Sedangkan fungsi batasan pada masalah dual yang berkaitan dengan S_1, S_2, dan S_3 berturut-turut adalah y_1 >= 0, y_2 >= 0 , dan y_3 >= 0.
Dari hal tersebut maka diperoleh informasi sebagai berikut.
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[y_1 - 0 = 0 -> y_1 = 0\] \[y_2 - 0 =1 -> y_2 =1\]
\[y_3 -0 = 1/2 -> y_3 = 1/2\]
Jadi, penyelesaian optimal masalah dual tercapai di
\[(y_1,y_2,y_3)=(1,0,1/2)\]
nilai optimal
\[W_- =6(0)=15(1)+24(1/2)=27\]
3.2 penyelesaian optimal dual dengan tablo simplex optimal dual
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[a-M=(4/6) -M -> a=4/6\]
\[b-M=5-M -> b=5\]
Jadi, penyelesaian optimal masalah primal tercapai di
\[(a,b)=(4/6,5\]
dengan nilai optimal
\[Z_+ = 3(4/6)+5(5)=27\]
Perhitungan program linier lebih tergantung pada banyaknya fungsi batasan dari pada banyaknya variabel. Jadi, apabila masalah dual diharapkan mempunyai fungsi batasan yang sedikit dibandingkan masalah primalnya, secara umum akan lebih efisien menggunakan permasalahan dual untuk memperoleh penyelesaian masalah primalnya.
Dari uraian di atas dapat disimpulkan bahwa:
- Untuk sebarang pasangan, penyelesaian awal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan lebih kecil sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
- Untuk sebarang pasangan, penyelesaian optimal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
Karen Natalie / 20204920015
Muhammad Naufal A. / 20204920017
1 PENYELESAIAN DENGAN R
Soal no.2
Sebuah toko menyediakan dua merk pupuk, yaitu Standard dan Super. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertentu.Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Standar dan Super masing-masing $3 dan $6. Petani tersebut ingin mengetahui berapa sak masing-masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi. Buatlah fungsi tujuan, kendala, penyelesaian manual, visualisasikan permasalan dengan grafik, dan penyelesaian dengan R.
1.1 CARA 1
library(lpSolve)
fungsi_tujuan<-c(3,6)
LHS<- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
arah_kendala<-c(">=", ">=")
RHS<-c(16, 24)
# penyelesaian
model3<-lp(direction = "min",
objective.in=fungsi_tujuan,
const.mat=LHS,
const.dir=arah_kendala,
const.rhs=RHS,
all.int = T,
compute.sens = TRUE)
print(model3)
## Success: the objective function is 24
str(model3)
## List of 28
## $ direction : int 0
## $ x.count : int 2
## $ objective : num [1:2] 3 6
## $ const.count : int 2
## $ constraints : num [1:4, 1:2] 2 4 2 16 4 3 2 24
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
## .. ..$ : NULL
## $ int.count : int 2
## $ int.vec : int [1:2] 1 2
## $ bin.count : int 0
## $ binary.vec : int 0
## $ num.bin.solns : int 1
## $ objval : num 24
## $ solution : num [1:2] 6 1
## $ presolve : int 0
## $ compute.sens : int 1
## $ sens.coef.from : num [1:2] 3e+00 -1e+30
## $ sens.coef.to : num [1:2] 1e+30 6e+00
## $ duals : num [1:4] 1.5 0 0 0
## $ duals.from : num [1:4] 1.45e+01 -1.00e+30 -1.00e+30 -1.00e+30
## $ duals.to : num [1:4] 1.0e+30 1.0e+30 1.0e+30 1.5
## $ scale : int 196
## $ use.dense : int 0
## $ dense.col : int 0
## $ dense.val : num 0
## $ dense.const.nrow: int 0
## $ dense.ctr : num 0
## $ use.rw : int 0
## $ tmp : chr "Nobody will ever look at this"
## $ status : int 0
## - attr(*, "class")= chr "lp"
# jika 0 berarti penyelesaiannya berhasil
print(model3$status)
## [1] 0
# nilai optimal pada variabel x_A dan x_B
nilop<-model3$solution
names(nilop)<-c("x_A","x_B")
nilop
## x_A x_B
## 6 1
# nilai fungsi tujuan pada titik optimum
print(paste("Biaya Minimum :", model3$objval, sep=""))
## [1] "Biaya Minimum :24"
library(ggplot2)
ggplot(data.frame(x = c(0, 100
)), aes(x = x)) +
stat_function(fun = function(x) {((16-2*x)/4)}, aes(color = "Function 1")) +
stat_function(fun = function(x) {((24-4*x)/4)} , aes(color = "Function 2")) +
theme_bw() +
scale_color_discrete(name = "Function") +
geom_polygon(
data = data_frame(
x = c(0, 0, 100, Inf),
y = c(0, 50, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 1"
),
inherit.aes = FALSE, alpha = 0.4
) +
geom_polygon(
data = data.frame(
x = c(0, 0, 25, Inf),
y = c(0, 75, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 2"
),
inherit.aes = FALSE, alpha = 0.4
) +
scale_fill_discrete(name = "Constraint Set") +
scale_y_continuous(limits = c(0, 100))
1.2 CARA 2
# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c(3, 6)
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
# Set unequality signs
f.dir <- c(">=",
">=")
# Set right hand side coefficients
f.rhs <- c(16,
24)
# Final value (z)
lp("min", f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp("min", f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
# Duals lower and upper limits
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
2 METODE SIMPLEX
Selesaikan linear program berikut ini dengan metode Simplex maksimumkan:
\[Z = 2X_1 + 3X_2 + X_3 \]
Dengan fungsi kendala:
\[1) X_1 + X_2 + X_3 ≤ 9 \]
\[ 2) 2X_1 + 3X_2 ≤ 25 \]
\[3) X_2 + 2X_3 ≤ 10 \]
\[4) X_1, X_2, X_3 ≥ 0\]
Maka Fungsi objektif akan berubah menjadi :
\[Max Z = 2 x_1 + 3 x_2 + x_3 + 0 S_1 + 0 S_2 + 0 S_3\]
Dan untuk contraints akan menjadi :
\[x_1 + x_2 + x_3 + S_1 = 9\]
\[2 x_1 + 3 x_2 + S_2 = 25\]
\[x_2 + 2 x_3 + S_3 = 10\]
\[ x_1,x_2,x_3,S_1,S_2,S_3≥0\]
\[x_1=0, x_2=253,x_3=23, Max Z=77/3\]
3 PRIMAL DAN DUAL
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual. Berikan penjelasan mengenai perbedaan Primal dan Dual (berikan juga contoh soal dan penyelesaiannya).
Bentuk Primal : bentuk asli dari persamaan program linear.
Bentuk Dual : bentuk duplikat atau rangkap dari persamaan program linear.
Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan sebagai berikut:
Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi koefisien fungsi tujuan dual.
Tanda pertidaksamaan pembatas dibalik (pada primal “<=”, pada dual “>=”)
Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada dual.
Setiap kolom pada prima berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya dengan variabel keputusan primal.
Setiap baris (pembatas) padaprimal berhubungan dengan suatu kolom dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan dual.
Bentuk dual dari dual adalah primal.
Contoh :
Masalah Primal
\[Max; Z=3a+5b\]
contraints :
\[2a<=6\]
\[3b<=15\]
\[6a+4b<=24\]
\[a,c>=0\]
Masalah Dual
\[ Min; W=6y_1+15y_2+24y_3\]
contraints:
\[2y_1+6y_3>=3\]
\[3y_2+4y_3>=5\]
\[y_1,y_2,y_3>=0\]
3.1 penyelesaian optimal dual dengan tablo simplex optimal primal
Pada tablo simpleks permasalahan di atas variabel basis awalnya adalah S1, S2, dan S3 dengan koefisien-koefisien persamaan optimal Z berturut-turut adalah 0, 1, dan 1/2. Sedangkan fungsi batasan pada masalah dual yang berkaitan dengan S_1, S_2, dan S_3 berturut-turut adalah y_1 >= 0, y_2 >= 0 , dan y_3 >= 0.
Dari hal tersebut maka diperoleh informasi sebagai berikut.
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[y_1 - 0 = 0 -> y_1 = 0\] \[y_2 - 0 =1 -> y_2 =1\]
\[y_3 -0 = 1/2 -> y_3 = 1/2\]
Jadi, penyelesaian optimal masalah dual tercapai di
\[(y_1,y_2,y_3)=(1,0,1/2)\]
nilai optimal
\[W_- =6(0)=15(1)+24(1/2)=27\]
3.2 penyelesaian optimal dual dengan tablo simplex optimal dual
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[a-M=(4/6) -M -> a=4/6\]
\[b-M=5-M -> b=5\]
Jadi, penyelesaian optimal masalah primal tercapai di
\[(a,b)=(4/6,5\]
dengan nilai optimal
\[Z_+ = 3(4/6)+5(5)=27\]
Perhitungan program linier lebih tergantung pada banyaknya fungsi batasan dari pada banyaknya variabel. Jadi, apabila masalah dual diharapkan mempunyai fungsi batasan yang sedikit dibandingkan masalah primalnya, secara umum akan lebih efisien menggunakan permasalahan dual untuk memperoleh penyelesaian masalah primalnya.
Dari uraian di atas dapat disimpulkan bahwa:
- Untuk sebarang pasangan, penyelesaian awal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan lebih kecil sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
- Untuk sebarang pasangan, penyelesaian optimal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
Muhammad Naufal A. / 20204920017
1 PENYELESAIAN DENGAN R
Soal no.2
Sebuah toko menyediakan dua merk pupuk, yaitu Standard dan Super. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertentu.Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Standar dan Super masing-masing $3 dan $6. Petani tersebut ingin mengetahui berapa sak masing-masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi. Buatlah fungsi tujuan, kendala, penyelesaian manual, visualisasikan permasalan dengan grafik, dan penyelesaian dengan R.
1.1 CARA 1
library(lpSolve)
fungsi_tujuan<-c(3,6)
LHS<- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
arah_kendala<-c(">=", ">=")
RHS<-c(16, 24)
# penyelesaian
model3<-lp(direction = "min",
objective.in=fungsi_tujuan,
const.mat=LHS,
const.dir=arah_kendala,
const.rhs=RHS,
all.int = T,
compute.sens = TRUE)
print(model3)
## Success: the objective function is 24
str(model3)
## List of 28
## $ direction : int 0
## $ x.count : int 2
## $ objective : num [1:2] 3 6
## $ const.count : int 2
## $ constraints : num [1:4, 1:2] 2 4 2 16 4 3 2 24
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
## .. ..$ : NULL
## $ int.count : int 2
## $ int.vec : int [1:2] 1 2
## $ bin.count : int 0
## $ binary.vec : int 0
## $ num.bin.solns : int 1
## $ objval : num 24
## $ solution : num [1:2] 6 1
## $ presolve : int 0
## $ compute.sens : int 1
## $ sens.coef.from : num [1:2] 3e+00 -1e+30
## $ sens.coef.to : num [1:2] 1e+30 6e+00
## $ duals : num [1:4] 1.5 0 0 0
## $ duals.from : num [1:4] 1.45e+01 -1.00e+30 -1.00e+30 -1.00e+30
## $ duals.to : num [1:4] 1.0e+30 1.0e+30 1.0e+30 1.5
## $ scale : int 196
## $ use.dense : int 0
## $ dense.col : int 0
## $ dense.val : num 0
## $ dense.const.nrow: int 0
## $ dense.ctr : num 0
## $ use.rw : int 0
## $ tmp : chr "Nobody will ever look at this"
## $ status : int 0
## - attr(*, "class")= chr "lp"
# jika 0 berarti penyelesaiannya berhasil
print(model3$status)
## [1] 0
# nilai optimal pada variabel x_A dan x_B
nilop<-model3$solution
names(nilop)<-c("x_A","x_B")
nilop
## x_A x_B
## 6 1
# nilai fungsi tujuan pada titik optimum
print(paste("Biaya Minimum :", model3$objval, sep=""))
## [1] "Biaya Minimum :24"
library(ggplot2)
ggplot(data.frame(x = c(0, 100
)), aes(x = x)) +
stat_function(fun = function(x) {((16-2*x)/4)}, aes(color = "Function 1")) +
stat_function(fun = function(x) {((24-4*x)/4)} , aes(color = "Function 2")) +
theme_bw() +
scale_color_discrete(name = "Function") +
geom_polygon(
data = data_frame(
x = c(0, 0, 100, Inf),
y = c(0, 50, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 1"
),
inherit.aes = FALSE, alpha = 0.4
) +
geom_polygon(
data = data.frame(
x = c(0, 0, 25, Inf),
y = c(0, 75, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 2"
),
inherit.aes = FALSE, alpha = 0.4
) +
scale_fill_discrete(name = "Constraint Set") +
scale_y_continuous(limits = c(0, 100))
1.2 CARA 2
# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c(3, 6)
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
# Set unequality signs
f.dir <- c(">=",
">=")
# Set right hand side coefficients
f.rhs <- c(16,
24)
# Final value (z)
lp("min", f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp("min", f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
# Duals lower and upper limits
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to
2 METODE SIMPLEX
Selesaikan linear program berikut ini dengan metode Simplex maksimumkan:
\[Z = 2X_1 + 3X_2 + X_3 \]
Dengan fungsi kendala:
\[1) X_1 + X_2 + X_3 ≤ 9 \]
\[ 2) 2X_1 + 3X_2 ≤ 25 \]
\[3) X_2 + 2X_3 ≤ 10 \]
\[4) X_1, X_2, X_3 ≥ 0\]
Maka Fungsi objektif akan berubah menjadi :
\[Max Z = 2 x_1 + 3 x_2 + x_3 + 0 S_1 + 0 S_2 + 0 S_3\]
Dan untuk contraints akan menjadi :
\[x_1 + x_2 + x_3 + S_1 = 9\]
\[2 x_1 + 3 x_2 + S_2 = 25\]
\[x_2 + 2 x_3 + S_3 = 10\]
\[ x_1,x_2,x_3,S_1,S_2,S_3≥0\]
\[x_1=0, x_2=253,x_3=23, Max Z=77/3\]
3 PRIMAL DAN DUAL
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual. Berikan penjelasan mengenai perbedaan Primal dan Dual (berikan juga contoh soal dan penyelesaiannya).
Bentuk Primal : bentuk asli dari persamaan program linear.
Bentuk Dual : bentuk duplikat atau rangkap dari persamaan program linear.
Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan sebagai berikut:
Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi koefisien fungsi tujuan dual.
Tanda pertidaksamaan pembatas dibalik (pada primal “<=”, pada dual “>=”)
Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada dual.
Setiap kolom pada prima berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya dengan variabel keputusan primal.
Setiap baris (pembatas) padaprimal berhubungan dengan suatu kolom dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan dual.
Bentuk dual dari dual adalah primal.
Contoh :
Masalah Primal
\[Max; Z=3a+5b\]
contraints :
\[2a<=6\]
\[3b<=15\]
\[6a+4b<=24\]
\[a,c>=0\]
Masalah Dual
\[ Min; W=6y_1+15y_2+24y_3\]
contraints:
\[2y_1+6y_3>=3\]
\[3y_2+4y_3>=5\]
\[y_1,y_2,y_3>=0\]
3.1 penyelesaian optimal dual dengan tablo simplex optimal primal
Pada tablo simpleks permasalahan di atas variabel basis awalnya adalah S1, S2, dan S3 dengan koefisien-koefisien persamaan optimal Z berturut-turut adalah 0, 1, dan 1/2. Sedangkan fungsi batasan pada masalah dual yang berkaitan dengan S_1, S_2, dan S_3 berturut-turut adalah y_1 >= 0, y_2 >= 0 , dan y_3 >= 0.
Dari hal tersebut maka diperoleh informasi sebagai berikut.
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[y_1 - 0 = 0 -> y_1 = 0\] \[y_2 - 0 =1 -> y_2 =1\]
\[y_3 -0 = 1/2 -> y_3 = 1/2\]
Jadi, penyelesaian optimal masalah dual tercapai di
\[(y_1,y_2,y_3)=(1,0,1/2)\]
nilai optimal
\[W_- =6(0)=15(1)+24(1/2)=27\]
3.2 penyelesaian optimal dual dengan tablo simplex optimal dual
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[a-M=(4/6) -M -> a=4/6\]
\[b-M=5-M -> b=5\]
Jadi, penyelesaian optimal masalah primal tercapai di
\[(a,b)=(4/6,5\]
dengan nilai optimal
\[Z_+ = 3(4/6)+5(5)=27\]
Perhitungan program linier lebih tergantung pada banyaknya fungsi batasan dari pada banyaknya variabel. Jadi, apabila masalah dual diharapkan mempunyai fungsi batasan yang sedikit dibandingkan masalah primalnya, secara umum akan lebih efisien menggunakan permasalahan dual untuk memperoleh penyelesaian masalah primalnya.
Dari uraian di atas dapat disimpulkan bahwa:
- Untuk sebarang pasangan, penyelesaian awal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan lebih kecil sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
- Untuk sebarang pasangan, penyelesaian optimal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
1 PENYELESAIAN DENGAN R
Soal no.2
Sebuah toko menyediakan dua merk pupuk, yaitu Standard dan Super. Setiap jenis mengandung campuran bahan nitrogen dan fosfat dalam jumlah tertentu.Seorang petani membutuhkan paling sedikit 16 kg nitrogen dan 24 kg fosfat untuk lahan pertaniannya. Harga pupuk Standar dan Super masing-masing $3 dan $6. Petani tersebut ingin mengetahui berapa sak masing-masing jenis pupuk harus dibeli agar total harga pupuk mencapai minimum dan kebutuhan pupuk untuk lahannya terpenuhi. Buatlah fungsi tujuan, kendala, penyelesaian manual, visualisasikan permasalan dengan grafik, dan penyelesaian dengan R.
1.1 CARA 1
library(lpSolve)
fungsi_tujuan<-c(3,6)
LHS<- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
arah_kendala<-c(">=", ">=")
RHS<-c(16, 24)
# penyelesaian
model3<-lp(direction = "min",
objective.in=fungsi_tujuan,
const.mat=LHS,
const.dir=arah_kendala,
const.rhs=RHS,
all.int = T,
compute.sens = TRUE)
print(model3)## Success: the objective function is 24str(model3)## List of 28
## $ direction : int 0
## $ x.count : int 2
## $ objective : num [1:2] 3 6
## $ const.count : int 2
## $ constraints : num [1:4, 1:2] 2 4 2 16 4 3 2 24
## ..- attr(*, "dimnames")=List of 2
## .. ..$ : chr [1:4] "" "" "const.dir.num" "const.rhs"
## .. ..$ : NULL
## $ int.count : int 2
## $ int.vec : int [1:2] 1 2
## $ bin.count : int 0
## $ binary.vec : int 0
## $ num.bin.solns : int 1
## $ objval : num 24
## $ solution : num [1:2] 6 1
## $ presolve : int 0
## $ compute.sens : int 1
## $ sens.coef.from : num [1:2] 3e+00 -1e+30
## $ sens.coef.to : num [1:2] 1e+30 6e+00
## $ duals : num [1:4] 1.5 0 0 0
## $ duals.from : num [1:4] 1.45e+01 -1.00e+30 -1.00e+30 -1.00e+30
## $ duals.to : num [1:4] 1.0e+30 1.0e+30 1.0e+30 1.5
## $ scale : int 196
## $ use.dense : int 0
## $ dense.col : int 0
## $ dense.val : num 0
## $ dense.const.nrow: int 0
## $ dense.ctr : num 0
## $ use.rw : int 0
## $ tmp : chr "Nobody will ever look at this"
## $ status : int 0
## - attr(*, "class")= chr "lp"# jika 0 berarti penyelesaiannya berhasil
print(model3$status)## [1] 0# nilai optimal pada variabel x_A dan x_B
nilop<-model3$solution
names(nilop)<-c("x_A","x_B")
nilop## x_A x_B
## 6 1# nilai fungsi tujuan pada titik optimum
print(paste("Biaya Minimum :", model3$objval, sep=""))## [1] "Biaya Minimum :24"library(ggplot2)
ggplot(data.frame(x = c(0, 100
)), aes(x = x)) +
stat_function(fun = function(x) {((16-2*x)/4)}, aes(color = "Function 1")) +
stat_function(fun = function(x) {((24-4*x)/4)} , aes(color = "Function 2")) +
theme_bw() +
scale_color_discrete(name = "Function") +
geom_polygon(
data = data_frame(
x = c(0, 0, 100, Inf),
y = c(0, 50, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 1"
),
inherit.aes = FALSE, alpha = 0.4
) +
geom_polygon(
data = data.frame(
x = c(0, 0, 25, Inf),
y = c(0, 75, 0, 0)
),
aes(
x = x, y = y, fill = "Constraint 2"
),
inherit.aes = FALSE, alpha = 0.4
) +
scale_fill_discrete(name = "Constraint Set") +
scale_y_continuous(limits = c(0, 100))1.2 CARA 2
# Import lpSolve package
library(lpSolve)
# Set coefficients of the objective function
f.obj <- c(3, 6)
# Set matrix corresponding to coefficients of constraints by rows
# Do not consider the non-negative constraint; it is automatically assumed
f.con <- matrix(c(2, 4,
4, 3), nrow = 2, byrow = TRUE)
# Set unequality signs
f.dir <- c(">=",
">=")
# Set right hand side coefficients
f.rhs <- c(16,
24)
# Final value (z)
lp("min", f.obj, f.con, f.dir, f.rhs)
# Variables final values
lp("min", f.obj, f.con, f.dir, f.rhs)$solution
# Sensitivities
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to
# Dual Values (first dual of the constraints and then dual of the variables)
# Duals of the constraints and variables are mixed
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals
# Duals lower and upper limits
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
lp("min", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to2 METODE SIMPLEX
Selesaikan linear program berikut ini dengan metode Simplex maksimumkan:
\[Z = 2X_1 + 3X_2 + X_3 \]
Dengan fungsi kendala:
\[1) X_1 + X_2 + X_3 ≤ 9 \]
\[ 2) 2X_1 + 3X_2 ≤ 25 \]
\[3) X_2 + 2X_3 ≤ 10 \]
\[4) X_1, X_2, X_3 ≥ 0\]
Maka Fungsi objektif akan berubah menjadi :
\[Max Z = 2 x_1 + 3 x_2 + x_3 + 0 S_1 + 0 S_2 + 0 S_3\]
Dan untuk contraints akan menjadi :
\[x_1 + x_2 + x_3 + S_1 = 9\]
\[2 x_1 + 3 x_2 + S_2 = 25\]
\[x_2 + 2 x_3 + S_3 = 10\]
\[ x_1,x_2,x_3,S_1,S_2,S_3≥0\]
\[x_1=0, x_2=253,x_3=23, Max Z=77/3\]
3 PRIMAL DAN DUAL
Dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual. Berikan penjelasan mengenai perbedaan Primal dan Dual (berikan juga contoh soal dan penyelesaiannya).
Bentuk Primal : bentuk asli dari persamaan program linear.
Bentuk Dual : bentuk duplikat atau rangkap dari persamaan program linear.
Bila masalah primal dibandingkan dengan masalah dual, terlihat beberapa hubungan sebagai berikut:
Koefisien fungsi tujuan masalah primal (c) menjadi konstanta ruas kanan pembatas dual. Sebaliknya, konstanta ruas kanan pembatas dual menjadi koefisien fungsi tujuan dual.
Tanda pertidaksamaan pembatas dibalik (pada primal “<=”, pada dual “>=”)
Tujuan berubah dari min (maks) pada primal menjadi maks (min) pada dual.
Setiap kolom pada prima berhubungan dengan suatu baris (kendala) dalam dual. Sehingga banyaknya pembatas dual akan sama banyaknya dengan variabel keputusan primal.
Setiap baris (pembatas) padaprimal berhubungan dengan suatu kolom dalam dual. Sehingga setiap pembatas primal ada satu variabel keputusan dual.
Bentuk dual dari dual adalah primal.
Contoh :
Masalah Primal
\[Max; Z=3a+5b\]
contraints :
\[2a<=6\]
\[3b<=15\]
\[6a+4b<=24\]
\[a,c>=0\]
Masalah Dual
\[ Min; W=6y_1+15y_2+24y_3\]
contraints:
\[2y_1+6y_3>=3\]
\[3y_2+4y_3>=5\]
\[y_1,y_2,y_3>=0\]
3.1 penyelesaian optimal dual dengan tablo simplex optimal primal
Pada tablo simpleks permasalahan di atas variabel basis awalnya adalah S1, S2, dan S3 dengan koefisien-koefisien persamaan optimal Z berturut-turut adalah 0, 1, dan 1/2. Sedangkan fungsi batasan pada masalah dual yang berkaitan dengan S_1, S_2, dan S_3 berturut-turut adalah y_1 >= 0, y_2 >= 0 , dan y_3 >= 0.
Dari hal tersebut maka diperoleh informasi sebagai berikut.
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[y_1 - 0 = 0 -> y_1 = 0\] \[y_2 - 0 =1 -> y_2 =1\]
\[y_3 -0 = 1/2 -> y_3 = 1/2\]
Jadi, penyelesaian optimal masalah dual tercapai di
\[(y_1,y_2,y_3)=(1,0,1/2)\]
nilai optimal
\[W_- =6(0)=15(1)+24(1/2)=27\]
3.2 penyelesaian optimal dual dengan tablo simplex optimal dual
Dari informasi tersebut selanjutnya dapat diperoleh penyelesaian optimal dari masalah dual, yaitu:
\[a-M=(4/6) -M -> a=4/6\]
\[b-M=5-M -> b=5\]
Jadi, penyelesaian optimal masalah primal tercapai di
\[(a,b)=(4/6,5\]
dengan nilai optimal
\[Z_+ = 3(4/6)+5(5)=27\]
Perhitungan program linier lebih tergantung pada banyaknya fungsi batasan dari pada banyaknya variabel. Jadi, apabila masalah dual diharapkan mempunyai fungsi batasan yang sedikit dibandingkan masalah primalnya, secara umum akan lebih efisien menggunakan permasalahan dual untuk memperoleh penyelesaian masalah primalnya.
Dari uraian di atas dapat disimpulkan bahwa:
- Untuk sebarang pasangan, penyelesaian awal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan lebih kecil sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.
- Untuk sebarang pasangan, penyelesaian optimal masalah primal dan masalah dual berlaku:
Nilai fungsi tujuan dalam masalah memaksimumkan sama dengan Nilai fungsi tujuan dalam masalah meminimumkan.