2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Аглоритмы, минимизация функционала на множестве N_0
Сообщение31.12.2016, 14:30 


31/12/16
1
Добрый день.
Возникла необходимость запрограммировать следующую задачу.
Пусть $A$ -- некоторая "большая" матрица (примерно 30000 строк и 10 столбцов). $b$ -- свободный член. $A$ и $b$ состоят из целых неотрицательных чисел.
Дан функционал $F(x) = i$, где $i$ -- индекс последнего ненулевого элемента вектора $x = (x_1, x_2, \dots, x_n)$.
Нужно найти $\underset{Ax = b, \,x \in \mathbb{N}^n}{\min}{F(x)}$. Не обязательно даже точное решение задачи, подойдет и просто маленькое значение функционала (определение "маленького значения" не могу дать, малость определяется исходя из начальной задачи).
Думаю, это нечто близкое задаче линейного программирования, существуют обобщения на целочисленные вектора. Но в ЗЛП минимизируется функционал $c^Tx$. Пытался заменять свой функционал на подобный, но ничего умнее, чем взять $c = (1^\alpha, 2^\alpha, \dots, n^\alpha)$, решать сотни ЗЛП и смотреть на $F(x)$ не придумал.
Возможно, существует более действенный метод минимизации?
Заранее благодарю.

 Профиль  
                  
 
 Re: Аглоритмы, минимизация функционала на множестве N_0
Сообщение31.12.2016, 16:28 


17/10/08

1313
Задача подозрительная: 30000 ограничений в виде равенств, и всего 10 переменных, к тому же, целочисленных... Может наоборот, 30000 переменных и 10 ограничений?

В любом случае, формально, задача может быть линеаризована с помощью дополнительных целочисленных переменных. Пусть $y_i$ -псевдобулева переменная, для которой выполняется условие
$M y_i\ge x_i$
Здесь $M$ - большое целое число. Т.е., если $x_i$ больше нуля, то $y_i$ - тоже будет больше нуля.
Получаем задачу
$z \rightarrow min$
при условиях $iy_i\ge z$ (ну, и изначальные ограничения не забываем)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group