Wie repräsentiert man eine Busfahrt in der linearen Programmierung?

Question

Hallo Ich arbeite als Programmierer bei einer Busgesellschaft und ich muss eine Fahrinitialisierungsanforderung implementieren. Ich denke, es könnte ein lineares Programmierproblem sein, aber ich bin mir nicht sicher und ich frage nach etwas Hilfe :)

Ein Passagier schickt meinem Server eine Anfrage, um eine Busfahrt zu initialisieren.

Die Anfrage enthält die verschiedenen Entitäten für die Fahrt. Zum Beispiel eine Anfrage könnte sein:

Mein Server weiß, was die verschiedenen Tickets der Passagier hat. Jedes Ticket hat Kosten (der Preis, mit dem der Passagier es gekauft hat) und eine Liste von Entitäten, für die es eine Fahrt ermöglicht.

Zum Beispiel könnte ein Passagier besitzen:

Ticket1- cost 10, enables [1 Adult, 1 Bike] 
Ticket2- cost 20, enables [1 Child] 
Ticket3- cost 10, enables [1 Adult, 1 Dog] 

Ich würde etwas Hilfe lieben einen Algorithmus entwerfen, die die optimale Sammlung von Karten findet für die Fahrt zu verwenden (optimal die günstigste Kombination ist), oder Fehler zurück wenn die Fahrt nicht möglich ist.

Ich denke, das könnte als ein lineares Programmierproblem dargestellt werden und dann kann ich einfach den Simplex-Algorithmus verwenden, um die optimale Lösung zu finden. Aber ich bin nicht sicher, wie es geht ... bitte helfen Sie mir, ich bin nicht viel von einem Mathe-Experten:/

Vielen Dank!

Answer 1

Hier ist ein R-Code, der als Vorlage für Ihr Problem verwendet werden kann.

library(lpSolveAPI) 

solve_request <- function(request, available_tickets) { 
    lprec <- make.lp(0, ncol=3) # decision variables: how many tickets of type 1, 2 or 3 
    set.type(lprec, columns=seq(1,3), type="integer") # the decision variables are integers, there are no half tickets 
    set.objfn(lprec, obj=c(10, 20, 10)) # objective: minimize costs of tickets 

    # first type of constraints: no more tickets than available 
    add.constraint(lprec, xt=c(1,0,0), type="<=", rhs=available_tickets["t1"]) 
    add.constraint(lprec, xt=c(0,1,0), type="<=", rhs=available_tickets["t2"]) 
    add.constraint(lprec, xt=c(0,0,1), type="<=", rhs=available_tickets["t3"]) 

    # second type of constraint: choosen ticket must meet request 
    add.constraint(lprec, xt=c(1,0,1), type=">=", rhs=request["adults"]) 
    add.constraint(lprec, xt=c(0,1,0), type=">=", rhs=request["children"]) 
    add.constraint(lprec, xt=c(0,0,1), type=">=", rhs=request["dogs"]) 
    add.constraint(lprec, xt=c(1,0,1), type=">=", rhs=request["bikes"]) 

    solve(lprec) 
    return(setNames(get.variables(lprec), c("t1", "t2", "t3"))) 
} 

solve_request(request=c(adults=2, children=3, dogs=1, bikes=2), available_tickets=c(t1=10, t2=10, t3=10)) 

Es gibt

t1 t2 t3 
1 3 1