Алгоритм.

← →
Founder (2001-11-29 11:34) [0]

Задача:
Есть:
M товаров. У каждого товара есть цена и кол-во в наличии. Есть N комплектов товаров(список какого товара и сколько входит в данный комплект).
Задача: надо найти оптимальную комплектацию (раскидать имеющийся в наличии товар по комплектам) с условием что суммарная стоимость скомплектованного товара была б максимальна.

← →
Владислав (2001-11-29 11:47) [1]

Может я чего-то не понял. Вот например:

Товары:
1. Стол, 100 руб., 20 шт.
2. Стул, 50 руб., 50 шт.
...
Комплекты:
1. Уголок: 2 стола, 4 стула.

Стоимость уголка 2 * 100 руб. + 4 * 50 руб. = 400 руб.

При чем здесь максимальная суммарная стоимость?

← →
Крутов Алексей (2001-11-29 12:35) [2]

Данная задача решается с помощью симплекс метода. Необходимо выбрать переменные, составить целевую функцию и составить систему ограничений.
А вообще поищи в Инете статьи по симплекс методу, их здесь немеренно.

← →
Владислав (2001-11-29 13:01) [3]

> Крутов Алексей © (29.11.01 12:35)

Ага. Или дуплекса. "Суммарная стоимость" х 2.

:)))

← →
Крутов Алексей (2001-11-29 13:08) [4]

> Владислав
Не совсем понял что ты имел в виду.
Подробнее о том, как можно поставить задачу.

Пусть x1- количество комплектов первого типа,
x2- количество комплектов второго типа и т.д. (неизвестные величины)

Обозначим через A11 количество товаров первого типа, входящих в
первый комплект.

Aij-количество товаров i-го типа, входящих в j комплект.
Пусть Bi-количество товара i-го типа, имеющихся в наличии

Система ограничений:

A11*x1+...+Ann*xn<=b1
...
Am1*x1+...+Amn*xn<=bm

xi>=0 по смыслу.

Целевая функция:
c1*x1+...+cm*xm->max, где сi- стоимость i-го комплекта

← →
Desdechado (2001-11-29 19:58) [5]

задача о назначениях из курса "исследование операций"
есть методы и проще, чем симплекс.
читайте учебники, например, Вентцель Е.С. "Исследование операций"

← →
SergVlad (2001-11-29 23:01) [6]

Думаю, что в данном случае можно обойтись и бе сложностей.
1. Имеется N разновидностей товара для составления комплекта.
2. По каждой разновидности товара имеется множество товарных позиций,
состоящее из партий Цена/Количество.
(Стул: 5 шт по цене 100р, 10 шт по цене 120р и т.д.)
Решение:
1.Найти минимальное количество товара MIN из N разнопидностей - это определит максимально возможное кол-во комплектов.
2.В каждой из N разновидностей произвести упорядчивание по ценам и отобрать
первые MIN позиций c максимальными ценами.
Собственно, вот и все.
Далее можно рассчитать среднюю цену комплекта и покомплектные цены.

Алгоритм. Найти похожие ветки