Menentukan Nilai Optimum Dengan Metode Garis Selidik Program Linear

Metode garis selidik adalah sebuah metode yang umum digunakan dalam program linear untuk menentukan nilai optimum dari suatu persoalan linear. Dalam program linear terdapat sebuah fungsi linear yang disebut fungsi objektif atau fungsi tujuan, yang biasanya ditulis dalam bentuk $z = ax + by$ atau $f(x, y) = ax + by$. Dalam program linear juga terdapat sebuah sistem pertidaksamaan linear yang disebut syarat atau batasan yang disebut juga kendala. Langkah-langkah untuk menentukan nilai optimum dengan metode garis selidik adalah sebagai berikut:
1. Menggambar himpunan penyelesaian dari batasan-batasan atau kendala yang diberikan pada sistem koordinat Cartesius.
2. Menentukan titik-titik ekstrim atau titik-titik pojok dari himpunan penyelesaian, karena nilai optimum terletak pada titik ekstrim.
3. Tentukan persamaan garis selidik awal dari fungsi sasaran atau fungsi objektif. Jika fungsi objektif adalah $z = ax + by$ atau $f(x, y) = ax + by$, maka sebagai persamaan garis selidik awal adalah $ax + by = z$, $z$ adalah bilangan sembarang. Untuk mempermudah ganti $z$ menjadi $ab$, sehingga persamaan garis selidik awal adalah $ax + by = ab$.
4. Tarik garis yang sejajar dengan persamaan garis selidik awal dan harus melalui titik-titik ekstrim atau titik-titik pojok. Garis paling kanan (untuk a > 0) atau paling atas (untuk b > 0) adalah garis yang melalui titik maksimum. Artinya, titik maksimum adalah titik yang dilalui oleh garis paling kanan jika a bernilai positif atau paling atas jika b bernilai positif. Sebaliknya titik minimum adalah titik yang dilalui oleh garis paling kiri jika a bernilai positif atau garis paling bawah jika b bernilai positif. Jika a < 0 atau b < 0 maka berlaku sebaliknya.
5. Untuk menentukan nilai optimum (maksimum atau minimum), masukkan nilai dari variabel yang sudah didapat (x dan y) ke dalam fungsi sasaran atau fungsi tujuan.

Contoh soal 1.
Nilai maksimum $f(x, y) = 2x + 3y$ pada daerah yang dibatasi oleh: $2x + y \leq 9$; $x + 3y \leq 12$; $x \geq 0;\ y \geq 0$ adalah . . . .
A. 9
B. 12
C. 15
D. 24
E. 27

Pembahasan:

Langkah 1:
Menggambar daerah penyelesaian dari syarat-syarat yang diberikan.
$\bullet$ Gambarkan persamaan garis $2x + y = 9$
Titik potong sumbu x → y = 0
2x + 0 = 9
2x = 9
$x = \dfrac{9}{2}$
jadi titik potong sumbu $x = (\dfrac{9}{2}, 0)$
Titik potong sumbu y → x = 0
2.0 + y = 9
y = 9
jadi titik potong sumbu y = (0, 9)
Hubungkan titik $(\dfrac{9}{2}, 0)$ dan (0, 9) didapat gambar persamaan garis $2x + 3y = 9$. Untuk mengetahui arah arsiran, lakukan uji titik O(0, 0).
$2x + 3y \leq 9$
$2.0 + 3.0 \leq 9$
$0 \leq 9$ → benar, berarti arsiran ke arah titik O(0, 0). Jika salah, arsiran harus arah sebaliknya.

$\bullet$ Gambarkan persamaan garis $x + 3y = 12$
Titik potong sumbu x → y = 0
x + 3.0 = 12
x = 12
jadi titik potong sumbu x = (12, 0)
Titik potong sumbu y → x = 0
0 + 3y = 12
3y = 12
y = 4
jadi titik potong sumbu y = (0, 4). Hubungkan titik (12, 0) dan (0, 4) didapat gambar persamaan garis $x + 3y = 12$. Untuk menentukan arah arsiran, lakukan uji titik O(0, 0).
$x + 3y \leq 12$
$0 + 3.0 \leq 12$
$0 \leq 12$ → benar, berarti arsiran kearah O(0, 0). Daerah yang diarsir pada gambar (OABC) adalah daerah penyelesaian.

Langkah 2:
Karena fungsi objektifnya adalah $z = f(x, y) = 2x + 3y$, maka persamaan garis selidik awalnya adalah $2x + 3y = 6$. Gambarkan garis selidik dengan langkah-langkah seperti di atas.
Titik potong sumbu x → y = 0
2x + 3.0 = 6
2x = 6
x = 3
jadi titik potong sumbu x = (3, 0)
Titik potong sumbu y → x = 0
2.0 + 3y = 6
3y = 6
y = 2
jadi titik potong sumbu y = (0, 2)
Hubungkan titik (3, 0) dan (0, 2) didapat gambar persamaan garis selidik awal $2x + 3y = 6$

Langkah 3:
Gambar garis yang sejajar dengan garis selidik awal dan melalui titik-titik ekstrem. Titik-titik ekstrimnya atau titik-titik pojok adalah titik O, A, B, dan C. Garis yang paling kanan (a > 0) atau garis yang paling atas (b > 0) adalah garis yang melalui titik maksimum. Berdasarkan gambar, titik maksimumnya adalah titik potong antara garis $2x + 3y = 9$ dengan garis $x + 3y = 12$ (titik B).


Untuk mengetahui koordinat titik B, lakukan eliminasi:
$2x + y = 9\ |\ \times\ 3$
$x + 3y = 12$

$6x + 3y = 27$
$x + 3y = 12$
-------------------- -
$5x = 15$
$x = 3$
$x + 3y = 12$
$3 + 3y = 12$
$3y = 9$
$y = 3$
Titik potong = (3, 3)

Masukkan titik (3, 3) kedalam persamaan fungsi sasaran.
$f(x, y) = 2x + 3y$
$= 2.3 + 3.3$
$= 15$

Berarti nilai maksimumnya adalah 15.
Jawab: C.

Contoh Soal 2.
Nilai minimum untuk $2x + 5y$ dengan syarat: $x \geq 0$, $y \geq 0$, $x + y \geq 12$, dan $x + 2y \geq 16$ adalah . . . .
A. 24
B. 32
C. 36
D. 40
E. 60

Pembahasan:

Langkah 1:
Menggambar daerah penyelesaian dari syarat-syarat yang diberikan.
$\bullet$ Gambarkan persamaan garis $x + y = 12$
Titik potong sumbu x → y = 0
x + 0 = 12
x = 12
jadi titik potong sumbu $x = (12, 0)$
Titik potong sumbu y → x = 0
0 + y = 12
y = 12
jadi titik potong sumbu y = (0, 12). Hubungkan titik $(12, 0)$ dan (0, 12) didapat gambar persamaan garis $x + y = 12$. Untuk mengetahui arah arsiran, lakukan uji titik O(0, 0).
$x + y \geq 12$
$0 + 0 \geq 12$
$0 \geq 12$ → salah, berarti arsiran ke arah atas, bukan ke arah titik O(0, 0).

$\bullet$ Gambarkan persamaan garis $x + 2y = 16$
Titik potong sumbu x → y = 0
x + 2.0 = 16
x = 16
jadi titik potong sumbu x = (16, 0)
Titik potong sumbu y → x = 0
0 + 2y = 16
2y = 16
y = 8
jadi titik potong sumbu y = (0, 8). Hubungkan titik (16, 0) dan (0, 8) didapat gambar persamaan garis $x + 2y = 16$. Untuk menentukan arah arsiran, lakukan uji titik O(0, 0).
$x + 3y \geq 16$
$0 + 2.0 \geq 16$
$0 \geq 16$ → salah, berarti arsiran kearah atas, bukan ke arah titik O(0, 0). Daerah yang diarsir pada gambar adalah daerah penyelesaian.

Langkah 2:
Karena fungsi objektifnya adalah $z = f(x, y) = 2x + 5y$, maka persamaan garis selidik awalnya adalah $2x + 5y = 10$. Gambarkan garis selidik dengan langkah-langkah seperti di atas.
Titik potong sumbu x → y = 0
2x + 5.0 = 10
2x = 10
x = 5
jadi titik potong sumbu x = (5, 0)
Titik potong sumbu y → x = 0
2.0 + 5y = 10
5y = 10
y = 2
jadi titik potong sumbu y = (0, 2)
Hubungkan titik (5, 0) dan (0, 2) didapat gambar persamaan garis selidik awal $2x + 5y = 10$

Langkah 3:
Gambar garis yang sejajar dengan garis selidik awal dan melalui titik-titik ekstrem. Ttik-titik ekstrimnya adalah titik A, B, dan C. Garis yang paling kiri (a > 0) atau garis yang paling bawah (b > 0) adalah garis yang melalui titik minimum. Berdasarkan gambar, titik minimumnya adalah titik C(16, 0).


Untuk mendapatkan nilai minimum, masukkan titik (16, 0) ke dalam persamaan fungsi sasaran.
$z = 2x + 5y$
$= 2.16 + 5.0$
$= 32$
Jawab: B.

Contoh soal 3.
Nilai maksimum $f(x, y) = 3x - 2y$ pada daerah yang dibatasi oleh: $x + y \leq 6$; $x + 2y \leq 8$; $x \geq 0;\ y \geq 0$ adalah . . . .
$A.\ -12$
$B.\ -8$
$C.\ 8$
$D.\ 18$
$E.\ 24$

Pembahasan:

Langkah 1.
Menggambar daerah penyelesaian dari syarat-syarat yang diberikan.
$\bullet$ Gambarkan persamaan garis $x + y = 6$
Titik potong sumbu x → y = 0
x + 0 = 6
x = 6
jadi titik potong sumbu x = (6, 0)
Titik potong sumbu y → x = 0
0 + y = 6
y = 6
jadi titik potong sumbu y = (0, 6). Hubungkan titik (6, 0) dan (0, 6) didapat gambar persamaan garis $x + y = 6$. Untuk mengetahui arah arsiran, lakukan uji titik O(0, 0).
$x + y \leq 6$
$0 + 0 \leq 6$
$0 \leq 6$ → benar, berarti arsiran ke arah titik O(0, 0), karena himpunan penyelesaiannya harus mengandung titik O(0, 0).
$\bullet$ Gambarkan persamaan garis $x + 2y = 8$
Titik potong sumbu x → y = 0
x + 2.0 = 8
x = 8
jadi titik potong sumbu x = (8, 0)
Titik potong sumbu y → x = 0
0 + 2y = 8
2y = 8
y = 4
jadi titik potong sumbu y = (0, 4). Hubungkan titik (8, 0) dan (0, 4) didapat gambar persamaan garis $x + 2y = 8$. Untuk menentukan arah arsiran, lakukan uji titik O(0, 0).
$x + 2y \leq 8$
$0 + 2.0 \leq 8$
$0 \leq 8$ → benar, berarti arsiran kearah O(0, 0). Daerah yang diarsir pada gambar (OABC) adalah daerah penyelesaian.

Langkah 2:
Karena fungsi objektifnya adalah $z = f(x, y) = 3x - 2y$, maka persamaan garis selidik awalnya adalah $3x - 2y = 6$ atau $3x - 2y = -6$ tidak akan mempengaruhi hasil. Kita ambil sebagai persamaan garis selidik awal $3x - 2y = 6$ Gambarkan garis selidik dengan langkah-langkah seperti di atas.
Titik potong sumbu x → y = 0
$3x - 2.0 = 6$
$3x = 6$
$x = 2$
jadi titik potong sumbu x = (2, 0)
Titik potong sumbu y → x = 0
$3.0 - 2y = 6$
$2y = -6$
$y = -3$
jadi titik potong sumbu $y = (0, -3)$. Hubungkan titik $(2, 0)$ dan $(0, -3)$ didapat gambar persamaan garis selidik awal $3x - 2y = 6$

Langkah 3:
Gambar garis yang sejajar dengan garis selidik awal dan melalui titik-titik ekstrim. Titik-titik ekstrimnya atau titik-titik pojok adalah titik O, A, B, dan C. Garis yang paling kanan (a > 0) atau garis yang paling bawah (b < 0) adalah garis yang melalui titik maksimum. Berdasarkan gambar, titik maksimumnya adalah titik A(6, 0).


Untuk mendapatkan nilai maksimum, masukkan titik (6, 0) kedalam persamaan fungsi sasaran.
$f(x, y) = 3x - 2y$
$= 3.6 - 2.0$
$= 18$
Jawab: D.

Contoh soal 4.
Nilai maksimum dan minimum dari $z = -3x + 6y$ yang memenuhi sistem pertidaksamaan : $4x + 2y \geq 20$, $x + y \leq 20$, $x + y \geq 10$, $x \geq 0$, $y \geq 0$ adalah . . . .
$A.\ 120\ dan\ -60$
$B.\ 30\ dan\ -30$
$C.\ 120\ dan\ 30$
$D.\ 60\ dan\ 30$
$E.\ -30\ dan\ -60$

Pembahasan:

Langkah 1
Menggambar daerah penyelesaian dari syarat-syarat yang diberikan. Silahkan adik-adik kerjakan, ikuti langkah-langkah pada contoh soal nomor 1 sampai 3.

Langkah 2.
Karena fungsi objektifnya adalah $z = f(x, y) = -3x + 6y$, maka persamaan garis selidik awalnya adalah $-3x + 6y = 18$ atau $-3x + 6y = -18$ tidak akan mempengaruhi hasil. Kita ambil sebagai persamaan garis selidik awal $-3x + 6y = -18$. Gambarkan garis selidik dengan langkah-langkah seperti di atas.
Titik potong sumbu x → y = 0
$-3x + 6.0 = -18$
$-3x = -18$
$x = 6$
jadi titik potong sumbu x = (6, 0)
Titik potong sumbu y → x = 0
$-3.0 + 6y = -18$
$6y = -18$
$y = -3$
jadi titik potong sumbu $y = (0, -3)$. Hubungkan titik $(6, 0)$ dan $(0, -3)$ didapat gambar persamaan garis selidik awal $-3x + 6y = -18$

Langkah 3.
Gambar garis yang sejajar dengan garis selidik awal dan melalui titik-titik ekstrim atau titik-titik pojok. Untuk menentukan nilai maksimum atau minimum, kita bisa menggunakan nilai a atau b atau kedua-duanya sekaligus sebagai patokan. Karena $a = -3 < 0$, maka nilai maksimum adalah pada titik yang dilalui garis selidik paling kiri dan nilai minimum adalah pada titik yang dilalui garis selidik paling kanan. Karena $b = 6 > 0$ maka nilai maksimum adalah pada titik yang dilalui garis selidik paling atas dan nilai minimum adalah pada titik yang dilalui garis selidik paling bawah. Hasil dari patokan a dan patokan b adalah sama.


Kesimpulan, nilai maksimum adalah pada titik $(0, 20)$ dan nilai minimum adalah pada titik $(20, 0)$. Masukkan masing-masing titik ke dalam persamaan fungsi objektif $z = -3x + 6y$.
Nilai maksimum $= -3.0 + 6.20 = 120$.
Nilai minimum $= -3.20 + 6.0 = -60$.
Jawab: A.

Demikianlah cara untuk menentukan nilai optimum dengan metode garis selidik, semoga bermanfaat !

SHARE THIS POST

Artikel Terkait:
1. Menentukan Daerah Himpunan Penyelesaian Sistem Pertidaksamaan Linear Dua Variabel
2. Soal dan Pembahasan Progran Linear

www.maretong.com



Post a Comment for "Menentukan Nilai Optimum Dengan Metode Garis Selidik Program Linear"