simple linear programming example 4 – protein consumption [GLPK]

This example was found on linkedIn SlideShare Page 9:

As part of your weight training regimen, you want to
consume lean sources of protein. You want to consume
at least 300 Calories a day from at least 48
grams of protein
. One ounce of chicken provides 35 Calories
and 8.5 g of protein
. One ounce of tofu provides 20 Calories
and 2.5 g protein
. Your local supermarket charges $5 a pound
for chicken and $2.5 a pound for tofu. How much of each food
should you eat each day if you want to meet your requierments
with the lowest cost?
What is this daily cost?

c = number of lbs of chicken
t = number of lbs of tofu

optimisation equation: P(Price Paid)
P = 5 * c + 2.5 * t

subject to: (16 ounces = 1 lb)
c >= 0
t >= 0
560 * c + 320 * t >= 300 //1 lb chicken = 16 * 35 = 560 calories
//1 lb tofu = 16 * 20 = 320 calories
136 * c + 40 * t >= 48 //1 lb chicken = 16 * 8.5 = 136 g of protein
//1 lb chicken = 16 * 2.5 = 40 g of protein

Also written as:
p = 560 * c + 320 * t
q = 136 * c + 40 * t

300 <= p <= +inf
0 <= x1 < +inf

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

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

#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_MIN);				//calls the routine glp_set_obj_dir to set the
												//omptimization direction flag,
												//where GLP_MAX means maximization

	//ROWS
	glp_add_rows(lp, 2);						//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_LO, 300.0, INFINITY);	//sets the type and bounds of the first row,
												//where GLP_LO means that the row has an lower bound.
												//300 <= p <= +inf	
	//row 2
	glp_set_row_name(lp, 2, "q");				//assigns name q to second row
	glp_set_row_bnds(lp, 2, GLP_LO, 48.0, INFINITY);//48 <= q <= +inf	

	//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, 5.0);				//sets the objective coefficient for thr first column
												//P = 5 * c + 2.5 * t
	//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, 2.5);				//sets the objective coefficient for thr second column

	/*
	p = 560 * c + 320 * t
	q = 136 * c + 40 * t
	*/

	row_index[1] = 1, col_index[1] = 1, value[1] = 560.0;	// a[1,1] = 560.0
	row_index[2] = 1, col_index[2] = 2, value[2] = 320.0;	// a[1,2] = 320.0
	row_index[3] = 2, col_index[3] = 1, value[3] = 136.0;	// a[2,1] = 136.0
	row_index[4] = 2, col_index[4] = 2, value[4] = 40.0;	// a[2,2] = 40.0
	
	for (int i = 1; i < 5; i++) {
		cout << value[i];
		cout << ((i % 2 == 0) ? "\n" : "\t");
	}

	glp_load_matrix(lp, 4, 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("\nPrize(z) = %g; chicken(x1) = %g; tofu(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:
560     320
136     40
GLPK Simplex Optimizer, v4.63
2 rows, 2 columns, 4 non-zeros
      0: obj =   0.000000000e+00 inf =   3.480e+02 (2)
      2: obj =   2.678571429e+00 inf =   0.000e+00 (0)
*     3: obj =   2.443181818e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND

Prize(z) = 2.44318; chicken(x1) = 0.159091; tofu(x2) = 0.659091;
Please enter a character to exit

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

simple linear programming example 2 – pancakes and waffle recipes [GLPK]

This example was found on linkedIn SlideShare Page 5:

Pancakes
3 cups Bisquick
1 cup Milk
2 Eggs
Serves 6

Waffles
2 cups Bisquick
2 cups Milk
2 Eggs
Serves 5

You have 24 cups of Biquick, 18 cups of milk, and 20
eggs. If you want to feed as many people as possible,
how many batches of each should you make?

p = number of batches of pancakes
w = number of batches of waffles

Optimisation equation: S(Servings)
S = 6 * p + 5 * w

Subject to:
3 * p + 2 * w <= 24 cups of Bisquick
1 * p + 2 * w <= 18 cups Milk
2 * p + 2 * w <= 20 Eggs

Also written as:
p = 3 * p + 2 * w
q = 1 * p + 2 * w
r = 2 * p + 2 * w

-inf < p <= 24 0 <= x1 < +inf
-inf < q <= 18 0 <= x2 < +inf
-inf < r <= 20 0 <= x2 < +inf

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

#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, 0.0, 24.0);	//sets the type and bounds of the first row,
													//where GLP_UP means that the row has an upper bound.
													//-inf < p <= 24
	//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, 18.0);//-inf < q <= 18
	//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, 6.0);				//sets the objective coefficient for thr first column
												//S = 6 * p + 5 * w
	//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, 5.0);				//sets the objective coefficient for thr second column

	/*
	p = 3 * p + 2 * w 
	q = 1 * p + 2 * w 
	r = 2 * p + 2 * w
	*/

	row_index[1] = 1, col_index[1] = 1, value[1] = 3.0;	// a[1,1] = 100000.0
	row_index[2] = 1, col_index[2] = 2, value[2] = 2.0;	// a[1,2] = 200000.0
	row_index[3] = 2, col_index[3] = 1, value[3] = 1.0;	// a[1,2] = 200000.0
	row_index[4] = 2, col_index[4] = 2, value[4] = 2.0;	// a[2,1] = 100.0
	row_index[5] = 3, col_index[5] = 1, value[5] = 2.0;	// a[2,2] = 75.0
	row_index[6] = 3, col_index[6] = 2, value[6] = 2.0;	// a[2,2] = 75.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("\nServings(z) = %g; pancakes(x1) = %g; waffles(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:
3       2
1       2
2       2
GLPK Simplex Optimizer, v4.63
3 rows, 2 columns, 6 non-zeros
*     0: obj =  -0.000000000e+00 inf =   0.000e+00 (2)
*     2: obj =   5.400000000e+01 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND

Servings(z) = 54; pancakes(x1) = 4; waffles(x2) = 6;
Please enter a character to exit

simple linear programming example – small and large vans [GLPK]

This example was found on linkedIn SlideShare Page 3:

The West Hartford Senior Center is trying to establish a
transportation system of small and large vans. It can
spend no more than $100,000 for both sizes of vehicles
and no more than $500 per month for maintenance. The
WHSC can purchase a small van, which carries up to 7
passengers
, for $10,000 and maintain it for $100 per
month
. The large vans, which carry up to 15
passengers
, cost $20,000 each and can be maintained for
$75 per month. How many of each type of van should
they purchase if they want to maximize the number of
passengers
?

s = small van
l = large van

optimisation equation:
z = 7 * s + 15 * l

subject to:
10.000 * s + 20.000 * l <= 100.000 //initial purchase costs
100 * s + 75 * l <= 500 //monthly maintenance

also written as:
p = 10.000 * s + 20.000 * l
q = 100 * s + 75 * l

-inf < p <= 100.000 0 <= x1 < +inf
-inf < q <= 500 0 <= x2 < +inf

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

#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;
	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, 2);						//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, 0.0, 100000.0);//sets the type and bounds of the first row,
												//where GLP_UP means that the row has an upper bound.
												//-inf < p <= 100
	//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, 500.0);//-inf < q <= 600


	//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, 7.0);				//sets the objective coefficient for thr first column
												//z = 10 * x1 + 6 * x2 + 4 * x3
	//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, 15.0);				//sets the objective coefficient for thr second column
	
	/*
	p = 10.000 * s + 20.000 * l
	q = 100 * s + 75 * l
	*/

	row_index[1] = 1, col_index[1] = 1, value[1] = 10000.0;	// a[1,1] = 100000.0
	row_index[2] = 1, col_index[2] = 2, value[2] = 20000.0;	// a[1,2] = 200000.0
	row_index[3] = 2, col_index[3] = 1, value[3] = 100.0;	// a[2,1] = 100.0
	row_index[4] = 2, col_index[4] = 2, value[4] = 75.0;	// a[2,2] = 75.0

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

	glp_load_matrix(lp, 4, 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("\nz = %g; x1 = %g; 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:
10000   20000
100     75
GLPK Simplex Optimizer, v4.63
2 rows, 2 columns, 4 non-zeros
*     0: obj =  -0.000000000e+00 inf =   0.000e+00 (2)
*     1: obj =   7.500000000e+01 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND

z = 75; x1 = 0; x2 = 5;
Please enter a character to exit