Solusi optimal yang dapat diterima pemrograman linier. Operasi pencarian

Pertimbangkan masalah pemrograman linier dasar (LPP): temukan nilai non-negatif dari variabel x1, x2,…, xn memenuhi kondisi m - persamaan

dan memaksimalkan fungsi linier dari variabel-variabel ini

Untuk mempermudah, kita akan mengasumsikan bahwa semua kondisi (1) adalah bebas linear (r \u003d m), dan kita akan beralasan dengan asumsi ini.

Setiap himpunan nilai nonnegatif x1, x2,…, xn yang memenuhi kondisi (1) disebut solusi yang dapat diterima dari LPLP. Solusi optimal adalah solusi yang dapat diterima yang memaksimalkan fungsi (2). Diperlukan untuk menemukan solusi yang optimal.

Apakah masalah ini selalu ada solusinya? Tidak, tidak selalu.

LPP tidak dapat diputuskan (tidak memiliki solusi optimal):

Karena ketidakcocokan sistem pembatasan. Itu. sistem tidak memiliki solusi apa pun, seperti yang ditunjukkan pada Gambar 1.

Gambar 1 - Sistem pembatasan yang tidak konsisten

Karena ketidakterbatasan fungsi tujuan pada kumpulan solusi. Dengan kata lain, ketika menyelesaikan LPP maksimal, nilai fungsi tujuan cenderung tak terhingga, dan dalam kasus LPP pada min, hingga minus tak terhingga, seperti yang ditunjukkan pada Gambar 2.

Gambar 2 - Ketidakterbatasan fungsi tujuan pada kumpulan solusi

LPP dapat dipecahkan:

Banyak solusi dibuat dari satu hal. Ini juga optimal, seperti yang ditunjukkan pada Gambar 3.

Gambar 3 - Banyak solusi terdiri dari satu titik

Satu-satunya solusi optimal untuk LPP. Garis lurus yang sesuai dengan fungsi tujuan pada posisi pembatas berpotongan dengan banyak solusi pada satu titik, seperti yang ditunjukkan pada Gambar 4.

Gambar 4 - Satu-satunya solusi optimal

Solusi optimal untuk LPP tidaklah unik. Vektor N tegak lurus dengan salah satu sisi himpunan solusi. Dalam hal ini, setiap titik pada segmen AB adalah optimal, seperti yang ditunjukkan pada Gambar 5.

Gambar 5 - Solusi optimal bukanlah satu-satunya

Memecahkan masalah pemrograman linier menggunakan metode simpleks

Metode simpleks adalah algoritma untuk memecahkan masalah LP, yang mengimplementasikan penghitungan titik sudut dari wilayah solusi yang layak ke arah peningkatan nilai fungsi tujuan C. Metode simpleks adalah yang utama dalam pemrograman linier.

Penggunaan metode ini dalam proyek diploma untuk menyelesaikan masalah LP disebabkan oleh faktor-faktor berikut:

Metode ini universal, berlaku untuk masalah pemrograman linier apa pun dalam bentuk kanonik;

Sifat algoritmik metode memungkinkannya untuk berhasil diprogram dan diimplementasikan dengan menggunakan cara-cara teknis.

Fungsi tujuan yang paling ekstrim selalu dicapai di sudut-sudut wilayah solusi yang memungkinkan. Pertama-tama, beberapa solusi awal (dukungan) yang layak ditemukan, yaitu. setiap titik sudut dari wilayah solusi yang layak. Prosedur metode memungkinkan untuk menjawab pertanyaan apakah solusi ini optimal. Jika ya, maka masalahnya sudah terpecahkan. Jika "tidak", maka transisi dilakukan ke titik sudut yang berdekatan dari wilayah solusi yang layak, di mana nilai fungsi tujuan meningkat. Proses penghitungan titik sudut wilayah solusi yang layak diulang sampai titik ditemukan, yang sesuai dengan ekstrem dari fungsi tujuan.

Karena jumlah simpul dari polytope terbatas, maka dalam jumlah langkah yang terbatas dijamin untuk menemukan nilai optimal atau untuk menetapkan fakta bahwa masalahnya tidak dapat dipecahkan.

Sistem kendala disini merupakan sistem persamaan linier dimana jumlah yang tidak diketahui lebih banyak dari pada jumlah persamaan. Jika peringkat sistem sama, maka dimungkinkan untuk memilih yang tidak diketahui yang diekspresikan dalam bentuk ketidaktahuan yang tersisa. Untuk kepastiannya, biasanya diasumsikan bahwa yang pertama tidak diketahui berturut-turut dipilih. (Variabel) yang tidak diketahui ini disebut dasar, sisanya gratis. Jumlah variabel dasar selalu sama dengan jumlah batasan.

Dengan menetapkan nilai-nilai tertentu ke variabel bebas dan menghitung nilai-nilai dasar (diekspresikan dalam bentuk yang gratis), berbagai solusi untuk sistem kendala diperoleh. Yang menarik adalah solusi yang diperoleh jika variabel bebas sama dengan nol. Solusi semacam itu disebut dasar. Solusi dasar disebut solusi dasar yang dapat diterima atau solusi pendukung jika nilai variabel di dalamnya non-negatif. Itu memenuhi semua batasan.

Memiliki sistem kendala, solusi dasar dari sistem ini ditemukan. Jika solusi dasar yang pertama ditemukan ternyata dapat diterima, maka itu diperiksa untuk optimalitas. Jika tidak optimal, transisi ke solusi dasar lain yang dapat diterima dilakukan.

Metode simpleks menjamin bahwa dengan solusi baru ini bentuk linier, jika tidak mencapai optimal, akan mendekatinya. Dengan solusi dasar baru yang dapat diterima, lakukan hal yang sama hingga mereka menemukan solusi yang optimal.

Jika solusi basa yang pertama kali ditemukan ternyata tidak dapat diterima, maka dengan menggunakan metode simpleks, transisi ke solusi basa lain dilakukan hingga pada beberapa langkah penyelesaian solusi basa ternyata dapat diterima, atau dapat disimpulkan bahwa sistem pembatas tidak konsisten.

Jadi, penerapan metode simpleks terbagi dalam dua tahap:

Menemukan solusi dasar yang dapat diterima untuk sistem pembatasan atau menetapkan fakta ketidakcocokannya;

Menemukan solusi optimal dalam hal kompatibilitas sistem kendala.

Algoritme untuk pindah ke solusi layak berikutnya adalah sebagai berikut:

Di baris koefisien fungsi tujuan, bilangan negatif terkecil dipilih saat mencari maksimum. Nomor seri koefisiennya adalah. Jika tidak ada, maka solusi dasar awal optimal;

Di antara elemen-elemen matriks dengan nomor kolom (kolom ini disebut leading, atau permitting), elemen-elemen positif dipilih. Jika tidak ada, maka fungsi tujuan tidak terbatas pada kisaran nilai variabel yang dapat diterima dan masalah tidak memiliki solusi;

Di antara elemen-elemen yang dipilih dari kolom utama matriks, yang nilai rasio suku bebasnya yang sesuai dengan elemen ini minimal dipilih. Elemen ini disebut leading, dan garis tempatnya disebut leading;

Variabel dasar yang sesuai dengan baris elemen utama harus diubah menjadi kategori bebas, dan variabel bebas yang sesuai dengan kolom elemen utama harus dimasukkan ke dalam jumlah elemen dasar. Sebuah solusi baru dibangun yang berisi sejumlah variabel dasar baru.

Kondisi optimalitas rencana untuk menyelesaikan masalah maksimum: tidak ada elemen negatif di antara koefisien fungsi tujuan.

Rumusan umum masalah pemrograman linier (LPP). Contoh LPP

Pemrograman linier adalah cabang matematika yang mempelajari metode untuk memecahkan masalah ekstrim, yang dicirikan oleh hubungan linier antara variabel dan kriteria linier optimal. Beberapa kata tentang istilah pemrograman linier. Itu membutuhkan pemahaman yang benar. Dalam hal ini, pemrograman tentu saja bukan menulis program komputer. Pemrograman di sini harus diartikan sebagai perencanaan, pembuatan rencana, pengembangan program aksi. Masalah matematika program linier mencakup studi tentang produksi dan situasi ekonomi tertentu, yang dalam satu atau lain bentuk diartikan sebagai masalah penggunaan optimal dari sumber daya yang terbatas. Kisaran tugas yang diselesaikan menggunakan metode pemrograman linier cukup luas. Sebagai contoh:

  • - masalah penggunaan sumber daya secara optimal dalam perencanaan produksi;
  • - masalah campuran (perencanaan komposisi produk);
  • - masalah menemukan kombinasi optimal dari berbagai jenis produk untuk penyimpanan di gudang (manajemen inventaris atau "masalah knapsack");
  • - tugas transportasi (analisis lokasi perusahaan, pergerakan barang). Pemrograman linier adalah cabang pemrograman matematika yang paling berkembang dan banyak digunakan (sebagai tambahan, ini termasuk: pemrograman integer, dinamis, nonlinier, parametrik). Ini karena hal berikut:
  • - model matematis dari sejumlah besar masalah ekonomi bersifat linier terhadap variabel yang dicari;
  • - jenis masalah ini yang paling banyak dipelajari saat ini. Baginya, metode khusus telah dikembangkan dengan bantuan yang masalah ini diselesaikan, dan program komputer yang sesuai;
  • - banyak masalah pemrograman linier, yang telah dipecahkan, telah ditemukan aplikasi yang luas;
  • - beberapa masalah, yang dalam rumusan aslinya tidak linier, setelah sejumlah pembatasan dan asumsi tambahan dapat menjadi linier atau dapat direduksi menjadi suatu bentuk sehingga dapat diselesaikan dengan metode pemrograman linier. Model ekonomi dan matematis dari masalah pemrograman linier meliputi: fungsi objektif, yang nilai optimal (maksimum atau minimum) perlu ditemukan; pembatasan berupa sistem persamaan linier atau pertidaksamaan; persyaratan non-negatif variabel. Secara umum modelnya ditulis sebagai berikut:
  • - fungsi objektif:

C1x1 + c2x2 + ... + cnxn\u003e max (min); - batasan:

a11x1 + a12x2 + ... + a1nxn (? \u003d?) b1,

a21x1 + a22x2 + ... + a2nxn (? \u003d?) b2

am1x1 + am2x2 + ... + amnxn (? \u003d?) bm;

Persyaratan non-negatif:

Dalam hal ini, aij, bi, cj () diberikan konstanta. Masalahnya adalah untuk menemukan nilai optimal dari fungsi (2.1) dengan batasan (2.2) dan (2.3). Sistem kendala (2.2) disebut kendala fungsional dari masalah, dan kendala (2.3) disebut langsung. Sebuah vektor yang memenuhi batasan (2.2) dan (2.3) disebut sebagai solusi yang dapat diterima (rencana) dari masalah pemrograman linier. Desain di mana fungsi (2.1) mencapai nilai maksimum (minimum) disebut optimal.

Di bawah ini adalah contoh dari beberapa masalah umum yang diselesaikan dengan menggunakan metode pemrograman linier. Tugas semacam itu memiliki kandungan ekonomi yang nyata. Sekarang kami hanya akan merumuskannya dalam istilah LPP, dan kami akan mempertimbangkan metode untuk menyelesaikan masalah tersebut di bawah ini.

1. Masalah penggunaan sumber daya secara optimal dalam perencanaan produksi. Arti umum dari tugas-tugas kelas ini adalah sebagai berikut. Perusahaan menghasilkan n produk yang berbeda. Produksinya membutuhkan berbagai jenis sumber daya (bahan mentah, bahan, waktu kerja, dll.). Sumber daya terbatas, cadangan mereka dalam periode perencanaan masing-masing adalah, b1, b2, ..., bm unit konvensional. Koefisien teknologi aij juga diketahui, yang menunjukkan berapa banyak unit sumber daya ke-i yang diperlukan untuk menghasilkan satu unit produk dari tipe ke-j (). Keuntungan yang diterima perusahaan dari penjualan produk tipe ke-j sama dengan cj. Dalam periode perencanaan, nilai aij, bi dan cj tetap. Diperlukan untuk menyusun rencana produksi seperti itu, yang dalam pelaksanaannya keuntungan perusahaan akan menjadi yang terbesar. Di bawah ini adalah contoh sederhana dari tugas kelas ini.

Perusahaan mengkhususkan diri dalam produksi tongkat hoki dan perangkat catur. Setiap klub menghasilkan keuntungan $ 2 untuk perusahaan dan $ 4 untuk setiap set catur. Dibutuhkan empat jam untuk membuat satu klub di Situs A dan dua jam di Situs B. Satu set catur diproduksi dengan enam jam di Situs A, enam jam di Situs B dan satu jam di Situs C. Kapasitas produksi yang tersedia di Situs A adalah 120 Nm. jam per hari, bagian B - 72 n-jam dan bagian C - 10 n-jam. Berapa banyak klub dan perangkat catur yang harus diproduksi perusahaan setiap hari untuk memaksimalkan keuntungan?

Kondisi masalah kelas ini sering disajikan dalam bentuk tabel (lihat Tabel 2.1).

Dalam kondisi ini, kami merumuskan masalah pemrograman linier. Mari kita tunjukkan: x1 - jumlah tongkat hoki yang diproduksi setiap hari, x2 - jumlah set catur yang diproduksi setiap hari. Kata-kata ZLP:

4x1 + 6x2? 120,

Mari kita tekankan bahwa setiap ketidaksetaraan dalam sistem batasan fungsional sesuai dalam hal ini dengan satu atau beberapa lokasi produksi, yaitu: yang pertama ke lokasi A, yang kedua ke situs B, dan yang ketiga ke situs C.

Sistem variabel dalam masalah mengoptimalkan struktur areal yang ditaburkan dengan mempertimbangkan rotasi tanaman

Masalah pemrograman linier umum (LPPP) dirumuskan sebagai berikut - temukan variabel masalahnya x 1 , x 2 , ..., x n, yang memberikan fungsi tujuan yang ekstrem

Solusi yang dapat diterima (rencana) dari masalah pemrograman linier (LPP) adalah apa saja nvektor -dimensi X=(x 1 , x 2 , ..., x n) yang memenuhi sistem persamaan dan kendala ketidaksetaraan. Kumpulan solusi yang layak untuk masalah membentuk area solusi yang layak D.

Sebuah solusi optimal (rencana) dari masalah pemrograman linier merupakan solusi yang layak sehingga fungsi objektifnya Z(X) mencapai titik ekstrim.

Masalah pemrograman linier kanonik (LCPP) memiliki bentuk

(1.2)

Ini berbeda dari OZLP karena sistem pembatasnya adalah sistem yang hanya terdiri dari persamaan dan semua variabel tidak negatif.

Membawa OZLP ke bentuk kanonis ZLP:

Untuk mengganti masalah minimisasi asli dengan masalah maksimisasi (atau sebaliknya, masalah maksimalisasi dengan masalah minimisasi), cukup dengan mengalikan fungsi tujuan dengan "-1" dan mencari maksimum (minimum) dari fungsi yang diperoleh;

Jika ada ketidaksetaraan di antara batasan, maka dengan memasukkan variabel nonnegatif tambahan x n +1 ≥ 0 mereka mengubahnya menjadi persamaan:

ketidaksamaan sebuah i 1 x 1 +…+sebuah di x n ≥ b saya digantikan oleh persamaan sebuah i 1 x 1 +…+sebuah di x n + x n +1 \u003d b saya,

ketidaksamaan sebuah i 1 x 1 +…+sebuah di x n ≤ b saya digantikan oleh persamaan sebuah i 1 x 1 +…+sebuah di x n + x n +1 \u003d b saya;

Jika beberapa variabel x k tidak memiliki batasan tanda, kemudian diganti (dalam fungsi tujuan dan dalam semua batasan) oleh perbedaan antara dua variabel non-negatif baru: x k = x" k – x” k , dimana x" k ≥ 0. x” k ≥ 0.

Metode grafis untuk menyelesaikan LPP dengan dua hal yang tidak diketahui

ZLP dengan dua unknown memiliki bentuk:

Metode ini didasarkan pada kemungkinan menampilkan area solusi yang layak secara grafis dan menemukan solusi optimal di antaranya.

Domain solusi yang layak (ODS) dari masalah adalah poligon cembung dan dibangun sebagai persimpangan (bagian umum) dari domain solusi untuk setiap ketidaksamaan kendala masalah.

Domain solusi untuk ketidaksetaraan sebuah i 1 x 1 +sebuah i 2 x 2 ≤ b saya adalah salah satu dari dua bidang setengah yang menjadi garis sebuah i 1 x 1 +sebuah i 2 x 2 = b Huruf i yang sesuai dengan pertidaksamaan ini membagi bidang koordinat. Untuk menentukan yang mana dari dua bidang-setengah yang merupakan daerah solusi, cukup mengganti koordinat dari beberapa titik yang tidak terletak pada garis pemisah menjadi pertidaksamaan:

Jika pertidaksamaan benar, maka domain solusi adalah setengah bidang yang berisi titik ini;

Jika pertidaksamaannya tidak benar, maka domain solusinya adalah bidang setengah yang tidak mengandung titik ini.

Garis level digunakan untuk menemukan solusi optimal di antara solusi yang layak.

Garis level tersebut disebut garis lurus dari 1 x 1 +dari 2 x 2 = l, dimana l= const, di mana fungsi tujuan tugas mengambil nilai konstan. Semua garis level sejajar satu sama lain.

Gradien fungsi tujuan lulusan Z(X) mendefinisikan vektor normal C = (c 1 , c 2) garis level. Fungsi tujuan pada garis level meningkat jika garis level dipindahkan ke arah normalnya, dan menurun ke arah yang berlawanan.

Garis referensi adalah garis tingkat yang memiliki setidaknya satu titik yang sama dengan ODR dan sehubungan dengan ODR yang terletak di salah satu bidang setengah. IDD masalah paling banyak memiliki dua jalur pendukung.

Solusi optimal dari LPP terletak pada garis dukungan di titik sudut poligon ODR. ZLP memiliki solusi unik jika garis dukungan melewati satu titik sudut ODR, kumpulan solusi tak terbatas jika garis dukungan melewati tepi poligon ODR. LPP tidak memiliki solusi jika ODR adalah himpunan kosong (ketika sistem batasan tidak konsisten) dan jika ODR tidak dibatasi ke arah ekstrem (fungsi tujuan tidak dibatasi).

Algoritma metode grafis untuk menyelesaikan LPP dengan dua hal yang tidak diketahui:

    Bangun SDT.

    Bangun vektor normal C = (c 1 , c 2) dan garis level dari 1 x 1 +dari 2 x 2 \u003d 0 melewati titik awal dan tegak lurus terhadap vektor DARI.

    Pindahkan garis level ke garis referensi ke arah vektor DARI dalam masalah untuk max, atau dalam arah yang berlawanan - dalam masalah untuk min.

    Jika, ketika garis level bergerak ke arah ekstrem, ODR pergi ke tak terhingga, maka LPP tidak memiliki solusi karena tak terbatasnya fungsi tujuan.

    Jika LPP memiliki solusi yang optimal, maka untuk mencarinya, selesaikan secara bersama-sama persamaan garis lurus yang membatasi GDR tersebut dan titik persekutuannya dengan garis support tersebut. Jika ekstrem dicapai pada dua titik sudut, maka LPP memiliki serangkaian solusi tak terbatas yang termasuk dalam tepi ODR yang dibatasi oleh titik sudut ini. Dalam hal ini, koordinat dari kedua titik sudut dihitung.

    Hitung nilai fungsi tujuan pada titik ekstrem.

Metode simpleks untuk menyelesaikan LPP

Metode simpleks didasarkan pada ketentuan berikut:

ODS dari masalah pemrograman linier adalah himpunan cembung dengan jumlah titik sudut yang terbatas;

Solusi optimal untuk LPP adalah salah satu titik sudut SDT. Titik sudut ODR mewakili secara aljabar beberapa solusi dasar (dukungan) dari sistem kendala LPP.

Solusi dasar (dukungan) dari LPP disebut solusi yang dapat diterima X 0 =( x 10 , x 20 , ..., x m 0, 0, ... 0), di mana vektor kondisi (kolom koefisien yang tidak diketahui dalam sistem batasan) tidak bergantung secara linier.

Koordinat bukan nol x 10 , x 20 , ..., x m 0 solusi X 0 disebut variabel dasar, koordinat yang tersisa dari solusi X 0 - variabel bebas. Jumlah koordinat bukan nol dari solusi referensi tidak boleh lebih besar dari pangkat r sistem pembatasan LPP (jumlah persamaan independen linier dalam sistem pembatasan LPP). Selanjutnya, kami mengasumsikan bahwa sistem kendala LPP terdiri dari persamaan independen linier, yaitu r = m.

Arti dari metode simpleks terdiri dari transisi yang disengaja dari satu solusi referensi LPP ke yang lain (yaitu, dari satu titik sudut SDT ke yang lain) ke arah ekstrem dan terdiri dari urutan tahapan:

Temukan solusi dukungan awal;

Transisi dari satu solusi referensi ke solusi lainnya;

Tentukan kriteria untuk mencapai solusi optimal atau simpulkan bahwa tidak ada solusi.

Algoritma eksekusiMetode simpleks ZLP

Algoritme metode simpleks membuat transisi dari satu solusi referensi LPP ke yang lain ke arah ekstrem dari fungsi tujuan.

Biarkan LPP diberikan dalam bentuk kanonik (1.2) dan kondisi

b saya ≥ 0, saya=1,2,…,m, (1.3)

relasi (1.3) selalu dapat dipenuhi dengan mengalikan persamaan yang sesuai dengan "-1" dalam kasus negatif b saya. Kami juga mengasumsikan bahwa sistem persamaan dalam kendala masalah (1.2) adalah bebas linier dan memiliki peringkat r = m... Dalam hal ini, vektor solusi dukungan memiliki m koordinat bukan nol.

Biarkan masalah awal (1.2), (1.3) direduksi menjadi bentuk, dimana variabel dasarnya x 1 , x 2 , ..., x m diekspresikan dalam variabel bebas x m + 1 , x m + 2 , ..., x n

(1.4)

Berdasarkan hubungan ini, kami membuat tabel 1

Tabel 1.

Tabel 1 disebut tabel simpleks. Semua transformasi lebih lanjut dikaitkan dengan perubahan dalam konten tabel ini.

Algoritma denganmetode implex:

1. Di baris terakhir Z Tabel simpleks dalam soal min menemukan unsur positif terkecil (dalam soal maks - unsur negatif terkecil), bukan menghitung suku bebasnya. Kolom yang sesuai dengan elemen ini disebut permisif.

2. Hitung rasio anggota bebas dengan elemen positif dari kolom pembatas (rasio simpleks). Temukan yang terkecil dari hubungan simpleks ini, yang cocok dengan string pembatas.

3. Di perpotongan dari garis pembatas dan kolom pembeda adalah elemen pembeda.

4. Jika ada beberapa hubungan-simpleks dengan ukuran yang sama, maka pilihlah salah satunya. Hal yang sama berlaku untuk elemen positif dari baris terakhir tabel simpleks.

5. Setelah menemukan elemen pembeda, lanjutkan ke tabel berikutnya. Variabel tidak diketahui yang sesuai dengan baris dan kolom pembeda ditukar. Dalam hal ini variabel dasar menjadi variabel bebas dan sebaliknya. Simpleks - tabel diubah sebagai berikut (tabel 2):

Meja 2

6. Elemen tabel 2 yang sesuai dengan elemen permisif tabel 1 sama dengan kebalikan dari elemen permisif.

7. Elemen-elemen dari baris tabel 2, yang sesuai dengan elemen-elemen dari baris perizinan pada tabel 1, diperoleh dengan membagi elemen-elemen yang sesuai pada tabel 1 dengan elemen perizinan.

8. Elemen-elemen kolom pada tabel 2, yang sesuai dengan elemen-elemen kolom perizinan pada tabel 1, diperoleh dengan membagi elemen-elemen yang sesuai dari tabel 1 dengan elemen perizinan dan diambil dengan tanda sebaliknya.

9. Sisa elemen dihitung dengan aturan persegi panjang: menggambar sebuah persegi panjang secara mental dalam tabel 1, satu simpul yang bertepatan dengan elemen pembeda (Re), dan yang lainnya dengan elemen yang kita cari; mari kita tunjukkan elemen di tabel baru 2 hingga (Ne), dan elemen berdiri di tempat yang sama di tabel lama 1 - hingga (Se). Dua simpul A dan B lainnya melengkapi bentuk menjadi persegi panjang. Maka elemen yang dicari Ne dari Tabel 2 sama dengan Ne \u003d Se - A * B / Re.

10. Kriteria optimalitas. Segera setelah Anda mendapatkan tabel di mana di baris terakhir dalam soal untuk min semua elemen bernilai negatif (dalam soal untuk maks semua elemen bernilai positif), dianggap bahwa ekstrem telah ditemukan. Nilai optimal dari fungsi tujuan sama dengan suku bebas di garis Z, dan solusi optimal ditentukan oleh suku bebas dengan variabel dasar. Semua variabel bebas disetel sama dengan nol.

11. Jika di kolom penyelesaian semua elemen negatif, maka masalah tidak memiliki solusi (minimum tidak tercapai).

Metode dasar buatan untuk memecahkan LPP

Algoritma metode simpleks dapat diterapkan jika ada solusi dukungan dari LPP yang dipilih, yaitu LPP asli (1.2) direduksi menjadi bentuk (1.4). Metode dasar buatan menawarkan prosedur untuk membangun solusi referensi semacam itu.

Metode basis buatan didasarkan pada pengenalan variabel basis buatan y 1 , y 2 ,…, y m, dengan mana kendala sistem LPP (2.2)

(1.5)

dapat diubah menjadi bentuk

(1.6)

Sistem (1.5) dan (1.6) akan setara jika semuanya y saya akan sama dengan nol. Seperti sebelumnya, kami percaya bahwa semuanya b saya ≥ 0. Untuk di saya sama dengan 0, kita harus mengubah masalah sedemikian rupa sehingga semua variabel basis buatan y saya diteruskan ke variabel bebas. Transisi seperti itu dapat dilakukan dengan algoritma metode simpleks sehubungan dengan fungsi tujuan tambahan

F(y) = y 1 + y 2 + ... + y m \u003d d 0 – (d 1 x 1 + d 2 x 2 +…+d n x n). (2.7)

Tabel simpleks asli untuk metode ini adalah

Pertama, tabel simpleks diubah relatif terhadap fungsi tujuan F(y) hingga solusi referensi diperoleh. Solusi referensi ditemukan ketika kriteria berikut terpenuhi: F(y) \u003d 0 dan semua variabel buatan di saya diterjemahkan ke dalam variabel bebas. Kemudian garis dihapus dari tabel simpleks untuk F(y) dan kolom untuk di saya dan memecahkan masalah untuk fungsi tujuan awal Z(x) hingga solusi optimal diperoleh.

Masalah pemrograman linier (LPP) adalah masalah menemukan nilai terbesar (atau terkecil) dari fungsi linier pada himpunan polihedral cembung.

Metode simpleks adalah metode untuk menyelesaikan masalah pemrograman linier. Inti dari metode ini adalah untuk menemukan rencana awal yang layak, dan dalam perbaikan rencana selanjutnya sampai nilai maksimum (atau minimum) dari fungsi tujuan tercapai dalam himpunan polihedral cembung tertentu atau penentuan tidak dapat dipecahkannya masalah.

Pertimbangkan masalah pemrograman linier berikut dalam bentuk kanonik:

(1)
(2)
(3)

Metode dasar buatan

Seperti yang ditunjukkan di atas, untuk masalah yang ditulis dalam bentuk kanonik, jika di antara vektor kolom matriks SEBUAH ada m independen tunggal dan linier, Anda dapat menentukan baseline secara langsung. Namun, untuk banyak masalah pemrograman linier yang ditulis dalam bentuk kanonik dan memiliki rencana dukungan, di antara vektor kolom matriks SEBUAH tidak selalu ada m tunggal dan independen linier. Pertimbangkan masalah berikut ini:

Biarkan itu diperlukan untuk menemukan fungsi maksimum

dalam kondisi

dimana yang pertama n elemen adalah nol. Variabel disebut buatan. Vektor kolom

(28)

membentuk apa yang disebut dasar buatan mruang vektor -dimensi.

Karena masalah yang diperpanjang memiliki rencana dasar, maka pemecahannya dapat ditemukan dengan menggunakan metode simpleks.

Teorema 4. Jika dalam perencanaan yang optimal masalah diperpanjang (24) - (26) nilai variabel buatan kemudian adalah rencana optimal untuk masalah (21) - (23).

Jadi, jika dalam rencana optimal yang ditemukan dari masalah yang diperluas, nilai variabel buatan sama dengan nol, maka diperoleh rencana optimal dari masalah asli. Mari kita membahas lebih detail tentang menemukan solusi untuk masalah yang diperpanjang.

Nilai fungsi tujuan dengan rencana referensi (27):

Catat itu F (X) dan terdiri dari dua bagian independen, salah satunya bergantung Mdan yang lainnya tidak.

Setelah menghitung F (X) dan nilainya, serta data awal dari masalah yang diperluas, dimasukkan ke dalam tabel simpleks, seperti yang ditunjukkan di atas. Satu-satunya perbedaan adalah tabel ini berisi satu baris lebih banyak dari tabel simpleks biasa. Selain itu, di ( m+1) baris ke-4 ditempatkan koefisien yang tidak mengandung M, dan masuk ( m+2) baris ke - koefisien pada M.

Saat berpindah dari satu rencana referensi ke rencana referensi lainnya, sebuah vektor dimasukkan ke dalam basis yang sesuai dengan bilangan negatif terbesar dalam nilai absolut ( m+2) string. Vektor buatan yang dikecualikan dari basis tidak masuk akal untuk diperkenalkan kembali ke basis. Ketika beralih ke rencana referensi lain, mungkin saja tidak ada vektor buatan dari basis yang akan dikecualikan. Perhitungan ulang tabel simpleks saat berpindah dari satu denah dasar ke denah lainnya dilakukan sesuai dengan aturan biasa dari metode simpleks (lihat di atas).

Proses iteratif dilakukan sesuai m+2 baris selama elemen m+2 baris sesuai dengan variabel tidak akan menjadi non-negatif. Selain itu, jika variabel buatan dikeluarkan dari basis, maka rencana yang ditemukan dari masalah yang diperluas sesuai dengan rencana dasar tertentu dari masalah asli.

m+2 baris, kolom x 0 negatif, maka masalah aslinya tidak memiliki solusi.

Jika tidak semua variabel buatan dikeluarkan dari basis dan elemennya m+2 baris, kolom x 0 sama dengan nol, maka denah dasar dari masalah awal merosot dan basisnya mengandung setidaknya satu vektor dari basis buatan.

Jika soal asli berisi beberapa vektor satuan, maka vektor-vektor itu harus dimasukkan dalam basis buatan.

Jika selama iterasi mGaris +2 tidak lagi mengandung elemen negatif, maka proses iteratif dilanjutkan m+1 baris hingga rencana optimal dari masalah yang diperpanjang ditemukan atau masalah tidak dapat diputuskan.

Dengan demikian, proses pencarian solusi dari masalah linear programming (21) - (23) dengan metode basis buatan meliputi tahapan utama sebagai berikut:

  • Masalah diperpanjang (24) - (26) didasari.
  • Temukan rencana dasar dari tugas yang diperpanjang.
  • Dengan menggunakan metode simpleks, vektor buatan dikeluarkan dari basis. Akibatnya, rencana dasar dari masalah asli ditemukan atau ketidaktegasannya diperbaiki.
  • Menggunakan rencana dukungan yang ditemukan dari LPP (21) - (23), baik rencana optimal dari masalah asli ditemukan, atau ketidaktegasannya ditetapkan.

Untuk memecahkan masalah pemrograman linier online, gunakan kalkulator

Komponen model matematika

Model matematika adalah dasar untuk memecahkan masalah ekonomi.

Model matematika tugas disebut himpunan hubungan matematis yang menggambarkan esensi tugas.

Penyusunan model matematika meliputi:
  • pemilihan variabel tugas
  • menyusun sistem pembatasan
  • pilihan fungsi objektif

Variabel tugas disebut nilai X1, X2, Xn, yang sepenuhnya mencirikan proses ekonomi. Biasanya mereka ditulis sebagai vektor: X \u003d (X1, X2, ..., Xn).

Sistem pembatasan Masalah disebut sekumpulan persamaan dan pertidaksamaan yang menggambarkan keterbatasan sumber daya dalam masalah yang sedang dipertimbangkan.

Fungsi target tugas tersebut disebut fungsi variabel tugas, yang mencirikan kualitas tugas dan ekstrem yang ingin Anda temukan.

Secara umum, masalah pemrograman linier dapat ditulis sebagai berikut:

Notasi ini berarti sebagai berikut: temukan ekstrem dari fungsi tujuan (1) dan variabel yang sesuai X \u003d (X1, X2, ..., Xn), asalkan variabel-variabel ini memenuhi sistem batasan (2) dan kondisi nonnegativitas (3).

Solusi yang valid (rencana) dari masalah pemrograman linier adalah setiap vektor berdimensi n X \u003d (X1, X2, ..., Xn) yang memenuhi sistem batasan dan kondisi non-negatif.

Kumpulan solusi yang layak (rencana) dari bentuk masalah berbagai solusi yang layak (ODR).

Solusi optimal (rencana) masalah pemrograman linier adalah solusi yang layak (rencana) dari masalah di mana fungsi tujuan mencapai titik ekstrim.

Contoh penyusunan model matematika Masalah penggunaan sumber daya (bahan baku)

Kondisi: Untuk pembuatan n jenis produk, m jenis sumber daya digunakan. Buat model matematika.

Diketahui:

  • bi (i \u003d 1,2,3, ..., m) - cadangan dari setiap jenis sumber daya ke-i;
  • aij (i \u003d 1,2,3, ..., m; j \u003d 1,2,3, ..., n) - biaya dari setiap jenis sumber daya ke-i untuk produksi satu unit volume dari jenis produk ke-j;
  • cj (j \u003d 1,2,3, ..., n) - keuntungan dari penjualan satu unit volume jenis produk ke-j.

Diperlukan untuk menyusun rencana produksi produk, yang memberikan keuntungan maksimum untuk pembatasan sumber daya (bahan baku).

Keputusan:

Kami memperkenalkan vektor variabel X \u003d (X1, X2, ..., Xn), di mana xj (j \u003d 1,2, ..., n) adalah volume produksi dari jenis produk ke-j.

Biaya jenis sumber daya ke-i untuk pembuatan volume produk xj tertentu sama dengan aijxj, oleh karena itu, pembatasan penggunaan sumber daya untuk produksi semua jenis produk adalah sebagai berikut:
Keuntungan dari penjualan produk jenis ke-j sama dengan cjxj, oleh karena itu fungsi tujuannya sama dengan:

Menjawab - Model matematisnya adalah:

Bentuk kanonik dari masalah pemrograman linier

Dalam kasus umum, masalah pemrograman linier ditulis sehingga persamaan dan pertidaksamaan menjadi batasan, dan variabel dapat berupa variabel non-negatif dan variabel sewenang-wenang.

Dalam kasus ketika semua kendala adalah persamaan dan semua variabel memenuhi kondisi nonnegativitas, masalah pemrograman linier disebut resmi.

Itu dapat direpresentasikan dalam koordinat, vektor dan notasi matriks.

Masalah pemrograman linier kanonik dalam notasi koordinat berupa:

Masalah pemrograman linier kanonik dalam notasi matriks berupa:

  • А - matriks koefisien dari sistem persamaan
  • X - matriks-kolom variabel tugas
  • Ao - matriks-kolom dari sisi kanan sistem batasan

Yang sering digunakan adalah masalah pemrograman linier yang disebut simetris, yang dalam notasi matriks berbentuk:

Mengurangi masalah pemrograman linier umum menjadi bentuk kanonik

Dalam kebanyakan metode untuk memecahkan masalah pemrograman linier, diasumsikan bahwa sistem kendala terdiri dari persamaan dan kondisi alam untuk variabel nonnegativitas. Namun, dalam menyusun model masalah ekonomi, kendala terutama dibentuk dalam bentuk sistem pertidaksamaan, sehingga perlu untuk dapat berpindah dari sistem pertidaksamaan ke sistem persamaan.

Hal ini dapat dilakukan sebagai berikut:

Ambil pertidaksamaan linier a1x1 + a2x2 + ... + anxn≤b dan tambahkan sejumlah xn + 1 ke sisi kirinya, sehingga pertidaksamaan tersebut berubah menjadi persamaan a1x1 + a2x2 + ... + anxn + xn + 1 \u003d b. Selain itu, nilai xn + 1 ini non-negatif.

Mari pertimbangkan semuanya dengan sebuah contoh.

Contoh 26.1

Bawa masalah pemrograman linier ke bentuk kanonis:

Keputusan:
Mari kita beralih ke masalah menemukan fungsi tujuan maksimum.
Untuk melakukan ini, kami mengubah tanda koefisien fungsi tujuan.
Untuk mengubah pertidaksamaan kedua dan ketiga dari sistem batasan menjadi persamaan, kami memperkenalkan variabel tambahan non-negatif x4 x5 (pada model matematika, operasi ini ditandai dengan huruf D).
Variabel x4 dimasukkan di sisi kiri pertidaksamaan kedua dengan tanda "+", karena pertidaksamaan tersebut berbentuk "≤".
Variabel x5 dimasukkan di sisi kiri pertidaksamaan ketiga dengan tanda "-", karena pertidaksamaan tersebut berbentuk "≥".
Variabel x4 x5 dimasukkan ke dalam fungsi tujuan dengan koefisien. sama dengan nol.
Kami menulis tugas dalam bentuk kanonik: