Kaedah simplex untuk menyelesaikan masalah pengaturcaraan linear. Pelbagai bentuk tatatanda ZLP (umum, kanonik, simetri)

Rakaman fungsi objektif dan sistem kekangan dalam pelbagai masalah pengaturcaraan linear tidak sama: dalam beberapa masalah diperlukan untuk mencari minimum fungsi objektif, dan dalam yang lain - maksimum; dalam beberapa kes pembolehubah yang dicari bergantung pada satu indeks, dan dalam kes lain pada dua; dalam beberapa masalah kekangan dinyatakan dalam bentuk sistem ketaksamaan linear, dan lain-lain – dalam bentuk sistem persamaan linear. Dalam amalan, ia juga mungkin mempunyai masalah di mana beberapa kekangan adalah dalam bentuk ketaksamaan linear, dan sebahagian lagi adalah dalam bentuk persamaan linear. Juga, tidak semua masalah mungkin memerlukan pembolehubah bukan negatif.

Mengambil kira pelbagai masalah pengaturcaraan linear memerlukan pembangunan kaedah khas untuk menyelesaikan kelas individu mereka. Kami akan menumpukan perhatian kepada pembelajaran sifat umum dan kaedah pengaturcaraan linear, ditulis dalam bentuk kanonik yang dipanggil.

Jika dalam masalah pengaturcaraan linear sistem kekangan awal berbentuk persamaan seperti

dan anda perlu mencari maksimum fungsi objektif linear

maka masalah pengaturcaraan linear dianggap ditulis dalam bentuk kanonik.

Sebarang masalah pengaturcaraan linear boleh dikurangkan dengan mudah kepada bentuk kanonik. Dalam kes umum, untuk ini sudah cukup untuk dapat, pertama, mengurangkan masalah meminimumkan fungsi objektif kepada masalah memaksimumkannya, kedua, beralih daripada kekangan ketidaksamaan kepada kekangan kesaksamaan, dan ketiga, menukar pembolehubah yang tidak tertakluk kepada syarat bukan negatif .

Dalam kes apabila anda perlu mencari minimum fungsi , kita boleh meneruskan untuk mencari maksimum fungsi , kerana pernyataan berikut adalah benar:
.

Kekangan ketidaksamaan masalah asal, yang mempunyai bentuk " ", boleh diubah menjadi kekangan persamaan dengan menambahkan pembolehubah bukan negatif tambahan ke sebelah kirinya, dan kekangan ketaksamaan dalam bentuk " ” – dengan menolak pembolehubah bukan negatif tambahan dari sebelah kirinya.

Ambil perhatian bahawa bilangan pembolehubah bukan negatif tambahan yang diperkenalkan sentiasa sama dengan bilangan ketaksamaan dalam sistem kekangan asal.

Pembolehubah tambahan yang diperkenalkan mempunyai makna ekonomi yang sangat spesifik. Jadi, jika kekangan masalah pengaturcaraan linear asal mencerminkan kos dan ketersediaan sumber pengeluaran, maka nilai angka pembolehubah tambahan menunjukkan jumlah sumber yang tidak digunakan yang sepadan.

Perhatikan juga bahawa jika beberapa pembolehubah tidak mematuhi syarat bukan negatif, maka ia mesti digantikan dengan dua pembolehubah bukan negatif Dan , setelah menerima
.

Contoh. Tulis masalah pengoptimuman linear berikut dalam bentuk kanonik: cari minimum fungsi
di bawah sekatan

Penyelesaian

Dalam masalah ini, anda perlu mencari minimum fungsi objektif, dan sistem kekangan termasuk empat ketaksamaan. Untuk menulisnya dalam bentuk kanonik, anda perlu beralih daripada kekangan ketidaksamaan kepada kekangan persamaan, dan juga mengubah fungsi sasaran.

Oleh kerana bilangan ketaksamaan yang termasuk dalam sistem kekangan masalah adalah sama dengan empat, peralihan ini mesti dijalankan dengan pengenalan empat pembolehubah bukan negatif tambahan. Selain itu, dalam ketidaksamaan kedua dan keempat terdapat tanda " ", jadi kami menambah pembolehubah tambahan di sebelah kirinya. Dalam ketaksamaan pertama dan ketiga terdapat tanda " “, yang bermaksud kita menolak pembolehubah tambahan dari sebelah kirinya.

Kami juga mengubah fungsi objektif, menukar semua tanda kepada sebaliknya, dan mencari maksimumnya.

Oleh itu, masalah pengaturcaraan linear ini akan ditulis dalam bentuk kanonik berikut:

cari maksimum fungsi

di bawah sekatan

Muka surat 1

Bentuk kanonik masalah dicirikan oleh tiga ciri berikut: 1) sistem kekangan homogen dalam bentuk sistem persamaan; 2) keadaan bukan negatif homogen yang digunakan untuk semua pembolehubah yang terlibat dalam masalah, dan 3) memaksimumkan fungsi linear. Dalam masalah ini, ketiga-tiga ciri ini dilanggar.

Bentuk kanonik masalah pengaturcaraan linear adalah mudah kerana mudah untuk mencari puncak awal kawasan yang boleh dilaksanakan.

Mari kita pertimbangkan bentuk kanonik masalah pengaturcaraan linear dan kaedah penghapusan Jordan-Gauss.

Bentuk kanonik masalah pengaturcaraan linear selalunya mudah.

Apabila mengubah sistem kekangan kepada bentuk kanonik masalah pengaturcaraan linear, ketaksamaan (12) dan (13) mesti digantikan dengan kesamaan. Untuk melakukan ini, pembolehubah bukan negatif tambahan diperkenalkan.

Buktikan bahawa matriks nyata ulang-alik berpasangan secara serentak dikurangkan kepada bentuk kanonik Masalah 1128 dengan penjelmaan persamaan menggunakan matriks ortogon.

Pada asasnya (4) - (5) boleh dianggap sebagai bentuk kanonik masalah pengaturcaraan tak linear, kerana kaedah yang digariskan dalam Bab. Biasanya dalam masalah pengaturcaraan tak linear tidak ada keperluan untuk pembolehubah menjadi integer.

Jenis sekatan dan kaedah untuk transformasi mereka.

Bentuk kanonik masalah dicirikan oleh kehomogenan sistem kekangan dalam bentuk sistem persamaan; memaksimumkan fungsi objektif; keadaan bukan negatif semua pembolehubah yang terlibat dalam masalah.

tiada ciri-ciri tambahan bentuk masalah kanonik tidak menambah skema pengiraan yang sedang dipertimbangkan.

Mari kita pertimbangkan dahulu bentuk kanonik kedua bagi masalah minimum.

Algoritma simplex-mete boleh dibahagikan kepada dua peringkat. Pada peringkat pertama, penyelesaian asas ditemui dengan menghapuskan pembolehubah. Jika ia dijumpai, maka kita mempunyai bentuk kanonik masalah untuk bergerak ke peringkat kedua. Langkah kedua ialah menyemak sama ada terdapat batas optimum. Sekiranya ia wujud, maka penyelesaian asas yang boleh diterima ditentukan dan dari mana penyelesaian yang optimum dipilih.

Jika masalah diselesaikan dalam bentuk kanonik, maka hanya sebahagian daripada operasi yang diperkenalkan dalam perenggan kedua digunakan. Oleh itu, untuk masalah minimum kanonik, hanya kes perenggan 3.4.1 direalisasikan, dan hanya operasi penyusunan semula kitaran lajur, melepasi lajur melalui zon sempadan menegak, membetulkan pelanggaran struktur dan sebahagian daripada operasi pemotongan diperlukan. Secara simetri, apabila menyelesaikan masalah maksimum kanonik, hanya kes perenggan 3.4.2 direalisasikan, dan operasi penyusunan semula kitaran rentetan, melepasi rentetan melalui zon sempadan mendatar, pembetulan pelanggaran struktur, dan bahagian lain operasi pemotongan adalah diperlukan. Jika tidak tiada apa-apa spesifik tambahan bentuk kanonik tugas tidak menambah.

Perenggan pertama pengenalan menunjukkan bagaimana tugas biasa Pengaturcaraan linear boleh dikurangkan kepada salah satu bentuk kanoniknya. Untuk masalah kanonik, penerangan kaedah penambahbaikan berurutan secara rasmi dipermudahkan, kerana tidak perlu mempertimbangkan dua pilihan untuk melanggar keadaan optimum dan dua pilihan untuk mencapai puncak seterusnya. Walau bagaimanapun, ini meningkatkan saiz matriks asas A [ /, J ], yang terutamanya menentukan kerumitan satu shat. Walau bagaimanapun, dalam banyak kes, menggunakan kaedah kepada bentuk kanonik masalah ternyata lebih baik, dan dalam bahagian ini kita akan membincangkan varian kaedah yang diperoleh untuk masalah pengaturcaraan linear tertentu.

Halaman: 1

Sebarang masalah pengaturcaraan linear boleh dikurangkan kepada masalah pengaturcaraan linear dalam bentuk kanonik. Untuk melakukan ini, dalam kes umum, anda perlu dapat mengurangkan masalah memaksimumkan kepada masalah meminimumkan; beralih daripada kekangan ketidaksamaan kepada kekangan kesaksamaan dan menggantikan pembolehubah yang tidak mematuhi syarat bukan negatif. Memaksimumkan fungsi tertentu adalah bersamaan dengan meminimumkan fungsi yang sama yang diambil dengan tanda bertentangan, dan sebaliknya.

Peraturan untuk mengurangkan masalah pengaturcaraan linear kepada bentuk kanonik adalah seperti berikut:

jika dalam masalah asal Jika anda ingin menentukan maksimum fungsi linear, maka anda harus menukar tanda dan mencari minimum fungsi ini;
jika ada sekatan bahagian kanan adalah negatif, maka had ini hendaklah didarab dengan -1;
jika terdapat ketidaksamaan antara sekatan, maka dengan memperkenalkan pembolehubah bukan negatif tambahan ia diubah menjadi kesamaan;
jika beberapa pembolehubah x j tidak mempunyai sekatan tanda, maka ia digantikan (dalam fungsi objektif dan dalam semua sekatan) dengan perbezaan antara dua pembolehubah bukan negatif baharu:
x 3 = x 3 + - x 3 - , Di mana x 3 + , x 3 - ≥ 0 .

Contoh 1. Mengurangkan masalah pengaturcaraan linear kepada bentuk kanonik:

min 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.

Marilah kita memperkenalkan pembolehubah meratakan ke dalam setiap persamaan sistem kekangan x 4 , x 5 , x 6. Sistem akan ditulis dalam bentuk kesamaan, dan dalam persamaan pertama dan ketiga sistem kekangan pembolehubah x 4 , x 6 dimasuki sebelah kiri dengan tanda "+", dan dalam persamaan kedua pembolehubah 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.

Sebutan bebas dalam bentuk kanonik mestilah positif; untuk melakukan ini, darabkan 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.

Dalam bentuk kanonik penulisan masalah pengaturcaraan linear, semua pembolehubah yang termasuk dalam sistem kekangan mestilah negatif. Mari kita andaikan itu x 1 = x 1" - x 7 , Di mana x 1"≥ 0, x 7 ≥ 0 .

Menggantikan ungkapan ini ke dalam sistem kekangan dan fungsi objektif dan, menulis pembolehubah dalam susunan indeks yang semakin meningkat, kami memperoleh masalah pengaturcaraan linear yang dibentangkan dalam bentuk kanonik:

L min = 2x 1" + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5;
-x 1" - x 2 + x 3 + x 5 + x 7 = 1;
-2x 1" + x 2 - x 6 + 2x 7 = 3;
x 1 "≥ 0; x i ≥ 0, i=2, 3, 4, 5, 6, 7.

Keadaan optimum untuk pelan asas masalah LP kanonik. Kaedah Simplex dan penumpuannya.

Kaedah simplex ialah universal, kerana ia membolehkan anda menyelesaikan hampir semua masalah pengaturcaraan linear yang ditulis bentuk kanonik.

Idea kaedah simplex penambahbaikan rancangan yang konsisten, ialah, bermula dari beberapa penyelesaian rujukan awal, pergerakan yang diarahkan secara berurutan daripada rujukan penyelesaian masalah kepada yang optimum.

Nilai fungsi objektif tidak berkurangan semasa pergerakan ini untuk masalah secara maksimum.

Oleh kerana bilangan penyelesaian sokongan adalah terhingga, maka selepas beberapa langkah terhingga kami memperoleh penyelesaian sokongan yang optimum.

Penyelesaian rujukan ialah penyelesaian asas bukan negatif.

Algoritma kaedah simplex

1. Model matematik masalah mestilah berkanun. Jika ia bukan kanonik, maka ia mesti dibawa ke bentuk kanonik.

2. Cari penyelesaian rujukan awal dan semak untuk keoptimuman.
Untuk melakukan ini, isikan jadual simplex 1.
Kami mengisi semua baris jadual langkah pertama mengikut data sistem sekatan dan fungsi objektif.

mungkin kes berikut apabila menyelesaikan masalah pada maksimum:

1. Jika semua pekali baris terakhir jadual simplex Dj³ 0, kemudian dijumpai

penyelesaian optimum.

2 Jika sekurang-kurangnya satu pekali Dj £ 0, tetapi untuk pembolehubah sepadan tidak ada satu hubungan penilaian positif, maka penyelesaiannya kita hentikan tugasan, sejak F(X) ® ¥ , iaitu fungsi objektif tidak terhad dalam bidang penyelesaian yang boleh dilaksanakan.

Jika sekurang-kurangnya satu pekali baris terakhir adalah negatif, dan untuk pembolehubah yang sepadan ada sekurang-kurangnya satu sikap menilai positif, maka anda perlu bergerak kepada penyelesaian rujukan yang lain.

4. E jika terdapat beberapa pekali negatif dalam baris terakhir, kemudian kepada lajur pembolehubah yang mendasari(BP) memperkenalkan itu pembolehubah, yang sepadan dengan terbesar dalam nilai mutlak pekali negatif.

5. Jika sekurang-kurangnya satu pekali Dk< 0 , Itu k - ke lajur terima untuk penyampai.

6. Untuk barisan terkemuka kami terima yang sesuai minimum nisbah ahli bebas bi kepada pekali positif terkemuka, k – yang itu kolum.

7. Elemen yang terletak di persimpangan baris dan lajur terkemuka dipanggil unsur peneraju.

Mengisi jadual simpleks 2 :

· isi lajur asas dengan sifar dan satu

· tulis semula baris pendahuluan dengan membahagikannya dengan unsur pendahulu

· jika baris utama mempunyai sifar, maka lajur yang sepadan boleh dialihkan ke jadual simpleks seterusnya

· kita mencari pekali yang tinggal menggunakan peraturan "segi empat tepat".

Kami memperoleh penyelesaian rujukan baharu, yang kami semak untuk optimum:

Jika semua pekali baris terakhir Dj³ 0, maka penyelesaiannya dijumpai maksimum.

Jika tidak, isi jadual simpleks langkah ke-8 dan seterusnya.

Jika fungsi objektif F(X) memerlukan pencarian nilai minimum, kemudian kriteria optimum masalah ialah pekali bukan positif D j untuk semua j = 1,2,...n.

Penumpuan kaedah simpleks. Degenerasi dalam masalah LP. Sifat paling penting bagi mana-mana algoritma pengiraan ialah penumpuan, iaitu kemungkinan mendapatkan hasil yang diingini semasa penggunaannya (dengan ketepatan yang diberikan) dalam bilangan langkah yang terhad (lelaran).

Adalah mudah untuk melihat bahawa masalah dengan penumpuan kaedah simpleks berpotensi timbul pada peringkat memilih nilai r (bahagian 2") dalam kes di mana yang sama nilai minimum perhubungan

akan dicapai untuk beberapa baris jadual T (q) secara serentak. Kemudian pada lelaran seterusnya, lajur b(β(q+1)) akan mengandungi unsur sifar.

: Masalah pengaturcaraan linear (LPP)

1. Pengaturcaraan linear

2. Jenis masalah pengaturcaraan linear

3. Bentuk rekod PAP

4. Bentuk kanonik masalah pengaturcaraan linear

Pengaturcaraan linear

Pengaturcaraan linear ialah satu cabang pengaturcaraan matematik yang digunakan dalam membangunkan kaedah untuk mencari ekstrem fungsi linear beberapa pembolehubah dengan linear sekatan tambahan, dikenakan ke atas pembolehubah.

Berdasarkan jenis masalah yang mereka selesaikan, kaedah LP dibahagikan kepada universal dan khas. Dengan menggunakan kaedah sejagat Sebarang masalah pengaturcaraan linear (LPP) boleh diselesaikan. Yang istimewa mengambil kira ciri model masalah, fungsi objektifnya dan sistem kekangan.

Ciri utama masalah pengaturcaraan linear ialah ekstrem fungsi objektif berada di sempadan kawasan penyelesaian yang boleh dilaksanakan.

Rajah 1 - Ekstrem bagi fungsi objektif

Model matematik ZLP ditulis seperti berikut:

maks (atau min) Z=z(X),(1)

ODR boleh diwakili oleh sistem persamaan linear atau ketaksamaan.

Vektor X = (x 1, x 2, .... x p) ialah vektor kawalan atau kesan kawalan.

Pelan X yang boleh diterima, di mana kriteria optimum Z=z(X) mencapai nilai ekstrem, dipanggil optimum dan dilambangkan dengan X*, nilai ekstrem fungsi objektif oleh Z*=z(X*).

Jenis masalah pengaturcaraan linear

Kaedah pengaturcaraan linear digunakan secara meluas di perusahaan perindustrian apabila mengoptimumkan program pengeluaran, mengedarkannya ke seluruh bengkel dan dari semasa ke semasa, apabila memuatkan pelbagai peralatan, merancang aliran kargo, menentukan pelan pusing ganti, dsb.

Jenis tugas yang paling biasa ialah tugasan penggunaan yang optimum sumber. Biarkan beberapa unit pengeluaran (bengkel, perusahaan, persatuan, dll.), berdasarkan keadaan pasaran, keupayaan teknikal dan sumber yang ada, boleh menghasilkan n pelbagai jenis produk yang dikenali di bawah nombor j.

Apabila menghasilkan produk, perusahaan dihadkan oleh sumber yang ada, kuantiti yang akan dilambangkan dengan m, dan vektor sumber B = (b 1, b 2, ..., b t). Pekali teknologi a ij juga diketahui, yang menunjukkan kadar penggunaan sumber ke-i untuk pengeluaran unit produk ke-j. Kecekapan keluaran unit produk j-i dicirikan oleh keuntungan p j .

Ia diperlukan untuk menentukan rancangan pengeluaran X = (x 1, x 2, ..., x p), memaksimumkan keuntungan perusahaan dengan sumber yang diberikan.

Fungsi objektif kelihatan seperti ini

di bawah sekatan

Selalunya julat produk ditubuhkan oleh organisasi yang lebih tinggi, iaitu volumnya mesti terkandung dalam sempadan tertentu D dalam j dan D dalam j: kemudian sekatan berikut ditetapkan:

Model masalah penggunaan sumber secara optimum menjadi asas model untuk mengoptimumkan program pengeluaran tahunan perusahaan. Model ini termasuk sekatan pada masa operasi peralatan.

Dengan mengekalkan tatatanda yang sama, kami menulis melalui b j dan c j, masing-masing, harga jualan dan kos seunit produk jth. Perkara berikut boleh diambil sebagai kriteria optimum:

1) keuntungan maksimum

2) kos pengeluaran minimum

3) output maksimum dari segi nilai (hasil daripada jualan produk)

Contoh. Perusahaan boleh menghasilkan empat jenis produk 1, 2, 3 dan 4. Jualan apa-apa jumlah adalah dijamin. Pada suku tersebut, perusahaan itu mempunyai tenaga buruh seramai 100 orang syif, produk separuh siap seberat 260 kg, dan peralatan mesin sebanyak 370 syif mesin. Kadar penggunaan sumber dan keuntungan seunit bagi setiap jenis produk dibentangkan dalam Jadual 1.

Perlu:

a) solekan model matematik tugas menentukan rancangan pengeluaran yang akan mencapai keuntungan maksimum;

b) menyelesaikan masalah dengan keperluan pembungkusan supaya bilangan unit produk ketiga adalah 3 kali ganda lebih kuantiti unit dahulu;

c) mengetahui pelbagai optimum untuk syarat-syarat tambahan: menghasilkan sekurang-kurangnya 25 unit produk pertama, tidak lebih daripada 30 unit produk ketiga, dan kedua dan keempat dalam nisbah 1:3.

Jadual 1

Data awal

Model matematik masalah:

Fungsi objektif:

maks: Z=40x 1 +50x 2 +100x 3 +80x 4

dengan sekatan:

a) untuk sumber buruh:

2.5x 1 +2.5x 2 +2x 3 +1.5x 4 ? 100;

untuk produk separuh siap:

4x 1 +10x 2 +4x 3 +6x 4 ? 260;

untuk alatan mesin:

8x 1 +7x 2 +4x 3 +10x 4 ? 370;

keadaan bukan negatif:

b) keperluan tambahan untuk konfigurasi akan dinyatakan oleh syarat

3x 1 =x 3, iaitu 3x 1 x 3 =0;

c) mari kita tunjukkan syarat sempadan dan keadaan konfigurasi seperti berikut: x 1 ? 25,

x 3?30, 3*x 2 = x 4.

Masalah membuat pesanan atau memuatkan kumpulan peralatan yang boleh ditukar ganti. Ia mengenai o pengedaran pesanan antara m (i=1,..., m) perusahaan (kedai, mesin, penghibur) dengan ciri pengeluaran dan teknologi yang berbeza, tetapi boleh ditukar ganti dari segi memenuhi pesanan. Ia dikehendaki merangka pelan penempatan pesanan di mana tugas itu akan diselesaikan dan penunjuk kecekapan akan mencapai nilai yang melampau.

Mari kita rumuskan masalah secara matematik. Biarkan n jenis produk perlu dihasilkan menggunakan m kumpulan peralatan homogen. Rancangan pengeluaran untuk setiap jenis produk tempoh tertentu diberikan oleh set x j (j=1,2, …n). Kuasa setiap jenis peralatan adalah terhad dan sama dengan b i. Matriks teknologi A=||a ij || diketahui, di mana a ij ialah bilangan unit produk ke-j yang dihasilkan setiap unit masa untuk peralatan ke-i. Matriks C ialah matriks kos, di mana c ij ialah kos yang berkaitan dengan output unit jth produk pada peralatan ke-i. X ialah vektor isipadu keluaran.

Model masalah akan mengambil bentuk berikut:

fungsi objektif - meminimumkan kos melaksanakan semua pesanan

dengan sekatan:

a) dengan kuasa peralatan

b) untuk pengeluaran

c) keadaan bukan negatif

Masalah ini dipanggil masalah pengedaran atau pengedaran.

Jika untuk beberapa jenis produk pelan dibenarkan untuk dilampaui, maka had (b) akan digunakan

Perkara berikut juga boleh diambil sebagai keuntungan sasaran:

a) keuntungan maksimum

b) kos minimum masa mesin

Kerana Mana-mana model mengandungi premis yang memudahkan; untuk aplikasi yang betul dari hasil yang diperoleh, pemahaman yang jelas tentang intipati penyederhanaan ini diperlukan, yang, akhirnya, membolehkan kita membuat kesimpulan tentang kebolehterimaan atau ketidakbolehterimaannya. Penyederhanaan yang paling ketara dalam model yang dipertimbangkan ialah andaian hubungan berkadar terus (linear) antara volum penggunaan sumber dan volum pengeluaran, yang dinyatakan menggunakan norma kos a ij . Jelas sekali, andaian ini tidak selalu dipenuhi. Oleh itu, jumlah penggunaan banyak sumber (contohnya, aset tetap) berubah secara tiba-tiba - bergantung pada perubahan dalam program pengeluaran X. Premis memudahkan lain termasuk andaian tentang kebebasan harga j daripada volum x j, yang hanya sah untuk had tertentu. perubahan mereka. Ia juga penting untuk mengetahui titik "terdedah" ini kerana ia menunjukkan arah asas untuk menambah baik model.

Borang rakaman PAP

Terdapat 3 bentuk rakaman PAP:

1) dalam bentuk fungsi

maks(atau min)Z=,maks(atau min)Z=,

2) bentuk vektor

(hasil skalar bagi vektor)

di bawah sekatan

A 1 x 1 +A 2 x 2 +..+A n x n = B

Di manakah vektor

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n), dan.

3) bentuk matriks

di bawah sekatan

di mana C = (c 1, c 2,...c n),

Bentuk kanonik masalah pengaturcaraan linear

Jika semua kekangan dalam masalah pengaturcaraan linear adalah persamaan dan keadaan bukan negatif dikenakan ke atas semua pembolehubah x j, maka ia dipanggil masalah pengaturcaraan linear dalam bentuk kanonik atau masalah pengaturcaraan linear kanonik (CLP).

di bawah sekatan

Untuk berpindah dari ZLP ke CLLP, adalah perlu untuk beralih daripada sekatan ketidaksamaan kepada sekatan kesaksamaan dan menggantikan pembolehubah yang tidak mematuhi syarat bukan negatif.

Peraturan untuk membawa ZLP ke bentuk kanonik:

1) jika sebelah kanan sekatan adalah negatif, maka sekatan ini harus didarab dengan -1;

2) jika terdapat ketidaksamaan antara sekatan, maka dengan memperkenalkan pembolehubah bukan negatif tambahan ia diubah menjadi kesamaan;

3) jika beberapa pembolehubah xk tidak mempunyai sekatan tanda, maka ia digantikan dalam fungsi objektif dan dalam semua sekatan dengan perbezaan antara dua pembolehubah bukan negatif baharu: xk=x * k - xl, di mana l ialah indeks ringkasan, x * k>=, xl >=0.

Mari kita lihat contoh. Mari kita bawa ke bentuk kanonik:

Mari kita perkenalkan pembolehubah meratakan x 4, x 5, x 6 ke dalam setiap persamaan sistem kekangan. Sistem akan ditulis dalam bentuk kesamaan, dan dalam persamaan pertama dan ketiga sistem sekatan, pembolehubah x 4, x 6 dimasukkan di sebelah kiri dengan tanda "+", dan dalam persamaan kedua x 5 dimasukkan dengan tanda “-”.

Sebutan bebas dalam bentuk kanonik mestilah positif; untuk melakukan ini, darabkan dua persamaan terakhir dengan -1:

Dalam bentuk kanonik penulisan masalah pengaturcaraan linear, semua pembolehubah yang termasuk dalam sistem kekangan mestilah bukan negatif. Mari kita anggap itu

Menggantikan ungkapan ini ke dalam sistem kekangan dan fungsi objektif dan menulis pembolehubah dalam susunan indeks menaik, kami memperoleh masalah pengaturcaraan linear yang dibentangkan dalam bentuk kanonik:

pengoptimuman pengaturcaraan linear simplex

Bentuk kanonik ZLP- masalah pengaturcaraan linear dalam bentuk ax = b dengan a ialah matriks pekali, b ialah vektor kekangan.

Tujuan perkhidmatan. Kalkulator dalam talian direka bentuk untuk peralihan PPP kepada KZLP. Membawa masalah kepada bentuk kanonik bermakna semua kekangan akan mempunyai bentuk kesamaan dengan memperkenalkan pembolehubah tambahan.
Jika kekangan tidak dikenakan ke atas mana-mana pembolehubah x j, maka ia digantikan dengan perbezaan pembolehubah tambahan, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Arahan. Pilih bilangan pembolehubah dan bilangan baris (bilangan kekangan). Penyelesaian yang terhasil disimpan dalam fail Word.

Bagaimana untuk mengurangkan masalah pengaturcaraan linear kepada bentuk kanonik

Model matematik ZLP dipanggil asas, jika kekangan di dalamnya dibentangkan dalam bentuk persamaan dengan syarat pembolehubah adalah bukan negatif.

Model matematik dipanggil berkanun, jika sistem kekangannya dibentangkan dalam bentuk sistem m persamaan bebas linear (kedudukan sistem r=m), sistem itu diperuntukkan asas unit, pembolehubah bebas ditakrifkan dan fungsi objektif dinyatakan dalam sebutan pembolehubah bebas. Dalam kes ini, sisi kanan persamaan adalah bukan negatif (b i ≥ 0).

Pembolehubah yang termasuk dalam salah satu persamaan sistem dengan pekali satu dan tiada dalam persamaan lain dipanggil asas yang tidak diketahui, dan semua yang lain - percuma.

Penyelesaian kepada sistem dipanggil asas, jika pembolehubah bebas di dalamnya adalah sama dengan 0, dan ia mempunyai bentuk:
X tapak = (0, 0; b 1 , …, b m), f(X tapak) = c 0

Penyelesaian asas ialah titik sudut bagi set penyelesaian sistem, i.e. mentakrifkan puncak poligon penyelesaian model. Antara penyelesaian tersebut ialah penyelesaian yang digunakan oleh fungsi objektif nilai optimum.

Penyelesaian asas dipanggil penyelesaian rujukan jika ia boleh diterima, i.e. semua sisi kanan persamaan sistem (atau ketaksamaan) adalah positif b i ≥ 0.

Bentuk padat model kanonik ialah:
AX = b
X ≥ 0
Z = CX(maks)

Konsep penyelesaian yang boleh diterima, kawasan penyelesaian yang boleh diterima, penyelesaian yang optimum masalah pengaturcaraan linear.
Definisi 1. Vektor X yang memenuhi sistem kekangan ZLP, termasuk keadaan bukan negatif, jika ada, dipanggil penyelesaian yang boleh diterima untuk ZLP.
Definisi 2. Set semua penyelesaian yang boleh diterima membentuk wilayah penyelesaian yang boleh diterima (ADA) PLP.
Definisi 3. Penyelesaian yang boleh dilaksanakan di mana fungsi objektif mencapai maksimum (atau minimum) dipanggil penyelesaian optimum.

Contoh No. 1. Kurangkan masalah LP berikut kepada bentuk kanonik: F(X) = 5x 1 + 3x 2 → maks di bawah sekatan:
2x 1 + 3x 2 ≤20
3x 1 + x 2 ≤15
4x 1 ≤16
3x 2 ≤12
Model ditulis dalam bentuk piawai. Mari kita perkenalkan baki pembolehubah bukan negatif x 3 , x 4 , x 5 , x 6 , yang kita tambah pada bahagian kiri kekangan ketaksamaan. Kami memperkenalkan semua pembolehubah tambahan ke dalam fungsi sasaran dengan pekali sama dengan sifar:
Dalam ketaksamaan makna pertama (≤), kami memperkenalkan pembolehubah asas x 3 . Dalam ketaksamaan makna ke-2 (≤) kami memperkenalkan pembolehubah asas x 4 . Dalam ketaksamaan ketiga kami memperkenalkan pembolehubah asas x 5 . Dalam ketaksamaan ke-4 - pembolehubah asas x 6. Kami memperoleh bentuk kanonik model:
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → maks

Contoh No. 2. Cari dua penyelesaian rujukan sistem
x 1 + 2x 4 - 2x 5 = 4
x 3 + 3x 4 + x 5 = 5
x 2 + 3x 5 = 2