aplikasi metode simplex

Metode Simplex

APLIKASI METODE SIMPLEX

I. Contoh Kasus MAKSIMISASI (dengan kendala semua bertanda )

Maksimumkan : Z = 10X + 15Y

Batasan : 3X + 3Y 36

5X + 2Y 50

2X + 6Y 60

X, Y 0

dimana : X = jumlah unit kursiY = jumlah unit meja

Langkah pertama mengubah pertidaksamaan menjadi persamaan yaitu dengan memasukkan variabel slack (S) :

Maksimumkan : Z = 10X + 15Y + 0.S1 + 0.S2 + 0.S3

Batasan : 3X + 3Y + S1 = 36

5X + 2Y + S2 = 50

2X + 6Y + S3 = 60

X, Y, S1, S2, S3 0

Model di atas sudah dalam bentuk standard karena semua non-negatif, semua kendala sudah dalam bentuk persamaan, dan ruas kanan adalah positif.

Solusi basic awal adalah : X = 0, Y = 0, S1 = 36, S2 = 50, S3 = 60

Nilai fungsi objektif :

Hitung Profit Relatif :

menjadi var. basic

(Profit Relatif dari var. basic tidak perlu dihitung karena nilainya adalah nol).

Profit Relatif terbesar adalah C2 , berarti Y akan dijadikan variabel basicSusun dalam bentuk Tabel :

TABEL I.

CB BasisCj

10 15 0 0 0 Konstanta X Y S1 S2 S3

Bambang S.Soedibjo : Riset Operasi 1

Metode Simplex

0

0

0

S1

S2

S3

3 3 1 0 0

5 2 0 1 0

2 6 0 0 1

36

50

60

10 15 0 0 0 Z=0

Gunakan kaidah minimum untuk menentukan variabel yang akan dikeluarkan dari var. basic.

Nomor Baris Basic Limit Atas utk Y

1 S1 36/3 = 12 2 S2 50/2 = 25 3 S3 60/6 = 10 min.(keluar)

S3 menjadi variabel non-basic, Y jadi variabel basic.

Susun Tabel II dengan tahapan seperti sebelumnya :

1. Tuliskan pertama kali baris Y dimana nilainya diperoleh dari pembagian baris S3 (Tabel I) dengan bilangan 6, agar nilai dalam sistem kanoniknya menjadi satu.

2. Hitung nilai-nilai untuk S1 dan S2 :

Baris S1 Baris S2

3 – ( 3 x 1/3) = 23 – (3 x 1) = 01 – (3 x 0) = 10 – (3 x 0) = 00 – (3 x 1/6) = -1/236 – (3 x 10) = 6

5 – (2 x 1/3) = 13/32 – (2 x 1) = 00 – (2 x 1) = 01 – (2 x 0) = 10 – (2 x 1/6) = -1/350 – (2 x 10) = 30

3. Hitung Profit Relatif

4. Hitung Fungsi Objektif baru :

TABEL II.

CB BasisCj



Metode Simplex

0

0

15

S1

S2

Y

2 0 1 0 -1/2

13/3 0 0 1 -1/3

1/3 1 0 0 1/6

6

30

10

5 0 0 0 -5/2 Z=150

Dengan cara yang sama diperoleh :TABEL III.

CB BasisCj


10015

XS2

Y

1 0 1/2 0 -1/4 0 0 -13/6 1 3/4 0 1 -1/6 0 1/4

3179

0 0 -5/2 0 -5/4 Z = 165

Karena nilai-nilai Profit Relatif tidak ada yang positif, solusi sudah optimal.Jadi fungsi objektif mencapai optimal yaitu Z = 165 dengan X = 3 unit dan Y = 9 unit.

Ringkasan langkah-langkah perhitungan untuk masalah maksimisasi.

Langkah 1. Nyatakan masalah dalam bentuk standard.Langkah 2. Mulai dengan solusi basic awal feasible dalam bentuk kanonik kemudian

buatlah tabel awal.Langkah 3. Gunakan kaidah inner product untuk mendapatkan koefisien profit relatif.

(baris ).Langkah 4. Jika semua koefisien negatif, maka solusi feasible yang baru sudah optimal.

Jika tidak maka pilih variabel non-basic yang memiliki nilai positif terbesar untuk masuk ke dalam basis.

Langkah 5. Gunakan kaidah rasio minimum untuk menentukan variabel basic yang akan keluar dari basis.

Langkah 6. Gunakan operasi pivot untuk mendapatkan tabel baru dan solusi basic yang feasible.

Langkah 7. Hitung koefisien profit relatif dengan menggunakan kaidah inner product. Kembali ke langkah 4.

Untuk problem minimisasi :

Ubah langkah 4 menjadi berikut :

Langkah 4. Jika semua koefisien adalah positif atau nol, maka solusi yang baru adalah optimal. Jika tidak, pilihlah variabel non-basic dengan nilai negative terendah dalam baris untuk masuk kedalam basis.

Catatan :Untuk persoalan minimisasi istilah profit relatif diganti oleh biaya relatif.

Beberapa hal penting.


Metode Simplex

Dalam sebuah tabel mungkin saja terdapat dua jawaban optimal yang sama. Per definisi setiap solusi feasible yang nilainya sama dengan nilai Z yang optimal maka solusi ini juga adalah solusi yang optimal.

Dalam Tabel III (lihat contoh sebelumnya), solusi optimal yang dihasilkan adalah solusi yang tunggal, karena semua variabel non-basic mempunyai nilai negatif. Artinya bahwa setiap penambahan nilai pada variabel x2, x4 atau x5, secara langsung akan mengurangi nilai fungsi objektif. Olehkarenanya adalah tidak mungkin untuk mendapatkan solusi feasible optimal lainnya kecuali Z = 81/5.

Masalah yang muncul dalam perhitungan :

1. Adanya nilai yang sama. Untuk memecahkannya pilih salah satu yang mana saja, meski pilihan yang salah dapat menyebabkan meningkatkan jumlah tabel simplex atau iterasi. Tidak ada satu cara yang dapat dipakai untuk memprediksi yang mana yang harus dipilih.

2. Adanya nilai rasio minimum yang sama. Akibatnya adalah semakin kompleksnya masalah pemecahan yang dihadapi. Meski demikian, secara praktis masalah ini jarang terjadi.

3. Solusi yang tidak terbatas akibat tidak dapat ditentukannya variabel basic mana yang harus keluar. Hal ini terjadi ketika tidak ada satupun dari koefisien kendala dari variabel non-basic (yang akan dipilih untuk masuk ke dalam basis) bernilai positif.

II. Contoh kasus MINIMISASI (semua kendala bertanda )

Vitamin A dan B terdapat dalam dua jenis makanan F1 dan F2. Satu unit makanan F1 berisikan 20 unit Vit. A dan 30 unit Vit. B. Satu unit makanan F2 berisikan 60 unit Vit. A dan 40 unit Vit. B. Satu unit makanan F1 dan F2, masing-masing memerlukan biaya $3 dan $4. Kebutuhan harian (satu orang) akan Vit. A adalah 80 unit dan Vit. B 100 unit. Anggaplah bahwa kelebihan mengkonsumsi dari kebutuhan harian minimum tidak berbahaya bagi seseorang. Hitunglah campuran optimum dari F1 dan F2 dengan biaya yang terendah sehingga memenuhi kebutuhan harian minimum seseorang akan Vit. A dan B.

Nyatakan masalah di atas dalam bentuk standard pemograman linier :

Variabel keputusan : X = jumlah unit makanan F1Y = jumlah unit makanan F2

Minimumkan : Z (total cost) = 3X + 4Y

Batasan : 20X + 60Y 8030X + 40Y 100X, Y 0

Karena batasan masih dalam bentuk pertidaksamaan, ubah batasan di atas dalam bentuk persamaan dengan menambahkan variabel surplus S1 dan S2. (perhatikan, berbeda dengan slack)

20X + 60Y – S1 = 8030X + 40Y – S2 = 100


Metode Simplex

Jika kita set X = Y = 0, maka S1 = -80 dan S2 = -100. Ini tidak mungkin. Disamping itu, sistem persamaan kendala tidak dalam bentuk kanonik, sehingga solusi tidak dapat dilakukan metode simpleks. Olehkarenya digunakan variabel artifisial A, sehingga diperoleh :

20X + 60Y – S1 + A1 = 8030X + 40Y – S2 + A2 = 100

Variabel artifisial ini bisa dianggap sebagai pengganti F1 dan F2 dengan harga yang sangat mahal, katakanlah M. (Oleh karena itu, metode ini dikenal pula sebagai metode Big-M). Harga variabel artifisial ini memungkinkan kita untuk memulai solusi awal dengan melibatkan suatu harga yang sangat mahal dan dijamin tidak akan muncul dalam solusi akhir nanti. Variabel artifisial umumnya digunakan untuk batasan atau kendala dengan tanda lebih besar atau sama dengan ()

Dengan demikian, formulasi persoalan pemograman linier di atas menjadi :

Minimumkan : Z (total cost) = 3X + 4Y +0. S1 + 0 S2 + M. A1 + M. A2

Batasan : 20X + 60Y – S1 + A1 = 8030X + 40Y – S2 + A2 = 100X, Y, S1, S2, A2, A2 0

TABEL AWAL

CB BasisCj

3 4 0 0 M M Konstanta X Y S1 S2 A1 A2

M

M

A1

A2

20 60 -1 0 1 0

30 40 0 -1 0 1

80

100

Untuk tabel simpleks, dihitung dahulu :

Fungsi Objektif :

Biaya Relatif :

Diperoleh solusi awal dalam Tabel I berikut :

TABEL I.

CB BasisCj



Metode Simplex

M

M

A1

A2

20 60 -1 0 1 0

30 40 0 -1 0 1

80

100

3-50M 4-100M M M 0 0 Z =180M

Karena kolom masih ada yang belum positif, maka solusi belum optimal. Teruskan perhitungan tabel berikutnya.

Dari tabel I diperoleh biaya relatif terkecil adalah , sehingga Y masuk basis.

Kaidah minimum rasio :


1 A1 80/60 = 4/3 (min.) keluar 2 A2 100/40 = 5/2

Lakukan operasi pivot atau kaidah yang telah diberikan sebelumnya serta perhitungan kolom dan fungsi objektif, sehingga diperoleh :

TABEL II.

CB BasisCj


4

M

Y

A2

1/3 1 -1/60 0 1/60 0

50/3 0 2/3 -1 -2/3 1

4/3

140/3

5/3-50/3M 0 1/15-2/3M M 5/3M-1/15 0 Z = 16/3-(140/3)M

Karena baris masih ada yang bernilai negatif, solusi belum optimal. Lanjutkan perhitungan dengan cara yang sama untuk memperoleh Tabel selanjutnya.

TABEL III.

CB BasisCj


4

3

Y

X

0 1 -3/100 1/50 3/100 -1/50

1 0 1/25 -3/50 -1/25 3/50

2/5

14/5

0 0 0 1/10 M M-(1/10) Z = 50

Tabel III memperlihatkan semua nilai bernilai nol atau positif, berarti biaya tidak dapat dikurangi lebih jauh lagi atau solusi sudah optimal.Bambang S.Soedibjo : Riset Operasi 6

Metode Simplex

Solusi optimal adalah membeli 14/5 unit makanan F1 dan 2/5 unit makanan F2 dengan biaya minimum sebesar $50.

3. Contoh kasus MINIMISASI (kendala berjenis , dan )

Perusahaan kimia PD. Gobanggocir harus memproduksi suatu jenis campuran bagi konsumennya sebanyak 10.000 kilogram. Campuran tersebut terdiri dari jenis Cx, Pb, dan N. Harga jenis Cx adalah $8/kg, jenis Pb seharga $10/kg dan jenis N seharga $11/kg. Jumlah jenis Cx yang digunakan tidak lebih dari 3.000 kg, dan paling sedikit 1.500 kg jenis Pb harus digunakan. Sedangkan untuk jenis N digunakan paling sedikit 2.000 kg. Perusahaan ingin meminimumkan biaya produksi, sehingga perlu diketahui berapa jumlah masing-masing bahan yang harus digunakan perusahaan.

Formulasi matematis dari persoalan di atas adalah :

Min. C (total biaya) = 8X +10 Y + 11Z

Dengan batasan : X + Y + Z = 10.000 X 3.000 Y 1.500 Z 2.000

X,Y,Z 0

Dimana :X = jumlah bahan jenis Cx (dalam kilogram)Y = jumlah bahan jenis Pb (dalam kilogram)Z = jumlahbahan jenis N (dalam kilogram)

Langkah selanjutnya adalah dengan mengubah pertidaksamaan menjadi persamaan.

Beberapa hal yang harus diperhatikan :

1. Untuk solusi awal, kita dapat men-set X, Y, dan Z sama dengan nol. Akan tetapi daripada menggunakan variabel slack, lebih baik menggunakan variabel artifisial (A1) yang dianggap sebagai suatu bahan jenis baru dengan harga yang sangat mahal (M).

2. Untuk kendala kedua kita harus menambahkan variabel slack S1 (karena bertanda ). Variabel slack ini dianggap sebagai selisih (kalau ada) antara 3.000 kg dengan jumlah bahan Cx yang sesungguhnya dipakai dalam campuran.

3. Untuk kendala ketiga dan keempat kita perlu menambahkan variabel surplus S2 dan S3

yang memperlihatkan jumlah ekstra (kalau ada) dari kedua bahan Pb dan N untuk campuran termurah. Jika dalam solusi awal X, Y, S2 dan S3 di set nol, maka kita harus memperkenalkan bahan baru katakanlah A2 dan A3, sebagai pengganti bahan Y dan Z dalam solusi pertama. Bahan baru ini bisa dianggap sebagai bahan yang sangat mahal harga per kilogramnya, katakanlah seharga M seperti yang pernah dibahas sebelumnya. Harga yang sangat mahal, menjamin bahwa keduanya tidak akan muncul dalam solusi akhir.

Dari catatan di atas maka, formulasi matematis dapat disajikan kembali sebagai :


Metode Simplex

Min. C = 8X + 10Y + 11Z + M.A1 + 0.S1 + 0.S2 + M.A2 + 0.S3 + M.A3

Dengan batasan :X + Y + Z + A1 = 10.000 X + S1 = 3.000 Y – S2 + A2 = 1.500 Z – S3 + A3 = 2.000

X, Y, Z, S1, S2, S3, A1, A2, A3 0

Penyajian dalam tabel simpleks :

TABEL AWAL

CiCB Basis 8 10 11 M 0 0 M 0 M Q

X Y Z A1 S1 S2 A2 S3 A3M A1 1 1 1 1 0 0 0 0 0 10.0

00

0 S1 1 0 0 0 1 0 0 0 0 3.00

0

M A2 0 1 0 0 0 -1 1 0 0 1.50

0

M A3 0 0 1 0 0 0 0 -1 1 2.00

0

Z=

Untuk membuat Tabel Simplex I, kita perlu menghitung Z dan nilai-nilai Biaya Relatif untuk diisikan pada tabel diatas. Contoh :

dan seterusnya, kemudian hasilnya masukkan ke dalam baris pada tabel awal, sehingga diperoleh tabel seperti berikut.

TABEL I


Metode Simplex


X Y Z A1 S1 S2 A2 S3 A3M A1 1 1 1 1 0 0 0 0 0 10.0

00

0 S1 1 0 0 0 1 0 0 0 0 3.00

0

M A2 0 1 0 0 0 -1 1 0 0 1.50

0

M A3 0 0 1 0 0 0 0 -1 1 2.00

0

8-M 10-

2M

11-

2M

0 0 M 0 M 0 1650

0M

Dari Tabel I terlihat bahwa kolom Y berisikan nilai yang paling rendah, sehingga Y masuk menjadi var.basic. Sedangkan variabel basic dari kolom CB yang harus keluar adalah dengan menggunakan kaidah rasio minimum :


1 A1 10.000/1 = 10.000

2 S1 3.000/0 =

3 A2 1.500/1 = 1.500 keluar

4 A3 2.000/0 =

Jadi yang harus keluar adalah A2 digantikan oleh Y, sehingga diperoleh Tabel II berikut :

TABEL II


X Y Z A1 S1 S2 A2 S3 A3M A1 1 0 1 1 0 1 -1 0 0 8.500

0 S1 1 0 0 0 1 0 0 0 0 3.000

10 Y 0 1 0 0 0 -1 1 0 0 1.500

M A3 0 0 1 0 0 0 0 -1 1 2.000

8-M 0 11-

2M

0 0 10-

M

2M-

10

M 0 10.50

0M

+15.0

00


Metode Simplex

Karena kolom belum ada yang positif, maka lanjutkan proses seperti di atas, sehingga diperoleh Tabel-tabel berikut ini, sampai kolom berisikan nilai nol atau positif.

TABEL III


X Y Z A1 S1 S2 A2 S3 A3M A1 1 0 1 1 0 1 -1 1 -1 6.50

0

0 S1 1 0 0 0 1 0 0 0 0 3.00

0

10 Y 0 1 0 0 0 -1 1 0 0 1.50

0

11 Z 0 0 1 0 0 0 0 -1 1 2.00

0

5-M 0 0 0 0 10-

M

2M-

10

11-

M

2M-

11

6500

M+

3700

0

TABEL IV


X Y Z A1 S1 S2 A2 S3 A3M A1 0 0 0 1 -1 1 -1 1 -1 3.50

0

8 X 1 0 0 0 1 0 0 0 0 3.00

0

10 Y 0 1 0 0 0 -1 1 0 0 1.50

0

11 Z 0 0 1 0 0 0 0 -1 1 2.00

0


Metode Simplex

0 0 0 0 M-8 10-

M

2M-

10

11-

M

2M-

11

3500

M+

6100

0

TABEL V


X Y Z A1 S1 S2 A2 S3 A3

0 S2 0 0 0 1 -1 1 -1 1 -1 3.50

0

8 X 1 0 0 0 1 0 0 0 0 3.00

0

10 Y 0 1 0 1 -1 0 0 1 -1 5.00

0

11 Z 0 0 1 0 0 0 0 -1 1 2.00

0

0 0 0 M-

10

2 0 M 1 M-1 610

00

Dari Tabel V tampak bahwa semua nilai sudah bernilai positif atau nol, oleh karenanya solusi sudah optimal yaitu menggunakan bahan jenis Cx sebanyak 3.000 kg, Pb sebanyak 5.000 kg dan jenis N sebanyak 200 kg dengan biaya sebesar $61.000.

4. Contoh kasus MAKSIMISASI (kendala berjenis , dan )

Maksimumkan : Z (total profit) = 5X + 6Y

Dengan kendala : X + Y = 5X 2Y 4X, Y 0

dimana, X = jumlah jenis P (kg) dalam kemasan Y = jumlah jenis Q (kg) dalam kemasan

Fungsi objektif dan kendala diubah menjadi :

Maksimumkan : Z = 5X + 6Y – M.A1 + 0.S1 – M.A2 + 0.S2


Metode Simplex

Dengan kendala : X + Y + A1 = 5X – S1 + A2 = 2 Y + S2 = 4 X, Y, S1, S2, A1, A2 0

Selanjutnya dibuat Tabel I dengan cara perhitungan seperti yang telah dicontohkan sebelumnya (dalam contoh ini, prosedurnya tidak diberikan secara rinci)

TABEL I

CB Basis 5 6 -M 0 -M 0 QX Y A1 S1 A2 S2

-M A1 1 1 1 0 0 0 5

-M A2 1 0 0 -1 1 0 2

0 S2 0 1 0 0 0 1 4

5+2

M

6+M 0 M 0 0 Z= -5M-

2M

Profit relatif maksimum terdapat pada kolom X, berarti X akan masuk ke dalam basis. Sedangkan A2 memberikan kontribusi terkecil (2/1), jadi A2 keluar dari basis.

TABEL II


M A1 1 1 1 0 0 0 3

5 X 1 0 0 -1 1 0 2

0 S2 0 1 0 0 0 1 4

0 6+M 0 5+M -5-

2M

0 Z= 3M-

10

Nilai optimum dalam Tabel II adalah Y dan menggantikan baris yang berisikan A2.

TABEL III


6 Y 1 1 1 0 0 0 3

5 X 1 0 0 -1 1 0 2

0 S2 0 1 0 0 0 1 1Bambang S.Soedibjo : Riset Operasi 12

Metode Simplex

0 0 -6-M -1 1-M 0 Z = 28

Tabel III memperlihatkan bahwa profit relatif sudah bernilai 0 atau negatif, berarti solusi sudah optimal. Dengan demikian dapat disimpulkan bahwa solusi optimal dari persoalan di atas adalah menggunakan bahan jenis P sebanyak 2 kg dan jenis Q sebanyak 3 kg dalam setiap kemasan dengan profit maksimum sebesar 28.

DEGENERASI DALAM PEMOGRAMAN LINIER

Metode Simplex adalah suatu proses iteratif yaitu dari satu tabel ke tabel lainnya sampai solusi optimal dicapai. Seperti pernah disampaikan sebelumnya bahwa dalam menentukan baris atau kolom yang harus diganti, maka ada dua kemungkinan terjadi :

1. Untuk sebuah tabel simplex, satu atau dua entri dalam kolom Q (konstanta) mungkin saja bernilai nol. Jika hal ini terjadi, maka proses melanjutkan dari tabel ini tidak dapat dilakukan karena variabel yang akan diganti sudah bernilai nol.

2. Dalam menentukan baris mana yang harus diganti mungkin saja kita dihadapkan oleh rasio minimum bernilai sama dari dua atau lebih variabel.

Dua keadaan di atas menimbulkan fenomena yang disebut sebagai degenerasi yang dapat mengakibatkan persoalan pemograman linier tidak dapat diselesaikan. Meski kita dapat memilih yang mana saja (memilih secara sembarang rasio minimum), akan tetapi bisa saja kita melakukan pilihan yang salah. Dengan demikian kita harus mengulang kembali untuk memilih variabel lainnya.

Dengan tersedianya berbagai perangkat lunak untuk persoalan pemogram linier ini, maka masalah-masalah seperti ini sudah bukan hambatan lagi dalam menyelesaikan persoalan tersebut.

TOPIK LAIN DALAM PEMOGRAMAN LINIER

Metode Simplex Revisi

Metode ini sebenarnya menggunakan dasar perhitungan yang sama dengan metode simples biasa. Perbedaannya terletak pada penyajian tabel simplexnya. Pada setiap iterasi tabel simplex tidak pernah dihitung. Informasi yang dibutuhkan untuk memindahkan satau solusi basic yang feasibel ke yang lainnya langsung dihasilkan dari sistem persamaan awal. Implikasi dari cara ini adalah berkurangnya pekerjaan perhitungan dan waktu yang digunakan dalam menghitung simplex. Hampir semua perangkat lunak yang tersedia di pasaran saat ini menggunakan metode simplex revisi ini. Salah satu program komputer yang cukup dikenal dalam pemograman linier ini adalah LINDO (Linear, INteractive, and Discrete Optimizer)


Metode Simplex

yang dikeluarkan oleh LINDO System Inc. Contoh luaran dari program ini dapat dilihat dalam lampiran bab ini.

Analisis Sensitivitas

Hampir semua model pemograman linier, koefisien fungsi objektif dan kendala merupakan data input atau sebagai parameter dari model. Solusi optimal yang diperoleh berdasarkan metode simplex didasarkan pada nilai-nilai ini. Dalam prakteknya, nilai-nilai ini jarang diketahui secara absolut. Variasi dalam nilai-nilai ini mengubah persoalan pemograman linier yang akan berakibat pada solusi yang telah diperoleh. Tujuan dari analisis sensitivitas atau analisis postoptimality adalah untuk mengkaji bagaimana solusi optimal akan berubah sesuai dengan perubahan nilai-nilai koefisien input. Tentunya dalam beberapa kasus, solusi persoalan tidak perlu dilakukan berulang-ulang. Analisis sensitivitas akan memerlukan variasi satu parameter input hanya sekali saja, sehingga kita dapat memetuskan apakah solusi kita sudah cukup atau tidak.

Latihan

1. Ubahlah program linier berikut dalam bentuk standard :

Minimumkan :

Dengan batasan :

; tidak dibatasi oleh tanda

2. Seorang manajer dari sebuah perusahaan yang memasok perlengkapan perkantoran bertanya kepada anda untuk mempersiapkan suatu skedul untuk memaksimumkan produksi mereka. Perusahaan ini menjual beberapa jenis meja (tipe A, B, C dan D) ke distribusi lokal dengan tingkat harga berikut. Demikian pula ongkos produksi untuk setiap jenis adalah sebagai berikut :

Jenis meja Harga Jual ($) Ongkos Produksi ($)ABCD

28355272

21303954

Untuk skedul jangka pendek, tenaga kerja harus ditetapkan dalam jumlah yang tepat dan produksi meja dilakukan dalam 2 langkah proses yaitu pemotongan dan tahap akhir. Tenaga kerja tidak dapat dipindahkan antara kedua operasi. Proses pemotongan dan tahap akhir masing-masing membutuhkan waktu 6.000 dan 4.000 jam. Jam kerja buruh untuk setiap jenis meja adalah sebagai berikut :

Jenis meja Jam pemotongan

Jam penyelesaian akhir


Metode Simplex

ABCD

49710

11340

Rumuskan persoalan pemograman linier di atas dan carilah solusinya.

3. Sumanto adalah petani yang memiliki 100 hektar lahan pertanian. Komoditas yang ditanam adalah tomat, kol, dan wortel. Masing-masing tanaman ini bisa dijual dengan harga untuk tomat Rp. 3000/kg, kol seharga 2000/kg dan wortel seharga Rp. 2500/kg. Hasil rata-rata pertanian adalah 2.000 kg tomat, 3000 kg kol dan 1000 kg wortel. Harga pupuk yang tersedia adalah Rp. 1000/kg. Sedangkan jumlah pupuk yang dibutuhkan per hektar adalah 100 kg untuk tomat dan 50 kg untuk kol dan wortel. Tenaga kerja yang dibutuhkan untuk menanam hingga memanen adalah 5 orang-hari-kerja untuk tomat dan kol, sedangkan untuk wortel adalah 6 orang-hari-kerja. Total 400 orang-hari-kerja tersedia saat ini. Rumuskanlah persoalan pemograman linier bagi petani tersebut untuk memaksimumkan total profitnya.

4. PT. Ogahrugi membuat empat produk melalui tiga tahapan proses. Kuantitas yang diperlukan untuk produksi yang akan datang adalah :

Produk 1 : 2000 unitProduk 2 : 3000 unitProduk 3 : 3000 unitProduk 4 : 6000 unit

Ada tiga line production dengan tingkat produksi sebagai berikut :

Productionline

Produk 1 2 3 4

Kapasitas maks. (hari)

Biaya/hari

123

150 100 500 400200 100 760 400160 80 800 600

202018

600500400

Total 2000 3000 3000 6000

Rumuskan persoalan pemograman linier untuk meminimumkan biaya produksi dari persoalan di atas dan cari solusinya.

5. Sebuah perusahaan cinderamata membuat dua jenis emblim A dan B. Perusahaan ini memiliki tiga tahapan proses yaitu persiapan, pemotongan dan pengepakan. Setiap proses ini haris dilalui dalam menghasilkan kedua produk tersebut. Rata-rata pembuatan emblim adalah sebagai berikut :

Proses Jenis A (menit/buah)

Jenis B (menit/buah)

PersiapanPemotonganPengepakan

486

323


Metode Simplex

Keuntungan per unit untuk produk A adalah Rp. 2000 dan jenis B Rp. 3000. Jika waktu yang tersedia adalah 1200 menit untuk setiap proses, tentukan skedul produksi optimal. Gunakan metode simplex.

Contoh Luaran Program LINDO

MAX 20 X + 6 Y + 8 Z SUBJECT TO 2) 8 X + 2 Y + 3 Z <= 200 3) 4 X + 3 Y <= 150 4) 2 X + Z <= 50 END

LP OPTIMUM FOUND AT STEP 3

OBJECTIVE FUNCTION VALUE

1) 566.6667

VARIABLE VALUE REDUCED COST X 0.000000 2.222222 Y 50.000000 0.000000 Z 33.333332 0.000000

ROW SLACK OR SURPLUS DUAL PRICES 2) 0.000000 2.666667 3) 0.000000 0.222222 4) 16.666666 0.000000

NO. ITERATIONS= 3

RANGES IN WHICH THE BASIS IS UNCHANGED:


Metode Simplex

OBJ COEFFICIENT RANGES VARIABLE CURRENT ALLOWABLE ALLOWABLE COEF INCREASE DECREASE X 20.000000 2.222223 INFINITY Y 6.000000 INFINITY 0.666667 Z 8.000000 1.000000 1.250000

RIGHTHAND SIDE RANGES ROW CURRENT ALLOWABLE ALLOWABLE RHS INCREASE DECREASE 2 200.000000 49.999996 99.999992 3 150.000000 150.000000 75.000000 4 50.000000 INFINITY 16.666666


aplikasi metode simplex

Documents