PROGRAM LINIER

Fungsi tujuan

Semua kendala

Bentuk Umum Program Linier :

Max

S.t

; C =

b = ; A =

didapat,

max C

s.t A b

x 0

Contoh :

Pabrik kayu menghasilkan 2 produk pintu dan jendela dengan proses sebagai berikut :

PROGRAM LINIER 1

Fungsi linier thd variabel keputusan

Spesifikasi :- Terdapat 4 mesin di unit I

- Terdapat 3 mesin di unit II

- Terdapat 3 mesin di unit III

- Tiap mesin di unit I dpt menghasilkan 1 pintu tiap 3 jam

- Tiap mesin di unit II dpt menghasilkan 1 jendela tiap 2 jam

- Tiap mesin di unit III dpt menghasilkan 1 pintu tiap 2 jam dan 1

jendela tiap 1 jam

- Tiap hari jam kerja yang tersedia adalah 9 jam

- Keuntungan tiap pintu = Rp 20.000

- Keuntungan tiap jendela = Rp 15.000

Buat Formulasi Program Linier supaya didapat keuntungan yang maksimum !

Penyelesaian :

: banyaknya pintu yang diproduksi

: banyaknya jendela yang diproduksi

: Keuntungan

Formulasi Program Linier :

max

s.t

Dalam Notasi Matrik :

C = A = b =

PROGRAM LINIER 2

Pintu dan jendela siap jualkayu

I

II

III

Pintu kasar

Jendela kasar

Penyelesaian Grafis dari Program Linier :

Titik – titik ekstrim dari program linier tersebut adalah :

, , , ,

kandidat penyelesaian dari program linier

Dari arah terlihat bahwa titik maksimumnya adalah :

dengan

Penyelesaian dengan Kuhn-Tucker :

max

PROGRAM LINIER 3

02 x

01 x

272 21 xx

272 2 x

363 1 x

min :

s.t :

:

:

:

:

PROGRAM LINIER 4

PENYELESAIAN MATRIK UNTUKPROGRAM LINIER

Pertidaksamaan diubah menjadi Persamaan dengan menambahkan SLACK :

max

s.t

Dengan menambahkan slack sebanyak kendala didapatkan :

max

s.t

Dalam bentuk Matrik didapatkan :

Max

s.t Bentuk Kanonik

dimana,

PROGRAM LINIER 5

Contoh :

Nyatakan dalam bentuk kanonik :

max

s.t

Bentuk Kanonik :

Max

s.t

PROGRAM LINIER 6

max

s.t

0

PROGRAM LINIER 7

PENYELESAIAN DASAR SISTEM PERSAMAAN LINIER

Sistem Persamaan Linier ditulis sebagai :

A x = b

Agar memiliki penyelesaian tunggal, harus dipenuhi syarat :

- banyaknya persamaan = banyaknya variabel

- A harus memiliki rank penuh yang berarti memiliki invers

Penyelesaiannya adalah :

Dalam program linier akan didapat sistem persamaan linier dengan banyaknya variabel

selalu lebih banyak dari banyaknya persamaan. Akibatnya sistem terseut akan punya

banyak penyelesaian, yang salah satunya adalah penyelesaian dasar yang dapat dicari

sbb :

dimana B adalah matrik bujur sangkar yang mempunyai invers

, berubah menjadi

=

+ =

X

+ =

+ =

= -

Penyelesaian dasar didapat dengan memilih :

PROGRAM LINIER 8

Didapat :

yang berarti :

penyelesaian dasar dari sistem persamaan linier

disebut variabel dasar

disebut variabel bukan dasar

disebut matrik dasar

disebut matrik bukan dasar

Contoh :

Max

s.t

bentuk kanoniknya adalah sbb :

max

s.t

Daerah kelayakannya adalah sbb :

Titik - titik ekstrim :

Penyelesaian dasarnya dapat dicari sbb :

PROGRAM LINIER 9

1x

alternatif 1 :

( titik ekstrim )

alternatif 2 :

( tdk memenuhi )

alternatif 3 :

dst………

PROGRAM LINIER 10

( titik ekstrim )

PENYELESAIAN PROGRAM LINIERDENGAN TABEL ELIMINASI

Menyelesaikan program linier sama saja dengan mencari penyelesaian dasar dari suatu

sistem persamaan linier, karenanya dapat dilakukan dengan menggunakan Eliminasi GAUSS. Untuk itu program linier tersebut dinyatakan dalam bentuk tabel sehingga

memudahkan proses eliminasi Gauss.

Pada proses in dimulai dari suatu penyelesaian dasar yang paling mudah dicari kemudian

pada tiap iterasi berusaha mendapatkan penyelesaian dasar yang memiliki nilai tujuan

( Z ) yang lebih baik dan seterusnya sampai tidak dapat menghasilkan yang lebih tinggi.

Pada saat itu iterasi dihentikan dan penyelesaian dasar yang terakhir adalah penyelesaian

optimal yang dicari.

Telah didapat bahwa :

atau

….. ( 1 )

Untuk nilai tujuan digunakan persamaan sbb :

……… ( 2 )

Bila , penyelesaian dasar yang sekarang sudah

Optimal

PROGRAM LINIER 11

Bila ada yang negatif, ambil yang nilai nya adalah yang paling negatif,

buat supaya variabel ini menjadi variabel dasar

Karena banyaknya variabel dasar adalah tetap, berarti harus ada salah satu variabel

dasar yang juga harus diubah menjadi variabel bukan dasar yaitu variabel dasar yang

menjadi nol karena ada variabel bukan dasar yang nilainya menjadi positip sesuai dengan

persamaan :

Terjadi pertukaran tempat antara salah satu dengan salah satu

Tabel Eliminasi Gauss dapat disusun dari persamaan (1) dan (2) sebagai berikut :

Z

Supaya prosesnya sederhana, sebagai awal dipilih variabel - variabel yang memiliki

koefisien 0 pada tujuan dan koefisien I pada kendala

Contoh 1:

Max

s.t

Bentuk kanonik :

Max

s.t

Z RK

PROGRAM LINIER 12

Z RK

10

0

I

Z 1 -1 -2 0 0 0

0 1 1 1 0 4

0 0 1 0 1 2

Z RK

Z 1 -1 0 0 2 4

0 1 0 1 -1 2

0 0 1 0 1 2

Z RK

Z 1 0 0 1 1 6

0 1 0 1 -1 2

0 0 1 0 1 2

Jadi

Contoh 2 :

Max

s.t

Bentuk Kanonik :

Max

s.t

Z RK

Z 1 -1 -1 0 0 0

PROGRAM LINIER 13

0 1 5 1 0 5

0 2 1 0 1 4

Z RK

Z 1 0 - 0 0 2

0 0 1 0 3

0 1 0 2

Z RK

Z 1 0 0 0

0 0 1 0

0 1 0

Jadi

PROGRAM LINIER 14

METODE SIMPLEK UNTUK PROGRAM LINIER TIDAK STANDAR

Standar :

- Tujuan Memaksimumkan

- Kendala

- Ruas kanan nonnegatif

- Variabel nonnegatif

Tidak Standar :

- Salah satu di atas tidak dipenuhi

1. Tujuan : Meminimumkan

min Z = - ( maks -Z )

2. Variabel tidak nonnegatif

tidak dibatasi

,

3. Ruas kanan tidak non negatif

PROGRAM LINIER 15X -1

Untuk menghadapi kasus dimana kendalanya tidak dalam bentuk ,

( dapat atau = ) perlu ditambahkan variabel semu.

: slack

tidak dapat dipakai sebagai variabel dasar untuk itu ditambahkan variabel semu yang

dapat dipakai sebagai variabel dasar.

: variabel semu yang diasumsikan bernilai

Tetapi melalui sejumlah iterasi harus dibuat menjadi variabel nondasar supaya bernilai

0

Kondisi ini dapat dicapai dengan cara : meminimumkan .

Contoh :

Max

s.t

Bentuk Kanonik :

Max

s.t

min max

Z RK

Za 0 0 0 0 0 1 0

Z 1 -2 -1 0 0 0 0

0 1 1 1 0 0 3

0 -1 1 0 -1 1 1

PROGRAM LINIER 16

Z RK

Za 0 1 -1 0 1 0 -1

Z 1 -2 -1 0 0 0 0

0 1 1 1 0 0 3

0 -1 1 0 -1 1 1

Z RK

Za 0 0 0 0 0 1 0

Z 1 -3 0 0 -1 1 1

0 2 0 1 1 -1 2

0 -1 1 0 -1 1 1

Z RK

Z 1 0 0 - 4

0 1 0 - 1

0 0 1 2

Jadi,

Contoh :

Min

s.t

Penyelesaian :

PROGRAM LINIER 17

Diabaikan, boleh dibuang

Misal :

sehingga,

min

s.t

menjadi,

max

s.t

min max

Z x RK

aZ 0 0 0 0 0 0 1 1 0-1 1 1 2 0 0 0 0 -10 1 -1 1 1 0 0 0 70 2 1 0 0 -1 1 0 20 1 0 2 0 0 0 1 5

Z x RK

aZ 0 -3 -1 -2 0 1 0 0 0-1 1 1 2 0 0 0 0 -10 1 -1 1 1 0 0 0 70 2 1 0 0 -1 1 0 20 1 0 2 0 0 0 1 5

Z x RK

aZ 0 0 ½ -2 0 -1/2 3/2 0 -4-1 0 1/2 2 0 ½ -1/2 0 -20 0 -3/2 1 1 ½ -1/2 0 6

PROGRAM LINIER 18

0 1 ½ 0 0 -1/2 ½ 0 10 0 -1/2 2 0 1/2 -1/2 1 4

Z x RK

aZ 0 0 0 0 0 0 1 1 0-1 0 1 0 0 0 0 -1 -60 0 -5/4 0 1 ¼ -1/4 -1/2 40 1 ½ 0 0 -1/2 ½ 0 10 0 -1/4 1 0 1/4 -1/4 1/2 2

Jadi

PROGRAM LINIER 19

Diabaikan, boleh dibuang