simple linear programming example 3 – maximize earnings [GLPK]

This example was found on linkedIn SlideShare Page 7:

Kayla works no more than 20 hours per week
during the school year. She is paid $10 an hour
for tutoring
Geometry students and $7 an hour
for babysitting
. She wants to spend at least 3
hours but no more than 8 hours a week tutoring.

Find Kayla’s maximum weekly earnings.

t = number of hours spent tutoring
b = number of hours spent babysitting

Optimisation equation: E(Earnings)
E = 10 * t + 7 * b

Subject to:
t >= 3
t <= 8 b >= 0
t + b <= 20

Also written as:
p = t
q = b
r = t + b

3 <= p <= 8
0 <= x1 < +inf

0 < q <= +inf
0 <= x2 < +inf

-inf < r <= 20
0 <= x2 < +inf

//  Philipp Siedler
//  Linear Programming
//  Real Life Example 3

#include <stdio.h>
#include <stdlib.h>
#include <glpk.h>
#include <std_lib_facilities.h>

int main(void)
{
	glp_prob *lp;
	int row_index[1 + 1000];					//Row indices of each element
	int	col_index[1 + 1000];					//column indices of each element
	double value[1 + 1000];						//numerical values of corresponding elements
	double z, x1, x2, x3;
	lp = glp_create_prob();						//creates a problem object
	glp_set_prob_name(lp, "sample");			//assigns a symbolic name to the problem object
	glp_set_obj_dir(lp, GLP_MAX);				//calls the routine glp_set_obj_dir to set the
												//omptimization direction flag,
												//where GLP_MAX means maximization

	//ROWS
	glp_add_rows(lp, 3);						//adds three rows to the problem object
	//row 1
	glp_set_row_name(lp, 1, "p");				//assigns name p to first row
	glp_set_row_bnds(lp, 1, GLP_UP, 3.0, 8.0);	//sets the type and bounds of the first row,
												//where GLP_UP means that the row has an upper bound.
												//3 <= p <= 8	
	//row 2
	glp_set_row_name(lp, 2, "q");				//assigns name q to second row
	glp_set_row_bnds(lp, 2, GLP_UP, 0.0, INFINITY);//0 < q <= +inf
	//row 3
	glp_set_row_name(lp, 3, "r");				//assigns name r to second row
	glp_set_row_bnds(lp, 3, GLP_UP, 0.0, 20.0);//-inf < r <= 20

	//COLUMNS
	glp_add_cols(lp, 2);						//adds three columns to the problem object
	//column 1
	glp_set_col_name(lp, 1, "x1");				//assigns name x1 to first column
	glp_set_col_bnds(lp, 1, GLP_LO, 0.0, 0.0);	//sets the type and bounds to the first column,
												//where GLP_LO means that the column has an lower bound
	glp_set_obj_coef(lp, 1, 10.0);				//sets the objective coefficient for thr first column
												//E = 10 * t + 7 * b
	//column 2
	glp_set_col_name(lp, 2, "x2");				//assigns name x2 to first column
	glp_set_col_bnds(lp, 2, GLP_LO, 0.0, 0.0);	//sets the type and bounds to the second column
	glp_set_obj_coef(lp, 2, 7.0);				//sets the objective coefficient for thr second column

	/*
	E = 10 * t + 7 * b
	p = t
	q = b
	r = t + b
	*/

	row_index[1] = 1, col_index[1] = 1, value[1] = 1.0;	// a[1,1] = 1.0
	row_index[2] = 1, col_index[2] = 2, value[2] = 0.0;	// a[1,2] = 0.0
	row_index[3] = 2, col_index[3] = 1, value[3] = 0.0;	// a[2,1] = 0.0
	row_index[4] = 2, col_index[4] = 2, value[4] = 1.0;	// a[2,2] = 1.0
	row_index[5] = 3, col_index[5] = 1, value[5] = 1.0;	// a[3,1] = 1.0
	row_index[6] = 3, col_index[6] = 2, value[6] = 1.0;	// a[3,2] = 1.0

	for (int i = 1; i < 7; i++) {
		cout << value[i];
		cout << ((i % 2 == 0) ? "\n" : "\t");
	}

	glp_load_matrix(lp, 6, row_index, col_index, value);	//calls the routine glp_load_matrix
															//loads information from three arrays
															//into the problem object
	glp_simplex(lp, NULL);						//calls the routine glp_simplex
												//to solve LP problem
	z = glp_get_obj_val(lp);					//obtains a computed value of the objective function
	x1 = glp_get_col_prim(lp, 1);				//obtain computed values of structural variables (columns)
	x2 = glp_get_col_prim(lp, 2);				//obtain computed values of structural variables (columns)

	printf("\nEarnings(z) = %g; tutoring(x1) = %g; babysitting(x2) = %g;\n", z, x1, x2); //writes out the optimal solution
	glp_delete_prob(lp);						//calls the routine glp_delete_prob, which frees all the memory
	keep_window_open();							//leave this line out and run program with ctrl + F5 to keep window open
												//that means you won't need std_lib_facilities.h
}
Output:
1       0
0       1
1       1
GLPK Simplex Optimizer, v4.63
3 rows, 2 columns, 4 non-zeros
*     0: obj =         -nan(ind) inf =   0.000e+00 (2)
*     2: obj =         -nan(ind) inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND

Earnings(z) = 164; tutoring(x1) = 8; babysitting(x2) = 12;
Please enter a character to exit

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.