Suka Software Engineering

Nilai Optimum Fungsi Objektif Program Linear

Pada program linear, fungsi objektif merupakan suatu fungsi $f(x,y) = ax + by$ yang hendak ditentukan nilai optimumnya (maksimum atau minimum).

Nilai optimum suatu fungsi objektif dapat ditentukan dengan menggunakan: (1) metode garis selidik (membuat persamaan garis selidik) dan menggeser-geser garis selidik di daerah himpunan penyelesaian, atau (2). metode pengujian titik sudut (menguji nilai $(x, y)$ titik sudut dan mensubstitusikannya pada fungsi objektif program linear.

Titik sudut merupakan titik perpotongan masing-masing pertidaksamaan linear. Koordinat titik sudut dapat dihitung dengan menggunakan sistem persamaan linear dua variabel (SPLDV).

Menurut penulis, cara yang paling mudah adalah dengan menggunakan metode pengujian titik sudut, di mana kita tinggal mensubstitusi nilai titik sudut sistem pertidaksamaan linear pada grafik koordinat Cartesius.

Contoh Soal Program Linear

Nilai maksimum dari $20x + 8y$ untuk $x$ dan $y$ yang memenuhi $x+y \ge 20$ , $2x + y \le 48$ , $0 \le x \le 20$ , dan $0 \le y \le 48$ adalah …. (SPMB 2005)

Jawab:

Gambarkan pertidaksamaan tersebut ke dalam koordinat Cartesius, yaitu sbb:

Kemudian tentukan daerah himpunan penyelesaiannya, yaitu irisan dari setiap pertidaksamaan. Yaitu seperti pada grafik di bawah ini:

Titik potong haris $x = 20$ dan $2x + y = 48$ adalah $(20, 8)$

Uji titik sudut:

$(0, 48) \longrightarrow f(x,y) = 20x + 8y = 20 \cdot 0 + 8 \cdot 48 = 384$

$(20, 8) \longrightarrow f(x,y) = 20x + 8y = 20 \cdot 20 + 8 \cdot 8 = 464$

Nilai fungsi pada titik $(0, 20)$ dan $(20, 0)$ tidak perlu dihitung, karena berada di bawah garis $2x + y = 48$ , yang mana nilainya pasti lebih rendah.

Jadi, nilai maksimum fungsi objektif $f(x, y) = 20x + 8y$ program linear tersebut adalah 464.

Matematika

Sistem Pertidaksamaan Linear

Sistem pertidaksamaan linear merupakan gabungan dari beberapa pertidaksamaan linear. Pertidaksamaan linear pada topik program linear biasanya berupa pertidaksamaan yang terdiri dari 2 variabel, yaitu x dan y. Misalnya, $ax + by \le c$ .

Pada soal program linear, terkadang bentuk pertidaksamaan tidak langsung dinyatakan dalam notasi variabel, tetapi melalui suatu bahasa atau pernyataan, sehingga perlu diterjemahkan ke bentuk pertidaksamaan linear biasa. Penerjemahan ini disebut dengan pemodelan matematika, dan sistem pertidaksamaan liner yang terbentuk disebut dengan model matematika.

Himpunan penyelesaian pertidaksamaan ini dapat ditentukan dengan menggunakan metode grafik dan uji titik.

Misalnya kita ingin menggambar grafik $ax+by <= c$ . Langkah-langkahnya adalah:

Gambarkan garis $ax+by=c$ pada koordinat Cartesius.
Pilih satu (sembarang) titik yang tidak terletak pada garis tersebut, lalu substitusikan nilai titik tersebut ke pertidaksaman . Untuk mempermudah perhitungan, ujilah pertidaksamaan tersebut pada titik O (0,0).
- Jika pertidaksamaan tersebut bernilai salah, maka himpunan penyelesaiannya adalah daerah yang tidak memuat titik tersebut, dengan batasnya adalah garis $ax+by=c$
- Jika pertidaksamaan tersebut bernilai benar, maka himpunan penyelesaiannya adalah daerah yang memuat titik tersebut, dengan batasnya adalah garis $ax+by=c$

Sedangkan himpunan penyelesaian sistem pertidaksamaan linearnya adalah irisan dari semua daerah himpunan penyelesaian pertidaksamaan linear tersebut.

Contoh:

Tentukanlah himpunan penyelesaian dari:

$3x+y \le 15 \newline \newline x+2y \le 10 \newline \newline x+y \ge 5 \newline \newline x \ge 0, y \ge 0$

Jawab:

Gambarkan terlebih dahulu grafik $3x+y=15$ , $x+2y=10$ , dan $x+y=5$ pada koordinat Cartesius. Perhatikan grafik di bawah ini:

Kemudian, uji masing-masing pertidaksamaan pada titik O (0,0), untuk menentukan daerah himpunan penyelesaian setiap pertidaksamaan, dan perhatikan daerah irisannya. Maka didapat himpunan penyelesaiannya seperti pada grafik berikut:

Matematika

Program Linear

Program Linear merupakan bagian dari matematika berupa pemecahan masalah pengoptimalan, yaitu memaksimumkan atau meminimumkan suatu fungsi linear yang bergantung pada kendala (batasan) linear. Kendala ini bisa berupa pertidaksamaan atau persamaan linear.

Sebagai contoh, kita ingin memaksimalkan nilai dari $x+y$ dengan kendala:

$3x + y \le 6 \newline \newline 2x+4y \le 8 \newline \newline x+y \ge 1$

Jadi, nilai $x$ dan $y$ yang memaksimumkan nilai $x+y$ harus memenuhi ketiga pertidaksamaan (kendala) di atas.

Untuk itu, agar kamu memahami materi program linear, kamu harus memahami terlebih dahulu materi persamaan garis lurus dan sistem pertidaksamaan linear.