LEMBAR PENGESAHAN

Program Linier

Koordinator : Sisca Sri Dewi Saragih, [Link]., [Link].

Dosen Pengampu : Sisca Sri Dewi Saragih, [Link]., [Link].
Tim Pengajar :-

Kisaran, 17 September 2025

Penyusun Menyetujui
Kepala Program Studi Prodi Pendidikan
Matematika

Sisca Sri Dewi Saragih, [Link]., [Link]. Mustika Fitri Larasati Sibuea, [Link]
NIDN. 0128079601 NIDN. 0114059001

Mengetahui
Dekan Fakultas Keguruan dan Ilmu Pendidikan

DR. Neni Mulyani, [Link]

NIDN. 0111097201

1
 MODUL MATA KULIAH
PROGRAM STUDI PENDIDIKAN MATEMATIKA
UNIVERSITAS ROYAL

Program Linier
PENDAHULUAN
Perkembangan ilmu pengetahuan dan teknologi menuntut adanya metode analisis
yang mampu membantu pengambilan keputusan secara tepat, efisien, dan optimal. Salah
satu cabang ilmu matematika terapan yang berperan besar dalam hal ini adalah Program
Linier (Linear Programming). Program Linier merupakan metode matematis yang
digunakan untuk menentukan solusi terbaik dari suatu permasalahan optimasi dengan
memperhatikan keterbatasan sumber daya yang ada.
Konsep dasar Program Linier pertama kali diperkenalkan pada awal abad ke-20
dan berkembang pesat sejak diperkenalkannya metode simpleks oleh George B. Dantzig
pada tahun 1947. Sejak saat itu, program linier telah menjadi salah satu alat utama dalam
operations research dan banyak diaplikasikan dalam berbagai bidang, mulai dari
ekonomi, bisnis, industri, transportasi, pertanian, hingga ilmu komputer. Keunggulan
utama program linier adalah kemampuannya menyelesaikan masalah kompleks secara
sistematis dengan mempertimbangkan berbagai kendala yang saling berkaitan.
Buku ini disusun untuk memberikan pemahaman yang komprehensif mengenai
teori, metode, dan aplikasi program linier. Dimulai dari konsep dasar, pembaca akan
diajak memahami cara merumuskan masalah optimasi ke dalam model matematika,
menyelesaikannya dengan metode grafik maupun metode simpleks, hingga menganalisis
hasil dengan konsep dualitas dan sensitivitas. Selain itu, buku ini juga dilengkapi dengan
penerapan program linier dalam kasus nyata serta pemanfaatan perangkat lunak
pendukung, seperti Excel Solver, LINDO, dan Python.
Dengan penyusunan yang sistematis, buku ini diharapkan dapat menjadi referensi
utama bagi mahasiswa, dosen, peneliti, maupun praktisi yang ingin memahami dan

2
mengaplikasikan Program Linier untuk memecahkan berbagai permasalahan optimasi
dalam kehidupan nyata.

A. Dekripsi Materi
Mata kuliah Program Linier membahas konsep dasar optimasi dengan fungsi tujuan dan
kendala linier, serta metode penyelesaiannya. Materi meliputi perumusan model
matematika dari masalah nyata, penyelesaian dengan metode grafik dan metode
simpleks, konsep dualitas, analisis sensitivitas, serta penerapan perangkat lunak
pendukung. Mata kuliah ini bertujuan membekali mahasiswa dengan kemampuan
menganalisis dan menyelesaikan masalah optimasi yang berkaitan dengan keterbatasan
sumber daya di berbagai bidang seperti industri, ekonomi, manajemen, dan sains.

B. Tujuan Belajar
1. Memahami konsep dasar optimasi dengan fungsi tujuan dan kendala linier.
2. Mampu merumuskan model matematika dari permasalahan nyata ke dalam bentuk
program linier.
3. Menguasai metode penyelesaian program linier, baik dengan metode grafik maupun
metode simpleks.
4. Menganalisis hasil optimasi menggunakan konsep dualitas dan analisis sensitivitas.
5. Menggunakan perangkat lunak pendukung (seperti Excel Solver, LINDO, atau
Python) untuk menyelesaikan masalah program linier.
6. Menerapkan program linier dalam kasus nyata di bidang industri, manajemen,
logistik, pertanian, dan sains.
7. Mengembangkan kemampuan berpikir analitis dan kritis dalam pengambilan
keputusan berbasis data.
D. Petunjuk Belajar
1. Bacalah pendahuluan modul ini sehingga benar-benar memahami isi, kegunaan,
kompetensi/kemampuan yang akan dicapai, dan cara mempelajari materi ini
2. Apabila mengalami kesulitan memahami konsep yang harus dipahami dari modul ini,
cobalah berdiskusi dan bertanya dengan teman atau kelompok belajar yang dianggap
tahu

3
 KEGIATAN BELAJAR
1

Konsep Program Linier

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan menguasai konsep Program Linier

A. Pengertian Program Linier

Program linier adalah salah satu cabang dari riset operasi atau matematika terapan
yang mempelajari cara mengoptimalkan suatu fungsi tujuan (objective function)
yang berbentuk linier, dengan memperhatikan kendala-kendala (constraints) yang juga
berbentuk linier.
Optimalisasi di sini dapat berupa:
• Maksimisasi, misalnya keuntungan, hasil produksi, atau efisiensi.
• Minimisasi, misalnya biaya, kerugian, atau waktu.
Keputusan yang optimal nantinya akan ditetntukan melalui model-model perhitungan
yang ada di dalamnya dengan beberapa pendekatan dengan menggunakan metode grafik
dan metode simpleks.

4
Tahap-tahap pemodelan :
1. Definisi Masalah:
Deskripsi tentang sasaran atau tujuan sistem. Maksudnya, adalah menggambarkan
apa yang menjadi tujuan dari sistem tersebut. Identifikasi keputusan dari sistem. Batasan
dan syarat sistem. Maksudnya apa yang menjadi kendala dalam sistem tersebut.
2. Pengembangan Model.
Tergantung dari definisi masalah. Entah matematis atau simulasi. Matematis
memiliki input dan output yang pasti sedangkan simulasi memiliki input dan output yang
tidak pasti.
3. Pemecahan/Solusi Model.
Biasanya disebut Linear Programming (Program Linier), dengan pemecahan yaitu
Optimalisasi dan Analisis Sensitivitas atau Post Optimality.
4. Validasi Model.
Membandingkan data dan hasil yang baru didapat dengan data dan hasil yang
sebelumnya, apa yang menjadi perbedaan dan apa artinya. Kemudian validasi model
yang baru itu berlaku umum.
5. Implementasikan.
Tahap-tahap pemodelan yang telah dilakukan dari awal sampai akhir,
diimplementasikan kedalam kehidupan yang nyata dalam hal ini yang menyangkut
bidang ekonomi. Tujuannya, untuk melihat berhasil atau tidaknya pemodelan yang
dibuat secara teori ke dalam prakteknya.

B. Komponen Utama Program Linier

Sebuah model program linier umumnya terdiri dari:
1. Variabel Keputusan (Decision Variables)→ Melambangkan besaran yang ingin
dicari nilainya, misalnya jumlah barang yang diproduksi.
2. Fungsi Tujuan (Objective Function)→ Persamaan linier yang menunjukkan apa
yang ingin dioptimalkan, misalnya:
𝑍 = 5𝑥1 + 4𝑥2
dengan 𝑍 = keuntungan total.
3. Kendala (Constraints)→ Persamaan atau pertidaksamaan linier yang
menggambarkan batasan sumber daya, misalnya:
2𝑥1 + 𝑥2 ≤ 100

5
 dengan 100 adalah kapasitas bahan baku.
4. Kondisi Non-negatif (Non-Negativity Constraints)→ Nilai variabel tidak
boleh negatif:
𝑥1 ≥ 0, 𝑥2 ≥ 0

C. Ciri-Ciri Program Linier

• Fungsi tujuan dan kendala bersifat linier.
• Variabel keputusan bernilai kontinu (real) dan non-negatif.
• Memiliki ruang solusi yang disebut daerah layak (feasible region).
• Solusi optimal berada di salah satu titik pojok (corner point) dari daerah layak.

D. Contoh Sederhana
Sebuah perusahaan ingin menentukan jumlah produksi dua jenis produk: 𝑥1 dan 𝑥2 .
• Keuntungan produk 𝑥1 = Rp 40/unit, dan produk 𝑥2 = Rp 30/unit.
• Waktu mesin tersedia = 120 jam.
• Produk 𝑥1 butuh 2 jam, produk 𝑥2 butuh 1 jam.
Formulasi Program Linier:
• Fungsi tujuan:
Maksimumkan 𝑍 = 40𝑥1 + 30𝑥2
• Kendala:
2𝑥1 + 𝑥2 ≤ 120
• Non-negatif:
𝑥1 , 𝑥2 ≥ 0

E. Manfaat Program Linier

• Menyelesaikan persoalan optimasi nyata seperti produksi, transportasi, distribusi,
dan perencanaan keuangan.
• Membantu pengambilan keputusan berbasis data dan keterbatasan sumber daya.
• Digunakan luas di bidang ekonomi, manajemen, industri, teknik, dan pertanian.

DAFTAR PUSTAKA
1. Rindengan, Altien J, Langi, Yohanes A.R,(2018), Program Linier,CV. Patra Media
Grafindo: Bandung

6
 KEGIATAN BELAJAR
2

Formulasi Model Program Linier

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Memformulasikan Model Program Linier.
2. Mampu membedakan Solusi maksimum, titik balik dan sebagainya.

A. Formulasi Model PL
Membuat model program linier harus digambarkan sesuai dengan data yang telah
diterima sesuai dengan keadaan faktualnya.
1. Identifikasi Tujuan (Objective)
• Tentukan apakah masalah yang dihadapi bertujuan untuk maksimisasi (misalnya
keuntungan, hasil produksi) atau minimisasi (misalnya biaya, waktu, kerugian).
• Hasil identifikasi ini akan menjadi fungsi tujuan (objective function).
Contoh:
Perusahaan ingin memaksimalkan keuntungan dari produksi dua jenis barang
2. Tentukan Variabel Keputusan (Decision Variables)
• Nyatakan keputusan yang harus dibuat dalam bentuk variabel.
• Variabel biasanya menyatakan jumlah unit, alokasi sumber daya, atau besaran
lain yang akan dicari nilainya.
Contoh:
𝑥1 = jumlah produk A yang diproduksi.
𝑥2 =jumlah produk B yang diproduksi.
3. Bentuk Fungsi Tujuan (Objective Function)
• Rumuskan fungsi linier berdasarkan variabel keputusan.
• Koefisien variabel mencerminkan kontribusi setiap variabel terhadap tujuan.
Contoh:
Jika keuntungan produk A = Rp40/unit dan produk B = Rp30/unit, maka:
Maksimumkan 𝑍 = 40𝑥1 + 30𝑥2

7
4. Tentukan Kendala (Constraints)
• Identifikasi batasan nyata yang harus dipenuhi, seperti keterbatasan bahan baku,
tenaga kerja, modal, atau waktu.
• Nyatakan batasan tersebut dalam bentuk persamaan atau pertidaksamaan linier.
Contoh:
• Waktu mesin maksimal 120 jam.
• Produk A butuh 2 jam/unit, produk B butuh 1 jam/unit.
2𝑥1 + 𝑥2 ≤ 120
5. Tambahkan Kendala Non-Negatif
Karena variabel keputusan biasanya berupa jumlah barang, waktu, atau sumber
daya, nilainya tidak boleh negatif.
Contoh:
𝑥1 ≥ 0, 𝑥2 ≥ 0
6. Model Program Linier Lengkap
Gabungkan semua elemen ke dalam bentuk model PL standar:
Maksimumkan 𝑍 = 40𝑥1 + 30𝑥2
dengan syarat:
2𝑥1 + 𝑥2 ≤ 120
𝑥1 , 𝑥2 ≥ 0
Ringkasan Proses Formulasi
1. Pahami masalah nyata → apa yang ingin dioptimalkan.
2. Tentukan variabel keputusan.
3. Susun fungsi tujuan.
4. Rumuskan semua kendala.
5. Tambahkan syarat non-negatif.
6. Tulis model matematika PL lengkap.

Contoh 2.1 (Masalah Maksimisasi)

Suatu perusahaan makanan ingin menghasilkan roti dalam tiga bentuk yang berbeda-
beda yaitu roti A, B, dan C. Bahan baku tepung terigu yang tersedia 300 kg dan waktu
kerja buruh yang tersedia adalah 200 jam kerja. Jika untuk membuat 1 buah roti A
diperlukan 3 jam buruh dan 0.4 kg tepung, untuk membuat 1 buah roti B diperlukan 5
jam buruh dan 0.8 kg tepung, serta 1 buah roti C diperlukan 4 jam buruh dan 0.6 kg

8
tepung. Dan jika harga yang ditawarkan per buah roti A, B dan C adalah berturut-turut
2000, 5000, dan 3500, maka formulasikan masalah ini sebagai model menghitung
pendapatan bagi perusahaan.
Penyelesaian:
1. Variabel Keputusan.
Masalah ini berisi tiga variable keputusan yang menunjukkan jumlah setiap bentuk
roti. 𝑥1 = Jumlah roti A
𝑥2 = Jumlah roti B
𝑥3 = Jumlah roti C
2. Fungsi Tujuan.
Tujuan perusahaan makanan adalah memaksimumkan pendapatan dari produksi roti
yang ditunjukkan sebagai :
𝑀𝑎𝑥 𝑍 = 2000𝑥1 + 5000𝑥2 + 3500𝑥3
3. Kendala/Batasan Model.
Bahan baku tepung terigu dan jam kerja buruh merupakan kendala.
• Kendala bahan baku tepung terigu:
0,4𝑥1 + 0,8𝑥2 + 0,6 𝑥3 ≤ 300
• Kendala jam kerja buruh:
3𝑥1 + 5𝑥2 + 4𝑥3 ≤ 200
• Kendala non negatif:
𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Untuk masalah-masalah besar seperti ini dapat dibuat tabel masalah:

Bentuk/Model program linear untuk masalah ini adalah:

𝑀𝑎𝑥 𝑍 = 2000𝑥1 + 5000𝑥2 + 3500𝑥3
Dengan Kendala, (subject to [s.t])
0,4𝑥1 + 0,8𝑥2 + 0,6𝑥3 ≤ 300
3𝑥1 + 5𝑥2 + 4𝑥3 ≤ 200
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

9
Contoh 2.2 (Masalah Minimisasi)
Jika seseorang ingin memenuhi kebutuhan minimum zat makanan perharinya dengan
mengkonsumsi beberapa jenis makanan dengan data (tabel masalah) sebagai berikut:

Formulasikan masalah ini untuk menentukan kombinasi konsumsi makanan yang

memenuhi kebutuhan minimum perhari dengan biaya terendah.
Penyelesaian:
1. Variabel keputusan
𝑥1 = jumlah sayur yang dikonsumsi
𝑥2 = jumlah daging yang dikonsumsi
𝑥3 = jumlah susu yang dikonsumsi
2. Tujuan
Menentukan kombinasi konsumsi makanan yang memenuhi kebutuhan minimum
per hari dengan biaya terendah.
Mis. fungsi biaya = Z
𝑀𝑖𝑛 𝑍 = 5𝑥1 + 8𝑥2 + 6𝑥3
3. Bentuk kendala
a. Kalsium 5𝑥1 + 𝑥2 ≥8
b. Protein 2𝑥1 + 2𝑥2 + 𝑥3 ≥ 10
c. Vitamin 𝑥1 + 5𝑥2 + 4𝑥3 ≥ 22
Nonegatif : 𝑥1 , 𝑥2 , 𝑥3 ≥ 0
Secara lengkap masalah tersebut :
𝑀𝑖𝑛 𝑍 = 5𝑥1 + 8𝑥2 + 6𝑥3
𝑠. 𝑡 5𝑥1 + 𝑥2 ≥8
2𝑥1 + 2𝑥2 + 𝑥3 ≥ 10
𝑥1 + 5𝑥2 + 4𝑥3 ≥ 22
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

10
B. Defenisi-Defenisi Pada PL
1. Himpunan Konveks
Himpunan 𝑆 ⊆ ℝ𝑛 disebut konveks jika untuk setiap dua titik 𝑥, 𝑦 ∈ 𝑆, semua
titik di antara keduanya juga termasuk dalam himpunan tersebut.
Artinya, untuk setiap 𝜆 dengan 0 ≤ 𝜆 ≤ 1:
𝜆𝑥 + (1 − 𝜆)𝑦 ∈ 𝑆
Sifat-sifat himpunan konveks:
1. Daerah solusi program linier selalu merupakan himpunan konveks.
2. Irisan dari himpunan konveks juga merupakan himpunan konveks.
3. Himpunan solusi yang dibatasi pertidaksamaan linier membentuk daerah
konveks.

2. Himpunan Layak (Feasible Set)

Himpunan layak adalah himpunan semua solusi yang memenuhi seluruh
kendala dalam masalah program linier. Himpunan layak biasanya berupa daerah
konveks di dalam ruang solusi. Jika himpunan layak kosong, maka masalah
program linier tidak memiliki solusi.

3. Titik Ekstrim (Extreme Point):

Titik ekstrim adalah titik pojok dari daerah layak (feasible region). Dalam
konteks grafis, titik ekstrim muncul dari perpotongan garis-garis kendala.
Teorema penting: Jika masalah program linier memiliki solusi optimal, maka
paling sedikit satu titik optimal adalah titik ekstrim dari himpunan layak.
4. Titik Solusi Optimal (Optimal Solution):
Titik dalam himpunan layak yang menghasilkan nilai fungsi tujuan maksimum
atau minimum.
Bisa berupa:
• Solusi tunggal → hanya satu titik yang memberikan nilai optimal.
• Banyak solusi (multiple optimal solutions) → lebih dari satu titik ekstrim
menghasilkan nilai fungsi tujuan yang sama.
• Tidak terbatas (unbounded) → fungsi tujuan bisa bertambah terus tanpa
batas.

11
PUSTAKA
1. Luenberger, D.G. and Y. Ye. 2016. Linear and Nonlinear Programming, 4ed.
Springer Int. Pub. Switzerland.
2. Taha, H.A. 2007. Operations Research: An Introduction, 8ed. Prentice Hall, New
Jersey.
3. Winston, W.L. 2008. Operations Research. Applications and Algorithms, 4ed .
Brooks/Cole, New York.

SOAL LATIHAN:
1. Sebuah perusahaan memproduksi 2 produk melalui dua proses perakitan. Proses
perakitan 1 memiliki kapasitas 100 jam dan perakitan 2 memiliki kapasitas 42 jam.
Pada proses perakitan 1, tiap produk memerlukan 10 jam, sedangkan pada proses
perakitan 2, produk 1 membutuhkan 7 jam dan produk 2 mebutuhkan 3 jam. Laba per
unit untuk produk 1 adalah $6 dan produk 2 adalah $4. Formulasikan model linier
untuk masalah ini.
2. Suatu perusahaan furnitur memproduksi kursi dan meja dari 2 sumber daya (tenaga
kerja dan kayu). Tiap hari tersedia 80 jam tenaga kerja dan 36 pon kayu untuk

12
 digunakan. Permintaan kursi tiap hari hanya 6 unit. Untuk memproduksi 1 unit kursi
dibutuhkan 8 jam kerja dan 2 pon kayu, sedangkan 1 unit meja dibutuhkan 10 jam
kerja dan 6 pon kayu. Laba per unit kursi $400 dan meja $100. perusahaan ingin
menentukan jumlah kursi dan meja yang harus diproduksi untuk memaksimalkan
laba. Formulasikan model linear untuk masalah ini.
3. Seorang manager investasi mempertimbangkan investasinya dalam portofolio yang
mencakup saham dan obligasi. Ia memiliki uang sebesar $ 720.000,-. Ia tidak ingin
saham dalam portofolionya mencakup lebih dari 65 %. Tingkat pengembalian
tahunan dari saham adalah 18% dan dari obligasi adalah 6%. Ia memperkirakan
bahwa kerugian tertinggi dari saham adalah 22% dan obligasi adalah 5%. Untuk
mengurangi resiko, ia membatasi kemungkinan potensi ruginya sebesar $ 100.000,-
.Formulasikan masalah ini sebagai model program linear untuk mencari kombinasi
portofolio optimal yang memberikan keuntungan maksimum.

13
 KEGIATAN BELAJAR
3

Model Program Linier Metode Grafik

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier Metode Grafik.

A. Penyelesaian Model PL
Langkah-langkah menentukan Solusi model program linier dengan metode grafik:
1. Tentukan Fungsi Tujuan dan Kendala
Tuliskan model program linier dalam bentuk:
• Fungsi tujuan (maksimisasi/minimisasi).
• Kendala berupa pertidaksamaan linier.
• Kendala non-negatif
2. Gambarkan Kendala pada Bidang Kartesius
Ubah setiap kendala pertidaksamaan menjadi persamaan. Tentukan daerah
perpotongannya, yang merupakan daerah solusi fisibel model dan titik-titik
perpotongan kendala yang berada pada daerah solusi fisibel, sebagai calon titik
solusi optimal.
3. Tentukan Daerah Layak (Feasible Region)
Gunakan garis selidik yang merupakan persamaan fungsi tujuannya dengan
mengambil sembarang nilai Z, untuk menentukan titik solusi optimalnya dengan
mengeser garis selidik tersebut sampai diperoleh titik yang paling
maksimal/minimal. Daerah layak adalah irisan semua daerah yang memenuhi
kendala. Biasanya berupa daerah segi banyak (poligon) konveks.
Contoh 3.1
Tentukan solusi optimal masalah program linier berikut:
𝑀𝑎𝑥 𝑍 = 300𝑥 + 500𝑦
s.t 2 𝑥 + 5 𝑦 ≤ 800
2𝑥 + 𝑦 ≤ 400
𝑥, 𝑦 ≥ 0

14
Penyelesaian:
Langkah 1 : Gambarkan Garis Batasan Persamaan Kendala

Langkah 2: Menentukan daerah solusi Fisibel dan titik calon solusi optimal
Daerah solusi fisibel ditentukan dari penentuan daerah yang memenuhi ketiga
kondisi pertidaksamaan kendala.

Titik-titik A, B, C sebagai perpotongan tiap pasangan persamaan kendala Adalah

calon calon titik solusi optimal.
Langkah 3: Menentukan solusi optimal dengan menggunakan garis selidik.
Jika dipilih nilai 𝑍 = 60000, maka perpotongan persamaan garis selidiknya yaitu
pada
300 𝑥 + 500 𝑦 = 60000 sumbu 𝑥 di titik (200,0) dan sumbu 𝑦 di titik (0,120).
Garis selidik ini digeser sampai pada titik terakhir (paling maksimal) yang masih
berpotongan dengan daerah solusi fisibel yaitu

Titik solusi optimal Adalah titik 𝐵 yang merupakan perpotongan garis 2 𝑥 + 5 𝑦 ≤

800 dan 2 𝑥 + 𝑦 ≤ 400, sehingga bisa dicari nilai 𝑥 dan 𝑦 nya dengan eliminasi.
2 𝑥 + 5 𝑦 = 800
2𝑥+ 𝑦 = 400

15
 4𝑦 = 400
𝑦 = 100
Nilai 𝑥 dicari dengan mensubtitusi nilai 𝑦 ke salah satu persamaan.
2𝑥 + 𝑦 = 400 ⇒ 2𝑥 + 100 = 400 ⟹ 𝑥 = 150

Sehingga nilai 𝑍 maksimum 𝑍 = 300𝑥 + 500𝑦 = 300.150 + 500.100 = 95000

Contoh 3.2
Tentukan solusi optimal masalah program Linier berikut:
𝑀𝑖𝑛 𝑍 = 𝑥1 + 3𝑥2
s.t 2𝑥1 + 3𝑥2 ≥ 30
𝑥1 + 4𝑥2 ≥ 20
5𝑥1 + 2𝑥2 ≥ 40
𝑥1 , 𝑥2 ≥ 0

Penyelesaian:

MIsalkan 𝑍 = 12, maka garis selidiknya Adalah 𝑥1 + 3𝑥2 = 12 dengan titik

potong pada sumbu 𝑥1 adalah (12,0) dan sumbu 𝑥2 adalah (0,4). Titik solusi
optimal Adalah titik 𝑃 yang merupakan perpotongan garis 2𝑥1 + 3𝑥2 = 30 dan
𝑥1 + 4𝑥2 ≥ 20, sehingga bisa dicari nilai 𝑥1 dan 𝑥2 -nya dengan eliminasi.
2𝑥1 + 3𝑥2 ≥ 30 (× 1) 2𝑥1 + 3𝑥2 = 30
𝑥1 + 4𝑥2 ≥ 20 (× 2) 2𝑥1 + 8𝑥2 = 40
−5𝑥2 = −10
𝑥2 = 2
Nilai 𝑥2 dicari dengan mensubstitusi nilai 𝑥1 ke salah satu persamaan.
𝑥1 + 4𝑥2 = 20
𝑥1 + 4(2) = 20

16
 𝑥1 = 20 − 8
𝑥1 = 12
Dan nilai 𝑍 minimum adalah : 𝑍 = 𝑥1 + 3𝑥2 = 12 + 3(2) = 18

Contoh 3.3
PT Auto Sound Stream memproduksi dua jenis subwofer, yaitu picasso dan tarantula.
Untuk dapat meraih konsumen berpenghasilan tinggi. Perusahaan ini memutuskan untuk
melakukan promosi dalam dua macam acara TV, yaitu pada acara hiburan dan acara olah
raga. Promosi pada acara hiburan akan disaksikan oleh 8 juta pemirsa wanita dan 4juta
pemirsa pria. Promosi pada acara olah raga akan disaksikan oleh 4juta pemirsa wanita
dan 12juta pemirsa pria. Biaya promosi pada acara hiburan adalah 4juta rupiah/menit,
sedangkan pada acara olah raga biayanya adalah 8juta/menit. Jika perusahaan
menginginkan promosinya disaksikan sedikitnya oleh 32juta pemirsa wanita dan
sedikitnya oleh 24juta pemirsa pria, bagaimanakah strategi promosi itu sebaiknya?
Penyelesaian:
Tabel masalahnya Adalah:
Acara Hiburan Acara Disaksikan
Olahraga
Wanita 8 4 32

Pria 4 12 24

biaya 4 8

Variabel Keputusan:
𝑥1 = lamanya promosi dalam acara hiburan.
𝑥2 = lamanya promosi dalam acara olah raga.

Formulasi persoalan:
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 8𝑥2
s.t 8𝑥1 + 4𝑥2 ≥ 32
4𝑥1 + 12𝑥2 ≥ 24
𝑥1 , 𝑥2 ≥ 0

17
Grafiknya adalah

Misalkan 𝑍 = 8, maka garis selidiknya Adalah 4𝑥1 + 8𝑥2 = 8 dengan titik potong pada
sumbu 𝑥1 adalah (2,0) dan sumbu 𝑥2 adalah (0,1).
Titik Solusi optimal Adalah titik yang merupakan perpotongan garis 8𝑥1 + 4𝑥2 = 32
dan 4𝑥1 + 12𝑥2 = 24 , sehingga bisa dicari nilai 𝑥1 dan 𝑥2 dengan eliminasi
8𝑥1 + 4𝑥2 = 32 (× 3) 24𝑥1 + 12𝑥2 = 96
4𝑥1 + 12𝑥2 = 24 (× 1) 4𝑥1 + 12𝑥2 = 24
20𝑥1 = 72
𝑥1 = 3,6
Nilai 𝑥2 dicari dengan mensubstitusi nilai 𝑥1 ke salah satu persamaan,
8𝑥1 + 4𝑥2 = 32
8(3,6) + 4𝑥2 = 32
𝑥2 = 20,8

18
 KEGIATAN BELAJAR
4

Model Program Linier Kasus Khusus

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier Solusi Khusus

A. Solusi Optimum Berganda

Terjadi karena kemiringan persamaan tujuan sama dengan kemiringan salah satu
persamaan kendala. Misalnya ada 2 persamaan : 𝑎𝑥 + 𝑏𝑦 = 𝑐 dan 𝑑𝑥 + 𝑒𝑦 = 𝑓
mempunyai kemiripan yang sama jika 𝑎/𝑑 = 𝑏/𝑒 atau 𝑎/𝑏 = 𝑑/𝑒. Solusinya berupa
kumpulan titik-titik yang berbentuk ruas garis solusi.
Contoh 4.1
Tentukan Solusi model LP berikut:
𝑀𝑎𝑥 𝑍 = 4𝑥 + 4𝑦
St 𝑥 + 2𝑦 ≤ 10
6𝑥 + 6𝑦 ≤ 36
𝑥≤4
𝑥, 𝑦 ≥ 0
Penyelesaian:

Memberikan solusi optimum berganda yang ditunjukkan dalam bentuk ruas garis solusi
optimal, tidak hanya titik solusi optimal.

Contoh 4.2
19
Tentukan Solusi model LP berikut:
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 2𝑥2
St 40𝑥1 + 60𝑥2 ≤ 1
50𝑥1 + 50𝑥2 ≤ 16
𝑥1 , 𝑥2 ≥ 0
𝑃𝑒𝑛𝑦𝑒𝑙𝑒𝑠𝑎𝑖𝑎𝑛𝑛𝑦𝑎:
Grafiknya Adalah

Memberikan solusi optimum berganda.

B. Solusi Tak Fisibel (Tak Layak)

Terjadi karena tidak ada daerah solusi fisibel. Artinya tidak ada daerah yang
merupakan perpotongan setiap pertidaksamaan/persamaan kendala

Contoh 4.3
Tentukan Solusi model LP berikut:
𝑀𝑎𝑥 𝑍 = 5𝑥 + 3𝑦
St 4𝑥 + 2𝑦 ≤ 8
𝑥≥1
𝑦≤5
𝑥, 𝑦 ≥ 0
Penyelesaian:
Grafiknya adalah :

20
Contoh 4.4
Tentukan Solusi model LP berikut:
𝑀𝑎𝑥 𝑍 = 5𝑥1 + 4𝑥2
St 30𝑥1 + 50𝑥2 ≤ 1
40𝑥1 + 40𝑥2 ≤ 1
𝑥1 ≥ 20
𝑥2 ≥ 10
𝑥1 , 𝑥2 ≥ 0
Penyelesaian:
Grafiknya adalah :

C. Solusi Optimum Tak terbatas

Artinya, daerah fisibel yang tak terbatas menyebabkan nilai Z meningkat tak terbatas
juga, akibatnya tidak pernah mencapai nilai yang paling optimum

21
Contoh 4.5
Tentukan Solusi model LP berikut:
𝑀𝑎𝑥 𝑍 = 2𝑥1 − 𝑥2
St 𝑥1 − 𝑥2 ≤ 1
2𝑥1 + 𝑥2 ≥ 6
𝑥1 , 𝑥2 ≥ 0
Penyelesaian:
Grafiknya adalah :

22
 KEGIATAN BELAJAR
5-6

Model Program Metode Simpleks

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dengan Metode Simpleks

A. Metode Simpleks

Metode simpleks adalah metode untuk mencari solusi optimal suatu model program
linear dengan prinsip iterasi. Iterasi (pengulangan) perhitungan dilakukan sampai
diperoleh solusi optimal. Pada setiap langkah iterasi diperoleh solusi yang fisibel, yang
jika dihubungkan pada metode grafik, solusi tersebut merupakan titik-titik solusi
perpotongan persamaan kendala pada daerah solusi fisibel tapi yang bukan solusi
optimal. Solusi optimal diperoleh pada akhir iterasinya. Beberapa syarat yang harus
diperhatikan pada metode ini adalah :
1. Bentuk kendala berupa pertidaksamaan atau persamaan dengan sisi kanan harus non
negatif.
2. Ada penambahan variabel pada masalah awalnya dengan tanda (+)/(–). Variabel
tersebut adalah :
a. Slack variable untuk bentuk kendala ≤,
b. Excess variable dan artificial variable untuk bentuk kendala ≥, dan
c. Artificial variable untuk bentuk kendala =.
B. Tabel Simpleks
Jika suatu model LP berbentuk :
Max 𝑍 = 𝑐1 𝑥1 + 𝑐3 𝑥2 + 𝑐3 𝑥3
s.t 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 ≤ 𝑏2
𝑎31 𝑥1 + 𝑎32 𝑥2 + 𝑎33 𝑥3 ≤ 𝑏3
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

23
Tambahkan slack variable untuk masalah maksimisasi, misalnya: 𝑥4 , 𝑥5 , 𝑥6 maka
masalahnya menjadi,
Max 𝑍 = 𝑐1 𝑥1 + 𝑐3 𝑥2 + 𝑐3 𝑥3
s.t 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + 𝑥4 ≤ 𝑏1
𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 + 𝑥5 ≤ 𝑏2
𝑎31 𝑥1 + 𝑎32 𝑥2 + 𝑎33 𝑥3 + 𝑥6 ≤ 𝑏3
𝑥1 , 𝑥2 , 𝑥3 ≥ 0

Tabel simpleks awal

Keterangan:
1. Variabel non basis yang akan dinaikkan (≥0) yang dapat memperbaiki
(menaikkan atau menurunkan) nilai fungsi tujuan Z disebut variabel masuk
(entering variable:e.v) menjadi variabel basis. Mis, 𝑥2
2. Variabel basis yang harus menjadi variabel non basis (bernilai nol) disebut
variabel keluar (leaving variable:l.v). Mis, 𝑥5
3. Kolom pada entering variable disebut entering column.
4. Baris yang berhubungan dengan leaving variable disebut persamaan pivot atau
pivot equation.
5. Elemen pada perpotongan antara entering column dan pivot equation disebut
pivot element. Mis, 𝑎22 .

Tabel simpleks baru

24
C. Algoritma Simpleks

Langkah-langkah untuk menentukan solusi optimal model LP dengan algoritma

simpleks adalah :
1. Pilih entering variable dengan nilai 𝑐𝑗 pada 𝑍 negatif nominal terbesar untuk
masalah maksimisasi, dan positif terbesar untuk masalah minimisasi.
2. Pilih leaving variable dengan nilai rasio 𝑏𝑗 /𝑎𝑖𝑗 non negatif terkecil. (𝑎𝑖𝑗 < 0 tidak
masuk dalam analisa).
3. Lakukan pivoting dan iterasi perhitungan untuk memperoleh tabel simpleks baru.
4. Jika 𝑐𝑗 semua non negatif (max) atau non positif (min) maka solusi telah optimal jika
tidak maka kembali ke awal.

Contoh 5.1 (Maksimisasi)

Tentukan solusi optimal dari model LP berikut.
𝑀𝑎𝑥 𝑍 = 6𝑥1 + 4𝑥2
𝑠. 𝑡 2𝑥1 + 2𝑥2 ≤ 30
𝑥1 + 2𝑥2 ≤ 20
4𝑥1 + 2𝑥2 ≤ 56
𝑥1 , 𝑥2 ≥ 0
Penyelesaian :
Tambahkan slack variable misalnya 𝑥3 , 𝑥4 , 𝑥5 pada bentuk kendala sehingga
masalahnya menjadi
𝑀𝑎𝑥 𝑍 = 6𝑥1 + 4𝑥2
𝑠. 𝑡 2𝑥1 + 2𝑥2 + 𝑥3 ≤ 30
𝑥1 + 2𝑥2 + 𝑥4 ≤ 20
4𝑥1 + 2𝑥2 + 𝑥5 ≤ 56
25
 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
𝐸𝑛𝑡𝑒𝑟𝑖𝑛𝑔 𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒 adalah 𝑥1 karena koeefisiennya pada baris 𝑍 sebesar -6 merupakan
negatif nominal terbesar dan leaving variable adalah 𝑥5 karena mempunyai nilai 𝑏𝑗
𝑎𝑖𝑗

nonnegative terkecil sebesar 56/4 = 14

Tabel Simpleks Awal

Lakukan pivoting dan menghitung nilai-nilainya menjadi tabel iterasi 1

Iterasi 1

Koeefisien pada 𝑍 belum nonnegatif. Negatif nominal terbesar pada 𝑥2 menjadi

entering variable. Leaving variable adalah 𝑥3 . Lakukan pivoting lagi sebagai iterasi 2
Iterasi 2

Koeefisien pada Z semuanya sudah non negatif. Solusi Optimal x1=13, x2=2, x3=0,
x4=3, x5=0, Z = 86
Contoh 5.2
Perusahaan sepatu “SENTOSA” membuat 2 macam sepatu . Macam pertama merek A1,
dengan sol dari karet, dan macam kedua merek A2 dengan sol dari kulit. Untuk membuat
sepatu-sepatu itu perusahaan memiliki 3 macam mesin. Mesin 1 khusus membuat sol
dari karet, mesin 2 khusus membuat sol dari kulit, dan mesin 3 membuat bagian atas
sepatu dan melakukan assembling bagian atas dengan sol. Setiap lusin sepatu merek A1
mula-mula dikerjakan dimesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus
dikerjakan dimesin 3 selama 6 jam. Sedang untuk sepatu merek A2 tidak diproses
dimesin 1, tetapi pertama kali dikerjakan dimesin 2 selama 3 jam kemudian dimesin 3

26
selama 5 jam. Jam kerja maksimum setiap hari untuk mesin 1 = 8 jam, mesin 2 = 15
jam, dan mesin 3 = 30 jam. Sumbangan terhadap laba untuk setiap lusin sepatu merek
A1 = Rp30.000,00 sedang merek A2 = Rp. 50.000,00. Tentukan berapa lusin sepatu
merek A1 dan merek A2 yang dibuat agar bisa memaksimumkan laba.
Penyelesaian:
Tabel masalahnya Adalah

Formulasi:
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2
𝑠. 𝑡 2𝑥1 ≤8
3𝑥2 ≤ 15
6𝑥1 + 5𝑥2 ≤ 30
𝑥1 , 𝑥2 ≥ 0
Tambahkan slack variabel: x3 , x4 , x5 pada bentuk kendala sehingga menjadi:
𝑀𝑎𝑥 𝑍 = 3𝑥1 + 5𝑥2
𝑠. 𝑡 2𝑥1 + 𝑥3 ≤8
3𝑥2 + 𝑥4 ≤ 15
6𝑥1 + 5𝑥2 + 𝑥5 ≤ 30
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0
Tabel Simpleks Awal

Iterasi 1:

Iterasi 2:

27
Karena semua 𝑐𝑗 ≥ 0, maka solusi telah optimal:

𝑥1 = 5/6, sehingga A1 = 5/6 lusin setiap hari.

𝑥2 = 5, sehingga A2 = 5 lusin setiap hari.
Z max = 27 artinya laba yang akan diperoleh = Rp. 275.000,00 setiap hari.
D. Big M Method

Untuk masalah minimisasi menggunakan suatu metode yang disebut Big M Method.
Aturan dalam metode ini adalah :
1. Penambahan artificial variable pada kendala yang tidak memiliki slack variable.
2. Artificial variable merupakan variabel basis pada kondisi awal.
3. Artificial variable akan bernilai nol pada solusi optimal.
4. Koefisien pada Z : M (MIN), -M (MAX) dengan M adalah nilai positif yang sangat
besar.
5. Persamaan tujuan (Z) pada tabel simpleks awal mengikuti inner product rule dengan
rumus :

Contoh 5.3
Tentukan Solusi optimal dari model LP berikut.
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 8𝑥2
S.t 𝑥1 + 𝑥2 ≥ 4
𝑥1 + 3𝑥2 ≥ 6
𝑥1 , 𝑥2 ≥ 0
Penyelesaian:
Kurangkan setiap kendala dengan excess variable misalnya x3, x4, maka
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 8𝑥2 + 0𝑥3 + 0𝑥4
S.t 𝑥1 + 𝑥2 − 𝑥3 =4
𝑥1 + 3𝑥2 − 𝑥4 = 6
𝑥1 , 𝑥2 ≥ 0
Menambahkan artificial variable misalnya 𝑎1 , 𝑎2 menjadi

28
Min 𝑍 = 4𝑥1 + 8𝑥2 + 0𝑥3 + 0𝑥4 + 𝑀𝑎1 + 𝑀𝑎2
S.t 𝑥1 + 𝑥2 − 𝑥3 + 𝑎1 = 4
𝑥1 + 3𝑥2 − 𝑥4 + 𝑎2 = 6
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑎1 , 𝑎2 ≥ 0

dengan koefisien tiap variabel pada Z mengikuti inner product rule, maka
Tabel simpleks awal

Entering variable : x_2 dan leaving variable : 𝑎2

Iterasi 1

Entering variable : x1 dan leaving variable : a1

Iterasi 2

Kooefisien pada Z senuamya sudah nonpositif Solusi optimal Z=20, x1=3, x2=1.

29
 KEGIATAN BELAJAR
7

Kuis

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dalam kuis dari pertemuan
1-6

30
 KEGIATAN BELAJAR
8

UTS

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dalam UTS dari pertemuan
1-6

31
 KEGIATAN BELAJAR
9

Model masalah Program Linier Metode Dual Simpleks

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dengan Metode Dual
Simpleks
A. Metodel Dual Simpleks
Untuk menghindari penambahan artificial variabel pada kendala , dapat dilakukan dengan
membuat kendala tersebut menjadi dengan mengalikan sisi kiri dan kanannya dengan -1.
Agar penyelesaiannya hanya menambahkan dengan slack variabel. Tetapi kasus ini akan
melanggar batasan model LP karena sisi kanan menjadi negatif. Untuk menyelesaikan
model ini dikenal dengan metode dual simplex. Langkah-langkah metode dual simplex :
- Buat bentuk kendala “≥” menjadi “≤”, agar tidak ada penambahan artificial variable
- Diawali solusi tak fisibel (sisi kanan negatif)
- Pilih Leaving Variable : variabel basis yang memiliki nilai pada sisi kanan negatif terbesar
(jika semua variabel basis nonnegatif maka proses berakhir dan solusi fisibel telah
optimum)
- Pilih Entering Variable : (dari variabel nonbasis), rasio koefisien pada Z dengan koefisien
pada pivot equation (abaikan penyebut ≥ 0) absolut terkecil. Jika semua penyebut ≥ 0,
solusi tak fisibel.
- Lakukan perhitungan seperti pada pivoting metode simpleks.

Contoh 9.1
Tentukan Solusi optimal masalah berikut dengan metodel dual simpleks.
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 2𝑥2
𝑠. 𝑡 3𝑥1 + 𝑥2 ≥ 27
𝑥1 + 𝑥2 ≥ 21
𝑥1 + 2𝑥2 ≥ 30
𝑥1 , 𝑥2 ≥ 0
Penyelesaian:
Buat bentuk kendala “≥” menjadi “≤”:

32
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 2𝑥2
𝑠. 𝑡 −3𝑥1 − 𝑥2 ≤ −27
− 𝑥1 − 𝑥2 ≤ −21
−𝑥1 − 2𝑥2 ≤ −30
𝑥1 , 𝑥2 ≥ 0
Tambah slack variabel : 𝑥3 , 𝑥4 , 𝑥5
𝑀𝑖𝑛 𝑍 = 4𝑥1 + 2𝑥2
𝑠. 𝑡 −3𝑥1 − 𝑥2 + 𝑥3 = −27
− 𝑥1 − 𝑥2 + 𝑥4 = −21
−𝑥1 − 2𝑥2 + 𝑥5 = −30
𝑥1 , 𝑥2 , 𝑥3 , 𝑥4𝑥 , 𝑥5 ≥ 0
Tabel simpleks awal

Iterasi 1

Iterasi 2

Iterasi 3

Solusi optimal : Z= 48, x1= 3, x2 = 18, x5= 9, x3= x4= 0

33
 KEGIATAN BELAJAR
10-14

Analisis Sensitivitas dan Model PL dengan Mathematica dan Lingo

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dengan bantuan Wolfram
Mathematica dan LINGO

Materi menggunakan jurnal dan praktek secara langsung

Materi:
Model ILP untuk dijadikan Program

1. Tahir, Windra dkk (2019). “Optimasi Penjadwalan Waktu Kerja Menggunakan

Integer Programming”. EULER : Jurnal Ilmiah Matematika, Sains dan Teknilogi.
Vol 7, No2.2 , Hal 51-55.
2. Safitri, Elfira dkk (2021), Optimasi Penjadwalan Perawat Menggunakan Integer
Linear Programming (Studi Kasus: RS. Aulia Hospital Pekanbaru),Jurnal Forier,
Vol 10, N0. 1, 45-56 15%
3. Saragih, Sisca Sri Dewi dkk (2025), Pemodelan Matematika Tipe S1S2E1E2I1I2T Pada
Diabetes Melitus Tipe 2 Dengan Mempertimbangkan Treatment Yang Diakibatkan
Adanya Pengaruh Obesitas, Imajiner: Jurnal Matematika dan Pendidikan
Matematika. Vol 7, N0.4, Hal: 308-316

34
 KEGIATAN BELAJAR
15

Kuis

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
1. Menjelaskan dan Menyelesaikan Model Program Linier dalam kuis dari pertemuan 1-14

KEGIATAN BELAJAR
16 35
 UAS

Tujuan:
Setelah mempelajari materi ini diharapkan mahasiswa memliki kemampuan untuk:
2. Menjelaskan dan Menyelesaikan Model Program Linier dalam UTS dari pertemuan 1-14

36