Evan Cooch
2024-Jan-29 21:28 UTC
[R] linear programming in R | limits to what it can do, or my mistake?
Question for 'experts' in LP using R (using the lpSolve package, say) --
which does not apply to me for the sort of problem I describe below.
I've run any number of LP's using lpSolve in R, but all of them to date
have objective and constraint functions that both contain the same
variables. This lets you set up a LHS and RHS matrix/vector that are
symmetrical.
But, for a problem a student posed in class, I'm stuck with how to do it
in R, if its even possible (its trivial in Maxima, Maple...even using
Solver in Excel, but I haven't been remotely successful in getting
anything to work in R).
Suppose you have a production system that at 4 sequential time steps
generate 640, 825, 580, and 925 units. At each time step, you need to
decide how many of those units need to be 'quality control' (QC) checked
in some fashion, subject to some constraints.
?--> at no point in time can the number of units in the system be >1000
?--> at the end of the production cycle, there can be no units left
?--> 'QC checking' costs money, varying as a function of the time
step
-- 35, 55, 50 and 65 for each unit, for each time step in turn.
Objective is to minimize total cost. The total cost objective function
is trivial. Let p1 = number sent out time step 1, p2 number sent out at
time step 3, and so on. So, total cost function we want to minimize is
simply
? cost=(35*p1)+(55*p2)+(50*p3)+(65*p4)
where p1+p2+p3+p4=(640+825+580+925)=2970 (i.e., all the products get
checked). The question is, what number do you send out at each time step
to minimize cost?
Where I get hung up in R is the fact that if I let t(i) be the number of
products at each time step, then
? ? t1=640,
??? t2=t1-p1+825
? ? t3=t2-p2+580
? ? t4=t3-p3+925
such that t1+t2+t3+t4=2970 (as it must), with additional constraints being
? p1<=t1, p2<=t2, p3<=t3, p4<=t4, {t1..t4}<=1000, and t4-p4=0.
There may be algebraic ways to reduce the number of functions needed to
describe the constraints, but I can't for the life of me see how I can
create a coefficient matrix (typically, the LHS) since each line of said
matrix, which corresponds to the constraints, needs to be a function of
the unknowns in the objective function -- being, p1, p2, p3 and p4.
In Maple (for example), this is trivial:
???? cost:=35*p10+55*p12+50*p14+65*p16;
cnsts:={t10=640,t12=t10-p10+825,t14=t12-p12+580,t16=t14-p14+925,t16-p16=0,p10<=t10,p12<=t12,p14<=t14,p16<=t16,t10<=1000,t12<=1000,t14<=1000,t16<=1000};
? ?? Minimize(cost,cnsts,assume={nonnegative});
which yields (correctly):
p1=640, p2=405, p3=1000, p4=925
for minimized cost of 154800.
Took only a minute to also set this up in Maxima, and using Solver in
Excel. But danged if I can suss out any way to do this in R.
Pointers to the obvious welcome.
[[alternative HTML version deleted]]
Martin Becker
2024-Jan-30 12:00 UTC
[R] linear programming in R | limits to what it can do, or my mistake?
Apart from the fact that the statement "such that t1+t2+t3+t4=2970 (as
it must)" is not correct, the LP can be implemented as follows:
library(lpSolve)
LHS <- rbind(
c(0,0,0,0, 1, 0, 0,0),
c(1,0,0,0,-1, 1, 0,0),
c(0,1,0,0, 0,-1, 1,0),
c(0,0,1,0, 0, 0,-1,1),
cbind(-diag(4),diag(4)),
c(0,0,0,0,0,1,0,0),
c(0,0,0,0,0,0,1,0),
c(0,0,0,0,0,0,0,1)
)
RHS <- c(640,825,580,925,0,0,0,0,1000,1000,1000)
DIR <-
c(rep("==",4),rep(">=",3),"=",rep("<=",3))
OBJ <- c(35,55,50,65,0,0,0,0)
lp("min",OBJ,LHS,DIR,RHS)
Best,
Martin
Am 29.01.24 um 22:28 schrieb Evan Cooch:> Question for 'experts' in LP using R (using the lpSolve package,
say) --
> which does not apply to me for the sort of problem I describe below.
> I've run any number of LP's using lpSolve in R, but all of them to
date
> have objective and constraint functions that both contain the same
> variables. This lets you set up a LHS and RHS matrix/vector that are
> symmetrical.
>
> But, for a problem a student posed in class, I'm stuck with how to do
it
> in R, if its even possible (its trivial in Maxima, Maple...even using
> Solver in Excel, but I haven't been remotely successful in getting
> anything to work in R).
>
> Suppose you have a production system that at 4 sequential time steps
> generate 640, 825, 580, and 925 units. At each time step, you need to
> decide how many of those units need to be 'quality control' (QC)
checked
> in some fashion, subject to some constraints.
>
> ?--> at no point in time can the number of units in the system be
>1000
> ?--> at the end of the production cycle, there can be no units left
> ?--> 'QC checking' costs money, varying as a function of the
time step
> -- 35, 55, 50 and 65 for each unit, for each time step in turn.
>
> Objective is to minimize total cost. The total cost objective function
> is trivial. Let p1 = number sent out time step 1, p2 number sent out at
> time step 3, and so on. So, total cost function we want to minimize is
> simply
>
> ? cost=(35*p1)+(55*p2)+(50*p3)+(65*p4)
>
> where p1+p2+p3+p4=(640+825+580+925)=2970 (i.e., all the products get
> checked). The question is, what number do you send out at each time step
> to minimize cost?
>
> Where I get hung up in R is the fact that if I let t(i) be the number of
> products at each time step, then
>
> ? ? t1=640,
> ??? t2=t1-p1+825
> ? ? t3=t2-p2+580
> ? ? t4=t3-p3+925
>
> such that t1+t2+t3+t4=2970 (as it must), with additional constraints being
>
> ? p1<=t1, p2<=t2, p3<=t3, p4<=t4, {t1..t4}<=1000, and
t4-p4=0.
>
> There may be algebraic ways to reduce the number of functions needed to
> describe the constraints, but I can't for the life of me see how I can
> create a coefficient matrix (typically, the LHS) since each line of said
> matrix, which corresponds to the constraints, needs to be a function of
> the unknowns in the objective function -- being, p1, p2, p3 and p4.
>
> In Maple (for example), this is trivial:
>
> ???? cost:=35*p10+55*p12+50*p14+65*p16;
>
cnsts:={t10=640,t12=t10-p10+825,t14=t12-p12+580,t16=t14-p14+925,t16-p16=0,p10<=t10,p12<=t12,p14<=t14,p16<=t16,t10<=1000,t12<=1000,t14<=1000,t16<=1000};
> ? ?? Minimize(cost,cnsts,assume={nonnegative});
>
> which yields (correctly):
>
> p1=640, p2=405, p3=1000, p4=925
>
> for minimized cost of 154800.
>
> Took only a minute to also set this up in Maxima, and using Solver in
> Excel. But danged if I can suss out any way to do this in R.
>
> Pointers to the obvious welcome.
> [[alternative HTML version deleted]]
>
>
--
apl. Prof. PD Dr. Martin Becker, Akad. Oberrat
Lehrstab Statistik
Quantitative Methoden
Fakult?t f?r Empirische Humanwissenschaften und Wirtschaftswissenschaft
Universit?t des Saarlandes
Campus C3 1, Raum 2.17
66123 Saarbr?cken
Deutschland