Teknik Artificial Variable

Progam Linier dengan kendala  Metode Teknik M

Pembahasan terdahulu hanya kendala bertanda ≤ , topik pembahasan selanjutnya untuk kendala bertanda ≥ dan atau bertanda =

Untuk menyelesaikan kasus tersebut kita memerlukan variable dummy(variable palsu) atau artificial var. sehingga basis awal bisa tetap ada .

Untuk tanda ≥ masih menggunakan variable S dan R sedangkan untuk tanda (=) menggunakan variable dummy R saja.

Contoh :

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala :

X1 ≥ 4

2X2 ≥ 12

3X1 + 2X2 = 18

X1, X2 ≥ 0

PL dg kendala  atau = lanjutan

Jika dituliskan dalam bentuk standar :

Maksimumkan Z = 3X1 + 5X2 +0S1 + 0S2 – MR1– MR2 – MR3

Atau

Z – 3X1 – 5X2 + 0S1 + 0S2 + MR1 + MR2 + MR3 = 0

X1 - S1 + R1 = 4

2X2 – S2 + R2 = 12

3X1 + 2X2 + R3 = 18

X1, X2 , S1 , S2 , R1 , R2 , R3 ≥ 0

Perhatikan bahwa penalty M di atas bertanda (–) karena fungsi tujuannya maksimasi, jika fungsi tujuannya minimasi, maka penalty bertanda (+), dengan M adalah bilangan yang cukup besar.

Contoh 1 Solusi PL dg Teknik M

Metoda Big M (metode penalty)

Contoh 1 : Cari solusi PL berikut ini

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala :

X1 ≤ 4

2X2 ≤ 12

3X1 + 2X2 = 18

X1, X2 ≥ 0

Penyelesaian :

Karena pembatas ketiga bertanda ( = ), maka untuk mendapatkan solusi basis awalnya kita harus menambahkan variable artificial sehingga diperoleh bentuk :

Maksimumkan :

Z = 3X1 + 5X2 + 0.S1 + 0.S2 – MR1

Contoh 1 Solusi PL dg Teknik M

Berdasarkan kendala :

X1 + S1 = 4

2X2 + S2 = 12

3X1 + 2X2 + R1 = 18

X1, X2, R1 , S1, S2 ≥ 0

Untuk memasukan model diatas kedalam bentuk table, maka terlebih dahulu subtitusikan R1 dari persamaan kendala ketiga :

R1 = 18 - 3X1 + 2X2

Kemudian masukan kedalam persamaan Z :

Z = 3X1 + 5X2 + 0.S1 + 0.S2 – M(18 - 3X1 + 2X2 )

Atau

Z = (3M + 3)X1 + (2M – 5)X2 + 0.S1 + 0.S2 – 18M atau

Z - (3M + 3)X1 - (2M – 5)X2 - 0.S1 - 0.S2 = -18M

Sehingga tabel simpleks awal (iterasi 0) dan iterasi ke 1 diberikan dalam tabel berikut ini :

Solusi Masalah Menggunakan Metode Big M

Persoalan di atas mempunyai model PL sbb. :

min z = 2x1 + 3x2 , dengan Z adalah biaya produksi

Berdasarkan kendala :

0.5x1 + 0.25x2 ≤ 4 (gula)

x1 + 3x2 ≥ 20 (Vitamin C)

x1 + x2 = 10 (10 ons dalam 1 botol)

x1, x2  0

Bentuk standar PL masalah ini ditampilkan dalam slide berikut :

Solusi Masalah Menggunakan Metode Big M

Baris 1 : -z + 2x1 + 3x2 = 0

Baris 2 : 0.5x1 + 0.25x2 + s1 = 4

Baris 3 : x1 + 3x2 - s2 = 20

Baris 4 : x1 + x2 = 10

Dengan menggunakan teknik artificial variables, yakni dengan menambahkan variabel artifisial a2 pada baris ketiga dan a3 pada baris keempat. Variabel a2 dan a3 ditulis hitam, maka diperoleh :

Baris 1 : -z + 2x1 + 3x2 = 0

Baris 2 : 0.5x1 + 0.25x2 + s1 = 4

Baris 3 : x1 + 3x2 - s2 + a2 = 20

Baris 4 : x1 + x2 + a3 = 10

Metode Dua Phasa

Digunakannya konstanta M ( bilangan positif yang sangat besar) sebagai penalty, bisa terjadi kesalahan perhitungan, terutama apabila perhitungan itu dilakukan dengan menggunakan computer. Kesalahan itu bisa terjadi karena koefisien fungsi tujuan relative sangat kecil dibandingkan dengan harga M sehingga computer akan memperlakukannya sebagai koefisien yang berharga nol. Kesulitan ini bisa dikurangi dengan menggunakan metoda dua fase. Disini konstanta M dihilangkan dengan cara menyelesaikan persoalan dalam dua fase sebagai berikut :

Fase 1 : Fase ini digunakan untuk menguji apakah persoalan yang kita hadapi memiliki solusi fisibel atau tidak. Pada fase ini fungsi tujuan semula diganti dengan meminimumkan jumlah variable artifisialnya. Jika nilai minimum fungsi tujuan baru ini berharga nol, berarti persoalan memiliki solusi fisibel, lanjutkan ke fase 2 tetapi, jika nilai minimum fungsi tujuan baru ini berharga positif, maka persoalan tidak memiliki solusi fisibel.

STOP

Metode Dua Phasa Lanjutan

Fase 2 :

Gunakan solusi basis optimum dari fase 1 sebagai

solusi awal bagi persoalan semula. Dalam hal ini

ubahlah bentuk fungsi tujuan fase 1 dengan

mengembalikannya pada fungsi tujuan persoalan

semula.

Pemecahan persoalan dilakukan dengan cara seperti biasa.

Read More

Program Linear Metode Kompleks

Program Linier : Metode Simpleks
  

•  Metode simpleks digunakan untukmemecahkan permasalahan Program Linier dengan dua atau lebih variabel keputusan

• Formulasi Fungsi Tujuan dan Fungsi Kendala Dari Permasalahan PL
• Mengkonversi Bentuk Pertidaksamaan Dalam Fungsi Kendala Menjadi Bentuk Standar
• Membuat Table Simpleks Awal
• Algoritma metode simpleks

 

 Program Linier : Bentuk Standar

1.Ruas kanan (RK) fungsi tujuan harus nol (0)

2.Ruas kanan (RK) fungsi kendala harus positif, jika negatif kalikan dengan –1.

3.Fungsi kendala dengan tanda “\<” harus diubah ke bentuk “=” dengan menambahkan variabel slack/surplus. Variabel slack/surplus disebut variabel basis.

4.Fungsi kendala dengan tanda “>/” diubah ke bentuk “\< ” dengan cara mengalikan dengan –1, lalu

diubah ke bentuk persamaan dengan menambahkan variabel slack, kemudian RKnya dikalikan dengan –1,

 karena bertanda negatip.

Mengkonversi Bentuk Pertidaksamaan Fungsi Kendala Menjadi Bentuk Standar 

•                 Ada tiga bentuk fungsi kendala: \<, ≥, dan =.
•                 Konversi fungsi kendala bertanda \<: menambahkan slack variable pada fungsi kendala tersebut.
•                 Untuk kendala berbentuk ‘\<’ dan ‘=‘ akan dibahas tersendiri dalam teknik variabel artifisial.
•                 Slack variable: sumber daya yang mengganggur pada suatu fungsi kendala.
•                  Penambahan slack variable dimaksudkan untuk memperoleh solusi fisibel awal (initial feasible solution, sama dengan titik origin pada grafik) pada fungsi kendala.

 
 

Contoh Metode Simpleks Masalah Maksimasi

Maksimumkan Z = 3X1 + 5X2

Berdasarkan kendala (constrain) 

  (1)  2X1  \< 8

  (2)     3X2  \<15

  (3)   6X1 + 5X2  \<30

  (4)  X1 >/ 0,  X2 >/ 0

Langkah-langkah metode simpleks

Langkah 1:
Mengubah fungsi tujuan dan kendala menjadi “bentuk standar” 

Fungsi tujuan

  Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0.

Fungsi kendala diubah menjadi persamaan dg menambahkan var. slack, sebagai berikut :

  (1) 2X1  \< 8   menjadi   2X1  +     X3            =  8

  (2) 3X2 \< 15 menjadi             3X2     + X4            = 15

  (3) 6X1 + 5X2  \< 30 menjadi   6X1 + 5X2     + X5= 30

Variabel slack adalah variabel tambahan yang mewakili tingkat pengangguran atau kapasitas yang merupakan batasan

Bentuk Standar :

Fungsi tujuan :

  Maksimumkan Z - 3X1 - 5X2 = 0

Fungsi kendala

  (1)   2X1           + X3      =  8

  (2)               3X2           +  X4      = 15

  (3)   6X1  +   5X2                 + X5    = 30

  (4)  X1 ,X2  ,X3  , X4 , X5  >/0

Langkah 2: Memindahkan bentuk standar ke dalam tabel 

Z = 3X1 + 5X2

               diubah menjadi Z - 3X1 - 5X2 + 0X3 + 0X4 + 0X5  = 0.

(1) 2X1  \< 8   menjadi   2X1           + X3   =  8

(2) 3X2  \< 15 menjadi              3X2          + X4   = 15

(3) 6X1 + 5X2  \< 30 menjadi   6X1 +    5X2      + X5  = 30

 

 

Read More

Program Linear

Program Linear

• Model matematika digunakan untuk menyelesaikan masalah optimisasi
• Memaksimumkan dan meminimumkan fungsi tujuan, yang bergantung pada sejumlah variabel input
• Hal terpenting yg harus dilakukan adalah mencari tahu tujuan penyelesaian masalah dan apa penyebab masalah tersebut

Beberapa istilah yang terdapat pada Model Program Linier

1.Suatu model PL akan membuat permasalahan menjadi suatu bentuk pengambilan keputusan mengenai tingkat aktivitas (x1, x2, x3, ……, xn) disebut variabel keputusan.

2.Solusi feasible (layak) adalah solusi di mana semua kendala yang ada terpenuhi, dan solusi disebut infeasible (tak layak) jika paling sedikit ada satu kendala yang tak terpenuhi.

3.Daerah feasible (layak) adalah kumpulan semua solusi feasible.

4.Solusi optimal adalah solusi layak yang memiliki nilai fungsi tujuan terbaik, terbesar jika masalahnya maksimasi dan terkecil jika masalahnya minimasi.

Beberapa Asumsi Dasar Program Linier  

1.Proportionality : naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding (proportional) dengan perubahan tingkat kegiatan

2.Additivity : nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam LP dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain

3.Divisibility : keluaran (output) yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan.

4.Deterministic (Certainty) : Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model LP (ai, bi Cj) dapat diperkirakan dengan pasti, meskipun jarang dengan tepat.


Model Program Linier

Fungsi Tujuan :

  Max/min            z = c1x1 + c2x2 + ... + cnxn

Berdasarkan kendala :

  a11x1 + a12x2 + ... + a1nxn    (≤, =, ≥) b1

  a21x1 + a22x2 + ... + a2nxn    (≤, =, ≥) b2

  :

     am1x1 + am2x2 + ... + amnxn (≤, =, ≥) bm

 

  x1, x2 , ... xn  ≥ 0

  xj = variabel keputusan ke j

  bi = kapasitas kendala ke i

  cj = koefisien fungsi tujuan ke j

  aij = koefisien kendala

 Tujuan Perusahaan

1.Memaksimalkan laba

2.Meminimumkan biaya

3 Pembatasan-pembatasan :

oWaktu

oTenaga kerja

oEnergi

oBahan baku

oUang

 Langkah-langkah program linier

§Tahap 1

§Masalah harus dapat diidentifikasi sbg sesuatu yg dapat diselesaikan oleh program linier

§Tahap 2

§Masalah yang tidak terstruktur harus dapat dirumuskan oleh model matematika

§Tahap 3

§Model harus dibuat menggunakan model matematika yag telah dibuat

 

 Teknik Program Linier

• Menggambarkan bahwa hubungan fungsi linier dalam model matematika adalah LINIER
• Teknik pemecahan masalah terdiri dari langkah-langkah matematika yang telah ditetapkan (program)

Formulasi Model

1.Variabel Keputusan

2.Fungsi Tujuan

3.Batasan Model

Contoh kasus 

Read More