Pemrograman linier dalam presentasi ekonomi. Pemrograman linier

Slide 14

Mari kita asumsikan bahwa produk tipe A, - produk tipe B dan - produk tipe C akan diproduksi.Kemudian, untuk produksi sejumlah produk seperti itu, perlu menghabiskan jam mesin peralatan penggilingan. Karena total dana waktu kerja mesin jenis ini tidak boleh melebihi 120, ketidaksetaraan harus dipenuhi

slide 15

Dengan alasan yang sama, kita dapat membuat sistem kendala

slide 16

Sekarang mari kita membuat fungsi tujuan. Keuntungan dari penjualan produk tipe A adalah 10, dari penjualan produk tipe B -14 dan dari penjualan produk tipe C-12 Total keuntungan dari penjualan semua produk adalah

Slide 17

Jadi, kita sampai pada LLP berikut: Di antara semua solusi non-negatif dari sistem ketidaksetaraan, diperlukan untuk menemukan solusi yang fungsi tujuannya mengambil nilai maksimum.

Slide 18

Contoh 2

Produk dari pabrik susu adalah susu, kefir dan krim asam yang dikemas dalam wadah. Untuk produksi 1 ton susu, kefir dan krim asam, dibutuhkan masing-masing 1010.1010 dan 9450 kg susu. Sedangkan biaya waktu kerja saat menumpahkan 1 ton susu dan kefir adalah 0,18 dan 0,19 jam mesin. Pada kemasan 1 ton krim asam, mesin khusus digunakan selama 3,25 jam.

Slide 19

Secara total, pabrik dapat menggunakan 136.000 kg susu untuk produksi produk susu murni. Peralatan utama dapat ditempati selama 21,4 jam mesin, dan mesin pengemas krim asam selama 16,25 jam. Keuntungan dari penjualan 1 ton susu, kefir, dan krim asam masing-masing adalah 30, 22, dan 136 rubel. Pabrik harus menghasilkan setidaknya 100 ton susu kemasan setiap hari. Tidak ada batasan pada produksi produk lain.

Slide 20

Diperlukan untuk menentukan produk apa dan berapa jumlah yang harus diproduksi pabrik setiap hari agar keuntungan dari penjualannya maksimal. Buatlah model matematis dari permasalahan tersebut.

slide 21

Larutan

Biarkan tanaman menghasilkan berton-ton susu, berton-ton kefir, dan berton-ton krim asam. Kemudian dia membutuhkan satu kg susu. Karena pabrik dapat menggunakan tidak lebih dari 136.000 kg susu setiap hari, ketidaksetaraan harus dipenuhi

slide 22

Batas waktu pengemasan susu dan kefir serta pengemasan krim asam. Karena setidaknya 100 ton susu harus diproduksi setiap hari, maka. Dari segi ekonomi

slide 23

Keuntungan total dari penjualan semua produk sama dengan rubel. Jadi, kita sampai pada masalah berikut: di bawah kendala Karena fungsi tujuan adalah linier dan kendala diberikan oleh sistem pertidaksamaan, masalah ini adalah LLP.

slide 24

Masalah campuran.

Ada dua jenis produk yang mengandung nutrisi (lemak, protein, dll.)

Slide 25

Meja

slide 26

Larutan

Total biaya diet di bawah batasan, dengan mempertimbangkan nutrisi minimum yang dibutuhkan

Slide 27

Pernyataan matematis dari masalah: buat diet harian yang memenuhi sistem pembatasan dan meminimalkan fungsi target. Secara umum, kelompok masalah campuran mencakup masalah menemukan set termurah dari bahan awal tertentu yang menghasilkan campuran dengan sifat yang diinginkan. Campuran yang dihasilkan harus mengandung n komponen yang berbeda dalam jumlah tertentu, dan komponen itu sendiri merupakan konstituen dari m bahan awal.

Slide 28

Mari perkenalkan notasinya: -jumlah bahan ke-j yang termasuk dalam campuran; -harga bahan tipe-j; adalah kandungan minimum yang dibutuhkan dari komponen ke-i dalam campuran. Koefisien menunjukkan berat jenis komponen ke-i dalam satuan material ke-j

Slide 29

Model ekonomi-matematis dari masalah.

Fungsi tujuan adalah total biaya campuran, dan batasan fungsional adalah pembatasan kandungan komponen dalam campuran: campuran harus mengandung komponen dalam volume tidak kurang dari yang ditentukan.

slide 30

Tugas pemotongan

Di pabrik garmen, kain dapat dipotong dengan beberapa cara untuk menghasilkan potongan garmen yang diinginkan. Biarkan suku cadang tipe ke-i diproduksi dengan varian pemotongan ke-j, dan jumlah pemborosan dalam varian pemotongan ini adalah pemborosan. Buatlah model matematis dari permasalahan tersebut.

Slide 31

Larutan. Asumsikan sesuai varian ke-J, kain yang dipotong ratusan. Karena saat memotong kain menurut opsi ke-j, diperoleh bagian dari tipe ke-i, untuk semua opsi pemotongan dari kain yang digunakan, jumlah total limbah untuk semua opsi pemotongan adalah

Slide 35

Tugas utama LP

def.4. Utama, atau kanonik, LLP adalah tugas yang terdiri dari menentukan nilai fungsi tujuan, asalkan sistem kendala disajikan sebagai sistem persamaan:

slide 36

Jika diperlukan untuk kenyamanan atau arti tugas untuk beralih dari satu bentuk rekaman ke bentuk lainnya, maka lakukan sebagai berikut. Jika Anda perlu menemukan fungsi minimum, maka Anda dapat mencari maksimum dengan mengalikan fungsi tujuan dengan (-1). Batasan tipe pertidaksamaan dapat diubah menjadi persamaan dengan menambahkan variabel tambahan non-negatif ke sisi kirinya, dan batasan tipe-pertidaksamaan dapat diubah menjadi batasan persamaan dengan mengurangkan variabel non-negatif tambahan dari sisi kirinya.

Slide 41

Desain pendukung disebut non-degenerate jika mengandung m komponen positif. Kalau tidak, itu disebut merosot. Rencana di mana fungsi tujuan LLP mengambil nilai maksimum (minimum) disebut optimal.

Lihat semua slide

Perkenalan

Pemrograman linier sebagai cabang riset operasi memiliki sejarah hampir empat puluh tahun. Pengenalan teknologi komputer memberikan dorongan yang signifikan untuk penelitian di bidang matematika ini. Sejumlah algoritme untuk memecahkan masalah pemrograman linier dikembangkan, dan pada tahun-tahun berikutnya program dan paket perangkat lunak dibuat, terutama untuk komputer besar. Sebagian besar literatur tentang pemrograman linier di negara kita dirilis pada tahun 60an - 70an. Penelitian di bidang ini (baik teoretis maupun terapan) berlanjut hingga saat ini.

Metode pemrograman linier terbukti sangat efektif untuk memecahkan beberapa masalah dari bidang riset operasi. Kami memahami kata "pemrograman" sebagai perencanaan, dan ini menentukan sifat aplikasi yang dipertimbangkan. Gagasan utama pemrograman linier muncul selama Perang Dunia Kedua sehubungan dengan pencarian strategi optimal dalam melakukan operasi militer. Sejak itu, mereka telah menemukan aplikasi luas dalam industri, perdagangan, dan administrasi - baik secara lokal maupun nasional. Metode ini dapat memecahkan banyak (walaupun tidak semua) masalah yang berkaitan dengan efisiensi penggunaan sumber daya yang terbatas.

Metode dan model matematika terkenal, tersebar luas dan digunakan dengan berbagai nama - metode matematika dalam pengambilan keputusan; metode riset operasi; metode ekonomi dan matematika; metode sibernetika ekonomi; metode kontrol optimal, matematika terapan dalam ekonomi dan organisasi produksi, dll. Dalam banyak publikasi tentang topik ini (kurang lebih komprehensif), mereka dipertimbangkan dalam berbagai kombinasi.

Riset operasi adalah disiplin ilmu yang berhubungan dengan pengembangan dan penerapan praktis metode untuk manajemen yang paling efektif dari berbagai sistem organisasi.

Manajemen sistem apa pun diimplementasikan sebagai proses yang mematuhi hukum tertentu. Pengetahuan mereka membantu menentukan kondisi yang diperlukan dan cukup untuk pelaksanaan proses ini. Untuk melakukan ini, semua parameter yang mencirikan proses dan kondisi eksternal harus dikuantifikasi dan diukur. Oleh karena itu, tujuan riset operasi adalah pembenaran kuantitatif atas keputusan yang dibuat pada organisasi manajemen.

Tujuan dari setiap pemodelan adalah untuk mempelajari objek pada awalnya secara kualitatif, dan kemudian, ketika informasi terakumulasi dan model berkembang, pada tingkat kuantitatif yang semakin akurat.

Pertimbangan ini dapat diilustrasikan dengan contoh sederhana. Ada (dan masih ada) metode "teori probabilitas" sebagai kelas luas model matematika yang beroperasi dengan konsep "probabilitas", "peristiwa acak", "variabel acak", "harapan matematis (nilai rata-rata) dari variabel acak ", "dispersi (hamburan)" dan lain-lain. Di perbatasan abad XIX dan XX. sebuah objek baru muncul - sistem komunikasi telepon yang diaktifkan, yang dengannya konsep "aplikasi untuk koneksi", "penolakan", "waktu tunggu koneksi", "switching" dan karakteristik lain dari sistem dikaitkan.

Di usia 20-an. A.K. Erlang menghubungkan metode dan objek ini; sebagai hasilnya, model proses probabilistik matematis dalam jaringan telepon yang dialihkan telah dibuat, yang beroperasi dengan konsep "aliran pesanan", "waktu tunggu rata-rata", "panjang antrian rata-rata untuk layanan", "variasi waktu tunggu", "kegagalan probabilitas", dll. Perkembangan lebih lanjut dari arah ilmiah ini menunjukkan keberhasilan dasar konseptual model ini, kemungkinan desainnya yang luas. Model berkembang menjadi metode untuk mempelajari sistem yang kompleks - "teori antrian", yang terminologi dan dasar konseptualnya diabstraksikan dari asosiasi dengan jaringan telepon dan memperoleh karakter teoretis umum. Dan sekarang model baru dapat dibangun dengan menerapkan teori antrian ke objek lain (proses produksi, sistem operasi komputer, arus lalu lintas, dll).

Dengan demikian, di satu sisi metode didefinisikan jika seperangkat model yang homogen dikembangkan, yaitu cara mempertimbangkan berbagai objek dalam satu aspek, dan di sisi lain, objek tersebut diketahui semakin dalam, semakin banyak model objek yang dikembangkan. . Pada saat yang sama, sifat ganda model mengarah pada dualisme dasar konseptual pemodelan, yang mencakup konsep umum (dari "metode") dan spesifik (dari "objek").

Riset operasi adalah seperangkat metode matematika terapan yang digunakan untuk memecahkan masalah organisasi praktis (termasuk ekonomi). Ini adalah disiplin ilmu yang kompleks. Kisaran masalah yang dipelajari olehnya tidak cukup didefinisikan. Terkadang riset operasi dipahami dengan sangat luas, termasuk sejumlah metode matematika murni, terkadang, sebaliknya, sangat sempit - sebagai teknik praktis untuk memecahkan daftar masalah yang ditentukan secara ketat menggunakan model ekonomi dan matematika.

Metode utama riset operasi adalah analisis sistematis tentang tindakan yang bertujuan (operasi) dan penilaian komparatif yang objektif (khususnya, kuantitatif) dari kemungkinan hasil dari tindakan ini.

Di antara kelas masalah yang paling penting dalam riset operasi adalah masalah manajemen inventaris, alokasi sumber daya dan penugasan (masalah distribusi), masalah antrian, masalah penggantian peralatan, pemesanan dan koordinasi (termasuk teori penjadwalan), permusuhan (misalnya, permainan), masalah pencarian, dan lain-lain. Di antara metode yang digunakan adalah pemrograman matematika (linier, non-linier, dll.), persamaan diferensial dan perbedaan, teori graf, proses Markov, teori permainan, teori solusi (statistik), teori pengenalan pola dan a jumlah orang lain.

Dipercayai bahwa riset operasi berasal dari malam Perang Dunia Kedua, ketika di Inggris sekelompok spesialis dibentuk di stasiun radar untuk memecahkan masalah teknis dengan bantuan matematika. Mereka berfokus pada membandingkan keefektifan cara memecahkan masalah, menemukan solusi optimal. Partisipasi dalam kelompok perwakilan dari berbagai spesialisasi ini telah ditentukan sebelumnya secara komprehensif, atau, seperti yang mereka katakan sekarang, pendekatan sistematis. Saat ini, ratusan lembaga dan kelompok penelitian di belasan negara sedang bekerja ke arah ini. Perhimpunan Riset Operasi diselenggarakan oleh Federasi Internasional (IFORS).

Ilmuwan Rusia L.V. Kantorovich, N.P. Buslenko, E.S. Wenzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin dan masih banyak lagi.

Kontribusi yang signifikan untuk pembentukan dan pengembangan riset operasi dibuat oleh ilmuwan asing R. Akof, R. Bellman, G. Danzig, G. Kuhn, J. Neumann, T. Saaty, R. Churchman, A. Kofman, dan lain-lain.

Metode penelitian operasi, seperti metode matematika lainnya, selalu menyederhanakan, sampai batas tertentu, memperkeruh masalah, mencerminkan proses nonlinier dengan model linier, sistem stokastik dengan deterministik, dll. Oleh karena itu, seseorang tidak boleh melebih-lebihkan nilai metode kuantitatif penelitian operasi, atau meremehkannya. , merujuk pada contoh keputusan yang tidak berhasil. Definisi paradoks diketahui, yang diberikan oleh seorang spesialis besar Amerika di bidang ini

T. A. Saaty: “Riset Operasi adalah seni memberikan jawaban yang buruk untuk pertanyaan praktis yang dijawab bahkan lebih buruk dengan cara lain.”

KULIAH TEKNOLOGI INDUSTRI DAN KEWIRAUSAHAAN INDUSTRI TENGAH TENGAH

Saya setuju

Wakil Direktur Pendidikan

« » 200 G .

LATIHAN

untuk desain kursus

dalam mata pelajaran "Metode Matematika"

Murid: Sergeev Evgeny Anatolyevich.

Tema proyek: "Pemrograman linier, pemecahan masalah dengan metode simpleks".

CATATAN PENJELASAN

1. Perkenalan
2. Bagian teoritis
3. Bagian praktis

Tugas dan solusinya:

Tugas satu:

Selesaikan masalah simpleks dengan metode:

F = 2X1 +3X2 → maks

3.1.2 Tugas dua:

Perusahaan memproduksi dua jenis produk. Jenis bahan baku, cadangannya, tingkat konsumsi bahan baku per y. e.setiap jenis produk, keuntungan produksi dari penjualan produk diberikan dalam tabel:

3.1.3. Tugas tiga:

Perusahaan memproduksi 3 jenis produk, sedangkan menggunakan 3 jenis bahan baku. Stok bahan baku, tingkat konsumsinya, dan keuntungan dari penjualan setiap produk ditunjukkan pada tabel:

Bagaimana seharusnya produksi direncanakan untuk memaksimalkan keuntungan?

3.1.4. Tugas empat:

Untuk pembuatan 4 jenis produk, digunakan 3 jenis bahan baku. Stok bahan baku, tingkat konsumsinya, dan keuntungan dari penjualan setiap produk ditunjukkan pada tabel:

Bagaimana seharusnya produksi direncanakan untuk memaksimalkan keuntungan?

3. Kesimpulan

4. Bibliografi

Ketua komisi siklus/ Baranov V.A.

Manajer proyek kursus/ Karpushkin A.G.

Tanggal penerbitan tugas: Tanggal akhir:

« » 2007 « » 2007

METODE SIMPLEKS

Metode simpleks pertama kali diusulkan oleh ilmuwan Amerika J. Danzig pada tahun 1949, namun, pada tahun 1939, ide metode tersebut dikembangkan oleh seorang ilmuwan Rusia.

L V. Kantorovich.

Metode simpleks, yang memungkinkan penyelesaian masalah pemrograman linier apa pun, bersifat universal. Saat ini digunakan untuk perhitungan komputer, tetapi contoh sederhana menggunakan metode simpleks juga dapat diselesaikan secara manual.

Untuk mengimplementasikan metode simpleks - peningkatan berurutan dari solusi - perlu menguasai tiga utama

elemen:

Sebuah cara untuk menentukan awal yang diijinkan

solusi dasar dari masalah;

Aturan transisi ke solusi terbaik (lebih tepatnya, bukan yang terburuk);

Kriteria untuk memeriksa optimalitas solusi yang ditemukan.

Untuk menggunakan metode simpleks, masalah pemrograman linier harus direduksi menjadi bentuk kanonis, yaitu sistem kendala harus disajikan dalam bentuk persamaan.

Pengecualian Jordan Biasa

Pertimbangkan sistem persamaan linier m dengan n yang tidak diketahui

a11 x1 + a12 x2 + … + a1n xn = b1,

am1 x1 + am2 x2 + … + amn xn = bm.

Kami menulis sistem ini dalam bentuk tabel

Langkah Ordinary Jordan Elimination (OJI) yang dilakukan pada tabel tertentu dengan elemen penyelesaian aij ≠ 0 dengan baris penyelesaian I dan kolom penyelesaian j adalah operasi penyelesaian persamaan

bi = ai1 x1 + ai2 x2 + … + aij xj + … + ain xn

sehubungan dengan xj, mensubstitusikan solusi ini ke dalam sistem asli, dan menulis sistem yang baru diperoleh dalam bentuk tabel baru.

Sangat mudah untuk memeriksa apakah tabel baru akan terlihat

di mana brs = ars aij - arj ais (i ≠ r, j ≠ s),

dan semua elemen tabel harus dibagi dengan aij .

Jadi, satu langkah Jordan Elimination (JJI) mengubah tabel asli menjadi tabel baru sesuai dengan skema yang terdiri dari 5 aturan berikut:

1) elemen yang memungkinkan diganti dengan satu

2) elemen yang tersisa dari kolom penyelesaian j tetap tidak berubah.

3) elemen yang tersisa dari string penyelesaian saya hanya mengubah tanda-tandanya.

4) sisa elemen brs dihitung dengan rumus brs = ars aij - arj ais

5) semua elemen tabel baru dibagi dengan elemen penyelesaian aij.

Contoh 1. Untuk tabel

Pengecualian Jordan memungkinkan untuk berpindah dari sistem bidang koordinat Cartesian yang diambil secara acak ke sistem baru di mana koordinat titik adalah penyimpangannya dari sistem bidang yang lebih menarik untuk masalah tertentu.

Pengecualian Jordan yang Dimodifikasi

Jika sistem persamaan awal ai1 x1 + ai2 x2 + … + ain xn = bi, di mana i = 1,m,

tulis sebagai -ai1 (-x1) - ai2 (-x2) - ... - ain (-xn) = bi

dan membuat tabel

yang diperoleh sesuai aturan 1 - 5 GOG dengan satu-satunya perubahan aturan 2 dan 3 mengubah peran:

1) elemen yang tersisa dari string permisif tetap tidak berubah

2) elemen yang tersisa dari kolom penyelesaian hanya mengubah tandanya

Pertimbangkan sistemnya

2X1 + 3X2 - 5X3 = 16 = b1,

3X1 - 2X2 + 4X3 = 36 = b2,

5X1 + 7X2 - 11X3 = 44 = b3.

Mari kita tulis dalam bentuk tabel

Ekstrem dari fungsi linier

Biarkan masalah pemrograman linier umum dipertimbangkan. Metode komputasi LP didasarkan pada teorema fundamental berikut.

Dalil. Jika masalah pemrograman linier memiliki solusi optimal

(selalu di daerah yang dibatasi, dan di daerah yang tidak dibatasi tergantung pada batasan fungsi Z), maka itu berimpit dengan setidaknya salah satu solusi pendukung dari sistem persamaan restriktif.

Menurut teorema ini, alih-alih mempelajari kumpulan solusi layak yang tak terbatas untuk menemukan solusi optimal yang diinginkan di antara mereka, perlu mempelajari hanya sejumlah solusi pendukung yang terbatas.

Teorema ini menyatakan bahwa setidaknya ada satu solusi optimal pendukung, namun dalam masalah mungkin ada beberapa solusi optimal pendukung (optimum alternatif).

Oleh karena itu, diagram skematik untuk menyelesaikan masalah program linier adalah sebagai berikut:

1. Dengan bantuan ZhI kami akan menemukan semua solusi dukungan sistem.

a11 x1 + a12 x2 + … + a1n xn = b1 ,

……...................

ak1 x1 + ak2 x2 + … + akn xn = bk ,

ak+1,1 x1 + ak+1,2 x2 + … + ak+1n xn ≤ bk+1 ,

……...................

am1 x1 + am2 x2 + … + amn xn ≤ bm .

2. Hitung masing-masing nilai fungsi Z, ditentukan oleh rasio.

Z = c1 x1 + c2 x2 + … + cn xn.

3. Kami memilih Z ekstrim dari mereka.

Perlu dicatat bahwa mungkin ada sejumlah besar solusi referensi, sehingga perlu dilakukan pencacahan solusi referensi yang teratur, mencapai pada

setiap langkah perubahan monoton dari fungsi Z.

Gagasan peningkatan solusi berturut-turut seperti itu tertanam dalam metode komputasi utama untuk memecahkan masalah pemrograman linier, yang disebut metode simpleks.

Metode simpleks berdasarkan tabel lengkap

Pernyataan masalah penentuan rentang produk yang optimal

Perusahaan dapat memproduksi dua jenis produk A dan B, dengan sumber daya bahan besi dan baja yang terbatas untuk pembuatannya, masing-masing dalam jumlah 350 dan 392 kg dan peralatan dalam jumlah 408 jam mesin. Data yang disajikan dalam bentuk tabel mencirikan biaya masing-masing dari tiga jenis sumber daya yang tercantum untuk pembuatan satu produk A dan B.

Diperlukan untuk menentukan berapa banyak produk A dan B yang harus diproduksi oleh perusahaan untuk mencapai keuntungan terbesar.

Kami memperkenalkan X1 dan X2 yang tidak diketahui yang diperlukan, yang menunjukkan jumlah produk A dan B yang harus diproduksi oleh perusahaan.

Maka secara matematis masalahnya dapat dirumuskan sebagai berikut.

Di antara himpunan solusi non-negatif dari sistem ketidaksetaraan

14X1 + 5X2 ≤ 350, (1,1)

14X1 + 8X2 ≤ 392,

6X1 + 12X2 ≤ 408,

menemukan solusi yang fungsi

Z = 10 X1 + 5 X2

mencapai nilai tertingginya.

Solusi geometris dari masalah

Pertama-tama, mari kita buat domain solusi layak yang sesuai dengan sistem pertidaksamaan.

Untuk melakukan ini, ganti setiap ketidaksetaraan dengan persamaan

14X1 + 5X2 = 350, (garis lurus ke-1),

14X1 + 8X2 = 392, (baris ke-2),

6X1 + 12X2 = 408, (garis lurus ke-3),

membangun garis batas. Mempertimbangkan bahwa X1 ≥ 0 dan X2 ≥ 0, kami memperoleh bagian bidang yang diarsir, yang membentuk poligon solusi OABCD (Gbr. 1).

Kemudian kami membangun garis level 10X1 + 5X2 = 0 dan vektor (10; 5), yang saling tegak lurus. Sangat mudah untuk menunjukkan bahwa vektor memberikan arah kenaikan terbesar dari fungsi linier.

Benar-benar

Z0 \u003d 10X10 + 5X20 \u003d 10 * 0 + 5 * 0 \u003d 0,

ZA \u003d 10X1A + 5X2A \u003d 10 * 0 + 5 * 34 \u003d 170,

ZD = 10X1D + 5X2D = 10 * 25 + 5 * 0 = 250 dst.

Dari semua garis level, kami memilih dua, yang satu melewati titik 0 dan memberikan nilai min dari fungsi Z, dan yang lainnya melewati titik C dan fungsi Z untuk mengambil nilai maks. Garis level ini disebut garis referensi.

Beras. 1

Titik C dibentuk oleh baris pertama dan kedua. Oleh karena itu, selesaikan sistem persamaan

14Xl + 5X2 = 350,

14X1 + 8X2 = 392,

tentukan koordinat titik C

X1 = 20, X2 = 14,

sedangkan Zmax \u003d 10 * 20 + 5 * 14 \u003d 270 rubel.

Jadi, keuntungan maksimal 270 rubel. akan diterima jika perusahaan menghasilkan 20 produk tipe A dan 14 produk tipe B.

Menemukan maksimum dari fungsi linier

Metode simpleks untuk memecahkan masalah pemrograman linier didasarkan, dengan beberapa tambahan, pada metode eliminasi berturut-turut yang dianalisis sebelumnya, yang merupakan sekumpulan algoritme komputasi yang mudah digunakan berdasarkan aplikasi sekuensial dari transformasi identik (simpleks) dari sistem persamaan.

Menambahkan ruas kiri pertidaksamaan

14X1 + 5X2 ≤ 350,

14X1 + 8X2 ≤ 392,

6X1 + 12X2 ≤ 408,

beberapa nilai non-negatif Yj ≥ 0 (i = 1, 2, 3), (1.2)

disebut variabel penyama atau dasar, kami mengubahnya menjadi persamaan:

Selain itu, dapat ditunjukkan bahwa setiap solusi dari sistem pertidaksamaan (1.1) sesuai dengan solusi unik dari sistem persamaan (1.3) dan pertidaksamaan (1.2) dan sebaliknya.

Masing-masing variabel Y1, Y2, Y3 hanya termasuk dalam satu persamaan dan bergantung pada variabel X1 dan X2, yang kita sebut bebas.

Sistem (1.3) sesuai dengan solusi dasar awal yang dapat diterima X1 = X2 = 0;

Y1 = 350; Y2 = 392; Y3 = 408 dan Z = 0.

Kami melakukan transformasi identik pertama dari sistem persamaan (1.3). Kami memilih kolom penyelesaian yang sesuai dengan elemen negatif terkecil di baris Z, karena telah ditetapkan secara teoritis bahwa, dalam kondisi yang sama, peningkatan yang lebih besar dalam fungsi Z dapat diharapkan. . Di persimpangan kolom dan baris yang dipilih adalah nomor resolusi.

Kami membagi persamaan pertama dengan nomor resolusi dan menuliskan persamaan yang dihasilkan. Mengalikan persamaan ini dengan 14, 6 dan -10 dan mengurangkan masing-masing dari persamaan sistem ke-2, ke-3 dan ke-4 (1.3), kita mendapatkan sistem berikut (1.4):

Transformasi identik seperti itu, di mana pilihan bilangan penyelesaian dibuat sesuai dengan aturan yang ditunjukkan, akan disebut transformasi simpleks.

Dengan demikian, transformasi simpleks dilakukan sesuai dengan aturan berikut:

1. Pilih kolom pengaktifan yang sesuai dengan elemen negatif terkecil di baris Z.

2. Baris penyelesaian dipilih yang sesuai dengan rasio positif terkecil dari elemen-elemen di sisi kanan persamaan dengan elemen kolom penyelesaian yang sesuai. Di persimpangan kolom penyelesaian dan baris penyelesaian adalah nomor penyelesaian.

3. Elemen string permisif dibagi dengan nomor permisif.

4. Elemen dari semua baris lainnya dihitung menurut rumus:

Dari sistem (1.4) kita menemukan solusi dasar kedua yang dapat diterima Х2 = Yl = 0; X1 = 25; Y2 = 42; Y3 = 258, yang sesuai dengan peningkatan nilai baru dari fungsi Z = 250.

Dengan demikian, proses transformasi simpleks yang berurutan adalah proses perbaikan solusi yang berurutan. Di mana:

1. Jika setidaknya ada satu elemen negatif di garis Z dan

a) setidaknya ada satu elemen positif di kolom penyelesaian, maka solusinya dapat diperbaiki;

b) jika kolom penyelesaian tidak mengandung elemen positif, maka fungsi Z bertambah tanpa batas.

2. Jika semua elemen pada baris Z adalah non-negatif, maka solusi optimal telah tercapai.

Ini adalah kondisi yang cukup untuk keberadaan rencana solusi optimal.

Pada sistem (1.4), koefisien pada X2 pada baris Z adalah negatif, sehingga kolom kedua akan menyelesaikan. Kami menemukan bahwa baris kedua akan permisif. Selanjutnya, kami melakukan transformasi simpleks sistem (1.4) sesuai dengan aturan yang ditunjukkan:

X1 + 8/42 Y1 - 5/42 Y2 = 20,

X2 - 1/3 Y1 + 1/3 Y2 = 14,

20/7 Y1 - 23/7 Y2 + Y3 = 120,

10/42 Y1 + 20/42 Y2 + Z = 270, (1,5)

Karena semua elemen pada baris-Z adalah non-negatif, rencana ini optimal. Dalam hal ini, Yl = Y2 = 0; X1 = 20; X2 = 14 dan Zmax = 270.

Melakukan transformasi simpleks dikaitkan dengan perhitungan yang telaten dan seringkali agak rumit. Perhitungan ini dapat sangat disederhanakan dengan menggunakan apa yang disebut tabel simpleks untuk menyelesaikan masalah.

Setiap transformasi simpleks dari sistem direduksi menjadi transisi dari satu tabel simpleks ke yang lain.

Menurut sistem persamaan asli (1.3), kami menyusun tabel simpleks pertama (Tabel 1.1).

Tabel 1.1

Kolom pertama adalah kolom variabel dasar, kolom kedua berisi koefisien bebas ruas kanan persamaan (1.3), baris pertama berisi semua variabel, kolom terakhir adalah kolom kontrol dan koefisien di dalamnya sama dengan jumlah semua koefisien pada baris tersebut.

Dari Tabel. 1.1 kita memiliki solusi pertama yang dapat diterima dari sistem (1.3) X1 = X2 = 0, Y1 = 350,

Y2 = 392, Y3 = 408, Z = 0, yang sesuai dengan simpul O (0,0) poligon solusi layak OABCD (Gbr. 1).

Transisi ke tabel simpleks kedua (Tabel 1.2) dilakukan sesuai dengan aturan yang ditentukan dalam paragraf ini untuk transformasi simpleks dari sistem persamaan, sedangkan variabel penyelesaian X1 menjadi basis alih-alih variabel penyelesaian Y1. 1.2.

Tabel 1.2

Setelah melengkapi tabel 1.2 perlu untuk memeriksa kebenaran pengisiannya, yang kami rangkum koefisiennya dengan baris dan jumlah ini harus sama dengan koefisien di sel yang sesuai dari kolom kontrol. Dari Tabel. 1.2 solusi valid kedua adalah X1 = 25, X2 = 0, Y1 = 0, Y2 = 42, Y3 = 258 dan Z = 250.

Sangat mudah untuk melihat bahwa tabel ini sesuai dengan sistem (1.4), dan solusi referensi

X1 = 25, X2 = 0 sesuai dengan simpul D(25,0) dari poligon solusi.

Karena ada elemen negatif di baris-Z, kami meningkatkan solusinya, yang kami buat tabel simpleks. 1.3.

Tabel 1. 3

* Catatan. Untuk kesederhanaan perhitungan, harus diingat bahwa di tabel baru, sebagai pengganti elemen kolom yang memungkinkan (kecuali untuk elemen yang memungkinkan), ada nol. Jika ada nol di garis penyelesaian, kolom yang sesuai dipindahkan ke tabel baru tanpa perubahan:

Karena tidak ada elemen negatif pada garis Z, solusi ini akan optimal.

Tab. 1.3 sesuai dengan sistem persamaan (1.5) dan solusi optimal Х1 = 20,

X2 = 14 dan Zmax = 270 dan simpul C (20,14) dari poligon solusi yang dapat diterima OABCD.

Tabel memanjang yang berisi semua variabel di baris pertama, berkat adanya kolom kontrol, memungkinkan Anda mengontrol kebenaran pengisian tabel dan menghindari kesalahan aritmatika.

Metode simpleks berdasarkan tabel terpotong

Perhatikan sistem persamaan (1.3) dan tuliskan dalam bentuk tabel 1.4

Tabel 1.4

Kami menulis variabel dasar (BP) di kolom pertama, dan variabel bebas (SP) di baris pertama. Selanjutnya, transisi ke tabel baru 1.5 dilakukan sesuai aturan:

1) tukar SP dan BP

2) di tempat elemen penyelesaian ada nilai timbal balik untuk itu

3) kami membagi elemen garis penyelesaian dengan nomor penyelesaian

4) kami membagi elemen kolom penyelesaian dengan kolom penyelesaian dan mengubah tandanya

5) elemen yang tersisa ditemukan seperti pada bab “Menemukan maksimum fungsi linier”, aturan 4 (aturan persegi panjang untuk OGI). Kami mendapatkan tabel 1.5.

Tabel 1.6

Kami mendapat rencana optimal Zmax = 270 dengan X1 =20, X2 = 14, dan sumber daya peralatan ternyata lebih dari 120 jam mesin.

Memecahkan masalah pemrograman linier

Temukan fungsi tujuan maksimum

di bawah batasan

14x + 5y ≤ 350

Memecahkan masalah menggunakan program Microsoft Unggul.

Mari kita tetapkan A3 dan B3 ke nilai variabel x dan y.

Di sel C4, masukkan fungsi tujuan

Di sel A7:A9 kami memperkenalkan bagian kiri dari batasan

dan di sel B7:B9 - bagian kanan dari batasan.

Setelah itu, pilih perintah Melayani, Menemukan solusi(Alat, Pemecah) dan isi kotak dialog yang terbuka Mencari solusi ( Pemecah) seperti yang ditunjukkan pada Gambar. 2. Setelah menekan tombol Berlari Jendela (Selesaikan) terbuka Hasil Pencarian Solusi(Hasil Pemecah), yang melaporkan bahwa solusi telah ditemukan (Gbr. 3).

Beras. 2. Menemukan solusi

Beras. 3. Hasil pencarian solusi

Solusi geometris dari masalah menggunakan program MATHCAD 2000.

1. Tuliskan dalam bentuk y = kx + b persamaan garis lurus yang membatasi rentang nilai variabel yang dapat diterima. Untuk memasukkan dan menyelesaikan batasan 14x + 5y ≤ 350 sehubungan dengan y, masukkan sisi kiri pertidaksamaan, tekan tombol Ctrl dan tekan tombol = secara bersamaan, tahan yang sebelumnya hingga tanda tebal = muncul, tandai variabel y dengan kotak pilihan, klik di menu Simbolik (Simbol) pada baris Selesaikan (Hitung) - hasil perhitungan akan ditampilkan di dokumen kerja di sebelah kanan persamaan; masukkan nama fungsi (dalam contoh ini, y1(x)) dan berikan ekspresi yang dihasilkan padanya. Dengan demikian, persamaan salah satu garis lurus, yang membatasi rentang nilai yang dapat diterima, ditentukan. Masukkan batasan lainnya dengan cara yang sama. Masukkan persamaan 10x + 5y = garis level C (garis referensi) dari fungsi target. Lanjutkan dengan cara yang sama seperti saat memasukkan batasan, tetapi sebelum menyelesaikan persamaan untuk y, tetapkan nilai pada konstanta C.
2. Gambarlah garis lurus yang sesuai pada grafik dan tentukan luas solusi yang dapat diterima dari sistem tersebut.
3. Dengan mengubah nilai konstanta C, misalnya C = 100.150.200.250,..., amati pergerakan garis acuan dan rumuskan kesimpulan tentang solvabilitas masalah.
4. Jika soal tersebut memiliki solusi yang unik, temukan titik di mana Z = Zmax. Dalam contoh kita, fungsi tujuan maksimum dicapai pada titik perpotongan garis 14x + 5y = 350 dan 7x + 14y = 196. Temukan koordinat titik tersebut menggunakan fungsi Temukan.
5. Hitung nilai fungsi tujuan pada titik yang ditemukan.

14x + 5y = 350 (-14/5)x + 70 y1(x):= (-14/5)x + 70

7x + 4y = 196 (-7/4)x + 49 y2(x):= (-7/4)x + 49

x + 2y = 68 (-1/2)x + 34 y3(x):= (-1/2)x + 34

10x + 5y = C -2x + (1/5)C y4(x):= -2x + (1/5)C

Beras. 4.

Temukan (x, y) → (20, 14)

f(x, y): = 10x + 5y

fmin := f(20, 14)

Solusi analitis dari masalah menggunakan program MATHCAD 2000.

Solusi analitis dari masalah di MathCAD jauh lebih sederhana.

1. Atur mode perhitungan otomatis.
2. Tulis masalah dengan x dan y arbitrer dan tetapkan nilai arbitrer (valid) sehingga program dapat mulai menghitung.

Z(x, y): = 10x + 5y

14x + 5x ≤ 360

M:=Maksimalkan(z,x,y) M=(20,14)Z(M0,M1)=270

Masalah memaksimalkan fungsi linier dengan adanya koefisien bebas negatif

Temukan maksimum dari fungsi linier

di bawah batasan

X1 – X2 ≤ 3,

2X1 – 3X2 ≤ 6,

X1 ≥ 0, X2 ≥ 0.

Kami menulis sistem dalam formulir

Y1 = -X1 + X2 + 3 ≥ 0

Y2 = X1 + X2 - 5 ≥ 0

Y3 = -2X1 + 3X2 + 6 ≥ 0

Y4 = -X2 + 6 ≥ 0

Mari kita membuat tabel.

Kami terus mengerjakan baris ke-2, karena elemen negatif belum hilang. Kami membuat SHMZhI dengan elemen penyelesaian -2. Kami mendapatkan meja.

Masalah minimisasi fungsi linier

Reduksi masalah minimalisasi menjadi masalah maksimalisasi fungsi linier

Kami mempertimbangkan solusi dari masalah menemukan fungsi linier maksimum dengan metode simpleks

W = c1 x1 + c2 x2 + … + cn xn.

Namun, dalam banyak masalah ekonomi diperlukan untuk menemukan fungsi linier minimum. Untuk ini cukup untuk menempatkan

W = -Z = -c1 x1 - c2 x2 - ... - cn xn

dan selesaikan masalah memaksimalkan fungsi W yang dihasilkan di bawah batasan yang sesuai. Karena jelas bahwa

Minimalkan Fungsi Linear

selama memenuhi larangan

7X1 + 2X2 ≥ 14,

5X1 + 6X2 ≤ 30,

3X1 + 8X2 ≥ 24,

X1 ≥ 0, X2 ≥ 0.

Solusi geometris dari masalah pada (Gbr. 5) dan itu sesuai dengan solusi optimal pada titik tersebut

C (48/11, 15/11) dan pada saat yang sama Zmin = -21/11.

Gambar 5. Solusi geometris dari masalah tersebut

Memperkenalkan variabel leveling Yi ≥ 0 dan fungsi W = -Z = 2X1 - 5X2 → maks, kami menulis masalahnya dalam formulir.

Y1 = 7X1 + 2X2 - 14,

Y2 = -5X1 - 6X2 + 30,

Y3 = 3X1 + 8X2 - 24,

Kami menulis sistem ini dalam bentuk tabel.

Kami menyingkirkan anggota bebas negatif di Y1 - baris, membuat SHMZhI dengan elemen penyelesaian "-50/8", kami mendapatkan tabel.

Karena tidak ada elemen negatif pada baris-W dan kolom 1-, kami mendapatkan solusi optimal X1 = 48/11, X2 = 15/11, Wmax - 21/11 atau Zmin = -Wmax = -21/11 ,

Bagian praktis

1. Selesaikan masalah tersebut dengan menggunakan metode simpleks.

X1 + 3X2 ≤ 300 F = 2X1 + 3X2 → maks

Larutan

X1 + 3X2 + X3 = 300 P - 2X1 - 3X2 = 0

X1 + X2 + X4 = 150

Jawab: X1 = 75; X2 = 75; X3 = 0; X4 = 0.

Tugas nomor 1.

Perusahaan memproduksi dua jenis produk. Jenis bahan baku, cadangannya, tingkat konsumsi bahan baku per c.u. setiap jenis produk, keuntungan produksi dari penjualan produk diberikan dalam tabel.

Larutan

2X1 + 2X2 ≤ 17

X1 + 3X2 + X3 = 20 F - 2X1 - X2 = 0

2X1 + X2 + X4 = 10

2X1 + 2X2 + X5 =17

Jawab: X1 = 5; X2 = 0; X3 = 15; X4 = 0; X5 = 7.

Tugas nomor 2.

Perusahaan memproduksi tiga jenis produk, menggunakan tiga jenis bahan baku. Stok bahan baku, tingkat konsumsinya, dan keuntungan dari penjualan setiap produk ditunjukkan pada tabel.

Bagaimana seharusnya produksi direncanakan agar keuntungan perusahaan menjadi yang terbesar?

Larutan

2X1 + 3X2 + 7X3 ≤ 1250 F = 41X1 + 35X2 + 96X3 → maks

5X1 + 3X2 ≤ 900

2X1 + 3X2 + 7X3 + X4 = 1250 P - 41X1 - 35X2 - 96X3 = 0

X1 + X2 + X5 = 250

5X1 +3X2 + X6 = 900

X1 + 3X2 ≤ 20 F = 2X1 + X2 → maks

2X1 + 2X2 ≤ 17

(-1/3)(-1/3)(2/3)

Jawab: X1 = 0; X2 = 29/5; X3 = 0; X4 = 13/5; X5 = 0; X6 = 0; X7 = 54/5.

Kesimpulan

Mari kita memikirkan interpretasi paling sederhana dari metode simpleks.

Arti aljabar dari metode simpleks adalah bahwa, dengan melakukan transformasi aljabar yang identik, kita berpindah dari satu solusi yang layak ke sistem persamaan aljabar ke sistem persamaan aljabar lainnya yang lebih baik, mencapai solusi optimal dari masalah tersebut.

Dari sudut pandang geometris, transformasi identik menurut metode simpleks adalah gerakan berturut-turut dari satu simpul poligon solusi cembung ke simpul tetangga, dari itu ke simpul berikutnya, dan seterusnya ke simpul optimal di sepanjang sisi poligon ini .

Esensi ekonomi dari metode simpleks terletak pada kenyataan bahwa ini adalah metode perbaikan solusi yang berurutan. Metode ini memungkinkan, setelah memilih titik awal - rencana tindakan dasar, untuk secara bertahap bergerak maju dan pada akhirnya mencapai rencana yang optimal, jika, tentu saja, ada.

Simplex adalah poligon cembung dalam ruang n-dimensi dengan n + 1 simpul yang tidak terletak pada hyperplane yang sama. Simpleks dipisahkan menjadi kelas yang terpisah karena simpleks adalah poligon paling sederhana yang berisi beberapa volume ruang n-dimensi.

Telah dibuktikan bahwa jika ada solusi optimal, maka solusi tersebut pasti akan ditemukan setelah sejumlah langkah terbatas (dengan pengecualian dari apa yang disebut "masalah degenerasi", di mana fenomena "bersepeda", yaitu pengembalian berganda ke posisi yang sama, adalah mungkin).

Pemrograman linier adalah bidang pemrograman matematika yang dikhususkan untuk teori dan metode untuk memecahkan masalah ekstrem yang ditandai dengan hubungan linier antar variabel.

Pemrograman matematika (pemrograman optimal) adalah cabang matematika yang menggabungkan berbagai metode dan disiplin matematika: pemrograman linier, pemrograman dinamis, pemrograman cembung, dll. Tugas umum pemrograman matematika adalah menemukan nilai optimal (maksimum atau minimum) dari tujuan fungsi, dan nilai variabel harus termasuk dalam rentang nilai yang dapat diterima.

Daftar literatur yang digunakan

1) A.S. Shapkin, N.P. Mazaeva; Metode matematika dan model penelitian operasi, 2005.

2) N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Riset Operasi di ekonomi. - UNITI, 2002.

Untuk menggunakan pratinjau presentasi, buat akun Google (akun) dan masuk: https://accounts.google.com

Keterangan slide:

Memecahkan masalah paling sederhana dari pemrograman linier dengan metode grafis 2012/04/17.

Jika sistem kendala dari masalah pemrograman linier direpresentasikan sebagai sistem pertidaksamaan linier dengan dua variabel, maka masalah tersebut dapat diselesaikan secara geometris.

Tugas. Ada 14 saluran relai radio (RRC) dan 9 saluran troposfer. Penting untuk mentransfer informasi dari 3 jenis: A, B, C. Selain itu, informasi A sama dengan 600 USD, B - 3000 USD, C - 5500 USD. (Informasi dapat dipahami sebagai jumlah percakapan telepon, transfer data, dll.). Kemampuan saluran dan biaya pemeliharaan untuk setiap saluran diberikan dalam tabel. Diperlukan untuk menemukan jumlah saluran yang terlibat dari kedua jenis, yang diperlukan untuk transmisi informasi yang diperlukan, sehingga biaya operasinya minimal.

Jenis informasi Saluran komunikasi Jumlah informasi yang dibutuhkan, c.u. Troposfer RRS A 80 40 600 V - 1000 3000 C 300 800 5500 Biaya perawatan untuk satu saluran, gosok. 3000 2000

Tahapan penyelesaian LLP: Membangun ODR. Bangun vektor gradien dari fungsi tujuan di beberapa titik X 0 milik ODR - (c 1 ;c 2) . Buatlah garis c 1 x 1 + c 2 x 2 = h, dengan h adalah sembarang bilangan positif, sebaiknya garis yang ditarik melewati poligon solusi.

Pindahkan garis yang ditemukan sejajar dengan dirinya sendiri ke arah vektor gradien hingga garis meninggalkan ODR (saat mencari maksimum) atau ke arah yang berlawanan (saat mencari minimum). Pada titik batas, fungsi tujuan mencapai maksimum (minimum), atau ketakterbatasan fungsi ditetapkan pada himpunan solusi. Tentukan koordinat titik maksimum (minimum) dari fungsi tersebut dan hitung nilai fungsi pada titik tersebut.

Pada topik: perkembangan metodologis, presentasi dan catatan

Perkembangan ini dapat digunakan sebagai pelajaran generalisasi pada topik "Sistem pertidaksamaan dengan dua variabel" di kelas 9 (aljabar 9, diedit oleh Telyakovsky) dan sebagai pelajaran pengulangan pada topik ini di kelas 10. ...

Materi ini ditujukan untuk siswa tingkat lanjut. program mempertimbangkan algoritme untuk menyusun plot dasar dan referensi dengan berbagai metode dan menemukan solusi optimal ...

Buku kerja untuk pelajaran matematika dengan topik "Masalah pemrograman linier" dikembangkan oleh saya untuk pelajaran matematika dengan nama yang sama (tingkat lanjutan). bisa digunakan baik di kelas, seminar...

Pengambilan Keputusan di Bawah Ketidakpastian Jika subjek pertama memiliki m strategi dan subjek kedua memiliki n strategi, maka kita mengatakan bahwa kita berhadapan dengan permainan m x n. Pertimbangkan game mxn. Biarkan satu set strategi diberikan: untuk pemain pertama (Аi), untuk pemain kedua (Bj), matriks pembayaran, di mana aij adalah keuntungan pemain pertama atau kerugian pemain kedua ketika mereka memilih strategi Аi dan Bj, masing-masing. Masing-masing pemain secara unik memilih dengan probabilitas saya beberapa strategi, yaitu. menggunakan strategi murni ketika memilih solusi. Dalam hal ini, solusi dari permainan ini adalah strategi murni. Karena kepentingan para pemain berlawanan, pemain pertama berusaha memaksimalkan keuntungannya, dan pemain kedua, sebaliknya, meminimalkan kerugiannya. Keputusan permainan adalah menentukan strategi terbaik untuk setiap pemain. Pilihan strategi terbaik oleh satu pemain dilakukan tanpa adanya informasi sama sekali tentang keputusan yang dibuat oleh pemain kedua.