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

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.