Linear Programming

Linear Programming merupakan topik bahasan dasar jika kamu mengambil Mata Kuliah Riset Operasi yang fokus terhadap masalah-masalah dataset yang bersifat linear dengan beragam contraint dan variabel.   Yuk coba library untuk memecahkan kasus-kasus seperti Linear Programming dan Simplex dengan menggunakan GLPK https://www.gnu.org/software/glpk/ . Salah satunya optlang yang merupakan interface terhadap GLPK, mari kita coba bandingkan dengan scipy. Agar lebih mudah, penulis langsung comot contoh kasus Linear Programming dan Simplex dari situs yang sudah ada sehingga bagi kalian yang belum paham apa itu Linear Programming dan Simplex bisa sekalian belajar dasar-dasarnya.

Contoh sederhana pada linear programming bisa diambil di link berikut

PT. LUNATEKSTIL 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 juta untuk kain sutera dan Rp 30 juta untuk kain wol. Masalahnya adalah bagaimana menentukan jumlah unit setiap jenis produk yang akan diproduksi setiap hari agar keuntungan yang diperoleh bisa maksimal?

Penulis menggunakan library ada 2 yaitu optlang dan scipy, untuk library optlang bisa download di https://github.com/biosustain/optlang;  kalau mau belajar cara install python bisa beli buku penulis di buku-belajar-mudah-python

from optlang import Model, Variable, Constraint, Objective


x1 = Variable('x1',lb=1)
x2 = Variable('x2',lb=1)


c1 = Constraint(4*x1+3*x2,ub=240)
c2 = Constraint(2*x1+x2,ub=100)
obj = Objective(700*x1+500*x2,direction='max')
model = Model(name='Linear Programming')
model.objective = obj
model.add([c1, c2])


status = model.optimize()

print("Status:", model.status)
print("Fungsi Objektif:", model.objective.value)
print("----------")
for var_name, var in model.variables.iteritems():
    print(var_name, "=", var.primal)

hasil

Status: optimal
Fungsi Objektif: 41000.0
----------
x1 = 30.0
x2 = 40.0

Kalau menggunakan scipy agak sedikit berbeda, seperti berikut https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linprog.html

import numpy as np
from scipy.optimize import linprog


c = np.array([700,500])
A = np.array([[4,3],[2,1]])
b = np.array([240,100])
x1_bound = (0,None)
x2_bound = (0,None)


#LP pada scipy hanya support pada fungsi minimisasi saja
#This LP problem has a maximize objective function and linprog supports minimize problems. To solve it:
res = linprog(-c, A_ub=A, b_ub=b, bounds=(x1_bound,x2_bound),method='simplex',options={"disp": True})
print(res)
print('\n')
print(f'x1 = {res.x[0]}, x2 = {res.x[1]}, z = {res.fun*-1}')

hasil

Optimization terminated successfully.
         Current function value: -41000.000000
         Iterations: 2
     con: array([], dtype=float64)
     fun: -41000.0
 message: 'Optimization terminated successfully.'
     nit: 2
   slack: array([0., 0.])
  status: 0
 success: True
       x: array([30., 40.])


x1 = 30.0, x2 = 40.0, z = 41000.0

Operasi Simplex

Pada kasus simplex bisa ditemui di https://duniakumu.com/program-linier-metode-simplekpengertiancontoh-soallinear-programming-metode-simpleksbeberapa-istilah-dalam-metode-simplek/

Kamu bisa menggunakan optlang sesuai dengan kode berikut

from optlang import Model, Variable, Constraint, Objective


x1 = Variable('x1',lb=0)
x2 = Variable('x2',lb=0)


c1 = Constraint(2*x1,ub=8)
c2 = Constraint(3*x2,ub=15)
c3 = Constraint(6*x1+5*x2,ub=30)
obj = Objective(3*x1+5*x2,direction='max')
model = Model(name='Simple model')
model.objective = obj
model.add([c1, c2,c3])


status = model.optimize()

print("status:", model.status)
print("objective value:", model.objective.value)
print("----------")
for var_name, var in model.variables.iteritems():
    print(var_name, "=", var.primal)

hasil

status: optimal
objective value: 27.5
----------
x1 = 0.8333333333333334
x2 = 5.0

Atau menggunakan scipy

import numpy as np
from scipy.optimize import linprog


c = np.array([3,5])
A = np.array([[2,0],[0,3],[6,5]])
b = np.array([8,15,30])
x1_bound = (0,None)
x2_bound = (0,None)



res = linprog(-c, A_ub=A, b_ub=b, bounds=(x1_bound,x2_bound),method='simplex',options={"disp": True})
print(res)
print('\n')
print(f'x1 = {res.x[0]}, x2 = {res.x[1]}, z = {res.fun*-1}')

hasil

Optimization terminated successfully.
         Current function value: -27.500000  
         Iterations: 3
     con: array([], dtype=float64)
     fun: -27.5
 message: 'Optimization terminated successfully.'
     nit: 3
   slack: array([6.33333333, 0.        , 0.        ])
  status: 0
 success: True
       x: array([0.83333333, 5.        ])


x1 = 0.8333333333333335, x2 = 5.0, z = 27.5

Sangat mudah bukan?