Author Archives: Linear Programming Webmaster

Fundamental Theorem of Linear Programming and its Properties

In this following article we will address properties set by the Fundamental Theorem of Linear Programming through a conceptual discussion and practical and simple examples. These properties are essential when taking into consideration algorithmic resolutions of this kind of mathematical optimization models, among them is what we call the Simplex Method.

Every Linear Programming (LP) problem in standard form complies with the following three properties:

  • Property 1: “If the problem has no optimal solution then it’s unbounded or infeasible”

Note that a linear problem with a domain of unbounded feasible solutions may (or may not) allow optimal solution, i.e. facing a model with these features does not determine the presence (or absence) of an optimal solution a priori.

In the implementation of the Simplex Method there is a detection of an unbounded problem without optimal solution when calculating the variable that leaves the base index of a variable, all elements of the J column in the table, are negative, for J the index of a non basic with negative reduced cost. For example, we will consider the following linear programming problem:

unbounded lp

After standardizing the previous model, adding X3 and X4 as slack variables for constraint 1 and 2, respectively, the following initial table is obtained.

unbounded simplex

X2 is a non-basic variable with a negative reduced cost and therefore must be incorporated into the base. However it is not practical to estimate the feasibility criteria or the minimum quotient because the entries in the column X2 are negative or zero. This shows clearly that the problem is unbounded and with no optimal solution.

Moreover a linear model is infeasible (The domain of feasible solutions is empty and therefore has no supported solution) if the value of the objective function at the end of Phase I of the The Two-Phase Simplex Method is not zero.

  • Property 2: “If it has a feasible solution, it has a basic feasible solution”

A basic property of linear programming models is that in case of admitting optimal solution, it will necessarily find a vertex or segment on the boundary of the domain of feasible solutions.

In this context the implementation of the Simplex Method as an algorithmic resolution strategy; we seek to provide solutions that meets the Ax=b (Standard restrictions) and x≥0 criteria defining a (not necessarily optimal) basic feasible solution.

For example the following graph represents a linear model in two variables that show that points A, B, C, D and E are feasible basic solutions.

linear-programing-two-decis
graphical-linear-programmin

  • Property 3: “If the problem has an optimal solution, then it has an optimal basic feasible solution”

Continuing with the same example, vertex C is not only a basic feasible solution but also an optimal basic feasible solution. If all reduced costs (of non-basic variables: S1 and S3) are greater than or equal to zero and we are in presence of a basic feasible solution (X=100, S2=400, Y=350 all ≥0), we meet the stopping criterion of the Simplex Method and consequently the current basic feasible solution is optimal.

optimal-tableau-simplex-method

Formulating and Solving a Capacity Allocation Problem of a Plane

The passenger transport industry faces the problem of determining how to efficiently allocate transportation capacity when offering different prices or fees to their customers for a specific route. This is why they must consider sales revenues associated with each type of rate, estimated customer demand for such fees and the capacity of the transport in terms of the number of seats simultaneously. The next problem considers the formulation and computational problem of the capacity of allocation an airplane for an airline company. The complexity of the problem and the level of detail of the information is simplified for academic purposes.

Capacity Allocation Problem

Let us consider an airline that flies the Santiago (Chile) route to Bogota (Colombia) with a layover in Lima (Peru). This route uses an airplane with a capacity of 200 passengers. The sales department has estimated market prices (in dollars) for combinations of source/destination of 3 types of rates currently offered by the company: “Fee Y” (first class), “Fee B” (standard) and “Fee C” (tourist).

ticket-prices-table

Additionally and according to historical information about this route, the airline has estimated the maximum number of passages seats that will be in demand for each combination of rate on a flight segment. For example the maximum demand expected for the Santiago (SCL) to Bogota (BOG) in Fee B is 35 tickets.

max-demand-per-ticket

With this information the airline wants to determine how to allocate the capacity of the aircraft in order to provide a certain number of tickets for each type of fee per flight segment. To do this we define the following linear programming model:

Decision Variables:

Xij: Number of tickets offered in the Fee i, for the Origin-Destination segment j

Where i=1,2,3 represent the various types of fees (Y, B and C, respectively) and j=1,2,3 combinations of source-destination (SCL-LIM, LIM-BOG and SCL-BOG, respectively).

Parameters:

Using a notation with parameters, we can represent an optimization model in a compact way.

Pij: Price in US$ (Dollars) for the ticket fee i from Origin-Destination j segment

Dij: Maximum demand of tickets fee i on the Origin-Destination j segment

Objective Function:
objetive-function-plane
Constraints:

We must offer for each fee in the source-destination combinations a number of tickets that does not exceed the market demand.

max-demand

For each flight segment you must respect the total capacity of 200 passenger per aircraft.

capacity-of-a-plane

When the plane takes off from Santiago to Lima, it takes passengers for both Lima and Bogota. Therefore independently of what fee each of these passengers paid (hence the sum in fees) may not exceed the total capacity of the aircraft. This is guaranteed by the first constraint of capacity. The second capacity restriction is for the stretch from Lima to Bogota, where passengers coming from Santiago are also considered.

Finally the non-negativity conditions are defined.

non-negativity-plane

By using Solver to solve the above problem with the following optimal solution which determines how many tickets the airline should offer for each combination of rate and source destination is reached.

optimal-solution-plane-prob

The optimal value of the problem of total income (in dollars) associated with the proposed optimal solution is US$ 158,340.

Do you want to have the Excel file with the solution of this problem with Solver? Recommend us on Facebook, Google or Twitter using the social network tool at the bottom of this article and then download the file.

How to Download and Install the Trial version of Premium Solver Pro in Excel 2010

Solver is definitely next What’sBest! The most popular tool for solving optimization models using Microsoft Excel as a platform. In fact the free version of Solver we use is developed by Frontline Systems Inc., which provides a number of tools and resolution engines that are very useful when addressing problems of real life situations that are applied in the industry.

In the following article we will show you how to download and install the trial version of Premium Solver which is available for free for a period of 15 days, which allows us to solve significantly higher operational research models when it comes to the number of decision variables and constraints than those which can be solved with the traditional version of Solver. Additionally, by having improved resolution algorithms reliability of the solutions found and the processing times are more reliable. Here are the detailed instructions on how to download and install the trial version of Premium Solver Pro on a computer with an Excel 2010 version.

Step 1: Sign in Frontline Systems Inc, fill out the information required in the subscription form.

download-frontline-solvers

Step 2: Download the trial version compatible with the version of Excel that you have. In this tutorial the 64-bit version installation is shown. Once you are sure of our choice select “Download Now”.

download-a-free-trial-solve

If you have Excel 2010 and want to know how many bits you use to run your version of Excel, go to menu and select the Help option. In the lower right corner the number of bits of your version is displayed under “About Microsoft Excel”.

bits-excel

Step 3: Check your email account (which you provided in the subscription form from Step 1) and write down the 2 passwords that you have been assigned (pictured below, these have been protected with blue and red).

email-solver

Step 4: Once the download is complete run the “SolverSetup64.exe” file (or the name that corresponds to the version of Excel you are using).

solversetup64exe

Then select “Next”.

frontline-excel-solvers-64-

Now we enter the password that we have received by email (Step 3) to continue the program activation:

password-activation-solver

Then we must accept the license agreements of the program and select “Next”.

license-agreement-solver

At the moment, the program license has been activated and we must continue the installation process by selecting “OK”.

activation-solver

You must select the folder where the program will be installed and you can at this point simply select the folder that the program has selected by default.

destination-folder-solver

It’s time to select the product you wish to activate. In this case we selected “Premium Solver Pro” which corresponds to the improved version of Solver which is generally used for academic purposes.

frontline-excel-solvers

The installation wizard will ask us to confirm that we have selected the installation (Press “Install”).

install-solver

Finally we have completed the installation of the Premium Solver Pro program and we are in a position to use it to solve optimization models using Microsoft Excel as a platform.

installation-complete-solve

Primal Dual Relationships in Linear Programming (Duality Theory in LP)

The dual model of a Linear Programming problem consists of an alternative modeling instance that allows us to recover the information of the original problem commonly known as primal model. Therefore it is sufficient to solve one of them (primal or dual) to obtain the optimal solution and the optimal value of the equivalent problem (primal or dual as applicable). For this you can use the conditions of the Complementary Slackness Theorem.

Primal Dual Relationships can be summarized in the following table:

primal-dual-relationship

The above table can be interpreted both left to right and right to left. Below is an optimization model to consider as the primal problem and that in a previous article was resolved through the Two Phase Simplex Method.

example-linear-programming-

Because in this case the problem is a primal minimization, to define their respective dual problem we will read the table summarizing the relationships of duality from left to right. Consequently, the dual problem will be one of maximization. Additionally the first and second constraints of the primal problem will define the decision variables (dual variables) in the dual problem (Y1 and Y2, respectively), with the coefficients in the objective function the current values of the right sides of the primal problem constraints. Thus the function of the dual problem is defined by the following expression:

objective-function-duality

Then for each variable in the primal problem we will have the same amount of constraints than the dual problem. In this case the variables X1, X2 and X3 define the structure of restrictions 1, 2 and 3 in our dual problem. For example the first constraint of the dual problem (associated with primal variable X1) will be 2Y1+2Y2<=160. Note that the coefficients weighted to the dual variables are variable parameters associated with the primal X1 in the first and second constraint, respectively. The constraint on the dual problem is of the “<=” because the X1 variable in the primal minimization problem has the status of non-negativity “>=0”. Finally the right side of the restriction is the coefficient of the X1 variable of the objective function of the primal problem. Following this procedure the constraints of the dual problem will be:

constraints-dual

Finally, because the first 2 restrictions of the primal problem are “>=” type in the primal minimization problem, the dual respective variables associated in the maximization problem will not be negative. Thus the dual problem is:

dual-problem

Complementary Slackness Theorem (Duality Theory in Linear Programming)

One of the major theorems in the theory of duality in Linear Programming is the Complementary Slackness Theorem. This theorem allows us to find the optimal solution of the dual problem when we know the optimal solution of the primal problem (and vice versa) by solving a system of equations formed by the decision variables (primal and dual) and constraints (primal and dual model).

The importance of this theorem is that it facilitates the resolution of the models of linear optimization, allowing you to find the simplest model to address (from the algorithmic point of view) because either way you will get the results of the associated equivalence model (may it be a primal or dual model).

Let us consider the following Linear Programming model (here in after primal) in 2 variables whose optimal solution is X=14/5 and Y=8/5 with optimal value V(P)=20.8.

primal-model

The dual model associated with the primal model is:

dual-model

Then the Complementary Slackness Theorem shows us the following relationships:

complementary-slackness-the

As we know X=14/5 and Y=8/5 (primal optimal solution). If we replace these values of X and Y in the third and fourth equation we generate a 2×2 system of equations in terms of A and B whose solution corresponds to A=6/5 and B=2/5 (a feasible and optimal solution of the dual model). If we subsequently evaluate the objective function in the dual problem of this solution we obtain: V(D)=12(6/5)+16(2/5)=20.8 which is similar to the primal problem’s optimum value (satisfy the Strong Duality Theorem).

Notes: Note that the 1 and 2 constraints of the primal problem are active at the optimum, i.e. equality is met.