METODE SIMPLEX

Metode Simplex adalah metode analitis untuk menyelesaikan masalah

depemrograman linier mampu menyelesaikan model yang lebih kompleks daripada yang
diselesaikan melaluimetode grafiktanpa batasan pada jumlah variabel.

Metode Simpleks adalah metode iteratif yang memungkinkan untuk terus memperbaiki solusi dalam
setiap langkah. Alasan matematis dari peningkatan ini terletak pada kenyataan bahwa metode ini terdiri dari
dalam berjalan dari sudut sebuah poliedra ke sudut tetangga dengan cara yang meningkat
atau kurangi (tergantung pada konteks fungsi tujuan, baik memaksimalkan atau meminimalkan),
mengingat bahwa jumlah titik sudut yang dimiliki oleh sebuah poliedro adalah terbatas
selalu akan ada solusi.
Metode populer ini dibuat pada tahun 1947 oleh warga negara Amerika [Link]
Bernard Dantzigdan Rusia Leonid Vitalievich Kantorovich, dengan semangat untuk menciptakan
sebuah algoritma yang mampu memecahkan masalah pembatasan dan variabel.

APA ITU MATRIS IDENTITAS?

Sebuah matriks dapat didefinisikan sebagai pengaturan berbentuk persegi panjang dari elemen, (atau
daftar elemen yang terbatas), yang dapat berupa angka real atau kompleks,
ditempatkan dalam bentuk baris dan kolom.

Matriks identitas atau identitas adalah matriks persegi (yang memiliki ukuran yang sama)
jumlah kolom dan baris) dari urutan n yang memiliki semua dari
elemen diagonal sama dengan satu (1) dan semua komponen lainnya sama dengan
cero (0), disebut matriks identitas atau identitas urutan n, dan dilambangkan dengan:

Pentingnya teori matriks dalam Metode Simplex sangat mendasar,

karena algoritma tersebut didasarkan pada teori tersebut untuk penyelesaian.
masalah.
CATATAN PENTING KE
MENGGUNAKAN METODE SIMPLEX
VARIABEL KELONGGARAN DAN KELEBIHAN
Metode Simplex bekerja berdasarkan persamaan dan batasan awal
yang dimodelkan melalui pemrograman linier tidak demikian, untuk itu harus
mengubah ketidaksamaan ini menjadi persamaan dengan menggunakan beberapa variabel
disebut sebagai kelonggaran dan kelebihan terkait dengan sumber daya yang dimaksud
rujuk pada pembatasan dan yang dalam tabel akhir mewakili "Slack atau
surplus" yang dirujuk oleh program-program terkenal untuk penyelesaian
investigasi operasi, variabel-variabel ini memperoleh nilai yang besar di
analisis sensitivitas dan berperan penting dalam pembuatan matriks
identitas dasar dari Simplex.

Variabel ini biasanya dilambangkan dengan huruf "S", ditambahkan jika

restriksi adalah tanda "<= " dan dikurangkan jika restriksi adalah tanda ">=."

Contohnya:
VARIABEL Buatan / METODE 'M'
Sebuah variabel buatan adalah trik matematis untuk mengubah ketidaksetaraan ">=" menjadi
persamaan, atau ketika muncul kesetaraan dalam masalah asli, maka
karakteristik utama dari variabel-variabel ini adalah bahwa mereka tidak boleh menjadi bagian dari
solusi, mengingat bahwa mereka tidak mewakili sumber daya. Tujuan utama dari ini
variabel adalah pembentukan matriks identitas.

Variabel ini dilambangkan dengan huruf "A", selalu dijumlahkan dengan

restriksi, koefisiennya adalah M (karena ini disebut Metode M
besar, di mana M berarti angka yang terlalu besar sangat tidak menarik untuk
fungsi tujuan), dan tanda dalam fungsi tujuan bertentangan dengan makna dari
Misma, yaitu, dalam masalah Maximisasi tanda nya adalah kurang (-) dan di
masalah Minimización tanda nya adalah (+), kita ulangi dengan tujuan bahwa
nilai dalam solusi sama dengan nol (0).

METODE SIMPLEKS LANGKAH DEMI LANGKAH

MASALAH
Perusahaan el SAMÁN Ltda. yang bergerak di bidang pembuatan furnitur, telah memperluas
produksinya dalam dua lini lagi. Oleh karena itu saat ini memproduksi meja, kursi,
kasur dan perpustakaan. Setiap meja memerlukan 2 potongan persegi panjang 8 pin, dan
2 potongan persegi 4 pin. Setiap kursi membutuhkan 1 potongan persegi panjang 8
pines dan 2 potongan persegi 4 pines, setiap tempat tidur membutuhkan 1 potongan persegi panjang
8 pin, 1 kotak berukuran 4 pin dan 2 pangkal trapezoid berukuran 2 pin dan akhirnya
setiap perpustakaan memerlukan 2 potongan persegi panjang berukuran 8 pin, 2 dasar
trapezoidal dengan 2 pin dan 4 potongan persegi panjang dengan 2 pin. Setiap meja biaya
memproduksinya seharga $10000 dan dijual seharga $30000, setiap kursi biaya produksinya $8000 dan se
dijual seharga $ 28000, setiap kasur biaya produksinya $ 20000 dan dijual seharga $ 40000
Setiap perpustakaan biaya produksinya $ 40000 dan dijual dengan harga $ 60000. Tujuan dari
pabrik adalah memaksimalkan keuntungan.

Masalah yang dihadapi

oleh Edwin Bastidas - Insinyur Industri
LANGKAH 1: PEMODELAN MELALUI
PROGRAMASI LINIER
Variabel:

X1Jumlah meja yang akan diproduksi (unit)

X2Jumlah kursi yang akan diproduksi (unit)
X3Jumlah tempat tidur yang akan diproduksi (unit)
X4Jumlah perpustakaan yang akan diproduksi (unit)

Pembatasan:

2X1+1X2+ 1X3+ 2X4<= 24

2X1+2X2+ 1X3<= 20
2X3+ 2X4<= 20
4X4<= 16

Fungsi Tujuan:

ZMAKS=20000X1+20000X2+20000X3+ 20000X4
LANGKAH 2: MENGUBAH INEKUASI MENJADI
PERSAMAAN
Pada langkah ini, tujuannya adalah untuk memberikan setiap sumber daya sebuah variabel Holgura, mengingat
bahwa semua batasan adalah "<=".

2X1+1X2+ 1X3+ 2X4+1S1+ 0S2+0S3+0S4= 24

2X1+2X2+ 1X3+0X4+0S1+ 1S2+0S3+0S4= 20
0X1+0X2+ 2X3+2X4+0S1+ 0S2+1S3+0S4=20
0X1+0X2+ 0X3+4X4+0S1+ 0S2+0S3+1S4=16

Dengan cara ini kita dapat menghargai matriks identitas (n = 4), yang dibentuk oleh
variabel slack yang hanya memiliki koefisien 1 dalam sumber dayanya masing-masing,
misalnya variabel slack "S1" hanya memiliki koefisien 1 dalam pembatasan
berkaitan dengan sumber daya 1.

Fungsi tujuan tidak mengalami variasi:

ZMaks=20000X1+20000X2+20000X3+ 20000X4
LANGKAH 3: MENENTUKAN SOLUSI DASAR AWAL
Metode Simplex dimulai dari solusi dasar awal untuk melakukan semua
iterasi, solusi dasar awal ini dibentuk dengan variabel koefisien
berbeda dari nol (0) pada matriks identitas.

1S1= 24
1S2= 20
1S3=20
1S4=16
LANGKAH 4: MENENTUKAN TABEL SIMPLEX AWAL

[Link]
Solusi: (istilah kedua)= Di baris ini dicatat istilah kedua dari
solusi, yaitu variabel, sebaiknya ini dicatat dari
dalam urutan yang teratur, sama seperti yang ditulis dalam definisi pembatasan.
Cj= Baris "Cj" mengacu pada koefisien yang dimiliki setiap variabel
dari baris "solusi" dalam fungsi tujuan.
Dalam kolom ini dicatat solusi dasar awal, dan a
mulai dari sini, di setiap iterasi variabel yang akan menjadi bagian akan ditambahkan
dari solusi akhir.
 Cb= Di baris ini dicatat nilai yang dimiliki oleh variabel yang terdapat di dalamnya
kanan "Variabel solusi" di fungsi tujuan.
Zj= Di baris ini dicatat kontribusi total, yaitu jumlah dari
produk antara istilah dan Cb.
Cj - Zj = Di baris ini, perbedaan antara baris Cj dan baris Zj dilakukan,
significado adalah 'Harga Bayangan', yaitu, utilitas yang tidak diterima oleh
setiap unit dari variabel terkait yang tidak menjadi bagian dari solusi.

Solusi awal:

[Link]
LANGKAH 5: MELAKUKAN ITERASI
PERLU
Ini adalah langkah terakhir dalam penyelesaian melalui Metode Simplex, terdiri dari
untuk melakukan percobaan saat model berpindah dari satu titik sudut poliedron tujuan ke titik sudut lainnya.

Prosedur yang harus diikuti adalah sebagai berikut:

1. Menilai variabel mana yang akan masuk dan mana yang akan keluar dari solusi optimal:

Memaksimalkan Meminimalkan
Variabel yang
Yang paling positif dari Cj - Zj Yang paling negatif dari Cj - Zj
masuk
Siendoblos nilai di bawah sel solusi Siendo blos nilai di bawah sel solusi
yael nilai yang sesuai dengan perpotongan yael nilai yang sesuai la
Variabel yang keluar a
masukkan variabel yang masuk. Yang kurang dari perpotongan antara variabel yang masuk.
 positiva de losb/a. Yang paling positif dari losb/a.

[Link]
Fakta bahwa suatu variabel yang berbeda menjadi bagian dari variabel solusi
mengimplikasikan serangkaian perubahan dalam tabel Simplex, perubahan yang akan dijelaskan di
lanjutan.

- Yang pertama adalah tidak melupakan nilai "a" yang sesuai dengan variabel yang akan dimasukkan,
dalam kasus ini "a = 4".

[Link]
- Hal berikutnya adalah mulai mengisi sisa tabel, baris demi baris.
[Link]
- Prosedur ini diulang dengan dua baris yang tersisa, sekarang kita akan melakukan
perhitungan yang sesuai di sisa sel.
[Link]
Dengan cara ini, iterasi pertama selesai, langkah ini akan diulang berapa pun yang diperlukan.
seringkali diperlukan dan hanya akan dihentikan metode sesuai dengan yang berikut
kriteria.
Maksimalkan Minimalkan
Solusi Optimal Ketika semua Cj - Zj <= 0 Ketika semua Cj - Zj >= 0
Kami melanjutkan dengan iterasi yang mana kita harus mengulangi langkah-langkah
sebelumnya.
[Link]
Pada iterasi terakhir ini kita dapat mengamati bahwa konsignasi Cj - Zj terpenuhi
<= 0, untuk latihan yang fungsi tujuannya adalah "Memaksimalkan", oleh karena itu kita telah
kedatangan pada jawaban optimal.

X1=3
X2=4
X3=6
X4=4
Dengan keuntungan sebesar: $ 340000

Namun, setelah Metode Simplex selesai, perlu mengamati sebuah matriks

identitas dalam persegi panjang yang ditentukan oleh variabel keputusan, kenyataannya
bahwa dalam kasus ini tidak ditampilkan matriks identitas berarti ada sebuah
solusi alternatif yang optimal.
[Link]
Cara untuk mencapai solusi lain adalah dengan mengubah urutan di mana setiap satu
dari variabel saya masuk ke solusi dasar, mari kita ingat bahwa prosesnya adalah
ditentukan secara acak karena kesetaraan di Cj - Zj dari tabel awal. Di sini mereka
kami mempersembahkan salah satu cara untuk mencapai solusi lainnya.
[Link]
Kita dapat mengamati bagaimana ada solusi optimal alternatif di mana
kombinasi variabel adalah berbeda dan ada konsumsi sumber daya yang lebih rendah,
mengingat bahwa fakta bahwa variabel "S1" ada dalam solusi optimal dengan
 koefisien "3" berarti ada keleluasaan sebesar 3 unit dari
sumber daya (potongan persegi panjang 8 pin).

X1=0 (Jumlah meja yang akan diproduksi = 0)

X2=7 (Jumlah kursi yang akan diproduksi = 7)
X3=6 (Jumlah tempat tidur yang akan diproduksi = 6)
X4=4 (Jumlah perpustakaan yang akan diproduksi = 4)
S1=3 (Jumlah potongan persegi panjang 8 pin yang tidak digunakan =3)

Dengan keuntungan sebesar: $ 340000

MASALAH MINIMISASI DENGAN

METODE SIMPLEX
Untuk menyelesaikan masalah minimisasi menggunakan algoritma simplex ada
dua prosedur yang digunakan secara teratur.

Yang pertama, yang menurut pendapat saya adalah yang paling dianjurkan, didasarkan pada suatu alat.
dapat diterapkan pada algoritma yang didasarkan pada logika matematis yang menentukan
Untuk setiap fungsi f(x), setiap titik yang meminimalkan f(x) akan memaksimalkan
juga a - f(x)". Oleh karena itu, prosedur yang harus diterapkan adalah mengalikan dengan
faktor negatif (-1) pada seluruh fungsi tujuan.

selanjutnya algoritma diselesaikan sebagai masalah maksimisasi.

Prosedur kedua, yang bertujuan untuk mempertahankan minimisasi

terdiri dari menerapkan kriteria keputusan yang telah kita skemakan dengan
anterioritas, dalam kasus variabel yang masuk, yang keluar dan kasus di
bahwa solusi optimal ditemukan. Di sini kami mengingat prosedur
sesuai dengan kriteria yang diberikan kasus "meminimalkan".

Meminimalkan
Variabel yang masuk Yang paling negatif dari (Cj - Zj)
Siendo 'b' los valores bajo la celda solución y 'a' el valor correspondiente a
Variabel yang keluar
persimpangan antara "b" dan variabel yang masuk. Yang paling positif dari "b/a".
Solusi Optimal Ketika semua (Cj - Zj) >= 0.

[Link]
industri/penyelidikan-operasional/metode-simplex/
2018

Metode Simplex

Metode Simplex yang diterbitkan oleh George Dantzig pada tahun 1947 terdiri dari algoritma iteratif yang
Secara berurutan melalui iterasi, mendekati solusi optimal dari masalah Pemrograman Linier dalam kasus
jika yang terakhir ini ada.

Implementasi komputasi pertama dari Metode Simplex adalah pada tahun 1952 untuk masalah dengan 71 variabel dan 48
persamaan. Penyelesaiannya memakan waktu 18 jam. Kemudian, pada tahun 1956, sebuah kode bernama RSLP1, diimplementasikan di sebuah IBM dengan
4Kb RAM, mendukung resolusi model dengan 255 pembatas.

Metode Simplex memanfaatkan sifat bahwa solusi optimal dari suatu masalah Pemrograman Linear
temukan di sebuah titik sudut atau batas dari domain titik yang memungkinkan (ini terakhir dalam kasus yang sangat khusus), oleh karena itu,
pencarian berurutan dari algoritma ini didasarkan pada evaluasi progresif dari simpul-simpul ini sampai menemukan yang optimal.
Perlu dicatat bahwa untuk menerapkan Metode Simplex pada model linier, model tersebut harus dalam format khusus
dikenal sebagai format standar yang akan kita definisikan di bawah ini.

BENTUK STANDARD DARI MODEL PEMPROGRAMAN LINIER

Mari kita pertimbangkan model Pemrograman Linear dalam bentuk standarnya, yang selanjutnya kita sebut:

Min c1x1 + c2x2 + ... + cnxn

sa a11x1 + a12x2 + ... + a1nxn = b1
a21x1 + a22x2 + ... + a2nxn = b2
... ... ...
am1x1 + am2x2 + ... + amnxn = bm
xi >= 0, i = 1, 2, ..., n m <= n y

Matricially written as:

Min cTx
s.a Ax = b
x >= 0

Tidak ada kehilangan umum dalam mengasumsikan bahwa model PL diberikan dalam bentuk standarnya:

CONTOH
P) Maks 9u + 2v + 5z
sa 4u + 3v + 6z <= 50
u + 2v - 3z >= 8
2u - 4v + z = 5
u,v >= 0
z e IR

Selalu mungkin membawa masalah maksimisasi menjadi masalah minimisasi. Jika f(x) adalah fungsi
objetivo untuk memaksimalkan yx* adalah solusi optimal f(x*) >= f(x), untuk semua x yang memungkinkan. -f(x*) <= - f(x),
untuk semua x yang dapat dilakukan. Akibatnya: x* juga merupakan minimum dari -f(x)
2. Setiap pembatasan tipe <= dapat diubah menjadi persamaan kesetaraan dengan menggunakan sebuah (variabel baru)
de holgurano negatif, dengan koefisien nol dalam fungsi objektif.
 3. Setiap kendala jenis >= dapat diubah menjadi persamaan kesetaraan menggunakan variabel (baru)
dari ekses negatif, dengan koefisien nol dalam fungsi objektif.
4. Selalu mungkin untuk menulis variabel bebas tanda sebagai selisih dari dua variabel tidak negatif.

Mengingat notasi berikut: u = x1, v = x2, z = x3 - x4, s1 = x5 (kelonggaran), s2 = x6 (kelebihan),

masalah P) dapat ditulis dalam bentuk yang setara sebagai:

Min - 9x1 - 2x2 - 5x3 + 5x4 + 0x5 + 0x6

sa: 4x1 + 3x2 + 6x3 - 6x4 + x5 = 50
x1 + 2x2 - 3x3 + 3x4 - x6 = 8
2x1 - 4x2 + x3 - x4 = 5
xi >= 0, i=1,2,3,4,5,6.

CONTOH

Menyelesaikan masalah Pemrograman Linier berikut menggunakan Metode Simpleks:

Maks 40*X1 + 60*X2

s.a. 2*X1 + 1*X2 <= 70
1*X1 + 1*X2 <= 40
1*X1 + 3*X2 <= 90
X1 >= 0

Untuk dapat menerapkan Metode Simplex, perlu membawa model ke format standarnya, untuk itu
kita mendefinisikan X3, X4, X5 >= 0 sebagai variabel slack masing-masing untuk pembatasan 1, 2, dan 3. Dengan cara ini
Tabela awal metode ditentukan sebagai berikut:

X1 X2 X3 X4 X5

2 1 1 0 0 70

1 1 0 1 0 40

1 3 0 0 1 90

-40 -60 0 0 0 0

Dalam situasi ini, variabel slack mendefinisikan solusi dasar yang layak awal, kondisi yang diperlukan untuk
aplikasi metode. Kemudian, biaya yang dikurangi untuk variabel non dasar (X1 dan X2 di tabel
inicial) dan dipilih sebagai variabel yang masuk ke basis yang memiliki biaya tereduksi "paling negatif". Dalam ini
kasus,X2.

Kemudian, untuk memilih variabel dasar mana yang akan ditinggalkan dari basis, kita harus mencari kuotien minimum antara sisi kanan dan
koefisien yang terkait dengan variabel masuk di setiap baris (untuk koefisien > 0 yang ditandai dengan merah di
tabel sebelumnya). Minimum dicapai di Min {70/1, 40/1, 90/3} =30 yang terkait dengan baris ketiga, yang sesuai dengan
variabel dasar actualX5, sebagai konsekuensinya, X5 meninggalkan basis. Pada posisi di mana kuotien minimum dicapai.
Kita akan menyebutnya "Pivote" (ditandai dengan merah) yang akan membantu kita melakukan operasi baris yang sesuai, mencapai
tabel berikut setelah satu iterasi:

X1 X2 X3 X4 X5
 5/3 0 1 0 -1/3 40

2/3 0 0 1 -1/3 10

1/3 1 0 0 1/3 30

-20 0 0 0 20 1800

Nilai fungsi tujuan setelah sebuah iterasi telah berubah dari 0 menjadi 1.800. Disarankan kepada pembaca untuk melakukan sebuah
representasi grafik dari masalah dan perhatikan bagaimana solusi yang layak dari metode tersebut sesuai dengan
titik sudut hapus domain de titik dapat dilaksanakan.

Tabel saat ini tidak sesuai dengan solusi optimal dari masalah P) karena ada satu variabel non dasar dengan
biaya negatif yang berkurang, jadi X1 masuk ke basis. Selanjutnya, melalui kriteria kuotien minimum
kami menghitung variabel yang harus meninggalkan basis: Min {40/(5/3), 10/(2/3), 30/(1/3)} = 15, terkait dengan baris 2 (variabel
básica aktual X4), oleh karena itu X4 meninggalkan basis. Setelah memperoleh yang sebelumnya, diterapkan iterasi metode:

X1 X2 X3 X4 X5

0 0 1 -5/2 1/2 15

1 0 0 3/2 -1/2 15

0 1 0 -1/2 1/2 25

0 0 0 30 10 2100

Akhirnya solusi optimal dari masalah P) dicapai dan diperiksa bahwa biaya yang dikurangi terkait dengan
variabel tidak dasar (X4 dan X5 lebih besar atau sama dengan nol). Perhatikan bahwa adanya biaya tereduksi sama dengan
nol untuk variabel non dasar pada tahap ini mendefinisikan masalah dengan 'solusi tak terbatas'.

Solusi yang dicapai adalah X1* = 15, X2* = 25 dengan V(P*) = 2.100. Selain itu, biaya yang dikurangi terkait
variabel non-basis mendefinisikan harga bayangan yang terkait dengan batasan 1, 2, dan 3, masing-masing, yang mana adalah
setara dengan perolehan harga bayangan melalui metode grafis. Kami akan meninggalkannya untuk selanjutnya
presentasi, cara menghitung interval variasi untuk sisi kanan yang memungkinkan validitas harga
bayangan, menggunakan tabel akhir Metode Simplex.

METODE SIMPLEX 2 FASE

Strategi ini digunakan ketika solusi dasar yang layak awalnya tidak segera tersedia dalam variabel asli.
modelo.

FASE 1: Dikatakan sebagai masalah tambahan yang dihasilkan dari menambahkan begitu banyak variabel tambahan ke dalam pembatasan
masalah, cara untuk mendapatkan solusi dasar yang layak. Menyelesaikan masalah dengan Simplex yang mempertimbangkan sebagai
fungsi tujuan penjumlahan variabel tambahan. Jika nilai optimal adalah nol, lanjutkan ke Fase II, jika tidak,
tidak ada solusi yang layak.

FASE 2: Menyelesaikan masalah asli dengan metode Simplex berdasarkan solusi dasar yang layak yang ditemukan di Fase I.
P) Maks 2X1 + X2
sa 10X1 + 10X2 <= 9
10X1 + 5X2 >= 1
X1, X2 >= 0

X3 harus ditambahkan sebagai variabel slack untuk batasan 1, X4 sebagai variabel surplus untuk batasan 2, dan X5
variabel tambahan untuk dapat memulai Fase 1. (Perhatikan bahwa hanya menambahkan X3 sebagai variabel slack ke
pembatasan 1 dan X4 sebagai variabel kelebihan pada pembatasan kedua tidak mendapatkan solusi dasar yang layak awal,
secara khusus X4<0).

F1) Min X5
sa ...............10X1 + 10X2 + X3 = 9
10X1 + 5X2 - X4 + X5 = 1
X1, X2, X3, X4, X5 >= 0

Tabel awal yang terkait dengan Fase I ditentukan sebagai berikut:

X1 X2 X3 X4 X5

10 10 1 0 0 9

10 5 0 -1 1 1

0 0 0 0 1 0

Kemudian, biaya tereduksi dari X5 harus dibuat 0, menghasilkan tabel awal berikut untuk menggunakan Simplex:

X1 X2 X3 X4 X5

10 10 1 0 0 9

10 5 0 -1 1 1

-10 -5 0 1 0 -1

X1 dipilih sebagai variabel yang masuk ke basis karena memiliki biaya yang lebih negatif. Selanjutnya, melalui
kriteria kuota minimum memilih variabel yang keluar dari basis: Min {9/10; 1/10} = 1/10, X5 keluar dari
base

X1 X2 X3 X4 X5

0 5 1 1 -1 8

1 1/2 0 -1/10 1/10 1/10

 0 0 0 0 1 0

Solusi optimal dari Fase I diperoleh, dengan nilai optimal nol. Kemudian kita memulai Fase II dari metode tersebut.
mengambil X1 dan X3 sebagai variabel dasar awal.

FASE 2: Menyelesaikan masalah asli dengan metode Simplex berdasarkan solusi dasar yang layak awal yang ditemukan di Fase I.

X1 X2 X3 X4

0 5 1 1 8

1 1/2 0 -1/10 1/10

-2 -1 0 0 0

Kami menghilangkan biaya yang disebabkan oleh variabel dasar yang rendah:

X1 X2 X3 X4

0 5 1 1 8

1 1/2 0 -1/10 1/10

0 0 0 -1/5 1/5

X4 memasuki basis. Berdasarkan kriteria kuotien minimum, pivot terletak di baris 1, sehingga X3 keluar dari basis.
dasar

X1 X2 X3 X4

0 5 1 1 8

1 1 1/10 0 9/10

0 1 1/5 0 9/5

Di mana solusi optimal adalah: X1=9/10 X2=0 Dengan nilai optimal V(P) = 9/5.

Apakah Anda perlu lulus ujian Anda?

 Pemrograman Linier dan Anda tidak memiliki latihan
Diselesaikan?...
Unduh HARI INI Buku Catatan Pemrograman Linear!

Selesaikan masalah pemrograman linier Anda di sini menggunakan metode simplex

Aplikasi berikut memungkinkan untuk menyelesaikan model Pemrograman Linier menggunakan Metode Simplex. Mari kita pertimbangkan
salah satu contoh di bagian ini untuk melihat penggunaannya. Perhatikan bahwa tidak perlu menambahkan batasan tidak
negativitas. Dari sini diperoleh solusi optimal, nilai optimal dan masing-masing tabel dari Metode Simplex. Untuk
visualisasi tabel yang lebih baik disarankan untuk memilih mode "Fraksi".

Tulis masalah linier Anda di bawah. (Pilih "Contoh" untuk melihat bagaimana cara kerjanya)
 Solusi:
SolusiOptimalakanmunculdisini

6
Pembulatan angka signifikan
Desimal
Porsi
Mode: Entero

Tabel-tabel Metode Simplex akan munculDI SINI.

Aplikasi yang digunakan dengan izin dari ZweigMedia Inc. Hak cipta milikZweigMedia.

URL tidak dapat diterjemahkan.

Dualitas dalam Pemrograman Linier
Mari kita pertimbangkan kembali contoh yang digunakan untuk memperkenalkantutorial Solver:

Misalkan kita ingin mengetahui batas atas dari nilai optimal masalah ini tanpa
kebutuhan untuk menyelesaikan masalah tersebut. Misalnya, jika kita mengalikan pembatasan 3 dengan 200
kami mendapatkan: 200X + 200Y + 200Z <= 10.000. Jelas sisi kiri dari batasan ini
amplificada adalah lebih besar atau sama dengan ekspresi yang menentukan fungsi tujuan, oleh karena itu kita bisa
menyatakan bahwa nilai optimal dari masalah ini adalah kurang dari atau sama dengan 10.000 (V(P)<=10.000). Oleh karena itu

diperkirakan dapat mencari kombinasi lain untuk menentukan batas atas yang lebih baik
yang digunakan sebagai contoh.

Dalam hal ini jika kita mempertimbangkan A, B, dan C sebagai pengali yang terkait dengan masing-masing dari
pembatasan, cara untuk menemukan batas atas terbaik untuk masalah asli (yang
akan kita sebut Primal) diperoleh dengan menyelesaikan masalah berikut
denominasiGanda

Masalah ini dapat diselesaikan melaluimetode simplex dualbagaimana dijelaskan secara rinci
di bagian tersebut. Dengan cara ini diperoleh solusi optimal berikut: A=8, B=10, C=60,
dengan nilai optimal 6.620. Jika kita mengalikan batasan dari masalah dual ini dengan ini
pengganda kami mencapai batas atas terbaik:

8(15X + 7,5Y + 5Z) + 10(2X + 3Y + 2Z) + 60(X + Y + Z) <= 8*315 + 10*110 + 60*50

200X + 150Y + 120Z <= 6.620

Dapat juga diverifikasi bahwa harga bayangan dari batasan yang bersangkutan
masalah primal (lihat laporan sensitivitas di bagianpenyelesai excel) bercorrespondensi dengan
variabel dual optimal atau solusi optimal dari masalah dual, dengan nilai optimal setara.

Secara umumhubungan dualitasdapat diringkas dalam tabel berikut:

Teorema Dualitas
Dualitas dalam pemrograman linier memberikan hasil teoretis menarik yang membenarkan nya
digunakan sebagai alat alternatif dan pelengkap untuk resolusi.

TEOREMA DUALITAS LEMAH: Secara umum, nilai dari setiap solusi yang layak ...
masalah minimisasi, memberikan batas atas dari nilai optimal dari masalah
maksimisasi. Secara analogis, nilai fungsi tujuan dari setiap solusi layak dari
masalah pemaksimalan adalah batas bawah dari nilai optimal masalah peminimalan.

TEOREMA DUALITAS KERAS:Dalam optimum, nilai fungsi tujuan dari masalah

primal akan sama dengan nilai fungsi tujuan dari masalah dual yang dievaluasi pada solusi dual
Optimal. Jika masalah primal tidak terbatas, maka dual tidak dapat dilakukan. Sebaliknya jika
masalah primal tidak layak, maka dual tidak terbatas.

TEOREMA KELEBIHAN KOMPLEMENTER:Unvariabel dalam primal terkait dengan sebuah

pembatasan di dual (dan sebaliknya). Dalam hal ini, jika di primal ada variabel non dasar
(nilai sama dengan nol), dalam dual, pembatas yang terkait tidak aktif, yaitu, tidak terpenuhi di
kesetaraan. Demikian pula, jika variabelnya dasar dalam primal, pembatas yang terkait dalam dual
dilakukan secara setara. Hasil teoretis ini berguna setiap kali menyederhanakan cara untuk mendapatkan
solusi optimal mengingat bahwa dalam masalah linier solusi optimal (jika ada)
ini berada di suatu sudut, ini berarti menyelesaikan sistem persamaan (dengan batasan)
kesetaraan).

[Link]
CIRI-CIRI METODE SIMPLEX

Ini berlaku untuk masalah pemrograman linier

multidimensi.

Ini didasarkan pada aljabar matriks dan proses

eliminasi Gauss-Jordan. Ini adalah suatu proses dari
pencarian yang menjadi sangat efisien
untuk menyelesaikan masalah yang sangat besar.

Saat ini metode simplex dapat diterapkan dengan

efisiensi terhadap keragaman paket perangkat lunak yang
mempermudah proses perhitungan.
 METODE SIMPLEX

Metode Simplex adalah prosedur umum untuk

menyelesaikan masalah pemrograman linier.
Dikembangkan oleh George Dantzig pada tahun 1947, ini
diperiksa efisiensinya yang luar biasa, dan digunakan di
cara rutin untuk menyelesaikan masalah besar
di komputer aktual. Juga digunakan
ekstensi dan variasi dari metode Simplex untuk
melakukan analisis pos-optimal (yang mencakup analisis dari
sensitivitas) terhadap model.

Metode Simplex adalah prosedur aljabar, Tanpa

embargo, sus conceptos fundamentales son
geometris, sehingga pemahaman tentang ini
konsep geometris memberi kita kekuatan
intuisi tentang bagaimana metode Simplex beroperasi dan
mengapa itu sangat efisien.

Metode ini digunakan dengan proses interaktif, yaitu bahwa

sama digunakan secara berturut-turut rutin dasar yang sama untuk perhitungan, itu

yang menghasilkan serangkaian solusi berturut-turut sampai

yang ditemukan yang terbaik. Sebuah karakteristik dasar dari
metode Simplex adalah bahwa solusi terakhir menghasilkan sebuah
kontribusi yang sangat besar atau lebih besar dari solusi sebelumnya
dalam masalah maksimisasi, apa yang diberikan oleh
kepastian mencapai jawaban yang optimal akhirnya.

UNTUK APA METODE SIMPLEX DIGUNAKAN?

Metode Simplex membantu kita untuk menyelesaikan masalah

di mana kita harus mengoptimalkan sumber daya kita dari
cara yang lebih efisien. Digunakan untuk
mengatasi masalah pemrograman linier di mana
campur tangan tiga o lebih variabel.

PENTINGNYA METODE SIMPLEX

Metode simplex memungkinkan untuk menemukan secara

efisien solusi optimal antara titik ekstrim
dari masalah pemrograman linier. Kebajikan besar
Kelebihan metode simplex adalah kesederhanaannya, metode yang sangat

praktis, karena hanya bekerja dengan koefisien dari

fungsi tujuan dan dari batasan.

Ini sangat penting di bidang bisnis karena itu

digunakan untuk mendapatkan solusi untuk masalah dari
perusahaan dalam hal inventaris, keuntungan, dan kerugian.
Metode ini memungkinkan untuk melihat berapa banyak yang harus dijual,
berapa banyak yang harus diproduksi atau berapa banyak yang harus dibeli

sesuai dengan keadaan agar perusahaan memperoleh

keuntungan optimal dan cukup untuk bersaing di
pasar.

Berdasarkan pentingnya ini, metode simplex telah

memiliki berbagai aplikasi di industri
terutama di bidang transportasi, di bagian
inventaris dan dalam dunia bisnis secara umum.

KEUNGGULAN DEL METODE SIMPLEX

 1) Ini adalah metode heuristik. Ini didasarkan pada
pertimbangan geometris dan tidak memerlukan
penggunaan turunan dari fungsi tujuan.
2) Ini sangat efisien bahkan untuk menyetel
sejumlah besar parameter.
3) Dapat digunakan dengan fungsi tujuan yang sangat
berliku karena pada iterasi awal
carilah yang minimum secara lebih luas dan hindari terjatuh
di minimum lokal dengan mudah.
4) Mudah diimplementasikan dan digunakan, namun demikian
memiliki efikasi tinggi.

KEKURANGAN METODE SIMPLEX

Konvergen lebih lambat daripada metode lain, karena

memerlukan lebih nomor de iterasi.

Dalam hal fungsi memiliki semua variabelnya

dasar positif, dan selain itu pembatasannya adalah
ketidaksetaraan "≤", saat melakukan perubahan tersisa
negatif dan di baris nilai fungsi tujuan se
masih positif, sehingga syaratnya terpenuhi
parada, dan secara default nilai optimal yang akan diperoleh
es 0.
VARIABEL KELONGGARAN DAN KELEBIHAN

Terapkan untuk pembatasan jenis (≥ y ≤), di mana

sisi kanan ketidaksetaraan mewakili batas
tentang ketersediaan suatu sumber daya dan sisi
izquierdo mewakili penggunaan sumber daya itu
terbatas yang ditetapkan oleh variabel model. Ini
artinya suatu celah mewakili jumlah
tersedia dari sumber yang melebihi penggunaan yang
memberi. Dalam konversi ketidaksetaraan jenis ini,
tambahkan variabel penyesuaian (Si) untuk mengubahnya menjadi
kesetaraan. Misalnya, kami memiliki batasan berikut:
3X1 + 2X2≥6, su equivalente seria, 3X1 + 2X2 + S1 =
6.

VARIABLE ARTIFICIAL / METODE 'M'

Variabel buatan adalah trik matematis untuk

mengubah pertidaksamaan ">=" menjadi persamaan, atau ketika
terjadi kesamaan dalam masalah asli, yang
karakteristik utama dari variabel-variabel ini adalah bahwa tidak
harus menjadi bagian dari solusi, mengingat tidak
perwakilan sumber daya. Tujuan mendasar dari ini
variabel adalah pembentukan matriks identitas.

Variabel ini dilambangkan dengan huruf "A", selalu.

sejumlah pembatasan, koefisiennya adalah M (oleh
ini disebut Metode M besar, di mana M
menandakan angka yang terlalu besar sangat sedikit
atraktif untuk fungsi tujuan), dan tanda di
fungsi tujuan bertentangan dengan makna itu sendiri,
artinya, dalam masalah Maksimalisasi tanda nya adalah
menos (-) dan dalam masalah Minimisasi tanda nya adalah
+), kami mengulang dengan tujuan agar nilainya di
solusi laut nol (0).

Secara umum, metode Símplex terdiri dari langkah-langkah

berikut:
Menentukan solusi dasar yang layak
awal.
Tentukan sebuah variabel input menggunakan
kondisi kelayakan. Algoritme tersebut
berhenti ketika tidak ada lagi variabel dari
masuk.
Pilih variabel keluaran
menggunakan kondisi kelayakan.
Menentukan solusi dasar yang baru
dapat dilakukan dengan menerapkan perhitungan yang tepat pada
melalui metodologi Gauss-Jordan.

URL not translatable