Artificial Intelligence Indra EHM

Fuzzy Linear Programming

Pada Fuzzy Linear Programming, bentuk persamaan akan mengalami sedikit perubahan sebagai berikut.

• Bentuk imperatif pada fungsi obyektif tidak lagi benar-benar “maksimum” atau “minimum”, karena adanya beberapa hal yang perlu mendapat pertimbangan dalam suatu sistem.
• Tanda ≤ (pada batasan) dalam kasus maksimasi dan tanda ≥ (pada batasan) dalam kasus minimasi tidak lagi bermakna crisp secara matematis, namun sedikit mengalami pelanggaran makna. Hal ini juga disebabkan karena adanya beberapa yang perlu dipertimbangkan dalam sistem yang mengakibatkan batasan tidak dapat didekati secara tegas.

Contoh kasus maksimasi pada Linear Programming:

Maksimumkan: f(x) = cTx
dengan batasan:
Ax ≤ b
x ≥ 0
dengan c,xєRn,bєRm,AєRmxn dan A,b,c adalah bilangan crisp.

Pada Fuzzy Linear Programming, akan dicari suatu nilai z yang erupakan fungi obyektif yang akan dioptimasikan sedemikian hingga unduk pada batasan-batasan yang dimodelkan dengan menggunakan himpunan fuzzy. Akhirnya persamaan di atas dirubah menjadi sebagai brikut.

Tentukan x sedemikian hingga:
cTx ≥ z
Ax ≤ b
X ≥ 0

Contoh kasus minimasi pada Linear Programming:

Minimumkan:
f(x)=CTx
dengan batasan:
Ax ≥ b
x ≥ 0
dengan c,xєRn,bєRm,AєRmxn

Minimasi pada Fuzzy Linear Programming:

Tentukan x sedemikian hingga:
cTx ≤ z
Ax ≥ b
X ≥ 0

Tiap-tiap batasan (0, 1, 2, …, m) akan direpresentasikan dengan ebuah himpunan fuzzy, dengan fungsi keanggotaan pada himpunan ke-i aalah μi[Bix].

Fungsi keanggotaan untuk model keputusan himpunan fuzzy dapat dnyatakan sebagai:

Tentu saja diharapkan akan didapat solusi terbaik, yaitu solusi dengan nilai keanggotaan yang paling besar. Dengan demikian solusi sebenarnya adalah:

Dari sini terlihat bahwa μi[Bix]=0 jika batasan ke-i benar-benar dilanggar. Sebaliknya, μi[Bix]=1 jika batasan ke-i benar-benar dipatuhi. Nilai μi[Bix] akan naik secara monoton pada selang [0,1], yaitu:

Gambar berikut menunjukkan fungsi keanggotaan tersebut.

Fungsi Keanggotaan

i = 0, 1, 2, …, m

dengan pi adalah toleransi interval yang diperbolehkan untuk melakukan pelanggaran baik pada fungi obyektif maupun batasan. Dengan mensubstitusikan (2) ke (1) akan diperoleh:

Dari gambar diatas, terlihat bahwa semakin besar nilai domain, akan memiliki nilai keanggotaan yang cenderung semakin kecil. Sehingga untuk mencari nilai λ-cut dapat dihitung sebagai λ=1-t, dengan:

di + tpi = ruas kanan batasan ke-i

Dengan demikian akan diperoleh bentuk Linear Programming baru sebagai berikut:

Maksimumkan: λ
Dengan batasan: λpi + Bix ≤ di + pi
i = 0, 1, …, m
x≥0

Penyelesaian masalah dengan metode Fuzzy Linear Programming

Maksimumkan:
x1 + x2
dengan batasan:
x1 + 2×2 ≥ 5
x1 + x2 ≤ 4
x1 + x2 = 3
x1, x2 ≥ 0

ketiga batasan memiliki toleransi interval masing-masing p1=3, p2=2, p3=1.

Bentuk tersebut di atas dapat diubah menjadi:

Maksimumkan:
x1 + x2
dengan batasan:
x1 + 2×2 ≥ 5 + 3t
x1 + x2 ≤ 4 + 2t
x1 + x2 = 3 + t
x1, x2 ≥ 0

Jika t=0 (λ=1), maka bentuk di atas menjadi:

Maksimumkan:
x1 + x2
dengan batasan:
x1 + 2×2 ≥ 5
x1 + x2 ≤ 4
x1 + x2 = 3
x1, x2 ≥ 0

yang dapat diselesaikan dengan menggunakan metode simpleks.

Bentuk standar Linear Programming:

Maksimumkan:
z = x1 + x2
dengan batasan:
x1 + 2×2 – S1 + S2 = 5
x1 + x2 + S3 = 4
x1 + x2 + S4 = 3
x1, x2 ≥ 0

Tabel simpleks untuk solusi awal adalah:

Tabel simpleks untuk solusi yang baru:

Tabel simpleks untuk solusi akhir:

Hasil akhir untuk t=0 (λ=1), adalah:

z = 10M;

Jika t=1 (λ=0), maka bentuk awal Linear Programming dapat diubah menjadi:

Maksimumkan:
x1 + x2
dengan batasan:
x1 + 2×2 ≥ 8
x1 + x2 ≤ 6
x1 + x2 = 4 x1,
x2 ≥ 0

yang juga dapat diselesaikan dengan menggunakan metode simpleks.

Bentuk standar Linear Programming:

Maksimumkan:
z = x1 + x2
dengan batasan:
x1 + 2×2 – S1 + S2 = 8
x1 + x2 + S3 = 6
x1 + x2 + S4 = 4
x1, x2 ≥ 0

Tabel simpleks untuk solusi awal adalah:

Tabel simpleks untuk solusi yang baru:

Tabel simpleks untuk solusi akhir:

Hasil akhir untuk t=1 (λ=0), adalah:

z =26M;

Dari kedua hasil ini (t=1 dan t=0), dapat ditentukan nilai p0, yaitu hasil pengurangan dari z pada saat t=1 dengan z pada saat t=0 (26M- 10M=16M).

Dengan mengambil λ=1-t, akhirnya dapat dibentuk model Fuzzy Linear Programming sebagai berikut.

Maksimumkan: λ
dengan batasan:
-16Mλ - x1 - x2 ≤ -26M – 16M
3λ + x1 + x2 ≤ 5 + 3
2λ + x1 + x2 ≤ 4 + 2
λ + x1 + x2 ≤ 3 + 1
λ, x1, x2 ≥ 0

Tabel simpleks untuk solusi awal:

Tabel simpleks untuk solusi baru:

ref : dari berbagai sumber

Popularity: 64% | December 16th, 2008 | Tags: Fuzzy Linear Programming, Fuzzy Logic, Linear Programming | Category: Algorithm, Fuzzy Logic | Subscribe to comments | Leave a comment | Trackback URL