Referencia external: Programacionlineal.net   External reference: Wikipedia

Q Remind me what a linear programming problem is.
A A linear programming (LP) problem is a problem in which we are asked to find the maximum (or minimum) value of a linear objective function

P Recuérdame qué es un problema de programación lineal.
R Un problema de programación lineal (PL) es un problema en lo que debemos hallar el valor máximo o mínimo de una función objetiva
subject to a set of linear constraints of the form
lineal sujeta a un conjunto de restricciones lineales de la forma
The desired largest (or smallest) value of the objective function is called the optimal value, and a collection of values of the unknowns x_1, x_2, ..., x_n that gives the optimal value constitutes an optimal solution. The variables x_1, x_2, ..., x_n are called the decision variables.
El valor deseado más grande (o más pequeño) de la función objetiva se llama el valor optimal, y un conjunto de valores para las incógnitas x_1, x_2, ..., x_n que nos da el valor óptimo es una solución óptima. Las variables x_1, x_2, ..., x_n se llaman las variables decisión.

A linear programming (LP) problem is called a standard maximization problem if:
  • We are to find the maximum (not minimum) value of the objective function.
  • All the decision variables x_1, x_2, ..., x_n are constrained to be non-negative.
  • All further constraints have the form bx_1 + bx_2 + .. + bx_n \leq c (and not \geq) with c nonnegative.
Un problema de programación lineal (PL) se llama un problema de maximización estándar si:
  • Necesitamos hallar el valor máximo (no mínimo) de la función objetiva.
  • Todos las variables x_1, x_2, ..., x_n son restringidas a ser no negativas.
  • Cada restricción adicional tiene la forma bx_1 + bx_2 + .. + bx_n \leq c (y no \geq) con c no negativa.
The following is a standard maximization problem:
El siguiente es un problema de maximización estándar:
Press the link on the side to learn how to solve non-standard maximization ones.

The method most frequently used to solve LP problems is the simplex method. Here is a step-by-step approach.
Pulsa el enlace a lo lado para aprender como solucionar problemas no estándar.

El método más común usado para solucionar los problemas PL es el método simplex. El siguiente es un enfoque paso a paso.

Step 1: Convert the LP problem to a system of linear equations. Paso 1: Convierte el problema PL en un sistema de ecuaciones lineales.
We do this by turning each constraint inequality into a linear equation by adding new variables we call slack variables, and rewriting the objective function as illustrated in the following example:
Lo hacemos por convertir cada desigualdad restricción en una ecuación lineal por añadir nuevas variables llamadas variables de holgura, y por reescribir la función objetiva como ilustrado en el siguiente ejemplo:
Start with the following LP problem:
Vamos a considerar el siguente problema:
This is the LP problem we will be using throughout this tutorial to explain the steps. We will refer it to throughout the tutorial as the demonstration LP problem. For practice, you will be given a different problem to work on below.
Eso es el problema PL que usaremos durante todo el tutorial. Lo denominarémos durante todo el tutorial como el problema PL demonstración. Para practicar, serás dado un otro problema en lo que vas a trabajar más abajo.
To turn the constraints into equalities, we will add new nonnegative "slack variables" to the left-hand side "take up the slack." In addition we will rewrite the objective function by bringing all the unknowns to the left-hand side:
Para convertir las restricciones en igualidades, añadiremos "variables de holgura" no negativas al lado izquierdo para equiparar el lado izquierdo al lado derecho. Además, reescribiremos la función objetivo por traer todas la variables al lado derecho:
    x + y + z + s = 10
    4x - 3y + z + t = 3
    2x + y - z + u = 10
    -2x + 3y - z + p = 0
Note that we omit the constraints x \geq 0, y \geq 0, z \geq 0; the simplex method assumes that all variables are nonnegative.
Nota que omitimos las restricciones x \geq 0, y \geq 0, z \geq 0; el método simplex asuma que todas las variables son no negativas.
Your problem Here is the problem you will be working on throughout this tutorial:
Tu problema Aquí está el problema PL en lo que estarás trabajando tu durante todo el tutorial:
Rewrite your LP problem as a system of linear equations. Use s, t, and u as your first, second, and third slack variables.
Reescribe tu problema PL como un sistema de ecuaciones lineales. Usa s como la primera variable de holgura, y t como la segunda, y u como la tercera.
We can now go to Step 2.
A continuación pasamos al Paso 2.

Step 2: Represent the system of equations obtained above in the form of an augmented matrix. Paso 2: Representa el sistema de ecuaciones obtenido más arriba en la forma de una matriz ampliada.
This matrix is called the first tableau, and we set it up as shown in the example below.
Ésta matriz se llama la tabla inicial, y la arreglamos como mostrada en el ejemplo más abajo.
For the system in the demonstration LP problem
Para el sistema en el problema PL demonstración
    x + y + z + s = 10
    4x - 3y + z + t = 3
    2x + y - z + u = 10
    -2x + 3y - z + p = 0
we obtain the following first tableau:
obtenemos la siguiente tabla inicial:
Refer again to your LP problem:
Refiérete de nuevo a tu problema PL:
You have already expressed it as a system of linear equations. Now set up the first tableau. (You can use the Tab key to move from cell to cell. Press "Check" when done.) Ya has convertidlo en un sistema de ecuaciones lineales. A continuación, configura la tabla inicial. (Puedes usar la tecla de tabulación para mover de una celda a la siguiente.)

Basic solutions

Let's take another look at the initial tableau in the demonstration LP problem:

Soluciones básicas

Vamos a echar un vistazo a la tabla inicial del problema PL demonstración:
Associated with each tableau (including the initial one above) is a so-called basic solution. This is one of the infinitely many possible solutions of the system of equations represented by the tableau.

To find the basic solution in a tableau, look at the variables listed down the leftmost column in the tableau above: s, t, u, p. You will notice that the corresponding columns with the same headings (shown in red above) are cleared (all zeros except for one "pivot" entry). We assign to each of these variables the ratio Answer/(Pivot entry) as shown:
Asociada a cada tabla (incluyendo la tabla inicial más arriba) es una presunta solución básica. Esta es una de los infinitamente muchas soluciones posibles representada por la tabla.

Para hallar la solución básica de la tabla, mira a todas las variables escritas en la columna más a la izquierda de la tabla más arriba: s, t, u, p. Observarás que las columnas correspondientes con los mismos títulos (mostrada en rojo más arriba) son despejadas (todo xero salvo una sola entrada "pivote"). Designamos a cada tal variable la razón Respuesta/(Entrada pivote) como mostrado:
For example, to find the value of u, divide the answer in the u row (10, shown in a green box) by the pivot in the u column (1) to obtain 10/1 = 10.

We call these variables the active variables. All the other variables (x, y, z in this case) are assigned zero and are called inactive.

Here is another example: Por ejemplo, para localizar el valor de u, divide la respuesta en el renglón u (10, mostrada dentro de una caja verde) por el pivote en la columna u (1) para obtener 10/1 = 10.

Llamamos a todas estas variables las variables activas. A cada una del resto de las variables (x, y, z en esto caso) asignamos el valor cero y llamamos inactiva.

El siguiente es un otro ejemplo:
Here is your initial tableau from the quiz above:
Aquíí estaá la tabla inicial del cuncurso más arriba:
Notice that the current value of p (p = 0) hardly seems like a maximum value. In the simplex method, we obtain larger and larger values of p by pivoting (clearing various columns). For more explanation, see the tutorial on Gauss-Jordan.

To select each pivot entry, we will first select a column, then a row.
Observa que el valor corriente de p (p = 0) no parece precisamente un valor máximo. Por el método simplex, vamos a obtener valores más y más grade de p por pivotar (despejar varias columnas). Por más explicación ve el tutorial sobre Gauss-Jordan.

Para escoger cada entrada pivote, primero escogeremos una columna, y entonces un renglón.

Step 3: Select a pivot column. Paso 3: Escoge una columna pivote.
The rule for the selecting a pivot column is this: Look at all the numbers in the bottom row, excluding the last entry on the right (in the Answer column). From these, choose the negative number with the largest magnitude; its column is the pivot column. If there are two or more candidates, choose any one. If there are no negative numbers to choose, then you are done, and the current basic solution is the optimal solution.
La regla para escoger una columna pivote is la siguiente: Mira todos los números en el último renglón, excluyendo la última entrada a la derecha (en la columna Resultado). Entre aquellos, escoge el número negativo con el valor absoluto más grande; su columna es entonces la columna pivote. Si hay dos o más candidatos, escoge alguno de aquellos. Si no hay números negativos a escoger, entonces estás terminado, y la solución del problema PL es la corriente solución básica.

In the initial tableau of the demonstration LP problem, the negative entry in the bottom row with the largest numerical value is the −2, so the pivot column is the x-column. The actual pivot will be somewhere in this column.
En la tabla inicial del problema PL demonstración, la entrada negativa con el valor absoluto más grande en el último renglón es la −2, así seleccionamos la columna-x como la columna pivote. El pivote en sí estará en alguna parte de esta columna.
Step 4: Select the pivot. Paso 4: Escoge el pivote.
Use the following rules to decide which of the entries in the column you selected to use as the pivot:
1) The pivot must always be a positive number (zeros or negative numbers are not permitted as pivots).
2) For each positive entry b in the pivot column, compute the ratio a/b, where a is the number in the rightmost column in that row. We call this a test ratio.
3) Of these ratios, choose the smallest one. The corresponding number b is the pivot.
Usa las siguientes reglas para decidir cual de las entradas en la columna seleccionada usar como el pivote:
1) El pivote debe ser positivo (números negativos o ceros no son permitidos como pivotes).
2) Con cada entrada positiva b en la columna pivote, calcula la razón a/b, el la que a es el número en aquel renglón más a la derecha. Llamamos a esta razón una razón de prueba.
3) Entre estas razones, escoge la más pequeña. La entrada correspondiente b es el pivote.

In the demonstration example we are working with, the pivot will be either the 4, the 1 or the 2 in the x-column. Here are the test ratios for these candidates:
En el ejemplo demonstración con el que estamos trabajando, el pivote será o la 4, la 1, o la 2 en la columna-. Aquí están las razones de prueba para estos candidatos:
Because the smallest test ratio is in row 2, our pivot will be the 4 as shown.
Ya que la razón de prueba más pequeña ocurre en rnglón 2, nuestro pivote será la 4 como mostrado.
Here again is your initial tableau. Click on the pivot for this tableau. Aquíí estaá de nuevo tu tabla inicial. Haz clic en el pivote para esta tabla.
Having selected the pivot, we now proceed to the next step.
Ahora que hemos escogido el pivote, podemos avanzar al próximo paso.

Step 5: Use the pivot to clear the pivot column in the normal manner. This gives the next tableau. Paso 5: Usa el pivote para despejar su columna en la manera usual. Así obtenemos la tabla siguiente.
To clear the column, or "pivot," we follow the exact prescription for formulating the row operations described in Section 2.2 of or . For quick instructions on how to pivot, press here. For a detailed tutorial with interactive examples, press here.)
Para despejar la columna, o "pivotar", seguimos las instrucciones para formular operaciones renglón como descritas en la sección 2.2 de o . Para instrucciones en-línea sobre como pivotar, haz clic aquí. Para un tutorial detallado con ejemplos interactivos, haz clic aquí.)

In the demonstration example we are working with, we clear the pivot column using the row operations shown:
En el ejemplo demonstración con el que estamos trabajando, despejamos la columna pivote por usar las operaciones renglón mostradas:
and thereby obtain the second tableau: y así obtenemos la segunda tabla:
Notice that the label on the left of the pivot row has been changed from "t" to x, which is the heading of the pivot column. Nota que la etiqueta a la izquierda del renglón pivote ha sido cambiada de "t" a x, que es es título de la columna pivote.

Here again is your initial tableau with the pivot selected. Carry out Step 5 to obtain the second tableau. (You can use the Tab key to move from cell to cell. Press "Check" when done.). Aquíí estaá de nuevo tu tabla inicial con el pivote seleccionado. Haz el Paso 5 para obtener la segunda tabla. (Puedes usar la tecla de tabulación para mover de una celda a la siguiente.)
     
Now that you have your second tableau, we go to the next step.
Ahora que tienes tu segunda tabla, vamos al siguiente paso.

Step 6: Repeat Steps 3–5 until there are no more negative numbers in the bottom row (with the possible exception of the Answer column). Paso 6: Repita Pasos 3–5 hasta que no hay ningunos números negativos en el último renglón (con la excepción posible de la columna resultado).
That is, we take the most negative number in the bottom row of the current tableau (excluding the rightmost entry) and clear its column using a pivot selected as per Step 4 to obtain the next tableau, and so on, until there are no more negative numbers in the bottom row (excluding the rightmost entry). At that point, we are done, and the solution to the LP problem is the corresponding basic solution.
Es decir, tomamos el número más negativo en el renglón mas bajo de la tabla corriente (excluyendo la entrada más a la derecha) y despejamos su columna a través de un pivote seleccionado según Paso 4 para obtener la tabla siguiente, y así en modo parecido hasta que no quedan ningunos números negativos en el último renglón (excluyendo la entrada más a la derecha). LLegado aquel momento, hemos terminado; la solución del problema PL es entonces la solución básica correspondiente.

Here is the second tableau of the demonstration example we are working with:
Aquí está la segunda tabla del ejemplo demonstración:
Since the third entry of the bottom row is negative, we need to repeat Steps 3–5 to clear its column:
Pues la tercera entrada del renglón mas bajo es negativa, necesitamos repitir Pasos 3–5 para despejar su columna:

Pues la tercera entrada del renglón mas bajo es negativa, necesitamos repitir Pasos 3–5 para despejar su columna:
This is the third tableau. As there are no more negative entries in the bottom row, we are done, and can write down the current basic solution as the solution of the original LP problem:
Esto es la tercera tabla. Ya que no quedan ningunas entradas negativas en el últomo renglón, hemos terminado, y podemos escribir la básica solución corriente como la solución del problema PL original:
    x = 0 (inactive); y = 0 (inactive); z = 3/1 = 3;
    s = 28/4 = 7; t = 0 (inactive); u = 26/2 = 13;
    p = 6/2 = 3;
Thus, the maximum value of p is 3, and occurs when (x, y, z) = (0, 0, 3). Por lo tanto, el valor máximo de p es 3, y ocurre cuando (x, y, z) = (0, 0, 3).
Esto es la tercera tabla. Ya que no quedan ningunas entradas negativas en el últomo renglón, hemos terminado, y podemos escribir la básica solución corriente como la solución del problema PL original:
Here again is your second tableau. Click on the pivot for this tableau. Aquíí estaá de nuevo tu tabla segunda. Haz clic en el pivote para esta tabla.
Now clear the pivot column to obtain the third tableau. Despeja la columna pivote para obtener la tercera tabla.
     
If you got this right, you will notice that there are no negative numbers in the bottom row. This means that we are done, and the current tableau is the final tableau. The solution of the LP problem is the current basic solution.
Si lo hiciste bien, te darás cuenta de que no quedan números negativos en el último renglón. Esto significa que hemos terminado, y la tabla corriente es la tabla final. La solución del problema PL es la solución corriente.
Thus, the solution of your LP problem is:
Por lo tanto, la solución de tu problema PL es:
Click here to bring up a window that summarizes all the steps in the simplex method.
Haz clic aquí para abrir una ventana que muestra todos los pasos en el método simplex.