Program Linear - Metode Grafik
Mencari Nilai Optimum PL dengan Metode Grafik
Pemrograman Linear merupakan metode matematik dalam mengalokasikan sumber daya yang langka untuk mencapai suatu tujuan seperti memaksimumkan keuntungan dan meminimumkan biaya. Sumber daya yang langka tersebut merupakan kendala, yang berupa fungsi linear, sedangkan tujuan merupakan fungsi tujuan yang berupa fungsi linear juga. PL diterapkan dalam masalah bisnis, ekonomi, industri, militer, sosial, teknik, dan lain-lain.
Penyelesaian PL dengan metode grafik dapat dilakukan dengan 3 cara, yaitu :
Metode Garis Selidik
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.
Bentuk umum fungsi tujuan dinotasikan dengan 
Bentuk umum garis selidik dinotasikan dengan 
dgn 
. Dimana 
sembarang bilangan yang dipilih.
Langkah-langkah penyelesaian dengan metode garis selidik:
1. Membuat model matematika
2. Menentukan daerah himpunan penyelesaian
3. Menentukan persamaan garis selidik dan fungsi tujuannya
4. Mencari nilai minimum atau maksimum
Nilai maksimum didapatkan dengan menggeser garis selidik secara sejajar ke arah kanan atau atas sampai memotong titik paling jauh dari daerah himpunan penyelesaian.
Nilai minimum didapatkan dengan menggeser garis selidik secara sejajar ke arah kiri atau bawah sampai memotong titik paling dekat dari daerah himpunan penyelesaian.
Metode Titik-Titik Sudut
Metode titik sudut dilakukan dengan cara menentukan nilai optimum dari fungsi tujuan yang dicapai (dipenuhi) oleh salah satu titik sudut dari daerah himpunan penyelesaian.
Langkah-langkah penyelesaian dengan metode titik-titik sudut :
1. Menentukan daerah layak
2. Menentukan koordinat titik-titik sudut daerah layak
3. Menentukan nilai fungsi dari semua titik sudut
4. Menentukan nilai fungsi yang optimal
Metode Gradien
Metode gradien adalah suatu metode yang secara langsung menggunakan gradien. Dengan metodegradien, akan langsung dapat kita tentukan titik pojok yang menyebabkan suatu fungsi tujuan memiliki nilai optimum (maksimum atau minimum).
Langkah penyelesaian menggunakan metode gradien :
1. Menentukan gradien garis dari semua kendala dan fungsi tujuan dengan 
untuk fungsi 
2. Mengurutkan nilai gradien dari kecil ke besar
3. Menentukan posisi nilai gradien fungsi tujuan, misalkan terletak di antara nilai gradien kendala ke-i dan ke-j
4. Menentukan titik optimal yang merupakan perpotongan garis dari kendala ke-i dan garis dari kendala ke-j
Misalkan ada fungsi tujuan dengan gradien 
, dan terdapat dua kendala yaitu kendala I dengan gradien 
dan kendala II dengan gradien 
, maka akan ada tiga kemungkinan yang terjadi, yaitu :
1. 
artinya nilai optimum diperoleh pada titik pojok garis pertama.
2. 
artinya nilai optimum diperoleh pada perpotongan kedua garis.
3. 
artinya nilai optimum diperoleh pada titik pojok garis kedua.
Syarat metode gradien :
1. Semua gradien fungsi tujuan dan kendalanya harus negatif
2. Tanda ketaksamaannya harus sama semua (
semua atau 
semua)
3. Banyaknya kendala bisa lebih dari 2
4. Dibatasi oleh sumbu 
dan sumbu 
dengan 
dan 
Bentuk umum garis selidik dinotasikan dengan dgn . Dimana sembarang bilangan yang dipilih.
Langkah-langkah penyelesaian dengan metode garis selidik:
1. Membuat model matematika
2. Menentukan daerah himpunan penyelesaian
3. Menentukan persamaan garis selidik dan fungsi tujuannya
4. Mencari nilai minimum atau maksimum
Nilai maksimum didapatkan dengan menggeser garis selidik secara sejajar ke arah kanan atau atas sampai memotong titik paling jauh dari daerah himpunan penyelesaian.
Nilai minimum didapatkan dengan menggeser garis selidik secara sejajar ke arah kiri atau bawah sampai memotong titik paling dekat dari daerah himpunan penyelesaian.
Metode Titik-Titik Sudut
Metode titik sudut dilakukan dengan cara menentukan nilai optimum dari fungsi tujuan yang dicapai (dipenuhi) oleh salah satu titik sudut dari daerah himpunan penyelesaian.
Langkah-langkah penyelesaian dengan metode titik-titik sudut :
1. Menentukan daerah layak
2. Menentukan koordinat titik-titik sudut daerah layak
3. Menentukan nilai fungsi dari semua titik sudut
4. Menentukan nilai fungsi yang optimal
Metode Gradien
Metode gradien adalah suatu metode yang secara langsung menggunakan gradien. Dengan metodegradien, akan langsung dapat kita tentukan titik pojok yang menyebabkan suatu fungsi tujuan memiliki nilai optimum (maksimum atau minimum).
Langkah penyelesaian menggunakan metode gradien :
1. Menentukan gradien garis dari semua kendala dan fungsi tujuan dengan
untuk fungsi
2. Mengurutkan nilai gradien dari kecil ke besar
3. Menentukan posisi nilai gradien fungsi tujuan, misalkan terletak di antara nilai gradien kendala ke-i dan ke-j
4. Menentukan titik optimal yang merupakan perpotongan garis dari kendala ke-i dan garis dari kendala ke-j
Misalkan ada fungsi tujuan dengan gradien , dan terdapat dua kendala yaitu kendala I dengan gradien dan kendala II dengan gradien , maka akan ada tiga kemungkinan yang terjadi, yaitu :
1. artinya nilai optimum diperoleh pada titik pojok garis pertama.
2. artinya nilai optimum diperoleh pada perpotongan kedua garis.
3. artinya nilai optimum diperoleh pada titik pojok garis kedua.
Syarat metode gradien :
1. Semua gradien fungsi tujuan dan kendalanya harus negatif
2. Tanda ketaksamaannya harus sama semua ( semua atau semua)
3. Banyaknya kendala bisa lebih dari 2
4. Dibatasi oleh sumbu dan sumbu dengan dan
Nomor 1
Berapa nilai maksimum dari fungsi dengan kendala sebagai berikut. (i) (ii) (iii) (iv)
Nomor 2
Tentukan nilai maksimum dari fungsi yang memenuhi kendala berikut: (i) (ii) (iii)