Model Program Linier

Bentuk Umum  Model Pemrograman Linear

Memaksimumkan / Meminimumkan 

dengan batasan-batasan 

 

Langkah-Langkah Perumusan Model Pemrograman Linear

1. Menentukan variabel-variabel keputusan
2. Merumuskan Fungsi Tujuan
3. Merumuskan Batasan-Batasan

Contoh. Hi-Tech. Inc., sebuah perusahaan kecil manufaktur, memproduksi dua buah switch microwave, yaitu switch A dan switch B. Laba penjualan satu unit switch A adalah 20 $, sedangkan untuk switch B adalah 30 $. Berdasarkan suatu perjanjian, Hi-Tech harus memproduksi paling sedikit 25 unit switch A setiap minggu, dan berdasarkan permintaan, Hi-Tech dapat menjual semua produknya. Perusahaan menginginkan untuk memaksimumkan laba penjualan setiap minggu dengan berbagai keterbatasan yang dimiliki perusahaan, yaitu :

                   waktu perakitan : tersedia 240 jam setiap minggunya

                   waktu pengujian : tersedia 140 jam setiap minggunya.

Satu unit switch A membutuhkan 4 jam perakitan dan 1 jam pengujian, sedangkan satu unit switch B membutuhkan 3 jam perakitan dan 2 jam pengujian.

1.   Menentukan variabel-variabel keputusan

     Menentukan jumlah switch A dan switch B yang harus diproduksi sedemikian sehingga laba setiap minggunya paling besar atau maksimum. Variabel-variabel keputusannya adalah :

                    : jumlah switch A yang diproduksi setiap minggu

                    : jumlah switch B yang diproduksi setiap minggu.

     Adalah sesuatu yang mustahil perusahaan memproduksi sejumlah bilangan negatif switch A dan switch B. Jadi haruslah .

2.   Merumuskan fungsi tujuan

     Tujuan perusahaan adalah memaksimumkan laba penjualan switch A dan switch B setiap minggu. Karena laba penjualan satu unit switch A adalah 20 $ dan untuk switch B adalah 30 $, maka laba penjualan  buah switch A dan  buah switch B setiap minggu adalah , sehingga fungsi tujuannya dapat dituliskan sebagai     

                                      Memaksimumkan .

3.   Merumuskan batasan-batasan

·         Waktu perakitan yang dibutuhkan untuk memproduksi  buah switch A dan  buah switch B setiap minggu adalah  karena satu unit switch A membutuhkan 4 jam perakitan dan satu unit switch B membutuhkan 3 jam perakitan. Selanjutnya, karena waktu perakitan yang tersedia setiap minggunya adalah 240 jam, maka diperoleh bahwa

                                           .

·         Waktu pengujian yang dibutuhkan untuk memproduksi  buah switch A dan  buah switch B setiap minggu adalah  karena satu unit switch A membutuhkan 1 jam pengujian dan satu unit switch B membutuhkan 2 jam pengujian. Selanjutnya, karena waktu pengujian yang tersedia setiap minggunya adalah 140 jam, maka diperoleh bahwa

                                           .

·         Hi-Tech harus memproduksi paling sedikit 25 unit switch A setiap minggu. Ini berarti .

Akhirnya kita dapatkan model pemrograman linier untuk masalah seperti pada contoh, yaitu

                   Memaksimumkan

                   dengan batasan-batasan

                                           

                                           

                                           

                                            .

Bentuk Standar Model Pemrograman Linear

Pada bentuk ini semua tanda “” atau “” pada batasan-batasan “diubah” menjadi tanda “=” dengan cara tertentu. Sebagai contoh lihat masalah pemrograman linier sebelumya, yaitu

                             Memaksimumkan

                             dengan batasan-batasan

                                                    

                                                    

                                                    

                                                     .

Akan kita “masukkan”  variabel-variabel yang tidak negatif pada batasan-batasan untuk “mengubah”  tanda “” atau “” menjadi tanda “=”. Perhatikan batasan pertama yang menggunakan tanda “”. Agar tandanya berubah menjadi “=” maka ruas kiri harus kita tambahkan dengan variabel lain yang tidak negatif, misalkan . Akibatnya, batasan pertama menjadi

.

Batasan kedua juga mempunyai tanda “” sehingga kita perlu menambahkan variabel lain yang non negatif, misalkan . Jadi batasan kedua menjadi

.

Variabel  dan  dinamakan variabel slack yang merupakan kekurangan dari ruas kiri untuk menyamakan dengan ruas kanan pada batasan pertama dan kedua. Selanjutnya, lihat batasan ketiga yang menggunakan tanda “”. Agar tandanya berubah menjadi “=” maka ruas kiri perlu kita kurangi dengan variabel lain yang tidak negatif, misalkan . Akibatnya, kita peroleh

.

Variabel  disebut sebagai variabel surplus yang merupakan kelebihan dari ruas kiri untuk menyamakan dengan ruas kanan  pada batasan ketiga. Akhirnya, diperoleh bentuk standar dari masalah pemrograman linier kita, yaitu

                             Memaksimumkan

                             dengan batasan-batasan

                                                    

                                                    

                                                    

                                                    

Bentuk Matriks Model Pemrograman Linera

Kita sudah memperoleh bentuk standar dari masalah pemrograman linier kita, yaitu

                             Memaksimumkan

                             dengan batasan-batasan

                                                     

                                                     

                                                     

                                                     

Bentuk matriks dari masalah pemrograman linier kita didasarkan pada bentuk standarnya, yaitu

                                      Memaksimumkan

                                      dengan batasan

                                                              

                                                               

dengan

, , , dan .

Penyelesaian Model Pemrograman Linear dengan Menggunakan Metode Simpleks

Contoh. Dengan menggunakan metode simpleks, carilah solusi optimal dari masalah pemrograman linier berikut :

                             Memaksimumkan

                             dengan batasan-batasan

                                                    

Langkah-Langkah Penyelesaian Masalah Pemrograman Linier dengan Menggunakan Metode Simpleks :

1.   Mengubah masalah menjadi bentuk standar. Bentuk standar masalah pada contoh adalah

                             Memaksimumkan

                             dengan batasan-batasan

                                                    

2.   Membuat bentuk matriks dari masalah. Bentuk matriks masalah :

                             Memaksimumkan

                             dengan batasan-batasan

                                                    

     Dalam bentuk matriks tersebut

, , , dan

3.   Membuat tabel berikut.

     Fungsi tujuan  serupa dengan  atau  atau

                                 .                                    (1)

     Barisan angka pada ruas kiri, yaitu 1,-1,-2,0,0 dan angka 0 pada ruas kanan di persamaan (1) akan mengisi baris ke-1 pada tabel I.

    

     Batasan  dapat dituliskan sebagai

                                                                          (2)

     Barisan angka pada ruas kiri, yaitu 0,1,1,1,0 dan angka 4 pada ruas kanan di persamaan (2) akan mengisi baris ke-2 pada tabel I.

Batasan  dapat dituliskan sebagai

                                                                     (3)

Barisan angka pada ruas kiri, yaitu 0,1,3,0,1 dan angka 6 pada ruas kanan di persamaan (3) akan mengisi baris ke-3 pada tabel I.

Kemudian perhatikan matriks

.

Kita akan menentukan variabel dasar pada tabel I dengan cara : pertama, pilih kolom-kolom pada pada matriks  yang membentuk matiks identitas, yaitu kolom ke-3 dan ke-4. Akibatnya, yang menjadi variabel dasar pada tabel I adalah  dan , yang akan diletakkan pada samping kiri tabel I. Jadi kita dapatkan tabel I :

Tabel I

						R.K.
	1	-1	-2	0	0	0
	0 0	1 1	1 3	1 0	0 1	4 6

4.   Perhatikan baris ke-1 pada tabel I. Jika semua angka pada baris ke-1 adalah positif maka proses pencarian solusi optimal selesai. Jika ada angka-angka pada baris ke-1 yang bernilai negatif  maka proses pencarian solusi optimal belum selesai. Selanjutnya lakukan langkah berikutnya.

5.   Diantara angka-angka negatif pada baris ke-1 tersebut pilih yang paling negatif. Kita dapatkan angka -2 sebagai angka yang paling negatif dan angka ini terletak pada kolom . Variabel  kita sebut sebagai variabel masuk yang akan menggantikan salah satu variabel dasar pada tabel I atau yang akan menjadi variabel dasar pada tabel berikutnya.

6.   Perhatikan kolom variabel masuk, dalam kasus contoh ini adalah kolom . Jika angka-angka pada kolom variabel masuk selain pada baris pertama bernilai negatif semua, maka prose pencarian solusi optimal dihentikan, karena hal itu berarti fungsi tujuan tidak terbatas atau tidak memiliki nilai maksimum. Jika terdapat angka-angka yang positif pada kolom variabel masuk selain pada baris pertama maka kita akan pilih salah satu di antara mereka untuk dijadikan sebagai elemen pivot. Sekarang perhatikan tabel I. Lihat kolom  (sebagai variabel masuk) selain pada baris pertama. Kita dapatkan 1 dan 3 sebagai angka yang positif. Kemudian lihat bahwa angka 4 pada kolom R.K. (Ruas Kanan) mempunyai baris yang sama dengan angka 1, dan jika kita bandingkan diperoleh 4/1=4. Kemudian angka 6 pada kolom R.K. mempunyai baris yang sama dengan angka 3, dan jika kita bandingkan diperoleh 6/3=2. Selanjutnya kita pilih angka yang minimum diantara 2 dan 4, yaitu 2. Angka 2 ini berkaitan dengan angka 3 pada kolom  (sebagai variabel masuk). Angka 3 ini kita jadikan sebagai elemen pivot. Angka 3 ini terletak pada baris . Variabel  kita sebut sebagai variabel keluar atau variabel yang akan digantikan oleh variabel masuk sebagai variabel dasar pada tabel berikutnya. Jadi  akan digantikan . Jadi pada tabel berikutnya yang menjadi variabel dasar adalah  dan .

7.  Di tabel berikutnya, pada kolom  (sebagai variabel masuk), elemen pivot yaitu 3 dijadikan 1 dan -2 serta 1 dijadikan 0. Agar 3 (terletak pada baris ke-3 (b3) sebagai baris patokan) menjadi 1 maka 3 harus dikalikan dengan 1/3. Jadi operasi baris elementer yang berlaku pada baris ke-3 yang memuat 3 sebagai elemen pivot adalah 1/3 b3. Selanjutnya, agar -2 (terletak pada baris ke-1 (b1)) menjadi 0, maka -2 harus ditambahkan dengan 2/3 dari 3 (yang merupakan elemen pivot). Jadi operasi baris elementer yang berlaku pada baris ke-1 yang memuat -2 adalah b1+2/3 b3. Kemudian, agar 1 (terletak pada baris ke-2 (b2)) menjadi 0, maka 1 harus ditambahkan dengan -1/3 dari 3 (yang merupakan elemen pivot). Jadi operasi baris elementer yang berlaku pada baris ke-2 yang memuat 1 adalah b2+(-1/3) b3. Dengan menggunakan operasi baris elementer pada masing-masing baris kita peroleh tabel II, yaitu

Tabel II

						R.K.
	1	-1/3	0	0	2/3	4
	0 0	2/3 1/3	0 1	1 0	-1/3 1/3	2 2

8.  Lihat baris pertama pada tabel II, masih terdapat angka negatif yaitu -1/3 yang terletak pada kolom . Dengan cara yang sama dengan langkah sebelumnya, kita peroleh  sebagai variabel masuk dan  sebagai variabel keluar. Yang menjadi elemen pivot adalah 2/3 yang terletak pada kolom  dan baris . Operasi baris elementer pada baris ke-2 sebagai baris patokan adalah       3/2b2. Operasi baris elementer pada baris ke-1 adalah      b1+1/2 b2. Operasi baris elementer pada baris ke-3 adalah b3+(-1/2)b2. Dengan menggunakan operasi baris elementer tersebut, kita dapatkan tabel III, yaitu

     Tabel III

						R.K.
	1	0	0	1/2	1/2	5
	0 0	1 0	0 0	3/2 -1/2	-1/2 1/2	3 1

9.  Lihat Tabel III, pada baris pertama tidak terdapat angka yang negatif. Ini berarti proses pencarian solusi optimal selesai. Perhatikan lagi baris pertama, kolom-kolom variabel dasar bernilai nol, sedangkan pada kolom lainnya bernilai positif. Ini berarti solusi optimalnya adalah tunggal atau hanya satu, yaitu . Namun, seandainya pada baris pertama, selain pada kolom variabel dasar, terdapat kolom yang bernilai nol, maka masalah tersebut memiliki solusi yang banyak.