ett linjärt programmeringsproblem kan definieras som problemet att maximera eller minimera en linjär funktion som omfattas av system med linjära begränsningar. Begränsningarna kan vara likheter eller ojämlikheter. Den linjära funktionen kallas målfunktionen, av formen f (x , y ) = A x + b y + c . Lösningsuppsättningen av ojämlikhetssystemet är uppsättningen möjlig eller genomförbar lösning , som är av formen ( x , y ) .,
om ett linjärt programmeringsproblem kan optimeras kommer ett optimalt värde att uppstå vid en av hörnen i regionen som representerar uppsättningen möjliga lösningar.
när grafen för ett system av ojämlikhet bildar en region som är stängd sägs regionen vara avgränsad. Ibland bildar ett system av ojämlikhet en region som är öppen. I detta fall kallas regionen obegränsad.
för att lösa ett linjärt programmeringsproblem, följ dessa steg.
• Graf den region som motsvarar lösningen av systemet med begränsningar.,
• hitta koordinaterna för vertikalerna i regionen som bildas.
• utvärdera målfunktionen vid varje vertex för att bestämma vilka X – och y-värden, om några, maximera eller minimera funktionen.