Metode Simplex By: Rita Wiryasaputra, ST., M. Cs.
• Daerah yang memenuhi semua kendala daerah fisibel • Hasil utama Linear Programming ditemukan oleh Dantzig • Pencarian titik optimum dengan 2 cara : grafis dan aljabar
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]
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)
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
Perlu diperhatikan : • Bahwa metode simpleks hanya bisa dipakai (diaplikasikan) pada bentuk standar, sehingga kalau tidak dalam bentuk standar harus ditransformasikan dulu menjadi bentuk standar.
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 X 1 , 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 + S 4 = 5 Fungsi tujuan: Maks Z = 4 X1 + 5 X2 + 0 S1 + 0 S2 + 0 S3 + 0 S4
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?
Solution Kite ‘N String X1 = number of diagonal to be produced X2 = number of box kite to be produced Max = 3 X1 + 5 X2 • 8 X1 + 6 X2 ≤ 10000 (square feet of paper constraint) • 5 X1 + 10 X2 ≤ 12000 (linear feet of wood constraint) • X1 + X2 = 1500 • X1 ≥ 0 ( first nonnegativity constraint) • X2 ≥ 0 ( second nonnegativity constraint)
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
• If the objective is to maximize cumulative total exposure (as measured by circulation) for the month of August, formulate and solve a linear program to determine the optimal placement of ads by PMA in the newspaper during August. Comment on the validity of the “no interaction” assumption of linear programming for this model • Diasumsikan : X1 = Weekdays dan X2 = Sunday
Manufacturing Golden Electronics •
• • • •
MANUFACTURING. Suppose that management at Golden Electronics (see problem 2) has decided to do extensive testing on every television manufactured to ensure its quality standards. Each GE45 television will require inspection time of 30 minutes and each GE60 television 45 minutes Reformulate the linear program for television production for Golden Electronics if management made available 80 hours for quality control Diasumsikan : X1 = GE45 dan X2 = GE60 30 minute ≈ 0.5 hours 45 minute ≈ 0.75 hours
Give an optimal solution that manufactures as many GE60 television sets as possible
Give an optimal solution that manufactures exactly three times as many GE45 television sets as GE60 television sets during a shift
