Matematika SMA/MA/SMK/MAK
Menentukan Nilai Optimum Fungsi Tujuan dengan Metode Uji Titik Pojok
Program Linear
Pengertian Metode Uji Titik Pojok
Metode Uji Titik Pojok (Corner Point Method) adalah salah satu metode untuk menentukan nilai optimum (nilai maksimum atau minimum) dari suatu fungsi tujuan pada masalah program linear.
Prinsip dasar metode ini adalah:
Nilai optimum fungsi tujuan selalu terletak pada salah satu titik pojok (titik sudut) daerah penyelesaian (daerah fisibel).
Titik pojok adalah titik-titik sudut dari daerah himpunan penyelesaian yang dibentuk oleh perpotongan garis-garis batas kendala.
Langkah-Langkah Metode Uji Titik Pojok
Berikut langkah-langkah menentukan nilai optimum dengan metode uji titik pojok:
- Tentukan fungsi tujuan dan sistem pertidaksamaan linear (kendala/batasan).
- Gambar daerah penyelesaian dari sistem pertidaksamaan linear tersebut.
- Tentukan semua titik pojok daerah penyelesaian. Titik pojok diperoleh dari:
- Titik potong dua garis batas
- Titik potong garis batas dengan sumbu-x atau sumbu-y
- Substitusi setiap titik pojok ke dalam fungsi tujuan.
- Bandingkan nilai-nilai yang diperoleh, lalu tentukan nilai maksimum atau minimum sesuai permintaan soal.
Konsep Penting
1. Fungsi Tujuan
Fungsi tujuan adalah fungsi yang akan dioptimumkan (dimaksimumkan atau diminimumkan). Bentuk umum:
dengan a dan b adalah koefisien dari variabel keputusan x dan y.
2. Kendala (Batasan)
Kendala berupa sistem pertidaksamaan linear dua variabel, misalnya:
a₁x + b₁y ≤ c₁
a₂x + b₂y ≤ c₂
x ≥ 0
y ≥ 0
3. Daerah Penyelesaian (Daerah Fisibel)
Daerah penyelesaian adalah irisan dari semua daerah yang memenuhi seluruh pertidaksamaan kendala. Daerah ini berbentuk poligon (segi banyak) yang dibatasi oleh garis-garis batas.
4. Titik Pojok
Titik pojok adalah titik-titik sudut poligon daerah penyelesaian. Berdasarkan Teorema Dasar Program Linear, nilai optimum fungsi tujuan pasti dicapai pada salah satu titik pojok.
Ilustrasi Metode Uji Titik Pojok
Perhatikan ilustrasi berikut. Misalkan daerah penyelesaian memiliki titik-titik pojok A, B, C, dan D:
Untuk menentukan nilai optimum, kita substitusi koordinat setiap titik pojok ke fungsi tujuan, lalu pilih nilai terbesar (maksimum) atau terkecil (minimum).
| Titik Pojok | Koordinat (x, y) | Nilai f(x, y) = ax + by |
|---|---|---|
| A | (x₁, y₁) | ax₁ + by₁ |
| B | (x₂, y₂) | ax₂ + by₂ |
| C | (x₃, y₃) | ax₃ + by₃ |
| D | (x₄, y₄) | ax₄ + by₄ |
| E | (x₅, y₅) | ax₅ + by₅ |
Nilai terbesar dari kolom ketiga adalah nilai maksimum, dan nilai terkecil adalah nilai minimum.
Contoh Soal – Tingkat Mudah
Contoh 1
Tentukan nilai maksimum dari f(x, y) = 2x + 3y pada daerah penyelesaian yang memiliki titik-titik pojok: A(0, 0), B(4, 0), C(0, 3).
Pembahasan:
Substitusi setiap titik pojok ke f(x, y) = 2x + 3y:
- A(0, 0): f = 2(0) + 3(0) = 0
- B(4, 0): f = 2(4) + 3(0) = 8
- C(0, 3): f = 2(0) + 3(3) = 9
Nilai maksimum = 9, dicapai di titik C(0, 3).
Contoh 2
Tentukan nilai minimum dari f(x, y) = x + 2y pada daerah penyelesaian dengan titik pojok: A(0, 5), B(3, 2), C(6, 0).
Pembahasan:
- A(0, 5): f = 0 + 2(5) = 10
- B(3, 2): f = 3 + 2(2) = 7
- C(6, 0): f = 6 + 2(0) = 6
Nilai minimum = 6, dicapai di titik C(6, 0).
Contoh 3
Tentukan nilai maksimum dari f(x, y) = 4x + y pada daerah penyelesaian dengan titik pojok: A(0, 0), B(5, 0), C(3, 4), D(0, 6).
Pembahasan:
- A(0, 0): f = 4(0) + 0 = 0
- B(5, 0): f = 4(5) + 0 = 20
- C(3, 4): f = 4(3) + 4 = 16
- D(0, 6): f = 4(0) + 6 = 6
Nilai maksimum = 20, dicapai di titik B(5, 0).
Contoh 4
Tentukan nilai minimum dari f(x, y) = 3x + 5y pada daerah penyelesaian dengan titik pojok: A(1, 1), B(4, 1), C(2, 3).
Pembahasan:
- A(1, 1): f = 3(1) + 5(1) = 8
- B(4, 1): f = 3(4) + 5(1) = 17
- C(2, 3): f = 3(2) + 5(3) = 21
Nilai minimum = 8, dicapai di titik A(1, 1).
Contoh 5
Tentukan nilai maksimum dari f(x, y) = x + y pada daerah penyelesaian dengan titik pojok: A(0, 0), B(6, 0), C(4, 4), D(0, 5).
Pembahasan:
- A(0, 0): f = 0 + 0 = 0
- B(6, 0): f = 6 + 0 = 6
- C(4, 4): f = 4 + 4 = 8
- D(0, 5): f = 0 + 5 = 5
Nilai maksimum = 8, dicapai di titik C(4, 4).
Contoh Soal – Tingkat Sedang
Contoh 6
Tentukan nilai maksimum f(x, y) = 3x + 2y dengan kendala:
x + y ≤ 6
x + 2y ≤ 8
x ≥ 0, y ≥ 0
Pembahasan:
Langkah 1: Tentukan titik potong garis batas.
Garis x + y = 6 memotong sumbu di (6, 0) dan (0, 6).
Garis x + 2y = 8 memotong sumbu di (8, 0) dan (0, 4).
Langkah 2: Titik potong kedua garis:
x + y = 6 … (1)
x + 2y = 8 … (2)
Dari (2) − (1): y = 2, maka x = 4
Titik potong: (4, 2)
Langkah 3: Titik pojok daerah penyelesaian: A(0, 0), B(6, 0), C(4, 2), D(0, 4).
Langkah 4: Substitusi:
- A(0, 0): f = 0
- B(6, 0): f = 18
- C(4, 2): f = 12 + 4 = 16
- D(0, 4): f = 8
Nilai maksimum = 18, dicapai di titik B(6, 0).
Contoh 7
Tentukan nilai maksimum f(x, y) = 5x + 4y dengan kendala:
2x + y ≤ 10
x + 2y ≤ 10
x ≥ 0, y ≥ 0
Pembahasan:
Garis 2x + y = 10: titik potong sumbu (5, 0) dan (0, 10).
Garis x + 2y = 10: titik potong sumbu (10, 0) dan (0, 5).
Titik potong kedua garis:
2x + y = 10 … (1)
x + 2y = 10 … (2)
Dari (1)×2: 4x + 2y = 20
(1)×2 − (2): 3x = 10, jadi x = 10/3
y = 10 − 2(10/3) = 10/3
Titik potong: (10/3, 10/3)
Titik pojok: A(0, 0), B(5, 0), C(10/3, 10/3), D(0, 5).
- A(0, 0): f = 0
- B(5, 0): f = 25
- C(10/3, 10/3): f = 50/3 + 40/3 = 90/3 = 30
- D(0, 5): f = 20
Nilai maksimum = 30, dicapai di titik C(10/3, 10/3).
Contoh 8
Tentukan nilai minimum f(x, y) = 2x + 5y dengan kendala:
x + y ≥ 4
x + 3y ≥ 6
x ≥ 0, y ≥ 0
Pembahasan:
Garis x + y = 4: titik (4, 0) dan (0, 4).
Garis x + 3y = 6: titik (6, 0) dan (0, 2).
Titik potong kedua garis:
x + y = 4 → x = 4 − y
Substitusi: (4 − y) + 3y = 6 → 2y = 2 → y = 1, x = 3
Titik pojok: A(6, 0), B(3, 1), C(0, 4).
- A(6, 0): f = 12 + 0 = 12
- B(3, 1): f = 6 + 5 = 11
- C(0, 4): f = 0 + 20 = 20
Nilai minimum = 11, dicapai di titik B(3, 1).
Contoh 9
Tentukan nilai maksimum f(x, y) = 4x + 3y dengan kendala:
x + y ≤ 8
2x + y ≤ 12
x ≤ 5
x ≥ 0, y ≥ 0
Pembahasan:
Titik potong x + y = 8 dan 2x + y = 12:
(2) − (1): x = 4, y = 4 → titik (4, 4)
Titik potong 2x + y = 12 dan x = 5:
10 + y = 12 → y = 2 → titik (5, 2)
Titik pojok: A(0, 0), B(5, 0), C(5, 2), D(4, 4), E(0, 8).
- A(0, 0): f = 0
- B(5, 0): f = 20
- C(5, 2): f = 20 + 6 = 26
- D(4, 4): f = 16 + 12 = 28
- E(0, 8): f = 24
Nilai maksimum = 28, dicapai di titik D(4, 4).
Contoh 10
Tentukan nilai minimum f(x, y) = x + 4y dengan kendala:
2x + y ≥ 6
x + y ≥ 4
x ≥ 0, y ≥ 0
Pembahasan:
Titik potong 2x + y = 6 dan x + y = 4:
(1) − (2): x = 2, y = 2 → titik (2, 2)
Titik pojok: A(4, 0), B(3, 0) — cek: (3,0) pada 2(3)+0=6 ≥ 6 ✓ dan 3+0=3 < 4 ✗
Koreksi: titik pada sumbu-x yang memenuhi keduanya: x ≥ 4 → titik (4, 0).
Titik pada sumbu-y: y ≥ 6 → titik (0, 6).
Titik pojok: A(4, 0), B(2, 2), C(0, 6).
- A(4, 0): f = 4 + 0 = 4
- B(2, 2): f = 2 + 8 = 10
- C(0, 6): f = 0 + 24 = 24
Nilai minimum = 4, dicapai di titik A(4, 0).
Contoh Soal – Tingkat Sulit
Contoh 11
Seorang pengusaha memproduksi dua jenis barang A dan B. Setiap unit A membutuhkan 2 jam mesin dan 1 jam tenaga kerja. Setiap unit B membutuhkan 1 jam mesin dan 3 jam tenaga kerja. Mesin tersedia 10 jam dan tenaga kerja 12 jam. Keuntungan tiap unit A adalah Rp40.000 dan tiap unit B adalah Rp50.000. Tentukan keuntungan maksimum!
Pembahasan:
Misalkan x = jumlah barang A, y = jumlah barang B.
Fungsi tujuan: f(x, y) = 40.000x + 50.000y (maksimumkan)
Kendala:
2x + y ≤ 10 (mesin)
x + 3y ≤ 12 (tenaga kerja)
x ≥ 0, y ≥ 0
Titik potong garis: 2x + y = 10 dan x + 3y = 12
Dari (1): y = 10 − 2x
Substitusi: x + 3(10 − 2x) = 12 → x + 30 − 6x = 12 → −5x = −18 → x = 18/5 = 3,6
y = 10 − 7,2 = 2,8
Titik pojok: A(0, 0), B(5, 0), C(3,6; 2,8), D(0, 4).
- A(0, 0): f = 0
- B(5, 0): f = 200.000
- C(3,6; 2,8): f = 144.000 + 140.000 = 284.000
- D(0, 4): f = 200.000
Keuntungan maksimum = Rp284.000, dicapai di titik C(3,6; 2,8).
(Catatan: Jika diharuskan bulat, maka perlu diperiksa titik bulat terdekat dalam daerah fisibel.)
Contoh 12
Tentukan nilai maksimum dan minimum f(x, y) = 3x + 5y dengan kendala:
x + 2y ≤ 12
3x + 2y ≤ 18
x + y ≥ 3
x ≥ 0, y ≥ 0
Pembahasan:
Garis x + 2y = 12: (12, 0), (0, 6)
Garis 3x + 2y = 18: (6, 0), (0, 9)
Garis x + y = 3: (3, 0), (0, 3)
Titik potong x + 2y = 12 dan 3x + 2y = 18:
(2) − (1): 2x = 6 → x = 3, y = 4,5 → titik (3, 4,5)
Titik potong x + y = 3 dan x + 2y = 12:
(2) − (1): y = 9 → tapi cek 3x + 2(9) = 18 → x = 0
Sebenarnya: x + 2y = 12 dan x + y = 3 → y = 9, x = −6 (tidak memenuhi x ≥ 0)
Titik pojok daerah: A(3, 0), B(6, 0), C(3, 4,5), D(0, 6), E(0, 3).
- A(3, 0): f = 9
- B(6, 0): f = 18
- C(3, 4,5): f = 9 + 22,5 = 31,5
- D(0, 6): f = 30
- E(0, 3): f = 15
Nilai maksimum = 31,5 di titik C(3, 4,5). Nilai minimum = 9 di titik A(3, 0).
Contoh 13
Sebuah perusahaan memproduksi meja dan kursi. Setiap meja membutuhkan 4 jam pemotongan dan 2 jam perakitan. Setiap kursi membutuhkan 2 jam pemotongan dan 4 jam perakitan. Waktu pemotongan tersedia 24 jam dan perakitan 20 jam. Keuntungan meja Rp80.000 dan kursi Rp60.000. Tentukan keuntungan maksimum!
Pembahasan:
Misalkan x = meja, y = kursi.
f(x, y) = 80.000x + 60.000y
Kendala: 4x + 2y ≤ 24 → 2x + y ≤ 12
2x + 4y ≤ 20 → x + 2y ≤ 10
x ≥ 0, y ≥ 0
Titik potong 2x + y = 12 dan x + 2y = 10:
Dari (1)×2: 4x + 2y = 24
(1)×2 − (2): 3x = 14 → x = 14/3, y = 12 − 28/3 = 8/3
Titik pojok: A(0, 0), B(6, 0), C(14/3, 8/3), D(0, 5).
- A(0, 0): f = 0
- B(6, 0): f = 480.000
- C(14/3, 8/3): f = 80.000(14/3) + 60.000(8/3) = 1.120.000/3 + 480.000/3 = 1.600.000/3 ≈ 533.333
- D(0, 5): f = 300.000
Keuntungan maksimum ≈ Rp533.333, dicapai di titik C(14/3, 8/3).
Contoh 14
Tentukan nilai minimum f(x, y) = 6x + 8y dengan kendala:
2x + y ≥ 10
x + 2y ≥ 10
x + y ≥ 8
x ≥ 0, y ≥ 0
Pembahasan:
Titik potong 2x + y = 10 dan x + y = 8:
(1) − (2): x = 2, y = 6 → titik (2, 6)
Titik potong x + 2y = 10 dan x + y = 8:
(1) − (2): y = 2, x = 6 → titik (6, 2)
Titik potong 2x + y = 10 dan x + 2y = 10:
(1)×2 − (2): 3x = 10 → x = 10/3, y = 10/3 → titik (10/3, 10/3)
Cek (10/3, 10/3) pada x + y ≥ 8: 20/3 ≈ 6,67 < 8 ✗ → tidak memenuhi.
Titik pojok: A(10, 0), B(6, 2), C(2, 6), D(0, 10).
- A(10, 0): f = 60
- B(6, 2): f = 36 + 16 = 52
- C(2, 6): f = 12 + 48 = 60
- D(0, 10): f = 80
Nilai minimum = 52, dicapai di titik B(6, 2).
Contoh 15
Sebuah toko kue membuat kue A dan kue B. Kue A membutuhkan 200 g tepung dan 100 g gula. Kue B membutuhkan 100 g tepung dan 150 g gula. Persediaan tepung 2.000 g dan gula 1.500 g. Kue A dijual Rp25.000 dan kue B dijual Rp30.000. Biaya produksi kue A Rp10.000 dan kue B Rp12.000. Tentukan keuntungan maksimum!
Pembahasan:
Keuntungan: A = 25.000 − 10.000 = 15.000; B = 30.000 − 12.000 = 18.000
f(x, y) = 15.000x + 18.000y
Kendala: 200x + 100y ≤ 2000 → 2x + y ≤ 20
100x + 150y ≤ 1500 → 2x + 3y ≤ 30
x ≥ 0, y ≥ 0
Titik potong 2x + y = 20 dan 2x + 3y = 30:
(2) − (1): 2y = 10 → y = 5, x = 7,5
Titik pojok: A(0, 0), B(10, 0), C(7,5; 5), D(0, 10).
- A(0, 0): f = 0
- B(10, 0): f = 150.000
- C(7,5; 5): f = 112.500 + 90.000 = 202.500
- D(0, 10): f = 180.000
Keuntungan maksimum = Rp202.500, dicapai di titik C(7,5; 5).
Latihan Soal – Tingkat Mudah
1.
Tentukan nilai maksimum dari f(x, y) = 3x + 2y pada daerah dengan titik pojok: A(0, 0), B(5, 0), C(0, 4).
2.
Tentukan nilai minimum dari f(x, y) = 2x + y pada daerah dengan titik pojok: A(1, 2), B(4, 0), C(3, 3).
3.
Tentukan nilai maksimum dari f(x, y) = x + 3y pada daerah dengan titik pojok: A(0, 0), B(6, 0), C(2, 4), D(0, 5).
4.
Tentukan nilai minimum dari f(x, y) = 5x + 2y pada daerah dengan titik pojok: A(0, 3), B(2, 1), C(4, 0).
5.
Tentukan nilai maksimum dari f(x, y) = 2x + 4y pada daerah dengan titik pojok: A(0, 0), B(3, 0), C(2, 3), D(0, 4).
Latihan Soal – Tingkat Sedang
6.
Tentukan nilai maksimum f(x, y) = 4x + 5y dengan kendala: x + y ≤ 7, 2x + y ≤ 10, x ≥ 0, y ≥ 0.
7.
Tentukan nilai minimum f(x, y) = 3x + 4y dengan kendala: x + 2y ≥ 8, x + y ≥ 5, x ≥ 0, y ≥ 0.
8.
Tentukan nilai maksimum f(x, y) = 2x + 3y dengan kendala: x + y ≤ 10, x + 3y ≤ 18, x ≤ 8, x ≥ 0, y ≥ 0.
9.
Tentukan nilai minimum f(x, y) = 5x + 3y dengan kendala: 2x + y ≥ 8, x + 2y ≥ 8, x ≥ 0, y ≥ 0.
10.
Tentukan nilai maksimum f(x, y) = 6x + 4y dengan kendala: 3x + 2y ≤ 18, x + 2y ≤ 10, x ≥ 0, y ≥ 0.
Latihan Soal – Tingkat Sulit
11.
Sebuah pabrik membuat produk P dan Q. Produk P membutuhkan 3 jam mesin A dan 2 jam mesin B. Produk Q membutuhkan 2 jam mesin A dan 4 jam mesin B. Mesin A tersedia 18 jam dan mesin B 20 jam. Keuntungan P = Rp50.000 dan Q = Rp40.000. Tentukan keuntungan maksimum!
12.
Tentukan nilai minimum dan maksimum f(x, y) = 4x + 6y dengan kendala: x + 2y ≤ 14, 3x + y ≤ 15, x + y ≥ 4, x ≥ 0, y ≥ 0.
13.
Seorang petani memiliki lahan 10 hektar. Ia ingin menanam jagung dan kedelai. Jagung membutuhkan 2 pekerja/hektar dan kedelai 3 pekerja/hektar. Tersedia 24 pekerja. Modal jagung Rp5 juta/hektar dan kedelai Rp4 juta/hektar. Modal tersedia Rp40 juta. Keuntungan jagung Rp3 juta/hektar dan kedelai Rp4 juta/hektar. Tentukan keuntungan maksimum!
14.
Tentukan nilai minimum f(x, y) = 8x + 10y dengan kendala: 3x + 2y ≥ 12, x + 3y ≥ 9, 2x + y ≥ 8, x ≥ 0, y ≥ 0.
15.
Sebuah perusahaan transportasi memiliki 2 jenis truk: truk besar (kapasitas 6 ton, biaya Rp500.000/trip) dan truk kecil (kapasitas 2 ton, biaya Rp200.000/trip). Perusahaan harus mengangkut minimal 30 ton barang. Truk besar tersedia 4 unit dan truk kecil 8 unit. Tentukan biaya minimum pengangkutan!