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:

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:

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

  1. Start the MPL application.

  2. Choose New from the File menu to create a new empty model file.

  3. 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.

  1. In the model editor remove the semicolon at the end of the first constraint as follows:

  2.     SUBJECT TO
    
            1/10 Sun + 1/5 Moon <= 10 * 140    ! note the missing semicolon
    
            Sun  <= 8000;
            Moon <= 5000;
          
  3. 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:

  4. 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.

  5. 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.

  6. 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:

  1. Choose Solve CPLEX from the Run menu or press the Run Solve button in the Toolbar.

  2. 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