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

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

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

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