Симплексный метод

← →
Nick-From © (2004-03-26 13:01) [0]

Народ, есть программка или компонент у кого, чтоб эту муть решать?

← →
Ega23 © (2004-03-26 13:06) [1]

Яндекс - найдётся всё!!!

← →
Blackweber © (2004-03-26 13:29) [2]

Excel - у нас в институте лабы по Симплекс-методу

← →
Ega23 © (2004-03-26 13:39) [3]

Blackweber © (26.03.04 13:29) [2]

Кстати - да, если это разовая лаба для ВУЗаб то лучше Excel не найдёшь. А если на работе потребовалось такой алгоритм втюхивать, то тебе программка готовая не поможет. По-любому самому разбираться придётся.

← →
ИМХО © (2004-03-26 13:39) [4]

TSimplexMethod - на торри.

← →
Nick-From © (2004-03-26 13:46) [5]

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

В чем задача - Задача рационального распределения ресурсов.
Постановка задачи:
Есть n альтернатив (X1, X2, ... ,Xn) - ну например проекты, на которые планируется потратить бюджет организации.
Каждая альтернатива имеет свою стоимость - c (cost) и вес (приоритет, прибыльность) - b (benefit).
Есть бюджет - Sum - который и пойдет на финансирование этих альтернатив. Но он как правило меньше суммарной стоимости всех альтернатив. Отсюда и задача:

c1X1 + c2X2 + ... + ciXi + ... + cnXn <= Sum
b1X1 + b2X2 + ... + biXi + ... + bnXn -> Max
Xi = 0 или Xi = 1

Т.е. надо максимизировать прибыль, не выходя за рамки бюджета. Такую задачу и Excel и комбинаторика может решить - согласен.
Но нужно предусмотреть такие ограничения еще:

1. Xi - обязательно должна быть профинансирована.
2. Xi, Xj, ... , Xk - обязательно должны быть профинансированы.
3. Xm - обязательно должна быть НЕ профинансирована.
4. Xm, Xs, ... , Xf - обязательно должны быть НЕ профинансированы.
5. Скажем 2 и 4 сразу.

6. И условия группирования альтернатив - скажем объединяем альтернативы Xm, Xs, ... , Xf в группу и говорим, что только одна из альтернатив этой группы должна быть профинансирована.

Как решить? Седня пятница как раз, можт кто подскажет?

← →
ИМХО © (2004-03-26 13:52) [6]

Тяпница как раз... грех не выпить... а то люди не поймут...

← →
TUser © (2004-03-26 14:02) [7]

А альтернатив много? Если не очень, то прямой перебор поможет. Я первым делом подумал о рекурсии - на каждом шаге определяем все возможные проекты, которые можно сейчас добавить и передаем в само себя массив уже профинансированных альтернатив + массив еще не профинансированных. Там снова определяем все альтернативы, которые можно провинансировать на новом этапе работы и т.д. Прокатит, если альтернатив меньше тысячи. Если больше - надо думать о конкретных особенностях задачи и искать, на чем бы съэкономить. Вот так.

← →
}|{yk © (2004-03-26 14:19) [8]

не мучайся в Excel все есть. Поиск решения посмотри - все классно и быстро решается. Можно написать макрос, выбрасывать в Excel и там запускать этот макрос. У меня книжка есть решение математических задач в Excel, тоненькая, но написано доходчиво. Правда, если перед этим прослушаешь курс мат. программирования

← →
}|{yk © (2004-03-26 14:22) [9]

А вообще то гоню. У меня есть такая програмка. Мы спорили с со знакомыми , они написали симплекс метод на С++Bulder с использованием STL, а я решил ту же задаче в Excel. Правда у них это заняло месяц, а у меня два часа. Но они оформили это потом как курсовой. Эта програмка с исходниками у меня есть.

← →
Sewix © (2004-03-26 15:12) [10]

вам нужны исходники программы
или просто нужно просто решить?
я делал курсовую "Симплексный метод с искусственным базисом" на Borland С++ 3.1. Если надо могу выслать на мыло

2 TUser © :) Трижды читал - не понял. Объясни по-подробнее пожалуйста. Я тоже думаю, что можно перебором решить. Альтернатив в идеале: 5-15, ну 20 шт. Ну даже если 50. Я так думал - без рекурсии:
1. Будем генерить все возможные сочетания альтернатив.
2. Из этих сочетаний отбираем те, которые подпадают под условие: c1X1 + c2X2 + ... + ciXi + ... + cnXn <= Sum
3. Из выбранных сочетаний выбираем те, которые удовлетворяют оставшимся условиям (не придумал пока как именно).
4. Из получившихся сочетаний ищем, то, которое дает максимум.
Ну в общем матрица получится, которая будет строки терять по мере прохождения алгоритма.

2 }|{yk © Excel уже читаю. Вышли прогу свою пожалуйста. Мне надо сделать двумя способами - в самой моей программе и с выгрузкой в Excel.

2 Sewix © Если не трудно, вышли пожалуйста, я в C не секу, но можт по теории разберусь.

А можт кто видел прогу Expert Choice, там есть такой модуль - Resources Aligner - мне надо такое же написать :)

Вот мать провайдера. Написал ответ - а mtu его не отправл [beep]. Короче, второй раз писать ланиво. Надо создать два массива - для хранения всех переменных и для хранения индексов тех, кто уже отобран. На вход получаем пустой массив. Стоимость -0. Далее делаем цикл по всем элементам. Определяем, можно ли их сейчас добавить в соотвествии с твоими правилами. сли можно - формируем массив из тех элементов, которые уже получены + данный. Передаем через рекурсию. Получаем результат. Для остальных элементов - также, минимум запопинаем. Массива передаваить черех var, тогда вместе с минимумом получим готовое значение массива. Для ускорения процесса можно передавать еще найденный в предыдущих переборах минимум (для первого вызова - просто все имеющиеся в распоряжении бабки) и при переборе не учитывать те варианты, стоимость которых + переданный свыше минимум больше максимума или больше минимума, найденного на пердыдущих итерациях перебора на данном уровне. Хотя для 15-ти вариантов такое ускорение несущественно.

PS. Сколько платят за такую работу? Я не программер, таких штук не далал, мне просто интересно.

Не, перебором и рекурсией не катит. Долго очень...
Никакой TSimplexMethod я не нашел.

Симплексный метод Найти похожие ветки