Masalah Program Linear

Program linear akan sangat berguna bagi Anda ketika dihadapkan pada beberapa pilihan dengan kendala-kendala tertentu, yang menuntut Anda untuk mengambil keputusan yang optimum (maksimum atau minimum). Oleh karena itu, permasalahan dalam program linear selalu berhubungan dengan pengoptimalisasian fungsi tujuan berdasarkan kendala yang membatasinya.Suatu program linear dua variabel x dan y memiliki satu fungsi tujuan yang dioptimumkan. Bentuk umum dari fungsi tujuan tersebut adalah sebagai berikut.

z = f(x, y) = ax + by dengan a, b bilangan real, a ≠ 0 dan b ≠ 0 Pada Contoh Soal ini , fungsi tujuan yang ingin dimaksimumkan adalah z = f(x, y) = 1.500x + 1.250y, dan fungsi kendalanya adalah x + y ≤ 60

2.500x + 2.000y ≤ 140.000
x ≥ 0
y ≥ 0

Tujuan dari permasalahan tersebut adalah menentukan banyaknya buah semangka dan melon yang harus dibeli/disediakan agar diperoleh keuntungan maksimum. Dalam memaksimumkan suatu fungsi tujuan z = ax + by, Anda perlu menentukan titik-titik (x, y) yang menghasilkan nilai z terbesar. Titik (x, y) yang menghasilkan nilai z terbesar harus memenuhi setiap pertidaksamaan linear pada fungsi kendala yang diberikan. Hampir sama dengan hal itu, dalam meminimumkan suatu fungsi, Anda perlu menentukan titik-titik (x, y). Namun dalam meminimumkan fungsi tujuan, dicari titik (x, y) yang menghasilkan nilai z terkecil. Berdasarkan uraian tersebut, diketahui bahwa model matematika yang diperoleh pada Contoh Soal 1.9 merupakan contoh permasalahan dalam upaya memaksimumkan fungsi tujuan. Dengan demikian, masalah program linearnya sebagai berikut. fungsi tujuan z = f(x, y) = 1.500x + 1.250y dengan kendalanya adalah x + y ≤ 60
2.500x + 2.000y ≤ 140.000
x ≥ 0
y ≥ 0
Dengan menggunakan konsep sistem pertidaksamaan linear dua variabel, diperoleh daerah penyelesaian seperti pada gambar berikut.

Selanjutnya, cari koordinat titik C yang merupakan perpotongan antara garis x + y = 60 dan 2.500x + 2.000y = 140.000. Gunakan metode gabungan eliminasi dan substitusi

Substitusikan nilai x = 40 ke persamaan x + y = 60 diperoleh
40 + y = 60
y = 60 – 40
y = 20
Jadi, koordinat titik C adalah (40, 20). Dari permasalahan ini diketahui koordinat titik sudut daerah penyelesaian dari sistem tersebut adalah A(0, 60), B(56, 0), C(40, 20) dan O(0, 0). Oleh karena tujuan dari permasalahan ini adalah ingin memaksimumkan nilai z maka tentukan dari keempat titik tersebut yang membuat nilai z maksimum, dengan cara menyubstitusikannya ke fungsi z = f(x, y) = 1.500x + 1.250y.
• Untuk A (0, 60) maka z = 1.500(0) + 1.250(60) = 75.000
• Untuk B (56, 0) maka z = 1.500(56) + 1.250(0) = 84.000
• Untuk C (40, 20) maka z = 1.500(40) + 1.250(20) = 85.000
• Untuk O (0, 0) maka  z = 1.500(0) + 1.250(0) = 0

Fungsi z maksimum di titik C (40, 20) dengan z = 85.000

Metode yang Anda gunakan pada uraian tersebut dikenal sebagai metode titik sudut. Secara umum, langkah-langkah dalam menentukan nilai optimum masalah program linear dengan fungsi tujuan z = f(x, y) = ax + by menggunakan metode titik sudut adalah sebagai berikut.

1. Buat model matematika dari masalah program linear yang diberikan.
2. Gambarkan grafik-grafik dari setiap pertidaksamaan linear dua variabel yang diketahui.
3. Tentukan daerah himpunan penyelesaian dari sistem pertidaksamaan linear dua variabel yang terdapat pada masalah (irisan dari setiap pertidaksamaan linear dua variabel yang diberikan).
4. Tentukan titik-titik sudut pada daerah himpunan penyelesaiannya. Substitusikan titik-titik sudut tersebut ke dalam fungsi tujuan.
5. Ambil nilai yang paling besar untuk penyelesaian maksimum, atau ambil nilai yang paling kecil untuk penyelesaian minimum.

Titik yang memberikan nilai optimum (maksimum atau minimum) dinamakan titik optimum.