Program

Linier
Kelompok 10 :
Rika Putri (4022021011)
Amanda Sapira (4022021042)
Saqinah (4022021044)
 Pendahuluan
Program linear adalah metode analisis kuantitatif yang digunakan untuk
mengoptimalkan alokasi sumber daya terbatas, seperti bahan baku, tenaga kerja,
atau kapasitas mesin, guna mencapai tujuan tertentu, seperti keuntungan
maksimal atau biaya minimal. Teknik ini sering diterapkan dalam berbagai bidang,
termasuk penugasan karyawan, distribusi, pengangkutan, dan investasi.

Sebagai metode riset operasi, program linear menyusun variabel dalam

bentuk persamaan linier, memungkinkan pengambilan keputusan secara
sistematis dan terukur. Meskipun memiliki kelebihan sebagai alat kuantitatif,
penggunaannya perlu disesuaikan dengan situasi dan masalah yang relevan.
 Sejarah Program Linier
Leonid Kantorovich menghadapi Tjalling Koopmans mengembangkan activity
kasus optimasi sumber daya di analysis, cikal bakal pemrograman linear, dan
pabrik dan mengembangkan memperkenalkan istilah "program linear" saat
analisis yang menjadi dasar bertemu George Dantzig di RAND Corporation
pemrograman linear. pada 1948.

1930 1940-an

1939 1947
Kantorovich menulis buku The Mathematical George Dantzig menciptakan
Method of Production Planning and Organization, Algoritma Simpleks, yang menjadi
menyatakan bahwa masalah ekonomi dapat dilihat alat utama dalam penerapan
sebagai upaya memaksimalkan fungsi dengan pemrograman linear.
kendala tertentu.
 Pengertian Program Linier
Program linear adalah metode matematis untuk merumuskan masalah dengan menggunakan
informasi yang tersedia dan menerjemahkannya ke dalam model matematika berbasis fungsi
linier.

Tujuan:
Mengalokasikan sumber daya terbatas, seperti uang, tenaga, atau bahan, secara optimal untuk:
- Memaksimalkan keuntungan.
- Meminimalkan biaya.

Definisi:
Pemrograman berarti perencanaan, sedangkan linier menunjukkan penggunaan fungsi-fungsi
linier. Teknik ini bertujuan menemukan solusi terbaik dalam menyusun strategi dan alokasi
sumber daya guna mencapai sasaran optimal.
 Bentuk Umum Program Linier
Bentuk umum linear programming adalah sebagai berikut:

Fungsi tujuan :
Maksimumkan atau minimumkan z = c1x1 + c2x2 + ... + cnxn
Sumber daya yang membatasi :
a11x1 + a12x2 + ... + a1nxn = /≤ / ≥ b1
a21x1 + a22x2 + … + a2nxn = /≤ / ≥ b2
…
am1x1 + am2x2 + … + amnxn = /≤ / ≥ bm
x1, x2, …, xn ≥ 0
 Cara Penyelesaian Program Linear
Dengan Metode Grafik

Ada beberapa langkah penyelesaian diantaranya sebagai berikut:

1. Buat model yang sesuai dengan masalah yang ada.

2. Gambar grafik kendala-kendalanya.
3. Tentukan daerah fisibel, yaitu daerah dalam grafik yang memenuhi semua
kendala.
4. Hitung nilai fungsi di titik-titik sudut segi-n daerah fisibel.
5. Cari titik yang menghasilkan nilai fungsi yang paling optimal
 Contoh Kasus
Seorang pengusaha Laptop membuat dua macam tipe, yaitu tipe portable touchscreen (A1) dan
tipe flip standar (A2). Kedua jenis laptop dibuat dari bahan yang sama yaitu X dan Y, dengan
komposisi yang berbeda. Setiap tipe laptop portable touchscreen dibuat dari campuran 1 unit
bahan X dan 3 bahan Y, sedangkan setiap tipe laptop flip standar dibuat dari campuran 2 unit
bahan X dan 1 unit bahan Y. Karena keterbatasan pasokan, setiap hari ia hanya memperoleh 20
unit bahan X dan 20 unit bahan Y. Untuk setiap laptop tipe portable touchscreen yang ia buat, ia
memperoleh keuntungan sebesar 300.000. Untuk setiap laptop tipe flip standar, ia memperoleh
keuntungan sebesar 200.000.

Jika diasumsikan bahwa semua laptop laku terjual, berapa laptop masing-masing tipe harus ia
buat agar keuntungan yang didapatkan maksimum?
 Penyelesaian
Bahan Laptop tipe portabletouchscreen (A1) Laptop tipe flip standar (A2) Pasokan Maksimum
X 1 2 20
Y 3 1 20
Untung 300.000 200.000

Maksimumkan, f(x1, x2) = 300.000 x1 + 200.000 x2 è 3 x1 + 2 x2 (dalam Titik-titik sudut daerah fisibel dapat melihat
ratusan ribu) keuntungan maksimum yang ingin dicapai
pengusaha:
Kendala :
x1 + 2 x2 ≤ 20 Titik-titik sudut Nilai fungsi , f(x 1, x2) = 3 x1 + 2 x2
3 x1 + x2 ≤ 20 daerah fisibel
3 x1 + 2 x2 (dalam ratusan ribu)
x1, x2 ≥ 0 O (0,0) 3(0) + 2(0) = 0
Penggambaran kendala x1 + 2 x2 ≤ 20, 3 x1 + x2 ≤ 20 dan x1, x2 ≥ 0 A (0,10) 3(0) + 2 (10) = 20
E (4,8) 3(4) + 2(8) = 12 + 16 = 28
Perpotongan bidang yang memenuhi semua kendala disebut daerah fisibel. D (20/3,0) 3(20/3) + 2(0) = 20
Daerah fisibel dalam kasus ini disebut daerah fisibel AEDO (bagian yang
diarsir pada bagian perpotongan bidang AOB dan bidang COD).
Koordinat E dapat dicari dari perpotongan x1 + 2 x2 ≤ 20 dan 3 x1 + x2 ≤
20 sehingga diperoleh E(4,8).
 Cara Penyelesaian Program Linear Dengan Metode Aljabar

a. Kasus Maksimisasi

Tujuan: Mencari nilai objektif maksimum.

Fungsi Pembatas:
Langkah-langkah: 4X1 + 2X2 ≤ 60 (P-Bahan)
Ubah ketidaksamaan fungsi pembatas menjadi 2X1 + 4X2 ≤ 48 (Penjahitan)
persamaan dengan menambah slack variable (S ≥ 0). X1 , X2 ≥ 0
Ubah fungsi tujuan dengan menambah slack variable Langkah Penyelesaian:
bernilai nol. Tambahkan slack variable:
Substitusi fungsi pembatas ke dalam fungsi tujuan. 4X1+2X2+S1=60
2X1+4X2+S2=48
Contoh: Substitusi ke fungsi tujuan:
Perusahaan konveksi "Maju" memproduksi baju (X₁) dan Z=8X1+6X2
celana (X₂).
Lanjutkan dengan mencari solusi optimal melalui eliminasi
Fungsi Tujuan: Maksimumkan Z=8X1+6X2 ​ (dalam Rp atau substitusi.
1.000).
b. Kasus Minimasi

Tujuan: Mencari nilai objektif minimum. Fungsi Pembatas:

3M1 + M2 ≥ 27 (Nutrisi A)
Langkah-langkah: M1 + M2 ≥ 21 (Nutrisi B)
Ubah ketidaksamaan fungsi pembatas menjadi M1 + 2M2 ≥ 30 (Nutrisi C)
persamaan dengan menambah surplus variable M1 , M2 ≥ 0
(S).
Ubah fungsi tujuan dengan menambah surplus Langkah Penyelesaian:
variable bernilai nol. Tambahkan slack variable:
Substitusi fungsi pembatas ke dalam fungsi 3M1 + M2 − S1 = 27
tujuan. M1 + M2 − S2 = 21
M1 + 2M2 − S3 = 30
Contoh:
Petani modern harus memenuhi nutrisi untuk sapi Substitusi ke fungsi tujuan:
dengan dua jenis makanan M1​ dan M2 Z = 40M1 + 20M2.

Fungsi Tujuan: Minimisasi Z= 40M1 + 20M2 ​. Solusi optimal diperoleh dengan menyusun tabel
eliminasi atau metode grafik.
c. Kasus Khusus

Solusi Optimum Ganda: Fungsi Tujuan: Z=5X1+3X2

Terdapat lebih dari satu solusi optimal.
Fungsi Pembatas:
Fungsi Tujuan: Z=4X1+4X2 4X1+2X2≤8
X1≥3
Fungsi Pembatas: X2≥7
X1+2X2≤10 X1,X2≥0
X1+6X2≤36
X1≤4 Gunakan metode grafik atau simpleks untuk
X1,X2≥0 analisis mendalam.

Tidak Memiliki Solusi Layak:

Tidak ada solusi yang memenuhi semua fungsi
pembatas.
 Cara Penyelesaian Program Linear
Dengan Metode Simplex
Metode simpleks digunakan untuk menyelesaikan 4. Langkah Iterasi Simpleks:
persoalan program linear yang kompleks, dengan - Pilih Kolom Kunci: Pilih kolom dengan nilai negatif
mengubah ketidaksamaan menjadi persamaan terbesar pada fungsi tujuan.
menggunakan variabel tambahan. - Pilih Baris Kunci: Hitung rasio NK / Kolom Kunci dan
pilih nilai positif terkecil.
Langkah-langkah Penyelesaian: - Tentukan Angka Kunci: Nilai pada perpotongan kolom
1. Formulasi Model Program Linear (PL): dan baris kunci.
- Tentukan fungsi tujuan (maksimum/minimum).
- Tentukan fungsi pembatas. 5. Perbarui Tabel:
- Ubah Baris Kunci: Bagi nilai baris kunci dengan angka
2. Ubah ke Model Simpleks: kunci.
- Tambahkan slack variable, surplus variable, dan/atau - Ubah Baris Lain: Gunakan operasi baris untuk
artificial variable. memperbarui nilai tabel.
- Ubah fungsi tujuan ke bentuk eksplisit.
6. Lanjutkan Iterasi:
3. Formulasikan Tabel Simpleks: - Ulangi langkah 3–5 hingga tidak ada nilai negatif di
- Susun fungsi tujuan dan pembatas ke dalam tabel. fungsi tujuan.
 Ciri – Ciri Program Liner
Tujuan Utama:
Memaksimalkan keuntungan atau meminimalkan biaya dengan keterbatasan sumber daya.

Ciri Khas Linear Programming:

1. Penyelesaian masalah bertujuan untuk maksimisasi atau minimisasi.
2. Kendala membatasi tingkat pencapaian tujuan.
3. Terdapat beberapa alternatif penyelesaian.
4. Hubungan matematis bersifat linear.

Asumsi Dasar Linear Programming:

1. Certainty (Kepastian): Fungsi tujuan dan kendala diketahui pasti dan tetap selama analisis.
2. Proportionality (Proporsionalitas): Hubungan variabel dalam fungsi tujuan dan kendala bersifat
proporsional.
3. Additivity (Penjumlahan): Aktivitas total adalah jumlah aktivitas individu.
4. Divisibility (Dapat Dibagi): Solusi dapat berupa bilangan pecahan atau bukan integer.
5. Non-Negative Variable: Nilai variabel tidak boleh negatif.
Thank You