Минимизация стоимости угольных смесей

Форум для обсуждения вопросов математики

Модератор: Admin

Сергей Денисов
Сообщения: 3
Зарегистрирован: Ср сен 10, 2014 11:37 am
Откуда: Россия
Контактная информация:

Минимизация стоимости угольных смесей

Сообщение Сергей Денисов » Чт сен 11, 2014 10:41 am

Область: Поиск минимума функции многих переменных с заданными ограничениями.
Цель: Создать компьютерный алгоритм, подобный экселевскому "Поиску решений", для конкретной задачи.

Добрый день.
Я на форуме новичок и, возможно, влез не совсем в ту тему. Буду благодарен, если направите меня в "ту".

Суть задачи:
1. Заказчик (например, ТЭС, работающая на угле) нуждается в угле с определенными количественным составом и параметрами (влажность %, сера %, теплотворность ккал/кг, размер частиц мм и т.п., всего около 25).
2. На параметры могут быть, а могут и не быть заданы мин. и макс. значения (ограничения могут задаваться как на мин. и макс., так и только на мин. или только на макс.).
3. Практически никогда конкретная марка угля (доступны несколько десятков марок, соответствующих разным месторождениям, шахтам, разрезам) сама по себе не удовлетворяет всем требуемым параметрам, а только некоторым, разным для разных марок.
Что делать? Смешивать разные марки и добиваться того, чтобы все параметры смеси (средневзвешенные по весу марки угля в составе заданного общего веса смеси) попали в разрешенный диапазон.
4. Все марки угля имеют разную конечную цену, которая формируется на основании нескольких показателей (как - к нашей задаче не относится). Естественно, из всех пригодных смесей необходимо выбрать ту, которая получается самой дешевой.

Итак, задача:

Найти минимальную величину ОбщаяСумма

ОбщаяСумма = ВесМарки1*Цена1 + ВесМарки2*Цена2 +ВесМарки3*Цена3 + ... + ВесМаркиN*ЦенаN,

подбором (перебором) входящих в смесь марок (не обязательно всех) и весов марок так, чтобы все средневзвешенные значения параметров смеси

(ЗначениеПараметраХМарки1 * ВесМарки1 + ЗначениеПараметраХМарки2 * ВесМарки2 + ... + ЗначениеПараметраХМаркиN * ВесМаркиN)/ОбщийВесСмеси

попадали в заданные диапазоны

ЗначениеПараметраХ_Мин <= ЗначениеПараметраХ <= ЗначениеПараметраХ_Макс


В Excel'e с помощью надстройки "Поиск решения" (с опцией "метод Ньютона") это решается менее, чем за секунду (дольше вводить исходные данные).
Изображение
Изображение

ТРЕБУЕТСЯ:

Расписать решение этой задачи в виде алгоритма, который я, как программист (не математик), смогу понять и реализовать программными средствами в своей базе данных, которая помимо этого решает еще кучу других задач.
Скорость нахождения минимума не очень критична - если не получится так же быстро, как в Excel'e, то, скажем, ожидание до 5 мин. устроит.
Точность - важнее (влияет на стоимость результирующей смеси).
Если функция имеет не единственный минимум, хотелось бы видеть минимум миниморум и ближайшие к нему (или вообще все минимумы) - т.е. в процессе подбора иметь возможность запоминать промежуточные подборки (это, конечно, моя забота).

Буду благодарен просто за конструктивные комментарии, советы и наводки.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Сб сен 20, 2014 12:25 am

Ваша задача - это классическая задача линейного программирования. Она эквивалентна так называемой задаче о рационе (подобрать наиболее дешёвый вариант рациона для домашнего животного, удовлетворяющий ограничениям по питательности). Решается точно симплекс-методом, который описан во множестве учебников (ищите в интернете).

Сергей Денисов
Сообщения: 3
Зарегистрирован: Ср сен 10, 2014 11:37 am
Откуда: Россия
Контактная информация:

Сообщение Сергей Денисов » Сб сен 20, 2014 5:01 pm

Спасибо, Kitonum.
Да, что это классика и что это симплекс, я уже почитал, понял, и восхитился.
Но вопрос-то был про то, есть ли у кого-то (или может кто-то написать или показать, где лежит) алгоритм нахождения минимума, понятный мне как программисту, без "страшилок" типа "векторы, входящие в базис, компоненты опорного плана, направляющие столбцы" и прочей недоступной мне магии.
Сил и времени у меня на ее постижение нет, вот и хотелось заинтересовать профессионалов.
А Admin меня отругал и удалил мой "коммерческий" вариант запроса.
Буду теперь запускать циклы на миллион итераций.
Да и то, боюсь, не поможет. :(

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Где почитать

Сообщение Kitonum » Сб сен 20, 2014 5:56 pm

Сергей Денисов писал(а):Но вопрос-то был про то, есть ли у кого-то (или может кто-то написать или показать, где лежит) алгоритм нахождения минимума, понятный мне как программисту, без "страшилок" типа "векторы, входящие в базис, компоненты опорного плана, направляющие столбцы" и прочей недоступной мне магии.
Сил и времени у меня на ее постижение нет, вот и хотелось заинтересовать профессионалов.

Алгоритм симплекс-метода предельно доступно описан в главе 3 книги Таха "Введение в исследование операций"

Сергей Денисов
Сообщения: 3
Зарегистрирован: Ср сен 10, 2014 11:37 am
Откуда: Россия
Контактная информация:

Сообщение Сергей Денисов » Сб сен 20, 2014 7:03 pm

Еще раз спасибо, придется изучать.