programación lineal para billetes de autobús

Question

Hola trabajo como programador en una empresa de autobuses y necesito implementar una petición de inicialización de viaje. Creo que puede ser un problema de programación lineal pero no estoy seguro y pido un poco de ayuda :)

Un pasajero envía a mi servidor una solicitud para iniciar un viaje en autobús.

La solicitud incluye las diferentes entidades para la cabalgata. Por ejemplo, una solicitud podría ser :

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

Mi servidor sabe cuáles son los diferentes billetes que tiene el pasajero. Cada billete tiene un coste (el precio al que lo compró el pasajero) y una lista de entidades a las que permite viajar.

Por ejemplo, un pasajero puede poseer :

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

Me encantaría recibir ayuda para diseñar un algoritmo que encuentre la colección óptima de billetes para la atracción (siendo óptima la combinación más barata), o que devuelva un error si la atracción no es factible.

Creo que esto podría representarse como un problema de programación lineal y entonces sólo tengo que utilizar el algoritmo simplex para encontrar la solución óptima. Pero no estoy seguro de cómo hacerlo... por favor, ayúdame que no soy muy experto en matemáticas :/

Gracias.

Answer 1

El ejemplo que has puesto se puede convertir muy fácilmente en un problema de programación lineal.

Versión 1:

Sea Num1 el número del Ticket1, Num2 el número del Ticket 2, etc.

Minimizar el coste total

st

CosteTotal = 10 Num1 + 20 Num2 + 10Num3

Num1+Num3 $\ge 2$ (esto garantiza el número correcto de adultos)

Num2 $\ge 3$ (así se garantiza el número correcto de hijos)

Num3 $\ge 1$ (esto garantiza el número correcto de perros)

Num1 $\ge 2$ (esto garantiza el número correcto de bicicletas)

Versión 2:

Leyendo sus comentarios, me he dado cuenta de la sutileza de que un pasajero ya posee un determinado número de billetes. Vamos a utilizar la variable NumHeld1, NumHeld2 etc para representar estos números.

Podemos suponer que un pasajero preferirá agotar los billetes que tenga en su poder (presumiblemente de prepago) antes de comprar otros nuevos, pero también preferirá optar por un modelo de menor coste. Esta preferencia puede modelizarse estableciendo una función objetivo en la que los billetes ya comprados cuesten menos que los nuevos:

CosteTotal = 10 Num1usingNew + 9 Num1usingHeld + 20 Num 18Num1usingHeld + 10Num3usingNuevo + 9Num3usingHeld

(He reducido un 10% el coste aparente de los billetes retenidos, pero puedes modificarlo en función de lo difícil que les resulte a los clientes comprar nuevos billetes o de lo desesperados que estén por agotar las existencias).

Num1+Num3 $\ge 2$ (esto garantiza el número correcto de adultos)

Num2 $\ge 3$ (así se garantiza el número correcto de hijos)

Num3 $\ge 1$ (esto garantiza el número correcto de perros)

Num1 $\ge 2$ (esto garantiza el número correcto de bicicletas)

Num1=Num1usandoNuevo + Num1usandoConservado

Num2=Num2usandoNuevo + Num2usandoCustodiado

Num3=Num3usandoNuevo + Num3usandoMantenido

Num1usandoCustodia $\le$ NúmeroCustodia1

Num2usandoCustodia $\le$ NúmeroCustodia2

Num3usandoCustodia $\le$ NúmeroCustodia3