algorithm - ser - Encuentra la mejor manera de comprar p Producto de limit x Proveedores

como encontrar proveedores mayoristas

Question

Tengo que comprar 100 productos (o productos p) de 20 proveedores (o v proveedores). Cada vendedor tiene todos estos productos, pero venden precios diferentes.

Quiero encontrar el mejor precio para obtener 100 productos. Supongamos que no hay costo de envío. Hay v ^ p maneras. Y solo obtendré una forma que tenga mejor precio. El problema parece ser fácil si no hay ningún requisito: LIMITE el número de proveedores a x en los pedidos debido a la entrega en el tiempo (o algunas razones).

Entonces, el problema es: Encuentre la mejor manera de comprar p Producto de los proveedores de x de límite (Hay proveedores de v, x <= v).

Puedo generar todas las combinaciones de proveedores (hay combinaciones C (v, x)) y comparar el precio total. Pero hay tantas combinaciones. (Si hay 20 proveedores, hay alrededor de 185k combinaciones). Me quedé en esta idea. Alguien tiene el mismo problema, por favor ayúdame. Muchas gracias.

Answer 1

¿Qué hay de usar un enfoque codicioso? Ya que tiene una limitación en los proveedores (necesita usar al menos x del total de proveedores v). Eso significa que debe elegir al menos 1 producto de cada proveedor de x ... Y aquí hay un ejemplo de solución:

Para cada proveedor en v, ordene los productos por precio, entonces tendrá "v" conjuntos de precios ordenados. Ahora puede elegir el mínimo de estos conjuntos y ordenarlos nuevamente, produciendo un nuevo conjunto de productos "v", que contienen solo los más baratos.

Ahora, si p <= v, luego elija los primeros elementos p y habrá terminado, de lo contrario, elija todos los elementos v y repita la misma lógica hasta que llegue a p.

Answer 2

EDITAR: el algoritmo húngaro no es la respuesta a su pregunta a menos que no haya querido poner un límite a los proveedores.

El algoritmo que está buscando es el algoritmo húngaro .

Hay muchas implementaciones disponibles en la web.

Answer 3

No he trabajado y verificado esto, pero creo que podría funcionar. Prueba esto:

Agregue dos columnas más llamadas "Precio más alto" y "Precio más bajo" a la tabla y genere datos para ellos: deben tener el precio más alto y más bajo para cada producto entre todos los proveedores. También agregue otra columna, llamada "Rango", que debe contener el (precio más alto - precio más bajo).

Ahora haz esto 100 (p) veces:

1. Elige la fila con el rango más alto. Compra el producto con el menor precio en esa fila. Una vez comprado, marque esa celda como ''comprada'' (quizás nula).
2. Recalcular el precio más bajo, rango para esa fila (ignorando las celdas marcadas como ''compradas'').

Answer 4

No es correcto como lo muestra @Per la estructura carece de subestructura óptima

Mis supuestos son los siguientes, de la tabla maestra que necesita para crear una lista secundaria que tenga solo "x" columnas de proveedores, y "Mejor precio" es la "Suma" de todos los precios.

Utilice un enfoque de programación dinámica. Lo que hace es definir dos funciones, Picking (i,k) y NotPicking(i,k) . Lo que significa es obtener lo mejor con la capacidad de elegir proveedores de 1, .. i con un máximo de k proveedores.

Picking (1,_) = Sum(All prices)
NotPicking (1,_) = INF
Picking (_,0) = INF
NotPicking (_,0) = INF

Picking (i,k) = Min (Picking(i-1,k-1) + NotPicking(i-1,k-1)) - D (The difference you get because of having this vendor)
NotPicking (i,k) = Min (Picking(i-1,k) + NotPicking(i-1,k))

Solo resuélvelo para una i de 1 a V y k de 1 a X

Usted calcula la diferencia manteniendo para cada selección la lista completa de productos y calculando la diferencia.

Answer 5

Este problema es equivalente al problema del centro k no métrico (ciudades = productos, almacenes = proveedores), que es NP-difícil.

Intentaría la programación de enteros mixtos. Aquí hay una formulación.

minimize c(i, j) y(i, j)  # cost of all of the orders
subject to
for all i: sum over j of y(i, j) = 1  # buy each product once
for all i, j: y(i, j) <= z(j)  # buy products only from chosen vendors
sum over j of z(j) <= x  # choose at most x vendors
for all i, j: 0 <= y(i, j) <= 1
for all j: z(j) in {0, 1}

La interpretación de las variables es que i es un producto, j es un proveedor, c(i, j) es el costo del producto i del proveedor j , y(i, j) es 1 si compramos el producto i del proveedor j y 0 contrario, z(j) es 1 es lo que compramos del vendedor j y 0 contrario.

Hay many solucionadores de programas enteros mixtos gratuitos disponibles.