| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > линейное программирование |
| Автор: Cashey 17.11.2002, 03:17 |
| Кто-нибуть может помочь с алгоритмом. Имеется двумерный массив (матрица) это набор исходных данных, далее имеется одномерный массив - это набор значений которые должны состовлять суммы вертикальных элиментов матрицы, для этого горизонтальные ряды матрицы должны буть умножены на какой-то множетель, который и нужно опредилить. Вся сложность заключается в том, что некоторые горизонтальные ряды матрицы могут составлять только определенный процент от конечного значения. Для большей ясности приведу такой пример: есть значения а 4.6.7.8.9 (первый ряд чисел - точка только разделитель разных чисел) b 2.7.5.8.4 (второй ряд чисел) с 4.6.5.6.8 (третий ряд чисел) x 56.134.104.148.114 (этому должна быть приближенно равна сумма соответствующего вертикального ряда, после умножение его на нужный множетель (каждому ряду свой), при этом доля ряда а может составлять только 10% от общей суммы, ряда b только 60%, ряда с - 30%. Требуется найти "нужный множетель" для каждого ряда чисел. Говорят для решения подобных задач созданы симплекс методы (а именно "алгоритм диеты") , но что это такое и с чем это едят я незнаю. |
| Автор: December 17.11.2002, 08:59 |
| Что это за симплекс-метод, я не знаю, но по поводу алгоритма: 1. Составить систему линейных уравнений и решить. Геморрой, но на бумаге - проще всего. 2. Перебор. Приближённый. Сначала приближённый. То есть сначала перебираешь множители 1, 5, 10, 15 и т.д. Потом, наидя минимально ошибочный вариант, танцуешь вокруг него с шагом в единицу. Так, кажется, делает MathCAD. |
| Автор: neutrino 17.11.2002, 19:30 |
| Возможно ты написал все верно, но не мог бы ты перефразировать для таких как я. P.S. Я не понимаю (вероятно это вытекает из первого предложения), куда здесь можно применить симплекс метод. А перебором такое решать - тормозить компьютер. |
| Автор: Shaman 17.11.2002, 20:28 |
| Что-то я не понимаю. Получилась обычная линейная система уравнений. Методов её решения туева хуча (как точных так и приблизительных). Что касается процентов, то такая задача будет не всегда разрешима. Скорее всего когда дискримнант матрицы будет равен 0, тогда решением будет не какой-то вектор а семейство векторов среди которых может быть найдётся нужный... |
| Автор: podval 18.11.2002, 22:51 |
| Обозначим матрицей А: 4 2 4 6 7 6 7 5 5 8 8 6 9 4 8 вектором Х: 56 134 104 148 114 вектором Y: y1 y2 y3 y4 y5 Имеем задачу линейного программирования (в матричной записи): найти Y, обращающий в минимум sum(A)*Y - Х -> min при ограничениях: 4*y1 + 6*y2 + 7*y3 + 8*y4 + 9*y5 <= 55,6 2*y1 + 7*y2 + 5*y3 + 8*y4 + 4*y5 <= 333,6 4*y1 + 6*y2 + 5*y3 + 6*y4 + 8*y5 <= 168,8 sum(A) - построчная сумма элементов <= - означает "меньше или равно" (для тех, кто не знаком с С) * - здесь поэлементное умножение (кронекеровское, нематричное) правые части ограничений - это те самые проценты от суммы элементов вектора Х (если это то, что имел в виду автор вопроса). Симплекс-методом решать или другим, дело хозяйское. Но это не просто СЛАУ. |
| Автор: Cashey 6.12.2002, 06:36 |
| Лажу все сдесь понаписали. Неужели так некто и не подскажет как в такой задаче найти подходящий множетель |
| Автор: podval 6.12.2002, 21:37 | ||
Cashey, здесь никто не обещал готовых решений. Вот вынь да положь! На то и форум, чтобы вести обсуждение, а не заключать "лажа - не лажа". Мы же пока пытаемся выяснить, в каких направлениях работать надо.
http://fmi.asf.ru/vavilov/ Изучай. Задачу о диете там тоже найдешь. |
| Автор: Cashey 11.12.2002, 07:32 | ||
Спасибо, podval, это то что доктор прописал. |