Здравствуйте. У меня такая задача. Есть набор ресурсов, есть соотношения за какой сколько дают другого, каждый с каждым. То есть квадратная матрица, с 1-й по диагонали, естественно. Надо найти такую цепочку обменов ресурсов один на другой с возвратом к первому, чтобы прибыль была максимальная.
Через графы это формулируется так, что каждый ресурс вершина, направленные рёбра - соотношения ценности ресурсов. Надо найти такой путь в графе с возвратом в исходную точку, чтобы произведение весов рёбер было максимально.
В прилагаемом файле - в ячейках B7:H11 сама матрица связности графа или таблица цен.
Ниже я сделал ячейки, где можно вручную вбить любой путь до 6 узлов и подсчитается результат для него. Вводятся номера ресурсов, и эти номера используются в функции =СМЕЩ() для нахождения нужной ячейки в таблице цен. Результат умножается на результат на предыдущем шаге. Если итог выше 1 - обмен выгоден. Вручную работает, но хочется автоматизировать.
Пробовал в лоб через "Поиск решения". Внизу упростил до 3-х узлов. Ожидал, что Excel будет делать полный перебор, но он как-то странно пытается в ячейки, где ставлю целое или уже сделал даже двоичное, подставлять дробные значения. Пробовал с разными параметрами в диалоге поиска решений - ничего не помогает.
Подскажите, пожалуйста, что делаю не так и возможно ли такое в Excel 2003 или появилось только в более поздних версиях? Там вроде есть другие варианты поиска решений, может перебор только там?
Здравствуйте. У меня такая задача. Есть набор ресурсов, есть соотношения за какой сколько дают другого, каждый с каждым. То есть квадратная матрица, с 1-й по диагонали, естественно. Надо найти такую цепочку обменов ресурсов один на другой с возвратом к первому, чтобы прибыль была максимальная.
Через графы это формулируется так, что каждый ресурс вершина, направленные рёбра - соотношения ценности ресурсов. Надо найти такой путь в графе с возвратом в исходную точку, чтобы произведение весов рёбер было максимально.
В прилагаемом файле - в ячейках B7:H11 сама матрица связности графа или таблица цен.
Ниже я сделал ячейки, где можно вручную вбить любой путь до 6 узлов и подсчитается результат для него. Вводятся номера ресурсов, и эти номера используются в функции =СМЕЩ() для нахождения нужной ячейки в таблице цен. Результат умножается на результат на предыдущем шаге. Если итог выше 1 - обмен выгоден. Вручную работает, но хочется автоматизировать.
Пробовал в лоб через "Поиск решения". Внизу упростил до 3-х узлов. Ожидал, что Excel будет делать полный перебор, но он как-то странно пытается в ячейки, где ставлю целое или уже сделал даже двоичное, подставлять дробные значения. Пробовал с разными параметрами в диалоге поиска решений - ничего не помогает.
Подскажите, пожалуйста, что делаю не так и возможно ли такое в Excel 2003 или появилось только в более поздних версиях? Там вроде есть другие варианты поиска решений, может перебор только там?Dron007
Если вершин всего 6, то можно решить полным перебором всех возможных вариантов, всего получится 5! = 120 перестановок 10-12 вершин также попадают под данный алгоритм решения, а вот 20 уже не решить перебором
Можно попробовать адаптировать какой нибудь алгоритм по обходу графа
Если вершин всего 6, то можно решить полным перебором всех возможных вариантов, всего получится 5! = 120 перестановок 10-12 вершин также попадают под данный алгоритм решения, а вот 20 уже не решить перебором
Можно попробовать адаптировать какой нибудь алгоритм по обходу графаMCH
Если вершин всего 6, то можно решить полным перебором всех возможных вариантов, всего получится 5! = 120 перестановок
Там вроде бы больше вариантов получается, т.к. 1-2-3-1 и 1-3-2-1 тут разные пути. По максимуму 6^6 = 46656, но на деле, конечно же намного меньше, т.к. нет петель 1-2-3-2-1 и пути типа 1-2-3 и 2-3-1 и 3-1-2 идентичны.
Но у меня вопрос в том, как на практике это осуществить в Excel и желательно не через макросы, так я могу и просто программу написать, без Excel.
Если вершин всего 6, то можно решить полным перебором всех возможных вариантов, всего получится 5! = 120 перестановок
Там вроде бы больше вариантов получается, т.к. 1-2-3-1 и 1-3-2-1 тут разные пути. По максимуму 6^6 = 46656, но на деле, конечно же намного меньше, т.к. нет петель 1-2-3-2-1 и пути типа 1-2-3 и 2-3-1 и 3-1-2 идентичны.
Но у меня вопрос в том, как на практике это осуществить в Excel и желательно не через макросы, так я могу и просто программу написать, без Excel.Dron007
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
