THE PROBLEM OF INTEGER PROGRAMMING AND APPLICATION IN THE ECONOMY

U modelu LP su uključene sljedeće pretpostavke: veze između promjenljivih su linearne, parametri su konstantni, ne javljaju su slučajne varijable, postoji samo jedna funkcija kriterija i upravljačke promjenljive su neprekidne ne negativne veličine. Iako ove pretpostavke, u konkretnim problemima, nisu uvijek u potpunosti ispunjene, LP daje rezultate koji se uspješno primjenjuju u praksi. Međutim, u nekim primjenama linearnog programiranja, pojedine ili svestrukturne promjenljive mogu imati samo cjelobrojne vrijednosti. Na primjer, broj mašina, izvršilaca, vozila, proizvodnih pogona, itd .Ako se radi o relativno velikim brojevima, pogreške zaokruživanja su relativno male tako da je u tim slučajevima prihvatljivo riješiti problem LP sa realnim promjenljivim i dobivene vrijednosti zaokružiti na najbliže cjelobrojne vrijednosti. S druge strane, postoje slučajevi gdje bi se zaokruživanjem pravile grube greške. To se dešava kada su vrijednosti cjelobrojnih rezultata relativno male ili u ekstremnom slučaju, kada promjenljive mogu dobiti samo vrijednosti 0 ili 1. Takvi slučajevi su tipični za situacije donošenja odluka o tome da li nešto uraditi ili ne – da li izgraditi tvornicu, da li zasijati određenu kulturu, da li izvršiti investiranje u određeni projekt. Iako formulacije cjelobrojnih problema programiranja često izgledaju vrlo slično nekim kontinualnim problemima programiranja, sličnost je na neki način zabluda. Algebarski izrazi funkcije cilja i ograničenja u ova dva tipa problema, imaju sličan oblik ,ali dodatna ograničenja, da neke ili sve promjenljive moraju biti cjelobrojne, čine cjelobrojne probleme znatno težim. Mnogi problemi cjelobrojnog programiranja su klasificirani kao teški( hard ) optimizacijski problemi. Tako, dok opći problem LP može biti riješen u polinominalnom vremenu, nalaženje optimalnog rješenja za odgovarajući cjelobrojni zadatak obično zahtijeva eksponencijalno računalno vrijeme. Međutim, postoje neki cjelobrojni problemi koji se mogu lako riješiti. Posebno, mnogi problemi linearnih mreža, kao problemi raspoređivanja i uparivanja ( III matching problems), transportni i problemi pretovara (transshipment problems), problemi mrežnog toka, uvijek kao optimalno rješenje dobiju cjelobrojni rezultat.The LP assumes the following assumptions: the links between the variables are linear, parameters are constant, no random variables occur, there is only one criterion function, educational variables are continuous unrelated sizes. Although these assumptions, in specific problems, are not always fully met, the LP yields results that are successfully applied in practice. However, in some linear programming applications, individual or structurally variable can only have integer values. For example, the number of machines, executors, vehicles, production plants, etc. With relatively large numbers, rounding errors are relatively small so that in such cases it is acceptable to solve the LP problem with the real variable and gained value rounded to the nearest integer values. On the other hand, there are cases where rounding would make rough mistakes. That's it Occurs when the values of the whole result are relatively small or far-reaching, when the values can only be gained 0 or 1. Such cases are typical for decision-making situations about whether to do something or not - whether to build a plant, plant a certain culture, Whether to make an investment in a specific project. Although the formulations of the overall programming problems often look very similar to some The continual programming problems, the similarity is somehow a mistake. Algebraic expressions of goal and limit functions in these two types of problems have a similar shape, but additional constraints, some or all of them being variable, must make the whole problem much more difficult. Many problems of total programming are classified as hard (hard) Optimization problems. Thus, while the general LP problem can be solved in polynomial time, finding an optimal solution for a corresponding overall task usually requires exponential computer time. However, there are some common problems that can be easily solved. Specifically, many linear network problems such as matching problems, transshipment problems, and network V fault issues always provide the optimal result as an optimal solution