Solusi Manual

Mari kita mulai dengan membuat grafik masalah ini dengan Python. Dalam artikel ini saya akan menjalankan Python dengan Rstudio. Oleh karena itu, anda perlu install Anaconda pada PC/Komputer anda, dan jangan lupa melakukan upgrade python tersebut menggukan CMD.exe pada anaconda navigator dengan menjalankan koding berikut:

conda update --all
conda create -n py3_9_13 python=3.9.13
conda activate py3_9_13

Kemudian jalankan koding berikut:

library(reticulate)
library(Rcpp)
# conda_list() 
use_condaenv("py3_9_13", required = TRUE)

Setelah itu, anda dapan menjalankan koding python pada Rstudio dengan mengganti berikut ini,

` ` `{r}

# Ini contoh Chunk pada koding R

` ` `

menjadi chunk seperti berikut,

` ` `{python}

import numpy as np
import matplotlib.pyplot as plt

# Construct lines
x = np.linspace(0, 20, 2000)              # x > 0
y1 = (x*0) + 2                            # y >= 2
y2 = (25-x)/2.0                           # 2y <= 25 - x
y3 = (2*x-8)/4.0                          # 4y >= 2x - 8 
y4 = 2 * x -5                             # y <= 2x - 5 

# Make plot
plt.plot(x, y1, label=r'$y\geq2$')
plt.plot(x, y2, label=r'$2y\leq25-x$')
plt.plot(x, y3, label=r'$4y\geq 2x - 8$')
plt.plot(x, y4, label=r'$y\leq 2x-5$')
plt.xlim((0, 16))
plt.ylim((0, 11))
plt.xlabel(r'$x$')
plt.ylabel(r'$y$')

# Fill feasible region
y5 = np.minimum(y2, y4)
y6 = np.maximum(y1, y3)
plt.fill_between(x, y5, y6, where=y5>y6, color='grey', alpha=0.5)
plt.legend(bbox_to_anchor=(1.05, 1), loc=2, borderaxespad=0.)

` ` `

## (0.0, 16.0)

## (0.0, 11.0)

Berdasarkan grafik di atas dapat disimpulkan bahwa daerah abu-abu adalah solusi kemungkinan optimasi minimum dan maksimal. Dalam contoh ini, terdapat 4 simpul kemungkinan yang menjadi daerah penyelesaian yang dinyatakan pada persamaan 3, untuk kita dapat menemukan solusi sesuai untuk setiap simpul maksimum.

\[ \begin{align*} &Line \space 1 & & Line \space 2& \\ y & \geq 2 & 4y & \geq 2x-8 \\ \tag{3} 2y & \leq 25-x & y & \leq 2x-5 \\ 4y & \geq 2x-8 & 2y & \leq 25-x \\ y & \leq 2x-5 & y & \leq 2 \end{align*} \]

Sehingga dengan demikian, maka kita dapat menghitung \(Z\) untuk setiap simpul sebagai berikut:

• Simpul Pertama

\[ \begin{align*} y \geq 2 \space & \text{dan} \space 4y≥2x–8, \\ \\ 2 & ={2x–8 \over 4} \\ \tag{4} x & =8 \\ y & =2 \\ Z & =(4\times 8)+ (3\times 2)=38 \\ \end{align*} \]

• Simpul Kedua

\[ \begin{align*} 2y \leq 25–x \space &\text{dan} \space y\leq 2x–5, \\ \\ {25–x \over 2} & = 2x–5 \\ \tag{5} x & = 7 \\ y & = 9 \\ Z & =(4 \times 7) + (3 \times 9)=55 \end{align*} \]

• Simpul Ketiga

\[ \begin{align*} 2y & \leq 25–x \space \text{dan} \space 4y\geq 2x–8, \\ \\ {25–x \over 2} & = {2x–8 \over 4}\\ \tag{6} x & =14.5\\ y & =5.25\\ Z &=(4\times 14.5)+(3\times 5.25)=73.75 \end{align*} \]

• Simpul Keempat

\[ \begin{align*} 2y & \leq 25–x \space \text{dan} \space 4y\geq 2x–8, \\ \\ {25–x \over 2} & = {2x–8 \over 4}\\ \tag{7} x & =14.5\\ y & =5.25\\ Z &=(4\times 14.5)+(3\times 5.25)=73.75 \end{align*} \]

Dari keempat simpul yang tersebut diatas, dapat disimpulkan bahwa nilai maksimum untuk \(Z\) adalah \(73.75,\) ketika \(x\) adalah \(14.5\) dan \(y\) adalah \(5.25.\)

Catatan: Metode pengujian setiap simpul ini hanya layak untuk sejumlah kecil variabel dan kendala. Sehingga, pada saat jumlah kendala dan variabel bertambah banyak maka akan semakin sulit untuk membuat grafik masalah ini dan menyelesaikan semua simpulnya. Misalnya saja, ada tiga variabel; \[Z=Ax+By+Cz\]. Maka, anda harus membuat grafik dalam tiga dimensi \((x, y\) dan \(z).\)

Untuk mengatasi permasalahan tersebut, berikutnya akan diperlihatkan bagaimana anda dapat menggunakan python dan menggunajan library pulp untuk menyelesaikan masalah pemrograman linier ini, yang kemudian juga dilajutkan beberapa kasul lain yang lebih kompleks.

Solusi Pulp

Library pulp sangat memungkinkan anda untuk memilih metode penyelesaian masalah dan merumuskan masalah dengan cara yang lebih sederhana dibandingkan dengan penyelesaian manual dan metode grafik diatas. pulp adalah paket pemrograman linier open-source untuk python. pulp dapat diinstal menggunakan pip, petunjuk di sini. Pada bagian ini, diperlihatkan bagaimana membangun dan memecahkan masalah pemrograman linier dengan Python.

# mengimport library PulP 
from pulp import LpMaximize, LpProblem, LpStatus, lpSum, LpVariable, value

model1 = LpProblem("model1", LpMaximize)          # model optimasi max
x = LpVariable('x', lowBound=0, cat='Continuous') # batasan variabel keputusan x
y = LpVariable('y', lowBound=2, cat='Continuous') # batasan variabel keputusan y

# Fungsi objektif
model1 += 4 * x + 3 * y, "Z"

# Fungsi kendala
model1 += 2 * y <= 25 - x
model1 += 4 * y >= 2 * x - 8
model1 += y <= 2 * x - 5

Mencetak model,

print(model1)

## model1:
## MAXIMIZE
## 4*x + 3*y + 0
## SUBJECT TO
## _C1: x + 2 y <= 25
## 
## _C2: - 2 x + 4 y >= -8
## 
## _C3: - 2 x + y <= -5
## 
## VARIABLES
## x Continuous
## 2 <= y Continuous

Mencetak status, apakah ditemukan solusi?

model1.solve()

## 1

LpStatus[model1.status]

## 'Optimal'

Ada lima kemungkinan pada saat anda memeriksa status dengan menggunakan solver, yakni;

• Not Solved: tidak dapat menyelesaikan masalah.
• Optimal: ditemukan solusi optima.
• Infeasible: tidak ada solusi yang layak (misalnya jika Anda menetapkan batasan \(x\leq 1\) dan \(x\geq 2)\).
• Unbounded: tidak ada batasan, memaksimalkan solusi akan cenderung menuju tak terhingga (misalnya jika satu-satunya kendala adalah \(x \geq 3).\)
• Undefined: solusi optimal mungkin ada tetapi dapat ditemukan.

Berikutnya, kita dapat melihat nilai variabel maksimal dan nilai maksimum \(Z.\) Selain itu, kita dapat menggunakan metode varValue untuk mengambil nilai variabel \(x\) dan \(y,\) dan fungsi value untuk melihat nilai maksimum nilai fungsi tujuan.

print("Variable x = {}".format(x.varValue)) 

## Variable x = 14.5

print("Variable y = {}".format(y.varValue))

## Variable y = 5.25

print(value(model1.objective))

## 73.75

Solusi Manual

Kerjakan seperti Contoh 1

Solusi Scipy

Untuk menyelesaikan permasalahan tersebut diatas anda dapata menggunakan library scipy yang ada di Python. Dalam hal ini menggunakan fungsi linprog(), yang mana fungsi tersebut hanya dapata menyelesaikan permasalahan minimisasi (bukan maksimalisasi) dan tidak mengizinkan kendala ketidaksetaraan dengan lebih besar dari atau sama dengan tanda \((≥)\). Untuk mengatasi masalah ini, Anda perlu mengubah masalah Anda sebelum memulai pengoptimalan:

• Alih-alih memaksimalkan \(z = x + 2y,\) Anda dapat meminimalkan negatifnya \((−z = -x -2y).\)
• Alih-alih memiliki tanda lebih besar dari atau sama dengan, Anda dapat mengalikan pertidaksamaan kuning dengan -1 untuk mendapatkan kebalikan persamaan tersebut menjadi kurang dari atau sama dengan tanda \((≤)\).

Setelah melakukan perubahan ini, maka diperoleh sistem persamaan baru:

Cantan: Sebenarnya, Sub-paket scipy.optimize-nya tidak hanya dapat digunakan untuk optimasi program linier tetapi juga dapat digunakan program nonlinier.

Berikut ini adalah penyelesaiannya dengan Python

from scipy.optimize import linprog

obj = [-1, -2]
#      ─┬  ─┬
#       │   └---------┤ yoefisien x
#       └-------------| koefisien y

lhs_ineq = [[ 2,  1], # Batas sisi kiri (garis merah)
           [-4,  5],  # Batas sisi kiri (garis biru)
           [ 1, -2]]  # Batas sisi kiri (garis kuning)

rhs_ineq = [20,       # Batas sisi kanan (garis merah)
             10,      # Batas sisi kanan (garis biru)
              2]      # Batas sisi kanan (garis kuning)

lhs_eq = [[-1, 5]]    # Batas sisi kiri  (garis hijau)
rhs_eq = [15]         # Batas sisi kanan (garis hijau)

Anda dapat memasukkan nilai dari sistem persamaan di atas ke dalam daftar, tupel, atau array NumPy yang sesuai:

• obj koefisien dari fungsi tujuan.
• lhs_ineq koefisien sisi kiri dari kendala pertidaksamaan (merah, biru, dan kuning).
• rhs_ineq koefisien sisi kanan dari kendala pertidaksamaan (merah, biru, dan kuning).
• lhs_eq koefisien sisi kiri dari kendala persamaan (hijau).
• rhs_eq koefisien sisi kanan dari kendala persaman (hijau).

Langkah selanjutnya adalah menentukan batas untuk setiap variabel dalam urutan yang sama dengan koefisien. Dalam hal ini, keduanya berada di antara nol dan tak terhingga positif:

bnd = [(0, float("inf")),  # batas x
       (0, float("inf"))]  # batas y

model2 = linprog(c=obj, 
              A_ub=lhs_ineq, 
              b_ub=rhs_ineq,
              A_eq=lhs_eq,
              b_eq=rhs_eq,
              bounds=bnd,
              method="revised simplex")

## <string>:1: DeprecationWarning: `method='revised simplex'` is deprecated and will be removed in SciPy 1.11.0. Please use one of the HiGHS solvers (e.g. `method='highs'`) in new code.

print(model2)

##      con: array([0.])
##      fun: -16.818181818181817
##  message: 'Optimization terminated successfully.'
##      nit: 3
##    slack: array([ 0.        , 18.18181818,  3.36363636])
##   status: 0
##  success: True
##        x: array([7.72727273, 4.54545455])

Anda juga dapat menggunakan metode dengan parameter yang lain, untuk menentukan metode pemrograman linier yang ingin Anda gunakan. Ada tiga opsi:

• method=“interior-point” memilih metode interior-point. Opsi ini diatur secara default.
• method=“revised simplex” memilih metode simpleks dua fase yang direvisi.
• method=“simplex” memilih metode simpleks dua fase yang lama.

Anda dapat mengakses hasil dari medel tersebut diatas ini secara terpisah:

model2.success        # chek apakah ditemukan solusi

## True

model2.fun            # fungsi optimum

## -16.818181818181817

model2.x              # variabel kemputusan

## array([7.72727273, 4.54545455])

Dalam hal ini hasil optimasi dapat diperlihatkan juga secara grafis berikut:

Seperti dibahas sebelumnya, solusi optimal untuk masalah program linier terletak pada simpul dari daerah layak. Dalam hal ini, daerah yang layak hanyalah bagian dari garis hijau antara garis biru dan merah. Solusi optimal adalah kotak hijau yang mewakili titik perpotongan antara garis hijau dan merah.

Jika Anda ingin mengecualikan batasan kesetaraan (hijau), cukup jatuhkan parameter A_eq dan b_eq dari panggilan linprog():

model3 = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq, bounds=bnd,
                 method="revised simplex")
model3

##      con: array([], dtype=float64)
##      fun: -20.714285714285715
##  message: 'Optimization terminated successfully.'
##      nit: 2
##    slack: array([0.        , 0.        , 9.85714286])
##   status: 0
##  success: True
##        x: array([6.42857143, 7.14285714])

Solusinya berbeda dari kasus sebelumnya. Anda dapat melihatnya pada grafik berikut:

Solusi Manual

Kerjakan Solusi manualnya disini

Solusi Pulp

Kerjakan Solusi Pulp disini

Solusi Scipy

Kerjakan Solusi Scipy disini