Mari kita pertimbangkan metode simpleks untuk memecahkan masalah pemrograman linier (LP). Hal ini didasarkan pada transisi dari satu rencana referensi ke rencana referensi lainnya, di mana nilai fungsi tujuan meningkat.

Algoritma metode simpleks adalah sebagai berikut:

1. Kami mengubah masalah asli ke dalam bentuk kanonik dengan memasukkan variabel tambahan. Untuk pertidaksamaan berbentuk ≤, dimasukkan variabel tambahan dengan tanda (+), tetapi jika berbentuk ≥, maka dengan tanda (-). Variabel tambahan dimasukkan ke dalam fungsi tujuan dengan tanda-tanda yang sesuai dengan koefisien yang sama 0 , Karena fungsi target tidak boleh mengubah makna ekonominya.
2. Vektor ditulis hal dari koefisien variabel dan kolom suku bebas. Tindakan ini menentukan jumlah vektor satuan. Aturannya adalah jumlah vektor satuan harus sebanyak jumlah ketidaksetaraan dalam sistem kendala.
3. Setelah itu, sumber data dimasukkan ke dalam tabel simpleks. Vektor satuan dimasukkan ke dalam basis, dan dengan mengeluarkannya dari basis, solusi optimal ditemukan. Koefisien fungsi tujuan ditulis dengan tanda berlawanan.
4. Tanda optimalitas suatu permasalahan LP adalah solusinya optimal jika masuk F– pada baris tersebut semua koefisiennya positif. Aturan untuk menemukan kolom pengaktifan - dilihat F– sebuah string dan di antara elemen negatifnya, elemen terkecil dipilih. Vektor hal isinya menjadi permisif. Aturan untuk memilih elemen penyelesaian - rasio elemen positif kolom penyelesaian dengan elemen vektor dikompilasi hal 0 dan bilangan yang memberikan rasio terkecil menjadi elemen penyelesaian yang akan digunakan untuk menghitung ulang tabel simpleks. Garis yang berisi elemen ini disebut garis aktifkan. Jika tidak ada unsur positif pada kolom penyelesaian, maka permasalahan tidak ada penyelesaiannya. Setelah menentukan elemen penyelesaian, mereka melanjutkan ke perhitungan ulang tabel simpleks baru.
5. Aturan pengisian tabel simpleks baru. Unit ditempatkan di tempat elemen penyelesaian, dan elemen lainnya dianggap sama 0 . Vektor penyelesaian ditambahkan ke basis, dari mana vektor nol yang bersesuaian dikecualikan, dan vektor basis lainnya ditulis tanpa perubahan. Elemen garis resolusi dibagi dengan elemen resolusi, dan elemen sisanya dihitung ulang menurut aturan persegi panjang.
6. Hal ini dilakukan sampai F– semua elemen string tidak akan menjadi positif.

Mari kita pertimbangkan untuk memecahkan masalah menggunakan algoritma yang dibahas di atas.
Diberikan:

Kami membawa masalah ini ke bentuk kanonik:

Kami menyusun vektor:

Isilah tabel simpleksnya:

:
Mari kita hitung ulang elemen pertama dari vektor hal 0, yang mana kita membuat persegi panjang berisi angka: dan kita mendapatkan: .

Kami melakukan perhitungan serupa untuk semua elemen tabel simpleks lainnya:

Dalam rencana yang diterima F– garis mengandung satu elemen negatif – (-5/3), vektor hal 1. Di dalam kolomnya terdapat satu elemen positif, yang akan menjadi elemen pendukung. Mari kita hitung ulang tabel mengenai elemen ini:

Tidak ada unsur negatif di dalamnya F– garis artinya ditemukan rencana optimal:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Pemrograman linier, M: Nauka, 1998,
• Ventzel E.S. Riset Operasi, M: Radio Soviet, 2001,
• Kuznetsov Yu.N., Kuzubov V.I., Voloshenko A.B. Pemrograman matematika, M: Sekolah Tinggi, 1986.

Solusi Pemrograman Linier Kustom

Anda dapat memesan tugas apa pun dalam disiplin ini di situs web kami. Anda dapat melampirkan file dan menentukan tenggat waktu di

Langkah 0. Tahap persiapan.

Masalah LP kita reduksi menjadi bentuk khusus (15).

Langkah 1. Kompilasi tabel simpleks, sesuai dengan bentuk khusus:

Perhatikan bahwa tabel ini sesuai dengan solusi dasar yang dapat diterima
masalah (15). Nilai fungsi tujuan pada solusi ini

Langkah 2. Pemeriksaan optimalitas

Jika diantara elemen baris indeks terdapat tabel simpleks
tidak ada satu pun unsur positifnya
, solusi optimal untuk masalah LP ditemukan :. Algoritme berakhir.

Langkah 3. Pemeriksaan ketidakpastian

Jika di antara
ada unsur positifnya
, dan di kolom yang sesuai
tidak ada satu pun elemen positif
, maka fungsi tujuan L tidak dibatasi dari bawah pada himpunan yang diizinkan. Dalam hal ini, tidak ada solusi optimal. Algoritme berakhir.

Langkah 4. Memilih Kolom Utama Q

Di antara elemen-elemennya
pilih elemen positif maksimum
.Kolom ini kami nyatakan sebagai kolom terdepan (permisif).

Langkah 5. Pemilihan garis memimpin P

Di antara elemen positif dari kolom
temukan elemennya
, yang persamaannya berlaku

.

Rangkaian P Kami nyatakan memimpin (mengizinkan). Elemen
Kita nyatakan sebagai pemimpin (mengizinkan).

Langkah 6. Konversi Tabel Simpleks

Kami membuat tabel simpleks baru di mana:

a) sebagai pengganti variabel dasar tuliskan , bukan variabel non-dasar tuliskan ;

b) elemen terdepan diganti dengan nilai kebalikannya
;

c) semua elemen kolom terdepan (kecuali
) kalikan dengan
;

d) semua elemen garis terdepan (kecuali
) kalikan dengan ;

e) elemen tabel simpleks yang tersisa ditransformasikan menurut skema “persegi panjang” berikut.

Produk tiga faktor dikurangkan dari elemen:

yang pertama adalah elemen yang sesuai dari kolom utama;

yang kedua adalah elemen yang sesuai dari garis terdepan;

yang ketiga adalah kebalikan dari elemen utama
.

Elemen yang ditransformasikan dan tiga faktor yang bersesuaian dengannya justru merupakan simpul dari “persegi panjang”.

Langkah 7 Peralihan ke iterasi berikutnya dilakukan dengan kembali ke langkah 2.

2.3. Algoritma metode simpleks untuk permasalahan maksimal

Algoritma metode simpleks untuk permasalahan maksimum berbeda dengan algoritma untuk permasalahan minimum hanya pada tanda garis indeks koefisien pada fungsi tujuan.
, yaitu:

Pada langkah 2:
:

Pada langkah 3
. Fungsi tujuan tidak dibatasi dari atas pada himpunan yang diizinkan.

Pada langkah 4:
.

2.4. Contoh penyelesaian suatu masalah dengan menggunakan metode simpleks

Selesaikan masalah yang tertulis pada formulir (15).

Mari buat tabel simpleks:

Karena koefisien garis fungsi tujuan tidak negatif, solusi basis awal tidak optimal. Nilai fungsi tujuan untuk basis ini L=0.

Pilih kolom terdepan - ini adalah kolom yang sesuai dengan variabel .

Pilih garis terdepan. Untuk melakukan ini kita temukan
. Oleh karena itu, garis terdepan berhubungan dengan variabel .

Kami mengubah tabel simpleks dengan memasukkan variabel ke dalam basis dan mengeluarkan variabel dari dasar. Kami mendapatkan tabel:

Satu iterasi metode telah selesai. Mari beralih ke iterasi baru. Tabel yang dihasilkan kurang optimal. Solusi dasar yang sesuai dengan tabel memiliki bentuk . Nilai fungsi tujuan atas dasar ini aku= -2.

Kolom terdepan di sini adalah kolom yang sesuai dengan variabel . Garis terdepan – garis yang sesuai dengan variabel . Setelah melakukan transformasi, diperoleh tabel simpleks:

Iterasi lainnya selesai. Mari beralih ke iterasi baru.

Garis fungsi tujuan tidak mengandung nilai positif, yang berarti solusi dasar yang sesuai adalah optimal, dan algoritma dihentikan.

Metode ini adalah metode enumerasi yang disengaja dari solusi referensi untuk masalah program linier. Hal ini memungkinkan, dalam sejumlah langkah yang terbatas, untuk menemukan solusi optimal atau menetapkan bahwa tidak ada solusi optimal.

1. Tunjukkan metode untuk menemukan solusi referensi optimal
2. Tunjukkan metode transisi dari satu solusi referensi ke solusi referensi lainnya, di mana nilai fungsi tujuan akan mendekati nilai optimal, yaitu. menunjukkan cara untuk meningkatkan solusi referensi
3. Tetapkan kriteria yang memungkinkan Anda untuk segera berhenti mencari solusi dukungan pada solusi optimal atau menarik kesimpulan tentang tidak adanya solusi optimal.

Algoritma metode simpleks untuk menyelesaikan masalah program linier

1. Bawalah masalah ke bentuk kanonik
2. Menemukan solusi dukungan awal dengan “basis unit” (jika tidak ada solusi dukungan, maka masalah tidak memiliki solusi karena ketidakcocokan sistem kendala)
3. Hitung perkiraan dekomposisi vektor berdasarkan solusi referensi dan isi tabel metode simpleks
4. Jika kriteria keunikan solusi optimal terpenuhi, maka penyelesaian masalah berakhir
5. Jika syarat adanya himpunan solusi optimal terpenuhi, maka semua solusi optimal dicari dengan enumerasi sederhana

Contoh penyelesaian masalah dengan menggunakan metode simpleks

Selesaikan masalah tersebut dengan menggunakan metode simpleks:

Larutan:

Kami membawa masalah ini ke bentuk kanonik.

Untuk melakukannya, kita masukkan variabel tambahan x 6 dengan koefisien +1 di sisi kiri batasan pertidaksamaan pertama. Variabel x 6 termasuk dalam fungsi tujuan dengan koefisien nol (yaitu tidak termasuk).

Kami mendapatkan:

Kami menemukan solusi dukungan awal. Untuk melakukan ini, kita menyamakan variabel bebas (belum terselesaikan) dengan nol x1 = x2 = x3 = 0.

Kami mengerti solusi referensi X1 = (0,0,0,24,30,6) dengan basis satuan B1 = (A4, A5, A6).

Kami menghitung perkiraan dekomposisi vektor kondisi berdasarkan solusi referensi sesuai dengan rumus:

Δ k = C b X k - ck

• C b = (c 1, c 2, ..., c m) - vektor koefisien fungsi tujuan untuk variabel dasar
• X k = (x 1k, x 2k, ..., x mk) - vektor muai dari vektor yang bersesuaian A k menurut basis solusi referensi
• C k adalah koefisien fungsi tujuan untuk variabel x k.

Estimasi vektor-vektor yang termasuk dalam basis selalu sama dengan nol. Solusi referensi, koefisien muai dan estimasi perluasan vektor kondisi berdasarkan solusi referensi dituliskan tabel simpleks:

Di bagian atas tabel, untuk memudahkan penghitungan estimasi, ditulis koefisien fungsi tujuan. Pada kolom pertama "B" ditulis vektor-vektor yang termasuk dalam basis solusi referensi. Urutan penulisan vektor-vektor ini sesuai dengan jumlah hal-hal yang tidak diketahui yang diperbolehkan dalam persamaan kendala. Pada kolom kedua tabel "C b" koefisien fungsi tujuan untuk variabel dasar ditulis dengan urutan yang sama. Dengan susunan koefisien fungsi tujuan yang benar pada kolom "C b", estimasi vektor satuan yang termasuk dalam basis selalu sama dengan nol.

Pada baris terakhir tabel perkiraan k pada kolom “A 0” dituliskan nilai fungsi tujuan pada solusi acuan Z(X 1).

Solusi dukungan awal tidak optimal, karena pada soal maksimum estimasi Δ 1 = -2, Δ 3 = -9 untuk vektor A 1 dan A 3 adalah negatif.

Menurut teorema peningkatan solusi dukungan, jika dalam suatu masalah maksimum setidaknya satu vektor memiliki estimasi negatif, maka Anda dapat menemukan solusi dukungan baru yang nilai fungsi tujuannya akan lebih besar.

Mari kita tentukan vektor mana yang akan menghasilkan kenaikan fungsi tujuan yang lebih besar.

Kenaikan fungsi tujuan dicari dengan rumus: .

Kami menghitung nilai parameter θ 01 untuk kolom pertama dan ketiga menggunakan rumus:

Kita memperoleh θ 01 = 6 untuk l = 1, θ 03 = 3 untuk l = 1 (Tabel 26.1).

Kita mencari pertambahan fungsi tujuan dengan memasukkan vektor pertama Z 1 = - 6*(- 2) = 12 ke dalam basis, dan vektor ketiga Z 3 = - 3*(- 9) = 27.

Akibatnya, untuk pendekatan yang lebih cepat terhadap solusi optimal, perlu untuk memasukkan vektor A3 ke dalam basis solusi referensi alih-alih vektor pertama dari basis A6, karena parameter minimum θ 03 dicapai pada baris pertama ( aku = 1).

Kita melakukan transformasi Jordan dengan elemen X13 = 2, kita memperoleh solusi referensi kedua X2 = (0,0,3,21,42,0) dengan basis B2 = (A3, A4, A5). (Tabel 26.2)

Solusi ini tidak optimal, karena vektor A2 mempunyai estimasi negatif Δ2 = - 6. Untuk memperbaiki solusi, perlu memasukkan vektor A2 ke dalam basis solusi referensi.

Kita menentukan banyaknya vektor yang diturunkan dari basis. Untuk melakukan ini, kita menghitung parameter θ 02 untuk kolom kedua, sama dengan 7 untuk l = 2. Oleh karena itu, kita memperoleh vektor basis kedua A4 dari basis. Kita melakukan transformasi Jordan dengan elemen x 22 = 3, kita memperoleh solusi referensi ketiga X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabel 26.3).

Solusi ini adalah satu-satunya solusi optimal, karena untuk semua vektor yang tidak termasuk dalam basis, perkiraannya positif

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Menjawab: maks Z(X) = 201 pada X = (0,7,10,0,63).

Metode pemrograman linier dalam analisis ekonomi

Metode pemrograman linier memungkinkan untuk membenarkan solusi ekonomi yang paling optimal dalam kondisi pembatasan yang ketat terkait dengan sumber daya yang digunakan dalam produksi (aset tetap, bahan, sumber daya tenaga kerja). Penggunaan metode ini dalam analisis ekonomi memungkinkan untuk memecahkan masalah-masalah yang terutama berkaitan dengan perencanaan kegiatan suatu organisasi. Metode ini membantu menentukan jumlah output produk yang optimal, serta arah penggunaan sumber daya produksi yang paling efektif yang tersedia bagi organisasi.

Dengan menggunakan metode ini, apa yang disebut masalah ekstrem diselesaikan, yang terdiri dari pencarian nilai ekstrem, yaitu fungsi maksimum dan minimum dari besaran variabel.

Periode ini didasarkan pada penyelesaian sistem persamaan linier dalam kasus di mana fenomena ekonomi yang dianalisis dihubungkan oleh ketergantungan linier yang sangat fungsional. Metode linear programming digunakan untuk menganalisis variabel dengan adanya faktor pembatas tertentu.

Sangat umum untuk menyelesaikan apa yang disebut masalah transportasi dengan menggunakan metode pemrograman linier. Isi tugas ini adalah meminimalkan biaya-biaya yang timbul sehubungan dengan pengoperasian kendaraan dengan batasan yang ada mengenai jumlah kendaraan, daya dukungnya, lama pengoperasiannya, jika diperlukan untuk melayani pelanggan sebanyak-banyaknya.

Selain itu, metode ini banyak digunakan dalam menyelesaikan masalah penjadwalan. Tugas ini terdiri dari pembagian waktu operasional untuk personel suatu organisasi tertentu yang paling dapat diterima baik bagi anggota personel tersebut maupun untuk klien organisasi.

Tugasnya adalah memaksimalkan jumlah klien yang dilayani dalam kondisi keterbatasan jumlah staf yang tersedia, serta dana waktu kerja.

Dengan demikian, metode program linier sangat umum digunakan dalam analisis penempatan dan penggunaan berbagai jenis sumber daya, serta dalam proses perencanaan dan peramalan kegiatan organisasi.

Namun demikian, pemrograman matematika juga dapat diterapkan pada fenomena ekonomi tersebut, yang hubungannya tidak linier. Untuk tujuan ini, metode pemrograman nonlinier, dinamis dan cembung dapat digunakan.

Pemrograman nonlinier bergantung pada sifat nonlinier dari fungsi tujuan atau batasannya, atau keduanya. Bentuk fungsi tujuan dan batasan pertidaksamaan pada kondisi tersebut bisa berbeda-beda.

Pemrograman nonlinier digunakan dalam analisis ekonomi, khususnya, ketika membangun hubungan antara indikator yang menyatakan efisiensi kegiatan suatu organisasi dan volume kegiatan ini, struktur biaya produksi, kondisi pasar, dll.

Pemrograman dinamis didasarkan pada pembuatan pohon keputusan. Setiap tingkatan pohon ini berfungsi sebagai tahapan untuk menentukan konsekuensi dari keputusan sebelumnya dan untuk menghilangkan pilihan-pilihan yang tidak efektif terhadap keputusan tersebut. Dengan demikian, pemrograman dinamis memiliki sifat multi-langkah dan multi-tahap. Jenis pemrograman ini digunakan dalam analisis ekonomi untuk menemukan pilihan optimal bagi perkembangan suatu organisasi baik saat ini maupun di masa depan.

Pemrograman cembung adalah salah satu jenis pemrograman nonlinier. Jenis pemrograman ini mengungkapkan sifat nonlinier dari hubungan antara hasil kegiatan organisasi dan biayanya. Pemrograman cembung (alias cekung) menganalisis fungsi tujuan cembung dan sistem batasan cembung (titik kelayakan). Pemrograman cembung digunakan dalam analisis kegiatan ekonomi untuk meminimalkan biaya, dan pemrograman cekung untuk memaksimalkan pendapatan di bawah batasan yang ada pada tindakan faktor-faktor yang mempengaruhi indikator yang dianalisis dengan cara yang berlawanan. Akibatnya, dengan jenis pemrograman yang dipertimbangkan, fungsi tujuan cembung diminimalkan, dan fungsi tujuan cekung dimaksimalkan.

Salah satu metode untuk memecahkan masalah optimasi ( biasanya dikaitkan dengan mencari minimum atau maksimum) pemrograman linier disebut . Metode simpleks mencakup seluruh kelompok algoritma dan metode untuk memecahkan masalah pemrograman linier. Salah satu metode ini, yang melibatkan pencatatan data awal dan penghitungan ulangnya dalam tabel khusus, disebut metode tabel simpleks.

Mari kita perhatikan algoritma metode tabel simpleks menggunakan contoh solusinya tugas produksi, yang intinya adalah menemukan rencana produksi yang menjamin keuntungan maksimal.

Masukkan data untuk soal metode simpleks

Perusahaan memproduksi 4 jenis produk, mengolahnya dalam 3 mesin.

Standar waktu (min./potong) untuk memproses produk pada mesin ditentukan oleh matriks A:

Dana waktu pengoperasian mesin (min.) ditentukan dalam matriks B:

Keuntungan dari penjualan setiap unit produk (RUB/buah) diberikan oleh matriks C:

Tujuan dari tugas produksi

Menyusun rencana produksi yang akan memaksimalkan keuntungan perusahaan.

Penyelesaian masalah tersebut menggunakan metode tabular simpleks

(1) Mari kita nyatakan dengan X1, X2, X3, X4 jumlah produk yang direncanakan untuk setiap jenis. Maka rencana yang diinginkan :( X1, X2, X3, X4)

(2) Mari kita tuliskan batasan rencana dalam bentuk sistem persamaan:

(3) Maka target keuntungannya adalah:

Artinya, keuntungan dari pemenuhan rencana produksi harus maksimal.

(4) Untuk menyelesaikan masalah ekstrem bersyarat yang timbul, kami mengganti sistem pertidaksamaan dengan sistem persamaan linier dengan memasukkan tambahan variabel non-negatif ke dalamnya ( X5, X6, X7).

(5) Mari kita terima yang berikut ini rencana referensi:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Ayo masukkan datanya ke dalam tabel simpleks:

Pada baris terakhir kita memasukkan koefisien fungsi tujuan dan nilainya sendiri dengan tanda berlawanan;

(7) Pilih di baris terakhir terbesar (modulo) adalah bilangan negatif.

Mari kita hitung b = N / Item_dari_kolom_yang_dipilih

Di antara nilai b yang dihitung kita pilih paling sedikit.

Perpotongan kolom dan baris yang dipilih akan memberi kita elemen penyelesaian. Kami mengubah basis menjadi variabel yang sesuai dengan elemen penyelesaian ( X5 hingga X1).

• Elemen penyelesaiannya sendiri berubah menjadi 1.
• Untuk elemen garis resolusi – a ij (*) = a ij / RE ( yaitu, kita membagi setiap elemen dengan nilai elemen penyelesaiannya dan memperoleh data baru).
• Untuk elemen kolom resolusi, elemen tersebut disetel ulang ke nol.
• Kami menghitung ulang elemen tabel yang tersisa menggunakan aturan persegi panjang.

a ij (*) = a ij – (A * B / KEMBALI)

Seperti yang Anda lihat, kami mengambil sel saat ini yang sedang dihitung ulang dan sel dengan elemen penyelesaian. Mereka membentuk sudut berlawanan dari persegi panjang. Selanjutnya, kita kalikan nilai dari sel di 2 sudut lain persegi panjang ini. Pekerjaan ini ( A * B) bagi dengan elemen penyelesaian ( ULANG). Dan kurangi dari sel saat ini yang sedang dihitung ulang ( sebuah ij) Apa yang terjadi. Kami mendapatkan nilai baru - sebuah ij (*).

(9) Periksa baris terakhir lagi ( C) pada adanya angka negatif. Jika tidak ada, rencana optimal telah ditemukan; kita lanjutkan ke tahap terakhir penyelesaian masalah. Jika ada maka perencanaannya belum optimal dan tabel simpleksnya perlu dihitung ulang lagi.

Karena kita kembali memiliki angka negatif di baris terakhir, kita memulai iterasi perhitungan yang baru.

(10) Karena tidak ada elemen negatif pada baris terakhir, artinya kami telah menemukan rencana produksi yang optimal! Yaitu: kami akan memproduksi produk-produk yang telah dipindahkan ke kolom “Basis” - X1 dan X2. Kita mengetahui keuntungan dari produksi setiap unit output ( matriks C). Tetap mengalikan volume produksi produk 1 dan 2 yang ditemukan dengan keuntungan per 1 buah, kita mendapatkan hasil akhir ( maksimum! ) keuntungan untuk rencana produksi tertentu.

MENJAWAB:

X1 = 32 buah., X2 = 20 buah., X3 = 0 buah., X4 = 0 buah.

P = 48 * 32 + 33 * 20 = 2.196 gosok.

Galyautdinov R.R.

© Menyalin materi hanya diperbolehkan jika ada hyperlink langsung ke

Pemrograman linier adalah teknik pemodelan matematika yang dirancang untuk mengoptimalkan penggunaan sumber daya yang terbatas. LP berhasil digunakan di bidang militer, industri, pertanian, industri transportasi, ekonomi, sistem kesehatan dan bahkan dalam ilmu sosial. Meluasnya penggunaan metode ini juga didukung oleh algoritma komputer yang sangat efisien yang mengimplementasikan metode ini. Algoritme optimasi untuk jenis model dan masalah riset operasi (OR) lain yang lebih kompleks, termasuk pemrograman bilangan bulat, nonlinier, dan stokastik, didasarkan pada algoritma pemrograman linier.

Masalah optimasi adalah masalah ekonomi dan matematika yang terdiri dari mencari nilai optimal (maksimum atau minimum) dari fungsi tujuan, dan nilai variabel harus berada dalam kisaran nilai tertentu yang dapat diterima.

Dalam bentuk yang paling umum, permasalahan program linier ditulis secara matematis sebagai berikut:

Di mana X = (x 1 , X 2 , ... , X N ) ; W– rentang nilai variabel yang diizinkan X 1 , X 2 , ... , X N ;f(x)– fungsi objektif.

Untuk menyelesaikan suatu masalah optimasi, cukup dicari solusi optimalnya, yaitu. menunjukkan itu dalam hal apapun.

Suatu permasalahan optimasi tidak akan terpecahkan jika tidak mempunyai solusi optimal. Secara khusus, masalah maksimalisasi tidak akan terpecahkan jika tujuan berfungsi f(x) tidak dibatasi dari atas pada himpunan yang diperbolehkan W.

Metode untuk menyelesaikan masalah optimasi bergantung pada jenis fungsi tujuan f(x), dan dari struktur himpunan yang diizinkan W. Jika fungsi target dalam soal adalah fungsi N variabel, maka metode penyelesaiannya disebut metode pemrograman matematika.

Ciri-ciri masalah program linier adalah sebagai berikut:

indeks optimalitas f(x) adalah fungsi linier dari elemen solusi X = (x 1 , X 2 , ... , X N ) ;

kondisi pembatas yang dikenakan pada kemungkinan penyelesaian berbentuk persamaan atau pertidaksamaan linier.

Masalah pemrograman linier disebut masalah riset operasi, yang model matematikanya berbentuk:

(2) (3)(4)(5)

Dalam hal ini, sistem persamaan linear (3) dan pertidaksamaan (4), (5), yang menentukan himpunan solusi yang dapat diterima untuk masalah tersebut W, ditelepon sistem pembatasan masalah pemrograman linier, dan fungsi linier f(x) ditelepon fungsi sasaran atau kriteria optimalitas .

Solusi yang sah adalah kumpulan angka ( rencana ) X = (X 1 , X 2 , ... , X N ) , memenuhi batasan masalah. Solusi optimal – ini adalah rencana di mana fungsi tujuan mengambil nilai maksimum (minimum).

Jika model matematika masalah program linier berbentuk:

kemudian mereka mengatakan bahwa masalahnya disajikan bentuk kanonik .

Setiap masalah program linier dapat direduksi menjadi masalah program linier dalam bentuk kanonik. Untuk melakukan ini, secara umum, Anda harus mampu mereduksi masalah maksimalisasi menjadi masalah minimalisasi; berpindah dari batasan ketimpangan ke batasan kesetaraan dan mengganti variabel yang tidak memenuhi kondisi non-negatif. Memaksimalkan suatu fungsi sama dengan meminimalkan fungsi yang sama yang diambil tandanya berlawanan, dan sebaliknya.

Aturan untuk membawa masalah program linier ke bentuk kanonik adalah sebagai berikut:

jika dalam soal awal perlu menentukan maksimum suatu fungsi linier, maka Anda harus mengubah tandanya dan mencari minimum dari fungsi tersebut;

jika sisi kanan dari pembatasan adalah negatif, maka pembatasan ini harus dikalikan dengan -1;

jika ada ketidaksetaraan di antara batasan-batasan tersebut, maka dengan memasukkan variabel non-negatif tambahan, variabel-variabel tersebut diubah menjadi kesetaraan;

jika beberapa variabel X J tidak memiliki batasan tanda, maka diganti (dalam fungsi tujuan dan semua batasan) dengan selisih antara dua variabel non-negatif baru: X 3 = x 3 + - X 3 - , Di mana X 3 + , X 3 - ≥ 0 .

Contoh 1. Mengurangi masalah program linier ke bentuk kanonik:

menit L = 2x 1 + x 2 - X 3 ; 2x 2 - X 3 ≤ 5; X 1 + x 2 - X 3 ≥ -1; 2x 1 - X 2 ≤ -3; X 1 ≤ 0; X 2 ≥ 0; X 3 ≥ 0.

Mari kita perkenalkan variabel leveling ke dalam setiap persamaan sistem kendala X 4 , X 5 , X 6 . Sistem akan ditulis dalam bentuk persamaan, dan pada persamaan pertama dan ketiga dari sistem kendala variabelnya X 4 , X 6 dimasukkan ke sisi kiri dengan tanda “+”, dan ke dalam persamaan kedua variabel X 5 dimasukkan dengan tanda "-".

2x 2 - X 3 + x 4 = 5; X 1 + x 2 - X 3 - X 5 = -1; 2x 1 - X 2 + x 6 = -3; X 4 ≥ 0; X 5 ≥ 0; X 6 ≥ 0.

Suku bebas dalam bentuk kanonik harus positif; untuk melakukannya, kalikan dua persamaan terakhir dengan -1:

2x 2 - X 3 + x 4 = 5; -X 1 - X 2 + x 3 + x 5 = 1; -2x 1 + x 2 - X 6 = 3.

Metode simpleks untuk menyelesaikan masalah program linier.

Algoritma metode simpleks mencari solusi optimal dengan mempertimbangkan sejumlah solusi dasar yang layak. Algoritma metode simpleks selalu dimulai dengan beberapa solusi basis layak dan kemudian mencoba mencari solusi basis layak lainnya yang “meningkatkan” nilai fungsi tujuan. Hal ini hanya mungkin terjadi jika peningkatan pada variabel nol (non-dasar) menyebabkan peningkatan nilai fungsi tujuan. Namun agar variabel non-basis menjadi positif, salah satu variabel dasar saat ini harus disetel ke nol, yaitu. ubah ke non-dasar. Hal ini diperlukan agar solusi baru dapat memuat dengan tepat M variabel dasar. Sesuai dengan terminologi metode simpleks, disebut variabel nol yang dipilih masukan (ke basis), dan variabel basis yang akan dihapus adalah dikecualikan (dari dasar).

Mari kita sebutkan dua aturan untuk memilih variabel masukan dan pengecualian dalam metode simpleks kondisi optimal Dan kondisi penerimaan . Mari kita rumuskan aturan-aturan ini dan juga pertimbangkan urutan tindakan yang dilakukan saat mengimplementasikan metode simpleks.

Kondisi optimal. Variabel masukan pada permasalahan maksimisasi (minimalkan) merupakan variabel non dasar yang mempunyai koefisien negatif (positif) terbesar dalam target-garis. Jika di target-line berisi beberapa koefisien seperti itu, kemudian pemilihan variabel yang dimasukkan dilakukan secara sewenang-wenang. Solusi optimal dicapai ketika target-line, semua koefisien untuk variabel non-dasar akan bernilai non-negatif (non-positif).

Kondisi penerimaan. Dalam permasalahan maksimalisasi dan minimalisasi, variabel basis yang rasio nilai sisi kanan batasannya terhadap koefisien positif kolom terdepan adalah minimum dipilih sebagai variabel yang dikecualikan. Jika terdapat beberapa variabel dasar dengan sifat ini, maka pemilihan variabel yang dikecualikan bersifat arbitrer.

Mari kita sajikan algoritma untuk menyelesaikan masalah pemrograman linier untuk mencari nilai maksimum menggunakan tabel simpleks.

F = с 1 x 1 +с 2 x 2 +…+с n x n maks

x 1 0, x 2 0,…, x n 0.

langkah pertama. Kami memperkenalkan variabel tambahan dan menulis sistem persamaan dan fungsi linier yang dihasilkan dalam bentuk sistem yang diperluas.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c hal.

langkah ke-2. Kami menyusun tabel simpleks awal.

langkah ke-3. Kami memeriksa pemenuhan kriteria optimalitas - adanya koefisien negatif di baris terakhir. Jika tidak ada, maka penyelesaiannya optimal dan F * =c o, variabel dasar sama dengan koefisien yang bersesuaian b j, variabel non-dasar sama dengan nol, yaitu X * =(b 1,b 2,…, b m, 0,…, 0).

langkah ke-4. Jika kriteria optimalitas tidak terpenuhi, maka koefisien negatif absolut terbesar pada baris (perkiraan) terakhir menentukan kolom penyelesaian s.

Untuk menentukan garis resolusi, kami menghitung rasio evaluasi dan isi kolom terakhir tabel.

Estimasi perbandingan baris ke-i adalah

 jika b i dan a is mempunyai tanda yang berbeda;

 jika b i =0 dan a adalah<0;

 jika a adalah =0;

0 jika b i =0 dan a >0;

Di kolom hubungan evaluatif kita menemukan elemen minimum min yang mendefinisikan string yang diaktifkang.

Jika tidak ada nilai minimum, maka permasalahan tersebut tidak mempunyai I optimal akhir dan tidak dapat diselesaikan.

Pada perpotongan baris dan kolom penyelesaian terdapat elemen penyelesaian a gs.

langkah ke-5. Mari kita buat tabel berikut. Untuk ini

Mari kita lanjutkan ke langkah ketiga.

Metode-M Kadang-kadang, ketika menyelesaikan ZLP, matriks koefisien untuk batasan sistem yang tidak diketahui tidak memiliki kolom satuan yang dapat digunakan untuk menyusun matriks satuan, yaitu. timbul masalah dalam pemilihan variabel dasar, atau solusi awal tidak dapat diterima. Dalam kasus seperti itu gunakan metode dasar buatan (M - metode). Dalam semua batasan dimana tidak ada variabel dasar, variabel buatan. Variabel buatan dimasukkan ke dalam fungsi tujuan dengan koefisien (- M) untuk soal dengan max dan dengan koefisien (+ M) untuk soal dengan min, di mana M adalah bilangan positif yang cukup besar. Kemudian permasalahan yang diperluas diselesaikan dengan menggunakan aturan metode simpleks. Jika semua variabel buatan sama dengan nol, mis. dikeluarkan dari basis, maka akan diperoleh solusi optimal terhadap masalah awal, atau masalah awal diselesaikan lebih lanjut dan solusi optimalnya ditemukan atau ketidakterpecahannya ditetapkan. Jika setidaknya salah satu variabel buatan ternyata berbeda dari nol, maka masalah awal tidak memiliki solusi