Contoh Program Linear di Python & R

Contoh Program Linear dengan Python dan R¶

Catatan kuliah MA3071 20210920
Diberikan masalah program linear sebagai berikut :

• Minimumkan $z=-2x_1-3x_2$
• Terhadap kendala :
  • $x_1+2x_2\leq 12$
  • $2x_1+x_2\leq 9$
  • $4x_1+3x_2\leq 35$
  • $x_1,x_2\geq 0$

---

Penyelesaian dengan metode simplex sudah dipelajari di kelas

Selesaikan dengan Python¶

In [1]:

import numpy as np
from scipy.optimize import linprog

## Kendala harus dalam bentuk Ax<=b
#Maktriks kendala
A = np.array([[1,2], [2,1], [4,3]])
#Koefisien ruas kanan
b = np.array([12,9,35])

#Koefisien fungsi objektif (cost)
c = np.array([-2,-3])

#Selesaikan masalah program linear
res = linprog(c, A_ub=A, b_ub=b)
print(res)

     con: array([], dtype=float64)
     fun: -18.999999910103906
 message: 'Optimization terminated successfully.'
     nit: 5
   slack: array([4.71281076e-08, 8.11758518e-08, 1.20000002e+01])
  status: 0
 success: True
       x: array([1.99999996, 5.        ])

/usr/local/lib/python3.7/dist-packages/numpy/core/fromnumeric.py:87: VisibleDeprecationWarning: Creating an ndarray from ragged nested sequences (which is a list-or-tuple of lists-or-tuples-or ndarrays with different lengths or shapes) is deprecated. If you meant to do this, you must specify 'dtype=object' when creating the ndarray
  return ufunc.reduce(obj, axis, dtype, out, **passkwargs)

Selesaikan dengan R¶

Untuk menggunakan R pada google colab, jalankan kode berikut

%load_ext rpy2.ipython

Setelah kode di atas dijalankan, pada awal cell, kita harus menambahkah %%R agar cell tersebut dieksekusi oleh R, bukan oleh python

In [2]:

%load_ext rpy2.ipython

In [3]:

%%R
install.packages("linprog")
library("linprog")

R[write to console]: Loading required package: lpSolve

In [4]:

%%R
library(linprog)
library(lpSolve)

## Kendala harus dalam bentuk Ax<=b
#Maktriks kendala
Amat <- rbind( c( 1,2 ),
               c( 2,1 ),
               c( 4,3 ))
#Koefisien ruas kanan
bvec <- c(12,9,35) #ruas kanan
##Bentuk pertidak samaan untuk setiap baris kendala
ineq=c("<=","<=","<=") 
#andaikan kendala kedua adalah 2x_1 +x_2 >= 9, maka ineq=c("<=",">=","<=")

#Koefisien fungsi objektif (cost)
cvec <- c(-2,-3) #cost

#Selesaikan masalah program linear
res <- solveLP( cvec, bvec, Amat, FALSE, const.dir = ineq )
print(res)

Results of Linear Programming / Linear Optimization

Objective function (Minimum): -19 

Iterations in phase 1: 0
Iterations in phase 2: 2
Solution
  opt
1   2
2   5

Basic Variables
    opt
1     2
2     5
S 3  12

Constraints
  actual dir bvec free     dual dual.reg
1     12  <=   12    0 1.333333      7.5
2      9  <=    9    0 0.333333      3.0
3     23  <=   35   12 0.000000     12.0

All Variables (including slack variables)
    opt cvec     min.c max.c     marg marg.reg
1     2   -2 -2.000000  -1.5       NA       NA
2     5   -3  2.000000  -1.0       NA       NA
S 1   0    0 -1.333333   Inf 1.333333      7.5
S 2   0    0 -0.333333   Inf 0.333333      3.0
S 3  12    0 -0.200000    NA 0.000000       NA

Hasil dari Python dan R sesuai dengan apa yang kita pelajari di kelas.

• Fungsi objektif : $z=-19$
• $x_1=2$ dan $x_2=5$
• Slack Variabel $x_3=0, x_4=0$ dan $x_5=12$
• Vektor Reduced Cost $c_B^TB^{-1}N-c_N^T=\begin{bmatrix}-4/3\\-1/3\end{bmatrix}$