I.
METODE SIMPLEK
Pada
metode Simplekmodel persamaan linier harus dilakukan standarisasi, sebelum
tahap awal dilakukan.
Langkah-langkah Standarisasi
1. Fungsi Tujuan
diubah dalam bentuk =0, dengan kata lain variabel yang terletak disebelah kanan
tanda parsamaan dipindahkan kesebelah kiri tanda.
Z = C1X1+C2X2+…+CnXn
persamaan
2. Fungsi pembatas
yang masih berupa pertidaksamaan diubah menjadi bentuk persamaan.
3. Menambahkan
variabel senjang ( slanck variabel ) biasa ditulis
S1 , S2 , … , Sn pada fungsi pembatas yang bertanda ≤
4.
Menambahkan
variabel surplus (super variable) biasa ditulis
S1 , S2 , … , Sn pada fungsi pembatas yang bertanda ≥
Dari langkah-langkah nomor 2-3
dapat ditulis menjadi
a1.1x1 + a1.2x2 + … +a1nxn+S1
= b1
a2.1x1 + a2.2x2
+ … +a2nxn+S2 = b2
am.1x1 + am.2x2 + … +amnxn+Sm
= bm
|
Dengan i =
1 , 2 , 3 , ….. , m
|
Setelah langkah-langkah
standarisasi tersebut selesei, maka langkah selanjutnya memasukkan hasi-hasil
perhitungan pada setiap langkah tersebut kedalam tabel (tabel matriks)
Pada
metode Simpleks dikenalkan dua macam tabel yakni tabel kolom variabel dasar dan
tabel baris Cj – Zi, maka kesempatan ini akan dibahas metode simpleks dengan
menggunakan tabel berkolom variabel dasar.
Metode
Simpleks Dengan Tabel Berkolom Variabel Dasar
Metode Program Liniernya
1.
Optimumkan
(maks/min) Fungsi tujuan menjadi:
Z – C1X1 – C2X2
- … - CnXn = 0
2.
Fungsi
pembatas
a1.1 x1
+ a1.2 x2 +… + a1n xn + S1 =
b1
a2.1 x1
+ a2.2 x2 +… + a2n xn + S2 =
b2
………
am.1 x1
+ am.2 x2 +… + amn xn + Sm =
bm
Buntuk Tabel Berkolom Variabel
Dasarnya
|
VD
|
Z
|
X1
|
X2
|
Xn
|
S1
|
S2
|
Sn
|
S
|
|
Z
|
1
|
C1
|
C2
|
Cn
|
0
|
0
|
0
|
0
|
|
S1
|
0
|
A11
|
A12
|
A1n
|
1
|
0
|
0
|
B1
|
|
S2
|
0
|
A21
|
A22
|
A2n
|
0
|
1
|
0
|
B2
|
|
|
…
|
|
|
|
|
|
|
|
|
Sm
|
0
|
Am1
|
Am2
|
Amn
|
0
|
0
|
1
|
Bm
|
Dimana: Kolom X1
X2 Xn disebut matrik utama (Am Xn )
Kolam S1 S2
Sn disebut matrik satuan (An Xn)
Baris Z disebut
persamaan ke-2
Baris S1
disebut persamaan ke-S1
Baris Sm
disebut persamaan ke-Sm
Keterangan:
1.
Kolom
VD (Variabel Dasar) / Baris Variabel / Variabel Anol (non zero
veriable)
Adalah
variabel-variabel yang nilainya ditunjukkan oleh konstanta yang bersesuaian
didalam S. pada tahap awal / tabel pertama ini diisi variabel-variabel semu,
karena pada tahap berikutnya variabel-variabel ini akan selalu berganti kecuali
Z yang senantiasa hadir dalam kolom VD mulai awal hingga akhir.
2.
Kolom
Z
Kolom ini
sebenarnya hanya berfungsi sebagai pelengkap, karena isi pada kolom tetap mulai
awal hingga akhir yakni: 1 , 0 ,…, 0.
3.
Kolom
Variabel
Pada tabel
pertama diisi koefisien / konstanta dari masing-masing variabel pada persamaan
yang bersesuaian yakni aij untuk variabel asli Xj
dan 0 atau 1 untuk variabel-variabel semu Sj.
4.
Kolom
S (satuan)
Berisi
nilai-nilai pada ruas kanan dari persamaan implisit yang terdapat didalam
model, baik persamaan fungsi tujuan maupun fungsi pembatas.
Bilangan
–bilangan yang tercantum pada kolom S ini mencerminkan nilai Z dan nilai variabel-variabel dasar
pada tahap penyeleseian yang bersangkutan.
Langkah-langkah
Pengerjaan Prolin Dengan Menggunakan Tabel Kolom VD
1.
Rumuskan
dan standarisasikan modelnya.
2.
Buat
tabel pertama dengan menetapkan semua variabel semu sebagai VD (semua variabel
asli sebagai variabel dasar).
3.
Tuntukan
satu variabel pendatang diantaranya variabel-variabel dasar yang ada untuk
variabel dasar dalam tabel berikutnya
Variabel
Pendatang(Entering Variable) adalah variabel dasar yang nilainya pada baris Z paling negatif (dalam kasus
MAKSIMAL) dan paling positif (dalam kasus MINIMAL).
4.
Tuntukan
satu “variabel pantau” diantara variabel-variabel yang ada.
Variabel Pantau
adalah VD yang memiliki “Rasip Solusi (RS)” dengan nilai positif terkecil.
Untuk Selanjutnya:
Kolom
yang mengandung variabel pendatang dinamakan kolom kunci.
Baris
kunci adalah baris yang mengandung variabel perantau.
Untuk
menentukan nilai kunci adalah perpotongan antara baris kunci dengan kolom kunci
pendatang dan perantau.
Rasio
Solusi (RS) adalah hasil bagi konstanta pada S terhadap unsur yang sebaris.
Dalam bentuk
variabel perantau / baris kunci abaikan RS yang bernilai nol (0), dan negatif
(-).
Bentuk
tablo berikutnya dengan cara memasukkan pendatang kekolom VD dan mengeluarkan
variabel perantau dan kolom VD serta mmelakukan tranformasi baris-baris tablo
termasuk baris-baris transformasi baris kunci yang sembarang yang bervariabel
dasar baru dilakukan dengan cara:|
Baris kunci baru =
|
|
Baris baru = baris lama –
unsur kolom kunci x baris kunci baru
|
Lakukan
pengujian optimatis, jika semua koefisien pada variabel dasar pada baris Z
sudah tidak ada lagi yang negatif, berarti penyeleseian sudah optimal , jika
masih ada yang negatif maka harus dilakukan langkah-langkah ke-3 hingga ke-6
untuk tablo berikutnya.
Conyoh soal:
Seandainya
diketahui fungsi-fungsi dan pembatas suatu masalah LP sebagai berikut:
Fungsi tujuan
(maks.) Xo = 4x1 + 3x2
Fungsi-fungsi
pembatas:
a.
2x1
+ 3x2 ≤ 6
b.
-3x₁
+2x2 ≤ 3
c.
2x₁
+ 2x2 ≤ 5
d.
2x₁
+ x2 ≤ 4
e.
x₁,
x2 ≥ 0
Seleseikan masalah diatas dengan metode
gravik, dan dengan metode simplek.
Penyeleseian…!
1.
Dengan
cara grafik.
Misal x = X1
y = X2
Fungsi Tujuan (maks) Xo = 4X1
+ 3X2 ó Z
= 4x + 3y
Fungsi Pembatas:
·
2X1
+ 3X2 ≤ 6 ó 2x + 3y
≤ 6
·
-3X1
+ 2X2 ≤ 3 ó -3x + 2y
≤ 3
·
2X1
+ X2 ≤ 5 ó 2x + y
≤ 5
·
2X1
+ 2X2 ≤ 4 ó 2x + 2y
≤ 4
·
X1
, X2 ≥ 0
2x + 3y
≤ 6 |
X
|
0
|
3
|
|
Y
|
2
|
0
|
-3x + 2y
≤ 3|
X
|
0
|
-1
|
|
Y
|
1
|
0
|
2x + y
≤ 5|
X
|
0
|
2
|
|
Y
|
2
|
0
|
2x + 2y
≤ 4 |
X
|
0
|
2
|
|
Y
|
4
|
0
|
X1
, X2 ≥ 0
Jika: Z = 4x + 3y
|
TITIK
|
CARTESIUS
|
NILAI
|
|
O
|
( 0 , 0 )
|
0
|
|
A
|
( 0 , 1
)
|
4
|
|
B
|
(
, 1
)
|
7
|
|
C
|
|
9
|
|
D
|
( 2 , 0 )
|
8
|
2.
Dengan Metode Simplek
Z – 4X1 – 3X2 = 0
2X1 + 3X2 + S1
= 6
-3X1 + 2X2 + S2
= 3
2X1 + 3X2 + S3 = 5
2X1 + X2 + S4
= 4
ð X1
, X2 ≥ 0
Tabel
Metode Simplek I
|
VD
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
S4
|
S
|
Rs
|
|
Z
|
1
|
-4
|
-3
|
0
|
0
|
0
|
0
|
0
|
0
|
|
S1
|
0
|
2
|
3
|
1
|
0
|
0
|
0
|
6
|
3
|
|
S2
|
0
|
-3
|
2
|
0
|
1
|
0
|
0
|
3
|
-1
|
|
S3
|
0
|
2
|
3
|
|
|
|
|
|
|
|
S4
|
|
|
|
|
|
|
|
|
|
3.
Dengan metode simpleks
Z - 4X1
- 3X2 = 0
2x1
+ 3x2 + S1 = 6
-3x₁
+2x2 + S2 = 3
2x₁
+ 2x2 + S3 = 5
2x₁
+ x2 + S4 = 4
X1
, X2 ≥ 0
ð Table metode
simplek I
|
VD
|
Z
|
X1
|
X2
|
S1
|
S2
|
S3
|
S4
|
S
|
|
Z
|
1
|
-4
|
-3
|
0
|
0
|
0
|
0
|
0
|
|
S1
|
0
|
2
|
3
|
1
|
0
|
0
|
0
|
6
|
|
S2
|
0
|
-3
|
2
|
0
|
1
|
0
|
0
|
3
|
|
S3
|
0
|
2
|
3
|
0
|
0
|
1
|
0
|
5
|
|
S4
|
0
|
2
|
1
|
0
|
0
|
0
|
1
|
4
|
Rs
=
Rs1 =
= 0 Rs2
=
Rs3 =
Rs4 =
Rs5 =
=2
Baris
kunci baru =
|
S4 merantau diganti
dengan X1 (baru)
|
X1(baru) = 0 1
0 0 0
2
Z (baru)
1 – ( -4 * 0) = 0
-4
– (-4 * 0) = 0
-3
– (-4 *
) = -1
0
– (-4 * 0) = 0
0
– (-4 * 0) = 0
0
– (-4 * 0) = 0
0
– (-4 *
) = 2
0
– (-4 * 2) = 8
S1 (baru)
0 komentar:
Posting Komentar