Operational Research - Herrera Cáceres

Some examples of previous exams: See here the document

Fundamentals of the Simplex Method: The Simplex table is the basis for displaying the duality concepts and performing sensitivity analysis or post-optimal. In the initial table, the constraint coefficients under the initial variables form an identity matrix (all elements on the main diagonal are 1, and all non-diagonal elements are zero). With this arrangement, the successive iterations of the Simplex algorithm, generated by the row operations using the Gauss-Jordan method, modify the elements of the identity matrix to produce what is known as the "inverse matrix". As we shall see, the inverse matrix is the key to compute all elements of the associated simplex table. See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.)

Cases with degenerate solutions: The convergence of the algorithm is guaranteed if there is no degeneration. However, in case of degeneration of several basic variables, the algorithm can enter an infinite cycle (loop), moving through a sequence of bases that correspond to the same vertex without improving the objective function. See the full lecture       See attached PDF document

Concepts and problems on Linear Programming and Networks: In Spanish: David Pujolar:               Casa del libro               Dialnet               Google books In English: Hillier & Lieberman             Problems on pages: 77, 150, 188, 261, 348, 412           In the cases referred to network models, focus your study on the algorithms seen in class. Hillier & Lieberman 7th edition             Problems on pages: from 90 to 108 and from 172 to 189 Hamdy A. Taha             Selected LP applications on page: 27.            Problem set on pages: 100, 106, 111, 115, 118, 120, 122, 126, 128, 134, 144, 149, 155, 157, 159, 162, 166, 171, 173, 177, 181, 184, 186, 189, 190, 238,242, 246, 250, 255  ...

Assignment about Simplex Algorithm with Artificial Variables Solve the following LPM using the simplex algorithm. Identify the type of solution, indicating in the final simplex table the reason of that solution. I.                      Solution applying the Big M Technique and  the Two-Phase Technique . See here the solution Solution of other LPM's Solve the following LPM's using the simplex algorithm. Identify the type of solution, indicating  in the final simplex table  the reason of that solution. I.               See here the solution using the Big M Technique See here the solution using the 2Phase Technique

Simplex Algorithm: un example: See the example   Simplex Algorithm: several types of solution: Summary of solution types Proper optimal and unique solution (global strict): An optimum solution has been found, and for all non-basic variable is true that: 𝑧𝑗 𝑐𝑗≠ (non-null values). Proper, optimal, but multiple bounded solution: An optimum solution has been found. However, there is at least one non-basic variable with 𝑧𝑗 𝑐𝑗= (null value). Proper, optimal, but multiple unbounded solution: The optimality condition has not been found, but it is observed that, for the entering variable, the column Ratio cannot be calculated because all values in the entering column (pivot) are non-positive. Unfeasible solution: A global optimum solution has been found. However, in the base there is still at least an artificial variable with non-zero value. Degenerate solution: A solution has been found for which at least one of the basic variables is null. In ...

Simplex algorithm when it is necessary to add artificial variables: The Big-𝑀 Technique. The Two-Phase Technique See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.)

Two examples of Simplex algorithm: I recommend you review the steps described in the Simplex Algorithm and see these two examples. You can review the suggested bibliography to expand your knowledge. See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.)

Simplex algorithm: 1. Express the model in the standard form. 2. Establish the initial conditions (first table). 3. Evaluate the criterion of optimality - infeasibility:     Is there a type of final solution?         Output: Solution type.         Stop.     Otherwise         Choose a new Entering Basic Variable.         Choose the Leaving Basic Variable.         Generate a new Simplex table.         Repeat step 3. See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.)

Definition: It is a general algebraic algorithmic procedure, developed by George Dantzig in 1947, based on geometric concepts and linear algebra to solve linear programming problems. General characteristics: It is an iterative algorithmic procedure in which calculations and results  of each iteration are represented in matrix or tabular form.  It is intuitive. It is of extraordinary efficiency. It is necessary to use the computer to solve big problems (large number of variables). There is a wide variety of complex software packages for this. It is adaptable to other forms of models. Extensions and variations of the simplex method are used to perform post-optimal analysis (including sensitivity analysis) of the model. See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.) Example of Gauss Jordan method

LP: Examples / Exercises Download this PowerPoint document to see the solution of several LPP using the graphical method. Additionally, you will find in it several exercises proposed with which you will be able to practice. Do not forget to check the recommended bibliography. There, you can expand possibilities and knowledge. See the full lecture   (This file is compressed. Therefore, you must install Winzip, winRAR or another compatible decompressor application on your computer.)