Latihan Management Science Penyelesaian Aljabar (Metode Simplex)
• Daerah yang memenuhi semua kendala daerah fisibel • Hasil utama Linear Programming ditemukan oleh Dantzig • Pencarian titik optimum dengan 2 cara : grafis dan aljabar
Metode Simpleks • Metode Simpleks umum digunakan untuk menyelesaikan seluruh problem program linier, baik yang melibatkan dua variabel keputusan maupun lebih dari dua variabel keputusan • Pertama kali diperkenalkan oleh George B. Dantzig (1947) • Solusi optimal diperoleh melalui perhitungan yang sama diulang (iteration) • Bahwa metode simpleks hanya bisa dipakai (diaplikasikan) pada bentuk standar, sehingga kalau tidak dalam bentuk standar harus ditransformasikan dulu menjadi bentuk standar.
Penyelesaian Dengan Metode Simpleks • Syarat: Model program linier (Canonical form) harus dirubah dulu kedalam suatu bentuk umum yang dinamakan ”bentuk baku” (standard form) Ciri-ciri bentuk baku Canonical form: • Semua fungsi kendala/pembatas berupa persamaan dengan sisi kanan non-negatif. • Semua variabel keputusan non-negatif. • Fungsi tujuan dapat memaksimumkan maupun meminimumkan
dapat dituliskan : • Fungsi tujuan/objective function : Maks / Min Z = CX • Fungsi pembatas/constraints : AX = b X>0
Transformasi ke bentuk standar:
•
Fungsi Pembatas –
•
Suatu fungsi pembatas yang mempunyai tanda < diubah menjadi suatu bentuk persamaan (bentuk standar) dengan cara menambahkan suatu variabel baru yang dinamakan slack variable (variabel pengurang).
Fungsi Tujuan –
–
Dengan adanya slack variable pada fungsi pembatas, maka fungsi tujuan juga harus disesuaikan dengan memasukkan unsur slack variable ini. Karena slack variable tidak mempunyai kontribusi apa-apa terhadap fungsi tujuan, maka konstanta untuk slack variable tersebut dituliskan nol.
Contoh : • Fungsi tujuan : Maks Z = 4 X1 + 5 X2 • Fungsi pembatas: X1 + 2 X2 < 40 4 X1 + 3 X2 < 120 X1 , X2 > 0
Penambahan slack variable, untuk merubah menjadi bentuk standar : X1 + 2 X2 < 40 X1 + 2 X2 + S1 = 40 4 X1 + 3 X2 < 120 4 X1 + 3 X2 + S2 = 120 Fungsi tujuan menjadi : Maks Z = 4 X1 + 5 X2 + 0 S1 + 0 S2
Contoh 2 : • Fungsi tujuan : Maks Z = 60 X1 + 30 X2 +20 X3 • Fungsi pembatas : 8 X1 + 6 X2 + X3 < 48 4 X1 + 2 X2 < 20 2 X1 + 1,5 X2 + 1,5 X3 < 8 X2 < 5 X1 , X2 , X3 > 0
dengan menambahkan slack variable, menjadi : 8 X1 + 6 X2 + X3 < 48 8 X1 + 6 X2 + X3 + S1 = 48 4 X1 + 2 X2 < 20 4 X1 + 2 X2 + S2 = 20 2 X1 + 1,5 X2 + 1,5 X3 < 8 2 X1 + 1,5 X2 + 1,5 X3 + S3 = 8 X2 < 5 X2 + S4 = 5 Fungsi tujuan: Maks Z = 4 X1 + 5 X2 + 0 S1 + 0 S2 + 0 S3 + 0 S4
Flair Furniture Company • The Flair Furniture Company produces inexpensive tables and chairs. The production process for each is similar in that both require a certain number of hours of carpentry work and a certain number of labor hours in the painting and varnishing department. Each table takes 4 hours of carpentry and 2 hours in the painting and varnishing shop. Each chair requires 3 hours in carpentry and 1 hour in painting and varnishing. During the current production period, 240 hours of carpentry time are available and 100 hours in painting and varnishing time are available. Each table sold yields a profit of $7; each chair produced is sold for a $5 profit. Flair furniture’s problem is to determine the best possible combination of tables and chairs to manufacture in order to reach the maximum profit.
Solution Flair Furniture X1 = number of tables to be produced X2 = number of chairs to be produced Max = 7 X1 + 5 X2 • 4 X1 + 3 X2 ≤ 240 (carpentry constraint) • 2 X1 + X2 ≤ 100 (painting and varnishing constraint) • X1 ≥ 0 ( first nonnegativity constraint) • X2 ≥ 0 ( second nonnegativity constraint)
Iterasi Metode Simplex
• Pivot kolom dipilih sedemikian sehingga Cj-Zj = TERBESAR/MAX • Pivot baris dipilih TERKECIL/MIN contoh: diantara = 50 meja dan = 60 meja • NEW Row number = (number in old row) – [number above or below pivot number] * [corresponding number in the new row]
Electrocomp. Corporation • The Electrocomp Corporation manufactures two electrical products: air conditioners and large fans. The assembly process for each is similar in that both require a certain amount of wiring and drilling. Each air conditioner takes 3 hours of wiring and 2 hours of drilling. Each fan must go through 2 hours of wiring and 1 hour of drilling. During the next production period, 240 hours of wiring time are available and up to 140 hours of drilling time may be used. Each air conditioner sold yields a profit of $25. Each fan assembled may be sold for a $15 profit. Formulate and solve this LP production mix situation to find the best combination of air conditioners and fans that yields the highest profit.
Solution Electrocomp. X1 = number of air conditioner to be produced X2 = number of large fans to be produced Max = 25 X1 + 15 X2 • 3 X1 + 2 X2 ≤ 240 (hours of wiring constraint) • 2 X1 + X2 ≤ 140 (hours of drilling constraint) • X1 ≥ 0 ( first nonnegativity constraint) • X2 ≥ 0 ( second nonnegativity constraint)
Product Production Kite ‘N String • Kite ‘N String manufactures old-fashioned diagonal and box kites from high-strength paper and wood. Each diagonal kite, which nets the company a $3 profit, requires 8 square feet of paper and 5 linear feet of wood (including waste). Box kites net a $5 profit and, including waste, require 6 square feet of paper and 10 linear feet of wood. Each is packaged in similar boxes. This week Kite ‘N String has 1500 boxes and capacity to tailor 10000 square feet of paper and 12000 linear feet of wood for kite production. How many of reach type of kite do you recommend Kite ‘N String produce this week?
Advertising • Print Media Advertising (PMA) has been given a contract to market Buzz Cola via newspaper ads in a major Southern newspaper, Fullpage ads in the weekday editions (Monday through Saturday) cost $2000, whereas on Sunday a full-page ad costs $ 8000. Daily circulation of the newspaper is 30000 on weekdays and 80000 on Sunday. • PMA has been given a $40000 advertising budget for the month of August. The experienced advertising executives at PMA feel that both weekday and Sunday newspaper ads are important; hence, they wish to run the equivalent of at least eight weekday and at least two Sunday ads during August. (Assume that a fractorial ad would simply mean that a smaller ad is placed on one of the days; that is, 3,5 ads would mean three full-page ads and one one-half page ad. Also assume that smaller ads reduce exposure and costs proportionately) This August has 26 weekdays and 5 Sundays
