A Computational Approach to Essential and Nonessential Objective
Functions in Linear Multicriteria Optimization
Agnieszka B. Malinowska
Faculty of Computer Science
Technical University of Bialystok
15-351 Bialystok, Poland
abmalina@pb.bialystok.pl
Delfim F. M. Torres
Department of Mathematics
University of Aveiro
3810-193 Aveiro, Portugal
delfim@mat.ua.pt
Last Change: 03 December 2008
This work was initiated while the first author was visiting the Department of Mathematics of the University of Aveiro, Portugal,
from June 5 to June 12, 2006, and then continued during two more visits of the first author to the University of Aveiro: January 4
to January 18, 2007; and from May 1 to May 10, 2007.
The financial support and the good working conditions provided by the R&D Centre for "Research on Optimization and Control" of the
Department of Mathematics of the University of Aveiro is here acknowledged.
The theory behind this Maple package can be found in the following reference and references therein:
Main Reference
[1] Agnieszka B. Malinowska and Delfim F. M. Torres,
Computational Approach to Essential and Nonessential
Objective Functions in Linear Multicriteria Optimization,
J. Optim. Theory Appl. (2008) 139: 577--590.
[DOI: 10.1007/s10957-008-9397-z]
| > |
################################################################## |
| > |
# returns true if F[-1] is nonessential;
# returns false if we can not conclude nothing from GL method |
| > |
################################################################## |
| > |
local c, f, v, LV, lc, SolSet, SS, i; |
| > |
v:= select(has,exp+abm,var); |
| > |
f := o -> if type(o,numeric) then o else 0 fi: |
| > |
v := (exp,n) -> Vector([seq(f(c(x||i,exp)),i=1..n)]): |
| > |
LV := [seq(LinearAlgebra[VectorScalarMultiply](v(F[i],NumVar),alpha||i),i=1..nops(F)-1)]; |
| > |
lc := LinearAlgebra[VectorAdd](lc,i): |
| > |
SolSet := solve({seq(lc[i]=c(x||i,F[-1]),i=1..NumVar)});
if SolSet = NULL then
return(false);
else |
| > |
SS := {seq(simplex[maximize](alpha||i,SolSet,NONNEGATIVE),i=1..nops(F)-1)}; |
| > |
glm([x1-x2,3*x1+x2,x2],2); |
 |
(1) |
| > |
glm([x1+3*x2,3*x1,2*x1+x2,-3*x1-x2],2); |
 |
(2) |
| > |
glm([x1-3*x2-x3,2*x2+3*x3,2*x1-4*x2+x3],3); |
 |
(3) |
| > |
glm([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],2); |
 |
(4) |
| > |
glm([x1+x2+x3,-x1+x2+x3,x1+x2],3); |
 |
(5) |
 |
(6) |
| > |
of := add(v||i,i=1..nops(F)); |
| > |
const := seq(-F[i]+v||i=0,i=1..nops(F));
const := [const,seq(v||i>=0,i=1..nops(F))]; |
| > |
S := simplex[maximize](of,const); |
| > |
return(not(evalb(subs(S,of)=0))): |
| > |
step1([x1+x2+x3, -x1+x2+x3, x1+x2]); |
 |
(7) |
| > |
step1([x1+3*x2, 3*x1, -3*x1-x2, 2*x1+x2]); |
 |
(8) |
| > |
step1([x1+3*x2, 3*x1, 2*x1+x2, -3*x1-x2]); |
 |
(9) |
| > |
step1([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3]); |
 |
(10) |
| > |
step1([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4]); |
 |
(11) |
| > |
step2 := F -> step1(F[1..-2]): |
| > |
step2([x1+3*x2, 3*x1, -3*x1-x2, 2*x1+x2]); |
 |
(12) |
| > |
step2([x1+3*x2, 3*x1, 2*x1+x2, -3*x1-x2]); |
 |
(13) |
| > |
step2([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3]); |
 |
(14) |
| > |
step2([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4]); |
 |
(15) |
| > |
step3 := proc(NumVar,X) |
| > |
local LHS, RHS, SC1, SC2, SC3, SC, SS3, i, a, epsilon, mylhs, myrhs;
epsilon := 0.001;
mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
LHS := [seq(mylhs(i),i=X)]; |
| > |
RHS := [seq(myrhs(i),i=X)]; |
| > |
SC1 := {seq(LHS[i]+a+v||i = RHS[i],i=1..nops(LHS))}; |
| > |
SC2 := {seq(v||i >= 0,i=1..nops(LHS)), a>=0}; |
| > |
SC3 := {seq(x||i>=0.001,i=1..NumVar)}; |
| > |
SC := SC1 union SC2 union SC3; |
| > |
SS3 := simplex[maximize](a,SC); |
| > |
assign(select(has,SS3,a)); |
| > |
if a = 0 then return(false) else return(true) fi; |
| > |
step3(3,{x1 <= 1, x2 <= 1}); |
 |
(16) |
| > |
step3(2,{x1+x2<=1,-x1-x2<=-1}); |
 |
(17) |
| > |
step3(3,{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2}); |
 |
(18) |
| > |
step3(2,{x1+x2<=1,-x1-x2<=-1}); |
 |
(19) |
| > |
################################################################### |
| > |
# procedure step4 does not use the last objective function F[-1] |
| > |
# procedure matrixA is used in steps 4 and 7 |
| > |
################################################################### |
| > |
matrixA := proc(X,NumVar) |
| > |
local c, LHS, row, mylhs; |
| > |
mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
c := (var,exp) -> if evalb({select(has,exp,var)} = {}) then 0 else select(has,exp,var)/var fi: |
| > |
LHS := [seq(mylhs(i)+abm,i=X)]; |
| > |
row := (exp,NumVar) -> map(c,[seq(x||i,i=1..NumVar)],exp): |
| > |
return(Matrix(map(row,LHS,NumVar))); |
| > |
############################### |
| > |
Proposition4dot12 := proc(F,X,LE) |
| > |
local SE, v, ETS, solW, SS, SV; |
| > |
SE := SE, add(SV[i]*w||i,i=1..nops(SV)); |
| > |
ETS := seq(SE[1]=i,i=SE[2..-1]), add(w||i,i=1..nops(SV))=1; |
| > |
solW := solve({ETS, add(w||i,i=1..nops(SV))=1}) union {seq(w||i>=0.00001,i=1..nops(SV))}; |
| > |
SS := {seq(simplex[maximize](w||i,solW),i=1..nops(SV))}; |
| > |
return(not(remove(i->i={},SS) = {})); |
| > |
step4 := proc(F,X,NumVar) |
| > |
local NX,NNumVar,b,A,rnk,dif,LP,zero,efficient,v,admissible,
vs,AM,sol,of,cstEps,cst,SC,p,myrhs,mylhs,LE, tv, val;
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi:
mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
tv := (x,s) -> myrhs(op(select(has,s,x))): |
| > |
b := X -> Vector([seq(myrhs(i),i=X)]): |
| > |
NX := {seq(mylhs(X[i])+x||(NumVar+i)=myrhs(X[i]),i=1..nops(X))}; |
| > |
NNumVar := NumVar+nops(X); |
| > |
A := matrixA(NX,NNumVar); |
| > |
rnk := LinearAlgebra[Rank](A); |
| > |
LP := combinat[choose]([seq(x||i,i=1..NNumVar)],dif); |
| > |
zero := L -> {seq(i=0,i=L)}: |
| > |
v := Vector([seq(x||i,i=1..NNumVar)]); |
| > |
admissible := sc -> not(member(false,{seq(evalb(myrhs(i)>=0),i=sc)})):
LE := NULL; |
| > |
for p in LP while efficient do |
| > |
vs := subs({seq(i=0,i=p)},v); |
| > |
AM := LinearAlgebra[MatrixVectorMultiply](A,vs); |
| > |
sol := solve({seq(AM[i]=b(NX)[i],i=1..nops(NX))});
if not(sol = NULL) and admissible(sol) then
sol := sol union zero(p): |
| > |
of := add(epsilon||i,i=1..nops(F)-1); |
| > |
cstEps := seq(epsilon||i>=0,i=1..nops(F)-1); |
| > |
cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1); |
| > |
SC := {cst} union {cstEps} union NX; |
| > |
efficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)=0);
if efficient then
val := [seq(tv(x||i, sol),i=1..NumVar)];
if not(member(false,map(i->type(i,numeric),val))) then
LE := LE, {seq(x||i=val[i],i=1..NumVar)};
fi;
fi;
fi: |
| > |
od;
if not(efficient) then |
| > |
return(efficient);
else
Proposition4dot12(F[1..-2],X,{LE});
fi: |
| > |
step4([x1+3*x2, 2*x1+x2],{x1+x2<=1,-x1-x2<=-1},2); |
 |
(20) |
| > |
step4([x1+3*x2, 2*x1+x2, 3*x1, -3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2); |
 |
(21) |
| > |
step4([-x1-2*x2+2*x3, 2*x1+3*x2,x1],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2},3); |
 |
(22) |
| > |
step4([x2,-x2],{-x1<=-1,x1<=1,x2<=1},2); |
 |
(23) |
| > |
step4([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2); |
 |
(24) |
| > |
step4([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2); |
 |
(25) |
| > |
step4([-x1-2*x2+2*x3, 2*x1+3*x2,-x1-x2-2*x3],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2},3); |
 |
(26) |
| > |
########################################################## |
| > |
# We only use the last objective function, that is F[-1] |
| > |
# We use an auxiliar procedure vert that receives: |
| > |
# - Sol (one solution given by simplex method); |
| > |
# - of (objective function); |
| > |
# - X = set of constraints. |
| > |
########################################################## |
| > |
local v,S,LFV,LS,i,tv,Min,Max,LL,LV,gaa,ga,VFV,freeVar,Sub,LSub,s,delFreeVar,varSol,varOF1,varOF,VerifySol,aux,NX, mylhs, myrhs;
mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
v := subs(Sol,of);
varOF1 := t -> op(select(i->not(type(i,numeric)),[op(t)])):
varOF := of -> map(varOF1,{op(of)}): |
| > |
S := solve(of = v,varOF(of));
freeVar := SS -> {seq(mylhs(i),i=select(i->mylhs(i)=myrhs(i),SS))}:
varSol := E -> {seq(mylhs(i),i=E)}: |
| > |
LFV := freeVar(S) union (varSol(Sol) minus varOF(of)); |
| > |
tv := (x,s) -> myrhs(op(select(has,s,x))): |
| > |
Min := (x,X) -> simplex[minimize](x,X union S,NONNEGATIVE): |
| > |
Max := (x,X) -> simplex[maximize](x,X union S,NONNEGATIVE): |
| > |
LL := [seq([tv(x,Min(x,X)),tv(x,Max(x,X))],x=LFV)]; |
| > |
LV := n -> [seq(i[j],j=1..n)]: |
| > |
gaa := (n,m,L) -> if m=n then seq(LV(m),i[m]=L[m]) else seq(gaa(n,m+1,L),i[m]=L[m]) fi: |
| > |
ga := L -> gaa(nops(L),1,L): |
| > |
Sub := (C1,C2) -> seq({seq(C2[j]=i[j],j=1..nops(i))},i=C1): |
| > |
LSub := Sub(VFV,LFV);
delFreeVar := SS -> SS minus {seq(i,i=select(i->mylhs(i)=myrhs(i),SS))}:
NX := X union {seq(i>=0,i=varSol(Sol))}:
VerifySol := PS -> not(member(false,{seq(evalb(subs(PS,i)),i=NX)})):
aux := {seq(subs(s,delFreeVar(S)) union s,s={LSub})}: |
| > |
return(select(VerifySol,aux)); |
| > |
vert({x1 = 1, x2 = 0},x1+x2,{x1+x2>=1,-x1-x2>=-1}); |
 |
(27) |
| > |
vert({x1 = 0, x2 = 1},x1+x2,{x1+x2>=1,-x1-x2>=-1}); |
 |
(28) |
| > |
simplex[maximize](x1+x2,{x1<=1,x2<=1,x3<=1},NONNEGATIVE); |
 |
(29) |
| > |
vert({x1 = 1, x2 = 1, x3 = 0},x1+x2,{x1<=1,x2<=1,x3<=1}); |
 |
(30) |
| > |
simplex[maximize](x1+x2+x3,{x1+x2+x3<=1,-x1-x2-x3<=-1},NONNEGATIVE); |
 |
(31) |
| > |
vert({x1 = 1, x2 = 0, x3 = 0},x1+x2+x3,{x1+x2+x3<=1,-x1-x2-x3<=-1}); |
 |
(32) |
| > |
simplex[maximize](x1+x2,{x1<=1,x2<=1},NONNEGATIVE); |
 |
(33) |
| > |
vert({x1 = 1, x2 = 1},x1+x2,{x1<=1,x2<=1}); |
 |
(34) |
| > |
##################################### |
| > |
SolSM := simplex[maximize](F[-1],X,NONNEGATIVE); |
| > |
return(vert(SolSM,F[-1],X)); |
| > |
step5([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1}); |
 |
(35) |
| > |
local STEP5, of, cstEps, notEfficient, sol, cst, SC; |
| > |
of := add(epsilon||i,i=1..nops(F)-1); |
| > |
cstEps := seq(epsilon||i>=0,i=1..nops(F)-1); |
| > |
for sol in STEP5 while notEfficient do |
| > |
cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1): |
| > |
SC := {cst} union {cstEps} union X: |
| > |
subs(simplex[maximize](of,SC,NONNEGATIVE),of); |
| > |
notEfficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)<>0); |
| > |
return(not(notEfficient)); |
| > |
step6([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1}); |
 |
(36) |
| > |
step6([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10}); |
 |
(37) |
| > |
step6([x1+x2,x1,-x1-x2],{x1<=1,x2<=1}); |
 |
(38) |
| > |
step6([x1+2*x2-x3+3*x4+2*x5+x7,x2+x3+2*x4+3*x5+x6,x1+x3-x4-x6-x7],{x1+2*x2+x3+x4+2*x5+x6+2*x7<=16,-2*x1-x2+x4+2*x5+x7<=16,-x1+x3+2*x5-2*x7<=16,x2+2*x3-x4+x5-2*x6-x7<=1}); |
 |
(39) |
| > |
step7a := proc(F,X,NumVar) |
| > |
local b,A,rnk,dif,LP,zero,efficient,v,admissible,vs,AM,sol,of,cstEps,cst,SC,p,LE,myrhs;
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
b := X -> Vector([seq(myrhs(i),i=X)]): |
| > |
A := matrixA(X,NumVar); |
| > |
rnk := LinearAlgebra[Rank](A); |
| > |
LP := combinat[choose]([seq(x||i,i=1..NumVar)],dif); |
| > |
zero := L -> {seq(i=0,i=L)}: |
| > |
v := Vector([seq(x||i,i=1..NumVar)]); |
| > |
admissible := sc -> not(member(false,{seq(evalb(myrhs(i)>=0),i=sc)})): |
| > |
vs := subs({seq(i=0,i=p)},v); |
| > |
AM := LinearAlgebra[MatrixVectorMultiply](A,vs); |
| > |
sol := solve({seq(AM[i]=b(X)[i],i=1..nops(X))});
if not(sol = NULL) and admissible(sol) then
sol := sol union zero(p): |
| > |
of := add(epsilon||i,i=1..nops(F)-1); |
| > |
cstEps := seq(epsilon||i>=0,i=1..nops(F)-1); |
| > |
cst := seq(F[i]-epsilon||i=subs(sol,F[i]),i=1..nops(F)-1); |
| > |
SC := {cst} union {cstEps} union X; |
| > |
efficient := evalb(subs(simplex[maximize](of,SC,NONNEGATIVE),of)=0);
if efficient then LE := LE, sol; fi:
fi: |
| > |
############################################################## |
| > |
# In step7b we change X |
| > |
# Note: All inequalities must be given in the form Ax <= b |
| > |
############################################################## |
| > |
step7b := proc(F,X,NumVar) |
| > |
local TX, SEV, good, sel, mylhs, myrhs;
mylhs := E -> if type(lhs(E),numeric) then rhs(E) else lhs(E) fi:
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
TX := {seq(mylhs(X[i])+x||(NumVar+i)=myrhs(X[i]),i=1..nops(X))}; |
| > |
SEV := step7a(F,TX,NumVar+nops(X)); |
| > |
good := (v,nv) -> member(v,{seq(x||i,i=1..nv)}): |
| > |
sel := (es,NumVar) -> select(e->good(mylhs(e),NumVar),es): |
| > |
return(map(sel,SEV,NumVar)); |
| > |
############################### |
| > |
step7 := proc(F,X,NumVar) |
| > |
local C, kernel, S7, tv, five, SD, basis, IBK, myrhs;
myrhs := E -> if type(rhs(E),numeric) then rhs(E) else lhs(E) fi: |
| > |
C := matrixA([seq(i=0,i=F[1..-2])],NumVar); |
| > |
kernel := LinearAlgebra[NullSpace](C); |
| > |
printf("Objective function %a is nonessential from step 7\n",F[-1]); |
| > |
S7 := step7b(F,X,NumVar); |
| > |
tv := (x,S) -> myrhs(op(select(has,S,x))): |
| > |
five := (S1,S2,NumVar) -> Vector([seq(tv(x||i,S2)-tv(x||i,S1),i=1..NumVar)]): |
| > |
SD := [seq(five(S7[1],S7[i],NumVar),i=2..nops(S7))]; |
| > |
basis := LinearAlgebra[Basis](SD); |
| > |
IBK := LinearAlgebra[IntersectionBasis]([basis,kernel]);
if IBK = {} then
printf("Objective function %a is nonessential from step 7\n",F[-1]);
else
printf("X_E^%a C X_E^%a from step 7\n",nops(F),nops(F)-1);
fi:
fi: |
| > |
step7([x2,x1],{-x1<=-1,x1<=1,x2<=1},2); |
| Objective function x1 is nonessential from step 7 |
|
| > |
step7([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1},3); |
| Objective function x1+x2 is nonessential from step 7 |
|
| > |
step7([x2,-x2,x1],{x1<=1,x2<=1},2); |
| X_E^3 C X_E^2 from step 7 |
|
| > |
####################################### |
| > |
# mm stands for Malinowska Method |
| > |
####################################### |
| > |
printf("Objective function %a is essential from step 6\n",F[-1]); |
| > |
printf("Objective function %a is nonessential from step 2\n",F[-1]); |
| > |
if step3(NumVar,X) then |
| > |
printf("Objective function %a is essential from step 3\n",F[-1]); |
| > |
if step4(F,X,NumVar) then |
| > |
printf("Objective function %a is nonessential from step 4\n",F[-1]); |
| > |
printf("Objective function %a is essential from step 4
and X_E^%a C X_E^%a\n",F[-1],nops(F)-1,nops(F)); |
| > |
mm([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1},3); |
| Objective function x1+x2 is nonessential from step 7 |
|
| > |
mm([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],{},2); |
| Objective function 2*x1+x2 is nonessential from step 2 |
|
| > |
mm([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1<=1,x2<=1},2); |
| Objective function -3*x1-x2 is essential from step 3 |
|
| > |
mm([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1},2); |
| Objective function -3*x1-x2 is nonessential from step 4 |
|
| > |
mm([x1-x2,x2,-2*x1+x2],{x1<=5,x1+x2<=10},2); |
| Objective function -2*x1+x2 is essential from step 3 |
|
| > |
mm([x1-x2,3*x1+x2,x2],{x1=5,x1+x2<=10},2); |
| Objective function x2 is nonessential from step 7 |
|
| > |
mm([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10},2); |
| Objective function x2 is essential from step 6 |
|
| > |
nonessential := proc(F,X)
local NumVar, y, cs;
cs := x -> [op(x)][-1]:
y := sort(map(cs,remove(i->type(i,numeric),map(i->op(i),[seq(op(i),i=F), seq(op(i),i=X)]))))[-1];
for NumVar from 1 by 1 while not(evalb(x||NumVar = y) or evalb(-x||NumVar = y)) do od; |
| > |
printf("Objective function %a is nonessential from GL method\n",F[-1]); |
| > |
nonessential([x1+x2+x3,-x1+x2+x3,x1+x2],{x1<=1,x2<=1,x3<=1}); |
| Objective function x1+x2 is nonessential from step 7 |
|
| > |
nonessential([x1+3*x2,3*x1,-3*x1-x2,2*x1+x2],{x1+x2<=1}); |
| Objective function 2*x1+x2 is nonessential from GL method |
|
| > |
nonessential([x1+3*x2,3*x1,-3*x1-x2],{x1+x2<=1}); |
| Objective function -3*x1-x2 is essential from step 3 |
|
| > |
nonessential([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1<=1,x2<=1}); |
| Objective function -3*x1-x2 is essential from step 3 |
|
| > |
nonessential([x1+3*x2,2*x1+x2,3*x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function -3*x1-x2 is nonessential from step 4 |
|
| > |
nonessential([x1+3*x2,2*x1+x2,3*x1],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function 3*x1 is nonessential from step 7 |
|
| > |
nonessential([x1+3*x2,2*x1+x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function 2*x1+x2 is essential from step 6 |
|
| > |
nonessential([2*x1+x2,x1+3*x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function x1+3*x2 is essential from step 6 |
|
| > |
nonessential([x1-x2,x2,-2*x1+x2],{x1<=5,x1+x2<=10}); |
| Objective function -2*x1+x2 is essential from step 3 |
|
| > |
nonessential([x1-x2,3*x1+x2,x2],{x1=5,x1+x2<=10}); |
| Objective function x2 is nonessential from step 7 |
|
| > |
nonessential([x1-x2,3*x1+x2,x2],{x1<=5,x1+x2<=10}); |
| Objective function x2 is essential from step 6 |
|
| > |
st:= time(): nonessential([x1,x1+x2+x3],{x1<=1,x2<=1,x3<=1}); printf("%a seconds\n",time() - st); |
| X_E^2 C X_E^1 from step 7 |
|
| > |
st:= time(): nonessential([x1+x2+x3+x4+x5,-x1+x2+x3+x4+x5,-x1-x2+x3+x4+x5,x1+x2],{x1<=1,x2<=1,x3<=1,x4<=1,x5<=1}); printf("%a seconds\n",time() - st); |
| Objective function x1+x2 is nonessential from step 7 |
|
| > |
nonessential([x2,x3,x1+x3],{x1<=1,x2<=1,x3<=1}); |
| X_E^3 C X_E^2 from step 7 |
|
| > |
nonessential([x2,x3],{x1<=1,x2<=1,x3<=1}); |
| X_E^2 C X_E^1 from step 7 |
|
| > |
nonessential([x1+x2+x3,x1+x2-x3,x3],{x1<=1,x2<=1,x3<=1}); |
| Objective function x3 is nonessential from step 7 |
|
| > |
nonessential([x2,x3,x2+3*x3],{x1<=1,x2<=1,x3<=1}); |
| Objective function x2+3*x3 is nonessential from GL method |
|
| > |
nonessential([-x1-2*x2+2*x3,2*x1+3*x2],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2}); |
| Objective function 2*x1+3*x2 is essential from step 6 |
|
| > |
nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function -3*x1-x2 is essential from step 4 |
|
| > |
nonessential([x2,4*x1+x2,-x1+4*x2],{x1+4*x2<=24,-x1-x2<=6,-x2<=-1,3*x1+2*x2<=32}); |
| Objective function -x1+4*x2 is nonessential from step 7 |
|
| > |
nonessential([x2,x1],{-x1<=-1,x1<=1,x2<=1}); |
| Objective function x1 is nonessential from step 7 |
|
| > |
nonessential([x2,-x2],{-x1<=-1,x1<=1,x2<=1}); |
| Objective function -x2 is essential from step 4 |
|
| > |
nonessential([-x2,x2],{-x1<=-1,x1<=1,x2<=1},2); |
| Objective function x2 is essential from step 4 |
|
| > |
nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function -3*x1-x2 is essential from step 4 |
|
| > |
nonessential([-x1-2*x2+2*x3,2*x1+3*x2,x1],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2}); |
| X_E^3 C X_E^2 from step 7 |
|
| > |
nonessential([-x1-2*x2+2*x3,2*x1+3*x2,-x1-x2-2*x3],{x2+x3<=2,-x2-x3<=-2,x1+x2+x3<=3,-x1-x2-x3<=-2,x1+x2<=2}); |
| Objective function -x1-x2-2*x3 is essential from step 4 |
|
| > |
st:= time(): nonessential([x1+2*x2-x3+3*x4+2*x5+x7,x2+x3+2*x4+3*x5+x6,x1+x3-x4-x6-x7],{x1+2*x2+x3+x4+2*x5+x6+2*x7<=16,-2*x1-x2+x4+2*x5+x7<=16,-x1+x3+2*x5-2*x7<=16,x2+2*x3-x4+x5-2*x6-x7<=1}); printf("%a seconds\n",time() - st);# Zeleny p.244 |
| Objective function x1+x3-x4-x6-x7 is essential from step 6 |
|
| > |
st:= time(): nonessential([x1+3*x2-x3,4*x1+x2+2*x3, -x1+x2+4*x3],{x1+x2+x3<=3,2*x1+2*x2+x3<=4,x1-x2<=0}); printf("%a seconds\n",time() - st);# Zeleny p.273 |
| Objective function -x1+x2+4*x3 is essential from step 6 |
|
| > |
st:= time(): nonessential([3*x1+x2+x3,x1-x2+2*x3, x1+x2],{4*x1+2*x2+3*x3<=10,x1+4*x2+2*x3<=8,x3<=5}); printf("%a seconds\n",time() - st);# Zeleny p.277 |
| Objective function x1+x2 is essential from step 6 |
|
| > |
st:= time(): nonessential([-x3-x4,-x5-x6,-x4-x6],{x1+3*x2<=24,3*x1+x2<=24,x1+4*x2+x3-x4<=40, -x1+4*x2-x3+x4<=-40,4*x1+x2+x5-x6<=40,-4*x1-x2-x5+x6<=-40}); printf("%a seconds\n",time() - st);# Zeleny p.273 |
| X_E^3 C X_E^2 from step 7 |
|
| > |
nonessential([x1+x2,x1,-3*x1-x2],{x1+x2<=1,-x1-x2<=-1}); |
| Objective function -3*x1-x2 is essential from step 4 |
|
| > |
st:= time(): nonessential([x1+2*x2+3*x3+x4,x2+3*x3+4*x4,-4*x1+2*x2+6*x3,2*x1+x2-x3,10*x1+11*x2+7*x3+6*x4],
{}); printf("%a seconds\n",time() - st); |
| Objective function 10*x1+11*x2+7*x3+6*x4 is nonessential from GL method |
|
| > |
st:= time(): nonessential([x1+4*x2-x3+2*x4-3*x5,2*x1-x3-4*x4+x5,-4*x1-8*x2+3*x3+5*x5,-7*x1-4*x2+4*x3+10*x4],
{}); printf("%a seconds\n",time() - st); |
| Objective function -7*x1-4*x2+4*x3+10*x4 is nonessential from GL method |
|
| > |
nonessential([x1+x2,x1+x2+x3,-3*x1-3*x2-x3],{x1+x2+x3 <= 1}); |
| Objective function -3*x1-3*x2-x3 is essential from step 3 |
|
Legal Notice: The copyright for this application is owned by the authors. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.
