Q What is a "general" linear programming problem?
A By a general linear programming problem, we will understand a linear programming problem that may or may not be a standard maximization problem, but where all the variables are still constrained to be non-negative.

Thus, a general LP problem can fail to be a standard maximization problem for one or both of the following reasons:

(We call problems with some ≤ constraints and other ≥ constraints problems with mixed constraints.)

P ¿Qué es un problema "general" de programación lineal?
R Por un problema general de programación lineal, entenderemos un problema de programación lineal que puede o no puede ser un problema maximización estándar, pero en el que todas las variables son restringidas a ser no negativas.

Por lo tanto, un problema general de programación lineal puede fallar ser un problema maximización estándar por una o ambas dos de las siguientes razones:

(Llamamos a problemas con algunas restricciones ≤ y otras restricciones ≥ problemas con restricciones mixtas.)
The following are not standard maximization problems (the offending parts are shown in red). Los siguientes no son problemas maximización estándar (las partes de infracción son mostradas en rojo).
Just as with standard maximization problems, the method most frequently used to solve general LP problems is the simplex method. However, there are a number of different ways to use the simplex method for non-standard problems. Here is the easy method described in and :
Como con las problemas maximización estándar, el método más común para solucionar los problemas no estándar es el método simplex. Sin embargo, hay varias maneras distintas aplicar el método simplex a los problemas no estándar. El siguiente es el método fácil describido en y :

Step 1: Convert the LP problem to a system of linear equations. Paso 1: Convierte el problema PL en un sistema de ecuaciones lineales.
As with standard maximization problems, we add slack variables for the "≤" constraints. For the "≥" constraints, we need to subtract the surplus. Thus, for instance, the constraint
x + y - z \geq 5
is written as
x + y - z - s = 5
The variable s in this case is called a surplus variable.
Como en el caso de los problemas maximización estándar, añadimos variables de holgura para las restricciones "≤." Para las restricciones "≥," debemos sustraer el exceso. Por lo tanto, por ejemplo, la restricción
x + y - z \geq 5
se escibe como
x + y - z - s = 5
La variable s en este caso se llama una variable exceso.
Here is a nonstandard LP problem with the associated system of equations:
El siguiente es un problema no estándar con el sisema asociada de ecuaciones lineales
LP problemProblema PL System of equationsSistema de ecuaciones
x - y + 3z - s = 10
4x - 3y + z + t = 3
2x - y + 3z - u = 15
-5x + 5y - z + p = 0
Here, s and u are surplus variables, while t is a slack variable.
Aquí, s y u son variables de exceso, mientras que t es una variable de holgura.
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 or surplus variables variables.
Reescribe tu problema PL como un sistema de ecuaciones lineales. Usa s como la primera variable de holgura o exceso, y t como la segunda, y u como la tercera.
We now set up the initial tableau as for standard LP problems.
A continuación configuramos la tabla inicial como para los problemas PL estándar.

Step 2: Set up the first tableau. Paso 2: Configura la tabla inicial.
Recall that this is the augmented matrix for system of equations we just obtained in matrix form.
Acuerdate que esta es la matriz ampliada del sistema de ecuaciones acabamos de conseguir.
Set up the initial tableau for your problem. Configura la tabla inicial para tu problema.
     
Notice that the values of the surplus variables and are currently negative. This is not permitted, since all variables are required to be non-negative. The result is that the current basic solution (x, y, z) = (0, 0, 0) is not feasible, (it does not satisfy the and constraints). We star the rows corresponding to negative basic variables:
Observa que los valores de las variables de exceso y son actualmente negativas. Ésto no es permitido, ya que todas las variables se requiren ser no negativas. El resultado es que la solución básica actual, (x, y, z) = (0, 0, 0), no es factible, (no satisface la y restricción ). Usamos estrellas para indicar los renglones que corresponden a aquellas variables negativas:
Our first order of business is to get into the feasible region. Equivalently:
Nuestra primera tarea es movernos a la región factible. Equivalentemente:

Phase 1: Get rid of the stars. Fase 1: Deshazte de las estrellas.
We can (eventually) get rid of all the stars by pivoting one or more times. The only way this differs from the procedure for pivoting in standard maximization problems is the way in which we select the pivot column.
  • For standard maximization problems, the pivot column is the column with the most negative number in the bottom row.
  • In Phase 1, on the other hand, the pivot column is the column with the the largest positive number in the first starred row.
Once we have selected the pivot column, we select the actual pivot as usual by using the lowest test ratio in the pivot column. (Note: If the lowest ratio occurs both in a starred row and an non-starred row, you must pivot in a starred row rather than the non-starred one.) Thus, in Phase 1, we don't worry about negative numbers in the bottom row at all (there might not even be any there to begin with).

That is all there is to Phase 1.
Podemos (eventualmente) deshacernos de todas las estrellas por pivotar una o más veces. La única manera en la que esto es distinto del proceso de pivotar en problemas maximización estándar es la manera en la que seleccionamos la columna del pivote.
  • Para problemas maximización estándar, la columna pivote es la columna con el número más negativo en el último renglón.
  • En Fase 1, por otro lado, se escoge la columna pivote es la columna con la entrada positiva más grande en el primer renglón con estrella.
Después de escoger la columna pivote, escogemos el pivote como de costumbre como la entrada en la columna pivote con la razón de prueba más pequeña. (Nota: Si razón de prueba más pequeña ocurre en un renglón con estrella y también en un renglón sin estrella, debes escoger el pivote en un renglón con estrella.) Por lo tanto, en Fase 1, no nos preocupamos de cualquieres números negativos en el último renglón (en realidad puede ser que no hay ningunos cuando empieces).

Eso es todo que hay de Fase 1.
Consider the following tableau, in which t, u and v currently have negative values, so their rows are starred, meaning we must follow the Phase 1 rule for selecting a pivot:
Considera la siguiente tabla en la que los renglones de t, u y v tienen estrellas porque sus valores son negativos (esto significa que estamos en Fase 1, así que debemos seguir la regla de Fase 1 para escoger el pivote):
The first starred row is the t-row (second row), and its largest entry is the 4 in the y-column, so the y-column is the pivot column. The lowest test ratio is 30/8, and so the pivot is the 8 as shown.
El primera renglón con estrella es el segundo: el renglón-t-row, y su intrada más grande es la 4 en la columna-y, de modo que la columna-y es la columna pivote. La razón de pruba más pequeña es 30/8, así que el pivote es la 8 como mostrado.
Here again is your first tableau. Click on the pivot for this tableau. Aquíí estaá de nuevo tu tabla incial. Haz clic en el pivote para esta tabla.
Now clear the pivot column to obtain the second tableau. Be sure to star every row that needs a star. Despeja la columna pivote para obtener la segunda tabla. Segúrate de poner estrellas en todos los renglones que la necesitan.
     

Q What happened to the star in Row
A It is gone, because the value of the basic solution we now get from Row is
which is no longer negative! Thus, we have eliminated one of the stars. In fact, whenever a pivot happens to be in a starred row, that row will lose its star after pivoting.

Since there is still one starred row left, we are not yet done with Phase 1.
 

P ¿Qué pasó con la estrella en Renglón
R Ha ido, porque el valor de la solución básica que ahora obtenemos de Renglón es
que ¡ya no es negativo! Así, hemos eliminado una de las estrellas. En realidad, siempre que un pivote sucede que estar en un renglón con estrella, va a perder su estrella aquel renglón después de pivotar.

Ya que queda un renglón con estrella, todavía no hemos terminado con Fase 1.
 
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.
     

Q Ok the stars are gone. Now what?
A Since there are no more stars, we are now in the feasible region, and can proceed to Phase 1I.

P Bueno, las estrellas se fueron. ¿Y ahora qué?
R Ya que no quedan ningunas estrellas, estamos en la región factible, y podemos andar a Fase 2.

Phase 2: Follow the simplex method as for standard maximization problems. Fase 2: Sigue el método simplex como para los problemas maximización estándar.
Revert back to selecting the pivot column using the most negative number in the bottom row (excluding the Answer column). Continue pivoting until there are no negative numbers in the bottom row (with the possible exception of the Answer column).
Revuelve a escoger la columna pivote por usar el número más negativo en el renglón más bajo (excluyendo la columna resulatado). Sigue pivotando hasta que no quedan ningunos números negativos en el renglón más bajo (con la excepción posible de la columna resultado).
Here again is your current tableau. Click on the pivot for this tableau. Aquíí estaá de nuevo tu tabla corriente. Haz clic en el pivote para esta tabla.
The resulting pivot operation gives the following tableau:
Aquí está la tabla que resulta de la operación pivote:
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 pf the LP problem is the current basic solution.
Darte 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:
Notes Notas

How to Solve Minimization Problems

We deal with minimization problems by simply converting them to maximization problems, as illustrated in the following example: Como solucionar problemas de minimización

Tratamos problemas de minimización por simplemente convertirlos en problemas de maximización, como mostrado en el siguiente ejemplo:
Example: Converting a Minimization Problem to a Maximization Problem
Here is a minimization problem:
Ejemplo: Convertir un problema de minimización en un problema de maximización
Aquí está un problema de minimización:
Since minimizing c is the same as maximizing p = -c, we can rewrite the above problem as follows:
Ya que minimizar c es lo mismo que maximizar p = -c, podemos reescribir el problema como sigue:
Since this problem is a maximization problem, we can solve it as above. If you would like to see the complete solution of this problem, enter it in the simplex method tool and set it to Integer Mode. You can simply copy the following text and paste it into the top text area:
Ya que este problema es un problema maximización, podemos solucionarlo como lo hicimos más arriba. Si deseas ver la solución entera de este problema, ingrésala en la herramiente método y ponlo en el modo número entero". Puedes simplemente copiar el siguiente texto y pegarlo en la área de texto más arriba:

You can now try some of the exercises in Section 4.4 of , try some chapter review exercises, or the Linear Programming true false quiz. Ahora puedes probar algunos ejercicios en la sección 4.4 de , probar unos ejercisios de repaso, o bien el concurso verdadero falso sobre la programación lineal.

Maximize p = 2x + 3y + z subject to x + y + z <= 40 2x + y - z >= 10 - y + z >=10 Game Version 1 Maximize p = 10x + 15y + 20z subject to x + y + {1, 2}z <= 40 2x + y - z >= {20, 30, 40, 50} - y + 2z >=10 2: Maximize p = 15x + 10y + 10z subject to x + y - z ² 12 x -z ³ 3 x + 2y - 2z ³ 15 3: Maximize p = 15x - 10y + 10z subject to x + y - z ² 12 x {+,-} z ³ 3 x + 2y - 2z ³ 15 4: Maximize p = {15, 10}x - 10y - 10z subject to x + y - z ² 24 x -y + z ³ 6 x + 2y - {2, 5}z ³ 27 5: Maximize p = 10x - 25y - 5z subject to x + 2y + {1, 2, 3}z <= 12 2x + 2y - z >= 2 - y + 2z >=2