Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 12 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 15:27 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте, уважаемые участники форума.
Прошу помочь с решением практической задачи.
Или подсказать в какую сторону копать

Даны товары от нескольких поставщиков.
Ключевыми характеристиками товаров являются:
1. Доступность на складе - stock
2. Кратность - mult (кол-во, кратно которому можно увеличивать заказ)
3. Минимальное кол-во - min (кол-во, минимально возможное для заказа)
4. Цена - price

Таблица 1 — Характеристики товаров

ПоставщикДоступноКратностьМин. ЗаказЦена
ООО Ромашка 1100004740
ООО Ромашка 2112420
ООО Ромашка 310001110
ООО Ромашка 48810505
ООО Ромашка 511150505

Всего доступно на складах поставщиков доступно — 11210 шт.

Требования
1. Необходимо осуществить сборку заказа, включающую — 5000 шт.
2. При этом сумма заказа должна быть минимальной.
3. В случае если решение задачи отсутствует, то должен быть предложен состав заказа, минимально превышающий целевое количество, т.е. 5000


Таблица 1 — Ожидаемый результат вычислений.

ПоставщикЗаказаноЦенаСтоимость
ООО Ромашка 1381240152480
ООО Ромашка 21020200
ООО Ромашка 3998109980
ООО Ромашка 4805400
ООО Ромашка 51005500
Итого5000163560



Рассмотренные варианты решения
1. Алгоритмический.
В цикле за один проход максимально забирать кол-во stock, соответствующее условиям mult и min.
Данный вариант не будет работать, т.к. в представленных для примера данных в этом случае можно получить только 4998 шт. товара. То есть требование по количеству не соблюдается.
Одним из вариантов может быть усложнение алгоритма, но этот путь не кажется оптимальным.

2. Симплексный метод.
В качестве второго варианта был рассмотрен симплексный метод. Недостатком его является сложность реализации со стороны разработчика, т.к. готовых php библиотек нет.
Кроме того, такое свойство товара, как кратность мне не удалось привести к канонической форме.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 15:37 
Не в сети
Одарённый
Зарегистрирован:
17 апр 2020, 10:40
Сообщений: 165
Cпасибо сказано: 4
Спасибо получено:
61 раз в 52 сообщениях
Очков репутации: 12

Добавить очки репутацииУменьшить очки репутации
Denis_m писал(а):
Кроме того, такое свойство товара, как кратность мне не удалось привести к канонической форме

Разделите все столбцы кроме цены нацело на кратность, цену - соответственно умножить.
Далее типовая задача ЛП.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю Bloodhound "Спасибо" сказали:
Denis_m
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 19:12 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Bloodhound писал(а):
Denis_m писал(а):
Кроме того, такое свойство товара, как кратность мне не удалось привести к канонической форме

Разделите все столбцы кроме цены нацело на кратность, цену - соответственно умножить.
Далее типовая задача ЛП.


Спасибо. С ценой и кратностью вроде разобрался. Что-то вроде похожее считает, а вот как быть с ограничением на минимальное количество.
Если поставить жесткие ограничение, например:
"ООО Ромашка 1" >= 7
"ООО Ромашка 2" >= 4
"ООО Ромашка 3" >= 1
"ООО Ромашка 4" >= 50
"ООО Ромашка 5" >= 50

то получается я вношу неверные условия.

А как сделать так, чтобы условие было примерно следующим?
"ООО Ромашка 1" >= 7 OR "ООО Ромашка 1" = 0
"ООО Ромашка 2" >= 4 OR "ООО Ромашка 1" = 0
"ООО Ромашка 3" >= 1 OR "ООО Ромашка 1" = 0
"ООО Ромашка 4" >= 50 OR "ООО Ромашка 1" = 0
"ООО Ромашка 5" >= 50 OR "ООО Ромашка 1" = 0

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 21:25 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Bloodhound писал(а):
Разделите все столбцы кроме цены нацело на кратность, цену - соответственно умножить.
Далее типовая задача ЛП


Что-то таки получилось, решение даже лучше, чем я сделал подбором (см. выше).
Изображение

Но есть один проблем.
Как я и писал ранее необходимо как-то обойти ситуацию с жестким ограничением на минимальное количество, потому что если я, например, изменю условие и у самого дешевого товара увеличу цену на 1000 , то симплекс все равно возьмет этот товар в минимальном количестве.

Вот пример этой проблемы.
Изображение



Denis_m писал(а):
А как сделать так, чтобы условие было примерно следующим?
"ООО Ромашка 1" >= 7 OR "ООО Ромашка 1" = 0

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 21:47 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Пока как вариант решения вижу только добавлять в цикле по одному поставщику с самым дешевым товаром, до тех пор пока у задачи не найдется решение.
Но может есть какой-то более оптимизированный вариант?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 02 апр 2024, 22:57 
Не в сети
Последняя инстанция
Зарегистрирован:
24 апр 2010, 23:33
Сообщений: 3344
Cпасибо сказано: 241
Спасибо получено:
1002 раз в 866 сообщениях
Очков репутации: 272

Добавить очки репутацииУменьшить очки репутации
По-моему, это задача динамического программирования.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю vvvv "Спасибо" сказали:
Denis_m
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 03 апр 2024, 00:02 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
vvvv писал(а):
По-моему, это задача динамического программирования.


Возможно, только ума не приложу, как ее правильно поставить.
Я представил задачу в более простом варианте , чем она есть на самом деле.
В реальности у одного поставщика может быть несколько предложений, например, цена за единицу товара может уменьшаться с увеличением количества закупаемого товара.
Количество поставщиков может доходить до 30, поиск может осуществляться сразу по 1000 разных товаров.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 03 апр 2024, 07:58 
Не в сети
Одарённый
Зарегистрирован:
17 апр 2020, 10:40
Сообщений: 165
Cпасибо сказано: 4
Спасибо получено:
61 раз в 52 сообщениях
Очков репутации: 12

Добавить очки репутацииУменьшить очки репутации
Denis_m
Согласен, учет мин.партии нарушает линейность.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 03 апр 2024, 12:37 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
vvvv
Bloodhound
Может подскажете в какую сторону копать?
Литературу какую-нибудь порекомендуете?
То что нашел в интернете по динамическому программированию, это скорее описание концепции, нежели подробное описание технологии и подходов к реализации.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача на сбор заказа по минимальной цене
СообщениеДобавлено: 03 апр 2024, 13:22 
Не в сети
Начинающий
Зарегистрирован:
02 апр 2024, 14:44
Сообщений: 7
Cпасибо сказано: 2
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Denis_m писал(а):
Bloodhound писал(а):
Разделите все столбцы кроме цены нацело на кратность, цену - соответственно умножить.
Далее типовая задача ЛП


Заметил, что картинки не добавляются, прилагаю ссылки на картинки.

Solve
https://photos.app.goo.gl/t7TNMsahEZbVhpQEA

Wrong solve
https://photos.app.goo.gl/nys3fjeTBLkTKk1H8

PS. Товарищи Модераторы просьба доработать загрузку файлов и картинок, к сожалению, работает неадекватно.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2  След.  Страница 1 из 2 [ Сообщений: 12 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задача по нахождению оптимального заказа

в форуме Исследование операций и Задачи оптимизации

akubonin

2

469

02 фев 2016, 15:53

Какова вероятность того, что выбранная из этого заказа

в форуме Комбинаторика и Теория вероятностей

ilanaP

1

347

05 дек 2017, 08:23

Привести функцию к минимальной ДНФ

в форуме Интегральное исчисление

dimitro

1

74

10 май 2023, 12:54

Несмещёная оценка с минимальной дисперсией

в форуме Математическая статистика и Эконометрика

tariel-x

0

206

22 май 2017, 01:04

Визуально-матричный метод нахождения минимальной ДНФ

в форуме Дискретная математика, Теория множеств и Логика

progrart

2

421

07 ноя 2015, 19:07

Доказать, что аддитивная цепочка является минимальной

в форуме Дискретная математика, Теория множеств и Логика

evgeniy_mea

4

509

02 июн 2014, 11:31

Масштабирование минимальной разницы между графиками

в форуме Исследование операций и Задачи оптимизации

Katrinka_111

1

93

07 апр 2023, 11:38

При какой минимальной скорости плиты u шайба может догнать

в форуме Механика

MuCTeP_TTP0

28

428

24 авг 2023, 13:38

Теория вероятности: задача про шары и задача про точку

в форуме Теория вероятностей

AdmiralAnanas

6

491

02 окт 2021, 01:43

Задача на построение. Корректна ли задача?

в форуме Геометрия

Student Studentovich

9

672

19 июл 2020, 19:17


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved