|
· Formulasi Masalah Program Linear
Fungsi tujuan:
Memaksimalkan/meminimumkan
f (x1, x2, …, xn) = c1x1 + c2x2 + … + cnxn
Terhadap kendala:
a11x1 + a12x2 + … + a1nxn (≤,=,≥) b1
a21x1 + a22x2 + … + a2nxn (≤,=,≥) b2
.
.
.
am1x1 + am2x2 + … + amnxn (≤,=,≥) bm ... (1)
.
.
.
am1x1 + am2x2 + … + amnxn (≤,=,≥) bm ... (1)
dengan x1, x2, ..., xn ≥ 0 ... (2)
Keterangan:
Keterangan:
(1) merupakan kendala utama
(2) merupakan kendala nonnegatif
· Penyelesaian Masalah Program Linear dengan Metode Grafik
Metode grafik digunakan untuk menyelesaikan masalah program linear dengan 2 variabel. Penyelesaian dengan metode grafik dapat menggunakan:
1. Garis selidik
2. Titik sudut
Langkah penyelesaiannya adalah menggambar garis-garis dari kendala yang diberikan, selanjutnya menentukan himpunan penyelesaian yang fisibel yaitu daerah yang memenuhi semua kendala (merupakan irisan dari semua daerah kendala).
Apabila menggunakan metode garis selidik untuk mencari nilai maks/min, gambarkan garis selidik dan menggesernya ke arah optimum hingga ditemukan titik maks/min.
1. Garis selidik
2. Titik sudut
Langkah penyelesaiannya adalah menggambar garis-garis dari kendala yang diberikan, selanjutnya menentukan himpunan penyelesaian yang fisibel yaitu daerah yang memenuhi semua kendala (merupakan irisan dari semua daerah kendala).
Apabila menggunakan metode garis selidik untuk mencari nilai maks/min, gambarkan garis selidik dan menggesernya ke arah optimum hingga ditemukan titik maks/min.
Apabila menggunakan metode titik sudut untuk mencari nilai maks/min, datalah semua titik sudut yang terjadi, lalu masukkan ke fungsi tujuan sehingga akan diperoleh titik maks/min.
· Penyelesaian Masalah Program Linear dengan Metode Simpleks
Metode simpleks digunakan untuk menyelesaikan masalah program linear dengan 2 variabel atau lebih.
Model program linear harus diubah ke bentuk kanonik.
Bentuk umum berikut
max/min z = c1x1 + c2x2 + … + cnxn
s.t. a11x1 + a12x2 + … + a1nxn ≤ b1
a21x1 + a22x2 + … + a2nxn ≥ b2
a31x1 + a32x2 + … + a3nxn = b3
x1 ≥ 0, x2 ≥ 0, … xn ≥ 0
mempunyai bentuk kanonik sebagai berikut.
max/min z = c1x1 + c2x2 + … + cnxn + 0s1 + 0s2 –+ MA2 –+ MA3
s.t. a11x1 + a12x2 + … + a1nxn + s1 = b1
a21x1 + a22x2 + … + a2nxn – s2 + A2 = b2
a31x1 + a32x2 + … + a3nxn + A3 = b3
x1 ≥ 0, x2 ≥ 0, … xn ≥ 0
Secara rinci mengubah kendala dan fungsi tujuan dari bentuk normal ke bentuk kanonik disajikan dalam tabel berikut.
memaksimalkan
|
kendala
|
fungsi tujuan
|
≤
|
+ s
|
+ 0s
|
≥
|
– s + A
|
+ 0s – MA
|
=
|
+ A
|
– MA
|
Meminimalkan
|
kendala
|
fungsi tujuan
|
≤
|
+ s
|
+ 0s
|
≥
|
– s + A
|
+ 0s + MA
|
=
|
+ A
|
+ MA
|
Selanjutnya dari bentuk kanonik yang terjadi, diubah ke dalam table simpleks.
Contoh:
Bentuk kanoniknya adalah sebagai berikut.
max z = 2x1 – x2 + x3 + 0s1 – MA2 + 0s3 – MA3
s.t. 3x1 + x2 + xn + s1 = 60
x1 – x2 + xn + A2 = 10
x1 + x2 – xn – s3 + A3 = 20
x1, x2, xn, s1, A2, s3, A3 ≥ 0
Tabel simpleks
Basis
|
xj
|
x1
|
x2
|
x
|
s1
|
s3
|
A2
|
A3
|
bi
|
bi/aij
|
cj
|
2
|
– 1
|
1
|
0
|
0
|
– M
|
– M
| |||
s1
|
0
|
3
|
1
|
1
|
1
|
0
|
0
|
0
|
60
|
20
|
A2
|
– M
|
1
|
– 1
|
1
|
0
|
0
|
1
|
0
|
10
|
10
|
A3
|
– M
|
1
|
1
|
– 1
|
0
|
– 1
|
0
|
1
|
20
|
20
|
cj – zj
|
2
|
– 1
|
1
|
0
|
0
|
0
|
0
| |||
Big M
|
2
|
0
|
0
|
0
|
– 1
|
0
|
0
|
Keterangan:
Baris kedua merupakan fungsi tujuan. Baris ketiga adalah kendala pertama, sedangkan baris keempat adalah kendala kedua, dan baris kelima adalah kendala ketiga.
Pemilihan kolom kunci:
i. Pada saat ingin memaksimalkan fungsi tujuan, kolom yang dipilih adalah kolom yang mempunyai nilai cj – zj paling besar.
ii. Pada saat ingin meminimalkan fungsi tujuan, kolom yang dipilih adalah kolom yang mempunyai nilai cj – zj paling kecil.
Sedangkan baris kunci selalu dipilih baris dengan nilai bi/aij paling kecil (≥0).
Tabel sudah optimal apabila:
i. Jika memaksimalkan fungsi tujuan, nilai cj – zj ≤ 0.
ii. Jika meminimalkan fungsi tujuan, nilai cj – zj ≥ 0.
Penyelesaian x1, x2, x3 dapat dilihat di kolom bi. Sedangkan nilai optimal dari fungsi tujuan dapat dilihat di baris cj – zj kolom bi
· Kejadian Khusus pada Metode Simpleks
1. Alternatif solution
Ciri: pada tabel optimal terdapat variabel non basis dengan cj – zj bernilai nol.
2. Infeasible solution
Ciri: terdapat variabel semu A bernilai positif dalam tabel optimal.
3. Unbounded solution
Ciri: jika pada suatu iterasi, semua elemen pada kolom kunci dalam tabel simpleks tidak ada yang positif (tidak harus di tabel terakhir).
4. Redundancy (kelebihan kendala)
Ciri: terdapat variabel slack bernilai nol dalam tabel optimal.
5. Degenerate
Ciri: jika ada paling sedikit satu variabel basis dalam penyelesaian optimal bernilai nol.
1. Alternatif solution
Ciri: pada tabel optimal terdapat variabel non basis dengan cj – zj bernilai nol.
2. Infeasible solution
Ciri: terdapat variabel semu A bernilai positif dalam tabel optimal.
3. Unbounded solution
Ciri: jika pada suatu iterasi, semua elemen pada kolom kunci dalam tabel simpleks tidak ada yang positif (tidak harus di tabel terakhir).
4. Redundancy (kelebihan kendala)
Ciri: terdapat variabel slack bernilai nol dalam tabel optimal.
5. Degenerate
Ciri: jika ada paling sedikit satu variabel basis dalam penyelesaian optimal bernilai nol.
