Problème de programmation linéaire de formulation

Question

Cela peut être une question assez fondamentale pour quelqu'un qui connaît la programmation linéaire.
Dans la plupart des problèmes que j'ai vu sur LP a un peu similaire au format suivant

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

En d'autres termes, nous avons même nombre d'inconnues dans les fonctions objectifs et contraintes.

Mon problème est que j'ai une variable inconnue dans la fonction objectif et 3 inconnues dans les fonctions de contrainte.
Le problème est comme ça

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 

Comme on le voit, la fonction objective n'a qu'un seul-à-dire inconnu w1 et les fonctions de contrainte ont 3 (ou disons que 2) inconnue à savoir w1, x et y.
Quelqu'un peut-il me guider comment résoudre ce problème, en particulier en utilisant R ou MATLAB boîte à outils de programmation linéaire.

Answer 1

Votre objectif ne consiste w1 mais vous pouvez voir encore en fonction de w1,x,y, où le coefficient de w1 est 1, et les coeffs de x,y sont nuls:

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

Une fois que vous voyez ce que vous pouvez le formuler de la manière habituelle en tant que LP "standard".

Answer 2

Prasad est correct. Le nombre d'inconnues dans la fonction objectif n'a pas d'importance. Vous pouvez afficher les inconnues qui ne sont pas présentes comme ayant un coefficient nul.

Ce LP est facilement résolu en utilisant la fonction linprog de Matlab. Pour plus de détails sur linprog voir la documentation here.

% 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);