TUGAS 4
(METODE SIMPLEKS, BIG M, DUA
PHASE)
Nama : Muhammad
Daniel Yuna
Kelas : 2TA03
NPM : 14315535
Dosen : Asri Wulan ST., MT.
Fakultas
Teknik Sipil dan Perencanaan
UNIVERSITAS GUNADARMA
Metode Big M digunakan untuk menyelesaikan
fungsi-fungsi dalam program linier yang tidak berada dalam bentuk baku atau
standar ( bentuk standar adalah memaksimalkan Z sesuai dengan kendala
fungsional dalam bentuk ≤ dan kendala nonegativitas di semua variabel) dan
salah satu contoh masalah dalam kendala funsional adalah bila fungsi dalam
bentuk-bentuk
= atau ≥
atau bahkan ruas kanan yang negatif.
Masalah ini akan muncul bila kita akan mencari basis fesibel awal
sehingga sebelum mencari variabel apa yang akan menjadi variabel nonbasis
bahkan basis perlu dilakukan suatu teknik pendekatan khusus untuk mengubah
fungsi tersebut ke bentuk baku atau standar. Teknik pendekatan khusus tersebut
dengan cara menambahkan variabel dummy (variabel artifisial) pada kendala
fungsional dan teknik ini disebut dengan teknik variabel artifisial.
Ada pun prosedur mendapatkan BF
awal pada kendala fungsional adalah :
a.
Gunakan teknik variabel artifisial
Tambahkan
variabel artifisal nonegatif pada fungsi kendala yang belum baku, dan anggaplah
variabel artifial tersebut sebagai salah satu variabel slack
b.
Tugaskan pinalty yang besar
Berilah nilai variabel artifisial dengan nilai > 0 sehingga koefisien
variabel artifisial menjadi M (big m) secara simbolik yang menunjukkan bahwa
variabel artifisial tersebut memiliki angka positif raksasa ( dan pengubahan
atas variabel artifisial bernilai 0 (variabel nonbasis) dalam solusi optimal
disebut metode big m).
|
Contoh
Soal :
|
|
|
|
|
Contoh =
Min Z = 4 X1 + X2
|
|
|
|
|
Kendala
|
3 X1 + X2
|
= 3
|
|
|
|
4 X1 + 3 X2
|
³ 6
|
|
|
|
X1 + 2 X2
|
£ 4
|
|
|
|
X1 , X2 ³ 0
|
|
|
|
è
Bentuk standar
|
|
|
|
|
Min Z =
|
4 X1 + X2
|
|
|
|
Kendala
|
3 X1 + X2
|
= 3
|
......... ( 1 )
|
|
|
4 X1 + 3 X2 - X3 = 6
|
......... ( 2 )
|
|
|
|
X1 + 2 X2 + X4 = 4
|
|
|
X1 , X2 , X3 , X4³ 0
Karena ( 1 ) dan ( 2 ) tidak memiliki var slack , maka
ditambahkan R1 dan R2 sebagai var bantuan
|
( 1 )
|
3 X1 + X2
|
+ R1 = 3
|
|
|
|
|
|
|
||||
|
( 2 )
|
4 X1 + 3 X2 - X3 - R2 = 6
|
|
|
|
|
|
|
|
||||
|
Ø Pada
fungsi tujuan berikan koefisien M > 0, untuk R1 dan R2 ;
sehingga :
|
|
|
|
|||||||||
|
Min Z = 4 X1 + X2 + MR1 + MR2
|
|
|
|
|
|
|
||||||
|
Kendala
|
3 X1 + X2 + R1
|
|
|
=
|
3
|
|
|
|
|
|
||
|
|
|
4 X1 + 3 X2 - X3 - R2
|
= 6
|
|
|
|
|
|
||||
|
|
|
|
X1 + 2 X2 + X4
|
= 4
|
|
|
|
|
|
|||
|
|
|
|
X1 , X2 , X3 , R1 , R2 , X4³ 0
|
|
|
|
|
|
||||
|
Ø
Subtitusikan R1 dan R2 ke
fungsi tujuan
|
:
|
|
|
|
|
|
|
|
||||
|
R1 = 3 - 3 X1 - X2
|
|
|
|
|
|
|
|
|
|
|
||
|
R2 = 6 - 4 X1 - 3 X2 + X3
|
|
|
|
|
|
|
|
|
|
|||
|
Maka :
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Z = 4 X1 + X2 + M(3 - 3 X1
|
-
|
X2) +
M(6 - 4 X1 - 3
X2 + X3)
|
|
|
|
|||||||
|
= ( 4 - 7M ) X1 + ( 1 – 4M ) X2 + M X3 + 9M
|
|
|
|
|
|
|||||||
|
Persamaan
Z dalam tabel :
|
|
|
|
|
|
|
|
|
|
|||
|
Z + ( 7M - 4 ) X1 + ( 4M
- 1 ) X2 - M X3 = 9M
|
|
|
|
|
|
|||||||
|
Ø
Solusi dasar awal ; X1 = 0, X2 = 0, X3 = 0
-> Z = 9M
|
|
|
|
|
|
|||||||
|
Sehingga X1 , X2 , X3 var non basis
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
Tabel Metode Big M
|
|
|
|
|
|
||||
|
Iterasi 0
|
|
Basis
|
X1
|
|
X2
|
|
X3
|
R1
|
R2
|
X4
|
Solusi
|
|
|
(awal)X1 (paling +
|
Z
|
(7M –
|
(4M – 1)
|
-M
|
0
|
0
|
0
|
9M
|
|
|||
|
) R1Keluar
|
|
|
4)
|
|
|
|
|
|
|
|
|
|
|
|
|
R1
|
3
|
|
1
|
|
0
|
1
|
0
|
0
|
3
|
3/3 = 1
|
|
|
|
R2
|
4
|
|
3
|
|
-1
|
0
|
1
|
0
|
6
|
6/4
|
|
|
|
X4
|
1
|
|
2
|
|
0
|
0
|
0
|
1
|
4
|
4/1
|
|
( 1
|
|
Z
|
0
|
(1+5M)/3
|
-M
|
(4-
|
0
|
0
|
4+2M
|
|
||
|
) X2masukR2keluar
|
|
|
|
|
|
|
7M)/3
|
|
|
|
|
|
|
|
|
X1
|
1
|
|
1/3
|
|
0
|
1/3
|
0
|
0
|
1
|
1/(1/3)= 3
|
|
|
|
R2
|
0
|
|
5/3
|
|
-1
|
-4/3
|
1
|
0
|
2
|
2/(5/3)=6/5
|
|
|
|
X4
|
0
|
|
5/3
|
|
0
|
-1/3
|
0
|
1
|
3
|
8/5
|
|
( 2 ) X3masuk
|
|
Z
|
0
|
|
0
|
|
1/5
|
(8/3-M)
|
(-1/5-
|
0
|
18/3
|
|
|
X4keluar
|
|
|
|
|
|
|
|
|
M)
|
|
|
|
|
|
|
X1
|
1
|
|
0
|
|
1/5
|
3/5
|
-1/5
|
0
|
3/5
|
3
|
|
|
|
X2
|
0
|
|
1
|
|
-3/5
|
-4/5
|
3/5
|
0
|
6/5
|
|
|
|
|
X4
|
0
|
|
0
|
|
1
|
1
|
-1
|
1
|
1
|
1
|
|
( 3 )
|
|
Z
|
0
|
|
0
|
|
0
|
7/3-M
|
-M
|
-
|
17/5
|
|
|
(optimum)
|
|
|
|
|
|
|
|
|
|
1/5
|
|
|
|
|
|
X1
|
1
|
|
0
|
|
0
|
2/5
|
0
|
-
|
2/5
|
|
|
|
|
|
|
|
|
|
|
|
|
1/5
|
|
|
|
|
|
X2
|
0
|
|
1
|
|
0
|
-1/5
|
0
|
3/5
|
9/5
|
|
|
|
|
X3
|
0
|
|
0
|
|
1
|
1
|
-1
|
1
|
1
|
|
Metode simpleks merupakan salah satu teknik
penyelesaian dalam program linier yang digunakan sebagai teknik pengambilan
keputusan dalam permasalahan yang berhubungan dengan pengalokasian sumberdaya
secara optimal. Metode simpleks digunakan untuk mencari nilai optimal dari
program linier yang melibatkan banyak constraint (pembatas) dan banyak variabel
(lebih dari dua variabel). Penemuan metode ini merupakan lompatan besar dalam
riset operasi dan digunakan sebagai prosedur penyelesaian dari setiap program
computer. Salah satu teknik penentuan solusi optimal yang digunakan dalam
pemrograman linier adalah metode simpleks. Penentuan solusi optimal menggunakan
metode simpleks didasarkan pada teknik eleminasi Gauss Jordan. Penentuan solusi
optimal dilakukan dengan memeriksa titik ekstrim satu per satu dengan cara
perhitungan iteratif. Sehingga penentuan solusi optimal dengan simpleks
dilakukan tahap demi tahap yang disebut dengan iterasi.
Beberapa istilah yang sangat
sering digunakan dalam metode simpleks, diantaranya yaitu :
a)
Iterasi adalah tahapan
perhitungan dimana nilai dalam perhitungan itu tergantung dari nilai tabel
sebelumnya.
b)
Variabel non basis adalah variabel yang nilainya
diatur menjadi nol pada
sembarang iterasi. Dalam terminologi
umum, jumlah variabel non basis selalu
sama
dengan derajat bebas dalam sistem
persamaan.
c) Variabel basis merupakan variabel yang nilainya bukan nol pada
sembarang iterasi. Pada solusi awal, variabel basis merupakan variabel slack
(jika fungsi kendala merupakan pertidaksamaan ≤ ) atau variabel buatan (jika
fungsi kendala menggunakan pertidaksamaan ≥ atau =). Secara umum, jumlah variabel
basis selalu sama dengan jumlah fungsi pembatas (tanpa fungsi non negatif).
d) Solusi atau nilai kanan merupakan nilai sumber daya pembatas yang
masih tersedia. Pada solusi awal, nilai kanan atau solusi sama dengan jumlah
sumber daya pembatas awal yang ada, karena aktivitas belum dilaksanakan.
e) Variabel slack adalah variabel yang ditambahkan ke model matematik
kendala untuk mengkonversikan pertidaksamaan ≤ menjadi persamaan (=).
Penambahan variabel ini terjadi pada tahap inisialisasi. Pada solusi awal,
variabel slack akan berfungsi sebagai variabel basis.
f) Variabel surplus adalah variabel yang dikurangkan dari model
matematik kendala untuk mengkonversikan pertidaksamaan ≥ menjadi persamaan (=).
Penambahan ini terjadi pada tahap inisialisasi. Pada solusi awal, variabel
surplus tidak dapat berfungsi sebagai variabel basis.
g)
Variabel buatan adalah variabel yang ditambahkan ke
model matematik
kendala dengan bentuk ≥ atau =
untuk difungsikan sebagai variabel basis awal.
Penambahan
variabel ini terjadi pada tahap inisialisasi.Variabel ini harus bernilai 0 pada
solusi optimal, karena kenyataannya variabel ini tidak ada. Variabel hanya ada
di atas kertas.
h)
Kolom pivot (kolom kerja) adalah
kolom yang memuat variabel masuk. Koefisien pada kolom ini akn menjadi pembagi
nilai kanan untuk menentukan baris pivot (baris kerja).
i)
Baris pivot (baris kerja) adalah
salah satu baris dari antara variabel basis yang memuat variabel keluar.
j)
Elemen pivot (elemen kerja)
adalah elemen yang terletak pada perpotongan kolom dan baris pivot. Elemen
pivot akan menjadi dasar perhitungan untuk tabel simpleks berikutnya.
k)
Variabel masuk adalah variabel
yang terpilih untuk menjadi variabel basis pada iterasi berikutnya. Variabel
masuk dipilih satu dari antara variabel non basis pada setiap iterasi. Variabel
ini pada iterasi berikutnya akan bernilai positif.
l)
Variabel keluar adalah variabel
yang keluar dari variabel basis pada iterasi berikutnya dan digantikan oleh
variabel masuk. Variabel keluar dipilih satu dari
antara variabel basis pada setiap iiterasi. Variabel ini pada iterasi
berikutnya akan bernilai nol.
·
BENTUK
BAKU
Sebelum melakukan perhitungan iteratif untuk
menentukan solusi optimal, pertama sekali bentuk umum pemrograman linier
dirubah ke dalam bentuk baku terlebih dahulu. Bentuk baku dalam metode simpleks
tidak hanya mengubah persamaan kendala ke dalam bentuk sama dengan, tetapi
setiap fungsi kendala harus diwakili oleh satu variabel basis awal. Variabel
basis awal menunjukkan status sumber daya pada kondisi sebelum ada aktivitas
yang dilakukan. Dengan kata lain, variabel keputusan semuanya masih bernilai
nol. Dengan demikian, meskipun fungsi kendala pada bentuk umum pemrograman
linier sudah dalam bentuk persamaan, fungsi kendala tersebut masih harus tetap
berubah.
Ada beberapa hal yang harus
diperhatikan dalam membuat bentuk baku,
yaitu :
a)
Fungsi kendala dengan
pertidaksamaan ≤ dalam bentuk umum, dirubah menjadi persamaan (=) dengan
menambahkan satu variabel slack.
b)
Fungsi kendala dengan
pertidaksamaan ≥ dalam bentuk umum, dirubah menjadi persamaan (=) dengan
mengurangkan satu variabel surplus.
c)
Fungsi kendala dengan persamaan
dalam benttuk umum,ditambahkan satu artificial variabel (variabel buatan).
Contoh soal :
Selesaikan kasus berikut ini
menggunakan metode simpleks :
Maksimum z = 8 x1 + 9 x2 + 4x3
Kendala :
x1 + x2 + 2x3 ≤ 2
2x1 + 3x2 + 4x3 ≤ 3
7x1 + 6x2 + 2x3 ≤ 8 x1,x2,x3 ≥ 0
Penyelesaian :
Bentuk bakunya adalah :
Maksimum z = 8 x1 + 9 x2 + 4x3 + 0s1 + 0s2 + 0s3 atau z - 8 x1 - 9 x2 - 4x3 + 0s1 + 0s2 + 0s3 = 0
Kendala :
x1 + x2 + 2x3 + s1 = 2 2x1 + 3x2 + 4x3 + s2 = 3 7x1 + 6x2 + 2x3 + s3 = 8 x1,x2,x3 ,s1 , s2 , s3 ≥ 0
Solusi / table awal simpleks :
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
|
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
|
|
|
|
|
|
|
|
|
|
|
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
|
|
|
|
|
|
|
|
|
|
|
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
|
|
|
|
|
|
|
|
|
|
|
Karena nilai negative terbesar ada pada kolom X2, maka kolom X2 adalah kolom pivot dan X2 adalah variabel masuk. Rasio
pembagian nilai kanan dengan kolom pivot terkecil adalah 1 bersesuaian dengan
baris s2, maka
baris s2 adalah
baris pivot dan s2 adalah
varisbel keluar. Elemen pivot adalah 3.
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
|
|
Z
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
2
|
|
|
|
|
|
|
|
|
|
|
|
S2
|
2
|
3
|
4
|
0
|
1
|
0
|
3
|
1
|
|
|
|
|
|
|
|
|
|
|
|
S3
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
8/6
|
|
|
|
|
|
|
|
|
|
|
Iterasi 1
Nilai
pertama yang kita miliki adalah nilai baris pivot baru (baris x2). Semua nilai pada baris s2 pada tabel solusi awal dibagi
dengan 3 (elemen pivot).
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
|
|
Z
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
|
|
|
|
|
|
|
|
|
|
|
|
S3
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Perhitungan
nilai barisnya :
Baris z :
|
|
|
|
-8
|
-9
|
-4
|
0
|
0
|
0
|
0
|
|
|
|
-9 ( 2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
) -
|
|||||
|
|
|
|
-2
|
0
|
8
|
0
|
3
|
0
|
9
|
|
|
|
Baris s1 :
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
1
|
1
|
2
|
1
|
0
|
0
|
2
|
|
|
|
1
|
(2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1 ) -
|
|
|
||
|
|
|
|
1/3
|
0
|
2/3
|
1
|
-1/3
|
0
|
1
|
|
|
|
Baris
s3 :
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
7
|
6
|
2
|
0
|
0
|
1
|
8
|
|
|
|
6
|
( 2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1 ) -
|
|
|||
|
|
|
|
3
|
0
|
-6
|
0
|
-2
|
1
|
2
|
|
|
Maka tabel iterasi 1 ditunjukkan tabel di bawah. Selanjutnya kita
periksa apakah tabel sudah optimal atau belum. Karena nilai baris z di bawah
variabel x1 masih
negatif, maka tabel belum optimal. Kolom dan baris pivotnya ditandai pada tabel
di bawah ini :
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
|
|
|
Z
|
-2
|
0
|
8
|
0
|
3
|
0
|
9
|
-
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
1/3
|
0
|
2/3
|
1
|
-1/3
|
0
|
1
|
3
|
|
|
|
|
|
|
|
|
|
|
|
X2
|
2/3
|
1
|
4/3
|
0
|
1/3
|
0
|
1
|
3/2
|
|
|
|
|
|
|
|
|
|
|
|
S3
|
3
|
0
|
-6
|
0
|
-2
|
1
|
2
|
2/3
|
|
|
|
|
|
|
|
|
|
|
Variabel masuk dengan demikian adalah X1 dan variabel keluar adalah S3 .Hasil perhitungan iterasi ke 2 adalah sebagai berikut :
Iterasi 2 :
|
VB
|
X1
|
X2
|
X3
|
S1
|
S2
|
S3
|
NK
|
Rasio
|
|
|
|
|
|
|
|
|
|
|
|
Z
|
0
|
0
|
4
|
0
|
5/3
|
2/3
|
31/3
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
0
|
0
|
4/3
|
1
|
-1/9
|
-1/9
|
7/9
|
|
|
|
|
|
|
|
|
|
|
|
|
X2
|
0
|
1
|
8/3
|
0
|
7/9
|
-2/9
|
5/9
|
|
|
|
|
|
|
|
|
|
|
|
|
X1
|
1
|
0
|
-2
|
0
|
-2/3
|
1/3
|
2/3
|
|
|
|
|
|
|
|
|
|
|
|
Tabel sudah optimal, sehingga perhitungan iterasi dihentikan !
Perhitungan dalam simpleks menuntut ketelitian
tinggi, khususnya jika angka yang digunakan adalah pecahan. Pembulatan harus
diperhatikan dengan baik. Disarankan jangan menggunakan bentuk bilangan
desimal, akan lebih teliti jika menggunakan bilangan pecahan. Pembulatan dapat
menyebabkan iterasi lebih panjang atau bahkan tidak selesai karena
ketidaktelitian dalam melakukan pembulatan.
Perhitungan iteratif dalam simpleks pada dasarnya merupakan pemeriksaan
satu per satu titik-titik ekstrim layak pada daerah penyelesaian. Pemeriksaan
dimulai dari kondisi nol (dimana semua aktivitas/variabel keputusan bernilai
nol). Jika titik ekstrim berjumlah n, kemungkinan terburuknya kita akan
melakukan perhitungan iteratif sebanyak n kali.
Dalam menyelesaiakan suatu persoalan dimana
variabelnya lebih dari dua, juga menggunakan suatu metode yang bertahap. Metode
ini disebut sebagai metode dua phase. Pada dasarnya Metode dua fase (phase)
sama seperti metode big M yang juga digunakan untuk menyelesaikan persoalan
pemrograman linier yang memiliki bentuk yang tidak standar. Berikut adalah
prosedur menggunakan metode dua fase :
1.
Inisialisasi
Menambahkan variabel-variabel artifisal pada fungsi kendala yang
memiliki bentuk tidak standar. Variabel artificial ini ditambahkan pada fungsi
batasan yang pada mulanya memiliki tanda (³). Hal ini digunakan agar dapat
mencari solusi basic fesibel awal.
2.
Fase 1
Digunakan untuk mencari basic fesibel awal. Pada
fase 1 memiliki langkah-langkah dimana tujuannya adalahm meminimalkan variabel
artifisial ( Min Y= Xa)
s.t : Ax = b X = 0
Pada fase pertama bertujuan untuk memperoleh penyelesaian yang optimum
dari suatu permasalahan. Pada fase pertama fungsi tujuan selalu minimum
variabel artificial, meskipun permasalahan yang ada adalah permasalahan yang
maksimum. Dalam meyelesaiakan pada fase pertama, yaitu membuat nilai nol dulu
pada variabel artifisial, kemudian melanjutkan iterasi seperti proses iterasi
biasanya(dengan aturan meminimumkan). Berhenti ketika pada baris ke-0 bernilai £ 0. Fase
pertama dianggap telah selesai atau memperoleh penyelesaian yang optimal adalah
apabila variabel artifisial adalah merupakan variabel basis. Sedangkan apabila
variabel artifisial adalah variabel non basis, maka masalah dianggap tidak
mempunyai penyelesaian yang optimal, sehingga harus dilanjutkan ke fase yang
kedua.
Pada fase kedua, tujuannya sama seperti fase
pertama, yaitu untuk mendapatkan penyelesaian yang optimal dari suatu
permasalahan yang ada. Fase dua berhenti sesuai dengan tujuan awal
permasalahan.
3.
Fase 2
Digunakan untuk mencari solusi optimum pada permasalahan riil. Karena
variabel artifisial bukan merupakan termasuk variabel dalam permasalahan riil,
variabel artifisial tersebut dapat
dihilangkan
( Xa=0). Bermula dari solusi BF yang didapatkan dari akhir fase 1. Pada fase 2
ini
memiliki langkah-langkah sebagai
berikut:
1.
Fungsi tujuan bisa memaksimalkan
dan juga bisa meminimalkan tergantung pada permasalahan yang dihadapi.
2.
Menggunakan fungsi batasan (s.t)
dari fase 1, melakukan proses iterasi seperti biasanya dan berhenti sesuai
funsi obyektif awal
Contoh soal : Tahap 1
Min A =
A1 + A2
Terhadap: x1 + x2 + A1 = 90 0.001x1 + 0.002x2 + s1 = 0.9 0.09x1 + 0.6x2
-s2 + A2 = 27 0.02x1 + 0.06x2 + s3 = 4.5 x1, x2, s1, s2, s3 ≥ 0
karena A1 dan A2 berfungsi sebagai variabel basis pada solusi awal, maka
koefisiennya pada fungsi tujuan harus sama dengan 0. untuk mencapai itu,
gantikan nilai A1 dari fungsi kendala pertama (kendala yang memuat A1) dan
nilai A2 dari fungsi kendala ketiga (kendala yang memuat A2). Dari kendala -1
diperoleh : A1 = 90 - x1 - x2
Dari kendala-3 diperoleh:
A2 = 27 - 0.09x1 - 0.6x2 + s2
Maka fungsi tujuan tahap-1
menjadi:
Min A = (90 - x1 - x2) + (27 - 0.09x1 - 0.6x2 + s2) =117 - 1.09x1 -
1.6x2 + s2
|
Solusi
|
X1
|
X2
|
S1
|
S2
|
S3
|
A1
|
A2
|
NK
|
Rasio
|
|
awal
|
|
|
|
|
|
|
|
|
|
|
VB
|
|
|
|
|
|
|
|
|
|
|
A
|
1.09
|
1.6
|
0
|
-1
|
0
|
0
|
0
|
117
|
-
|
|
A1
|
1
|
1
|
0
|
0
|
0
|
1
|
0
|
90
|
90
|
|
0.001
|
0.002
|
1
|
0
|
0
|
0
|
0
|
0.9
|
450
|
|
|
A2
|
0.09
|
0.6
|
0
|
-1
|
0
|
0
|
1
|
27
|
45
|
|
S3
|
0.02
|
0.06
|
0
|
0
|
1
|
0
|
0
|
4.5
|
75
|
Tahap 2
Min z = 2 x1 + 5.5 x2
Terhadap: tabel optimal tahap
pertama
Dari tabel optimal tahap 1
diperoleh:
X1 = 52.94 – 17/12s2
X2 = 37.059 + 1.7542s2
Maka fungsi tujuan adalah:
Min z = 2(52.94 – 17/12s2) + 5.5
(37.059 + 1.7542s2)
= -17/6s2
+ 9.6481s2 + 309.7045 = 6.814767s2 + 309.7045
|
|
Solusi awal
|
|
X1
|
X2
|
S1
|
S2
|
S3
|
NK
|
|
|
optimal. VB
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
z
|
|
0
|
0
|
0
|
-6.814767
|
0
|
309.7045
|
|
|
|
|
|
|
|
|
|
|
|
|
X1
|
|
1
|
0
|
0
|
17/12
|
0
|
52.94
|
|
|
|
|
|
|
|
|
|
|
|
|
S1
|
|
0
|
0
|
1
|
0.0023417
|
0
|
0.772942
|
|
|
|
|
|
|
|
|
|
|
|
|
X2
|
|
0
|
1
|
0
|
-1.7542
|
0
|
37.059
|
|
|
|
|
|
|
|
|
|
|
|
|
S3
|
|
0
|
0
|
0
|
0.09358
|
1
|
1.21766
|
|
|
|
|
|
|
|
|
|
|
Tabel di
atas sudah optimal. Solusi optimalnya adalah:
X1 = 52.94; x2 = 37.059; dan z =
309.7045
Tidak ada komentar:
Posting Komentar