Penyelesaian Program Linear

·         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)
dengan x1, x2, ..., xn ≥ 0      ... (2) 

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.

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.

0 komentar:

Poskan Komentar