Apa itu pemrograman linier integer?

Masalah pemrograman linier integer muncul ketika mencoba memecahkan sistem linier sambil menentukan bahwa semua variabel yang tidak diketahui harus bilangan bulat, atau bilangan bulat.Sistem linier adalah set persamaan yang menggambarkan situasi yang programmer berusaha menemukan solusi.Mereka biasanya terdiri dari satu persamaan yang harus dimaksimalkan atau diminimalkan dan satu atau lebih persamaan yang membatasi yang membatasi variabel yang tidak diketahui.Agar sistem menjadi linier, setiap pembatasan harus menjadi persamaan linier;Artinya, ia harus tidak mengandung contoh variabel yang tidak diketahui dengan eksponen yang lebih besar dari satu.

Sistem linier reguler dapat diselesaikan dengan mudah menggunakan komputer.Program ini dapat mengidentifikasi solusi dengan menemukan turunan dan menetapkannya sama dengan nol.Kemudian dapat memverifikasi bahwa titik tersebut adalah maksimum atau minimum dengan memeriksa lingkungan terdekatnya pada fungsi tersebut.Selama turunan didefinisikan pada setiap titik di sepanjang fungsi, komputer hanya memiliki sejumlah solusi yang mungkin untuk memeriksa.

Pemrograman linier menjadi pemrograman linier integer dengan penambahan pembatasan integer.Ini berarti bahwa masalahnya tetap sama, tetapi jawabannya harus terdiri dari nilai -nilai integer untuk nilai -nilai yang tidak diketahui: mereka harus bilangan bulat.Terkadang, ini berarti bahwa solusinya akan suboptimal dibandingkan dengan kasus di mana fraksi diizinkan;Ini reflektif, bagaimanapun, dari dunia nyata, di mana barang -barang sering datang dalam unit yang tidak terpisahkan.Ini membuat pemrograman linier integer penting untuk aplikasi bisnis, karena perusahaan ingin memaksimalkan laba sebanyak mungkin tetapi tidak dapat memilih untuk menjual sebagian kecil dari suatu produk.

Setelah pembatasan integer ada, masalah penyelesaian sistem linier adalah NP-menyelesaikan.Ini berarti bahwa waktu yang diperlukan bagi komputer untuk menyelesaikan sistem tidak pasti.Dengan pembatasan integer, komputer tidak dapat menggunakan alat turunan karena tidak ada jaminan bahwa titik nol dari turunan akan jatuh pada bilangan bulat.Solusinya akan menjadi bilangan bulat dengan nilai tertinggi atau terendah dari semua bilangan bulat, sehingga komputer harus memeriksa semuanya mdash;sebuah proses yang dapat membutuhkan waktu yang tak terbatas.

Programmer telah mengembangkan heuristik, atau metode pemecahan masalah, untuk menangani kompleksitas masalah ini.Salah satu metode pemecahan masalah pemrograman linier integer adalah algoritma cabang dan terikat, di mana komputer memecahkan serangkaian masalah yang terkait dengan yang asli untuk mempersempit rentang nilai yang tersedia menjadi satu solusi.Namun, untuk masalah yang kompleks, ini bisa memakan waktu lama.