Формулировка задачи линейного программирования


Это может быть довольно простой вопрос для тех, кто разбирается в линейном программировании.
В большинстве задач, которые я видел на LP, несколько похожи на следующий формат

max            3x+4y  
subject to     4x-5y = -34
               3x-5y = 10      (and similar other constraints)

Другими словами, у нас одинаковое количество неизвестных в целевых функциях и ограничивающих функциях.

Моя проблема в том, что у меня есть одна неизвестная переменная в целевой функции и 3 неизвестных в функциях ограничений.
Проблема такая

Objective function:  min w1
subject to:
w1 + 0.1676x + 0.1692y >= 0.1666 
w1 - 0.1676x - 0.1692y >= -0.1666 
w1 + 0.3039x + 0.3058y >= 0.3  
w1 - 0.3039x - 0.3058y >= -0.3  
x + y = 1
x >= 0
y >= 0

Как видно, целевая функция имеет только одно неизвестное, то есть w1, а функции ограничений имеют 3 (или, скажем, 2) неизвестных, то есть w1, x и y < / strong>.
Может кто-нибудь посоветовать мне, как решить эту проблему, особенно с использованием набора инструментов линейного программирования R или MATLAB.


r matlab mathematical-optimization linear-programming
person Ikram Ullah    schedule 12.04.2011    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Ваша цель включает только w1, но вы все равно можете рассматривать ее как функцию от w1,x,y, где коэффициент w1 равен 1, а коэффициенты x,y равны нулю:

min w1*1 + x*0 + y*0

Как только вы это увидите, вы можете сформулировать его обычным образом как «стандартный» LP.

person Prasad Chalasani    schedule 12.04.2011

arrow_upward
2
arrow_downward

Прасад правильный. Количество неизвестных в целевой функции не имеет значения. Вы можете рассматривать неизвестные, которые отсутствуют, как имеющие нулевой коэффициент.

Этот LP легко решается с помощью функции linprog в Matlab. Дополнительные сведения о linprog см. В документации здесь.

% We lay out the variables as X = [w1; x; y]
c = [1; 0; 0]; % The objective is w1 = c'*X
% Construct the constraint matrix
% Inequality constraints will be written as Ain*X <= bin
%       w1      x        y
Ain = [ -1 -0.1676 -0.1692;
        -1  0.1676  0.1692;
        -1 -0.3039 -0.3058;  
        -1  0.3039  0.3058; 
      ];
bin =  [ -0.166; 0.166; -0.3; 0.3];

% Construct equality constraints Aeq*X == beq
Aeq = [ 0 1 1];
beq = 1;

%Construct lower and upper bounds l <= X <= u
l = [ -inf; 0; 0];
u = inf(3,1);

% Solve the LP using linprog
[X, optval] = linprog(c,Ain,bin,Aeq,beq,l,u);

% Extract the solution
w1 = X(1);
x  = X(2);
y  = X(3);
person codehippo    schedule 15.09.2011