Definisi riset operasi. Operasi pencarian. Membangun rencana referensi awal

1. Pokok bahasan dan tujuan riset operasi di bidang ekonomi. Konsep dasar teori riset operasi.

Subjek penelitian operasi adalah sistem atau organisasi manajemen organisasi, yang terdiri dari sejumlah besar unit yang saling berinteraksi yang tidak selalu konsisten satu sama lain dan mungkin berlawanan.

Tujuan dari riset operasi adalah untuk secara kuantitatif mendukung keputusan yang dibuat untuk mengelola organisasi.

Solusi yang paling bermanfaat bagi seluruh organisasi disebut optimal, dan solusi yang paling bermanfaat bagi satu atau lebih divisi akan disebut suboptimal.

Riset operasi adalah ilmu yang berhubungan dengan pengembangan dan penerapan praktis metode untuk pengelolaan sistem organisasi yang paling optimal.

Operasi adalah setiap peristiwa (sistem tindakan) yang disatukan oleh satu rencana dan ditujukan untuk mencapai suatu tujuan.

Tujuan dari riset operasi adalah pembenaran kuantitatif awal atas solusi optimal.

Pilihan parameter tertentu yang bergantung pada kita disebut solusi. Solusi optimal adalah solusi yang lebih disukai daripada solusi lain berdasarkan karakteristik tertentu.

Parameter yang kombinasinya membentuk suatu solusi disebut elemen solusi.

Himpunan solusi yang layak diberikan kondisi yang tetap dan tidak dapat dilanggar.

Indikator efisiensi adalah ukuran kuantitatif yang memungkinkan Anda membandingkan berbagai solusi dalam hal efisiensi.

2. Konsep perencanaan dan pengelolaan jaringan. Model jaringan dari proses dan elemen-elemennya.

Metode bekerja dengan grafik jaringan - perencanaan jaringan - didasarkan pada teori grafik. Diterjemahkan dari bahasa Yunani, grafik (grafpho - saya menulis) mewakili sistem titik, beberapa di antaranya dihubungkan oleh garis - busur (atau tepi). Ini adalah model topologi (matematis) dari sistem yang berinteraksi. Dengan menggunakan grafik, Anda tidak hanya dapat memecahkan masalah perencanaan jaringan, tetapi juga masalah lainnya. Metode perencanaan jaringan digunakan ketika merencanakan serangkaian pekerjaan yang saling terkait. Hal ini memungkinkan Anda untuk memvisualisasikan urutan kerja organisasi dan teknologi dan membangun hubungan di antara mereka. Selain itu, hal ini memungkinkan koordinasi operasi dengan berbagai tingkat kompleksitas dan identifikasi operasi yang menjadi sandaran durasi seluruh pekerjaan (yaitu, acara organisasi), serta berfokus pada penyelesaian tepat waktu dari setiap operasi.

Dasar perencanaan dan pengelolaan jaringan adalah model jaringan (NM), yang memodelkan serangkaian pekerjaan dan peristiwa yang saling berhubungan yang mencerminkan proses pencapaian tujuan tertentu. Dapat disajikan dalam bentuk grafik atau tabel.

Konsep dasar model jaringan:

Acara, pekerjaan, jalan.

Peristiwa adalah hasil dari satu atau lebih pekerjaan. Mereka tidak mempunyai perpanjangan waktu.

Jalur adalah rangkaian pekerjaan yang mengikuti satu sama lain, menghubungkan simpul awal dan akhir.

Lamanya perjalanan ditentukan oleh penjumlahan jangka waktu karya-karya penyusunnya.

3. Konstruksi dan pengorganisasian diagram jaringan.

Model jaringan digunakan sebagai model yang mencerminkan hubungan teknologi dan organisasi dari proses kerja konstruksi dan instalasi dalam sistem perencanaan dan manajemen jaringan (NPS).

Model jaringan adalah representasi grafis dari proses, yang implementasinya mengarah pada pencapaian satu atau lebih tujuan yang ditetapkan, yang menunjukkan hubungan yang terjalin antara proses-proses ini. Diagram jaringan adalah model jaringan dengan parameter waktu yang dihitung.

Struktur diagram jaringan, yang menentukan saling ketergantungan antara aktivitas dan peristiwa, disebut topologinya.

Pekerjaan adalah suatu proses produksi yang memerlukan waktu, tenaga, dan sumber daya material, yang apabila selesai akan membawa pada tercapainya hasil tertentu.

Ketergantungan (pekerjaan fiktif) yang tidak memerlukan waktu digambarkan dengan panah putus-putus. Pekerjaan fiktif digunakan dalam diagram jaringan untuk menunjukkan hubungan antara peristiwa dan aktivitas.

Diagram jaringan menggunakan waktu, biaya dan karakteristik pekerjaan lainnya.

Pekerjaan berkelanjutan - waktu yang diperlukan untuk menyelesaikan pekerjaan ini dalam hari kerja atau satuan waktu lain yang sama untuk semua pekerjaan pada jadwal jaringan. Durasi kerja dapat berupa variabel tertentu (deterministik) atau variabel acak yang ditentukan oleh hukum distribusinya.

Biaya pekerjaan adalah biaya langsung yang diperlukan untuk menyelesaikannya, tergantung pada durasi dan kondisi pekerjaan tersebut.

Sumber daya dicirikan oleh kebutuhan akan unit fisik yang diperlukan untuk menyelesaikan pekerjaan tertentu.

Kualitas, keandalan, dan indikator pekerjaan lainnya berfungsi sebagai karakteristik tambahan dari pekerjaan.

Suatu peristiwa adalah fakta penyelesaian satu atau lebih pekerjaan, yang diperlukan dan cukup untuk dimulainya satu atau lebih pekerjaan berikutnya. Setiap peristiwa diberi nomor yang disebut kode. Setiap pekerjaan ditentukan oleh dua kejadian: kode kejadian awal, dilambangkan dengan i, dan kode kejadian akhir, dilambangkan dengan j.

Peristiwa yang tidak mempunyai hasil sebelumnya disebut peristiwa awal; peristiwa yang tidak memiliki peristiwa berikutnya adalah terbatas.

1 Arah pembangunan jaringan dapat berbeda sifatnya. Diagram jaringan dapat dibangun dari kejadian awal ke kejadian akhir dan dari kejadian terakhir ke kejadian awal, serta dari kejadian mana pun ke kejadian awal atau akhir.

2 Saat membangun jaringan, masalah berikut diselesaikan:

Pekerjaan apa yang harus diselesaikan untuk memulai pekerjaan ini;

Pekerjaan apa yang disarankan untuk dilakukan secara paralel dengan pekerjaan ini;

3 Jadwal jaringan awal dibuat tanpa memperhitungkan durasi pekerjaan yang membentuk jaringan.

4 Bentuk grafik harus sederhana dan mudah dilihat secara visual.

5 Hanya satu pekerjaan yang dapat terjadi di antara dua peristiwa. Dalam konstruksi bangunan dan struktur, pekerjaan dapat dilakukan secara berurutan, paralel atau bersamaan, ada yang berurutan dan ada yang paralel, sehingga timbul berbagai ketergantungan antara masing-masing pekerjaan.

Penomoran (coding) kejadian dilakukan setelah selesainya pembangunan jaringan, dimulai dari kejadian awal sampai dengan kejadian akhir.

4. Jalur kritis diagram jaringan. Cadangan waktu. Tanggal awal dan akhir acara dan pekerjaan dalam jadwal jaringan.

Dalam diagram jaringan, terdapat beberapa jalur antara kejadian awal dan akhir. Jalur dengan durasi terpanjang disebut jalur kritis. Jalur kritis menentukan total durasi aktivitas. Semua jalur lain memiliki durasi yang lebih pendek, dan oleh karena itu pekerjaan yang dilakukan di jalur tersebut memiliki cadangan waktu.

Jalur kritis ditunjukkan pada diagram jaringan dengan garis tebal atau ganda (panah).

Dua konsep yang sangat penting ketika menyusun diagram jaringan:

Awal pekerjaan adalah periode sebelum pekerjaan ini tidak dapat dimulai tanpa melanggar urutan teknologi yang berlaku. Hal ini ditentukan oleh jalur terpanjang dari awal kejadian hingga awal pekerjaan ini

Keterlambatan penyelesaian pekerjaan adalah batas akhir penyelesaian pekerjaan, dimana total durasi pekerjaan tidak bertambah. Hal ini ditentukan oleh jalur terpendek dari suatu peristiwa tertentu hingga selesainya semua pekerjaan.

Penyelesaian awal adalah batas waktu dimana pekerjaan tidak dapat diselesaikan. Ini sama dengan permulaan awal ditambah lamanya pekerjaan ini

Awal yang terlambat - periode setelah pekerjaan tidak dapat dimulai tanpa menambah total durasi konstruksi. Ini sama dengan keterlambatan penyelesaian dikurangi durasi pekerjaan ini.

Jika suatu peristiwa merupakan akhir dari hanya satu pekerjaan (yaitu, hanya satu panah yang diarahkan ke sana), maka akhir awal dari pekerjaan ini bertepatan dengan awal dimulainya pekerjaan berikutnya.

Cadangan umum (penuh) adalah waktu maksimum dimana penyelesaian suatu pekerjaan tertentu dapat ditunda tanpa menambah total durasi pekerjaan. Hal ini ditentukan oleh perbedaan antara permulaan yang terlambat dan awal (atau penyelesaian yang terlambat dan awal - yang merupakan hal yang sama).

Cadangan pribadi (gratis) adalah waktu maksimum di mana pelaksanaan pekerjaan tertentu dapat ditunda tanpa mengubah permulaan awal pekerjaan berikutnya. Cadangan ini hanya mungkin jika peristiwa tersebut mencakup dua atau lebih pekerjaan (ketergantungan), yaitu. dua atau lebih anak panah (padat atau putus-putus) diarahkan ke sana. Maka hanya satu dari pekerjaan ini yang akan memiliki penyelesaian awal yang bertepatan dengan dimulainya pekerjaan berikutnya, namun sisanya akan memiliki nilai yang berbeda. Perbedaan untuk setiap pekerjaan ini akan menjadi cadangan pribadinya.

5. Pemrograman dinamis. Prinsip optimalitas dan kontrol Bellman.

Pemrograman dinamis adalah salah satu metode optimasi yang paling ampuh. Spesialis dari berbagai profil menangani masalah pengambilan keputusan rasional, pemilihan opsi terbaik, dan manajemen optimal. Di antara metode optimasi, pemrograman dinamis menempati posisi khusus. Metode ini sangat menarik karena kesederhanaan dan kejelasan prinsip dasarnya – prinsip optimalitas. Cakupan penerapan prinsip optimalitas sangatlah luas, cakupan permasalahan yang dapat diterapkan belum sepenuhnya diuraikan. Sejak awal, pemrograman dinamis telah menjadi sarana untuk memecahkan masalah optimasi secara praktis.

Selain prinsip optimalitas, metode penelitian utama, peran besar dalam peralatan pemrograman dinamis dimainkan oleh gagasan untuk membenamkan masalah optimasi tertentu ke dalam keluarga masalah serupa. Ciri ketiga yang membedakannya dengan metode optimasi lainnya adalah bentuk hasil akhirnya. Penerapan prinsip optimalitas dan prinsip pencelupan dalam proses diskrit multi-langkah menghasilkan persamaan fungsional berulang mengenai nilai optimal kriteria kualitas. Persamaan yang dihasilkan memungkinkan penulisan kontrol optimal secara konsisten untuk masalah awal. Manfaatnya di sini adalah bahwa masalah penghitungan pengendalian untuk keseluruhan proses dibagi menjadi beberapa masalah penghitungan pengendalian yang lebih sederhana untuk masing-masing tahapan proses.

Kelemahan utama dari metode ini, dalam kata-kata Bellman, adalah “kutukan dimensi” – kompleksitasnya meningkat secara drastis seiring dengan meningkatnya dimensi masalah.

6. Masalah distribusi dana antar perusahaan.

Dapat dikatakan bahwa prosedur membangun pengendalian optimal dengan menggunakan metode pemrograman dinamis dibagi menjadi dua tahap: tahap awal dan akhir. Pada tahap awal, untuk setiap langkah, BUMN ditentukan tergantung pada keadaan sistem (dicapai sebagai hasil dari langkah-langkah sebelumnya), dan keuntungan optimal bersyarat pada semua langkah yang tersisa, mulai dari yang ini, juga tergantung pada keadaan. . Pada tahap akhir, kontrol optimal (tanpa syarat) untuk setiap langkah ditentukan. Optimalisasi awal (bersyarat) dilakukan langkah demi langkah dalam urutan terbalik: dari langkah terakhir ke langkah pertama; optimasi akhir (tanpa syarat) - juga dalam langkah-langkah, tetapi dalam urutan alami: dari langkah pertama hingga langkah terakhir. Dari dua tahap pengoptimalan, tahap pertama jauh lebih penting dan memakan waktu. Setelah menyelesaikan tahap pertama, menyelesaikan tahap kedua tidak menimbulkan kesulitan: yang tersisa hanyalah “membaca” rekomendasi yang sudah disiapkan pada tahap pertama.

7. Pernyataan masalah program linier.

Pemrograman linier adalah alat populer untuk memecahkan masalah ekonomi yang ditandai dengan adanya satu kriteria (misalnya, memaksimalkan pendapatan produksi melalui pilihan program produksi yang optimal, atau, misalnya, meminimalkan biaya transportasi, dll.). Permasalahan ekonomi ditandai dengan keterbatasan sumber daya (materi dan/atau finansial). Mereka ditulis dalam bentuk sistem ketidaksetaraan, terkadang dalam bentuk persamaan.

Dari sudut pandang peramalan interval harga (atau volume penjualan) yang dapat diterima dalam kerangka metode nonparametrik umum, penggunaan program linier berarti:

Kriterianya adalah harga MAX produk berikutnya dari kelompok minat f.

Variabel yang dikendalikan adalah harga seluruh produk dari kelompok f.

Keterbatasan dalam masalah peramalan kita dengan menggunakan metode nonparametrik umum adalah:

a) sistem ketidaksetaraan (pembatasan rasionalitas perilaku konsumen) (lihat 4.2. Peramalan dalam kerangka metode nonparametrik umum);

b) persyaratan variabel terkontrol yang tidak negatif (dalam masalah peramalan kita, kita akan mensyaratkan bahwa harga produk dari kelompok f tidak turun di bawah 80% dari nilai harga pada titik waktu terakhir);

c) batasan anggaran dalam bentuk kesetaraan - persyaratan bahwa jumlah biaya pembelian produk dari kelompok f harus konstan (dengan mempertimbangkan inflasi 15%, misalnya).

8. Metode grafis untuk menyelesaikan masalah program linier.

Metode grafis didasarkan pada interpretasi geometri dari masalah program linier dan digunakan terutama ketika memecahkan masalah dalam ruang dua dimensi dan hanya beberapa masalah dalam ruang tiga dimensi, karena cukup sulit untuk membangun polihedron solusi yang dibentuk sebagai hasil perpotongan setengah spasi. Secara umum tidak mungkin untuk menggambarkan masalah dalam ruang yang dimensinya lebih besar dari tiga secara grafis.

Biarkan masalah program linier dispesifikasikan dalam ruang dua dimensi, yaitu batasannya mengandung dua variabel.

Temukan nilai minimum suatu fungsi

(2.1) Z = С1х1+С2х2

a11x1 + a22x2 b1

(2.2)a21x1 + a22x2 b2

am1x1 + am2x2 bM

(2.3) x1 0, x2 0

Mari kita asumsikan bahwa sistem (2.2) pada kondisi (2.3) konsisten dan poligon solusinya dibatasi. Masing-masing pertidaksamaan (2.2) dan (2.3), sebagaimana disebutkan di atas, mendefinisikan setengah bidang dengan garis batas: ai1x1 + ai2x2 + ai3x3 = bi,(i = 1, 2, ..., n), x1=0 , x2=0 . Fungsi linier (2.1) untuk nilai Z tetap adalah persamaan garis lurus: C1x1 + C2x2 = const. Mari kita buat poligon solusi sistem kendala (2.2) dan grafik fungsi linier (2.1) di Z = 0 (Gbr. 2.1). Maka masalah program linier yang diajukan dapat diberikan interpretasi sebagai berikut. Temukan titik poligon solusi di mana garis support C1x1 + C2x2 = const dan fungsi Z mencapai minimum.

Nilai Z = C1x1 + C2x2 bertambah searah dengan vektor N = (C1, C2), maka kita gerakkan garis lurus Z = 0 sejajar dengan dirinya searah dengan vektor X. Dari Gambar. 2.1 maka garis lurus tersebut dua kali menjadi garis acuan terhadap poligon solusi (di titik A dan C), dan mengambil nilai minimum di titik A. Koordinat titik A (x1, x2) dicari dengan menyelesaikan persamaan sistem persamaan garis lurus AB dan AE.

Jika poligon solusinya adalah luas poligon tak berbatas, maka ada dua kasus yang mungkin terjadi.

Kasus 1. Garis C1x1 + C2x2 = const, bergerak searah atau berlawanan dengan vektor N, terus-menerus memotong poligon solusi dan tidak mendukungnya di titik mana pun. Dalam hal ini, fungsi linier tidak dibatasi pada poligon solusi baik di atas maupun di bawah (Gbr. 2.2).

Kasus 2. Garis lurus, bergerak, namun menjadi penopang relatif terhadap poligon solusi (Gbr. 2.2, a - 2.2, c). Kemudian, bergantung pada jenis luasnya, fungsi linier dapat dibatasi dari atas dan tidak terbatas dari bawah (Gbr. 2.2, a), dibatasi dari bawah dan tidak terbatas dari atas (Gbr. 2.2, b), atau dibatasi keduanya dari bawah dan dari atas (Gbr. 2.2, c).

9. Metode simpleks.

Metode simpleks merupakan metode utama dalam pemrograman linier. Pemecahan masalah dimulai dengan mempertimbangkan salah satu simpul dari polihedron kondisi. Jika titik yang diteliti tidak sesuai dengan titik maksimum (minimum), maka titik tersebut berpindah ke titik tetangganya, menaikkan nilai fungsi tujuan ketika menyelesaikan masalah ke titik maksimum dan menurunkannya ketika menyelesaikan masalah ke titik minimum. Jadi, perpindahan dari satu titik ke titik lainnya akan meningkatkan nilai fungsi tujuan. Karena jumlah simpul polihedron terbatas, dalam jumlah langkah yang terbatas dijamin akan menemukan nilai optimal atau menetapkan fakta bahwa masalahnya tidak dapat diselesaikan.

Metode ini bersifat universal, dapat diterapkan pada semua masalah pemrograman linier dalam bentuk kanonik. Sistem kendala di sini adalah sistem persamaan linier yang jumlah persamaannya lebih banyak daripada jumlah persamaannya. Jika peringkat sistem adalah r, maka kita dapat memilih r yang tidak diketahui, yang kita nyatakan dalam bentuk sisa yang tidak diketahui. Untuk lebih pastinya, kita asumsikan bahwa bilangan-bilangan tak diketahui pertama yang berturut-turut X1, X2, ..., Xr dipilih. Maka sistem persamaan kita dapat ditulis sebagai

Metode simpleks didasarkan pada teorema yang disebut teorema dasar metode simpleks. Di antara rencana optimal masalah program linier dalam bentuk kanonik, tentu terdapat solusi referensi untuk sistem kendalanya. Jika rencana optimal suatu permasalahan bersifat unik, maka rencana tersebut bertepatan dengan beberapa solusi referensi. Ada sejumlah solusi pendukung yang berbeda terhadap sistem kendala. Oleh karena itu, penyelesaian masalah dalam bentuk kanonik dapat dicari dengan mencari solusi referensi dan memilih di antara solusi tersebut yang nilai Fnya paling besar. Namun, pertama, semua solusi referensi tidak diketahui dan perlu ditemukan, dan kedua, dalam masalah nyata terdapat banyak solusi seperti itu dan pencarian langsung hampir tidak mungkin dilakukan. Metode simpleks adalah prosedur tertentu untuk enumerasi terarah dari solusi pendukung. Berdasarkan solusi referensi tertentu yang ditemukan sebelumnya dengan menggunakan algoritma metode simpleks tertentu, kami menghitung solusi referensi baru yang nilai fungsi tujuan F tidak kurang dari nilai fungsi tujuan lama. Setelah serangkaian langkah, kita sampai pada solusi referensi, yaitu rencana optimal.

10. Pernyataan masalah transportasi. Metode untuk menentukan rencana referensi.

Terdapat m titik keberangkatan (“pemasok”) dan n titik konsumsi (“konsumen”) dari beberapa produk yang identik. Untuk setiap item, berikut ini ditentukan:

ai - volume produksi pemasok ke-i, i = 1, …, m;

вj - permintaan konsumen ke-j, j= 1,…,n;

сij adalah biaya pengangkutan satu unit produk dari titik Ai, pemasok ke-i, ke titik Bj, konsumen ke-j.

Agar lebih jelas, data dapat disajikan dalam bentuk tabel, yang disebut tabel biaya transportasi.

Penting untuk menemukan rencana transportasi yang dapat memenuhi permintaan semua konsumen sepenuhnya, sementara pasokan dari pemasok akan mencukupi dan total biaya transportasi akan minimal.

Rencana transportasi mengacu pada volume transportasi, yaitu. jumlah barang yang perlu diangkut dari pemasok ke-i ke konsumen ke-j. Untuk membangun model matematika dari soal tersebut, perlu memasukkan m·n variabel xij, i= 1,..., n, j= 1,..., m, setiap variabel xij menyatakan volume angkutan dari titik Ai ke titik Bj. Himpunan variabel X = (xij) akan menjadi rencana yang perlu dicari berdasarkan rumusan masalah.

Hal ini merupakan syarat penyelesaian masalah transportasi tertutup dan terbuka (CTZ).

Jelasnya, agar Masalah 1 dapat diselesaikan, total permintaan harus tidak melebihi volume produksi dari pemasok:

Jika pertidaksamaan ini dipenuhi secara ketat, maka permasalahan tersebut disebut “terbuka” atau “tidak seimbang”, tetapi jika , maka permasalahan tersebut disebut permasalahan transportasi “tertutup”, dan akan berbentuk (2):

Kondisi keseimbangan.

Ini merupakan syarat untuk menyelesaikan masalah transportasi tertutup (CTP).

11. Algoritma penyelesaian masalah transportasi.

Penerapan algoritma memerlukan kepatuhan terhadap sejumlah prasyarat:

1. Biaya pengangkutan satu unit produk dari setiap titik produksi ke setiap tujuan harus diketahui.

2. Stok produk pada setiap titik produksi harus diketahui.

3. Kebutuhan produk pada setiap titik konsumsi harus diketahui.

4. Total pasokan harus sama dengan total permintaan.

Algoritma penyelesaian masalah transportasi terdiri dari empat tahap:

Tahap I: Sajikan data dalam bentuk tabel standar dan temukan alokasi sumber daya yang layak. Dapat diterima adalah distribusi sumber daya yang memungkinkan Anda memenuhi semua permintaan di tujuan dan mengeluarkan seluruh stok produk dari titik produksi.

Tahap 2. Memeriksa optimalitas alokasi sumber daya yang dihasilkan

Tahap 3. Jika alokasi sumber daya yang dihasilkan tidak optimal, maka sumber daya tersebut didistribusikan kembali sehingga mengurangi biaya transportasi.

Tahap 4. Memeriksa kembali optimalitas alokasi sumber daya yang dihasilkan.

Proses iteratif ini diulangi hingga diperoleh solusi optimal.

12. Model manajemen inventaris.

Terlepas dari kenyataan bahwa setiap model manajemen inventaris dirancang untuk menjawab dua pertanyaan utama (kapan dan berapa banyak), ada sejumlah besar model, yang konstruksinya menggunakan berbagai alat matematika.

Situasi ini dijelaskan oleh perbedaan kondisi awal. Dasar utama untuk mengklasifikasikan model manajemen inventaris adalah sifat permintaan akan produk yang disimpan (ingat bahwa dari sudut pandang gradasi yang lebih umum, kami sekarang hanya mempertimbangkan kasus dengan permintaan independen).

Jadi, tergantung pada sifat permintaan, model manajemen inventaris bisa jadi

deterministik;

probabilistik.

Pada gilirannya, permintaan deterministik bisa bersifat statis, ketika intensitas konsumsi tidak berubah seiring waktu, atau dinamis, ketika permintaan yang dapat diandalkan dapat berubah seiring waktu.

Permintaan probabilistik bisa stasioner, ketika fungsi kepadatan probabilitas permintaan tidak berubah seiring waktu, dan non-stasioner, di mana fungsi kepadatan probabilitas berubah tergantung waktu. Klasifikasi di atas diilustrasikan oleh gambar.

Kasus paling sederhana adalah kasus permintaan statis deterministik terhadap produk. Namun konsumsi jenis ini cukup jarang dalam praktiknya. Model yang paling kompleks adalah model tipe non-stasioner.

Selain sifat permintaan produk, ketika membangun model manajemen inventaris, banyak faktor lain yang harus dipertimbangkan, misalnya:

batas waktu pemenuhan pesanan. Durasi periode pengadaan dapat bersifat konstan atau variabel acak;

proses pengisian kembali persediaan. Bisa seketika atau didistribusikan seiring waktu;

adanya pembatasan modal kerja, ruang gudang, dll.

13. Sistem antrian (QS) dan indikator efektivitasnya.

Sistem antrian (QS) adalah sistem tipe khusus yang mengimplementasikan eksekusi berulang dari tugas serupa. Sistem seperti ini memainkan peranan penting dalam banyak bidang ekonomi, keuangan, produksi dan kehidupan sehari-hari. Seperti contoh QS di bidang keuangan dan ekonomi; di bidangnya kita dapat menyebutkan bank dari berbagai jenis (komersial, investasi, hipotek, inovatif, tabungan), organisasi asuransi, perusahaan saham gabungan negara, perusahaan, firma, asosiasi, koperasi, inspektorat pajak, layanan audit, berbagai sistem komunikasi (termasuk pertukaran telepon), kompleks bongkar muat (pelabuhan, stasiun pengangkutan), pompa bensin, berbagai perusahaan dan organisasi jasa (toko, meja informasi, penata rambut, kantor tiket, kantor penukaran mata uang, bengkel, rumah sakit). Sistem seperti jaringan komputer, sistem pengumpulan, penyimpanan dan pemrosesan informasi, sistem transportasi, area produksi otomatis, jalur produksi, berbagai sistem militer, khususnya sistem pertahanan udara atau rudal, juga dapat dianggap sebagai semacam QS

Setiap QS mencakup sejumlah perangkat layanan dalam strukturnya, yang disebut saluran layanan (perangkat, saluran). Peran saluran dapat dimainkan oleh berbagai perangkat, orang yang melakukan operasi tertentu (kasir, operator, penata rambut, tenaga penjualan), jalur komunikasi, mobil, derek, kru perbaikan, rel kereta api, pompa bensin, dll.

Sistem antrian dapat berupa saluran tunggal atau multi saluran.

Setiap QS dirancang untuk melayani (memenuhi) aliran aplikasi (persyaratan) tertentu yang masuk ke input sistem, sebagian besar tidak secara teratur, tetapi pada waktu yang acak. Layanan aplikasi, dalam hal ini, juga tidak berlangsung dalam waktu yang konstan dan telah diketahui sebelumnya, melainkan waktu acak, yang bergantung pada banyak alasan acak, terkadang tidak kita ketahui. Setelah melayani permintaan, saluran dibebaskan dan siap menerima permintaan berikutnya. Sifat acak dari aliran permintaan dan waktu pelayanannya menyebabkan beban QS yang tidak merata: di lain waktu, aplikasi yang tidak terlayani dapat terakumulasi pada input QS, yang menyebabkan kelebihan beban QS, dan terkadang ketika ada saluran gratis di input QS, tidak akan ada aplikasi, yang menyebabkan kekurangan QS, mis. kemalasan salurannya. Aplikasi yang terakumulasi di pintu masuk QS akan “bergabung” dengan antrian, atau, karena ketidakmungkinan untuk tetap berada dalam antrian, membiarkan QS tidak terlayani.

Indikator efektivitas berfungsinya pasangan “CMO - konsumen”, di mana konsumen dipahami sebagai seluruh rangkaian aplikasi atau beberapa sumbernya (misalnya, pendapatan rata-rata yang dihasilkan oleh CMO per unit waktu, dll. ). Kelompok indikator ini berguna ketika sebagian pendapatan yang diterima dari layanan aplikasi dan biaya layanan diukur dalam satuan yang sama. Indikator-indikator ini biasanya bersifat sangat spesifik dan ditentukan oleh kekhususan QS, permintaan yang dilayani, dan disiplin pelayanan.

14. Persamaan dinamika keadaan probabilistik (persamaan Kolmogorov). Membatasi probabilitas negara.

Membedakan secara formal persamaan Kolmogorov – Chapman terhadap s pada s = 0, kita memperoleh persamaan Kolmogorov langsung:

Membedakan persamaan Kolmogorov-Chapman secara formal terhadap t pada t = 0, kita memperoleh invers persamaan Kolmogorov

Harus ditekankan bahwa untuk ruang berdimensi tak terhingga operatornya tidak lagi kontinu, dan tidak dapat didefinisikan di semua tempat, misalnya menjadi operator diferensial dalam ruang distribusi.

Jika jumlah keadaan sistem S terbatas dan tampaknya mungkin untuk berpindah dari setiap keadaan (dalam sejumlah langkah tertentu) ke keadaan lainnya, maka probabilitas pembatas dari keadaan tersebut ada dan juga tidak bergantung pada keadaan awal. dari sistem.

Pada Gambar. menunjukkan grafik keadaan dan transisi yang memenuhi kondisi yang dinyatakan: dari keadaan mana pun, sistem cepat atau lambat dapat bertransisi ke keadaan lain. Kondisi tersebut tidak terpenuhi bila arah panah 4-3 pada grafik pada Gambar berubah, melainkan sebaliknya.

Mari kita asumsikan bahwa kondisi yang disebutkan terpenuhi, dan oleh karena itu, ada probabilitas pembatas:

Probabilitas pembatas akan dilambangkan dengan huruf yang sama dengan probabilitas keadaan, sedangkan yang dimaksud adalah angka, bukan variabel (fungsi waktu).

Jelas bahwa probabilitas pembatas suatu negara harus berjumlah satu: Akibatnya, dalam sistem pada rezim stasioner pembatas tertentu terbentuk: bahkan jika sistem mengubah negaranya sendiri secara acak, probabilitas masing-masing negara ini tidak bergantung pada waktu dan masing-masing terjadi dengan probabilitas konstan, yang merupakan waktu relatif rata-rata sistem tetap berada dalam keadaan ini.

15. Proses kematian dan reproduksi.

Mari kita menyebut proses kematian dan reproduksi Markov dengan waktu berkelanjutan sebagai suatu proses yang hanya dapat mengambil nilai bilangan bulat non-negatif; perubahan dalam proses ini dapat terjadi kapan saja t, sedangkan pada suatu waktu dapat bertambah satu atau tetap tidak berubah.

Aliran reproduksi λi(t) akan disebut aliran Poisson yang menyebabkan peningkatan fungsi X(t). Oleh karena itu, μi(t) adalah aliran kematian yang menyebabkan penurunan fungsi X(t).

Mari kita buat persamaan Kolmogorov dari grafik:

Jika alirannya berhingga:

Sistem persamaan Kolmogorov untuk proses kematian dan reproduksi dengan sejumlah keadaan terbatas berbentuk:

Proses reproduksi murni merupakan proses kematian dan reproduksi yang intensitas seluruh aliran kematian sama dengan nol.

Proses kematian murni adalah proses kematian dan reproduksi yang intensitas seluruh aliran reproduksinya sama dengan nol.

16. Sistem antrian yang mengalami kegagalan.

Masalah paling sederhana yang dipertimbangkan dalam kerangka teori antrian adalah model QS saluran tunggal dengan kegagalan atau kerugian.

Perlu dicatat bahwa dalam hal ini jumlah saluran adalah 1 (). Saluran ini menerima aliran permintaan Poisson, yang intensitasnya sama dengan . Waktu mempengaruhi intensitas:

Jika suatu aplikasi masuk ke saluran yang saat ini tidak gratis, maka aplikasi tersebut ditolak dan tidak lagi terdaftar di sistem. Pelayanan aplikasi dilakukan dalam waktu acak yang pendistribusiannya dilaksanakan sesuai dengan hukum eksponensial dengan parameter:

17. Sistem antrian dengan menunggu.

Permintaan yang diterima ketika saluran sedang sibuk dimasukkan ke dalam antrian dan menunggu layanan.

Sistem dengan panjang antrian terbatas. Mari kita asumsikan terlebih dahulu bahwa jumlah tempat dalam antrian dibatasi oleh m, yaitu jika suatu aplikasi tiba pada saat sudah ada m aplikasi dalam antrian, maka sistem tidak terlayani. Nantinya, dengan mengarahkan m hingga tak terhingga, kita akan memperoleh karakteristik QS saluran tunggal tanpa batasan panjang antrian.

Kami akan memberi nomor status QS sesuai dengan jumlah aplikasi dalam sistem (baik yang sedang dilayani maupun yang menunggu layanan):

— saluran ini gratis;

— saluran sedang sibuk, tidak ada antrian;

— saluran sedang sibuk, satu permintaan sedang dalam antrian;

—saluran sibuk, k - 1 permintaan sedang dalam antrian;

— saluran sedang sibuk, banyak sekali aplikasi yang mengantri.

18. Metode pengambilan keputusan dalam kondisi konflik. Permainan matriks. Game strategi murni dan campuran.

Permainan matriks adalah permainan jumlah nol berhingga yang terdiri dari dua pemain, di mana hasil dari pemain 1 ditentukan dalam bentuk matriks (baris matriks sesuai dengan jumlah strategi yang diterapkan pemain 2, kolom sesuai dengan dengan jumlah strategi yang diterapkan pemain 2; pada perpotongan baris dan kolom matriks adalah hasil pemain 1, sesuai dengan strategi yang diterapkan).

Untuk permainan matriks, telah terbukti bahwa salah satu dari mereka memiliki solusi dan dapat dengan mudah ditemukan dengan mereduksi permainan tersebut menjadi masalah pemrograman linier.

Permainan matriks zero-sum dua pemain dapat dianggap sebagai permainan dua pemain abstrak berikut.

Pemain pertama mempunyai m strategi i = 1,2,...,m, pemain kedua mempunyai n strategi j = 1,2,...,n. Setiap pasangan strategi (i,j) dikaitkan dengan nomor aij, yang menyatakan keuntungan pemain 1 dengan mengorbankan pemain 2 jika pemain pertama menerima strategi ke-i, dan 2 - strategi ke-j.

Setiap pemain melakukan satu gerakan: pemain 1 memilih strategi ke-i (i=), 2 - strategi ke-j (j=), setelah itu pemain 1 menerima pembayaran aij dengan mengorbankan pemain 2 (jika aij

Setiap strategi pemain i=; j = sering disebut strategi murni.

Definisi. Strategi campuran seorang pemain adalah keseluruhan kemungkinan penggunaan strategi murninya.

Jadi, jika pemain 1 mempunyai m strategi murni 1,2,...,m, maka strategi campurannya x adalah himpunan bilangan x = (x1,...,xm) yang memenuhi hubungan

xi³ 0 (saya= 1,m), =1.

Demikian pula, untuk pemain 2, yang mempunyai n strategi murni, strategi campuran y adalah himpunan angka

y = (y1, ..., yn), yj ³ 0, (j = 1,n), = 1.

Karena setiap kali seorang pemain menggunakan satu strategi murni mengecualikan penggunaan strategi lainnya, strategi murni adalah peristiwa yang tidak kompatibel. Terlebih lagi, itu adalah satu-satunya kejadian yang mungkin terjadi.

Strategi murni adalah kasus khusus dari strategi campuran. Memang benar, jika dalam strategi campuran, strategi murni ke-i diterapkan dengan probabilitas 1, maka semua strategi murni lainnya tidak diterapkan. Dan strategi murni ke-i ini merupakan kasus khusus dari strategi campuran. Untuk menjaga kerahasiaan, setiap pemain menerapkan strateginya sendiri terlepas dari pilihan pemain lain.

19. Metode geometris untuk menyelesaikan permainan matriks.

Solusi permainan ukuran 2xn atau nx2 memungkinkan interpretasi geometris yang jelas. Permainan seperti itu dapat diselesaikan secara grafis.

Pada bidang XY sepanjang sumbu absis kita memplot satu segmen A1A2 (Gambar 5.1). Mari kita tetapkan pada setiap titik segmen beberapa strategi campuran U = (u1, u2). Selain itu, jarak dari suatu titik tengah U ke ujung kanan segmen ini adalah peluang u1 untuk memilih strategi A1, jarak ke ujung kiri adalah peluang u2 untuk memilih strategi A2. Titik A1 berhubungan dengan strategi murni A1, titik A2 berhubungan dengan strategi murni A2.

Pada titik A1 dan A2 kami akan mengembalikan garis tegak lurus dan menempatkan kemenangan para pemain pada titik tersebut. Pada garis tegak lurus pertama (bertepatan dengan sumbu OY) kami menunjukkan hasil pemain A saat menggunakan strategi A1, pada garis kedua - saat menggunakan strategi A2. Jika pemain A menggunakan strategi A1, maka bayarannya dengan strategi B1 pemain B sama dengan 2, dan dengan strategi B2 sama dengan 5. Angka 2 dan 5 pada sumbu OY berhubungan dengan titik B1 dan B2. Demikian pula, pada tegak lurus kedua kita menemukan titik B"1 dan B"2 (keuntungan 6 dan 4).

Dengan menghubungkan titik B1 dan B"1, B2 dan B"2, kita memperoleh dua garis lurus, jarak dari sumbu OX menentukan hasil rata-rata untuk setiap kombinasi strategi yang sesuai.

Misalnya, jarak dari titik mana pun di segmen B1B"1 ke sumbu OX menentukan hasil rata-rata pemain A untuk setiap kombinasi strategi A1 dan A2 (dengan probabilitas u1 dan u2) dan strategi B1 pemain B.

Koordinat titik-titik yang termasuk dalam garis putus-putus B1MB"2 menentukan pembayaran minimum pemain A ketika dia menggunakan strategi campuran apa pun. Nilai minimum ini adalah yang terbesar di titik M, oleh karena itu, titik ini sesuai dengan strategi optimal U* = ( ,), dan ordinatnya sama dengan biaya permainan v .

Koordinat titik M kita cari sebagai koordinat titik potong garis B1B"1 dan B2B"2.

Untuk melakukan ini, Anda perlu mengetahui persamaan garis. Anda dapat membuat persamaan seperti itu menggunakan rumus persamaan garis yang melalui dua titik:

Mari kita buat persamaan garis lurus untuk soal kita.

Garis B1B"1: = atau y = 4x + 2.

Langsung B2B"2: = atau y = -x + 5.

Kita mendapatkan sistemnya: y = 4x + 2,

Mari kita selesaikan: 4x + 2 = -x + 5,

x = 3/5, y = -3/5 + 5 = 22/5.

Jadi, U = (2/5, 3/5), v = 22/5.

20. Permainan bi-matriks.

Permainan bimatrix adalah permainan berhingga yang terdiri dari dua pemain dengan jumlah bukan nol, di mana hasil masing-masing pemain ditentukan oleh matriks secara terpisah untuk pemain yang bersangkutan (dalam setiap matriks, satu baris sesuai dengan strategi pemain 1, satu kolom sesuai dengan strategi pemain 2, pada perpotongan baris dan kolom pada matriks pertama adalah hasil pemain 1, pada matriks kedua - hasil pemain 2.)

Teori perilaku pemain optimal juga telah dikembangkan untuk permainan bimatrix, namun menyelesaikan permainan seperti itu lebih sulit daripada permainan matriks biasa.

21. Permainan statistik. Prinsip dan kriteria pengambilan keputusan dalam kondisi ketidakpastian total dan sebagian.

Dalam riset operasi, biasanya kita membedakan tiga jenis ketidakpastian:

ketidakpastian tujuan;

ketidakpastian pengetahuan kita tentang lingkungan dan faktor-faktor yang berperan dalam fenomena tersebut (ketidakpastian alam);

ketidakpastian tindakan mitra atau musuh aktif atau pasif.

Dalam klasifikasi di atas, jenis ketidakpastian dipertimbangkan dari sudut pandang satu atau beberapa elemen model matematika. Misalnya, ketidakpastian tujuan tercermin ketika menetapkan tugas dalam memilih kriteria individu atau seluruh vektor efek menguntungkan.

Di sisi lain, dua jenis ketidakpastian lainnya terutama mempengaruhi perumusan fungsi tujuan persamaan kendala dan metode pengambilan keputusan. Tentu saja, pernyataan di atas agak sewenang-wenang, seperti halnya klasifikasi apa pun. Kami menyajikannya hanya dengan tujuan untuk menyoroti beberapa fitur ketidakpastian yang harus diingat dalam proses pengambilan keputusan.

Intinya, selain klasifikasi ketidakpastian yang dibahas di atas, perlu juga mempertimbangkan jenis (atau “genus”) dari sudut pandang hubungannya dengan keacakan.

Atas dasar ini, ketidakpastian stokastik (probabilistik) dapat dibedakan, ketika faktor-faktor yang tidak diketahui stabil secara statistik dan oleh karena itu mewakili objek teori probabilitas biasa - variabel acak (atau fungsi acak, peristiwa, dll.). Dalam hal ini, semua karakteristik statistik yang diperlukan (pola distribusi dan parameternya) harus diketahui atau ditentukan ketika menetapkan masalah.

Contoh tugas tersebut dapat berupa, khususnya, sistem pemeliharaan dan perbaikan semua jenis peralatan, sistem pengorganisasian penjarangan, dll.

Kasus ekstrem lainnya mungkin adalah ketidakpastian tipe non-stokastik (dalam kata-kata E.S. Ventzel - “ketidakpastian buruk”), di mana tidak ada asumsi tentang stabilitas stokastik. Terakhir, kita dapat berbicara tentang jenis ketidakpastian perantara, ketika keputusan dibuat berdasarkan beberapa hipotesis tentang hukum distribusi variabel acak. Pada saat yang sama, pengambil keputusan harus mengingat bahaya ketidaksesuaian antara hasil yang diperolehnya dan kondisi nyata. Risiko ketidaksesuaian ini diformalkan dengan menggunakan koefisien risiko.

Pengambilan keputusan dalam kondisi berisiko dapat didasarkan pada salah satu kriteria berikut:

kriteria nilai yang diharapkan;

kombinasi nilai yang diharapkan dan varians;

tingkat batas yang diketahui;

peristiwa yang paling mungkin terjadi di masa depan.

Bab 1. Pokok bahasan dan tugas riset operasi.

§ 1. Apa itu riset operasi dan apa fungsinya.

§ 2. Konsep dasar dan prinsip riset operasi.

§ 3. Model operasi matematika.

Bab 2. Macam-macam masalah riset operasi dan pendekatan pemecahannya.

§ 4. Masalah riset operasi langsung dan terbalik. Tugas deterministik.

§ 5. Masalah memilih solusi dalam kondisi ketidakpastian.

§ 6. Masalah multikriteria dalam riset operasi. "Pendekatan sistem".

Bab 3. Pemrograman linier.

§ 7. Masalah pemrograman linier.

§ 8. Masalah utama pemrograman linier.

§ 9. Adanya solusi 03LP dan metode pencariannya.

§ 10. Masalah transportasi program linier.

§ 11. Masalah pemrograman bilangan bulat. Konsep pemrograman nonlinier.

Bab 4. Pemrograman dinamis.

§ 12. Metode pemrograman dinamis.

§ 13. Contoh penyelesaian masalah pemrograman dinamis.

§ 14. Masalah pemrograman dinamis dalam bentuk umum. Prinsip optimalitas.

Bab 5. Proses acak Markov.

§ 15. Konsep proses Markov.

§ 16. Aliran peristiwa.

§ 17. Persamaan Kolmogorov untuk probabilitas keadaan. Probabilitas keadaan akhir.

Bab 6. Teori antrian.

§ 18. Masalah teori antrian. Klasifikasi sistem antrian.

§ 19. Skema kematian dan reproduksi. Rumus si kecil.

§ 20. Sistem antrian paling sederhana dan karakteristiknya.

§ 21. Masalah teori antrian yang lebih kompleks.

Bab 7. Pemodelan statistik proses acak (metode Monte Carlo).

§ 22. Ide, tujuan dan ruang lingkup penerapan metode.

§ 23. Lot tunggal dan bentuk organisasinya.

§ 24. Penentuan karakteristik proses acak stasioner berdasarkan satu implementasi.

Bab 8. Metode permainan untuk mendukung suatu keputusan.

§ 25. Pokok bahasan dan tugas teori permainan.

§ 26. Permainan matriks antagonis.

§ 27. Metode untuk menyelesaikan permainan terbatas.

§ 28. Masalah teori solusi statistik.

SUBJEK DAN TUJUAN PENELITIAN OPERASI

Konsep dasar dan prinsip riset operasi

Pada bagian ini kita akan mengenal terminologi, konsep dasar dan prinsip ilmu “riset operasi”.

Operasi adalah setiap peristiwa (sistem tindakan) yang disatukan oleh satu rencana dan ditujukan untuk mencapai suatu tujuan (semua peristiwa yang dibahas dalam paragraf 1 - 8 paragraf sebelumnya adalah “operasi”).

Suatu operasi selalu merupakan peristiwa yang terkendali, artinya tergantung pada kita bagaimana memilih beberapa parameter yang menjadi ciri organisasinya. “Organisasi” di sini dipahami dalam arti luas, termasuk seperangkat sarana teknis yang digunakan dalam operasi.

Pilihan parameter tertentu yang bergantung pada kita disebut solusi. Keputusan bisa berhasil dan tidak berhasil, masuk akal dan tidak masuk akal. Solusi optimal adalah solusi yang lebih disukai daripada solusi lain berdasarkan karakteristik tertentu. Tujuan dari riset operasi adalah pembenaran kuantitatif awal atas solusi optimal.

Kadang-kadang (relatif jarang) sebagai hasil penelitian dimungkinkan untuk menunjukkan satu solusi yang benar-benar optimal, lebih sering lagi dimungkinkan untuk mengidentifikasi wilayah solusi optimal (masuk akal) yang hampir setara di mana pilihan akhir dapat dibuat.

Perhatikan bahwa pengambilan keputusan itu sendiri melampaui lingkup studi operasi dan berada dalam kompetensi orang yang bertanggung jawab, lebih sering - sekelompok orang yang diberi hak untuk memilih akhir dan bertanggung jawab atas pilihan ini. Dalam menentukan pilihan, mereka dapat mempertimbangkan, bersama dengan rekomendasi yang timbul dari perhitungan matematis, sejumlah pertimbangan (kuantitatif dan kualitatif) yang tidak diperhitungkan dalam perhitungan ini.

Kehadiran seseorang yang sangat diperlukan (sebagai pengambil keputusan akhir) tidak dibatalkan bahkan dengan adanya sistem kendali yang sepenuhnya otomatis, yang tampaknya membuat keputusan tanpa campur tangan manusia. Kita tidak boleh lupa bahwa pembuatan algoritma kontrol, pilihan salah satu opsi yang memungkinkan, juga merupakan keputusan, dan keputusan yang sangat bertanggung jawab. Seiring berkembangnya automata kendali, fungsi manusia tidak dibatalkan, tetapi hanya dipindahkan dari satu tingkat dasar ke tingkat lain yang lebih tinggi. Selain itu, sejumlah sistem kendali otomatis menyediakan intervensi aktif manusia selama proses pengendalian.

Parameter-parameter tersebut, yang kombinasinya membentuk suatu solusi, disebut elemen solusi. Berbagai bilangan, vektor, fungsi, ciri fisik, dan lain-lain dapat muncul sebagai elemen penyelesaian, misalnya jika dibuat rencana pengangkutan barang homogen dari titik pemberangkatan. SEBUAH 1, SEBUAH 2,…, Saya ke tujuan DALAM 1,B 2, ..., B n, maka unsur penyelesaiannya adalah bilangan x ij , menunjukkan berapa banyak kargo yang akan dikirim dari titik keberangkatan pertama dan saya V J tujuan ke- di j. Seperangkat angka X 11 , X 12, …, X 1 n , …, X m 1, X m2,…, x mn membentuk solusi.

Dalam permasalahan riset operasi yang paling sederhana, jumlah elemen solusi bisa jadi relatif kecil. Namun dalam sebagian besar masalah yang penting secara praktis, jumlah elemen solusi sangat banyak, karena pembaca dapat memverifikasinya dengan mencoba mengidentifikasi dan “memberi nama” secara mandiri elemen solusi dalam contoh 1 - 8 paragraf sebelumnya. Untuk mempermudah, kami akan menyatakan seluruh himpunan elemen solusi dengan satu huruf X dan ucapkan "keputusan" X".

Selain unsur-unsur solusi yang sampai batas tertentu dapat kita kendalikan, dalam setiap tugas riset operasi juga diberikan kondisi “mendisiplinkan” yang sudah ditetapkan sejak awal dan tidak dapat dilanggar (misalnya, kapasitas beban mesin, ukuran tugas yang direncanakan;

karakteristik berat peralatan, dll.). Secara khusus, kondisi tersebut mencakup sarana (materi, teknis, manusia) yang berhak kami gunakan, dan pembatasan lain yang dikenakan pada keputusan tersebut. Secara bersama-sama, mereka membentuk apa yang disebut “serangkaian solusi yang mungkin.”

Mari kita nyatakan himpunan ini lagi dengan satu huruf X, dan fakta bahwa keputusan tersebut X milik himpunan ini, kami akan menuliskannya sebagai rumus: X X(baca: elemen X termasuk dalam set X).

Intinya adalah dalam banyak kemungkinan solusi X soroti solusi tersebut X(terkadang satu, tetapi lebih sering seluruh area solusi), yang dari sudut pandang tertentu lebih efektif (berhasil, lebih disukai) daripada yang lain. Untuk membandingkan solusi yang berbeda dalam hal efisiensi, Anda perlu memiliki semacam kriteria kuantitatif, yang disebut indikator efisiensi (sering disebut “fungsi tujuan”). Indikator ini dipilih sehingga mencerminkan orientasi sasaran operasi. Solusi “terbaik” akan dianggap sebagai solusi yang paling berkontribusi terhadap pencapaian tujuan. Untuk memilih, “nama demi nama” sebagai indikator kinerja W, Pertama-tama, Anda perlu bertanya pada diri sendiri: apa yang kita inginkan Apa tujuan kita saat melakukan operasi? Saat memilih solusi, tentu saja kita akan memilih solusi yang membalikkan indikator efisiensi W secara maksimal (atau minimal). Misalnya, saya ingin memaksimalkan pendapatan dari sebuah operasi; jika indikator efisiensi adalah biaya, disarankan untuk menguranginya seminimal mungkin. Jika diinginkan untuk memaksimalkan indikator efisiensi, kami akan menuliskannya dalam bentuk W => maks, dan jika diminimalkan - W => menit.

Seringkali, pengoperasian disertai dengan faktor acak (keanehan cuaca, fluktuasi pasokan dan permintaan, kegagalan perangkat teknis, dll.). Dalam kasus seperti itu, biasanya bukan nilai itu sendiri yang ingin dimaksimalkan (diminimalkan), melainkan nilai rata-ratanya (ekspektasi matematis) yang dijadikan indikator efisiensi.

Dalam beberapa kasus, suatu operasi, disertai dengan faktor acak, memiliki tujuan yang sangat spesifik A, yang hanya dapat dicapai sepenuhnya atau tidak tercapai sama sekali (skema “ya-tidak”), dan kami tidak tertarik pada hasil antara apa pun. Kemudian probabilitas tercapainya tujuan tersebut dipilih sebagai indikator efisiensi R(A). Misalnya, jika penembakan dilakukan pada suatu objek dengan kondisi yang sangat diperlukan untuk menghancurkannya, maka indikator efektivitasnya adalah kemungkinan hancurnya objek tersebut.

Memilih indikator kinerja yang salah sangatlah berbahaya. Operasi yang diselenggarakan berdasarkan kriteria yang dipilih secara tidak berhasil dapat menyebabkan biaya dan kerugian yang tidak dapat dibenarkan (mari kita ingat, misalnya, “poros” yang terkenal sebagai kriteria utama untuk menilai kegiatan ekonomi perusahaan).

Untuk mengilustrasikan prinsip pemilihan indikator efisiensi, mari kita kembali ke contoh 1 - 8 dari § 1, pilih indikator efisiensi alami untuk masing-masing indikator dan tunjukkan apakah perlu dimaksimalkan atau diminimalkan. Saat menganalisis contoh, perlu diingat bahwa tidak semuanya pilihan indikator kinerja ditentukan dengan jelas oleh deskripsi verbal tugas, sehingga mungkin ada perbedaan antara pembaca dan penulis mengenai masalah ini.

1. Rencana pasokan perusahaan. Tujuan dari operasi ini adalah untuk memastikan pasokan bahan baku sekaligus meminimalkan biaya transportasi. Indikator kinerja R- total biaya pengangkutan bahan mentah per satuan waktu, misalnya sebulan ( R => menit).

2. Pembangunan suatu ruas jalan raya. Pembangunannya perlu direncanakan sedemikian rupa agar dapat diselesaikan secepatnya. Indikator efisiensi alami adalah waktu penyelesaian konstruksi, jika tidak dikaitkan dengan faktor acak (kegagalan peralatan, keterlambatan penyelesaian pekerjaan individu). Oleh karena itu, rata-rata waktu yang diharapkan dapat dipilih sebagai indikator efisiensi T penyelesaian konstruksi (T => menit).

3. Penjualan barang musiman. Sebagai indikator efisiensi, kita dapat mengambil rata-rata keuntungan yang diharapkan P dari penjualan barang pada musim tersebut (P => maks).

4. Perlindungan jalan dari salju. Kita berbicara tentang rencana perlindungan salju yang paling menguntungkan secara ekonomi, sehingga biaya rata-rata per unit waktu (misalnya, per tahun) dapat dipilih sebagai indikator efisiensi R untuk pemeliharaan dan pengoperasian jalan, termasuk biaya yang terkait dengan pembangunan alat pelindung diri dan pembersihan jalan serta penundaan lalu lintas (R => menit).

5. Serangan anti-kapal selam. Karena penggerebekan itu memiliki tujuan yang sangat spesifik A - kehancuran kapal, maka probabilitas harus dipilih sebagai indikator efektivitas R(A) bahwa perahu itu akan dihancurkan.

6. Pengendalian sampel produk. Indikator alami efisiensi, yang disarankan oleh rumusan masalah, adalah biaya rata-rata yang diharapkan R untuk pengendalian per satuan waktu, asalkan sistem pengendalian menjamin tingkat kualitas tertentu, misalnya persentase rata-rata cacat tidak lebih tinggi dari persentase tertentu ( R=> menit).

7. Pemeriksaan kesehatan. Anda dapat memilih persentase rata-rata (share) sebagai indikator efisiensi Q pasien dan pembawa infeksi yang diidentifikasi (Q => memeriksa).

8. Pelayanan perpustakaan. Beberapa ketidakjelasan sengaja dibiarkan dalam rumusan masalah:

Tidak jelas apa yang dimaksud dengan “layanan pelanggan terbaik” atau “memuaskan permintaan mereka semaksimal mungkin”. Jika kualitas pelayanan dinilai dari waktu tunggu pelanggan yang meminta buku untuk menerimanya, maka waktu rata-rata dapat dijadikan indikator efisiensi. T ekspektasi buku oleh pembaca yang mengajukan permohonan untuk itu ( T=> mnt). Anda dapat mendekati masalah ini dari posisi yang sedikit berbeda, dengan memilih angka rata-rata sebagai indikator efisiensi M buku yang diterbitkan per satuan waktu (M => maks).

Contoh-contoh yang dipertimbangkan dipilih secara khusus sedemikian sederhana sehingga pemilihan indikator kinerja relatif mudah dan langsung ditentukan oleh rumusan masalah secara verbal dan (hampir selalu) orientasi sasarannya yang jelas. Namun, dalam praktiknya hal ini tidak selalu terjadi. Pembaca dapat memverifikasi hal ini dengan mencoba, misalnya, memilih indikator efisiensi transportasi perkotaan. Apa yang harus kita ambil sebagai indikator? Kecepatan rata-rata penumpang yang bepergian keliling kota? Atau rata-rata jumlah penumpang yang diangkut? Atau berapa rata-rata kilometer yang harus ditempuh seseorang yang tidak dapat diangkut ke tempat yang tepat dengan berjalan kaki? Ada banyak hal yang perlu dipikirkan di sini!

Sayangnya, dalam sebagian besar masalah yang penting secara praktis, pemilihan indikator efisiensi tidaklah sederhana dan diselesaikan secara ambigu. Untuk tugas kompleks apa pun, situasi biasanya terjadi ketika efektivitas operasi tidak dapat dikarakterisasi secara mendalam oleh satu angka - angka lain harus dilibatkan untuk membantunya. Kita akan mengenal masalah “multi-kriteria” seperti itu di § 6.

Contoh penyelesaian masalah pemrograman dinamis

Pada bagian ini kita akan melihat (dan bahkan menyelesaikan sampai akhir) beberapa contoh masalah pemrograman dinamis yang sederhana (sangat disederhanakan).

1. Meletakkan rute yang paling menguntungkan antara dua titik. Mari kita mengingat kembali masalah 4 paragraf sebelumnya dan menyelesaikannya sampai akhir dalam kondisi yang sangat (dan sengaja) disederhanakan. Kita perlu membangun jalur yang menghubungkan

dua poin A Dan DI DALAM, yang kedua terletak di timur laut yang pertama. Untuk mempermudah, katakanlah. bahwa pembuatan jalan terdiri dari serangkaian langkah, dan pada setiap langkah kita dapat bergerak ke arah timur atau ke utara; dari mana pun A V DI DALAM adalah garis putus-putus berundak yang ruas-ruasnya sejajar dengan salah satu sumbu koordinat (Gbr. 13.1). Biaya pembangunan masing-masing bagian ini diketahui. Diperlukan untuk meletakkan jalan seperti itu A V DI DALAM, dimana total biayanya minimal.

Bagaimana cara melakukannya? Anda dapat melakukan salah satu dari dua cara ini: menelusuri semua opsi jalur yang mungkin dan memilih salah satu dengan biaya minimal (dan dengan jumlah segmen yang banyak, hal ini sangat, sangat sulit!); atau pisahkan proses transisi dari A V DI DALAM menjadi langkah-langkah terpisah (satu langkah - satu segmen) dan mengoptimalkan kontrol langkah demi langkah. Ternyata cara kedua jauh lebih nyaman! Di Sini, Seperti halnya penelitian operasi lainnya, terdapat keuntungan dari pencarian solusi yang terarah dan terorganisir dibandingkan pencarian “buta” yang naif.

Mari kita tunjukkan bagaimana hal ini dilakukan dengan contoh spesifik. Bagilah jarak dari A sebelum DI DALAM di arah timur, katakanlah, menjadi 7 bagian, dan di arah utara - menjadi 5 bagian (pada prinsipnya penghancuran bisa sekecil yang diinginkan). Lalu jalan mana pun dari A V DI DALAM terdiri dari T= 7 + 5 == 12 ruas mengarah ke timur atau utara (Gbr. 13.2). Mari kita beri nomor pada setiap segmen yang menyatakan (dalam beberapa satuan konvensional) biaya pembuatan jalur di sepanjang segmen ini. Anda harus memilih jalur ini A V DI DALAM, yang jumlah bilangan pada ruas-ruasnya minimal.

Kami akan menganggap jalur yang sedang dibangun sebagai sistem terkendali S, bergerak di bawah pengaruh kendali dari keadaan awal A sampai akhir DI DALAM. Keadaan sistem ini sebelum dimulainya setiap langkah akan dicirikan oleh dua koordinat: timur (X) dan utara (kamu), keduanya bilangan bulat (0 X 5 7, 0 pada 5). Untuk setiap keadaan sistem (titik nodal dari grid persegi panjang pada Gambar 13.2), kita harus menemukan kontrol optimal bersyarat: kita harus bergerak dari titik ini ke utara (kontrol “c”) atau ke timur (kontrol "C"). Pengendalian ini dipilih sehingga biaya seluruh langkah yang tersisa hingga akhir (termasuk langkah ini) menjadi minimal. Kami akan terus menyebut biaya ini sebagai “keuntungan optimal bersyarat” (walaupun dalam kasus ini bukan “kemenangan”, melainkan “kerugian”) untuk keadaan sistem tertentu. S sebelum memulai langkah berikutnya.

Kami akan memperluas prosedur optimasi bersyarat ke arah yang berlawanan - dari akhir ke awal. Pertama-tama, kita akan melakukan optimasi bersyarat pada langkah terakhir ke-12. Mari kita perhatikan secara terpisah sudut kanan atas kotak persegi panjang kita (Gbr. 13.3). Di manakah kita bisa berada setelah langkah ke-11? Hanya

di mana dalam satu langkah (terakhir) Anda bisa mencapainya DI DALAM, yaitu di salah satu titik DALAM 1 atau PADA 2 . Jika kita berada pada suatu titik DALAM 1 , kita tidak punya pilihan (kontrol paksa): kita harus pergi ke timur, dan biayanya 10 unit. Mari kita tuliskan angka 10 ini dalam lingkaran dekat titik DALAM 1 , dan kami menunjukkan kontrol optimal dengan panah pendek yang berasal dari DALAM 1 dan mengarah ke timur. Untuk satu hal PADA 2 kontrolnya juga dipaksa (utara), laju aliran ke ujung adalah 14, kita tuliskan dalam lingkaran di titik tersebut PADA 2 . Dengan demikian, optimasi bersyarat dari langkah terakhir telah selesai, dan perolehan optimal bersyarat untuk setiap titik adalah B 1, B 2 ditemukan dan dicatat dalam lingkaran yang sesuai.

Sekarang mari kita optimalkan langkah kedua dari belakang (11). Setelah langkah kedua dari belakang (ke-10) kita bisa sampai pada salah satu poin C 1, C 2, C 3(Gbr. 13.4). Mari kita cari masing-masing kontrol optimal bersyarat dan penguatan optimal bersyarat. Untuk satu hal C 1 kontrol paksa: pergi ke timur;

kita akan dikenakan biaya 21 unit sampai akhir (11 pada langkah ini, ditambah 10 yang ditulis dalam lingkaran di DALAM 1). Kita tuliskan angka 21 dalam lingkaran pada titik tersebut C 1. Untuk satu hal dari 2 kendali tidak lagi dipaksakan: kita bisa pergi ke timur dan utara. Dalam kasus pertama, kita akan menghabiskan 14 unit pada langkah ini dan dari PADA 2 Tinggal 14 unit lagi, total 28 unit. Jika kita ke utara, kita akan menghabiskan 13 + 10, totalnya 23 unit. Artinya pengendalian optimal bersyarat pada titik tersebut dari 2 - pergi ke utara (kita tandai dengan panah, dan tuliskan angka 23 dalam lingkaran di dekatnya dari 2), Untuk satu hal dari 3 kontrolnya dipaksa lagi (“dengan”), ini akan memakan biaya 22 unit sampai akhir (letakkan panah ke utara, tulis angka 22 dalam lingkaran di dari 3).

Demikian pula, “mundur” dari langkah mundur kedua dari belakang, kita menemukan untuk setiap titik dengan koordinat bilangan bulat kontrol optimal bersyarat (“c” atau “c”), yang kita nyatakan dengan panah, dan penguatan optimal bersyarat (konsumsi ke ujung jalan), yang kita tulis dalam lingkaran. Ini dihitung sebagai berikut: laju aliran pada langkah ini ditambahkan ke laju aliran yang sudah dioptimalkan, ditulis dalam lingkaran yang ditunjuk oleh panah. Jadi, pada setiap langkah kami hanya mengoptimalkan langkah ini, dan langkah berikutnya sudah dioptimalkan. Hasil akhir dari prosedur optimasi ditunjukkan pada Gambar. 13.5.

Dengan demikian, optimasi bersyarat telah selesai: tidak peduli di titik simpul mana kita berada, kita sudah tahu ke mana harus pergi (panah) dan berapa biaya yang harus dikeluarkan untuk mencapai titik akhir (angka dalam lingkaran). Dalam lingkaran di suatu titik A penguatan optimal dicatat untuk seluruh konstruksi jalur dari A V DI DALAM:

W* = 118.

Sekarang tinggal membangun kendali optimal tanpa syarat - sebuah lintasan yang mengarah dari A Dan DI DALAM dengan cara termurah. Untuk melakukan ini, Anda hanya perlu “mendengarkan panah”, yaitu membaca apa yang mereka perintahkan untuk Anda lakukan di setiap langkah. Lintasan optimal ini ditandai pada Gambar. 13,5 dilingkari dua kali. Kontrol optimal tanpa syarat yang sesuai adalah:

x* =(s, s, s, s, di, di, s, di, di, di, di, di)

yaitu, kita harus mengambil empat langkah pertama ke utara, dua langkah berikutnya ke timur, lalu satu langkah lagi ke utara dan lima langkah sisanya ke timur. Masalah terpecahkan.

Perhatikan bahwa selama optimasi bersyarat kita mungkin menghadapi kasus di mana kedua kontrol untuk beberapa titik pada bidang adalah optimal, yaitu, keduanya menyebabkan pengeluaran dana yang sama dari titik ini hingga akhir. Misalnya, pada titik dengan koordinat (5; 1) kedua kontrol “c” dan “b” optimal dan memberikan laju aliran ke ujung sama dengan 62. Kami secara sewenang-wenang memilih salah satu dari mereka (dalam kasus kami, kami memilih “c”; dengan keberhasilan yang sama kami dapat memilih “c ”). Kasus-kasus pilihan kontrol optimal yang ambigu seperti itu terus-menerus ditemui dalam pemrograman dinamis; di masa depan kami tidak akan menandainya secara khusus, tetapi hanya akan memilih secara sewenang-wenang salah satu opsi yang setara. Tentu saja, kendali optimal atas keseluruhan proses, namun bukan perolehan optimal, mungkin bergantung pada kesewenang-wenangan ini. Secara umum, dalam permasalahan pemrograman dinamis (seperti dalam permasalahan pemrograman linier), solusinya tidak selalu merupakan satu-satunya.

Sekarang mari kita kembali ke awal dan mencoba menyelesaikan masalah dengan cara yang “naif”, memilih di setiap langkah, mulai dari arah pertama yang paling menguntungkan (untuk langkah ini) (jika ada dua, pilih salah satu ). Dengan cara ini kita akan mendapatkan kendali

x = (c, s, di, di, di, di, s, di, di, di, s, s).

Mari kita hitung biaya lintasan ini. Mereka akan setara W=10 +12 +8+10 +11 +13 +15+8 + +10+9+8+14=128, yang tentunya lebih dari W* = 118. Dalam kasus ini perbedaannya tidak terlalu besar, namun dalam kasus lain perbedaannya mungkin signifikan.

Dalam permasalahan yang dipecahkan di atas, kondisinya sengaja disederhanakan hingga ekstrim. Tentu saja, tidak ada seorang pun yang akan melewati jalur kereta api “demi langkah”, hanya bergerak ke utara atau ke timur. Kami membuat penyederhanaan ini untuk memilih di setiap titik hanya dari dua kontrol: “c” atau “c”. Daripada menggunakan dua arah, kita bisa memperkenalkan beberapa arah dan, sebagai tambahan, mengambil langkah-langkah yang lebih kecil; Hal ini tidak terlalu penting, tetapi tentu saja mempersulit dan memperpanjang perhitungan.

Perhatikan bahwa masalah serupa dengan yang dibahas di atas sangat sering ditemui dalam praktik: misalnya, ketika memilih jalur tercepat antara dua titik atau peningkatan kecepatan dan ketinggian yang paling ekonomis (dalam hal konsumsi bahan bakar) oleh sebuah pesawat terbang.

Mari kita membuat satu komentar sekilas. Pembaca yang penuh perhatian mungkin telah memperhatikan bahwa dalam masalah kita ada poin-poinnya A Dan DI DALAM(awal dan akhir) pada prinsipnya tidak berbeda satu sama lain: adalah mungkin untuk membangun kontrol optimal bersyarat bukan dari akhir ke awal, tetapi dari awal ke akhir, dan kontrol optimal tanpa syarat - dalam arah yang berlawanan. Memang benar: dalam masalah pemrograman dinamis apa pun, "awal" dan "akhir" dapat ditukar. Ini sepenuhnya setara dengan metode yang dijelaskan sebelumnya dalam hal perhitungan, tetapi agak kurang nyaman ketika menjelaskan gagasan metode secara lisan: lebih mudah untuk berdebat dengan mengacu pada kondisi "yang sudah ditetapkan" di awal suatu langkah tertentu dibandingkan dengan mereka yang masih “akan datang” setelah langkah ini. Intinya, kedua pendekatan tersebut sepenuhnya setara.

2. Masalah alokasi sumber daya. Metode pemrograman dinamis memungkinkan Anda berhasil memecahkan banyak masalah ekonomi (lihat, misalnya). Mari kita pertimbangkan salah satu masalah paling sederhana. Kami memiliki sejumlah cadangan dana (sumber daya) KE, yang harus didistribusikan antara T perusahaan P 1, P 2, ..., P m. Masing-masing perusahaan P Saya ketika menginvestasikan sejumlah uang di dalamnya X menghasilkan pendapatan tergantung pada X, yaitu mewakili beberapa jenis fungsi ( X). Semua fungsi ( X) (Saya = 1, 2, ..., T) diberikan (tentu saja, fungsi-fungsi ini tidak berkurang). Pertanyaannya adalah bagaimana dana tersebut harus disalurkan? KE. antar perusahaan sehingga secara total memberikan pendapatan yang maksimal?

Masalah ini mudah diselesaikan dengan metode pemrograman dinamis, walaupun dalam rumusannya tidak disebutkan waktu, namun secara mental Anda tetap dapat menerapkan operasi penyaluran dana dalam urutan tertentu, mengingat langkah pertama yang harus dilakukan adalah menginvestasikan dana di dalamnya. perusahaan P 1, yang kedua - ke P 2, dll.

Sistem yang dikelola S dalam hal ini dana atau sumber daya yang disalurkan. Keadaan sistem S sebelum setiap langkah ditandai dengan satu angka S- cadangan kas dari dana yang belum diinvestasikan. Dalam permasalahan ini, “kontrol langkah” adalah sarananya x 1, x 2, ..., x 3, dialokasikan kepada perusahaan. Diperlukan untuk menemukan kontrol optimal, yaitu sekumpulan angka x 1, x 2, ..., xm, di mana total pendapatan maksimum:

(13.1)

Mari kita selesaikan masalah ini terlebih dahulu dalam bentuk rumusan umum, dan kemudian untuk data numerik tertentu. Kami akan menemukan sesuatu untuk semua orang Saya langkah ke-th adalah keuntungan optimal bersyarat (dari langkah ini hingga akhir), jika kita mendekati langkah ini dengan cadangan dana S. Mari kita nyatakan penguatan optimal bersyarat W saya (S), dan pengendalian optimal bersyarat yang sesuai adalah dana yang diinvestasikan Saya-perusahaan ke-, - xi(S).

Mari kita mulai optimasi dari yang terakhir, T - langkah ke-th. Mari kita dekati langkah ini dengan sisa dana S. Apa yang harus kita lakukan? Tentu saja, investasikan seluruh jumlahnya S seluruhnya di perusahaan P M. Oleh karena itu, kendali optimal bersyarat aktif M-langkah: berikan semua dana yang tersedia kepada perusahaan terakhir S, yaitu

dan keuntungan optimal bersyarat

Wm (S)= (S).

Mengingat berbagai macam arti S(menempatkannya cukup dekat), untuk setiap nilai kita S kita akan tahu xm(S) Dan Wm(S). Langkah terakhir dioptimalkan.

Mari kita beralih ke yang kedua dari belakang, (T- 1) langkah ke-. Mari kita dekati dia dengan dana cadangan S. Mari kita tunjukkan W m -1 (S) hasil optimal bersyarat pada dua langkah terakhir: ( M- 1) dan M-m (yang sudah dioptimalkan). Jika kita memilih berdasarkan ( M- 1)langkah ke-( M- 1) sarana perusahaan X, maka langkah terakhir akan tetap ada S-x. Imbalan kita pada dua langkah terakhir akan sama

,

dan Anda perlu menemukan sesuatu seperti ini X, di mana keuntungan ini maksimum:

Tandanya berarti nilai maksimal diambil alih semua X, mungkin (berinvestasi lebih dari S, kita tidak bisa), dari ekspresi dalam tanda kurung kurawal. Maksimum ini adalah hasil optimal bersyarat untuk dua langkah terakhir, jika tidak maka nilainya X, dimana maksimum ini tercapai adalah kendali optimal bersyarat aktif (T- 1) langkah ke-1.

dan kontrol optimal bersyarat yang sesuai x saya (S) - lalu nilainya X, di mana maksimum ini tercapai.

Melanjutkan cara ini, kita akhirnya akan mencapai perusahaan pertama P 1. Di sini kita tidak perlu memvariasikan nilainya S; kita tahu pasti bahwa cadangan dana sebelum langkah pertama adalah sama KE:

Jadi, keuntungan (pendapatan) maksimum dari semua perusahaan telah ditemukan. Sekarang yang tersisa hanyalah “membaca rekomendasinya.” Artinya X, dimana maksimum (13,4) tercapai, dan terdapat pengendalian optimal pada langkah pertama. Setelah kami menginvestasikan dana ini di perusahaan pertama, kami akan memilikinya KE- ."Membaca" rekomendasi untuk nilai ini S, Kami mengalokasikan jumlah dana optimal untuk perusahaan kedua:

,

dll sampai akhir.

Sekarang mari kita selesaikan dengan contoh numerik. Stok dana awal K = 10 (unit konvensional), dan perlu didistribusikan secara optimal kepada lima perusahaan (t = 5). Untuk mempermudah, kita asumsikan hanya sejumlah dana yang diinvestasikan. Fungsi pendapatan ( X) diberikan pada tabel 13.1.

Tabel 13.1

X
	0,5 1,0 1,4 2,0 2,5 2,8 3,0 3,0	0,1 0,5 1,2 1,8 2,5 2,9 3,5 3,5	0,6 1,1 1,2 1,4 1,6 1,7 1,8 1,8	0,3 0,6 1,3 1,4 1,5 1,5 1,5 1,5	1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3

Di setiap kolom, mulai dari sejumlah investasi tertentu, pendapatan berhenti meningkat (pada kenyataannya, hal ini sesuai dengan kenyataan bahwa setiap perusahaan hanya mampu “menguasai” sejumlah dana terbatas).

Mari kita lakukan optimasi bersyarat seperti dijelaskan di atas, dimulai dari langkah ke-5 yang terakhir. Setiap kali kita mendekati langkah berikutnya, memiliki dana cadangan S, kita coba alokasikan dana ini atau itu untuk langkah ini, ambil kemenangan pada langkah ini sesuai tabel 13.1, tambahkan dengan kemenangan yang sudah dioptimalkan di semua langkah berikutnya sampai akhir (mengingat sisa dana kita sudah lebih sedikit, cukup untuk jumlah dana ini, yang telah kami soroti) dan temukan investasi di mana jumlah ini mencapai maksimum. Investasi ini adalah kontrol optimal bersyarat pada langkah ini, dan nilai maksimumnya sendiri adalah keuntungan optimal bersyarat.

Tabel 13.2 menunjukkan hasil optimasi bersyarat untuk semua langkah. Tabelnya disusun sebagai berikut: kolom pertama menunjukkan nilai stok dana S, s yang kita dekati pada langkah ini. Tabel ini selanjutnya dibagi menjadi lima pasang kolom, sesuai dengan nomor langkah. Kolom pertama dari setiap pasangan berisi nilai

Tabel 13.2

S	saya=5	saya=4	saya=3	saya=2	saya=1
x 5(S)	W 5(S)	x 4(S)	W 4(S)	x 3(S)	W 3(S)	x 2(S)	W 2(S)	x 1(S)	W 1(S)
		1,0 1,2 1,3 1,3 1,3 1,3 1,3 1,3 1,3 1,3		1,0 1,3 1,6 2,3 2,5 2,6 2,7 2,8 2,8 2,8		1,0 1,6 2,1 2,4 2,9 3,4 3,6 3,7 3,9 4,1		1,0 1,6 2,1 2,4 2,9 3,5 4,1 4,6 5,1 5,6		5,6

kontrol optimal bersyarat, yang kedua - penguatan optimal bersyarat. Tabel diisi dari kiri ke kanan, atas ke bawah. Keputusan pada langkah kelima - terakhir - terpaksa: semua dana dialokasikan;

Pada semua langkah lainnya, solusinya harus dioptimalkan. Sebagai hasil dari optimasi sekuensial pada langkah ke-5, ke-4, ke-3, ke-2 dan ke-1, kita akan memperoleh daftar lengkap semua rekomendasi untuk kontrol optimal dan penguatan optimal tanpa syarat. A* untuk seluruh operasi - dalam hal ini sama dengan 5.6. Pada dua kolom terakhir Tabel 13.2, hanya satu baris yang diisi, karena kita mengetahui secara pasti keadaan sistem sebelum memulai langkah pertama:

S 0 = K = 10. Kontrol optimal di semua langkah disorot dengan bingkai. Jadi, kita mendapat kesimpulan akhir: kita harus mengalokasikan dua unit dari sepuluh ke perusahaan pertama, lima unit ke perusahaan kedua, dua unit ke perusahaan ketiga, tidak satu pun ke perusahaan keempat, dan satu unit ke perusahaan kelima. Dengan pembagian ini pendapatan akan maksimal dan setara dengan 5,6.

Untuk memperjelas kepada pembaca bagaimana Tabel 13.2 diisi, kami akan mendemonstrasikannya dengan menggunakan satu contoh perhitungan. Misalnya, kita perlu mengoptimalkan solusinya x 3(7)- apa yang harus dilakukan pada langkah ketiga jika kita mendekatinya dengan dana cadangan S= 7, dan berapa jumlah maksimum yang bisa kita menangkan pada semua sisanya

Tabel 13.3

X	7 - X		W 4(7 - X)	+W 4 (7 - X)
		1,8 1,7 1,6 1,4 1,2 1,1 0,6	1,0 1,3 1,6 2,3 2,5 2,6 2,7	1,8 2,7 2,9 3,0 3,5 3,2 2,7

langkah, termasuk yang ketiga? Mari kita asumsikan bahwa semua langkah setelah langkah ketiga (4 dan 5) telah dioptimalkan, yaitu dua pasang kolom pertama pada Tabel 13.2 terisi. Kami akan menemukannya X 3 (7) dan W 3(7). Untuk melakukan ini, kita akan membuat tabel tambahan (lihat Tabel 13.3). Kolom pertamanya mencantumkan semua kemungkinan lampiran X pada langkah ketiga, tidak melebihi S = 7. Di kolom kedua - apa yang tersisa setelah investasi dari dana cadangan S = 7. Di kolom ketiga - kemenangan pada langkah ketiga dari dana investasi X pada perusahaan ketiga diisi sesuai kolom (Tabel 13.1). Pada kolom keempat - kemenangan optimal pada semua langkah yang tersisa (keempat dan kelima) dengan syarat kita mendekati langkah keempat dengan sisa dana (diisi pada kolom saya = 4 tabel 13.2). Di kolom kelima - jumlah dari dua kemenangan: langkah dan dioptimalkan lebih lanjut untuk investasi tertentu X memasuki langkah ketiga.

Dari semua kemenangan pada kolom terakhir, dipilih maksimum (pada Tabel 13.3 sama dengan W 3(7) = 3.6, dan kontrol yang sesuai X(7) = 2).

Timbul pertanyaan: bagaimana jika dalam tabel bantu seperti 13.3 maksimum dicapai lebih dari satu X, dan dengan dua atau lebih? Kami menjawab: sama sekali tidak ada bedanya mana yang harus dipilih; kemenangan tidak bergantung pada ini. Secara umum, dalam permasalahan pemrograman dinamis, solusinya tidak harus unik (kami telah menyebutkan ini).

3. Masalah memuat mesin. Dengan menggunakan metode pemrograman dinamis, Anda berhasil memecahkan sejumlah masalah optimasi yang dijelaskan di Bab 3, khususnya beberapa masalah pemrograman bilangan bulat. Perhatikan bahwa sifat bilangan bulat dari solusi, yang membuat masalah pemrograman linier menjadi begitu sulit, dalam hal ini tidak mempersulit, namun sebaliknya, menyederhanakan prosedur (sama seperti jumlah bilangan bulat dari embeddings pada masalah sebelumnya menyederhanakannya bagi kita).

Sebagai contoh, perhatikan masalah memuat mesin (kami telah menyebutkannya di bab sebelumnya): ada sekumpulan objek tertentu P 1, P 2,..., P n (masing-masing dalam satu salinan); bobotnya diketahui q 1 , q 2 , ..., qn dan biaya dari 1, dengan 2, ..., dengan n. Kapasitas beban mesin adalah Q. Pertanyaannya barang apa saja yang perlu dibawa ke dalam mobil agar total biayanya (dengan berat total Q) apakah sudah maksimal?

Masalah Riset Operasi

Pendahuluan…………………………………………………………………………………...3

1. Konsep dasar dan definisi riset operasi……..……..5

2. Pernyataan umum masalah riset operasi………..…………6

Kesimpulan…………………………………………………………….....13

Sastra…………………………………………………………………………………......14

Perkenalan

Operasi pencarian - suatu disiplin ilmu yang berhubungan dengan pengembangan dan penerapan praktis metode untuk pengelolaan berbagai sistem organisasi yang paling efektif.

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

Saat memecahkan masalah manajemen tertentu, penggunaan metode riset operasi melibatkan:

Konstruksi model ekonomi dan matematika untuk masalah pengambilan keputusan dalam situasi kompleks atau dalam kondisi ketidakpastian;

Mempelajari hubungan yang selanjutnya menentukan pengambilan keputusan dan menetapkan kriteria kinerja yang memungkinkan penilaian keuntungan dari suatu tindakan tertentu.

Contoh tugas riset operasi yang mencerminkan kekhususannya antara lain tugas-tugas berikut.

Tugas 1. Untuk memastikan produk manufaktur berkualitas tinggi, sistem kontrol pengambilan sampel diselenggarakan di pabrik. Penting untuk memilih bentuk organisasi seperti itu - misalnya, menetapkan ukuran lot kontrol, menunjukkan urutan operasi kontrol, menentukan aturan penolakan - untuk memastikan kualitas yang diperlukan dengan biaya minimal.

Tugas 2. Untuk menjual sejumlah barang musiman tertentu, jaringan gerai ritel sementara dibuat. Penting untuk memilih parameter jaringan - jumlah titik, lokasinya, jumlah personel - untuk memastikan efisiensi penjualan yang maksimal.

Tugas 3. Pada tanggal tertentu perlu dilakukan pemeriksaan kesehatan massal terhadap sekelompok penduduk untuk mengidentifikasi penyakit tertentu. Bahan, peralatan, dan personel telah dialokasikan untuk pemeriksaan. Rencana pemeriksaan seperti itu perlu dikembangkan - untuk menetapkan jumlah pos medis, lokasinya, jenis dan jumlah tes, untuk mengidentifikasi persentase pasien yang paling besar.

Penting juga untuk memperhatikan masalah-masalah tentang penggunaan sumber daya, tentang campuran, tentang penggunaan kapasitas, tentang pemotongan bahan, masalah transportasi, dll., yang mana perlu dicari solusi ketika beberapa masalah terjadi. kriteria kinerja(misalnya, keuntungan, pendapatan, biaya sumber daya, dll.) mengambil nilai maksimum atau minimum.

Tugas-tugas yang diberikan berkaitan dengan bidang praktik yang berbeda, tetapi mereka memiliki ciri-ciri yang sama: dalam setiap kasus kita membicarakan beberapa hal peristiwa yang dikendalikan (operasi), mengejar tertentu target. Dalam tugas 1 - ini adalah organisasi pengendalian pengambilan sampel untuk memastikan kualitas produk; dalam tugas 2 - mengatur gerai sementara untuk tujuan mengadakan penjualan musiman; dalam tugas 3 - pemeriksaan kesehatan massal untuk menentukan persentase kasus.

Setiap tugas berisi beberapa kondisi mengadakan acara ini, dalam kerangka yang perlu diambil solusi - sehingga acara tersebut membawa manfaat. Kondisi untuk melaksanakan operasi pada setiap tugas adalah sarana, waktu, peralatan, teknologi yang kita miliki, dan solusi dalam tugas 1 adalah memilih bentuk kendali - ukuran lot kendali, aturan penolakan; dalam tugas 2 - dalam memilih jumlah titik penempatan dan jumlah personel; dalam tugas 3 - dalam memilih jumlah pos medis, jenis dan jumlah tes.

1. Konsep dasar dan definisi riset operasi

Operasi- setiap peristiwa terkendali yang bertujuan untuk mencapai suatu tujuan. Hasil operasi tergantung pada metode pelaksanaannya, organisasi, jika tidak - pada pilihan parameter tertentu.

Pilihan parameter tertentu disebut keputusan.

Optimal pertimbangkan solusi-solusi yang, karena satu dan lain hal, lebih disukai daripada solusi lain. Itu sebabnya tugas utama riset operasi bersifat kuantitatif awal pembenaran solusi optimal.

Catatan 1. Perhatian harus diberikan pada rumusan masalah: the membuat keputusan melampaui lingkup riset operasi dan merupakan tanggung jawab orang atau sekelompok orang yang bertanggung jawab yang mungkin mempertimbangkan pertimbangan selain pertimbangan yang dapat dibenarkan secara matematis.

Catatan 2. Jika dalam beberapa masalah riset operasi solusi optimalnya adalah solusi yang mengambil beberapa kriteria efisiensi

nilai maksimum atau minimum, maka dalam tugas lain hal ini sama sekali tidak diperlukan. Jadi, pada tugas 2, jumlah gerai ritel dan staf yang optimal di dalamnya dapat dianggap sedemikian rupa sehingga rata-rata waktu layanan pelanggan tidak melebihi, misalnya 5 menit, dan panjang antrian rata-rata setiap saat tidak lebih. dari 3 orang.

Untuk menerapkan metode penelitian kuantitatif, perlu dibangun model matematika dari operasi tersebut. Saat membangun suatu model, operasi, sebagai suatu peraturan, disederhanakan, dibuat skema, dan skema operasi dijelaskan menggunakan satu atau beberapa peralatan matematika.

Model operasi - ini adalah gambaran yang cukup akurat tentang operasi menggunakan peralatan matematika (berbagai macam fungsi, persamaan, sistem persamaan dan pertidaksamaan, dll). Menyusun model suatu operasi memerlukan pemahaman tentang esensi fenomena yang dijelaskan dan pengetahuan tentang peralatan matematika.

Efisiensi operasi - tingkat kemampuan beradaptasinya terhadap tugas dinyatakan secara kuantitatif dalam bentuk kriteria efisiensi - fungsi target. Misalnya, dalam masalah penggunaan sumber daya, kriteria efisiensi adalah keuntungan dari penjualan produk manufaktur yang perlu dimaksimalkan; dalam masalah transportasi, total biaya pengangkutan barang dari pemasok ke konsumen yang perlu diminimalkan . Pilihan kriteria efektivitas menentukan nilai praktis penelitian. (Kriteria yang dipilih secara salah dapat merugikan, karena operasi yang diselenggarakan berdasarkan kriteria efisiensi terkadang menimbulkan biaya yang tidak dapat dibenarkan.)

2. Pernyataan umum masalah riset operasi

Penting untuk memahami metodologi untuk membangun model masalah riset operasi. Semua faktor yang termasuk dalam deskripsi operasi dapat dibagi menjadi dua kelompok:

faktor konstan(kondisi operasi), yang tidak dapat kami pengaruhi. Mari kita nyatakan dengan α1, α2, ... ;

faktor ketergantungan(elemen solusi) X 1, x2, ...; yang, dalam batas tertentu, dapat kita pilih sesuai kebijaksanaan kita.

Misalnya, dalam masalah penggunaan sumber daya, faktor konstan harus mencakup cadangan sumber daya dari setiap jenis, matriks produksi, yang elemen-elemennya menentukan konsumsi bahan baku setiap jenis per unit output setiap jenis. Elemen solusi - rencana produksi untuk setiap jenis produk.

Kriteria kinerja yang dinyatakan oleh beberapa fungsi disebut target, tergantung pada faktor dari kedua kelompok, sehingga fungsi tujuan Z dapat ditulis dalam bentuk

Z= F (x1, x2, ..., α1, α2, ...)

Semua model riset operasi dapat diklasifikasikan menurut sifat dan sifat operasi, sifat masalah yang dipecahkan, dan ciri-ciri metode matematika yang digunakan.

Perlu diperhatikan, pertama-tama, yang besar kelas model optimasi. Masalah seperti ini muncul ketika mencoba mengoptimalkan perencanaan dan pengelolaan sistem yang kompleks, terutama sistem ekonomi. Masalah optimasi dapat dirumuskan dalam bentuk umum: temukan variabel x1, x2, ..., x N , memenuhi sistem pertidaksamaan (persamaan)

G Saya (x1, x2, x3,..., X N )<= B Saya , saya = 1, 2,..., N (0.1)

Dan mengubah fungsi tujuan menjadi maksimum (atau minimum), mis.

Z= F (x1, x2, ..., X N ) - M ah (m di dalam ) (0.2)

(Kondisi variabel non-negatif, jika ada, termasuk dalam batasan (0,1))

Mari kita pertimbangkan masalah lain yang khas untuk riset operasi - masalah konsumsi klasik, sangat penting dalam analisis ekonomi.

Biarkan disana ada P jenis barang dan jasa, yang jumlahnya (dalam satuan alami) x1, x2, ..., X N, dengan harga yang sesuai P 1, P 2, ..., P N untuk satu unit. Total biaya barang dan jasa ini adalah ∑ P Saya X Saya .

Tingkat konsumsi Z dapat dinyatakan dengan beberapa fungsi Z= F (x1, x2, ..., X N ) ,ditelepon fungsi utilitas. Penting untuk menemukan sekumpulan barang dan jasa seperti itu x1, x2, ..., X N diberikan jumlah pendapatan saya, ke memastikan tingkat konsumsi maksimum, itu.

Z= F (x1, x2, ..., X N ) - M Oh (0.3)

mengingat bahwa

∑ P Saya X Saya <= SAYA (0.4)

X Saya >= 0 ( Saya = 1, 2,..., N ) (0.5)

Solusi untuk masalah ini bergantung pada harga P 1, P 2, ..., P N dan jumlah pendapatan SAYA, disebut fungsi permintaan.

Jelaslah bahwa permasalahan konsumsi (0,3)-(0,5), dan juga permasalahan lainnya, merupakan kasus khusus dari permasalahan umum (0,1)-(0,2) yang dirumuskan di atas untuk menentukan titik ekstrem suatu fungsi. P variabel dalam batasan tertentu, yaitu tugas untuk bersyarat ekstrim.

Dalam kasus di mana fungsinya F Dan G Saya, dalam soal (0.1)-(0.2) setidaknya dapat terdiferensiasi dua kali, kita dapat menggunakan klasik metode optimasi. Namun, penggunaan metode ini dalam riset operasi sangat terbatas, karena tugas menentukan ekstrem bersyarat dari suatu fungsi variabel i secara teknis sangat sulit: metode ini memungkinkan untuk menentukan ekstrem lokal, dan karena multidimensi dari fungsinya, menentukan nilai maksimum (atau minimum) (ekstrim global) mungkin menjadi sangat memakan waktu - terutama karena nilai ekstrem ini mungkin terjadi pada batas wilayah solusi. Metode klasik tidak berfungsi sama sekali jika kumpulan nilai argumen yang valid adalah diskrit atau fungsinya Z diberikan dalam sebuah tabel. Dalam kasus ini, untuk menyelesaikan masalah (0,1)-(0,2) metode digunakan pemrograman matematika.

Jika kriteria kinerja Z= F (x1, x2, ..., X N ) (0.2) mewakili fungsi linier, dan fungsinya G Saya (x1, x2, x3,..., X N ) dalam sistem kendala (0,1) juga linier, maka masalah tersebut merupakan masalah pemrograman linier. Jika berdasarkan isinya, solusinya harus bilangan bulat, maka masalah ini pemrograman linier bilangan bulat. Jika kriteria efisiensi dan (atau) sistem pembatasan ditentukan oleh fungsi nonlinier, maka kita mempunyai masalah pemrograman nonlinier. Khususnya, jika fungsi yang ditunjukkan memiliki sifat konveksitas, maka permasalahan yang dihasilkan adalah masalah pemrograman cembung.

Jika dalam suatu permasalahan pemrograman matematika terdapat variabel waktu dan kriteria efisiensi (0,2) dinyatakan tidak secara eksplisit sebagai fungsi variabel, tetapi secara tidak langsung melalui persamaan yang menggambarkan aliran operasi dalam waktu, maka permasalahan tersebut adalah permasalahan. pemrograman dinamis.

Jika kriteria efisiensi (0,2) dan sistem pembatasan (0,1) ditentukan oleh fungsi formulir Dengan*( X 1^α 1 )*( X 2^α 2 )...( X N ^α N ) , maka kita punya masalah pemrograman geometris. Jika fungsinya F dan/atau G Saya dalam ekspresi (0.2) dan (0.1) bergantung pada parameternya, maka kita memperoleh masalahnya pemrograman parametrik, jika fungsi-fungsi ini bersifat acak, maka tugasnya pemrograman stokastik. Jika tidak mungkin menemukan solusi optimal yang tepat secara algoritmik karena terlalu banyak pilihan solusi, maka gunakan metode heuristis pemrograman, memungkinkan Anda mengurangi secara signifikan jumlah opsi yang Anda cari dan menemukan, jika tidak optimal, maka solusi yang cukup baik dan memuaskan dari sudut pandang praktis.

Dari metode pemrograman matematika yang terdaftar, yang paling umum dan dikembangkan adalah pemrograman linier. Ini mencakup berbagai tugas riset operasi.

Tugas perencanaan dan manajemen jaringan pertimbangkan hubungan antara tanggal penyelesaian suatu kompleks operasi (pekerjaan) yang besar dan waktu mulai semua operasi kompleks tersebut. Tugas-tugas ini terdiri dari menemukan durasi minimum dari serangkaian operasi, rasio optimal nilai biaya dan waktu pelaksanaannya.

Masalah antrian dikhususkan untuk studi dan analisis sistem layanan dengan antrian aplikasi atau persyaratan dan terdiri dari penentuan indikator kinerja sistem, karakteristik optimalnya, misalnya, penentuan jumlah saluran layanan, waktu layanan, dll.

Tugas manajemen inventaris terdiri dari mencari nilai optimal tingkat persediaan (titik pemesanan) dan ukuran pesanan. Keunikan dari tugas-tugas tersebut adalah dengan peningkatan tingkat persediaan, di satu sisi, biaya penyimpanannya meningkat, namun di sisi lain, kerugian akibat kemungkinan kekurangan produk yang disimpan berkurang.

Masalah Alokasi Sumber Daya timbul selama serangkaian operasi (pekerjaan) tertentu yang harus dilakukan dengan sumber daya yang tersedia terbatas, dan perlu dicari distribusi sumber daya yang optimal antar operasi atau komposisi operasi.

Tugas perbaikan dan penggantian peralatan relevan karena keausan peralatan dan kebutuhan untuk menggantinya seiring waktu. Tugasnya adalah menentukan waktu optimal, jumlah perbaikan dan inspeksi preventif, serta kapan harus mengganti peralatan dengan peralatan modern.

Menjadwalkan (scheduling) tugas terdiri dari penentuan urutan operasi yang optimal (misalnya, pemrosesan suku cadang) pada berbagai jenis peralatan.

Tugas perencanaan dan penempatan terdiri dari penentuan jumlah dan lokasi optimal objek baru, dengan mempertimbangkan interaksinya dengan objek yang sudah ada dan satu sama lain.

Masalah pemilihan rute atau jaringan Permasalahan yang paling sering ditemui dalam kajian berbagai permasalahan dalam sistem transportasi dan komunikasi dan terdiri dari penentuan rute yang paling ekonomis.

Di antara model-model riset operasi, model pengambilan keputusan optimal dalam situasi konflik, dipelajari oleh teori permainan. Situasi konflik di mana kepentingan dua (atau lebih) pihak bertabrakan, mengejar tujuan yang berbeda, mencakup sejumlah situasi di bidang ekonomi, hukum, militer, dll. Dalam permasalahan teori permainan, perlu dikembangkan rekomendasi untuk perilaku wajar para pihak yang berkonflik, untuk menentukan strategi optimal mereka.

Dalam praktiknya, dalam banyak kasus, keberhasilan suatu operasi dinilai bukan berdasarkan satu kriteria, tetapi berdasarkan beberapa kriteria sekaligus, yang satu harus dimaksimalkan, yang lain harus diminimalkan. Peralatan matematika juga dapat berguna dalam kasus-kasus masalah riset operasi multi-kriteria, setidaknya membantu membuang solusi yang jelas-jelas tidak berhasil.

Untuk memilih fungsi tujuan dari berbagai kriteria, termasuk kriteria yang bertentangan satu sama lain (misalnya laba dan beban), perlu ditetapkan Sebuah prioritas kriteria. Mari kita tunjukkan F 1 (x), f 2 (X), ..., F N (X)(Di Sini X - argumen bersyarat). Biarkan mereka diatur dalam urutan prioritas. Tergantung pada kondisi tertentu, pada dasarnya ada dua pilihan:

Kriteria dipilih sebagai fungsi tujuan F 1 (X), mempunyai prioritas tertinggi;

Kombinasi sedang dipertimbangkan

F ( X ) = ω 1 * F 1 ( X ) + ω 2 * F 2 ( X ) + …+ ω N * F N ( X ) , (0.6)

Di mana ω 1 , ω 2 , … ω N- beberapa koefisien (bobot).

Besarnya F (X), yang mempertimbangkan semua kriteria sampai batas tertentu, dipilih sebagai fungsi tujuan.

Dalam kondisi kepastian ω Saya- angka, F Saya (X)- fungsi. Dalam kondisi ketidakpastian F Saya (X) mungkin berubah menjadi acak dan sebaliknya F Saya (X) ekspektasi matematis dari jumlah (0,6) harus dianggap sebagai fungsi tujuan.

Upaya mereduksi permasalahan multi kriteria menjadi permasalahan dengan satu kriteria efisiensi (fungsi tujuan) dalam banyak kasus tidak memberikan hasil yang memuaskan. Pendekatan lain terdiri dari membuang ("pemusnahan") dari serangkaian solusi yang dapat diterima yang jelas-jelas tidak berhasil, yang lebih rendah daripada solusi lain dalam hal kualitas. semua kriteria. Sebagai hasil dari prosedur ini, apa yang disebut efektif(atau " Pareto") solusi, yang himpunannya biasanya jauh lebih kecil daripada solusi aslinya. Dan pilihan akhir dari solusi “kompromi” (tidak optimal menurut semua kriteria, yang biasanya tidak ada, tetapi dapat diterima menurut kriteria ini) tetap berada pada orang – pengambil keputusan.

Kesimpulan

Ilmuwan Rusia L.V. memberikan kontribusi besar terhadap penciptaan peralatan matematika modern dan pengembangan banyak bidang riset operasi. Kantorovich, N.P. Buslenko, E.S. Ventzel, N.N. Vorobyov, N.N. Moiseev, D.B. Yudin dan masih banyak lainnya. Yang paling patut diperhatikan adalah peran Akademisi L.V. Kantorovich, yang pada tahun 1939, setelah mulai merencanakan pengoperasian unit pabrik kayu lapis, memecahkan beberapa masalah: tentang pemuatan peralatan terbaik, tentang pemotongan bahan dengan kerugian minimal, tentang distribusi kargo di antara beberapa jenis transportasi, dll. L.V. Kantorovich merumuskan kelas baru masalah ekstrem bersyarat dan mengusulkan metode universal untuk menyelesaikannya, meletakkan dasar bagi arah baru dalam matematika terapan - pemrograman linier.

Kontribusi signifikan terhadap 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 riset operasi, seperti metode matematika lainnya, selalu menyederhanakan dan mempermasalahkan masalah sampai tingkat tertentu, terkadang mencerminkan proses nonlinier dengan model linier, sistem stokastik dengan model deterministik, proses dinamis dengan model statis, dll. Hidup lebih kaya dari skema apa pun. Oleh karena itu, seseorang tidak boleh membesar-besarkan pentingnya metode kuantitatif dalam riset operasi atau meminimalkannya dengan mengutip contoh-contoh solusi yang gagal. Dalam hal ini, pantas untuk mengutip definisi riset operasi yang sangat paradoks dan lucu, yang dibuat oleh salah satu penciptanya, T. Saaty, sebagai “seni memberikan jawaban buruk terhadap pertanyaan-pertanyaan praktis yang bahkan dapat dijawab lebih buruk lagi dengan metode lain.”

literatur

1. Kremer N.Sh., Putko B.A., Trishin I.M., Fridman M.N. Penelitian operasi di bidang ekonomi: Buku teks untuk universitas - M.: UNITI, 2002.

2. Ventzel E.S. Operasi pencarian. Tujuan, Prinsip, Metodologi - M.: Nauka, 1980.

3. Gorelik V.A., Ushakov I.A. Operasi pencarian. - M.: Teknik Mesin, 1986.

Operasi Setiap peristiwa (sistem tindakan) yang disatukan oleh satu rencana dan bertujuan untuk mencapai tujuan tertentu disebut. Selalu ada operasi dikendalikan acara, yaitu Dimungkinkan untuk memutuskan bagaimana memilih parameter tertentu yang menjadi ciri organisasinya. Parameter ini disebut variabel kontrol.

Pilihan spesifik apa pun dari variabel tersebut disebut keputusan. Keputusan bisa berhasil dan tidak berhasil, masuk akal dan tidak masuk akal. Optimal sebutkan solusi yang, menurut beberapa kriteria, lebih disukai daripada kriteria lainnya.

Tujuan dari riset operasi adalah pembenaran kuantitatif awal atas solusi optimal, yang mungkin ada lebih dari satu. Pilihan akhir atas keputusan melampaui lingkup riset operasi dan dibuat melalui apa yang disebut teori keputusan.

Setiap tugas riset operasi memiliki kondisi “pendisiplinan” awal, yaitu. data awal yang sudah ditetapkan sejak awal dan tidak dapat dilanggar. Secara bersama-sama, mereka membentuk apa yang disebut himpunan solusi yang mungkin.

Untuk membandingkan solusi yang berbeda dalam hal efektivitas, Anda perlu memiliki kriteria kuantitatif yang disebut indikator kinerja(atau fungsi tujuan). Indikator ini dipilih untuk mencerminkan orientasi sasaran operasi.

Seringkali operasi disertai dengan tindakan faktor acak. Kemudian, sebagai indikator efisiensi, yang diambil bukanlah nilai itu sendiri yang ingin dioptimalkan, melainkan nilai rata-ratanya (atau ekspektasi matematisnya).

Terkadang suatu operasi yang disertai dengan faktor acak memiliki tujuan seperti itu A, yang dapat dicapai sepenuhnya atau tidak tercapai sama sekali (seperti “ya-tidak”). Kemudian probabilitas tercapainya tujuan tersebut dipilih sebagai indikator efisiensi P(A). (Jika P(A) = 0 atau 1, maka kita sampai pada masalah “kotak hitam” yang dikenal dalam sibernetika.)

Memilih indikator kinerja yang salah sangatlah berbahaya. Operasi yang diselenggarakan berdasarkan kriteria yang dipilih secara tidak berhasil dapat mengakibatkan biaya dan kerugian yang tidak dapat dibenarkan. (Misalnya, “poros” sebagai kriteria utama untuk menilai aktivitas ekonomi suatu perusahaan.)

1.3. Pernyataan umum masalah riset operasi

Masalah riset operasi terbagi dalam dua kategori: a) maju dan b) mundur.

Tugas langsung jawab pertanyaannya: indikator efisiensinya akan sama dengan apa? Z, jika dalam kondisi tertentu kamu  Y beberapa keputusan akan dibuat X  X. Untuk mengatasi masalah tersebut, dibangun model matematika yang memungkinkan seseorang untuk menyatakan indikator efisiensi melalui kondisi tertentu dan solusinya, yaitu:

Di mana
faktor tertentu (data awal),

variabel kontrol (keputusan),

Z– indikator efisiensi (fungsi target),

F– ketergantungan fungsional antar variabel.

Ketergantungan ini dinyatakan secara berbeda dalam model yang berbeda. Ketergantungan antara Dan biasanya dinyatakan dalam batasan

Jika jenis ketergantungan F diketahui, maka indikatornya Z ditemukan dengan substitusi langsung Dan ke dalam fungsi ini.

Masalah terbalik jawab pertanyaannya: bagaimana dalam kondisi seperti ini memilih solusi
sehingga menjadi indikator kinerja Z berubah menjadi maksimum (minimum). Masalah ini disebut masalah optimasi solusi.

Biarkan masalah langsung diselesaikan, mis. model operasi ditentukan dan jenis ketergantungan ditentukan F terkenal. Maka masalah inversnya (yaitu masalah optimasi) dapat dirumuskan sebagai berikut.

Perlu menemukan keputusan seperti itu
di mana indikator efisiensi Z = memilih:

Rumusnya berbunyi seperti ini: Z ada nilai optimalnya
mengambil alih semua solusi yang termasuk dalam himpunan solusi yang mungkin X.

Metode untuk mencari indikator efisiensi ekstrem Z dan solusi optimal terkait harus selalu dipilih berdasarkan fitur fungsinya F dan jenis pembatasan yang dikenakan pada solusi tersebut. (Misalnya, masalah pemrograman linier klasik.)

Operasi pencarian– ilmu yang berhubungan dengan pengembangan dan penerapan praktis metode matematis dan kuantitatif untuk mendukung keputusan di semua bidang aktivitas manusia yang memiliki tujuan (manajemen organisasi yang efektif).

Ciri-ciri Umum Riset Operasi

Setiap tugas adalah tentang suatu peristiwa yang mengejar tujuan tertentu.

Beberapa kondisi ditentukan yang menjadi ciri situasi tersebut (termasuk dana yang dapat kami keluarkan).

Dalam kondisi seperti ini, perlu diambil keputusan agar acara yang direncanakan menjadi yang paling menguntungkan.

Fitur riset operasi

Pendekatan sistematis terhadap analisis masalah yang diajukan berarti bahwa masalah tertentu harus dipertimbangkan dari sudut pandang pengaruhnya terhadap kriteria berfungsinya keseluruhan sistem.

Efek terbesar hanya dapat dicapai dengan penelitian berkelanjutan, yang memastikan kesinambungan transisi dari satu masalah ke masalah lainnya, yang timbul selama penyelesaian masalah sebelumnya.

Meskipun tujuan dari riset operasi adalah untuk menemukan solusi optimal, karena kompleksitas komputasi masalah kombinatorial, penelitian ini terbatas pada menemukan solusi yang “cukup baik”.

Riset operasional dilakukan secara komprehensif di banyak bidang. Untuk melakukan penelitian, dibentuk kelompok operasional:

Konsep Dasar Riset Operasi

OPERASI adalah peristiwa apa pun yang terkendali (yaitu, bergantung pada pilihan parameter), disatukan oleh satu rencana dan ditujukan untuk mencapai suatu tujuan.

KEPUTUSAN – pilihan parameter tertentu yang bergantung pada kita.

SOLUSI OPTIMAL – keputusan berdasarkan karakteristik tertentu yang lebih disukai daripada karakteristik lainnya.

TUJUAN PENELITIAN OPERASIONAL adalah pembenaran kuantitatif awal atas solusi optimal.

ELEMEN SOLUSI – parameter, kombinasi yang membentuk solusi.

INDIKATOR EFISIENSI (FUNGSI TARGET) adalah kriteria kuantitatif yang memungkinkan Anda membandingkan solusi yang berbeda dalam hal efektivitas dan mencerminkan orientasi target operasi (W=>maks atau W=>min).

Solusi terbaik adalah solusi yang berkontribusi terhadap pencapaian tujuan secara maksimal.

Konsep model matematika suatu operasi

Deskripsi operasi yang skematis dan disederhanakan menggunakan peralatan matematika tertentu, yang mencerminkan fitur paling penting dari operasi, semua faktor penting yang menjadi sandaran utama keberhasilan operasi.

Masalah penelitian operasi langsung dan terbalik

MASALAH LANGSUNG menjawab pertanyaan tentang apa yang akan terjadi jika, dalam kondisi tertentu, kita membuat suatu keputusan x X, yaitu. berapakah indikator efisiensi W (atau sejumlah indikator) yang akan sama?

Untuk mengatasi permasalahan tersebut maka dibuatlah matras. suatu model yang memungkinkan satu atau lebih indikator kinerja dinyatakan melalui kondisi dan elemen solusi tertentu.

MASALAH INVERSE menjawab pertanyaan bagaimana memilih solusi x sehingga indikator efisiensi W menjadi maksimum (minimum).

Tugas-tugas ini lebih sulit. Masalah-masalah tersebut dapat diselesaikan hanya dengan mencari solusi terhadap permasalahan yang ada.

Namun ketika jumlah pilihan solusi banyak, metode pencarian terarah digunakan, di mana solusi optimal ditemukan dengan melakukan “percobaan” atau perkiraan yang berurutan, yang masing-masing membawa kita lebih dekat ke solusi optimal yang diinginkan.