INDIKATOR

RINGKASAN ......................................................................................................................... 2
ABSTRAK ..................................................................................................................... 3
PENDAHULUAN................................................................................................................ 4
Tujuan Umum............................................................................................................ 5
Objektif Khusus......................................................................................................... 5
TEORI PEMPROGRAMAN LINEAR ..................................................................... 6
Konsep dasar ............................................................................................................. 6
Solusi grafis ................................................................................................................ 7
Bentuk standaro.................................................................................................................... 9

Bentuk kanonik............................................................................................................... 10
METODE SEDERHANAX ..................................................................................................... 11

Algoritma Simplex Tabular

Solusi Optimal Ganda............................................................................................. 12
Adaptasi Kasus Spesifik................................................................................... 12
Metode Besar-M ................................................................................................................ 12

DUALITAS DALAM PEMPROGRAMAN LINIER .......................................................... 13

KESIMPULAN
REFERENSI BIBLIOGRAFI
 RINGKASAN

Dalam pekerjaan ini dilakukan studi tentang konsep-konsep utama Pemrograman

Linier, untuk memberikan pemahaman tentang metode konstruksi dan penyelesaiannya
masalah. Untuk itu, telah dipelajari dan disini disajikan konsep-konsep esensial
untuk formulasi masalah dalam bentuk standarnya melalui suatu dasar
teoritis dan penyelesaian contoh, sehingga memungkinkan pemahaman tentang Pemrograman
Linear. Untuk solusi masalah, metode Simplex dan Simplex telah dipelajari.
Revisi dan Dual Simplex serta Dualitas dalam pemrograman linier dan bentuknya
dari resolusi.

Kata Kunci: Pemrograman Linier. Simplex. Dualitas. Direvisi

2
 ABSTRAK

Pekerjaan ini dilakukan untuk mempelajari konsep-konsep utama Pemrograman Linier di

untuk memberikan pemahaman tentang metode konstruksi dan pemecahan masalah mereka.
Untuk itu, telah dipelajari dan disajikan di sini, konsep-konsep penting untuk perumusan
masalah dalam bentuk standar mereka melalui dasar teori dan resolusi dari
contoh, sehingga memungkinkan pemahaman tentang Pemrograman Linier. Untuk menyelesaikan

masalah, metode Simplex, Revised Simplex, dan Dual Simplex serta

Dualitas dalam pemrograman linier dan bentuk penyelesaiannya telah digunakan.

Pemrograman Linier. Simplex. Dualitas. Direvisi.

3
 PENDAHULUAN

Tema yang dipilih untuk objek disertasi ini adalah "Pemrograman Linier"
Pemrograman Linier diciptakan oleh Dantzig (1948) sebagai bentuk perencanaan
diotomatisasi untuk distribusi sumber daya, logistik, dan alokasi waktu untuk
Angkatan Darat Amerika Serikat. Pada intinya, Pemrograman Linier memiliki fokus pada
optimasi sistem, melalui maksimisasi atau minimisasi tertentu
masalah yang dirumuskan secara matematis (Hillier; Leiberman, 2006).

Pada tahun 1949, Dantzig menerbitkan sebuah studi yang menggambarkan Metode Simplex untuk

penyelesaian masalah Program Linear. Metode ini banyak digunakan

karena kemampuannya dalam mengelola masalah kompleks dalam pengambilan keputusan, baik
sebagai kemampuan untuk menghasilkan keputusan yang dapat diterima dalam waktu singkat
(Hillier; Leiberman, 2006). Penelitian ini bertujuan untuk memberikan pengetahuan.
perlu tentang konsep utama dan cara penyelesaian masalah dari
Pemrograman Linier, berfungsi sebagai cara pembelajaran dalam penyelesaian dan pembangunan dari

masalah melalui algoritma yang tersedia saat ini.

4
Tujuan Umum

Digunakan untuk mengoptimalkan (memaksimalkan atau meminimalkan) suatu fungsi linier dari

variabel, disebut sebagai fungsi tujuan, terikat pada serangkaian persamaan (atau
inekuasi) linier, disebut batasan.

Tujuan Spesifik

Mengenali masalah yang dapat dianalisis oleh model;

Membantu analis dalam tahap awal penyelidikan;
Menilai dan menginterpretasikan hasil dengan cerdas;

5
 TEORI PEMPROGRAMAN LINIER

Konsep dasar
Pemrograman Linier bertujuan untuk melakukan operasi dengan
tujuan untuk menemukan solusi terbaik dan membantu dalam pengambilan keputusan masalah
yang diwakili oleh model dengan ekspresi linier. Pendekatan ini memiliki
bagaimana ruang lingkup maksimum atau minimum dari fungsi linier, yang disebut Fungsi
Tujuan, yang umumnya dinyatakan dengan:

= 1+ 1 +⋯
2 2+ tidak ada variabel disebut variabel
keputusan.

Untuk menentukan nilai yang tepat yang harus dimiliki oleh variabel keputusan
membutuhkan untuk mengikuti sekumpulan persamaan atau pertidaksamaan juga linear,
yang menentukan aturan yang harus diadopsi oleh model. Kumpulan ekspresi ini adalah
dikenal sebagai Pembatasan Model dan mengikuti struktur berikut:

11+ 11+ ⋯12+ 12 ≤ 1 1 1

+ 21 + ⋯22+ 22 ≤
21 2 2 2
⋮ ⋮ ⋮ ⋮ ⋮
+1 1 ⋯ +2 ≤2
+ m

,1 , …
2 , ≥ 0.

Sebagai Batasan Model bertanggung jawab untuk membatasi suatu area dari
solusi yang dikenal dengan area yang dapat dicapai atau area yang layak. Solusi terbaik, dikenal dengan

solusi optimal, ditemukan dalam wilayah ini dapat memaksimalkan atau meminimalkan
fungsi objektif. Bazaraa, Jarvis dan Sherali (2010) mendefinisikan bahwa sebuah masalah dari

Pemrograman Linear harus dibuat berdasarkan analisis yang memerlukan serangkaian

langkah-langkah, yaitu:

Perumusan masalah: Terdiri dari evaluasi terhadap masalah nyata, di

faktor-faktor pembatas yang harus dipertimbangkan, kemungkinan variasi, konstanta dan
restriksi. Di tahap ini berlangsung pengumpulan data dan diidentifikasi
masalah yang harus dipelajari;

Pembangunan model matematis: Mewakili tahap di mana masalah

matematik diidealkan melalui analisis yang dilakukan pada langkah sebelumnya. A

6
 formulasi harus dibangun dengan cermat agar dapat menghasilkan sebuah
model matematis yang mewakili masalah;
Pengambilan sebuah solusi: Harus dipilih pendekatan mana yang
resolusi memberikan model. Adalah mungkin untuk mencari beberapa solusi optimal
kamu hanya satu, dan untuk kedua kasus tersebut, harus memilih heuristik atau
teknik yang paling sesuai untuk mengurangi penurunan sekecil mungkin
kualitas
Uji model: Dalam langkah ini dilakukan analisis keandalan dan jika
perlu, restrukturisasi melalui tambahan atau penyederhanaan ekspresi,
agar model yang dimaksud dapat dipercaya dalam berbagai situasi.
Untuk mendapatkan kredibilitas hasil yang lebih besar, sangat penting juga bahwa

analisis hasil yang diharapkan dengan hasil yang sudah diprediksi;

Implementasi: Penting agar model terus diperbarui
dengan kemungkinan parameter atau pembatasan baru jika perlu, serta
meskipun harus dievaluasi secara terus-menerus agar tidak menjadi usang.

Solusi grafis
Di antara metode solusi yang ada untuk masalah Pemrograman Linier, adalah
secara luas dibahas oleh penulis seperti Bazaraa, Jarvis, dan Sherali (2010) serta Kolman dan
Beck (1995) kemungkinan untuk menyelesaikan masalah secara grafis dengan sedikit
jumlah variabel keputusan. Sebagai contoh, pertimbangkan masalah (I).

Adanya dua variabel keputusan memungkinkan representasi grafis di

ruang dua dimensi, di mana dapat mengambil
1 sumbu absis dan sebagai 2
terurut. Kategori solusi masalah ini dapat mencapai solusi optimal,
mengikuti langkah-langkah berikut:

1. Menemukan daerah solusi yang layak melalui representasi masing-masing

atasi batasan, dengan mematuhi poin-poin yang memenuhi batasan.

7
 2. Melalui verifikasi titik (0,0), untuk setiap batasan, adalah mungkin untuk menganalisis
secara visual di sisi mana dari garis solusi akan berada, sehingga memungkinkan sebuah
delimitasi global menggunakan semua batasan, memperlihatkan kawasan
dapat dicapai.
a) Mungkin ada masalah di mana area yang dapat diterima tidak ada, yaitu

maka dianggap sebagai masalah yang mustahil, atau tidak dapat dilakukan.

Satu rangkaian garis paralel dapat dihasilkan melalui representasi dari

fungsi objektif. Solusi optimal terletak pada titik yang terkait dengan
nilai yang paling mengoptimalkan masalah dan menyentuh daerah yang layak.

Gambar 1 menunjukkan representasi grafis dari semua pembatasan yang berkaitan dengan model

Mengingat batasan untuk persepsi wilayah yang layak dari masalah ini,
sesuai yang diindikasikan pada langkah 2, maka grafik yang ditampilkan pada Gambar 2 dibuat.

Gambar 2–Wilayah yang layak dari masalah (I) disorot

8
 Gambar 3 menunjukkan garis-garis yang berkaitan dengan fungsi tujuan, menghasilkan gradien
yang memungkinkannya untuk melihat kemungkinan solusi dari masalah.

Gambar 3–Garis potong dengan fungsi tujuan yang disorot dalam grafik.

Dapat diasumsikan melalui analisis tren garis bahwa titik yang mengarah ke
solusi terbaik dari masalah terletak pada perpotongan antara garis-garis dari persamaan (1) dan
(2), menghasilkan sistem yang sesuai:

Penyelesaian sistem yang dihasilkan oleh dua persamaan ini menghasilkan titik (200,
600). Menggantikan nilai-nilai tersebut ke dalam fungsi tujuan, diperoleh = 2600. Apa solusinya

hebat.

Bentuk standar

Agar dapat menggunakan algoritma solusi seperti Simplex atau Simplex

direvisi, umumnya digunakan dalam masalah praktis, disarankan agar masalah tersebut
perjanjian diubah menjadi bentuk standar. Model minimisasi berada di
dalam bentuk standar pada formulasi berikut, menurut Marins (2011):

9
 Bentuk kanonik
Pertimbangkan sistem persamaan berikut:

Himpunan solusi dari sistem adalah nilai-nilai dari 1, 2, 3, e apa 4 5

memuaskan kedua persamaan sistem secara bersamaan. Dikenal sebagai sebuah

Sistem Setara. Sistem setara dapat diperoleh melalui suatu proses
matematik yang disebut Metode Eliminasi Gauss Jordan. Proses ini didasarkan pada
pada perkalian dan pembagian salah satu persamaan dari sebuah sistem dengan suatu nilai tertentu

nomor yang ketika dijumlahkan dengan kombinasi linier dalam persamaan lain, menghasilkan istilah

dihapus.

Metode Eliminasi Gauss Jordan pada sistem yang mengandung persamaan (11)
e (12) dimulai dengan pengalian (11) dengan -1 diikuti oleh penambahan ke (12), menghasilkan
jadi, sistem ekuivalen berikut:

Masih mungkin untuk menghilangkan 2de (13) Mengalikan (14) dengan 2 dan menjumlahkannya dalam persamaan

dalam hal ini, apa yang dihasilkan adalah:

Karena tidak lagi mungkin untuk mengurangi jumlah variabel, maka dikatakan bahwa
ini adalah Bentuk Kanonik dari sistem asli. Mengingat sistem dalam bentuknya
kanonik, maka dimungkinkan untuk melakukan definisi berikut:

Dikatakan sebagai variabel dasar yang memiliki koefisien 1 dalam salah satu dari
persamaan, dan menganggap nilai nol pada yang lainnya. Jika kondisi ini salah, ini
variabel maka dianggap sebagai variabel non dasar. Sistem kanonik (II)
dibahas, mengandung 1e 2sebagai variabel dasar dan 3, 4e 5seperti yang tidak mendasar.

10
 Solusi dasar dari sebuah sistem dalam bentuk kanoniknya diberikan dengan membuat agar
semua variabel non dasar harus mengambil nilai nol. Untuk sistem (II) 3=
4= 5= 0, 1= 6 e 2= 2 kembali ke solusi dasar.
Ketika semua variabel mengambil nilai positif, dikatakan bahwa solusi ini adalah
solusi dasar yang layak. Untuk sistem (II) yang diberikan, solusi dasarnya adalah
solusi dasar yang layak.

METODE SIMPLEX
Ini adalah prosedur iteratif aljabar yang dikembangkan oleh George B. Dantzig pada
1947. Bertujuan untuk melanjutkan dari solusi dasar yang layak yang ada.
di sebuah titik ekstrem, untuk titik lain yang berdekatan yang berusaha menambah fungsi
tujuan, atau setidaknya dalam kasus terburuk menjaga nilainya tetap sama.

Algoritma dijalankan sampai menemukan solusi optimal atau disimpulkan

bahwa masalah tersebut tidak memiliki solusi optimal finite (Kolman; Beck, 1995). O
algoritma didasarkan pada dua langkah utama sesuai dengan Kolman dan Beck (1995):

1) Memverifikasi apakah solusi dasar yang layak tertentu adalah solusi optimal;

2) Menemukan solusi dasar yang layak dengan nilai yang sama atau nilai yang lebih besar

untuk fungsi tujuan.

Algoritma Simplex Tabular

Metode Simplex digunakan dalam format tabel, yang mewakili sebuah bentuk
singkat dan terorganisir untuk penyelesaian masalah. Untuk pembuatan tabel, adalah
perlu identifikasi koefisien variabel dan konstanta di sisi kanan
da persamaan. Tabel yang disebut Tabel Simplex, memiliki tujuan untuk menyederhanakan
Menampilkan sistem persamaan secara ringkas yang menghasilkan solusi dasar yang layak.

Berbagai penulis seperti Kolman dan Beck (1995), Bazaraa, Jarvis dan Sherali (2010)
Hillier dan Leiberman (2006) menyajikan variasi kecil dalam konstruksi Tabel
Simplex, namun tidak ada perubahan dalam pelaksanaan algoritma untuk solusi
dari masalah. Untuk studi ini, digunakan model Bazaraa, Jarvis, dan Sherali (2010),
yang disajikan dalam Tabel 1.

11
 Tabel 1 - Format tabel dalam metode Simplex tabul

Solusi Optimal Ganda

Fakta bahwa sebuah masalah Program Linear dapat memiliki lebih dari satu solusi,
dapat mengarah pada kasus di mana lebih dari satu hasil optimal dapat ditemukan. Metode
Simplex, saat diselesaikan, dapat menunjukkan jika solusi optimal lain berlaku. Jika
apakah ada = 0 yang terkait dengan variabel non-dasar , jadi model di
pertanyaan memiliki solusi optimal lain yang layak di mana ini adalah variabel dasar.

Adaptasi Kasus Spesifik

Dalam kasus di mana model tidak mengikuti bentuk standar yang diselesaikan dengan metode

Simplex mungkin bisa menggunakan proses agar bisa disesuaikan dan dapat
biasanya diselesaikan dengan baik. Adaptasi ini biasanya membutuhkan tabel Simplex
melewati proses penyelesaian dalam dua tahap, yang dapat dilakukan melalui
Metode Big-M.

Metode Big-M
Metode ini diterapkan pada batasan yang tidak menghormati model standar melalui
dari penggunaan pembatasan fungsional, sehingga memiliki bentuk berikut:

12
 Ometode Big-M didasarkan pada manipulasi pada format model, menciptakan
sebuah masalah buatan yang solusi optimalnya sama dengan masalah asli. Itu adalah
variabel buatan diperkenalkan tidak negatif dalam pembatasan masing-masing seolah-olah
fossem variabels dari kelebihan. Variabel yang dibuat memerlukan biaya yang sangat tinggi
alto, diwakili oleh koefisien dalam fungsi tujuan. Metode Simplex untuk
masalah buatan biasanya dieksekusi, namun harus diperhatikan bahwa
kebutuhan semua akan menjadi variabel non-dasar, oleh karena itu, mengasumsikan
nilai nol. Selanjutnya, kolom yang mewakili nilai dari haruslah
dihapus dari tabel Simplex dan proses dilanjutkan sampai ditemukan solusi
baik. Jika solusi optimal yang ditemukan mengandung variabel buatan dengan nilai
berbeda dari 0, masalah asli adalah tidak layak.

DUALITAS DALAM PROGRAMMING LINIER

Untuk setiap masalah pemrograman linier, ini dianggap Primal, ada yang lain
masalah yang disebut Dual. Masalah ini dihasilkan langsung dari nilai-nilai yang terkandung
tidak ada masalah Primal asli (BAZARAA; JARVIS; SHERALI, 2010). Mengasumsikan
format berikut:

Koefisien fungsi objektif di Primal mengambil nilai dari sisi

hak dari pembatasan masalah Dual;
Nilai di sisi kanan masalah Primal menjadi koefisien
dari biaya fungsi tujuan dalam masalah Dual, yaitu, menghasilkan sebuah
variabel berdasarkan pembatasan;

Setiap kumpulan koefisien yang termasuk dalam variabel yang sama hadir
nas restrições do Primal, torna-se uma variável no problema Dual;
Tanda ketidaksetaraan dibalik.

Figura 4–Paralel antara masalah Primal dan Dual

13
 KESIMPULAN

Pekerjaan ini bertujuan untuk bertindak sebagai praktik pembelajaran bagi para
konsep utama dan penyelesaian masalah pemrograman linier. Tujuan ini telah
diselesaikan melalui paparan konsep-konsep yang berkaitan dengan metode Simplex,
Simplex Revisi, dan Dual Simplex untuk penyelesaian masalah pemrograman linier.
Melalui konseptualisasi ini berdasarkan pada dasar teori dari
algoritma, teknik penyelesaian dan adaptasi kasus memungkinkan untuk melakukan penyelesaian
masalah yang mengarah pada pemahaman konsep yang dijelaskan.

14
 REFERENSI BIBLIOGRAFI

BAZARAA M. S.; JARVIS J. J; SHERALI H. D. Pemrograman Linier dan

Aliran Jaringan. Virginia: Wiley, 2010. Edisi ke-4. 748 hlm. DANTZIG G. B. Pemrograman dalam a

Struktur Linier, Pengendali, Angkatan Udara Amerika Serikat, Washington, 1948. HILLIER F.
S.; LIEBERMAN G. J,. Pengantar penelitian operasional. São Paulo: McGraw Hill,
2006. Edisi ke-8. 829 hlm. KOLMAN B.; BECK R. E. Pemrograman Linear Dasar dengan
Aplikasi, Amerika Serikat: Elsevier, 1995, 449 hlm. MARINS F. A. S. Pengantar ke
penelitian operasional. São Paulo: Cultura Acadêmica, 2011. 176 hlm.

15