Return to Index
Operations Research Models and Methods
 
Computation Section
Subunit Mathematical Programming Model Builder
 - Tableau Format

Textbooks often use the tableau presentation because it is relatively compact. This format is illustrated below.

tableau
  In the following we review each component of the tableau format.

 

Variables

 

The data and results for the variables appears at the top of the worksheet in a row format. We call it the row format because each row provides a vector of values of a particular type. For example row 10 holds the names of the variables and row 11 holds the values of the variables. The solution shown is the optimal primal solution.

The variables section provides all the data for each variable except the constraint coefficients. A variable has all its data in a column of the worksheet. For example column M holds the information for the first variable. Row 11 is outlined in green to indicate that the algorithms of the add-in fill this array. The names in row 10 and the data in rows 12 through 15 are filled by the user to represent the situation under consideration.

The Type data has two recognized values, Real and Integer. When all types are Real, the model is a linear program. If all the types are Integer, the model is an integer program. Problems with some real and some integer types are often called mixed linear integer programs. Only the first letter is used to identify the type, so i and r can replace integer and real.

variables

  Rows 16 and 17 are also filled by the computer. They show the dual solution associated with the variables. These numbers are sometimes called the reduced costs. The dual variables are included only when the Jensen LP/IP solver is used. The same results are found on the sensitivity worksheet created by either the Jensen LP/IP solver and the Excel solver. At optimality, the dual values for variables with a restrictive lower bound are negative (or zero). Variables with a restricted upper bound are positive (or zero).

 

Constraints

  Information regarding the constraints start at row 22 and column D. We say the constraint data is column oriented because the data and results are shown by the columns of the display. The user can identify particular constraints with names in column E. The dual values (or shadow prices) are in column F. The left side of the constraints are evaluated using the solution variables and constraint coefficients and presented in column G. This range is yellow indicating that the cells hold formulas. The relationships (<=, =, >=) are in column H and the constraint bounds are in column I.
constraints

 

Coefficient Matrix

  For the tableau format, the constraint coefficients are stored in a matrix. The figure below shows the constraint matrix for a randomly generated problem. The two dimensional matrix is convenient for problems small enough to display the entire matrix in a worksheet window. It becomes difficult to use when the problem has more than 50 variables and 20 constraints. For larger problems only a portion of the matrix appears in the worksheet window and it is sometimes difficult to find individual cells.
coefficients
 

The matrix is not convenient if the number of nonzero coefficients is small compared to the number of cells in the matrix, n*m. This is called a sparse matrix. For older Excel versions, the number of columns on the worksheet, 256, restrict the size of the problem to around 220 variables. Excel 2010 for Windows and Excel 2011for Mac OS allow many more columns on the worksheet.

 
line
  
Return to Top

tree roots

Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved