Решение линейной программы в случае ограничения равенства

Я задал вопрос, который можно найти здесь:
Вычисление оптимальной комбинации < бр>

И было предложено линейное программирование. Я просмотрел линейное программирование и симплексный метод. Но все примеры, с которыми я сталкивался, имеют ограничения неравенства, которые преобразуются в равенства с использованием переменных резерва. Затем симплекс-метод меняет местами основные и неосновные переменные для получения оптимального решения.

Но моя проблема:

свернуть :
x1 + x2 + ... + xn

при условии:
a1*x1 + a1*x2 + a1*x3 + ... + a1*xn = c1;
a2*x1 + a2*x2 + a2*x3 + ... + a2*xn = c2;
a3*x1 + a3*x2 + a3*x3 + ... + a3*xn = c3;

Теперь я не знаю, как я могу применить здесь симплекс-метод, так как у меня здесь нет базовых переменных.
Также я не могу просто решить линейные уравнения, так как у меня есть n переменных и 3 уравнения.
Кто-нибудь может предложить мне выход?


algorithm math linear-algebra linear-programming
person user1925405    schedule 25.06.2013    source источник
comment
Голосование за закрытие. Это не programming question, так как этот термин обычно используется в SO. Это вопрос о применении симплекс-метода для линейного программирования.   -  person High Performance Mark    schedule 25.06.2013
comment
Это был вопрос по программированию. Пожалуйста, смотрите ссылку в вопросе. Я столкнулся с этой путаницей по поводу предложенного метода, поэтому я подумал, что задам его здесь, чтобы люди могли предложить альтернативный метод программирования, если линейное программирование не должно работать.   -  person user1925405    schedule 25.06.2013

Ответы (4)


arrow_upward
5
arrow_downward

Вы можете переписать каждое из ваших уравнений в два неравенства:

a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≤ c1
a1*x1 + a1*x1 + a1*x3 + … + a1*xn ≥ c1

Это предполагает, что коэффициенты, помеченные a1, на самом деле разные; в противном случае весь ваш LP был бы очень взаимозависимым и либо тривиальным для решения, либо вообще неразрешимым. Затем вы добавляете переменные резерва, чтобы снова превратить неравенства в равенства:

a1*x1 + a1*x1 + a1*x3 + … + a1*xn + y1a = c1    y1a ≥ 0
a1*x1 + a1*x1 + a1*x3 + … + a1*xn - y1b = c1    y1b ≥ 0

Теперь эти y1a и y1b являются вашими исходными базовыми переменными, и вы можете начать поворот. Либо найти оптимальное решение, если исходное базовое решение уже допустимо, либо найти допустимое решение, если нет.

person MvG    schedule 25.06.2013
comment
Спасибо! Не могли бы вы также объяснить преобразование минимизации в максимизацию? Я думаю, вы просто отрицаете переменные в целевой функции. то есть вышеупомянутая функция должна стать максимизируемой: -x1 -x2 -x3 ... -xn. Правильно ? Если да, то как сейчас работает симплекс? Он должен выбрать небазисную переменную, для которой коэффициент в целевой функции положителен, верно? - person user1925405; 25.06.2013
comment
Или, может быть, вы используете двойственность. Но я так и не смог этого понять. Не могли бы вы объяснить, если это применимо? - person user1925405; 25.06.2013
comment
@user1925405 user1925405: Пошаговое введение в симплекс-метод выходит за рамки ответа SO, imo. Если ресурсов, доступных в Интернете, недостаточно, я предлагаю вам получить экземпляр книги Introduction to Algorithms Cormen et al. Насколько я помню, описание симплекса там было вполне понятное. Короткий ответ: переключение между максимизацией и минимизацией означает отрицание целевой функции, правильно. Если есть определенный шаг симплексного метода, который вы не понимаете, может помочь публикация нового вопроса с явными (и желательно простыми) числами. - person MvG; 25.06.2013

arrow_upward
2
arrow_downward

В учебнике

«Комбинаторная оптимизация» Кеннета Стейглица и Христоса Пападимитиу.

вы можете найти подробное, автономное описание симплексного алгоритма. Если я правильно помню, для случая заданных только ограничений равенства, но без базиса, вводится искусственный базис с дополнительными искусственными переменными с нулевой стоимостью каждая. Интуитивно это похоже на «приклеивание» единичной матрицы к одной стороне матрицы ограничений. Затем запускается симплекс-алгоритм для «вытеснения» искусственного базиса, т. е. он итерируется до тех пор, пока ни одна из искусственных переменных не перестанет содержаться в базисе, а это означает, что базис исходной формулировки найден.

person anonymous    schedule 26.06.2013

arrow_upward
1
arrow_downward

Вам не нужно делать это самостоятельно, поэтому существуют языки моделирования. Я предлагаю вам попробовать либо GLPK, либо SCIP.

У них есть собственный язык моделирования, у GLPK есть GNU MathProg, а у SCIP есть ZIMPL, так что вы можете удобно кодировать свою задачу LP. Прочитайте документацию.

Связанный с этим вопрос: это.

person Ali    schedule 25.06.2013

arrow_upward
0
arrow_downward

Линейное программирование будет работать над этой проблемой. Не описывайте ограничения с помощью двух неравенств, просто передайте их решателю, такому как GLPK. Например, вы можете написать это несколькими строками GMPL:

param k, n;
param a{1..k}{1..n};
param c{1..k};
var x{1..n}, >= 0;

minimize cost : sum{i in 1..n} x[i];
s.t. constraints{j in 1..k} : sum{i in 1..n}(a[j][i] * x[i]) = c[j];

Однако, как вы заявили здесь, ваша модель, вероятно, не имеет оптимума: без ограничений неотрицательности это всего лишь недоопределенная линейная система с неограниченным решением. Я предполагаю, что x должен оставаться неотрицательным и что ограничения немного сложнее, как в вашем связанном посте.

person Gabriel Gouvine    schedule 11.11.2014