Co to jest programowanie liniowe liczb całkowitych?
Problemy z programowaniem liniowym liczb całkowitych powstają podczas próby rozwiązania układów liniowych przy jednoczesnym określeniu, że wszystkie nieznane zmienne muszą być liczbami całkowitymi lub liczbami całkowitymi. Układy liniowe to zbiory równań opisujące sytuację, w której programista próbuje znaleźć rozwiązanie. Zwykle składają się z jednego równania, które należy zmaksymalizować lub zminimalizować, oraz jednego lub więcej równania ograniczającego, które nakłada ograniczenia na nieznane zmienne. Aby układ był liniowy, każde ograniczenie musi być równaniem liniowym; oznacza to, że nie może zawierać instancji nieznanej zmiennej z wykładnikami większymi niż jeden.
Zwykłe systemy liniowe można łatwo rozwiązać za pomocą komputera. Program może zidentyfikować rozwiązanie, znajdując pochodną i ustawiając ją na zero. Następnie może sprawdzić, czy punkt jest maksimum lub minimum, sprawdzając jego bezpośrednie sąsiedztwo na funkcji. Dopóki pochodna jest zdefiniowana w każdym punkcie funkcji, komputer ma ograniczoną liczbę możliwych rozwiązań do sprawdzenia.
Programowanie liniowe staje się całkowitym programowaniem liniowym z dodaniem ograniczenia liczby całkowitej. Oznacza to, że problem pozostaje ten sam, ale odpowiedź musi składać się z liczb całkowitych dla nieznanych wartości: muszą to być liczby całkowite. Czasami oznacza to, że rozwiązanie będzie nieoptymalne w porównaniu z przypadkiem, w którym frakcje są dozwolone; odzwierciedla jednak rzeczywisty świat, w którym przedmioty często występują w odrębnych, niepodzielnych jednostkach. To sprawia, że programowanie liniowe liczb całkowitych jest ważne dla aplikacji biznesowych, ponieważ firmy chcą maksymalizować zyski w jak największym stopniu, ale nie mogą zdecydować się na sprzedaż części produktu.
Po wprowadzeniu ograniczeń liczb całkowitych problem rozwiązania układu liniowego jest NP-zupełny. Oznacza to, że czas niezbędny do rozwiązania systemu przez komputer jest nieokreślony. Przy ograniczeniach całkowitych komputery nie mogą korzystać z narzędzia pochodnej, ponieważ nie ma gwarancji, że punkt zerowy pochodnej spadnie na liczbę całkowitą. Rozwiązaniem będzie liczba całkowita o najwyższej lub najniższej wartości spośród wszystkich liczb całkowitych, więc komputer będzie musiał sprawdzić je wszystkie - proces, który może zająć nieskończoną ilość czasu.
Programiści opracowali heurystykę lub metody rozwiązywania problemów, aby poradzić sobie ze złożonością tych problemów. Jedną z metod rozwiązywania całkowitych problemów programowania liniowego jest algorytm rozgałęziony i związany, w którym komputer rozwiązuje szereg problemów związanych z pierwotnym, aby zawęzić dostępny zakres wartości do jednego rozwiązania. W przypadku złożonych problemów może to jednak zająć dużo czasu.