Do strony głównej
Programowanie całkowite
Na końcu strony
13. ZINTEGROWANE PROGRAMOWANIE
Programowanie całkowite jest jedną z najmłodszych, najbardziej obiecujących i szybko rozwijających się gałęzi programowania matematycznego. Możesz wyliczyć wiele różnych zadań związanych z planowaniem gospodarki, organizowaniem produkcji, studiowaniem sytuacji konfliktowych, syntezowaniem automatycznych systemów kontroli, które formalnie sprowadzają się do wyboru najlepszych, w pewnym sensie, wartości parametrów z pewnego dyskretnego zestawu określonych wartości. Można im przypisać ekstremalne problemy kombinatoryczne pojawiające się w różnych sekcjach matematyki dyskretnej.
Zadania i metody związane z wymienionym zakresem zagadnień w literaturze nazywane są inaczej. Termin „programowanie całkowite” uzyskał najbardziej rozpowszechnione zastosowanie, ale są też takie jak „programowanie dyskretne”, rzadziej „programowanie kombinatoryczne (lub diofantyczne)”.
Najbardziej badanymi problemami tej klasy są całkowite problemy z programowaniem liniowym, w których wszystkie zmienne (lub ich części) podlegają dodatkowemu wymaganiu co do całkowitej jasności. Zwyczajowo odróżnia się od nich tak zwane dyskretne problemy programowania liniowego, w których obszar dopuszczalnej zmienności każdej zmiennej nie jest zbiorem nieujemnych liczb całkowitych, lecz pewnym skończonym zbiorem.
Integralne problemy programowania matematycznego mogą powstać na różne sposoby.
1. Istnieją problemy programowania liniowego, które nie są formalnie związane z liczbami całkowitymi, ale z odpowiednimi danymi źródłowymi zawsze mają plan całkowity. Przykładami takich zadań są problemy z transportem i jego modyfikacje (problemy z przydzielaniem, przepływy w sieciach).
2. Impulsem do badania problemów liczb całkowitych we właściwym znaczeniu tego słowa było rozważenie problemów programowania liniowego, w których zmienne reprezentowały fizycznie niepodzielne wielkości. Nazywano je zadaniami z niepodzielnością. Takimi są na przykład zadania optymalizacji kompleksu środków dostawy ładunku, znalezienia minimalnego pustego przebiegu samochodów przy realizacji danego planu transportu, określenia optymalnej floty maszyn i jej optymalnego rozkładu wśród określonych prac, pod warunkiem zminimalizowania całkowitego kosztu (park maszynowy i wykonywana praca), znalezienie minimalnej liczby statków do wdrożenia tego harmonogramu przesyłek itp.
3. Innym ważnym impulsem do konstrukcji teorii programowania całkowitoliczbowego było nowe podejście do niektórych ekstremalnych problemów kombinatorycznych. Muszą znaleźć ekstremum integralnej funkcji liniowej zdefiniowanej na skończonym zestawie elementów. Takie zadania nazywane są problemami ze zmiennymi alternatywnymi. Przykłady obejmują zadania komiwojażera (wędrownego kupca), optymalne przypisanie, teorię planowania lub planowanie i zadania z dodatkowymi warunkami logicznymi (na przykład takie jak „lub - lub”, „jeśli - to” itp.) .
Historycznie, pierwszym zadaniem typu integralnego jest przydzielanie personelu, który został opublikowany w 1932 roku przez węgierskiego matematyka E. Egervari. W 1955 r. Na drugim sympozjum programowania liniowego rozważono problem bombowca, znany jako problem plecakowy.
Podajemy przykłady całkowitych problemów programowania liniowego.
Przykład. Problem plecakowy. Istnieje m-wektor ograniczonych zasobów. 
które mogą być używane do przewozu towarów o różnych właściwościach. Każde j-te obciążenie 
ma następujące właściwości: 1) niepodzielność; 2) przydatność 
; 3) zużycie i-tego zasobu do transportu jednostki j-tego ładunku 
. Wybierz liczbę ładunków do transportu, która maksymalizuje ogólną użyteczność lotu (całkowity koszt towarów przewożonych podczas podróży).
Tworzymy matematyczny model problemu. Oznacz jako 
liczba przedmiotów wybranych do transportu. Wymóg niepodzielności spełnia warunek
liczby całkowite 
(13.1)
Porównanie kosztów zasobów każdego rodzaju do transportu jednostki ładunku i ich dostępność prowadzi do ograniczenia
(13.2)
Ogólna użyteczność podróży jest określona przez wartość funkcji.
. (13.3)
Szczególnym przypadkiem problemu (13.1) - (13.2) jest problem plecakowy, w którym dowolny z danego zestawu obiektów 
można wybrać, czy nie. Następnie model matematyczny przyjmie następującą postać:
Maksymalizuj
w warunkach
Przykład. W okolicy
znajdź maksymalną funkcję 
.
Problem rozwiązujemy geometrycznie (rys. 13.1). Obszar wyszukiwania ekstremum to wielokąt OABCD. Ponieważ linia poziomu funkcji celu jest równoległa do boku BC wielokąta, ekstremum jest osiągane przy wierzchołkach 
i 
, jak również w dowolnym punkcie segmentu BC i jest równy 7. Interesują nas tylko punkty ze współrzędnymi całkowitymi, dlatego ani B, ani C nie jest prawidłowym rozwiązaniem problemu. Zaokrąglając wartość współrzędnych punktów B i C, otrzymujemy punkt (4; 3), który nie należy do obszaru wyszukiwania. Łatwo jest pokazać, że optymalna liczba całkowita jest osiągnięta w punktach M (2; 3) i N (3; 2) i jest równa 5. Oba punkty znajdują się w obszarze wyszukiwania.
Rysunek 13.1
Niepowodzenie zaokrąglenia jest również podkreślone przez następujące rozważania. Chociaż zmienne całkowite zwykle wyrażają liczbę niepodzielnych elementów, możliwe są inne typy specyfikacji tych zmiennych. W przypadku problemu plecakowego rozwiązanie jest reprezentowane przez zmienną boolowską. 
(x = 0 lub x = 1). W tym przypadku nie ma sensu operowanie wartościami ułamkowymi x, a procedura zaokrąglania jest logicznie niedopuszczalna.
Z powyższego przykładu jasno wynika, że w celu rozwiązania problemów związanych z programowaniem całkowitym konieczne jest uwzględnienie specjalnych metod optymalizacji. Ponadto optymalne rozwiązanie problemów z programowaniem całkowitym niekoniecznie musi należeć do granicy wielościanu (wielokąta) warunków, co jest typowe dla problemów programowania liniowego.
Z powrotem Do początku strony Naprzód
