Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > линейное программирование


Автор: 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
Цитата

http://fmi.asf.ru/vavilov/

Спасибо, podval, это то что доктор прописал.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)