Одно уравнение

Форум для обсуждения вопросов математики

Модератор: Admin

bk19
Сообщения: 1
Зарегистрирован: Вт июн 11, 2013 10:03 am

Одно уравнение

Сообщение bk19 » Вт июн 11, 2013 10:11 am

Подскажите, пожалуйста, в какой программе можно решить вот такую задачу:

Есть общее уравнение вида

x1*a1 + x2*a2 + x3*a3 + ..... + XnAn <= B

неизвестные Х - либо 0 либо 1,
коэффициенты а и B - вещественные

нужно найти решение, чтобы значение целевой функции было максимально близкое к В.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Re: Одно уравнение

Сообщение Kitonum » Ср июн 12, 2013 7:57 am

bk19 писал(а):Подскажите, пожалуйста, в какой программе можно решить вот такую задачу:

Есть общее уравнение вида

x1*a1 + x2*a2 + x3*a3 + ..... + XnAn <= B

неизвестные Х - либо 0 либо 1,
коэффициенты а и B - вещественные

нужно найти решение, чтобы значение целевой функции было максимально близкое к В.

У Вас неполная формулировка задачи! Почему не написали формулу самой целевой функции, а только ограничение на неизвестные?
Сама задача относится к классу задач с булевыми (двоичными) переменными. Т.к. множество, на котором ищется решение, конечно (это - декартово произведение {0, 1} само на себя n раз), то Ваша задача в принципе может быть решена точно обычным перебором на любом языке, например на Паскале. Конечно, этот подход проходит только в случае небольшого n (n<20), а то перебор может слишком затянуться.
Практика показывает, что применение команд для прямого решения (без программирования), имеющихся, например, в Экселе, матпакетах типа Maple и т.п. не всегда эффективно. По этому поводу можете почитать обсуждение решения похожей задачи по ссылке

http://www.mapleprimes.com/questions/12 ... Plusminus-