|
решение задачи методом "распределения в запросе" | ☑ | ||
---|---|---|---|---|
0
leobrn
19.03.17
✎
11:15
|
Есть задача из универа:
Есть фура объемом 50 000т. Ее нужно загрузить так , чтобы Суммарная стоимость товара, перевозимого фурой, должна быть максимальной. Результат должен быть такой: код партии вес Стоимость 101 10 000 700 000 302 4 000 240 000 601 24 000 2 160 000 602 11 000 990 000 Пробую методом из статьи(http://catalog.mista.ru/public/568299/): ВЫБРАТЬ "A" КАК Фура, 50000 КАК Объем ПОМЕСТИТЬ Фуры ; //////////////////////////////////////////////////////////////////////////////// ВЫБРАТЬ "101" КАК Партия, 10000 КАК Вес, 700000 КАК Стоимость ПОМЕСТИТЬ Партии ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "201", 12000, 540000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "301", 14000, 840000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "302", 4000, 240000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "401", 8000, 640000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "501", 16000, 880000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "601", 24000, 2160000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "602", 11000, 990000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "701", 10000, 400000 ОБЪЕДИНИТЬ ВСЕ ВЫБРАТЬ "801", 18000, 630000 ; //////////////////////////////////////////////////////////////////////////////// ВЫБРАТЬ Фуры.Фура КАК Фура, Фуры.Объем КАК Объем, ЕСТЬNULL(СУММА(Фуры1.Объем), 0) + 1 КАК ПорядокРаспределенияС, ЕСТЬNULL(СУММА(Фуры1.Объем), 0) + Фуры.Объем КАК ПорядокРаспределенияПо ПОМЕСТИТЬ ФурыПоПорядку ИЗ Фуры КАК Фуры ЛЕВОЕ СОЕДИНЕНИЕ Фуры КАК Фуры1 ПО Фуры.Фура > Фуры1.Фура СГРУППИРОВАТЬ ПО Фуры.Фура, Фуры.Объем ; //////////////////////////////////////////////////////////////////////////////// ВЫБРАТЬ Партии.Партия КАК Партия, Партии.Вес КАК Вес, Партии.Стоимость КАК Стоимость, ЕСТЬNULL(СУММА(Партии1.Вес), 0) + 1 КАК ПорядокРаспределенияС, ЕСТЬNULL(СУММА(Партии1.Вес), 0) + Партии.Вес КАК ПорядокРаспределенияПо ПОМЕСТИТЬ ПартииПоПорядку ИЗ Партии КАК Партии ЛЕВОЕ СОЕДИНЕНИЕ Партии КАК Партии1 ПО Партии.Стоимость < Партии1.Стоимость СГРУППИРОВАТЬ ПО Партии.Партия, Партии.Вес, Партии.Стоимость ; //////////////////////////////////////////////////////////////////////////////// ВЫБРАТЬ ФурыПоПорядку.Фура КАК Фура, ПартииПоПорядку.Партия КАК Партия, ВЫБОР КОГДА ПартииПоПорядку.ПорядокРаспределенияПо < ФурыПоПорядку.ПорядокРаспределенияПо ТОГДА ПартииПоПорядку.ПорядокРаспределенияПо ИНАЧЕ ФурыПоПорядку.ПорядокРаспределенияПо КОНЕЦ - ВЫБОР КОГДА ПартииПоПорядку.ПорядокРаспределенияС > ФурыПоПорядку.ПорядокРаспределенияС ТОГДА ПартииПоПорядку.ПорядокРаспределенияС ИНАЧЕ ФурыПоПорядку.ПорядокРаспределенияС КОНЕЦ + 1 КАК Вес, ПартииПоПорядку.Стоимость КАК Стоимость, ПартииПоПорядку.ПорядокРаспределенияПо, ФурыПоПорядку.ПорядокРаспределенияПо КАК ПорядокРаспределенияПо1, ПартииПоПорядку.ПорядокРаспределенияС, ФурыПоПорядку.ПорядокРаспределенияС КАК ПорядокРаспределенияС1 ИЗ ФурыПоПорядку КАК ФурыПоПорядку ВНУТРЕННЕЕ СОЕДИНЕНИЕ ПартииПоПорядку КАК ПартииПоПорядку ПО ФурыПоПорядку.ПорядокРаспределенияС <= ПартииПоПорядку.ПорядокРаспределенияПо И ФурыПоПорядку.ПорядокРаспределенияПо >= ПартииПоПорядку.ПорядокРаспределенияС Результат получается такой: Партия Вес Стоимость 601 24 000 2 160 000 602 11 000 990 000 501 15 000 880 000 Подскажите, как изменить условия, чтобы получалась максимальная загрузка по стоимости. |
|||
1
МихаилМ
19.03.17
✎
12:42
|
10+
4+ 24+ 11+ = 49 нечего распределять. все итак помещается. объем указывается в единицах объема , а не веса. |
|||
2
leobrn
19.03.17
✎
12:53
|
(1) это результат, который должен получить я, понятно что он помещается .
|
|||
3
Dmitry1c
19.03.17
✎
12:54
|
(0) никак ты это не решишь алгоритмически, мощности железа не хватит.
Эта задача из разряда "задача про коммивояжера" |
|||
4
leobrn
20.03.17
✎
05:25
|
(3) решают как-то) и на 1с...
|
|||
5
organizm
20.03.17
✎
08:00
|
А габариты разве не надо учитывать? Объем и вес вы может и заполните, а габариты груза окажутся не подходящими...
|
|||
6
organizm
20.03.17
✎
08:01
|
+ у вас ведь не жидкость.
|
|||
7
Garykom
гуру
20.03.17
✎
08:14
|
Меня иногда реально удивляют люди... интересно сколько "программистов" сможет ЕГЭ пройти хотя бы на 70 баллов
1. Раз нет ограничений по объему (только по весу) и информации об упаковках считаем что грузить можно любого товара сколько угодно МАЛЫЙ вес. 2. Поэтому считаем коэффициент выгодности в пересчете на 1 кг груза. 3. Грузим фуру последовательно всеми наиболее выгодными грузами по 1 кг, сначала 11 тонн общей стоимостью 990 000, затем всем прочими грузами (кончился более выгодный грузим следющим по очереди) пока грузоподъемность фуры есть |
|||
8
Naf2017
20.03.17
✎
08:20
|
Самый дорогой товар надо грузить
|
|||
9
НЕА123
20.03.17
✎
08:23
|
(7)
> Грузим фуру последовательно всеми наиболее выгодными грузами по 1 кг, сначала нет. далеко не всегда так. |
|||
10
Garykom
гуру
20.03.17
✎
08:27
|
(9) Прекрасно понимаю, но каким образом это относится к данной учебной задаче?
|
|||
11
НЕА123
20.03.17
✎
08:32
|
(10)
короче, перебор в оптимизации никто не отменял. как это делать запросом... |
|||
12
Garykom
гуру
20.03.17
✎
08:53
|
(11) Это надо у Ildarovich спросить как гения (имхо изврат но склоняю голову) в применении запросов для подобного
http://catalog.mista.ru/public/267268/ http://catalog.mista.ru/public/271270/ |
|||
13
rabbidX
20.03.17
✎
09:22
|
(0) Навскидку 48т 601 товара должны быть решением.
Если последовательно решать, то Целевая функция 70а + 24b + 216c + 99d ->max ограничения 10а + 4b + 24c + 11d <=50 a,b,c,d целые неотрицательные Пусть х = а+b+d, тогда Целевая функция 193x + 216c ->max ограничения 25x + 24c <=50 x,c целые неотрицательные. Допустимые решения (2,0) (1,1) (0,2) Оптимальное (0,2) как и предполагалось. Если бы получили решение с x <> 0, тогда вернулись бы к начальной задаче, но уже зная значение c. В общем, максимум в 3 этапа решается. |
|||
14
rabbidX
20.03.17
✎
09:24
|
(7) Товар неделимый, судя по всему.
|
|||
15
rabbidX
20.03.17
✎
09:36
|
Вроде, в унивире решали сразу для нескольких переменных такие задачи, че-то подзабывлось.
Вообще, раз все коэффициенты неотрицательные, и целевая функция линейная, то все, кроме одного должны быть равны 0. Это видно, если решить графически задачу для двух переменных. |
|||
16
rabbidX
20.03.17
✎
09:37
|
(15) хотя нет, это для целочеисленных коэффициентов не работает.
|
|||
17
Garykom
гуру
20.03.17
✎
09:41
|
(14) Если неделимый то обычная укладка рюкзака и там куча способов
|
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |