Pemrograman Linear Dan Penyelesaianya Dengan Metode Grafik

PEMROGRAMAN LINEAR

Kode MK Nama Mata Kuliah Jurusan Dosen

: Tahun Akademik : Teknik Riset Operasi Semester : Teknik Informatika Materi : Adnan Sauddin, S.Pd., M.Si

February 16, 2006

: 2008/2009 :5 : Chapter 2

II. Pengantar Pemrograman Linear Pemrograman linear adalan alat untuk pemecahan masalah optimasi. Metode yang ditelah dikembangkan adalah yang dikenal dengan metode simpleks. Sejak dikembangkan algoritma simpleks, LP telah digunakan untuk pemecahana masalah optimasi dalam industri, seperti – perbankan, pendidikan, kehutanan, perminyakan, perusahaan truk (ekspedisi). 2.1 Contoh Penyelesaian dengan Pemrograman linear Pada bagian sebelumnya diberikan satu contoh yang berkaitan dengan Produksi Mainan yang terbuat dari kayu oleh Giapetto. Bagaimanakah pemrograman linear menyelesaikan masalah optimasi berkaitan dengan kasus tersebut? Berikut akan diberikan apa dan bagaimana sebenarnya pemrograman linear tersebut. Teladan 1: Usaha Ukiran Kayu Giapetto Usaha Ukuran Kayu Giapetto, memproduksi dua jenis Mainan yang terbuat dari kayu: Prajurit Mainan dan Kereta. Satu Prajurit Mainan dijual dengan harga $27 dan proses produksi membutuhkan $10 dari harga material. Setiap Prajurit mainan yang dibuat meningkatkan variable buruh dan kelebihan biaya $14. Untuk Setiap kereta mainan yang dibuat dijual dengan harga $21 dan membutuhkan $9 dari harga material. Untuk setiap pembuatan Kereta Mainan meningkatkan variable buruh dan kelebihan biaya $10. Pembuatan Tentara dan Kereta mainan dari kayu membutuh dua jenis keahlian: Tukang kayu dan Finishing. Satu Prajurit membutuh waktu pengerjaan finishing selama 2 jam dan 1 jam untuk pengerjaan oleh tukang kayu. Untuk Kereta mainan membutuhkan 1 jam untuk finishing dan2 jam untuk pengerjaan oleh tukang kayu. Setiap minggu, Giapetto dapat memenuhi seluruh kebutuhan material, akan tetapi hanya memiliki 100 jam untuk pengerjaan finishing dan 80 jam untuk pengerjaan tukang kayu. Permintaan untuk Kereta mainan dalam jumlah tak terbatas, tapi hanya mencapai 40 unit tentara mainan tiap minggu. Giapetto berkeinginan untuk memaksimumkan keuntungan perminggu (keuntungan – biaya). Rumuskan model matematika dari permasalah tersebut yang dapat digunakan untuk memaksimumkan keuntungan. Abu Abdirrahman

6

PEMROGRAMAN LINEAR

February 16, 2006

Solusi: Dalam mengembangkan model dari kasus diatas, terlebih dahulu kita harus mengetahui karakteristik dari masalah pemrograman linear sebagaimana yang telah dituliskan pada bagian 1, yaitu: Variabel Keputusan: Seluruh bagian dari proses pemecahan masalah dengan menggunakan pemrograman linear, pertama adalah mendefinisikan variable keputusan. Dalam model pemrograman linear, variable keputusan secara lengkap harus menjelaskan keputusan yang akan dibuat. Jelasnya, kasus di atas harus diputuskan berapa banyak Tentara Mainan dan Kereta main yang harus diproduksi tiap minggu. Dalam kasus ini, x1 : Jumlah Tentara Mainan yang harus produksi tiap minggu x2 : Jumlah Kereta Mainan yang harus diproduksi tiap minggu Didefinisikan sebagai variable keputusan Fungsi Tujuan: Dalam banyak permasalahan LP, pembuat keputusan ingin memaksimumkan (pendapatan atau keuntungan) atau meminimumkan (biaya) beberapa fungsi dari variable keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan disebut fungsi tujuan. Dari kasus ini, diketahui biaya tetap (seperti: biaya sewa dan jaminan) tidak bergantung pada nilai x1 dan x2 . Selanjutnya kita dapat berkonsentrasi pada proses memaksimumkan (pendapatan mingguan) – (Biaya pembelian material) – (biaya variable lain). Pendapatan mingguan dan biaya dapat diekspresikan dalam terminology variable keputusan x1 dan x2 . Merupakan tindakan yang kurang bijaksana, jika sebuah perusahaan memproduksi sesuati dimana dia tidak mampu menjualnya, dengan demikian kita asumsikan bahwa seluruh mainan yang diproduksi dari kasus ini akan terjual. Maka pendapatan perminggu = Pendapatan permgg dari prajurit mainan

+ Pendapatan permgg dari kereta mainan  dollar  prajurit   dollar   Kereta  =  +    prajurit  minggu   kereta   minggu  = 27 x1 + 21 x2 Juga, Biaya Material Perminggu = 10 x1 + 9 x2 Abu Abdirrahman

7

PEMROGRAMAN LINEAR

February 16, 2006

Biaya lain-lain perminggu = 14 x1 + 10 x2 Selanjut, perusahaan Giapetto yang memaksimumkan ( 27 x1 + 21 x2 ) − (10x1 + 9x2 ) − (14x1 + 10x2 ) = 3x1 + 2 x2 Fungsi tujuan dari kasus ini adalah: Maksimumkan z = 3 x1 + 2 x2

(0.1)

Kendala ketika x1 dan x2 meningkat, fungsi tujuan pun naik.

Artinya, Giapetto bebas memilih nilai untuk variable x1 dan x2 untuk meningkatkan keuntungan. Namun, perlu diperhatikan bahwa, nilai x1 dan x2 dibatasi oleh tiga keadaan beirkut (selanjut disebut batasan atau konstrain): Batasan 1 Tiap minggu, tidak lebih dari 100 jam waktu yang digunakan untuk pekerjaan finishing Batasan 2 Tiap minggu, tidak lebih dari 80 jam waktu yang digunakan untuk pekerjaan Tukang Kayu Batasan 3 Karena permintaan terbatas, maka prajurit mainan yang harus diproduksi hanya pada kisaran 40 Prajurit mainan tiap minggu. Jumlah material yang dapat diperoleh diasumsikan tidak terbatas, dengan demikian tidak ada pembatasan pada masalah ini. Langkah selanjutnya dalam merumuskan model matematika dari contoh ini adalah menyatakan batasan 1 – 3 dalam terminology variable keputusan x1 dan x2 . Batasan 1 dalam termonologi x1 dan x2 : Total Jam Finishing  Jam Finishing  Pembuatan Praj. Mainan  =   Minggu Minggu  Praj. mainan    Jam Finishing   Pembuatan Kereta  +   Kereta Minggu    = 2( x1 ) + 1 ( x2 ) = 2 x1 + x 2 Secara Lengkap, Rumusan batasan 1 adalah: 2 x1 + x1 ≤ 100

(0.2)

Batasan 2 dalam terminology x1 dan x2 :

Abu Abdirrahman

8

PEMROGRAMAN LINEAR

February 16, 2006

Total Jam Carpentry  Jam Carpentry  Pembuatan Praj. Mainan  =   Minggu Minggu  Praj. mainan    Jam Carpentry   Pembuatan Kereta  +   Kereta Minggu    = 1( x1 ) + 1 ( x2 ) = x1 + x 2 Secara lengkap, Batasan 2 adalah: x1 + x2 ≤ 80

(0.3)

Terakhir, sebagaimana telah disebutkan pada kasus tersebut bahwa jumlah yang dapat diproduksi pada setiap minggunya terbatas, untuk Prajurit mainan terbatas pada 40, hal dapat dinyatakan sebagai satu keterbatan (salah satu fungsi batasan), yaitu: x1 ≤ 40

(0.4)

Kemudian, dari persamaan (0.2)-(0.4) dalam terminology variable keputusan, dinyatakan sebagai batasan untuk masalah pemrograman linear. Setiap nilai yangberkaitan dengan variable keputusan disebut koefisien, contoh koefisien untuk x2 dalam persamaan (0.3) adalah 1, hal ini mengindikasikan bahwa prajurit mainan membutuhkan 1 jam pengerjaan oleh tukang kayu. Bilangan yang terdapat pada bagian sebelah kanan dari masingmasing batasan disebut sisi kanan (right-hand side or rhs). Biasanya rhs batasan merepresentasikan jumlah sumber yang dibutuhkan atau yang tersedia. Tanda Keterbatasan, Untuk melengkapi rumusan dari masalah pemrograman linear, pertanyaan yang harus dijawab yang berkaitan dengan variable keputusan: • Dapatkan variable keputusan dapat diasumsikan sebagai nilai non-negatif? • Apakah variable keputusan memungkinkan untuk diasumsikan bahwa nilai positif dan negative? Jika variable keputusan xi hanya dapat diasumsikan bernilai nonnegative, maka kita tambahkan tanda batasan xi ≥ 0 . Setelah seluruh bagian diselesaikan, mulai dari penentuan Fungsi Tujuan, Variabel Keputusan, Batasan, Tanda batasan, seluruh bagian tersebut dituliskan dalam bentuk system persamaan linear sebagai berikut: Abu Abdirrahman

9

PEMROGRAMAN LINEAR

max z = 3 x1 + 2 x2

February 16, 2006

(Fungsi Tujuan)

Fungsi Kendala: 2 x1 + x2 ≤ 100

(Batasan Finishing)

x2 + x2 ≤ 80

(Batasan Tukang Kayu)

x1

(Batasan Permintaan ut. Praj. Mainan)

≤ 40

Batasan Non-negatif x1 , x2 ≤ 0 (Tanda Batasan) Fungsi Kendala memiliki makna bahwa nilai dari variable keputusan x1 dan x2 harus memenuhi seluruh batasan dan tanda ketaksamaannya (batasannya). Sebelum diberikan definisi tentang masalah pemrograman linear, terlabih dahulu akan didefinisikan konsep dari fungsi dan ketaksamaan linear. Defenisi 1 : Suatu fungsi f ( x1 , x2 ,
, xn ) dari x1 , x2 ,
, xn merupakan fungsi linear jika dan hanya jika untuk semua himpunan konstanta c1 , c2 ,


cn , f ( x1 , x2 ,
xn ) = c1 x1 + c2 x2 +
+ cn xn Definisi 2 : Untuk sembarang fungsi f ( x1 , x2 ,
, xn ) dan sembarang bilangan b , ketaksamaan

f ( x1 , x2 ,
, xn ) ≤ b

dan

f ( x1 , x2 ,
, xn ) ≥ b

merupakan ketaksamaan linear. Definisi 3 : Masalah Pemrograman Linear merupakan suatu masalah proses optimasi yang memenuhi: 1. Kita berusaha untuk memaksimumkan (atau meminimumkan) variable keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan disebut fungsi tujuan. 2. Nilai dari variable keputusan harus memenuhi himpunan batasan. Masing-masing batasan harus merupakan persamaan linear atau ketaksamaan linear. 3. Tanda keterbatasan berkaitan dengan masing-masing variable keputusan. Untuk sembarang variable xi , tanda keterbatasan yang menjelaskan xi harus nonnegative ( xi ≥ 0). Asumsi Proporsional dan Aditif Fakta bahwa fungsi tujuan untuk suatu masalah pemrograman linear harus merupakan sebuah fungsi linear dari variable keputusan, keadaan terputusan berimplikasi pada: 1. Kontribusi fungsi tujuan dari masing-masing variable keputusan adalah proporsional terhadap nilai dari variable keputusan. Contoh: kontribusi fungsi Abu Abdirrahman

10

PEMROGRAMAN LINEAR

February 16, 2006

tujuan dari pembuatan empat Prajurit mainan (4 x 3 = $12) adalah secara tepat empat kali kontribusi terhadap fungsi tujuan dari pembuatan satu prajurit ($3). 2. Kontribusi fungsi tujuan untuk sembarang variable independen dari nilai variable keputusan yang lain. Sebagai contoh, berapapun nilai dari x2 , pembuatan x1 akan selalu memberikan kontribusi terhadap fungsi tujuan sebesar $3. Secara analogi, bahwa tiap batasan dari pemrograman linear harus merupakan ketaksamaan atau persamaan linear berimplikasi: 1. Kontribusi masing-masing variable terhadap sisi kiri dari masing-masing batasan adalah proporsional terhadap nilai dari variable. Contoh, dibutuhk tiga kali waktu penyelesaian (2 x 3 = 6 jam finishing) untuk membuat tiga prajurit mainan. 2. Kontribusi variable terhadap sisi kanan dari masing-masing batasan adalah bergantung dari nilai variable. Implikasi pertama yang diberikan disebut asumsi proporsional. Implikasi kedua dari yang pertama merupakan nilai fungsi tujuan adalah jumlah kontribusi setiap variable secara sendiri-sendiri, dan akibat yang kedua dari daftar kontribusi kedua bahwa sisi kanan dari masing-masing batasan merupakan jumlah kontribusi dari masing-masing variable. Untuk alas an tersebut, implikasi yang kedua disebut asumsi aditif . Daerah Penyelesaian dan Solusi Optimum Dua dari beberapa konsep dasar yang berkaitan dengan masalah pemrograman linear adalah daerah penyelesaian dan solusi optimal. Kita gunakan terminology titik untuk memahami spesifikasi nilai untuk masing-msing variable keputusan. Definisi 4 : Daerah Penyelesaian (feasible Region) untuk suatu pemrograman linear adalah himpunan semua titik-titik yang memenuhi semua batasan dan tanda batasan dari pemgrograman linear. Definisi 5 : Untuk masalah maksimasi, suatu solusi optimum pada suatu pemrograman linear merupakan sautu titik dalam daerah penyelesaian dengan nilai fungsi tujuan terbesar. Dengan cara yang sama, untuk suatu masalah minimasi, suatu solute optimum merupakan titik dalam daerah penyelesaian dengan nilai fungsi tujuan terkecil. 2.2 Bentuk Umum Pemrograman Linear (PL) Sebagaimana yang telah dijelaskan pada bagian 2.1, bahwa masalah pemrograman linear memuat tiga hal, yaitu: 1) Fungsi tujuan 2) Fungsi kendala (keterbatasan sumber daya) Abu Abdirrahman

11

PEMROGRAMAN LINEAR

February 16, 2006

3) Batasan Nonnegatif Ketiga hal tersebut dapat dirumus secara matematis sebagai berikut: Fungsi Tujuan, max/min z = c1 x1 + c2 x2 + c3 x3 +
+ cn xn Fungsi Kendala,

a11 x1 + a12 x2 + a13 x3 +
+ a1 n xn ≤ (=) ≥ b1 a21 x1 + a22 x2 + a23 x3 +
+ a2 n xn ≤ (=) ≥ b2 a31 x1 + a32 x2 + a33 x3 +
+ a3n xn ≤ (=) ≥ b3      am1 x1 + am 2 x2 + am 3 x3 +
+ amn xn ≤ (=) ≥ bm

Syarat nonnegatif

(0.5)

xi ≥ 0, ∀i = 1,2,3,
, n aij , ∀i = 1,2,3,
m; j = 1,2,3,
, n

2.3 Solusi Masalah Pemrograman Linear dengan Metode Grafik Beberapa kasus dari masalah pemrograman linear hanya dapat diselesaikan secara grafik terbatas pada system persamaan linear dengan dua variable. Variable pada masalah pemrograman linear selalu disimbolkan dengan x1 dan

x2 (untuk masalah dua variable). Sebelum dijelaskan bagaimana menyelesaikan masalah pemrograman linear dengan metode ini, terlebih dahulu dijelaskan beberapa hal yang berkaitan dengan hal tersebut, yaitu: a. Arah tanda ketaksamaan/persamaan pada system persamaan linear b. Menentukan daerah penyelesaian c. Menentukan penyelesaian optimum Berikut penjelasan berkaitan dengan ketiga hal diatas:

Arah Tanda ketaksamaan/persamaan Andaikan kita ingin menggambarkan grafik dari himpunan titik yang memenuhi persamaan berikut: 2 x1 + 3 x 2 ≤ 6 (0.6) Himpunan titik yang memenuhi, 3 x 2 ≤ 6 − 2 x1 2 x 2 ≤ 2 − x1 3

(0.7)

Abu Abdirrahman

12

PEMROGRAMAN LINEAR

February 16, 2006

Karena pergerakannya ke bawah grafik x2 (lihat gambar 1), maka himpunan titik yang memenuhi persamaan (0.6) dan (0.7) berada dibawah x2 = 2 − 23 x1 . Himpunan titik-titik tersebut diindikasikan dengan bagian gambar yang berwarna merah (dibawah garis). Jika persamaannya berbentuk 2 x1 − 3 x2 = 6 , maka himpunan titik yang memenuhinya adalah tepat pada garis dari persamaan tersebut. Dan jika bentuk tanda ketaksamaannya adalah ≥ (besar dari), 2 x1 + 3 x2 ≥ 6 , maka himpunan titik yang memenuhi persamaan ini diindikasikan dengan daerah yang berwarna biru (diatas garis persamaan). Gambar 1. Grafik ketaksamaan Linear Secara sederhana: - Jika tanda ketaksamaannya adalah ≤ , maka himpunan titik yang memenuhi persamaan yang dimaksud berada di bawah garis - Jika tanda ketaksamaannya adalah ≥ , maka himpunan titik yang memnuhi persamaaan yang dimaksud berada di atas - Jika tandanya =, maka himpunan titik yang memenuhi tepat sepanjang garis dari persamaan yang dimaksud

Menentukan Daerah Penyelesaian Dengan menggunakan kasus giapeto, menentukan daerah penyelesaian suatu system persamaan linear secara grafik dijelaskan sebagai berikut: Diketahui: 2 x1 + x2 ≤ 100 (Batasan)

x1 + x2 ≤ 80 x1

≥ 40

(Tanda Keterbatasan)

(0.8)

x2 ≥ 0 Catatan: Untuk titik-titik ( x1 , x2 ) yang berada dalam daerah penyelesaian, ( x1 , x2 ) harus

memenuhi seluruh ketaksamaan (0.8). Penyelesaian: • Gambarkan 2 x1 + x2 ≤ 100 pada bidang kartesius
Untuk x1 =0, ⇒ x2 =100 (tempatkan kedua titik yang diperoleh pada

bidang kartesius Abu Abdirrahman

13

PEMROGRAMAN LINEAR

February 16, 2006


Untuk x2 =0, ⇒ x1 =50 (tempat kedua titik yang diperoleh pada

bidang kartesius)
Tarik garis penghubung dari titik x2 =100 ke titik x1 =50 •

Gambarkan x1 + x2 ≤ 80 pada bidang kartesius
Untuk x1 =0, ⇒ x2 =80 (tempatkan kedua titik yang diperoleh pada

bidang kartesius
Untuk x2 =0, ⇒ x1 =80 (tempat kedua titik yang diperoleh pada bidang kartesius)
Tarik garis penghubung dari titik x2 =80 ke titik x1 =80 •

Gambarkan x1 ≥ 40 pada bidang kartesius

•

Lihat Gambar 2 Gambar 2. Grafik Masalah Giapetto

Abu Abdirrahman

14

PEMROGRAMAN LINEAR

February 16, 2006

Menentukan Solusi Optimal Setelah menggambarkan daerah penyelesaian dari masalah giapetto, langkah selanjutnya adalah menentukan titik-titik penyelesaian optimal dari kasus tersebut, yaitu titik yang terdapat dalam daerah penyelesaian yang memberikan nilai terbesar terhadap fungsi tujuan, z = 3 x1 + 2 x2 . Untuk menentukan solusi optimum, yang harus kita lakukan adalah mengambarkan sebuah garis yang disebut dengan isoprofit, , jika merupakan permasalah maksimasi, dan garis isocost, jika merupakan permasalahan minimasi. Untuk kasus giapetto, Diketahui z = 3 x1 + 2 x 2 Ambil titik (20,0), maka z = 3(20) + 2(0) = 60. Kemudian, 3 x1 + 2 x2 = 60

3 x2 = 30 − x1 2 Sebagaimana yang telah dipelajari dalam Kalkulus, turunan pertama dari 3 3 adalah x2' = − merupakan koefisien kemiringan dari garis x2 = 30 − x1 2 2 3 x1 + 2 x2 = 60 . Dengan demikian, karena persamaan 3 x1 + 2 x2 = 60 memiliki 3 kemiringan yang sama, x2' = − , maka sekali kita menggambarkan satu garis iso 2 profit, kita dapat mendapatkan seluruh garis isoprofit dengan menggeser garis isoprofit yang pertama secara parallel. Solusi optimumnya dapat ditentukan berdasarkan titik terluar yang bersinggungan dengan garis isoprofit yang telah digambarkan. Dari gambar 2, titik terluar adalah titik G, G(20,60), sehingga solusi optimum dari kasus ini adalah: 3 x1 + 2 2 =z

3(20) + 2(60) = 180 180. 2.4 Kasus yang diselesaikan Dalam menentukan penyelesaian dari suatu system persamaan linear, ada tiga jenis dari masalah LP yang sering kita jumpai: 1. Masalah LP dengan jumlah solusi optimal yang tak terbatas 2. Masalah LP dengan tanpa penyelesaian 3. Masalah LP dengan penyelesaian tak terbatas Abu Abdirrahman

15

PEMROGRAMAN LINEAR

February 16, 2006

Berikut akan diberikan contoh yang berkaitan dengan hal tersebut, untuk penentuan solusi optimum diberikan kepada mahasiswa sebagai tugas. Kasus 1: (memiliki himpunan penyelesaian optimum yang banyak) Suatu perusahaan otomotof memproduksi dua jenis kendaraan, mobil sedan dan truck. Tiap komponen harus diproses dalam bengkel pengecatan dan bengkel pemasangan body. Jika bengkel pengecatan hanya mengecat truck, maka dalam sehari dapat menyelesaikan 40 truck. Jika bengket pengecatan hanya mengecat mobil, maka dalam sehari dapat menyelesaikan 60 mobil sedan . Jika bengkel pengerjaan body hanya membuat mobil sedan, maka dalam sehari dapat menghasilkan 50 body mobil sedan. Jika bengkel pengerjaan body hanya membuat truck, maka dalam sehari dapat menghasilkan 50 body truck. Tiap truck yang dihasilkan memberikan keuntungan sebesar $300, dan tiap mobil sedan yang dihasilkan memberikan keuntungan sebesar $200. Gunakan Pemrograman linear untuk menentukan rencana produksi perhari yang akan memaksimumkan keuntungan perusahaan. Kasus 2: (Kasus tanpa penyelesaian) Andaikan bahwa dealer dari pabrik ini membutuhkan jumlah produksi paling sedikit 30 untuk truk dan 20 untuk mobil sedan. Tentukan solusi optimum untuk pemrograman linear yang baru. Kasus 3: (Penyelesaian tak terbatas)

Abu Abdirrahman

16

PEMROGRAMAN LINEAR

Contoh Kelompok A Untuk soal nomor 1 – 4, tentukan yang mana yang termasuk, solusi optimum tunggal, banyak, tak terbatas, tanpa solusi optimum. Maks z = x1 + x 2

1.

Kendala

x1 + x 2 ≤ 4 x1 − x 2 ≥ 5 x1 , x 2 ≥ 0

Maks 2.

Kendala

z = 4 x1 + x 2 8 x1 + 2 x2 ≤ 16 5 x1 − 2 x2 ≤ 12 x1 , x 2 ≥ 0

Maks 3.

Kendala

z = − x1 + 3 x 2 x1 − x 2 ≤ 4 x1 + 2 x 2 ≥ 4 x1 , x 2 ≥ 0

Maks 4.

Kendala

z = 3 x1 + x 2 2 x1 + x 2 ≤ 6 x1 + 3 x 2 ≥ 9 x1 , x 2 ≥ 0

5. Benar atau salah: Untuk suatu LP yang penyelesaiannya akan tak terbatas, daerah penyelesaian dari LP tersebut harus tak terbatas. 6. Benar atau salah: Setiap LP dengan daerah penyelesaian tak terbatas mempunyai solusi optimum tak terbatas. 7. Tentukan semua solusi optimum masalah LP beriktu dengan menggunakan metode grafik:

Min

February 16, 2006

z = x1 − x 2

Kendala

x1 + x 2 ≤ 6 x1 − x 2 ≥ 0 x 2 − x1 ≥ 3 x1 , x 2 ≥ 0

8. Tentukan dua solusi optimum masalah LP beriktu dengan menggunakan metode grafik min z = 3 x1 + 5 x 2 Kendala

3 x1 + 2 x2 ≤ 36 3 x1 + 5 x2 ≥ 45 x1 , x 2 ≥ 0

Kelompok B 9. Manager keuangan Boris Milkem telah menyetujui mata uang prancis (frenc) dan mata uang amerika (dollar). Pada jam 12 tengah malam, dia dapat membeli francs dengan 0.25 dollar per franc dan dollar dengan 3 francs per dollar. Misalkan x1

merupakan jumlah dollar yang dibeli dan x2 merupakan jumlah francs yang dibeli. Andaikan bahwa kedua jenis transaksi membutuhkan tempat secara bersamaan, dan hanya terbatas pada jam 12.01. Boris harus mempunyai bilangan nonnegative dari francs dan dollars. a. Rumuskan masalah LP dari Boris untuk memaksimumkan jumlah dollars yang harus dimiliki setelah seluruh transaksi selesai b. Tentukan solusi optimum dari LP secara grafik dengan berikan ulasan terhadap jawaban tersebut.

Abu Abdirrahman

17