|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Roman Kukushkin 2:5025/37.216 21 May 2003 18:19:44
To : Paul Lyakhnitskiy
Subject : Задача календаpного планиpования
--------------------------------------------------------------------------------
Воскресенье Май 18 2003 в 23:32 Paul Lyakhnitskiy писал Roman Kukushkin:
PL> В том-то и дело, что поводом дискуссии и был вопрос применимости
PL> симплекс-метода к описанной задаче. Если вспомнить стандартную форму
PL> записи ОЗЛП: cx -> min (целевая функция линейно зависима от х)
PL> Ax = b (ограничения - линейны)
PL> x >= 0 (х на полуплоскости - непрерывны)
PL> то возникает вопрос, какие усилия нужно потратить, чтобы
PL> сформулировать постановку ОЗЛП для задачи о которой шла речь? В
PL> названной задаче целевая функция - дискретная функция
PL> выбора максимального из значений, получаемых путем поэлементного
PL> сложения множеств, состав которых зависит от вектора переменных
PL> х. Требуется получить минимум данной целевой функции.
Если я правильно понял о какой задаче идет речь, то там полный перебор требует
около 600 вариантов, следовательно это лучший метод.
PL> Какие учебники читать посоветуете? IMHO поверхностного взгяда
PL> недостаточно, чтобы решить _дискретную_ задачу методами _линейного_
PL> программирования ;)
Hасколько я знаю, для любой конечной дискретной задачи можно придумать
эквивалентную задачу линейного программирования. Другой вопрос, стоит ли
извращаться, не проще ли просто перебрать, а если не проще, то стоит попробовать
метод ветвей и границ.
C уважением, Roman Kukushkin.
---
* Origin: (2:5025/37.216)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
