Session 2: Formulating a Simple Product-Mix Model
In this session you will be introduced to the formulation of linear programming
models through a simple product-mix problem called Better Bread Bakery.
Formulating Linear Programming Models
The purpose of this session is to introduce to you the basic concepts of:
- Decision variables
- Objective function
- Constraints
You need to identify these concepts when formulating linear programming models.
The first step when formulating a model is to identify and give names to the
decision variables. Decision variables are the elements of the model
that the decision maker controls and those values determine the solution of the model.
The next step is to determine the objective function in terms of the decision variables.
The objective function is where you specify the goal you are trying to achieve. The
goal can either be to maximize or to minimize the value of the objective function.
We sometimes use the phrase that we want to optimize the model. This means we want to
find the values for the decision variables which gives either the maximum or the minimum
value of the objective function. In many cases, the objective function has a monetary
value, for example to maximize profit or minimize cost, although this is not always the
case.
Constraints are the real world limitations on the decision variables. A constraint
restricts or constrains the possible values which the variable can take. An example of
a constraint could be, for example, that certain resources, such as machine capacity or
manpower, are limited.
Problem Description: A Simple Product-Mix Model
The Better Bread Bakery is famous for its breads. They make two
kinds: "Sunshine", a white bread and "Moonlight",
a large dark bread.
The market for the famous breads is endless. Every Sunshine loaf sold
brings a profit of $0.05 and each loaf of Moonlight bread brings a profit
of $0.08. There is a fixed cost of running the bakery of $4000 per month,
regardless of the amount of bread baked.
The bakery is divided into two departments: baking and mixing, with limited
capacity in both departments.
In the baking department there are ten big ovens, each with a capacity
of 140 baking sheets per day. It is possible to put ten loaves of Sunshine
on each of these baking sheets, or five of the larger Moonlight breads.
You can make any combination of the two breads on the baking sheets.
Just keep in mind that each Moonlight loaf takes twice the space of a
Sunshine loaf.
The mixing department can mix up to 8000 loaves of Sunshine bread per
day and 5000 loaves of Moonlight bread. There are two separate automatic
mixers so there is no conflict between making the two kinds of dough.
Since the market for both types of breads is unlimited, the management
of BBB has decided to find the best product mix. The question is
how many loaves of each type of bread should be baked each day to produce
the highest profit, given the physical limitations of the bakery.
We will now show you how to identify the decision variables, the objective
function and the constraints for this model and then enter the formulation
in MPL.
Formulating the Model
Identify the Decision Variables
For our bakery, the decision variables correspond to the numbers of
loaves of each type made daily. To make the formulation easier to read,
it is a good idea to assign the decision variables names, which allow you
to identify what they represent in the real world. Use two decision variables,
named Sun and Moon, and agree that they have the following
meanings:
Sun = The number of loaves of Sunshine bread produced per day
Moon = The number of loaves of Moonlight bread produced per day
Now you want to determine the values for these two decision variables in
order to maximize the bakery's profit.
Identify the Objective Function
In our example, the goal is to maximize the daily profit. We make a
profit of $0.05 on each Sunshine loaf, so the total daily production of
Sunshine bread yields $0.05 multiplied by the value of the Sun variable
for profit.
For the Moonlight production, the corresponding yield is $0.08 multiplied
by the value of the Moon variable. We call the values $0.05 and
$0.08 the coefficients for the corresponding decision variables
in the objective function. To get the total contribution towards profit
in a day, we add the contributions from the two bread types. From that,
we subtract the fixed cost of $4000 divided by 30 days in a month, to obtain
the net daily profit. This leads to the following quantity we want to maximize:
We have now defined the objective function for this particular problem. The
solver uses the objective function as a criteria to determine which solution is
optimal.
Identify the Constraints
The first constraint in the baking department is complicated since
there is an interaction between the bread types. It is possible to put either
ten Sunshine breads or five Moonlight breads on each baking
sheet. It is also possible to use any combination of the two. The expression
1/10 Sun + 1/5 Moon gives us the total usage of baking sheets.
If you measure the capacity of each oven as the number of baking sheets
which it can handle per day (10 x 140), you can express the constraint
as:
1/10 Sun + 1/5 Moon <= 10 x 140
We express the constraints which were given by the mixing department
like this:
Sun <= 8000
Moon <= 5000
Summing up the Formulation
We have now defined the objective function and all of the constraints.
This is the formulation of the linear programming problem
as shown below:
Subject to
Once you have your formulation, most of the work is done. As you are
about to see, MPL accepts its input in a form similar to what you
have just written down.
Step 1: Start MPL and Create a New Model File
Start the MPL application.
Choose New from the File menu to create a new empty model file.
Choose Save As from the File menu and save the fileas Bakery2.mpl.
Step 2: Enter the Model Formulation for the Bakery Model
You are now ready to put the model into the MPL language. The
model editor in MPL is a standard text editor which allows you to
enter the model and perform various editing operations on the model text.
In the model editor, enter the following model formulation:
TITLE BetterBreadBakery;
MAX
Profit = 0.05 Sun + 0.08 Moon - 4000/30;
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140;
Sun <= 8000;
Moon <= 5000;
END
Notice that there is one small difference between the formulation in
the previous step and the file shown here. There is a semicolon ';' after
the objective function and after each constraint. This allows MPL to
separate the constraints.
The spacing used between entries and lines in MPL is not rigid.
It is recommended, when entering the model, to use spaces and extra lines
to make the model formulation easier to read and understand. MPL
is only concerned with the actual text in the model file.
When you have finished entering the model, choose Save from the
File menu to save the model.
Step 3: Check the Syntax of the Model
After you have entered the formulation in the model editor, you can
check the model for syntax errors. If MPL finds a mistake in the
formulation it will report it in the Error Message window showing
the erroneous line in the model, along with a short explanation of the
problem. The cursor is automatically positioned at the error in the model
file, with the offending word highlighted.
To check the syntax choose Check Syntax from the Run menu.
If there are no errors found MPL will respond with a message stating
that the syntax of the model is correct. If there is an error in the model
MPL will display the Error Message window.
If you did not have any errors in your formulation (congratulations!)
you may still want to see how the error messages work. We are going to
introduce an error in the model and note how the error messages in MPL
can help you correct it.
In the model editor remove the semicolon at the end of the first
constraint as follows:
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140 ! note the missing semicolon
Sun <= 8000;
Moon <= 5000;
Choose Check Syntax from the Run menu. MPL will
go through the model and find the missing semicolon when it is parsing
the second constraint, displaying the following error message:
The Error Message Window
The reason MPL did not notice the missing semicolon until it reached
the second constraint, is because it thinks 10*140 is a coefficient for the
Sun variable in the line below.
When you press the OK button you are returned to the model
editor. The cursor will automatically be positioned at the location where
MPL found the error which in our case is at the `<=' in the second
constraint.
Now you can reenter the semicolon for the first constraint and if
you check the syntax again, MPL will report back with message that
the syntax is correct.
Step 4: Solve the Model
The next step is to solve the model 'Bakery2.mpl'. Solving the
model involves several tasks for MPL, including checking the syntax,
parsing the model into memory, transfering the model to the solver, solving the
model and then retrieving the solution from the solver and creating the solution
file. All these tasks are done transparently to the user when he chooses
the solve command from the menu. To solve the model follow these steps:
Choose Solve CPLEX from the Run menu or press the Run Solve
button in the Toolbar.
While solving the model the Status Window appears; providing
you with information about the solution progress.
The Status Window for the Bakery2 Model
If everything goes well MPL will display the message
"Optimal
Solution Found"
. If there is an error message window with a syntax
error please check the formulation you entered with the model detailed
earlier in this session.
Step 5: Viewing and Analyzing the Solution
After solving the model MPL automatically creates a standard
solution file containing various elements of the solution to the model.
This includes, among other things, the optimal value of the objective function,
the activity and reduced costs for the variables, and slack and shadow
prices for the constraints. This solution file is created with the same
name as the model file but with the extension '.sol'. In our case
the solution file will be named 'Bakery2.sol'.
After you have solved the model you can display the solution file in
a view window by pressing the View button at the bottom of the
Status
Window
. This will display the view window shown below.
View Window with the Bakery2.sol Solution File
The View Window stores the solution file in memory, allowing
you to quickly browse through the solution using the scroll bars. A full
listing of the solution file is shown here below:
MPL Modeling System - Copyright (c) 1988-1999, Maximal Software, Inc.
--------------------------------------------------------------------------------
MODEL STATISTICS
Problem name: BetterBreadBakery
Filename: Bakery2.mpl
Date: April 2, 1998
Time: 17:29
Parsing time: 0.04 sec
Solver: CPLEX
Objective value: 506.666666667
Iterations: 3
Solution time: 0.14 sec
Constraints: 3
Variables: 2
Nonzeros: 4
Density: 67 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 506.6667
DECISION VARAIBLES
PLAIN VARIABLES
Variable Name Activity Reduced Cost
------------------------------------------------------
Sun 8000.0000 0.0000
Moon 3000.0000 0.0000
------------------------------------------------------
CONSTRAINTS
PLAIN CONSTRAINTS
Constraint Name Slack Shadow Price
------------------------------------------------------
c1 0.0000 -0.4000
c2 0.0000 -0.0100
c3 2000.0000 0.0000
------------------------------------------------------
END
The first part of the solution file contains various statistics for
the model, such as the filename, date and time the model was solved, which
solver was used, the value of the objective function and the size of the
model.
The next part of the solution file contains the solution results. Here
you can see if the solution that was found was optimal or if it was unbounded
or infeasible. It also shows you the name and optimal value of the objective
function. In our case the profit for the bakery is equal to $506 per day.
In the DECISION VARIABLE section you get a list of the variables
in the model, Sun and Moon. You will see that for Sun
bread the solution suggests that you produce 8000 loaves per day, which
is the same amount as the capacity of the mixing department for the
Sun
bread. For the Moon bread the solution suggests that we produce
3000 loaves per day, which is less than the maximum capacity of 5000 Moon
loaves per day in the mixing department.
In the CONSTRAINTS section the solution file lists all of the
constraints for the model. In our model we had three constraints, one for
the ovens in the baking department, and two constraints in the mixing department
for each type of bread. Since the slack for the first constraint is zero this
means that the ovens in the baking department are running at full capacity.
In a similar way, the mixers for the Sunshine Bread are running at full
capacity, but the mixer for the Moonlight Bread has a slack of 2000.
Therefore, since the ovens in the bakery department are shared between
the two types of breads, the solver has chosen to produce as much of the
Sunshine bread as possible, then use the rest of the capacity to produce
the Moonlight bread.
Back To Top
|
Maximal Home Page
|
Overview |
Previous Page
|
Next Page