LINEAR PROGRAMMING
PERTEMUAN KE-7
Model Programasi Linear
Adalah sebuah model matematis yang
bersifat umum yang digunakan untuk
mengalokasikan faktor produksi atau
sumber daya yang jumlahnya terbatas
secara optimal, sehingga dapat
menghasilkan laba maksimal atau biaya
minimal
Fungsi-Fungsi Dalam PL
1. Fungsi Tujuan (objective function)
Fungsi yang menyatakan tujuan yang
akan dicapai, dapat berupa laba maksimal
atau biaya minimal
2. Fungsi Kendala (contrains or subject to)
Fungsi yang menyatakan batasan atau kendala dari
faktor produksi yang dimiliki
Simbol yang digunakan : <, >, =
3. Fungsi Status (status function)
Fungsi yang menyatakan bahwa setiap variabel
yang terdapat di dalam model programasi linear
tidak boleh negatif
Asumsi Dasar PL
1. Certainty
Angka yang diasumsikan dlm [Link]
dan [Link] secara pasti diketahui dan
tidak berubah selama waktu dipelajari
2. Proporsionality
Alokasi sumber daya dengan goal yang
ingin dicapai harus proporsional
3. Additivity
Total dari semua aktivitas adalah sama dengan
jumlah dari aktivitas individual
4. Divisibility
Jumlah produk yang akhirnya direkomendasikan
dalam kondisi optimum, dapat berupa pecahan
bukan bilangan bulat
5. Non-negatif variable
Semua variabel bukan negatif, bisa nol atau
positif (negatif dalam kuantitas fisik a/d mustahil)
Fungsi Matematika untuk
Masing-masing Fungsi
1. Fungsi Tujuan
Maks. Laba Z = c1x1 + c2x2 + … + cnxn
2. Fungsi Kendala
a11x1 + a12x2 + … + a1nxn < b1
a21x1 + a22x2 + … + a2nxn < b2
.. .. .. ..
.. .. .. ..
am1x1 + am2x2 + … + amnxn < bn
3. Fungsi Status
x1 ; x2 ……………….. Xn > 0
Metode-Metode Dlm PL
Metode
Programasi Linear
Metode Aljabar Metode Grafik
Simpleks Primal Simpleks M-Besar
Simpleks Dual Simpleks Dua Fase
Perbedaan Metode Solusi
Karakteristik Simpleks
pada formulasi Grafis Simpleks Big – M
masalah
Jumlah 2 >2 >2
Variabel
Jenis fungsi maksimisasi dan maksimisasi dan maksimisasi dan
tujuan minimisasi minimisasi minimisasi
Jenis fungsi semua bentuk Pertidak-samaan Pertidaksamaan
kendala bertanda “ < “ bertanda “ > “ atau
persamaan “=“
METODE GRAFIK
metode digunakan untuk
permasalahan dengan jumlah
variabel sebanyak dua,
dengan tanda
pertidaksamaan pada fungsi
kendala bebas
Contoh Soal
Sebuah perusahaan pabrikasi hendak memproduksi 2 buah produk, yaitu
x1 dan x2 yang masing-masing memberikan laba bersih sebesar Rp.4000, -
dan Rp.5000,- per unitnya. Untuk membuat kedua produk tersebut
diperlukan 2 buah bahan baku (bb), yaitu bb-A dan bb-B. Bahan baku A
tersedia maksimal 12 ton dan bahan baku B tersedia tidak boleh lebih dari
24 ton.
Setiap unit produk x1 memerlukan 1 ton bb-A dan 4 ton bb-B. Sedang
setiap unit produk x2 memerlukan 3 ton bb-A dan 3 ton bb-B.
Buatlah formulasi persoalan tersebut, dan hitunglah berapa komposisi
jumlah bb-A dan bb-B yang digunakan agar perusahaan mendapatkan
keuntungan maksimal ?
Matriks Persoalan
Uraian Produk Produk Tanda kapasitas
X1 X2 Kendala
Bb-A 1 3 < 12
Bb-B 4 3 < 24
Laba 4 5 - -
(000 Rp)
Formulasi Persoalan
x1 = Jumlah produk x1
X2 = Jumlah produk x1
F. Tujuan : Maks. Laba Z = 4x1 + 5x2
F. Pembatas : x1 + 3x2 < 12 ( bb-A )
4x1 + 3x2 < 24 ( bb-B )
F. Status : x 1 ; x2 > 0
Penyelesaian Aljabar Analitik
x1 + 3x2 < 12
Jika x1 = 0 x2 = 4
Jika x2 = 0 x1 = 12
4x1 + 3x2 < 24
Jika x1 = 0 x2 = 8
Jika x2 = 0 x1 = 6
Grafik
8 (8,0)
(4,0)
4
( 4, 2 2/3)
2 Daerah
Feasible
(6,0) (12,0)
0 2 4 6 8 10 12 14
Jadi, untuk mendapatkan laba maks, perusahaan harus memproduksi 4
unit produk x1 dan 2 2/3 unit produk x2, sehingga diperoleh laba
maksimal sebesar Rp.29.338,33
Metode Simpleks
Digunakan untuk permasalahan
dengan jumlah variabel sebanyak
dua atau lebih, dengan tanda
pertidaksamaan pada fungsi kendala
adalah kurang dari atau sama
dengan.
Langkah-Langkah Metode
Simpleks Primal
1. Ubahlah tanda pertidaksamaan lebih kecil atau sama dengan
(<) yang terdapat pada persamaan fungsi kendala menjadi
tanda sama dengan (=). Caranya dengan memasukkan
variabel slek (slack variable atau S) yang bernilai positif.
Adapun banyaknya variabel slek tersebut bergantung pada
fungsi kendala.
Dalam contoh soal, ada 2 buah tanda < pada persamaan
fungsi kendala. Jadi gunakan +S1 dan +S2.
F/tujuan : Zmax = 4x1 + 5x2
F/kendala : x1 + 5x2 + S1 …….. = 12
4x1 + 3x2 ….. + S2 …= 24
F/status : x1 ; x2 …………….. > 0
2. Kemudian varibel-variabel slek tadi kita tambahkan pada
persamaan fungsi tujuan tetapi koefisiennya nol.
F/tujuan : Zmax = 4x1 + 5x2 + 0S1 + 0S2
F/kendala : x1 + 5x2 + S1 …….. = 12
4x1 + 3x2 ….. + S2 …= 24
F/status : x1 ; x2 ………………. > 0
3. Kesemua variabel tadi, baik varibel keputusan ( x1 dan x2 ) maupun
varibel slek ( S1 dan S2 ) tidak boleh negatif nilainya atau harus > nol.
F/tujuan : Zmax = 4x1 + 5x2 + 0S1 + 0S2
F/kendala : x1 + 5x2 + S1 …….. = 12
4x1 + 3x2 ….. + S1….= 24
F/status : x1 ; x2 ; S1 ; S2 …… > 0
4. Hasil langkah ke-1 s.d ke-3, masukkan ke dalam tabel
simpleks primal ( tabel 1)
5. Tentukanlah variabel dasarnya, yaitu varibel yang besarnya sama
dengan nilai sisi kanan pada fungsi kendala pada saat belum
dihasilkan produk.
6. Lakukanlah langkah iterasi. Hitunglah nilai-nilai baris Z iterasi ke-1
7. Hitunglah nilai-nilai pada baris C-Z pada iterasi ke-1
8. Tentukanlah variabel masuk (entering variabel) atau produk yang
akan dibuat terlebih dahulu, yaitu dengan cara memilih nilai C-Z
yang terbesar (karena fungsi tujuan adalah maksimisasi laba)
Pada contoh soal, variabel masuk adalah x2 ( x2 berada satu kolom
dengan angka 5 )
9. Tentukanlah kolom kunci, yaitu kolom-kolom yang sejajar dengan
variabel masuk
10. Hitunglah nilai rasio masing-masing, dengan rumus :
Rasio = ( nilai kanan / kolom kunci )
11. Tentukan varibel keluar (leaving variabel), yaitu dengan cara memilih
nilai rasio yang terkecil dan positif.
Pada contoh soal, leaving variabel adalah S1 ( S1 berada satu baris
dengan niali rasio yang terkecil dan positif )
12. Tentukan baris kunci
13. Angka yang terdapat pada perpotongan kolom kunci dan baris kunci
disebut angka kunci. Pada contoh soal yaitu angka 3.
Kemudian angka kunci tsb nilainya dijadikan nilai 1, dan disebut “pivot”. Karena
angka kunci untuk menjadi pivot dibagi g=dgn bil. 3,
maka seluruh angka pada baris kunci juga dibagi dengan 3
14. Hitunglah nilai-nilai pada baris 0S2 pada iterasi ke-2 ( baris S2
baru ) dengan cara :
Baris S2 lama : 4 3 0 1 24
Baris Pivot : 3(1/3 1 1/3 0 4) -
Baris S2 baru : 3 0 -1 1 12
15. Hitung kembali nilai-nilai Z yang baru
16. Hitung pula nilai C-Z yang baru
17. Periksalah apakah semua nilai C-Z yang baru sudah tidak ada nilai
negatif lagi. Bila iya, maka proses pehitungan dihentikan karena solusi
sudah optimal. Tetapi jika tidak, maka dilanjutkan ke langkah 18.
18. Ulangilah langkah mulai langkah 8
Tabel Iterasi
Iterasi ke- C 4 5 0 0 Nilai
Var. Dasar Kanan
Rasio
X1 X2 S1 S2
0 S1 1 3 1 0 12 12/3 = +4
1
0 S2 4 3 0 1 24 24/3 = +8
Z 0 0 0 0 0
C-Z 4 5 0 0 -
5 X2 1/3 1 1/3 0 4 4/(1/3) =
2 +12
0 S2 3 0 -1 1 12 12/3 = +4
Z 5/3 5 5/3 0 20 20/(5/3) =
+12
C-Z 7/3 0 -5/3 0 -
5 X2 0 1 4/9 -1/9 8/3
3
4 X1 1 0 -1/3 1/3 4
Z 4 5 8/9 7/9 88/3
C-Z 0 0 -8/9 -7/9 -
SEKIAN…
PERSIAPKAN UNTUK UTS YA….