Forma estándar de los modelos de Programación Lineal.

            Supóngase que existe cualquier número (digamos m) de recursos limitados de cualquier tipo, que se pueden asignar entre cualquier número (digamos n) de actividades competitivas de cualquier clase. Etiquétense los recursos con números (1, 2, ..., m) al igual que las actividades (1, 2, ..., n). Sea x_j (una variable de decisión) el nivel de la actividad j, para  j = 1, 2, ..., n, y sea Z la medida de efectividad global seleccionada. Sea c_j el incremento que resulta en Z por cada incremento unitario en x_j (para j = 1, 2, ..., n). Ahora sea b_i la cantidad disponible del recurso i (para i = 1, 2, ..., m). Por último defínase a_ij como la cantidad de recurso i que consume cada unidad de la actividad j (para i = 1, 2, ..., m  y  j = 1, 2, ..., n). Se puede formular el modelo matemático para el problema general de asignar recursos a actividades. En particular, este modelo consiste en elegir valores de x₁, x₂, ..., x_n para:

Maximizar   Z = c₁x₁ + c₂x₂+ ... + c_nx_n,

sujeto a las restricciones:

a₁₁x₁ + a₁₂x₂+ ...+ a_1nx_n£ b₁

a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n£ b₂

a_m1x₁ + a_m2x₂ + ... + a_mnx_n£b_m

y

x₁³ 0,      x₂³0,    ...,    x_n³ 0

Ésta se llamará nuestra forma estándar (porque algunos libros de texto adoptan otras formas) para el problema de PL. Cualquier situación cuya formulación matemática se ajuste a este modelo es un problema de PL.

            En este momento se puede resumir la terminología que usaremos para los modelos de PL. La función que se desea maximizar, c₁x₁ + c₂x₂+ ... + c_nx_n, se llama función objetivo. Por lo general, se hace referencia a las limitaciones como restricciones. Las primeras m restricciones (aquellas con una función del tipo a_i1x₁ + a_i2x₂+ ... + a_inx_n, que representa el consumo total del recurso i) reciben el nombre de restricciones funcionales. De manera parecida, las restricciones x_j³ 0 se llaman restricciones de no negatividad. Las variables x_j son las variables de decisión. Las constantes de entrada, a_ij, b_i, c_j, reciben el nombre de parámetros del modelo.

  

Otras formas de modelos de Programación Lineal.

            Es conveniente agregar que el modelo anterior no se ajusta a la forma natural de algunos problemas de programación lineal. Las otras formas legítimas son las siguientes:

1. Minimizar en lugar de maximizar la función objetivo:

Minimizar   Z = c₁x₁ + c₂x₂+ ... + c_nx_n,

2. Algunas restricciones funcionales con desigualdad en el sentido mayor o igual:

a_i1x₁ + a_i2x₂+ ... + a_inx_n, ³b_i,      para algunos valores de i,

3. Algunas restricciones funcionales en forma de ecuación:

a_i1x₁ + a_i2x₂+ ... + a_inx_n, = b_i,      para algunos valores de i,

4. Las variables de decisión sin la restricción de no negatividad:

x_j no restringida en signo para algunos valores de j.

Cualquier problema que incluya una, varias o todas estas formas del modelo anterior también se clasifica como un problema de PL, siempre y cuando éstas sean las únicas formas nuevas introducidas. Puede ser que la interpretación que se ha dado de asignación de recursos limitados entre actividades que compiten no se aplique, pero independientemente de la interpretación o el contexto, lo único que se necesita es que la formulación matemática del problema se ajuste a las formas permitidas. Se verá que estas otras cuatro formas legales se pueden reescribir en una forma equivalente para que se ajuste al modelo que se presentó. Entonces, todo problema de PL se puede poner en nuestra forma estándar si se desea.