EIE 6653 Advanced Optimization

Linear Programming and Integer Programming topics to solve the problem with LINGO software. The assignment is basically to apply some of these techniques on any subject to make a study case in 5 single line spaces.

The students will work as individuals on an optimization project at their workplace or other real-world environment and must have a project/problem defined by Module 2 of the class. Students will be required to use one of the tools discussed in class to solve a real-world optimization problem

- The Simplex Algorithm and Goal Programming

´Unfortunately, most real-life LPs have many variables, so a method is needed to solve LPs with more than two variables.

´We devote most of this chapter to a discussion of the simplex algorithm, which is used to solve even very large LPs. In many industrial applications, the simplex algorithm is used to solve LPs with thousands of constraints and variables.

´we explain how the simplex algorithm can be used to find optimal solutions to LPs. We also detail how two state-of-the-art computer packages (LINDO and LINGO) can be used to solve LPs.

Briefly, we also discuss Karmarkar’s pioneering approach to solving LPs. We close the chapter with an introduction to goal programming, which enables the decision-maker to consider more than one objective function

´Before the simplex algorithm can be used to solve an LP, the LP must be converted into a problem where all the constraints are equations and all variables are nonnegative.

´An LP in this form is said to be in standard form.

Example :

´Leather Limited manufactures two types of leather belts: the deluxe model and the regular model.

´Each type requires 1 square yard of leather.

´A regular belt requires 1 hour of skilled labor and a deluxe belt requires 2 hours of skilled labor.

´Each week, 40 square yards of leather and 60 hours of skilled labor are available.

´Each regular belt contributes $3 profit and each deluxe belt $4.

´Write an LP to maximize profit.

Solutions 1 :

´The decision variables are:

´x1 = number of deluxe belts produced weekly

´x2 = number of regular belts produced weekly

´The appropriate LP is:

max z = 4x1 + 3x2

s.t. x1 + x2 ≤ 40 (leather constraint)

2x1 +x2 ≤ 60 (labor constraint)

x1, x2 ≥ 0

Lingo Software

• Lingo can be employed in the analysis of multivariable objective functions.
• Lingo has a Pivot function
• A simple example presented
• From the Lindo Website
•  Simple Simplex iterator exploiting the (Simplex.lg4)
•  programming capabilities of a LINGO CALC section.
•  Assumptions:
• The first row of the matrix is objective,
• The objective is MIN,
• The last column of the matrix is RHS,
• Constraints are already inequality form,
• Initial tableau is feasible.
• Simplex iterations are performed until either:
• tableau is optimal, or
• entering column is unbounded, or
• iteration limit, ITERLIM, is exceeded;
• Keywords: Simplex method, Algorithm for LP, Primal simplex,
• Tableau, Pivoting