Download - Kuliah ke 2 program linear iain zck langsa
![Page 1: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/1.jpg)
![Page 2: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/2.jpg)
PROGRAM LINEAR
SISTEM PERTIDAKSAMAAN LINIER DAN GRAFIKNYAPERTEMUAN 2
![Page 3: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/3.jpg)
Sejarah Linear Program (LP)
• LP telah dikembangkan sebelum perang dunia II oleh matematikawan Rusia, A.N. Kolmogorov dan Leonid Kantorovic penerima nobel “Optimasi Perencanaan”.
• Dalam aplikasi berikutnya LP dikembangkan oleh Stigler (1945) dalam persoalan Diit (kesehatan).
• 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 Programming”. Dia seorang matematikawan di Angkatan Udara Inggris menjabat 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.
![Page 4: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/4.jpg)
DEFINISI PROGRAM LINIER (1)• Program tidak ada hubungannya dengan program komputer.• Program berarti memilih serangkaian tindakan/ perencanaan
untuk memecahkan masalah dalam membantu manajer mengambil keputusan.
• Contoh: masalah produksi, biaya, pemasaran, distribusi, dan periklanan.
• Pimpinan perusahaan harus mampu memanfaatkan sumber yang ada untuk menetapkan jenis dan jumlah barang yang harus diproduksi sehingga diperoleh keuntungan maksimal atau digunakan biaya minimal.
![Page 5: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/5.jpg)
DEFINISI PROGRAM LINIER (2)
• Program linear dan variasinya merupakan kelompok teknik analisis kuantitatif yang memakai model matematika (model simbolik). Artinya setiap penyelesaian masalah harus didahului dengan perumusan masalah ke dalam simbol-simbol matematika.
• Dalam program linier, pada umumnya masalah berasal dari dunia nyata kemudian dibentuk menjadi model simbolik yang merupakan dunia abstrak yang dibuat mendekati kenyataan. Dikatakan linear karena peubah-peubah pembentuk model dianggap linear.
![Page 6: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/6.jpg)
LANGKAH-LANGKAH (1)
1. Menentukan jenis permasalahan program linier
Jika permasalahan membicarakan keuntungan (profit), maka jenis permasalahan PL adalah maksimalisasi.
Jika permasalahan membicarakan biaya (cost), maka jenis permasalahan PL adalah minimalisasi.
Jika ada informasi tentang selisih antara hasil penjualan (sales) dan biaya dengan pokok pembicaraan profit, maka jenis permasalahannya adalah maksimalisasi.
![Page 7: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/7.jpg)
LANGKAH-LANGKAH (2)2. Mendefinisikan peubah keputusan (decision variable), yaitu
pernyataan dalam permasalahan yang hendak dicari penyelesaiannyaBeberapa hal yang harus diperhatikan adalah:– Banyaknya koefisien peubah keputusan membantu dalam
mengidentifikasikan peubah-peubah keputusan.– Jika x dimisalkan sebagai peubah keputusan berkaitan dengan kursi
yang diproduksi, maka x kursi, tetapi x = banyaknya kursi yang diproduksi.
![Page 8: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/8.jpg)
LANGKAH-LANGKAH (3)
3. Merumuskan fungsi tujuan/sasaran (objective function)– Jenis permasalahan PL dan definisi peubah
keputusan akan merumuskan fungsi tujuan.– Jika peubah keputusan terdefinisi dengan jelas,
maka fungsi tujuan akan mudah ditetapkan.
![Page 9: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/9.jpg)
LANGKAH-LANGKAH (4a)
4. Merumuskan model kendala/syarat/ batasan (constraint)Dua pendekatan umum perumusan model kendala:– Pendekatan “ruas kanan”– Pendekatan “ruas kiri”
![Page 10: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/10.jpg)
LANGKAH-LANGKAH (4b)– Pendekatan ruas “kanan”
• Ruas kanan suatu kendala tunggal dan konstan. • Maksimalisasi: ruas kanan sering menyatakan “total sumber
daya yang ada”. Prosedur pembentukannya:– Identifikasikan nilai total sumber daya dan sesuaikan tanda
pertidaksamaan dengan masing-masing total sumber daya, biasanya “”.
– Kelompokkan peubah keputusan yang terkait di sebelah kiri tanda pertidaksamaan .
– Tentukan koefisien setiap peubah keputusan. Model kendala terbentuk.
![Page 11: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/11.jpg)
LANGKAH-LANGKAH (4b)• Minimalisasi: ruas kanan sering menyatakan “minimal
sumber daya yang dibutuhkan”. Prosedur idem, kecuali tanda pertidaksamaan, biasanya “”.
– Pendekatan “ruas kiri”• Semua nilai koefisien dan peubah-peubah keputusan
disusun dalam bentuk matriks. Setelah matriks ini terbentuk, identifikasikan nilai-nilai ruas kanan dan tambahkan tanda pertidaksamaan.
![Page 12: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/12.jpg)
LANGKAH-LANGKAH (5)
5. Menetapkan syarat non negatif– Setiap peubah keputusan dari kedua jenis
permasalahan PL tidak boleh negatif (harus lebih besar atau sama dengan nol)
![Page 13: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/13.jpg)
MODEL DASAR PL• Maksimumkan atau minimumkan:
Z = c1x1 + c2x2 + ….+ cnxn (1)• Memenuhi kendala-kendala:
a11x1 + a12x2 + …. + a1nxn atau b1 (2)a21x1 + a22x2 + …. + a2nxn atau b2
.
.am1x1 + am2x2 + …. + amnxn atau bm
dan xj 0 untuk j = 1,2,…,n. (3)
![Page 14: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/14.jpg)
A. Sistem Pertidaksamaan Linear Dua Variabel
• Suatu garis dalam bidang koordinat dapat dinyatakan dengan persamaan yang berbentuk:
• Persamaan semacam ini dinamakan persamaan linear dalam variabel x dan y (dua variabel). Secara umum, dapat didefinisikan sebagai persamaan linear dengan n variabel x1, x2, . . . xn dalam bentuk berikut :
• dengan a1, a2, . . ., an, b adalah konstanta-konstanta real
bxaxa 2211
bxaxaxa nn ...2211
![Page 15: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/15.jpg)
• Jika melibatkan lebih dari satu persamaan, maka disebut dengan sistem persamaan linear. Dapat dituliskan sebagai berikut :
•
nnnnnn
nn
nn
bxaxaxa
bxaxaxabxaxaxa
...
......
2211
22222121
11212111
![Page 16: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/16.jpg)
• Untuk saat ini, pembahasan dibatasi menjadi dua variabel saja. Untuk pertidaksamaan linear, tanda “ = ” diganti dengan “ ≤ ”, “ < ”, “ ≥ ”, “ > ”. Sebagai contoh, untuk pertidaksamaan linear dua variabel dijelaskan sebagai berikut. Misalnya, kalian menggambar garis x + y = 2 dapat digambarkan sebagai berikut :
![Page 17: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/17.jpg)
Garis x + y =-2
x + y = -2
3
2
1
321
-3
0
-2
![Page 18: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/18.jpg)
Daerah x + y > -2 ini diarsir seperti pada gambar berikut :
Gambar 2.2Daerah Penyelesaian x + y ≥ -2
x + y ≥ -2
![Page 19: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/19.jpg)
Daerah x + y < -2 ini diarsir seperti pada gambar berikut :
Gambar 2.2Daerah Penyelesaian x + y ≤ -2
x + y ≤ -2
![Page 20: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/20.jpg)
Jika daerah tersebut dibatasi untuk nilai-nilai x, y ≤ 0, maka diperoleh gambar seperti berikut :
x + y > -2
HP
y ≤ 0
x ≤ 0
NEXT
![Page 21: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/21.jpg)
Kuliah ke - 3
![Page 22: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/22.jpg)
B. Model Matematika
• Sistem pertidaksamaan linear yang telah dijelaskan sebelumnya dapat diterapkan pada permasalahan sehari-hari dengan memodelkan permasalahan tersebut ke dalam model matematika.
![Page 23: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/23.jpg)
• Sebagai ilustrasi perhatikan contoh berikut. PT. Samba Lababan memproduksi ban motor dan ban sepeda. Proses pembuatan ban motor melalui tiga mesin, yaitu 2 menit pada mesin I, 8 menit pada mesin II, dan
• 10 menit pada mesin III. Adapun ban sepeda diprosesnya melalui dua mesin, yaitu 5 menit pada mesin I dan 4 menit pada mesin II. Tiap mesin ini dapat dioperasikan 800 menit per hari. Untuk memperoleh keuntungan maksimum, rencananya perusahaan ini akan mengambil keuntungan Rp40.000,00 dari setiap penjualan ban motor dan Rp30.000,00 dari setiap penjualan ban sepeda. Berdasarkan keuntungan yang ingin dicapai ini, maka pihak perusahaan merencanakan banyak ban motor dan banyak ban sepeda yang akan diproduksinya dengan merumuskan berbagai kendala sebagai berikut.
![Page 24: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/24.jpg)
• Perusahaan tersebut memisalkan banyak ban motor yang diproduksi sebagai x dan banyak ban sepeda yang diproduksi sebagai y, dengan x dan y bilangan asli. Dengan menggunakan variabel x dan y tersebut, perusahaan itu membuat rumusan kendala-kendala sebagai berikut :
(4).Persamaan0.........y 0, x,Aslibilangan y x,rsamaan(3)........Pe800.......10x 3Mesin Pada
n(2)..Persamaa800.......4y8x 2Mesin Padan(1)..Persamaa800.......5y2x 1Mesin Pada
![Page 25: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/25.jpg)
• Fungsi tujuan (objektif) yang digunakan untuk memaksimumkan keuntungan adalah f(x, y) = 40.000x + 30.000y. Dalam merumuskan masalah tersebut, PT. Samba Lababan telah membuat model matematika dari suatu masalah program linear.
![Page 26: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/26.jpg)
DEFINISI
• Model matematika adalah suatu cara sederhana untuk menerjemahkan suatu masalah ke dalam bahasa matematika dengan menggunakan persamaan, pertidaksamaan, atau fungsi.
NEXT
![Page 27: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/27.jpg)
C. Nilai Optimum Suatu Fungsi Objektif
• Bentuk umum dari fungsi tersebut adalah f(x, y) = ax + by. Suatu fungsi yang akan dioptimumkan (maksimum atau minimum). Fungsi ini disebut fungsi objektif. Untuk menentukan nilai optimum fungsi objektif ini, kalian dapat menggunakan dua metode, yaitu metode uji titik pojok dan metode garis selidik. Bentuk umum dari fungsi tersebut adalah f(x, y) = ax + by. Suatu fungsi yang akan dioptimumkan (maksimum atau minimum). Fungsi ini disebut fungsi objektif.
NEXT
![Page 28: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/28.jpg)
C. 1. Metode Uji Titik Pojok
• Untuk menentukan nilai optimum fungsi objektif dengan menggunakan metode uji titik pojok, lakukanlah langkah-langkah berikut :
• a. Gambarlah daerah penyelesaian dari kendala-kendala dalam masalah program linear tersebut.
• b. Tentukan titik-titik pojok dari daerah penyelesaian itu.
• c. Substitusikan koordinat setiap titik pojok itu kedalam fungsi objektif.
• d. Bandingkan nilai-nilai fungsi objektif tersebut. Nilai terbesar berarti menunjukkan nilai maksimum dari fungsi f(x, y), sedangkan nilai terkecil berarti menunjukkan nilai minimum dari fungsi f(x, y).
![Page 29: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/29.jpg)
Sebagai contoh maksimumkan keuntungan PT Samba Lababan dari produksi ban dengan model matematika
f(x, y) = 40.000x + 30.000y.
Gambar 2.4Daerah Penyelesaian yang memenuhi 2x + 5y ≤ 800; 8x + 4y ≤800; x ≥ 0; y ≥ 0
x ≥ 0Daerah kanan
x ≤ 800
2x + 5y ≤ 800
y ≥ 0Daerah atas
8x + 4y ≤ 800
![Page 30: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/30.jpg)
Perhatikan daerah penyelesaian dari grafik pada gambar di atas.
• Titik O adalah titik pusat koordinat. Jadi, titik O(0,0).• Titik A adalah titik potong antara garis x = 80 dan sumbu-
x.Jadi, titik A(80, 0).
• Titik B adalah titik potong antara garis x = 80 dan garis 8x + 4y = 800Substitusi x = 80 ke persamaan 8x + 4y = 800
y = 40 Jadi titik B(80, 40)
8004808 y
![Page 31: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/31.jpg)
• Titik C adalah titik potong antara garis 8x + 4y = 800 dan garis 2x + 5y = 800.Dari 8x + 4y = 800 didapat y = 200 – 2x.Substitusi nilai y ke persamaan 2x + 5y = 800
2x + 5 (200 – 2x) = 800 2x + 1000 – 10x = 800
-8x = -200 x = 25
Substitusi x = 25 ke persamaan y = 200 – 2x y = 200 – 2.25
y = 150Jadi titik C( 25, 150)
![Page 32: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/32.jpg)
• Titik D adalah titik potong antara garis 2x + 5y = 800 dan sumbu-y.Substitusikan x = 0 ke persamaan 2x + 5y = 800
2.0 + 5y = 8005y = 800 y = 160
Jadi titik D(0, 160)
![Page 33: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/33.jpg)
b. Uji titik-titik pojok ke fungsi objektif f(x,y) = 40.000x + 30.000y, sehingga fungsi objektif ini
maksimum
![Page 34: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/34.jpg)
• Dari tabel tersebut dapat diperoleh nilai maksimum fungsi objektiff(x, y) = 40.000x + 30.000y adalah f(25, 150) = 5.500.000. Jadi, PT. Samba Lababan harus memproduksi 25 ban motor dan 150 ban sepeda untuk memperoleh keuntungan maksimum.
NEXT
![Page 35: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/35.jpg)
![Page 36: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/36.jpg)
C. 2. Metode Garis Selidik
• Untuk menentukan nilai optimum fungsi objektif dengan menggunakan metode garis selidik, lakukanlah langkah-langkah berikut.
• a. Tentukan garis selidik, yaitu garis-garis yang sejajar dengan garis
ax + by = k, a ≥ 0, b ≥ 0, dan kЄ R.• b. Gambarkan garis selidik-garis selidik tersebut pada
koordinat Cartesius!• c. Untuk menentukan nilai maksimum fungsi tujuan maka
carilah garis selidik yang jaraknya terbesar terhadap titik pusat O(0, 0) dan berada pada daerah penyelesaian. Sedangkan untuk menentukan nilai minimum fungsi tujuan maka carilah garis selidik yang jaraknya terkecil terhadap titik pusat O(0, 0) dan berada pada daerah penyelesaian.
NEXT
![Page 37: Kuliah ke 2 program linear iain zck langsa](https://reader033.vdokumen.com/reader033/viewer/2022061608/587c82801a28ab93568b587f/html5/thumbnails/37.jpg)
37