Как представить поездку на автобусе в линейном программировании?

Question

Привет Я работаю программистом в автобусной компании, и мне нужно реализовать запрос инициализации езды. Я думаю, что это может быть проблема линейного программирования, но я не уверен, и я прошу о помощи :)

Пассажир отправляет моему серверу запрос на инициализацию поездки на автобусе.

Запрос включает в себя различные объекты для поездки. Например, запрос может быть:

Request = [2 Adults, 3 Children, 1 Dog, 2 Bikes] 

Мой сервер знает, какие у пассажиров разные билеты. Каждый билет имеет стоимость (цена, которую купил его пассажир) и список объектов, на которые он может ездить.

Например, пассажир может обладать:

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

Я хотел бы некоторую помощь разработке алгоритма, который находит оптимальную коллекцию билетов использовать для поездки (оптимальное время самое дешевое сочетание), или вернуть ошибку если поездка невозможна.

Я думаю, что это может быть представлено как проблема линейного программирования, а затем я могу просто использовать симплекс-алгоритм, чтобы найти оптимальное решение. Но я не уверен, как это сделать ... пожалуйста, помогите мне. Я не очень квалифицированный специалист по математике:/

Спасибо!

Answer 1

Это код, который может быть использован как шаблон для вашей проблемы.

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)) 

возвращает

t1 t2 t3 
1 3 1