Linear Programming using GNU Octave

GNU Octave can solve linear programming problems to optimize outputs. Here is a simple two variable example of how the octave function “glpk” helps to optimize.

The problem

A company manufactures bicycles and tricycles, each of which must be processed through two machines A and B. Machine A can work for maximum 120 hours and machine B can work for maximum 180 hours. Bicycle requires machine A for 6 hours and machine B for 3 hours. Tricycle requires 4 hours of machine A and 10 hours of machine B.

Every bicycle fetches profit of 180 Rs and a tricycle fetches profit of Rs 220. Determine the number of bicycles and tricycles to be manufactured so that the profit is maximum.

Formating the problem

Bicycle hrs Tricycle hrs Max machine hrs
Machine A 6 4 120
Machine B 3 10 180

Let x and y be the number of bicycles and tricycles which fetch the maximum profit. Considering above constraints, we write following equations / inequalities:

  • Function to be maximized (this is input argument c below): fmax =  180 x + 220 y
  • Machine A constraint: 6 x +4 y leq 120
  • Machine B constraint: 3 x + 10 y leq 180
  • Non negative constraints are naturally, x geq 0 , y geq 0

The “glpk” function

“glpk” means GNU Linear Programming Kit. The format of the function is shown below:

[xopt,fopt,errnum,extra] = glpk (c,A,b,lb,ub,ctype,vartype,s,param)

Input arguments

  • c is the function to be maximized. In this case it is the relation between number of bicycles and tricycles (which fetch the maximum profit). c = [180;220]. It is a column matrix.
  • A is the matrix containing the constraints coefficients. A = [6 4;3 10]
  • b is a column array that contains right hand side of each constraint. b = [120;180] in this case.
  • lb is an array containing the lower bound on each of the variables. Default value of lb is zero. lb = [0;0] in this case.
  • ub is an array containing the upper bound on each variable. Default value is infinite. ub = []. Because there is no upper bound in this case.
  • ctype is an array of characters containing the sense of each constraint: (see script image )
    • “F” means constraint is ignored
    • “U” means inequality with upper bound (has <= sign in it)
    • “S” means equality constraint
    • “L” means inequality with lower bound (has >= sign in it)
    • “D” means inequality with both bounds
  • vartype tells whether the variable is continuous or integer. (see script image )
    • “C ” if continuous
    • “I” if integer
  • param describes various parameters which dictate structure of parameters like message level and limit to number of iterations etc. See the script image for current example case.

Output values

In this case, we are need only first two output values. When we run the script in GNU Octave, it results in values shown in the third image below. Notice that the number of bicycles are 10 and number of tricycles are 15 which fetch the total maximum profit of 5100 Rs.

  • xopt is the value of the decision variable at the optimum. (xmax or xmin)
  • fopt is the optimum value of the objective function. (fmax or fmin)
  • errnum is error code.
  • extra contains some additional information like time used to solve the problem or status of optimization etc.

Octave script

The input arguments are defined in octave language as shown below:

The image below shows how the “glpk” function finds the value and how they can be displayed.

 

The image below shows the results of the script when run on the octave prompt.

You can download the script lppExample for your study.