Beberapa Asumsi Yang Berlaku Dalam LP :
PENDAHULUAN Tujuan utama suatu usaha bisnis : memaksimumkan laba atau meminimumkan biaya. Untuk itu,pasti usaha itu memiliki berbagai kendala sumberdaya Baik tujuan maupun kedala pada umumnya dalam kondisi deterministik. Suhubungan dengan itu, Linier Programming (LP) memberikan solusi dalam pengambilan keputusan usaha bisnis tersebut . Linier programming adalah suatu teknik atau cara yang membantu dalam keputusan mengalokasi sumberdaya yang dimiliki perusahaan. Sumberdaya tersebut meliputi misalnya, mesin-mesin, tenaga kerja, uang, waktu, kapasitas gudang (ruangan), material , dll., yang akan digunakan untuk memproduksi barang (sandang, pangan, papan, dll) atau jasa (rencana pengiriman dan produksi, keputusan investasi, kebijakan advertensi, dll)
Sejarah Linier Program
Persyaratan Yang Diperlukan Dalam L P :
LP telah dikembangkan sebelum perang dunia II oleh matematikawan Rusia, A.N. Kolmogorov dan Leonid Kantorovic penerima nobel “Optimasi Perencanaan”.
1. Perusahaan mempunyai tujuan,yaitu memaksimumkan laba atau miminimumkan biaya
Dalam aplikasi berikutnya LP dikembangkan oleh Stigler (1945) dalam persoalan Diit (kesehatan).
2. Perusahaan mempunyai kerterbatasan atau kendala sumberdaya dalam mencapai tujuan. 3. Perusahaan mempunyai keputusan atau kegiatan alternatif, salah satu diantaranya dipakai atau dipilih untuk mencapai tujuan. 4. Tujuan dan kendala dinyatakan dalam hubungan persamaan ( = ) dan pertidaksamaan ( < / > ) matematik yang linier.
Perkembangan berikutnya (1947), George D. Dantzig mengembang kan solusinya dengan metode simplex. Jasa Dantzig ini luar biasa sehingga kita kenal sampai sekarang dengan istilah “Linier Program-ming”. Dia seorang matematikawan di Angkatan Udara Inggris menja- bat sebagai kepala Pengendali Analisis Perang Angkatan Udara. Saat itu militer memerlukan sekali program perencanaan latihan militer, pemasokan peralatan dan amunisi, penempatan unit-2 tempur. Dantzig memformulasikan sistem pertidaksamaan linier. Setelah perang dunia II aplikasi dalam dunia bisnis luar biasa, misalnya dalam usaha pengolahan, jasa, pertanian, dll. Tahun 1984 N.Karmarkar mengembangkan model yang lebih su-perior dari metode simplex utk berbagai aplikasi yg lebih luas.
Metode Grafik / Maksimasi
METODE GRAFIK PERSOALAN MAKSIMASI . CONTOH : PERUSAHAAN
XYZ
Sebuah industri XYZ berkecimpung dalam proses produksi dua macam produk, yaitu produk A dan B. Kedua produk tesebut dapat dijual masing-masing dengan harga Rp 3000,00 per unit. Dalam proses produksinya diperlukan tiga macam departemen, yaitu Departemen P yang memiliki 3 unit mesin tipe P, Departemen Q memiliki 6 unit mesin tipe Q dan Departemen R memiliki 9 unit mesin tipe R. Lama waktu pemakaian mesin mesin tersebut berbeda untuk setiap produk. Produk A memerlukan waktu 2 jam untuk proses produksinya pada mesin tipe P, kemudian 2 jam pada mesin tipe Q dan 4 jam pada mesin tipe R. Sedangkan untuk produk B memerlukan waktu 1 jam pada mesin tipe P, kemudian 3 jam pada mesin tipe Q dan 3 jam pada mesin tipe R. Lamanya waktu mesin-mesin tersebut berope-rasipun sangat terbatas, yaitu mesin tipe P beroperasi selama 10 jam per hari per mesin, kemudian mesin tipe Q dapat beroperaasi 10 jam per hari per mesin dan mesin tipe R beroperaasi selama 8 jam per hari per mesin. - Rumuskan persoalan tsb. dalam model program linier (formula matematika) ! - Gambarlah persoalan LP tersebut dan Hitunglah berapa produk A dan B harus dijual sehingga penerimaannya maksimal
Dari contoh persoalan LP di atas, dapat diringkas pada tabel berikut :
1.Kondisi-kondisi bisnis dalam perusahaan dalam kepastian dimana nilai-nilai, jumlah-jumlah dalam fungsi tujuan dan kendala diketahui dengan pasti (deterministik), tidak berubah selama periode analisis. 2.Hubungan dalam fungsi tujuan dan kendala adalah proporsional dalam bentuk matematik yang linier, contoh : L = 10 X jika X = 2, maka L = 20 jika X = 4, maka L = 40 M < 60X jika X = 2, maka M < 120 jika X = 5, maka M < 300 3.Bentuk fungsi tujuan dan kendala besifat aditivity, artinya jumlah total nilai kegiatan = penjumlahan dari nilai-nilai kegiatan individu : L = $3 X1 + $5 X2 Jika X1 = 10 dan X2 = 20, maka L = $3(10) + $5(20) = $ 130. 4.Barang dan jasa yang dihasilkan (variabel keputusan) harus positif bukan negatif (non negatively) paling tidak nol (tidak menghasilkan)
Model Formulasi Model LP berisikan beberapa komponen dan karakteristik tertentu. Komponen adalah Fungsi Tujuan dan Fungsi Kendala, yg didalamnya terdapat Variabel Keputusan dan Parametrer. Variabel Keputusan adalah simbul matematik dari kegiatan yang dilakukan oleh perusahaan, misalnya : X1 = jml. Radio, X2 = jml. Televisi dan X3 = jml Kulkas yang akan diproduksi Parameter adalah nilai-nilai di depan variabel keputusan yang pada dasarnya sudah diketahui. Fungsi Tujuan merupakan hubungan matematika linier yg menggambarkan tujuan perusahaan baik memaksimumkan laba atau meminimumkan biaya untuk membuat variabel keputusan. Fungsi Kendala juga merupakan hubungan linier antar variabel keputusan yg menggambarkan keterbatasan sumberdaya. Misalnya, keterbatasan dlm. jumlah Tenaga Kerja utk memproduksi radio sebesar 40 jam/hari selama periode produksi. Nilai-nilai Konstanta dalam fungsi tujuan atau kendala juga merupakan parameter.
•
Max. TR = 3000A + 3000B
Sd
A
B
Kap.
P : 2A + B < 30 Jika A = 0 , maka B = 30
P
2
1
< 30
Jika B = 0 , maka A = 15
Q
2
3
< 60 < 72
R
4
3
Harga
3000
3000
Metode Grafik / Maksimasi
GAMBAR FUNGSI KENDALA
Stc.
P :
2A +
B < 30
Q :
2A + 3B < 60
R :
4A + 3B < 72 A,B
>
0
•
Kemudian dengan lebih mudah dapat disusun formulasi matematisnya : Max. TR = 3000A + 3000B Stc.
P :
2A + B < 30
Q :
2A + 3B < 60
R :
4A + 3B < 72 A, B
> 0
1
Metode Grafik / Maksimasi
Metode Grafik / Maksimasi
FISIBLE AREA dan ISO REVENUE
KEPUTUSAN BERALTERNATIF
TR = 3000A + 3000B B =
B
•
0 45000 60000 63000 66000 > 66000
P
TR
/3000 - A
= 3000(0) + 3000(0) = 3000(15) + 3000(0) = 3000(0) + 3000(20) = 3000(9) + 3000(12) = 3000(6) + 3000(16) = IMPOSIBLE
1) Antara titik A dan B 2) Antara titik B dan C
• • Q
3) Antara titik C dan D
A
•
Solusi : Produk A = 6 unit Produk B = 16 unit TR = $ 66000
B
•
Evaluasi Sumberdaya : P : 2(6) + 1(16) = 28 jam sisa 2 jam Q : 2(6) + 3(16) = 60 jam persis R : 4(6) + 3(16) = 72 jam persis
C
•
R
•
•
D
•
A
Metode Grafik / Maksimasi
- Variabel slack S1, S2 dan S3 merupakan nilai yang diperlukan untuk membuat sisi sebelah kiri persamaan menjadi sama dengan sisi sebelah kanan. Misalnya secara hipotetis, A = 9 dan B = 10. Masukkan kedua nilai itu kedalam persamaan : P : 2(9) + 10 + S1 = 30 S1 = 2 Q : 2(9) + 3(10) + S2 = 60 S2 = 12 R : 4(9) + 3(10) + S3 = 72 S3 = 6 - Dalam contoh di atas, menghasilkan solusi yang tidak menghabiskan jumlah sumberdaya. Pada kendala P hanya menggunakan 28 jam, berarti sisa 2 jam yang tidak digunakan. Jadi S1 merupakan jumlah waktu yang tidak digunakan pada sumberdaya P atau disebut slack P. Demikian juga pada kendala Q dan R masing-masing mempunyai slack Q dan slack R sebagai sisa 12 jam dan 6 jam yang tidak digunakan. - Jika perusahaan belum melakukan kegiatan produksi, maka seluruh kapasitas sumberdaya masih utuh, sehingga slacknya masing-masing sebesar 30, 60 dan 72 jam
KASUS MINIMASI
Pengaruh Variabel Slack Terhadap Fungsi Tujuan
Metode Grafik / Maksimasi
Metode Grafik / Maksimasi
Fungsi tujuan dari contoh adalah : TR = 3000 A + 3000 B. Koefisien 3000 dan 3000, masing-masing merupakan kontribusi TR setiap A dan B. Lalu, apa wujud kontribusi variabel slack S1 dan S2 ?. Variabel slack tidak mempunyai kontribusi apapun terhadap TR sebab variabel slack merupakan sumberdaya yg tidak digunakan. TR dicapai hanya setelah sumberdaya digunakan dlm proses produksi. Dengan demikian variabel slack dalam fungsi tujuan dapat ditululis :
A = 0 B = 20 TR = 60000 S1 = 10 S2 = 0 S3 = 12
A = 6 B = 16 TR = 66000 S1 = 2 A = 9 S2 = 0 B = 12 S3 = 0 TR = 63000 S1 = 0 X S2 = 6 S3 = 0
•w
TR = 3000A + 3000 B + 0S1 + 0S2 + 0S3
Max. TR = 3000 A + 3000B Kendala : 2A + B + S1 2A + 3B + S2 4A + 3B + S3 A, B , S1, S2 dan S3
•
Z
•
Metode Grafik / Minimasi GAMBAR FUNGSI KENDALA
Min. TC = 80A + 100B Stc. MT : 8A + 6B > 24 D : 10A + 4B > 20 S : 6A + 12B > 24 A,B > 0
MT : 8A + 6B > 24 B > 4 – 4 /3 A
B
A
B
Min. TC = 80A + 100B Stc. MT : 8A + 6B > 24 D : 10A + 4B > 20 S : 6A + 12B > 24 A,B > 0
MT : 8A + 6B > 24 B > 4 – 4 /3 A
A
D : 10A + 4B > 20 B > 5 - 2,5 A
A = 15 B = 0 TR = 45000 S1 = 0 S2 = 30 S3 = 12
Metode Grafik / Minimasi
GAMBAR FUNGSI KENDALA
B
30 60 72 0
Y
A, B , S1, S2 dan S3 > 0 Dengan adanya varibel slack, model LP baku secara lengkap dapat ditulis sbb.: Maksimumkan : TR = 3000 A + 3000 B + 0S1 + 0S2 +0S3 Kendala : 2A + B + S1 < 30 2A + 3B + S2 < 60 4A + 3B + S3 < 72 A, B , S1, S2 dan S3 > 0
B
< < < >
•
Seperti halnya pada variabel keputusan (A dan B), variabel slack bernilai non-negative, sebab tidak mungkin sumberdaya itu negatif. Oleh karenanya, model formulasinya :
Metode Grafik / Minimasi
Contoh : Perusahaan Rodio Perusahaan Rodio memproduksi 2 macam bahan pelarut (A dan B). Untuk meproduksi kedua bahan tersebut memerlukan semberdaya Minyak Tanah paling tidak memerlukan 24 liter, Damar minimal 20 liter dan dan Spiritus paling sedikit diperlukan 24 liter. Kebutuhan minyak tanah untuk setiap unit bahan pelarut A diperlukan 8 liter dan bahan pelarut B diperlukan 6 liter, kebutuhan Damar untuk setiap unit bahan pelarut A sebanyak 10 liter dan bahan pelarut B sebanyak 4 liter, dan kebutuhan Spiritus untuk setiap unit bahan pelarut A sebanyak 6 liter dan bahan pelarut B sebanyak 12 liter. Kalau biaya produksi per unit bahan pelarut A dan B masing sebesar Rp 80 dan Rp 100, berapa bahan pelarut A dan B harus diproduksi agar biaya produksi minimal. Selesaikan persoalan ini dengan gambar, evaluasi pula penggunaan bahan bakunya.
Metode Grafik / Maksimasi
Variabel Slack
- Ingat bahwa solusi terjadi pada titik ekstrim, di mana garis persamaan kendala berpotongan satu sama yang lain atau berpotongan dengan sumbu pada grafk. Jadi dalam hal ini, kendala-kendala tsb. lebih dipertimbangkan sebagai persamaan daripada pertidaksamaan. - Prosedur baku untuk merubah pertidaksamaan kendala menjadi persamaan, adalah dengan menambah sebuah variabel baru ke dalam masing-masing kendala, yang disebut sebagai variabel slack. - Untuk contoh perusahaan XYZ di muka, model kendala adalah : P : 2A + B < 30 Q : 2A + 3B < 60 R : 4A + 3B < 72 - Penambahan sebuah variabel slack, S1 pada kendala P, S2 pada kendala Q dan S3 pada kendala R hasilnya dapat dilihat sbb. : P : 2A + B + S1 = 30 Q : 2A + 3B + S2 = 60 R : 4A + 3B + S3 = 72
A
S : 6A + 12B > 24 B > 2 - 0,5 A
A
B
D : 10A + 4B > 20 B > 5 - 2,5 A
A
B
S : 6A + 12B > 24 B > 2 - 0,5 A
A
2
Metode Grafik / Minimasi
FISIBLE AREA dan ISO COST Solusi Optimal : B.Pelarut A = 2,4 unit B.Pelarut B = 0,8 unit TC min = 80 (2,4) + 100(0,8) = Rp 272 Penggunaan Sumberdaya : MT = 8(2,4) + 6(0,8) = 24 Lt. persis D = 10(2,4) + 4(0,8) = 27,2 Lt. > 20 S = 6(2,4) + 12(0,8) = 24 Lt. persis
•( 2, 4 ; 0,8 )
METODE SIMPLEK
METODE SIMPLEK
PENDAHULUAN Kenyataan yang sering dihadapi oleh para manajer dalam pengambilan keputusan adalah kompleks. Keputusan yang harus diambil tidak hanya untuk 2 variabel saja, bisa saja lebih, sementara metode grafik terbatas hanya 2 demensi atau paling banyak mencakup 3 variabel. Untuk mengatasi persoalan linier programming yang kompleks jelas menjadi tidak sederhana. Satu cara sederhana (simple) dan efisien yang dapat menyelesaikan persoalan adalah dengan Metode Smplex, di mana metode ini menggunakan tabel yang unik yang sering disebut “Tabel Simplek”
Metode simplek untuk linier programming dikembangkan pertama kali oleh George Dantzing pada tahun 1947, kemudian digunakan juga pada penugasan di Angkatan Udara Amerika Serikat. Dia mendemonstrasikan bagaimana menggunakan fungsi tujuan (iso-profit) dalam upaya menemukan solosi diantara beberapa kemungkinan solosi sebuah persoalan linier programming. Proses penyelesaiaanya dalam metode simplek, dilakukan secara berulang-ulang (iterative) sedemikian rupa dengan menggunakan pola tertentu (standart) sehingga solusi optimal tercapai. Ciri lain dari metode simplek adalah bahwa setiap solosi yang baru akan menghasilkan sebuah nilai fungsi tujuan yang lebih besar daripada solosi sebelumnya.
Metode Simplek / Maksimasi
Untuk memperoleh pengertian yang lebih mudah dan cepat, dalam pembahasan ini kita gunakan persoalan yang meliputi 2 variabel riil saja (sekedar untuk cross cek) Dengan menggunakan contoh kasus perusahaan XYZ di muka, penyelesaian dapat dilakukan dengan beberapa langkah : Langkah 1. Menyususun Persoalan Dalam Matematik Maksimumkan : TR = 3000 A + 3000 B Kendala : P : 2A + B < 30 Q : 2A + 3B < 60 R : 4A + 3B < 72 A, B > 0
Metode Simplek / Maksimasi
MENGEMBANGKAN SOLUSI KEDUA
Langkah 3. Memasukkan Fungsi Tujuan dan Kendala ke Tabel Simplek Cj Variabel Kuanti 3000 3000 Basis tas A B
0 SP
0 SQ
0 SR
0 0 0
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
2 1 2 3 4 3 0 0 3000 3000
Misal : SP = waktu yang tidak dipakai dlm. Dep. P SP = 30 - 2A - B SQ = waktu yang tidak dipakai dlm. Dep.Q SQ = 60 - 2A - 3B SR = waktu yang tidak dipakai dlm. Dep. R SR = 72 - 4A - 3B
2A + B + SP = 30 2A + 3B + SQ = 60 4A + 3B + SR = 72
Metode Simplek / Maksimasi
30 60 72 0
Mengandung pengertian : tidak selalu kapasitas SD digunakan seluruhnya, diantaranya masih ada yang tersisa ada kelonggaran (slack) untuk menambah sebuah variabel sehingga menjadi persamaan. Variable baru ini disebut Variabel Slack Variabel Slack = sejumlah unit kapasitas yang tidak dipakai dalam suatu Departemen/ SD.
Atau dari persamaan diatas dapat disusun :
TR = 3000 A + 3000 B + 0 SP + 0 SQ + 0 SR . P : 2A + B + 1 SP + 0SQ + 0SR = 30 Q : 2A + 3B + 0SP + 1SQ + 0SR = 60 R : 4A + 3B + 0SP + 0SQ + 1SR = 72
SP SQ SR Zj Cj - Zj
Metode Simplek / Maksimasi
Langkah 2. Mengubah Pertidaksamaan menjadi Persamaan
MENYUSUN SOLUSI AWAL
Zj = aij . Bi Sollusi Awal, belum berproduksi, Zj = 0
Ri
Metode Simplek / Maksimasi
Variabel Slack ini harus dimasukkan dalam fungsi tujuan dan kendala. Koefisien setiap variabel pada kedua fungsi tsb. harus terlihat dengan jelas. Oleh karena itu, untuk variabel yang tidak mempunyai pengaruh terhadap persamaan, koefisiennya harus ditulis dengan “nol”, sehingga tidak merubah hakekatnya. Misalkan, karena : SP, , SQ, dan SR tidak menghasilkan TR, SQ, dan SR tidak berpengaruh terhadap Dep. P, SP dan SR tidak berpengaruh terhadap Dep. Q, dan SP, dan SQ tidak berpengaruh terhadap Dep. R, maka fungsi tujuan dan kendala dapat ditulis sbb. : TR = 3000 A + 3000 B + 0 SP + 0 SQ + 0 SR . P : 2A + B + 1 SP + 0SQ + 0SR = 30 Q : 2A + 3B + 0SP + 1SQ + 0SR = 60 R : 4A + 3B + 0SP + 0SQ + 1SR = 72
Metode Simplek / Maksimasi
Langkah 1. Menentukan Variabel Riil yang akan dimasukkan dalam solusi (going in)
Solusi awal menunjukkan perusahaan masih belum berproduksi. Selanjutnya kita akan melakukan perubahan sehingga TR sebagai tujuan tercapai lebih baik.
Secara rasional, memilih varibel riil yang tepat adalah variabel yang mempunyai kontribusi menambah laba/TR atau mengurangi biaya yang paling besar.
Jika tabel yang telah diperbaiki masih ada kemungkinan dirubah untuk mencapai tujuan yang lebih baik lagi, maka perubahanpun terus berlanjut sampai tercapai solusi yang optimal.
Dengan memilih nilai-nilai baris Cj - Zj pada kolom variabel riil yang terbesar, mengindikasikan adanya peningkatan laba/TR yang lebih baik.
Tahap-tahap perubahan dari tabel satu ke tabel yang lain disebut “pivoting”.
Oleh karena Nilai Cj - Zj untuk kedua kolom variabel riil A dan B sama, maka bisa kita pilih salah satu.
Perhitungan solusi kedua dapat diikuti dengan langkah-langkah berikut ini.
Misalnya saja, kita tentukan kolom B, maka kolom B tersebut dinamakan “kolom optimum”, yang bakal pertamkalinya masuk dalam kolom variabel basis.
3
Metode Simplek / Maksimasi
Langkah 2. Menentukan Variabel yang akan diganti (going out) Pertama kali, kita membagi nilai-nilai dalam kolom variabel basis dengan nilai-nilai pada kolom optimum, dan kemudian hasil bagi-hasil bagi tersebut kita pilih yang paling kecil. Baris yang mempunyai nilai “Ri” terkecil bakal diganti atau dikeluakan dari variabel basis.
VB
Q
3000 3000 A B
Iterasi 2 0 Sp 10 1.3333 0 3000 B 20 0.6667 1 0 Sr 12 2 0 Zj 60000 2000 3000 Cj - Zj 1000 0 Iterasi 3 0 Sp 2 0 0
0 Sp
0 Sq
0 Sr
1 0 0 0 0
- 0.333 0.333 -1 1000 -1000
0 0 1 0 0
1
0,333 - 0,667
3000
B
16
0
1
0
0,67 - 0,33
3000
A
6
1
0
0
- 0,5
Zj 66.000 3000 3000 Cj - Zj 0 0
0 0
0,5
500 500 - 500 - 500
NILAI-NILAI Cj - Zj < 0 SOLUSI OPTIMAL
SOLUSI AWAL
Ri 7.5 30 6
Iterasi 1 0 0 0
VB
Q
Sp Sq Sr Zj Cj - Zj
30 60 72 0
Cj
3000 A
3000 B
0 Sp
0 Sq
0 Sr
2 2 4 0 3000
1 3 3 0 3000
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
Ri 30 20 24
Iterasi 1 0 0 0
Iterasi 2 0 3000 0
VB
Q
3000 A
3000 B
0 Sp
0 Sq
0 Sr
Sp Sq Sr Zj Cj - Zj
30 60 72 0
2 2 4 0 3000
1 3 3 0 3000
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
Sp B
10 20
11/3 2/3
0 1
1 0
-1/3 1/3
0 0
Sr
12
2
0
0
-1
1
Zj Cj - Zj
60000
2000 1000
3000 0
0 0
1000 -1000
0 0
Ri
Menentukan / Menghitung :
30 20 24
Menentukan / Menghitung : - Kolom optimum : pilih nilai Cj - Zj yang terbesar - Baris yang diganti : Pilih nilai Ri yang terkecil Ri = nilai Q / kolom optimum - Nilai baris baru yang masuk : NBBM = NBL : N Insek : 12/2 = 6 ; 2/2 =1 ; 0/2 = 0; 0/2 = 0; -1/2 = - 0,5; 1/2 = 0,5 - Nilai baris baru yang lain : NBBL= NBL(N Intsek x NBBM) Baris Sp : 10 (1,33 x 6) = 2 1,33 (1,33 x1) = 0 0 (1,33 x 0) = 0 1 (1,33 x 0) = 1 - 0,33 (1,33 x -0,5) = 0,33 0 (1,33 x 0,5) = - 0.67 Baris B : 20 (0,67 x6) 0,67 (0,67 x 1) 1 (0,67 x 0) 0 (0,67 x 0) 0,33 (0,67 x - 0,5) 0 (0,67 x 0,5)
Zj Cj - Zj
= = = = = =
16 0 1 0 0,67 - 033
Metode Simplek / Minimasi
Merubah persamaan dan pertidaksamaan pada kendala - Untuk tanda Persamaan ( = ) harus ditambah dengan variabel Artifisial (A) - Untuk Pertidaksamaan”lebih besar sama dengan” ( > ) harus dikurangi variabel surplus (S) dan ditambah variabel Artifisial (A) - Untuk Pertidaksamaan kurang sama dengan ( < ) harus ditambah variabel slack (S) Untuk Kendala : P + C = 200 P + C + A1 = 200 P < 80 P + S1 = 80 C > 60 C S2 + A2 = 60
INTERPERTASI EKONOMI TABEL SIMPLEK Cj Iterasi 3 0 3000 3000
VB
Q
Sp 2 B 16 A 6 Zj 66000 Cj - Zj
3000 A
3000 B
0 Sp
0 0 1 3000 0
0 1 0 3000 0
1 0 0 0 0
Nilai2 pada Kolom Q Tabel 3 : Baris Sp = 2 (Sisa Sbrdaya P) Baris B = 16 (Jml Prduksi B) Baris A = 6 (Jml Prduksi A) Baris Zj = 66000 (TR max.) Anga-angka dalam kwadran matrik (input-outpu) atau diberi simbul aij menunjukkan MRTS atau Koefisien Teknologi antara kegiatan pada kolom dengan sbrdaya pada baris.
SOLUSI AWAL
0 Sq
0 Sr
Ri
0.3333 -0.6667 0.6667 -0.3333 -0.5 0.5 500 500 -500 -500
Nilai2 pada Baris Cj-Zj di bawah ko-lom vaibel riil menunjukkan nilai produk marginal : Jika positif menunjukkan kemung-kinan tambahan TR jika variabel riil ditambah 1 unit Jika negatif menunjukkan pengura-ngan TR jika variabel riil ditambah 1 unit Nilai2 di baris Zj menggambarkan berkurangnya TR (oportunity cost) akibat tambahan 1 unit kegiatan riil atau disposal
Metode Simplek / Minimasi
Secara lengkap : Minimize: Cost = 3P + 8C + 0S1 + 0S2 + MA1 + MA2 P + C + A1 = 200 P + S1 = 80 C S2 + A2 = 60 P, C, S1, S2, A1, A2 > 0
= = = = = =
12 2 0 0 -1 1
Metode Simplek / Minimasi CONTOH : PERUSAHAAN PNT Perusahaan Nutrisi Ternak (PNT) khusus menghasilkan makanan campuran sebagai makanan tambahan, mendapat pesanan makanan campuran "141-B" dengan ukuran/paket 200 pon. Makanan Campuran tersebut terdiri dari dua bahan ramuan , yaitu P (sumber protein) dan C (sumber karbohidrat). Biaya bahan protein sebesar $ 3 per pon, sedang bahan karbohidrat sebesar $ 8 per pon. Dalam makanan campuran itu kandungan Protein (P) tidak boleh melebihi 40 % dan kandungan bahan Carbohidrat (C) paling tidak tersedia 30 %. Persoalan PNT adalah menetapkan berapa banyak masingmasing bahan digunakan agar biaya minimal.
FORMULASI MATEMATIKA PERSOALAN ( IDENTIFIKASI) Minimumkan : Cost = $ 3P+ $ 8C Kendala : P + C = 200 pon P < 80 pon C > 60 pon P dan C > 0
Nilai2 Negatif pada Baris Cj-Zj di bawah kolom variabel Slack : menunjukkan tambahan TR yg dapat dicapai jika ditambahkan 1 jam lagi pada departemen diwakili variabel slack
Koefisien teknologi (para meter) masing-masing variabel , secara ekplisit harus ditulis, dengan ketentuan yang tidak ada pengaruhnya ditulis nol Nilai biaya untuk variabel Artifisial diberi nilai yang sangat besar (M), dan untuk variabel Slack/Surplus = 0
- Nilai baris baru yang lain :
Baris Sr : 72 ( 3 x 20) 4 ( 3 x 2 /3 ) 3 ( 3 x 1) 0 ( 3 x 0) 0 ( 3 x 1 /3 ) 1 ( 3 x 0)
Langkah 1 : menentukan kolom optimum (going in) Langkah 2 : menentukan baris optimum (going out)
- Nilai baris baru yang masuk : NBBM = NBL : N Insek : 60/3 = 20 ; 2/3 = 2/3 ; 3/3 = 1; 0/3 = 0 ; 1/3 = 1/3; 0/3 = 0 NBBL= NBL (N Intsek x NBBM) Baris Sp : 30 ( 1 x 20) = 10 2 ( 1 x 2 /3 ) = 1 1 /3 1 ( 1 x 1) = 0 1 ( 1 x 0) = 1 0 ( 1 x 1/3) = -1/3 0 ( 1 x 0) = 0
Iterasi 3
Elemen-elemen (nilai) pada basis SP, SQ dan SR di bawah kolom optimum, disebut elemen interseksi-onal, yang akan beerperan dalam perhitungan nilai nilai pada tabel berikutnya.
MENGEMBANGKAN SOLUSI KETIGA
Cj
Iterasi 2
Baris SP : 30 / 1 = 30 Baris SQ : 60 / 3 = 20 dikeluarkan Baris SR : 72 / 3 = 24
Cj
Aplikasi Langkah 1 dan Langkah 2
Metode Simplek / Minimasi
SOLUSI TABEL SIMPLEK Cj
BV
$M $0 $M
A1 S1 A2 Zj Cj –Zj A1 S1 C Zj Cj –Zj A1 P C Zj Cj –Zj
$M $0 $8
$M $3 $8
$0 $3 $8
$3 $8 P C 1 1 1 0 0 1 $M $2M $3 $M $8 $2M 140 1 0 80 1 0 60 0 1 $140M+$480 $M $8 $3 - $M $0 60 0 0 80 1 0 60 0 1 $60M+ $720 $3 $8 $0 $0 Quantity 200 80 60 $260M
$M A1 1 0 0 $M $0 1 0 0 $M $0 1 0 0 $M $0
$0 S1 0 1 0 $0 $0 0 1 0 $0 $0 1 1 0 $3 $M $M $3 1 1 1 $5 $5
S2 P C
60 80 120
0 1 0
0 0 1
1 0 1
Zj Cj –Zj
$1200
$3 $0
$8 $0
$8 $M $8
$0 S2 0 0 1 $M $M 1 0 -1 $M-$8 $8-$M 1 0 -1
$M A2 0 0 1 $M $0 -1 0 1 $8-$M $2M-$8 -1 0 1
$M $8 $8 $M 1 0 0
$8 $M $2M$8 -1 0 1
$0 $0
$8 $M - $8
Ri 200 60
140 80 -
- 60 60
4
Metode Simplek / Minimasi
SOLUSI TABEL SIMPLEK Cj $M $0 $M
$M $0 $8
$M $3 $8
$0 $3 $8
BV A1 S1 A2 Zj Cj –Zj A1 S1 C Zj Cj –Zj A1 P C Zj Cj –Zj
$3 $8 P C 1 1 1 0 0 1 $M $2M $3 $M $8 $2M 140 1 0 80 1 0 60 0 1 $140M+$480 $M $8 $3 - $M $0 60 0 0 80 1 0 60 0 1 $60M+ $720 $3 $8 $0 $0 Quantity 200 80 60 $260M
$M A1 1 0 0 $M $0 1 0 0 $M $0 1 0 0 $M $0
$0 S1 0 1 0 $0 $0 0 1 0 $0 $0 1 1 0 $3 $M $M $3 1 1 1 $5 $5
S2 P C
60 80 120
0 1 0
0 0 1
1 0 1
Zj Cj –Zj
$1200
$3 $0
$8 $0
$8 $M $8
Contoh 1: Primal Minimumkan
$0 S2 0 0 1 $M $M 1 0 -1 $M-$8 $8-$M 1 0 -1
$M A2 0 0 1 $M $0 -1 0 1 $8-$M $2M-$8 -1 0 1
$M $8 $8 $M 1 0 0
$8 $M $2M$8 -1 0 1
$0 $0
$8 $M - $8
Ri 200 60
140 80 -
- 60 60
Permasalahan yang pertama disebut dengan “primal” dan permasalahan kedua disebut dengan “dual”. Jadi misalnya, jika permasalahan primalnya adalah maksimasi tujuan dengan kendala tertentu, maka sekarang menjadi dual, yaitu minimasi kendala dengan kendalanya adalah fungsi tujuannya. Demikian sebaliknya, jika permasalahan primalnya adalah menimasi tujuan dengan kendala tertentu, maka sekarang menjadi maksimasi kendala dengan fungsi tujuan sebagai kendalanya.
CONTOH : ( Ek. Mikro) DUAL Minimumkan : B = 30L + 40C Kendala : 300 = L . C L dan C optimum = ?
Maksimumkan : Q = L . C Kendala : 1200 = 30L + 40C L dan C optimum = ?
Jawab
Jawab
Slope Isoquant = Slope Budget Line
Slope Isoquant = Slope Budget Line
2Y1 + 6Y2 + 7Y3 < 5
2)
3Y1 + 8Y2 + Y3 < 2
3)
Y1 + 5Y2 + 3Y3 < 1
= PL/ PC = 30/ 40
dC
MPL / MPC = PL/ PC C / L = 30/ 40 C = 3/ 4 L
1)
Dengan demikian dalam sebuah pemodelan Pemrograman Linear, terdapat dua konsep yang saling berlawanan. Konsep yang pertama kita sebut Primal dan yang kedua Dual.Bentuk Dual adalah kebalikan dari bentuk Primal. Hubungan Primal dan Dual sebagai berikut: Masalah Primal (atau Dual) Masalah Dual (atau Primal) Koefisien fungsi tujuan …………… Nilai kanan fungsi batasan Maksimumkan Z (atau Y) ………… Minimumkan Y (atau Z) Batasan i …………………………… Variabel yi (atau xi) Bentuk < …………………………. yi > 0 Bentuk = …………………………… yi > dihilangkan Variabel Xj ………………………. . Batasan j Xj > 0 ………………………………. Bentuk < Xj > 0 dihilangkan ………………… Bentuk =
CONTOH : USAHA KATERING (RANGSUM)
PRIMAL
Z = 5X1 + 2X2 + X3
Fungsi batasan: 1) 2X1 + 3X2 + X3 > 20 2) 6X1 + 8X2 + 5X3 > 30 3) 7X1 + X2 + 3X3 > 40 X1 , X2 , X3 > 0 Dual Maksimumkan Z ’ = 20Y1 + 30Y2 + 40Y3 Fungsi batasan:
DUALITAS ANTARA MAKSIMASI dan MINIMASI
Untuk setiap permasalahan optimasi yang mempunyai kendala/pembatas, akan terdapat “permasalahan dual”, yaitu dengan memaksimasi atau meminimasi fungsi kendala dan fungsi tujuan sebelumnya menjadi kendalanya. Hubungan ini disebut sebagai dualitas (duality)
/dL 300 2 /L 2
L = 400 Jadi : L = (400)1/2 = 20 dan C = 15 Bmin. = 30(20) + 40 (15 ) = 1200
1200 = 30L + 40 (3 / 4 L ) 1200 = 60L Jadi : L = 20 dan C = 15 Q max. = 20 x 15 = 300
Kasus Primal sebuah usaha kesehatan dalam rangka membuat susunan rangsum dari berbagai bahan makanan dengan biaya murah adalah sbb. : Minimumkan : Z = 150X1 + 100X2 + 350X3 + 250X4 + 320X5 Kendala : Protein : 8,3 X1 + 246 X2 + 17,2 X3 + 5,2 X4 + 2,01 X5 > 70 Karbohidrat : 5 X1 + 26 X2 + 595 X3 + 3,1 X4 + 4 X5 > 3000 Lemak : 0,4 X1 + 793 X2 + 14,8 X3 + 0,6 X4 + 0,16 X5 > 800 Vitamin : 6 X1 + 93 X2 + 61,6 X3 + 6,8 X4 + 2,05 X5 > 40 Zat Besi : 24,9 X1 + 243 X2 + 810 X3 + 16,4 X4 + 0,57 X5 > 12 Dimana :
X1 = Nasi X2 = Sayur X3 = Lauk pauk
X4 = Buah X5 = Susu
Buatlah model Dual persoalan di atas, dan selesaikan !
SOLUSI Cj Langka 1 0 0 0 0 0
JAWAB : Maksimumkan : Z’ = 70Y1 + 3000Y2 + 800Y3 + 40Y4 + 12Y5 Kendala : X1 : 8,3 Y1 + 5,0 Y2 + 0,4 Y3 + 6,0 Y4 + 24,9 Y5 < 150 X2 : 246 Y1 + 26 Y2 + 793 Y3 + 93 Y4 + 243 Y5 < 100
X5 : 2,01 Y1 +
4 Y2 + 0,16 Y3 + 2,05 Y4 + 0,57 Y5 < 320 Y1 , Y 2 , Y 3 , Y 4 , Y 5
> 0
70 Y1
3000 Y2
800 Y3
40 Y4
12 Y5
slack 1 slack 2 slack 3 slack 4 slack 5 zj cj-zj
150 100 350 250 320 0
8.3 246 17.2 5.2 2.01 0 70
5 26 595 3.1 4 0 3,000
0.4 793 14.8 0.6 0.16 0 800
6 93 61.6 6.8 2.05 0 40
24.9 243 810 16.4 0.57 0 12
0 0 0 0 0 slack 1 slack 2 slack 3 slack 4 slack 5 1 0 0 0 0 0 0
0 1 0 0 0 0 0
0 0 1 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 0
slack 1 slack 2 Y2 slack 4 slack 5 zj cj-zj
147.0588 84.7059 0.5882 248.1765 317.6471 1,764.71
8.1555 0 0.2756 245.2484 0 792.3533 0.0289 1 0.0249 5.1104 0 0.5229 1.8944 0 0.0605 86.7227 3,000 74.6218 -16.7227 0 725.3782
5.4824 90.3082 0.1035 6.4791 1.6359 310.5882 -270.588
18.0933 207.605 1.3613 12.1798 -4.8754 4,084.03 -4,072.03
1 0 0 0 0 0 0
0 1 0 0 0 0 0
-0.0084 -0.0437 0.0017 -0.0052 -0.0067 5.042 -5.042
0 0 0 1 0 0 0
0 0 0 0 1 0 0
slack 1 Y3 Y2 slack 4 slack 5 zj cj-zj
147.0294 0.1069 0.5856 248.1206 317.6406 1,842.25
8.0701 0 0.3095 0 0.0212 1 4.9485 0 1.8756 0 311.241 3,000 -241.241 0
5.4509 0.114 0.1007 6.4195 1.629 393.263 -353.263
18.0211 0.262 1.3548 12.0428 -4.8912 4,274.09 -4,262.09
1 0 0 0 0 0 0
-0.0003 0.0013 0 -0.0007 -0.0001 0.9155 -0.9155
-0.0084 -0.0001 0.0017 -0.0052 -0.0067 5.002 -5.002
0 0 0 1 0 0 0
0 0 0 0 1 0 0
Langkah 2
0 0 3,000 0 0
X3 : 17,2 Y1 + 595 Y2 + 14,8 Y3 + 61,6 Y4 + 810 Y5 < 350 X4 : 5,2 Y1 + 3,1 Y2 + 0,6 Y3 + 6,8 Y4 + 16,4 Y5 < 250
Basic Quantity Variable
Langkah3
0 800 3,000 0 0
0 1 0 0 0 800 0
5
Soal N0. 8 Perusahaan mebel Jati Indah memproduksi meja dan kursi dari sumberdaya tenaga kerja dan kayu. Perusahaan memiliki kapasitas terbatas untuk tenaga kerja 80 jam perhari dan 36 Kg kayu perhari. Permintaan atau penjualan kursi terbatas 6 kursi per hari. Untuk memproduksi satu unit kursi memerlukan 8 jam tenaga kerja dan 2 Kg kayu, sedang setiap satu meja memerlukan 10 jam tenaga kerja dan 6 Kg kayu. Laba yang diperoleh untuk setiap meja sebesar Rp 40.000 dan untuk setiap kursi sebesar Rp 50.000. Perusahaan ingin menetapkan jumlah meja dan kursi yang harus dijual agar memperoleh laba maksimum. a. Formulasikan model LP untuk persoalan ini. b. Selesaikan persoalan ini dengan analisis grafik.
Bahan 1 Bahan 2 Minimize
KaP
80000
50000
Antibiotik 1
3
1
>=
Antibiotik 2
1
1
>=
4
Antibiotik 3
2
6
>=
12
Soal N0.12 Perusahaan Kimia Farma memproduksi sebuah obat dengan ramuan dua bahan. Setiap bahan berisi tiga antibiotik yang sama tapi berbeda dalam proporsinya. Satu gram bahan 1 menyumbangkan 3 unit dan bahan 2 menyumbangkan1 unit antibiotik 1; obat membutuhkan 6 unit. Sedikitnya 4 unit antibiotik 2 dibutuhkan, dan per gram bahan masingmasing menyumbang 1 unit. Paling sedikit 12 unit antibiotik 3 diperlukan; satu gram bahan 1 menyumbang 2 unit, dan satu gram bahan 2 menyumbang 6 unit. Biaya per gram bahan 1 dan bahan 2 masingmasing Rp 80.000 dan Rp 50.000. Kimia Farma ingin memformulasikan model LP untuk menetapkan jumlah (gram) ma-sing-masing bahan yang harus digunakan dalam pembuatan obat agar biaya campuran antibiotik itu serendah mungkin. a. Formulasikan model LP untuk persoalan ini. b. Selesaikan persoalan ini dengan menggunakan analisis grafik.
SOAL N0. 8
M
K
Kap
Maximize 40000 50000 Labor
10
8
<=
Kayu
6
2
<=
Demand
0
1
<=
Solution->
3.2
6
80 36 6 428.000
Soal N0.12
KASUS UCP
KASUS Giman Piza
6 X2
Kap.
Sur.
Klaim
16
12
> 450
30
PI
PS
Kap
Slack
Rusak
SD
0,5
1,4
> 25
31
DM
1
1
< 150
17,5
Kompt
1
1
< 40
0
TM
4
8
< 800
0
Sales PI
1
C Solusi
X1
64000 42000 0
40
TC = 168000
SD
Sales PI
KASUS Toko Perhiasan
Sd
K
G
Kap
Emas
30
20
18
Platina
20
40
20
1
40
DG
Slack
Laba 300000 400000 Solusi
0,4
0,3
L=240000
1
Laba
500
750
Solusi
75
62,5
< 75
0
< 125
62,5
84375
KASUS Usaha Ternak
KASUS Obat Sd
B1
B2
Kap
Sur
A1
3
1
>6
0
A2
1
1
>4
0
A3
2
6
> 12
8
TC Solusi
80000 50000 1
3
TC=230000
Min. TC = 60A + 100K Stc. Pr : 20 A + 40 K Lm : 2 A + 0,5 K Prod. : 1 A + 1 K A, K
> 30 > 1 < 1 ,> 0
78,571 43
Sd
A
K
kap
Pr
20
40
> 30
Lm
2
0,5
>1
0
1
1
<1
0,07
Prod
Solusi 0,36 TC
Slack 0
0,57
21,43 57,14 78,57
6
KASUS Della & Pandu
Mak. L = 2C + 2T Stc. K : 8 C + 6 T Tom : 3 C + 6 T B : 3C+ 2T Prod : 1 C + 1 T C, T
78,571 43
KASUS Untitled
Mak. L = 3 X + 2 Y Stc. A : 3 X + 2 Y < 120 F : 1 X + 2 Y < 80 Pro X : 1 X + 0 Y > 10 Pro Y : 0 X + 1 Y > 10 X, Y > 0
< 120 < 90 < 45 < 24
> 0
Sd
C
T
kap
Slack
Sd
X
Y
kap
K
8
6
< 120
0
A
3
2
< 120
0
Tom
3
6
< 90
0
F
1
2
< 80
26,67
3
2
< 45
3
Pro X
1
-
> 10
13,33
< 24
6
1
> 10
0
B
1
1
Solusi
6
12
Laba
Prod
12
24
36
Pro Y
-
Solusi 33,33
10
Laba
20
100
S
120
7
