Podręcznik

• Zmienne decyzyjne: \( x_j = 1,2,...,n \)
• Przestrzeń decyzji: \(X = R^n\)
• Zbiór decyzji dopuszczalnych: \(Q\subset X\)
  
• Wektory (rozwiązania, decyzje) dopuszczalne: \( x\in Q \)
• Miara jakości (wynik) decyzji, funkcja celu, kryterium: \(f: R^n\rightarrow R\)
•  Zadanie optymalizacji (programowanie matematyczne):\\
     \(\max \{ f(x): x\in Q\}\)

        Wyznaczyć \(\bar{x}\in Q\) taki, że
        \(f(\bar{x}) \geq f(x)\quad \forall x\in Q\)

•   \(\bar{x}\) -- rozwiązanie optymalne
• \(f(\bar{x})\) -- wartość optymalna

W zadaniach liniowych Q jest zbiorem rozwiązań następującego układu ograniczeń:

a funkcja celu ma postać:

W problemach dyskretnych natomiast zbiór \(Q\) jest dyskretny, tzn. jest zbiorem skończonym albo jest skończoną sumą niespójnych składowych. Oznacza to, że zmienne decyzyjne przyjmują wartości całkowitoliczbowe. W takiej sytuacji zadanie optymalizacji, liniowe-całkowitoliczbowe (PLC, ILP), wygląda (w zapisie macierzowym) następująco:

Jeśli w zadaniu mogą występować również zmienne ciągłe, mamy do czynienia z zadaniem mieszanym, liniowym-całkowitoliczbowym (MILP).

Znaczenie problemów MILP wynika z tego, że wiele zagadnień nieliniowych, kombinatorycznych czy logicznych daje się modelować dokładnie bądź w przybliżeniu za pomocą takich modeli. W szczególności modelowanie matematyczne, w tym MILP, możemy traktować jako rodzaj programowania deklaratywnego, analogicznie do języka opisu zapytań SQL. Stąd nazwa programowanie matematyczne.

Przykłady klas problemów, które można rozwiązywać przez optymalizację modeli MILP: zadania harmonogramowania, kombinatoryczne, przydziału zasobów, optymalizacji łańcucha dostaw, optymalizacji sieciowej, etc.

Modele MILP mogą być rozwiązywane za pomocą specjalizowanych algorytmów (branch-and-bound, branch-and-cut, programowanie dynamiczne, itp), często dostępnych w postaci solwerów. Do najbardziej znanych należą: a)komercyjne: CPLEX, GUROBI b) otwarte: CBC, GLPK, ORTOOLS.