Menentukan fungsi tujuan yang memiliki nilai maksimum pada daerah penyelesaian sistem pertidaksamaan

Selain metode "uji titik pojok", terdapat metode lain yang digunakan sebagai alternatif untuk menentukan nilai optimum dari suatu fungsi tujuan. Metode alternatif tersebut dikenal sebagai metode garis selidik. Pada artikel ini kita akan membahas Program Linear : Nilai Optimum dengan Garis Selidik. Untuk memudahkan mempelajari materi Program Linear : Nilai Optimum dengan Garis Selidik ini, sebaiknya kita harus menguasai dulu materi "Persamaan dan Grafik Bentuk Linear", "Menentukan Daerah Penyelesaian (Arsiran) sistem Pertidaksamaan", dan "Menyusun Model Matematika".

Jika bentuk umum fungsi tujuan dinotasikan dengan $ z = f(x, y) = ax + by \, $ maka bentuk umum garis selidik dinotasikan dengan $ \, ax + by = k , $ dengan $ \, k \in R \, $ dimana $ k \, $ sembarang bilangan yang kita pilih. Garis selidik $ ax + by = k (k \in R) $ merupakan himpunan garis-garis yang sejajar. Dua buah garis dikatakan sejajar jika memiliki gradien yang sama. Pada dasarnya, metode garis selidik dilakukan dengan cara menggeser garis selidik secara sejajar ke arah kiri, kanan, atas, atau bawah sampai garis tersebut memotong titik-titik pojok daerah himpunan penyelesaian sistem pertidaksamaan linear dua variabel. Untuk fungsi tujuan maksimum, titik optimum dicapai jika semua himpunan penyelesaian dari kendala-kendala sistem pertidaksamaan linear dua variabel berada di bawah atau sebelah kiri garis selidik. Adapun untuk fungsi tujuan minimum, titik optimum dicapai jika semua himpunan penyelesaian berada di atas atau sebelah kanan garis selidik dengan syarat koefisien $ y \, $ harus positif ($ b > 0 $). Jika koefisien $ y \, $ negatif ($b < 0$), maka berlaku sebaliknya.

Langkah-langkah Menentukan nilai Optimum dengan Garis Selidik : i). Buat model matematikanya yang teridiri dari kendala dan fungsi tujuan; ii). Tentukan grafik dan daerah himpunan penyelesaiannya (DHP); iii). Tentukan persamaan garis selidik dari fungsi tujuannya; Untuk mendapatkan nilai maksimum, geser garis selidik secara sejajar ke arah kanan atau atas sampai memotong titik paling jauh dari daerah himpunan penyelesaian. Titik yang paling jauh tersebut merupakan titik yang memaksimumkan fungsi tujuan. iv). Untuk mendapatkan nilai minimum, geser garis selidik secara sejajar ke arah kiri atau bawah sampai memotong titik paling dekat dari daerah himpunan penyelesaian. Titik yang paling dekat tersebut merupakan titik yang meminimumkan fungsi tujuan. Perhatikan gambar ilustrasi garis selidik berikut ini :

Berdasarkan gambar tersebut, titik A merupakan titik yang meminimum kan fungsi tujuan (objektif ) dan titik D merupakan titik yang me maksimum kan tujuan.

Contoh soal nilai optimum dengan garis selidik : 1). Tentukan nilai maksimum dari fungsi tujuan $ z = f(x, y) = 3x + 4y \, $ dan fungsi kendalanya adalah $ x + 2y \leq 10 , \, 4x + 3y \leq 24, \, x \geq 0 , \, y \geq 0 $ Penyelesaian : *). Menentukan grafik dan daerah himpunan penyelesaiannya (DHP) :

Silahkan baca : "Persamaan dan Grafik Bentuk Linear", dan "Menentukan Daerah Penyelesaian (Arsiran) sistem Pertidaksamaan".

*). Fungsi tujuannya : $ z = f(x, y) = 3x + 4y $, bentuk umum garis selidiknya adalah $ 3x + 4y = k $ . Untuk memudahkan menggambar, kita pilih nilai $ k = 12 \, $ sehingga persamaan garis selidiknya adalah $ 3x + 4y = 12 $. gambar garis selidiknya :

Berdasarkan gambar garis selidik di atas, garis selidik yang digeser secara sejajar ke kanan atau ke atas, memotong titik terjauh dari himpunan penyelesaian sistem pertidaksamaan linear dua variabel yang diketahui, yaitu titik B. Koordinat titik B setelah dicari adalah $(\frac{18}{5}, \frac{16}{5})$. Artinya fungsi tujuannya maksimum pada titik pojok B. *). Menentukan nilai maksimumnya dengan substitusi titik B ke fungsi tujuannya : $ f(x,y) = f(\frac{18}{5}, \frac{16}{5}) = 3 \times \frac{18}{5} + 4 \times \frac{16}{5} = 23,6 $. Jadi, nilai maksimum dari fungsi tujuannya adalah 23,6. *). Bagaimana dengan nilai minimumnya? Perhatikan gambar garis selidiknya, garis selidik harus digeser ke kiri atau ke bawah seperti gambar berikut.

Berdasarkan gambar tersebut, titik O(0, 0) merupakan titik paling dekat dari himpunan penyelesaian sistem pertidaksamaan linear dua variabel yang diberikan. Dengan demikian, nilai minimum fungsi tujuan yang diberikan dicapai pada titik O(0, 0), yaitu $ z = f(x, y) = 3x + 4y = 3(0) + 4(0) = 0 $ . Sehingga nilai minimum fungsi tujuannya adalah 0. 2). Tentukan nilai maksimum fungsi tujuan $ f(x,y) = 80x + 125y \, $ yang memenuhi kendala $ x + y \leq 350, \, 600x + 1.000y \leq 300.000 , \, x \geq 0, \, y \geq 0 $. Penyelesaian : *). Gambar grafik dan DHP nya :

*). Fungsi tujuan dari masalah program linear tersebut adalah $ 80x + 125y $. Bentuk umum garis selidiknya $ ax + by = k \, $ , kita pilih $ k = 10.000 , \, $ sehingga garis selidiknya menjadi $ 80x + 125y = 10.000 \, $ atau $ \, 16x + 25y = 2.000 $ . catatan : nilai $ k \, $ bebas kita pilih, tapi kita pilih yang mudah dalam menggambar. *). Oleh karena yang dicari adalah nilai maksimum maka geser garis selidik ke kanan atau atas seperti pada gambar berikut. gambar garis selidik dan pergeserannya :

*). Berdasarkan gambar di atas, garis selidik yang digeser secara sejajar ke kanan atau ke atas, memotong titik terjauh dari himpunan penyelesaian pertidaksamaan linear dua variabel di titik B (125, 225). Dengan demikian, nilai fungsi tujuan $ z = 80x + 125y \, $ maksimum dicapai di titik B (125, 225). *). Menentukan nilai maksimum dengan substitusi titik B ke fungsi tujuan : $ f(x,y) = 80x + 125y \rightarrow f(125,225) = 80 \times 125 + 125 \times 225 = 38.125 $. Jadi, nilai maksimum fungsi tujuan $ z = 80x + 125y \, $ adalah 38.125.

Catatan :

Dari dua contoh soal di atas, dapat disimpulkan bahwa metode garis selidik digunakan hanya untuk menentukan titik pojok mana yang menyebabkan fungsi tujuannya memiliki nilai optimum. Hanya saja metode garis selidik memerlukan ketelitian dalam menggambar dan menggeser garis selidiknya, jangan sampai salah.

HOME MATEMATIKA SMA PROGRAM LINEAR

Tentukan titik potong garis kendala yang diberikan terhadap sumbu x dan sumbu y untuk menentukan titik kordinat.
Gambarkan garis kendala ke dalam grafik sesuai dengan titik koordinat yang telah diperoleh pada langkah 1.
Tentukan daerah himpunan penyelesaian yang sesuai dengan tanda pertidaksamaan. Jika masih bingung bagaimana menentukan daerah himpunan penyelesaian, anda dapat membaca postingan Menentukan Himpunan Penyelesaian Sistem Pertidaksamaan Linear.
Tentukan titik-titik pojok yang berada dalam daerah himpunan penyelesaian dan substitusi nilainya ke dalam fungsi objektif atau fungsi tujuan untuk melihat titik mana yang menghasilkan nilai maksimum. Untuk tahap ini, kita juga dapat menggunakan Garis Selidik.

Contoh soal :

Apabila x, y anggota bilangan real terletak pada himpunan penyelesaian sistem pertidaksamaan x ≥ 0; y ≥ 0; 2x + y ≤ 8; dan x + 3y ≤ 9 maka tentukanlah nilai maximum fungsi sasaran x + 2y pada himpunan penyelesaian tersebut.

Pembahasan : Tentukan titik potong masing-masing kendala terhadap sumbu x dan sumbu y sebagai berikut : Untuk 2x + y = 8 misal x = 0 , y = 8 → (0,8) misal y = 0 , x = 4 → (4,0) Untuk x + 3y = 9 misal x = 0 , y = 3 → (0,3) misal y = 0 , x = 9 → (9,0) Selanjutnya, gambarkan garis tersebut ke dalam grafik seperti berikut :

Setelah itu tentukan daerah himpunan penyelesaiannya. Karena pertidaksamaan bertanda lebih kecil dari sama dengan (≤), maka daerah himpunan penyelesaiannya adalah daerah di bawah/kiri garis.

Dari gambar dapat dilihat bahwa ada tiga titik pojok yaitu titik A, B, dan C. Titik A dan C dapat dengan mudah ditentukan karena merupakan titik potong terhadap sumbu y dan sumbu x. Titik B merupakan perpotongan antara garis 2x + y = 8 dan x + 3y = 9. Dari grafik dapat dilihat bahwa kedua garis itu berpotongan tepat di titik (3,2). Langkah terakhir, substitusi nilai x dan y dari masing-masing titik pojok ke fungsi tujuan F(x,y) = x + 2y sebagai berikut : A(0,3) → F(0,3) = 0 + 2(3) = 6
B(3,2) → F(3,2) = 3 + 2(2) = 7 → maksimum.
C(4,0) → F(4,0) = 4 + 2(0) = 4 Jadi nilai maksimum fungsi tujuannya adalah 7 yaitu pada titik B.
Jika diketahui A = x + y dan B = 5x + y, maka tentukanlah jumlah nilai maksimum dari A dan B pada sistem pertidaksamaan x ≥ 0; y ≥ 0; x + 2y ≤ 12; 2x + y ≤ 12.
Pembahasan : Tentukan titik potong masing-masing kendala terhadap sumbu x dan sumbu y sebagai berikut : Untuk x + 2y = 12 misal x = 0 , y = 6 → (0,6) misal y = 0 , x = 12 → (12,0) Untuk 2x + y = 12 misal x = 0 , y = 12 → (0,12) misal y = 0 , x = 6 → (6,0)

Selanjutnya, gambarkan garis tersebut ke dalam grafik seperti di atas dan tentukan daerah himpunan penyelesaiannya.

Dari gambar dapat dilihat bahwa ada tiga titik pojok yaitu titik A, B, dan C. Titik A dan C dapat dengan mudah ditentukan karena merupakan titik potong terhadap sumbu y dan sumbu x. Titik B merupakan perpotongan antara garis x + 2y = 12 dan 2x + y = 12. Dari grafik dapat dilihat bahwa kedua garis itu berpotongan tepat di titik (4,4) → pada gambar di atas, 1 kotak mewakili 2 satuan. Langkah terakhir, substitusi nilai x dan y dari masing-masing titik pojok ke fungsi tujuan A(x,y) = x + y dan B(x,y) = 5x + y sebagai berikut : A(0,6) → A(0,6) = 0 + 6 = 6
B(4,4) → A(4,4) = 4 + 4 = 8 → maksimum.
C(6,0) → A(6,0) = 6 + 0 = 6 A(0,6) → B(0,6) = 5(0) + 6 = 6
B(4,4) → B(4,4) = 5(4) + 4 = 24

C(6,0) → B(6,0) = 5(6) + 0 = 30 → maksimum. Jadi jumlah nilai maksimum fungsi tujuan A + B = 8 + 30 = 38
Tentukan nilai maksimum dari fungsi tujuan 4x + 3y dari sistem pertidaksamaan yang memiliki himpunan penyelesaian seperti gambar di bawah ini.

Pembahasan : Pada gambar di atas, daerah yang diarsir (berwarna gelap) merupakan daerah himpunan penyelesaian sistem pertidaksamaan. Daerah tersebut memiliki 4 titik pojok atau titik sudut yang di antaranya adalah titik (0,0). Karena kita akan mencari nilai maksimum fungsi objektif atau fungsi tujuan, maka titik (0,0) tentu tidak memenuhi.

Dari gambar di atas, terdapat 3 titik pojok yang salah satunya menghasilkan nilai maksimum jika disubstitusikan ke fungsi tujuan, yaitu titik A, B, dan C. Sekarang yang harus dilakukan adalah menentukan titik-titik tersebut. Titik A dan C dapat dengan mudah diketahui karena merupakan titik potong garis terhadap sumbu x dan sumbu y. Adapun titik A (0,4) dan titik C (3,0). Sementara itu, titik B merupakan perpotongan antara dua garis yang belum kita ketahui persamaan garisnya. Oleh karena itu, untuk mengetahui titik B sebaiknya kita tentukan terlebih dahulu persamaan garis yang saling berpotongan di titik itu dengan cara sebagai berikut :

Sesuai dengan skema dan rumus di atas, maka :

4x + 8y = 32 → x + 2y = 8 untuk a = 6, b = 3 6x + 3y = 18 → 2x + y = 6 Titik B (titik potong antara x + 2y = 8 dan 2x + y = 6) dapat dicari dengan metode eliminasi.

Selanjutnya substitusi masing-masing titik (A, B, dan C) ke fungsi tujuan f(x,y) = 4x + 3y. A (0,4) → f(x,y) = 4(0) + 3(4) = 12
B (4/3, 10/3) → f(x,y) = 4(4/3) + 3(10/3) = 46/3 = 15,3
C (3,0) → f(x,y) = 4(3) + 3(0) = 12
Jadi nilai maksimum fungsi tujuan dengan kendala seperti gambar di atas adalah 15,3 yaitu pada titik B.