MINIMIZACIÓN POR EL MÉTODO

SIMPLEX EN CONTENIDOS GRASOS Y

SUS RESPECTIVOS COSTOS EN DIETA
NORMAL SERVIDAS EN EL HOSPITAL
NACIONAL CAYETANO HEREDIA

TESIS PARA OPTAR EL GRADO DE

MAESTRO EN MATEMÁTICAS APLICADAS

NELLY KAU KAU

LIMA - PERÚ

2018
ASESOR DE LA TESIS

MSc. Jaime García Sócola

 JURADOS

PRESIDENTE

PhD. Juvenal Castromonte Salinas

VOCAL

PhD. César Cárcamo Cavagnaro

SECRETARIO

PhD. Mirko Zimic Peralta

AGRADECIMIENTOS

Al profesor Jaime García Sócola, quien con su constante insistencia y

preocupación, ésta tesis fue posible realizarlo.

A la Nutricionista Yianina Rojas por la ayuda incondicional en

proporcionar los datos del Hospital Nacional Cayetano Heredia.

FUENTES DE FINANCIAMIENTO

Tesis Autofinanciada
Tabla de Contenidos

I. Introducción 1

II. Planteamiento del problema 3

II.1 Antecedentes 3

II.2 Justificación 4

III. Marco teórico 5

IV. Objetivos 19

IV.1 Objetivo general 19

IV.2 Objetivos específicos 19

V. Metodología 20

V.1 Caso 1 20

V.1.1 Definición del problema de interés 20

V.1.2 Desarrollo de un procedimiento basado en el

método simplex matricial 20

V.1.3 Desarrollo de un procedimiento basado en el

método simplex tabla 29

V.2 Caso 2 37

V.2.1 Definición del problema de interés 37

V.2.2 Recolección de datos 38

V.2.3 Formulación y planteamiento del modelo matemático 46

VI. Resultados 56

VII. Discusión 68

VIII. Conclusiones 70
IX. Recomendaciones 72

X. Referencias bibliográficas 73

XI. Anexos
Resumen

Asociado a cada problema lineal existe otro problema de programación

lineal denominado problema dual. Este último posee importantes propiedades y

relaciones notables con respecto al problema lineal original, denominado primal.

Los modelos de programación lineal (minimización o maximización)

aplicados en la planeación de dietas, consisten en una función lineal que satisface

a un conjunto de restricciones lineales de desigualdad. A partir de los menús del

Hospital Nacional Cayetano Heredia se obtiene las dietas. Para ello usaremos el

método simplex matricial el que empieza en alguna solución factible inicial, ésta

es una esquina del conjunto factible S originario. Cada iteración nos lleva a otra

esquina de S por lo general con un valor mejorado de la función objetivo.

También usaremos el método simplex tabular basado en el método de

eliminación de Gauss – Jordan.

Cuando las variables y restricciones sobrepasan las tres dimensiones las

soluciones requieren grandes cantidades de operaciones, razón por la cual es

preferible recurrir a los programas LINGO o EXCEL. En éstos programas de uso

generalizado los métodos anteriormente mencionados se ejecutan incorporando

análisis de sensibilidad lo que nos ayuda en la toma de decisiones.

En ésta tesis se formula el problema de la dieta del Hospital Nacional

Cayetano Heredia como un problema de programación lineal, se analiza la

factibilidad y optimalidad. Terminada ésta primera etapa, se traduce a un código

de programación (LINGO o EXCEL), se ejecuta y se obtienen las soluciones

numéricas. Estas soluciones se analizan tanto en su consistencia interna como en

la viabilidad de su ejecución en el Hospital Nacional Cayetano Heredia. Además

se estudia la sensibilidad de los parámetros como medida conducente a tomar

decisiones adecuadas en un tiempo mínimo.

Abstract

Associated with each linear problem there is another linear programming

problem called the dual problem. The latter has important properties and

remarkable relations with respect to the original linear problem, called primal.

The models of linear programming (minimization or maximization)

applied in the planning of diets, consist of a linear function that satisfies a set of

linear constraints of inequality. From the menus of the National Hospital

Cayetano Heredia you get the diets. To do this we use the matrix simplex method

that starts in some initial feasible solution, this is a corner of the feasible set S

originating. Each iteration takes us to another corner of S usually with an

improved value of the objective function. We will also use the simplex tabular

method based on the Gauss-Jordan elimination method.

When the variables and restrictions exceed the three dimensions the

solutions require large amounts of operations, which is why it is preferable to use

the LINGO or EXCEL programs. In these programs of widespread use the above

mentioned methods are executed by incorporating sensitivity analysis which helps

us in decision making.

In this thesis the problem of the diet of the National Hospital Cayetano

Heredia is formulated as a problem of linear programming, the feasibility and

optimality are analyzed. Once this first stage is finished, it is translated into a

programming code (LINGO or EXCEL), executed and the numerical solutions are

obtained. These solutions are analyzed both in their internal consistency and in the

feasibility of their execution at the Cayetano Heredia National Hospital. In

addition, the sensitivity of the parameters is studied as a measure leading to

making adequate decisions in a minimum time.

I. Introducción

En el año 2016, el 20.7% de la población del país, que equivale en

cifras absolutas a 6 millones 518 mil personas, se encontraban en situación

de pobreza, es decir, tenían un nivel de gasto inferior al costo de la canasta

básica de consumo compuesto por alimentos y no alimentos (vivienda,

vestido, educación, salud, transporte, etc.).

Alimentarse tiene un costo y en el Perú es elemental contar con

S/328.00, costo promedio mensual, para acceder a la canasta básica de

alimentos.

Los mayores niveles de pobreza se registraron en la Sierra rural (47.8

%), en la Selva rural (39.3 %) y en la Costa rural (28.9 %).

Los departamentos con mayor incidencia de pobreza fueron

Cajamarca y Huancavelica, cuya nivel de pobreza se situó en 43.8% y

50.9%, respectivamente.

En el transcurso de los años los malos hábitos alimenticios han sido

uno de los problemas a nivel nacional, trayendo como consecuencia

malnutrición y/o sobre peso.

El consumo de nutrientes adecuados en cada etapa del desarrollo y

crecimiento de una persona mejora su capacidad física e intelectual, en

consecuencia mejora su productividad.

Una buena nutrición no depende en gran medida de un sustento

económico, comer saludable a un costo mínimo es una opción que favorecen

1
a todas las persona. La adecuada asignación de nutrientes coopera en la

recuperación del paciente.

El presente estudio tuvo como objetivo establecer el costo mínimo en

una dieta normal con valores nutricionales requeridos, minimizando además

la cantidad de grasa.

Para tal fin, se usó datos que fueron obtenidos de un menú completo

que incluye desayuno, almuerzo y cena del Hospital Nacional Cayetano

Heredia.

2
II. Planteamiento del problema

II.1. Antecedentes
Durante la Segunda Guerra Mundial, fueron necesarios grandes

esfuerzos bélicos los que requerían de manera eficaz la distribución de

grandes recursos que permitieran las maniobras militares, así como

otras actividades que componían cada operación militar. Por ésta

razón los administraciones militares estadounidenses y británicas

llamaron a un gran número de científicos quienes aplicaron diversos

métodos matemáticos en la búsqueda de soluciones prácticas a éstos

problemas tácticos, estratégicos y logísticos.

El nombre de programa no está asociado de manera alguna con

un programa de ordenador, de hecho, para la época esto hubiera sido

imposible. Dado que en la fuerza aérea los planes y proyectos a

implementar son llamados programas, Dantzig solía referirse a los

problemas de programación lineal como «programa en una estructura

lineal», y no fue hasta 1948 que el matemático Koopmans acuñó el

término «programación lineal».

El método simplex fue desarrollado por el físico y matemático

estadounidense George Bernard Dantzig (considerado como el padre

de la Programación Lineal), la cual era un algoritmo para resolver

problemas de programación lineal de dos o más variables. Este

algoritmo fue elegido como uno de los diez algoritmos más

importantes del siglo XX.

3
II.2. Justificación
El método simplex es una herramienta importante para la toma

de decisiones, para ser usada en un ambiente de incertidumbre, es un

proceso iterativo que puede generar varias aproximaciones a la

solución a través de distintas tablas de solución. Se puede identificar

cuando se ha llegado a la solución óptima del modelo.

Se planteará un modelo matemático de dieta normal con los

valores nutricionales que deben ingerirse bajo ciertas condiciones de

nutrición minimizando el coste de compra de los nutrientes y

además minimizando la cantidad de grasa. Los datos son obtenidos en

uno de los 30 menús que se sirven durante cada día del mes en el

Hospital Nacional Cayetano Heredia.

4
III. Marco Teórico
La programación lineal, que trata exclusivamente con funciones

objetivos y restricciones lineales, es una parte de la programación

matemática, y una de las áreas más importantes de las matemáticas

aplicadas. El adjetivo lineal significa que todas las funciones matemáticas

del modelo deben ser funciones lineales. En este caso, la palabra

programación es sinónimo de planificación y no se refiere al acto de

programar computadoras. Por lo tanto, la programación lineal involucra la

planificación de actividades para obtener un resultado óptimo. Para ello, se

dispone de un procedimiento de solución muy eficiente llamado método

simplex.

Un problema de programación lineal está compuesto por una función

objetivo y un conjunto de restricciones. Asumiendo que cada restricción

contiene n variables (x1, x2, … ,xn) se tiene:

Máx (o Mín) z  c1 x1  c2 x2  ...  cn xn

s.a
a11x1  a12 x2  ...  a1n xn  ó  ó  b1
a21x1  a22 x2  ...  a2 n xn  ó  ó  b2
.
.
.
am1 x1  am 2 x2  ...  amn xn  ó  ó  bm

xi  0 i  1, 2,..., n

El Problema de programación lineal así formulado puede ser

expresado mediante la introducción de variables de holgura, en lo que se

llama la forma estándar la que puede escribir de la siguiente manera:

5
 a11x1  a12 x2  ...  a1n xn  h1  b1
a21x1  a22 x2  ...  a2 n xn  h2  b2
.
.
.
am1 x1  am 2 x2  ...  amn xn  hm  bm

Donde las variables hi representan las variables de holgura.

En forma matricial lo anteriormente expuesto se representa a

continuación:

Max (o Min) z  cT x

s.a

Ax  b
esto puede ser escrito como
x0

z 
1  cT 0   0
 x    
0 A I   x  b
 s

Donde, xs son las variables de holgura introducidas en el proceso

de eliminación.

x, b, c son vectores columna.

A es la matriz coeficiente.

Este es el primer paso del método simplex. Una vez ejecutado el

primer paso, se expresa la matriz A y el vector x descompuestos en

variables básicas y no básicas tenemos:

6
  xB 
A  B N ; x  luego Ax  b se puede escribir como
 xN 

 xB 
B N    b o bien Bx B  NxN  b La función objetivo sería
 xN 

x 
z B  cB c N  B   cB xB donde xB  0
0 

Si hacemos xN  0 , Ax  b se convierte en BxB  b cuya solución

es: xB  B 1b

 xB 
Supongamos que B 1b  0 de manera que   es una solución
0 

básica factible.

La función objetivo puede expresarse como

x 
z B  cB cN  B   cB B 1b
0 
1 1
Se sabe que xB  B NxN  B b llamando Y  B 1 N tenemos

xB  Yx N  B 1b  xB

Esto quedaría expresado como cB xB  cBYx N  cB xB restando

z  cB xB  cN xN de la ecuación anterior tenemos

cN  cBY xN  z  z  z  z   z j  c j x j donde

jJ

 
Y  yj jJ
 
 ysj sI , jJ

(Hillier,F.,Lieberman,G.,2010,p.162)

7
Definición 1

Se puede reordenar las columnas de la matriz A de la forma que

A  B N  donde B es una matriz invertible de dimensiones m x m,

 xB 
entonces el punto x    donde xB  B 1b y x B  0 se llama
 xN 

solución básica. Si además de ello, cumple que xB  0 , se dirá que la

solución es básica factible. (Chavez. A., p.18)

Definición 2

Una submatriz no singular B de dimensión m x m de A se denomina

matriz básica. B también se denomina matriz básica factible si y solo si

B 1b  0

Definición 3

Dada una matriz base B formada por m columnas de la matriz A, se

dice que x B es solución básica si verifica Bx B  b . Todas las componentes

no básicas son ceros. Por lo tanto, una solución básica tiene como máximo

m componentes distintas de cero. Si además, x B tiene todas sus

componentes no negativas se dice que es solución básica factible.

Teorema 1

Sea el modelo de programación lineal, en su forma estándar, donde A

es una matriz m x n, y el rango de A es m, se tiene:

a) Si existe una solución posible, también existe una solución posible

básica.

8
 b) Si el problema tiene una solución posible óptima, entonces también

tiene una solución posible básica óptima. (Luenberger D., Ye y.,

2016, p.21)

Teorema 2

Sea el modelo de programación lineal, en su forma estándar, donde A

es una matriz m x n de rango m y b un vector m. Sea F el politopo convexo

que consiste en todos los n – vectores x que satisface

Ax  b
x0

Un vector x es solución básica factible si y sólo si x es un punto

extremo de F. (Luenberger D., Ye y., 2016, p.23)

Teorema 3

Sea el modelo de programación lineal, en su forma estándar

Máx (o Mín) z  cT x

Ax  b
x0

El valor óptimo de la función objetivo se encuentra en un punto

extremo del conjunto F.

Teorema 4

Sea S  x : Ax  b, x  0, donde A es una matriz m x n de rango m,

y b es un vector de dimensión m. Un punto x es punto extremo S si y sólo si

9
  B 1b
A puede descomponerse en B N  tal que x  donde B es una
0 

matriz de dimensión m x m invertible que satisface B 1b  0 (Bazaraa M.,et

al, 1993, p.70)

Definición 4

Considere el sistema Ax  b y x  0 en donde A es una matriz

m × p y b es un vector m. Suponga que el rango (A,b) = rango (A) = m.

Después de un posible reordenamiento de las columnas de A, sea

A  B, N  , en donde B es una matriz invertible de m x m y N es una

 xB 
matriz de m x (n-m). La solución x    de las ecuaciones Ax  b ,
 xN 

1
en donde xB  B b y xN  0

Se denomina solución básica del sistema. Si xB  0 , entonces x se

denomina solución básica factible del sistema. Aquí, B se denomina matriz

básica y N se denomina matriz no básica. Los componentes de xB se

denomina variables básicas (o variables dependientes), y las componentes

x N se llaman variables no básicas (o variables independientes). Si xB  0 ,

entonces x se denomina solución básica factible no degenerada, y si por lo

menos una componente de xB es igual a cero, entonces x se denomina

solución básica degenerada. (Bazaraa M.,et al, 1999, p.99)

10
Criterios del método simplex
1. Criterio de óptimo.- La condición necesaria y suficiente para que una

solución básica factible asociada a una base B sea óptima es:

j  J z j  c j   0

2. Criterio de entrada.- Se introduce la variable xk tal que


zk  ck  máximo z j  c j ; z j  c j   0 
3. Criterio de salida.- Si xk es la variable de entrada, la de salida será

xl x 
la xl que cumpla  mínimo s ; ysk  0 / s  I 
ylk  ysk 

 
4. Criterio de no acotación.- k  J / z j  c j  0 con yk  0 (Barazza

M., 1999, p.128)

Proposición 1

El conjunto de soluciones factibles de un problema de programación

lineal es un conjunto convexo.

Proposición 2

Si K es un poliedro convexo, entonces la función objetivo z alcanza un

mínimo en un vértice de K.

Proposición 3

Si tenemos un conjunto de K vectores A1 , A2 ,..., Ak , que sean

linealmente independientes y de forma que: x1 A1  x2 A2  ...  xk Ak  b con

las xi  0 , entonces, el punto X  x1 , x2 ,..., xk ,0,...,0 es un vértice del

T

conjunto convexo K de soluciones factibles. (Martin Q, 2011, p.38)

11
Definición 5

Un conjunto S en R n se dice que es convexo si y sólo si

x  1   y  S para todo   0,1 y x, y  S (Castillo E., et al, 2002,

p.104)

El método simplex tabular se desarrolla con el siguiente algoritmo, la

cual es una secuencia de pasos lógicos que siempre se realizan en el mismo

orden. Partiendo de un modelo de programación lineal en su forma estándar

se realiza los siguientes pasos:

Paso 1. Convertir las desigualdades en igualdades al sumarles una

variable de holgura hi. Esta variable representa la cantidad

que le falta a la desigualdad para ser igualdad. Las variables

de holgura siempre son positivas. No se incluye las

condiciones de no negatividad.

a11x1  a12 x2  ...  a1n xn  h1  b1

a21x1  a22 x2  ...  a2 n xn  h2  b2
.
.
.
am1 x1  am 2 x2  ...  amn xn  hm  bm

Paso 2. Escribir la función objetivo como una igualdad a cero

sumando las variables de holgura hi con coeficiente cero y

conservando positivo el coeficiente de z.

z  c1 x1  c2 x2  ...  cn xn  0h1  0h2  ...  0hm  0

12
Paso 3. Formar la tabla simplex

En la primera fila se escribe las variables básicas; la función

objetivo z; las variables originales del modelo, seguidas de

las variables de holgura y por último solución.

En la segunda fila contiene los coeficientes,

correspondientes a cada variable original, de la función

objetivo escrito como se obtuvo en el paso 2 y con el

coeficiente cero para todas las variables de holgura y la

solución.

En la primera columna y a partir de la tercera fila se coloca

verticalmente todas las variables de holgura empleadas.

También a partir de la tercera fila se colocan los

coeficientes de cada una de las restricciones en la columna

de la variable correspondiente (esto genera los componentes

de una matriz identidad en las variables de holgura).

En la columna solución se colocan los términos

independientes y además identificamos un elemento pivote.

13
 Paso 4. Verificamos si todos los coeficientes asociados a la fila de z

son mayores o iguales a cero. Si es así, entonces la solución

en la tabla es la óptima y el proceso termina. Si no es así, se

continúa.

Paso 5. El elemento pivote se obtiene de los coeficientes de la fila z

se toma el menor valor y se selecciona toda la columna, se

divide la columna solución entre el elemento

correspondiente de la columna seleccionada, y de los

resultados de la división se selecciona el menor valor

positivo y toda fila asociada a este valor. Las divisiones

entre cero o entre valores negativos no se toman en cuenta.

Si todas son negativas o indeterminadas el problema no

tiene solución y el proceso termina. El elemento pivote con

el método de eliminación de Gauss-Jordan usando las

operaciones de filas se convierte en 1, y todos los elementos

de es columna se convierte en cero.

Paso 6. Se repite el proceso desde el paso 4 operando sobre

matrices hasta obtener todos los coeficientes de la fila z, con

valores mayores o iguales a cero. (Haeussler,P.,2017,p.314)

Definición 6

Columna unitaria – Si una de las entradas en la columna es 1 y las

otras entradas son ceros. (Soo,T.,2010,p.254)

14
Notación para las operaciones de filas

Sea Ri que denota el iésima fila de una matriz, escribimos:

Operación1. Ri  R j Intercambio de filas

Operación 2. cRi c veces la fila i

Operación 3. Ri  aR j Sustituir la fila i con la suma de la fila i y a

veces la fila j

(Soo,T.,2010,p.255)

El método dual – simplex se desarrolla partiendo de un modelo con el

objetivo de minimizar, se utiliza la tabla primal – dual para trasladar el

problema a maximización o viceversa. Para formar la tabla primal –

dual se realiza la siguiente secuencia:

1. El tamaño de la tabla es de m+2 renglones y n+2 columnas. (n

número de variables y m número de restricciones del problema

primal)

2. La celda de la esquina superior izquierda se divide en 2 con una

diagonal en la parte superior escribimos la palabra primal y dual.

En la primera fila, las variables del problema primal (n variables)

ya continuación el símbolo <= (máx) ó >= (mín).

3. Los coeficientes de la función objetivo del modelo primal en la

última fila. Los coeficientes de las restricciones en las siguientes

filas.

4. La última columna las cantidades limitantes de las restricciones

del modelo primal.

15
 5. El modelo primal se lee en forma vertical y el modelo dual en

forma horizontal.

(Hillier,F.,Lieberman,G.,2010,p.181)

Definición 7

Dado el problema de programación lineal minimizar

z  cT x

Sujeto a

Ax  b
x0

Su problema dual es maximizar

z  bT y

Sujeto a

AT y  c
y0

Donde y   y1 ,..., ym  se denominan variables duales.

T

La dualidad es una relación simétrica, esto es, si el problema D es el

dual del problema P, entonces P es el dual de D. Para comprobar esto, se

16
escribe el problema dual anterior como un problema de minimización con

restricciones de la forma >=.

Minimizar

z  bT y

Sujeto a

 AT y   c
y0

Entonces, su dual es maximizar

z  cT x

Sujeto a

 Ax   b
x0

que es equivalente al problema primal original.

(Hillier,F.,Lieberman,G.,2010,p.180)

Teorema 5

Sea P un problema primal de programación lineal, y D su dual. Sea x

una solución factible de P e y una solución factible de D. Entonces (Castillo

E., et al, 2002, p.89)

bT y  c T x

Teorema 6

Dados un par de problemas primal – dual, si uno de ellos admite

solución óptima, entonces el otro también la admite y los respectivos

valores óptimos son iguales.

17
 El análisis de sensibilidad consiste en determinar cuál es el rango de

variación de los parámetros del problema de modo que la base óptima

encontrada siga siendo óptima.

Consideremos la forma estándar Máx (o Mín) z  cT x

Ax  ó  b
x0

Sea B la base óptima, analizando la variación del parámetro b y c, de

modo que B siga siendo óptima.

1
Para ello se debe verificar, la factibilidad xB  B b  0 y la

1
optimalidad cN  cN  cB B N  0 (Taha,A.,2012,p.80)

18
IV. Objetivos

IV.1.Objetivo General

Determinar la solución óptima del problema de minimización de

costos y sus contenidos grasos de un menú completo, servidas en el

Hospital Nacional Cayetano Heredia.

IV.2. Objetivos específicos

1. Determinar la factibilidad y optimalidad del problema de

programación lineal en el entorno del problema de las dietas.

2. Analizar el beneficio, a través de un análisis pos óptimo de la

solución óptima hallada.

19
V. Metodología
Se analizan dos casos:

V.1. Caso 1

V.1.1 Definición del problema de interés.

Para ilustrar el problema de interés se analiza un sistema

de tres variables con dos restricciones, desarrollado por el

método simplex matricial y tabla.

El problema de programación lineal consiste en una

función objetivo lineal que será minimizada, sujeta a ciertas

restricciones en forma de desigualdades.

Función Objetivo: min z  18 y1  42 y2  24 y3

2 y1  2 y2  3 y3  3
s.a: y1  3 y2  y3  2
y1 , y2 , y3  0

V.1.2 Desarrollo de un procedimiento basado en el método simplex

matricial.

Debido a que el problema de programación lineal es un

sistema de tres variables con 2 restricciones, usando el método

simplex dual (tabla primal - dual), se convertirá en un sistema

de 2 variables y tres restricciones, lo cual es más sencillo para su

desarrollo.

20
Lo que se tiene:

Primal y1 y2 y3 

Dual

x1 2 2 3 3

x2 1 3 1 2

 18 42 24

Función Objetivo: máx z  3x1  2 x2

2 x1  x2  18
2 x1  3 x2  42
s.a: 3 x  x  24
1 2

x1 , x2  0

Para el método simplex matricial, se transcribe tanto la

función objetivo como las restricciones en un sistema matricial.

Lo cual sería

cT  3 2 0 0 0
2 1 1 0 0  18 
A  2 3 0 1 0; xT  x1 x2 h1 h2 h3 ; b  42
3 1 0 0 1  24

Partiremos de una base inicial e iremos pasando en

sucesivas iteraciones por bases hasta alcanzar el óptimo.

Sea la base inicial B1 formada por las columnas h1, h2, h3

de la matriz A, una vez formada la base inicial, se halla su

1
inversa que es B1

21
 Luego se determina las variables x B1 , y x1 , y x2 para

poder encontrar los criterios óptimos z x1  cx1 y z x2  cx2

1 0 0 1 0 0 18 
B1  0 1 0;  0 1 0; xB1  B1 b  42
1 1
B1
0 0 1 0 0 1 24

1 0 0 2 2  2
y x1  B1 x1  0 1 0 2  2  z x1  cB1 y x1  0 0 02  0
1

0 0 1 3  3  3 

1 0 0 1  1  1 
y x2  B1 x2  0 1 0 3  3  z x2  cB1 y x2  0 0 03  0
1

0 0 1 1  1  1 

z x1  c x1  0  3  3
z x2  c x2  0  2  2

Como los criterios óptimos son negativos, entonces se

introduce el criterio de entrada, lo cual es hallar el

 
max z x1  cx1 ; z x2  cx2  3;2  3 esto quiere decir que

entra x1 a la base y el criterio de salida que es el


h h h   18 42 24 
min  1 , 2 , 3    , ,   8
 y y y  2 2 3
 x11 x12 x13 

esto quiere decir que deja h3 a la base.

Por lo tanto
18 
z  cB1 xB1  0 0 042  0
24

22
 Realizando entonces la primera iteración con la base B2

formada por las columnas h1, h2, x1 de la matriz A, una vez

1
formada la base, se halla su inversa que es B2

Luego se determina las variables xB2 , y x2 , yh3 para

poder encontrar los criterios óptimos z x2  cx2 y zh3  ch3

1 0 2  1 0  0,6667 2 
B2  0 1 2 ; B2  0 1  0,6667; xB2  B2 b  26
1 1

0 0 3 0 0 0,3333  8 

1 0  0,6667  1  0,333
y x2  B2 x2  0 1  0,6667  3  2,333 
1

0 0 0,3333  1  0,333

0,333
z x2  cB2 y x2  0 0 32,333  0,999
0,333
1 0  0,6667  0  0,6667 
yh3  B2 h3  0 1  0,6667  0   0,6667  
1

0 0 0,3333  1  0,3333 

 0,6667 
z h3  cB2 yh3  0 0 3 0,6667   0,9999
0,3333 

z x2  cx2  0,999  2  1,001

z h3  ch3  0,999  0  0,999

23
 Como los criterios óptimos son negativos, entonces se

introduce el criterio de entrada, lo cual es hallar el

 
max z x2  cx2 ; zh3  ch3  1,001 esto quiere decir que

entra x2 a la base y el criterio de salida que es el


 h h x 
  2 26 8 
min  1 , 2 , 1  , , 6
 
 y y y  0,333 2,333 0,333 
 x21 x22 x23

esto quiere decir que deja h1 a la base.

2 
 
Por lo tanto z  cB2 xB2  0 0 326  24
8 

Realizando la segunda iteración con la base B3 formada

por las columnas x2, h2, x1 de la matriz A, una vez formada la

1
base, se halla su inversa que es B3

Luego se determina las variables xB3 , yh1 , yh3 para

poder encontrar los criterios óptimos zh1  ch1 y zh3  ch3

1 0 2 3 0  2 6 
B3  3 1 2 ;   7 1 4 ; xB3  B3 b  12
1 1
B3
1 0 3   1 0 1  6 

24
  3 0  2 1  3 
yh1  B3 h1   7 1 4  0   7  
1

 1 0 1  0  1 

3 
z h1  cB3 yh1  2 0 3 7   3
 1 
 3 0  2  0    2 
yh3  B3 h3   7 1 4  0  4  
1

 1 0 1  1  1 

 2
z h3  cB3 yh3  2 0 34   1
1 

z h1  ch1  3  0  3
z h3  ch3  1  0  1

Como en los criterios óptimos existe todavía valores

negativos, entonces se introduce el criterio de entrada, lo cual es

 
hallar el max zh1  ch1 ; zh3  ch3  1 esto quiere decir que

entra h3 a la base y el criterio de salida que es el


x h x 
  6 12 6 
min  2 , 2 , 1  , , 3
 y y y    2 4 1
 h31 h32 h33 

esto quiere decir que deja h2 a la base.

6 
 
Por lo tanto z  cB3 xB3  2 0 312  30
6 

25
 Vemos que cada paso que realiza la iteración mejora la

solución.

Realizando la tercera iteración con la base B4 formada

por las columnas x2, h3, x1 de la matriz A, una vez formada la

1
base, se halla su inversa que es B4

Luego se determina las variables xB4 , yh1 , yh2 para

poder encontrar los criterios óptimos zh1  ch1 y zh2  ch2

1 0 2   0,5 0,5 0  12

B4  3 0 2; B4   1,75 0,25 1 ; xB4  B4 b  3 
1 1

1 1 3  0,75  0,25 0 3 

 0,5 0,5 0  1   0,5 

yh1  B4 h1   1,75 0,25 1  0   1,75 
1

0,75  0,25 0 0 0,75 

 0,5 
z h1  cB4 yh1  2 0 3 1,75  1,25
0,75 
 0,5 0,5 0  0 0,5 
yh2  B4 h2   1,75 0,25 1  1   0,25  
1

0,75  0,25 0 0  0,25

0,5 
z h2  c B4 yh2  2 0 30,25   0,25
 0,25

z h1  ch1  1,25  0  1,25

z h2  ch2  0,25  0  0,25

26
 Observamos que ya no es posible mejorar por el criterio

 
óptimo j  J z j  c j  0

12
Por lo tanto z  cB4 xB 4  2 0 33   33
3 

Ahora es importante el estudio del rango de variación de

los parámetros b (factibilidad) y c (optimalidad) de modo que B

siga siendo óptima.

2 1 0 
B  2 3 0
Sea B la base óptima

3 1 1 

Hallando su inversa tenemos

3 1 
 4 4 0
 

B  0
1 1 1
 2 2 
 7 1 
 1
 4 4 

Hallando la factibilidad: B 1b  0

Para el parámetro b1 se calcula de la forma siguiente:

3 1 
 4 4 0
  b1 

B 1   0  42  0  14  b1  19,71
1 1
2 2 
  7 1  24
 1
 4 4 

27
 De igual forma para el parámetro b2:

3 1 
 4 4 0
  18 

B 1   0  b2   0  30  b2  54
1 1
2 2 
  7 1  24
 1
 4 4 

Y el parámetro b3:

3 1 
 4 4 0
  18 

B  0  42  0  b3  21
1 1 1
2 2 
  7 1  b3 
 1
 4 4 

Hallando la optimalidad: c N  c N  cB B 1 N  0

Para el parámetro c1: x1 es la básica, entonces tenemos

que considerar todos los costos reducidos.

c3 , c4   c3 , c4   c1 , c2 , c5 B 1 N  0

 3 1 
 4 4 0
  1 0 
1 1 
 0,0    c1 ,2,0 0 0 1   0 
4
 c1  4
 2 2  3
  7 1  0 0
 1
 4 4 

Para el parámetro c2: x2 es la básica, entonces tenemos

que considerar todos los costos reducidos.

28
 c3 , c4   c3 , c4   c1 , c2 , c5 B 1 N  0
 3 1 
 4 4 0
  1 0 
1 1 
 0,0    3,c2 ,0  0 0 1   0 
3 9
 c2 
 2 2  2 2
  7 1  0 0
 1
 4 4 

V.1.3 Desarrollo de un procedimiento basado en el método simplex

tabla

Para el método simplex tabla, se escribe la función

objetivo como una igualdad a cero sumando las variables de

holgura hi con coeficiente cero y conservando positivo el

coeficiente de z.
z  3x1  2 x2  0h1  0h2  0h3  0

Luego se llena una tabla de la siguiente forma:

En la primera fila se escribe las variables básicas; la

función objetivo z; las variables originales del modelo, seguidas

de las variables de holgura y por último solución.

En la segunda fila contiene los coeficientes,

correspondientes a cada variable original, de la función objetivo

y con el coeficiente cero para todas las variables de holgura y la

solución.

En la primera columna y a partir de la tercera fila se

coloca verticalmente todas las variables de holgura empleadas.

También a partir de la tercera fila se colocan los coeficientes de

cada una de las restricciones en la columna de la variable

29
correspondiente (esto genera los componentes de una matriz

identidad en las variables de holgura).

En la columna solución se colocan los términos

independientes y además identificamos un elemento pivote.

Variables z x1 x2 h1 h2 h3 Solución

Básicas

z 1 3 2 0 0 0 0

h1 0 2 1 1 0 0 18
0 2 3 0 1 0 42
h2
3 1 0 0 1
0 24
h3

Se determina el primer elemento pivote. El elemento

pivote se obtiene de los coeficientes de la fila z que le asignamos

con el nombre de Ro, donde se toma el menor valor y se

selecciona toda la columna, se divide la columna solución entre

el elemento correspondiente de la columna seleccionada, y de

los resultados de la división se selecciona el menor valor

positivo y toda fila asociada a este valor.

Las divisiones entre cero o entre valores negativos no se

toman en cuenta. Si todas son negativas o indeterminadas el

problema no tiene solución y el proceso termina. El elemento

pivote con el método de eliminación de Gauss-Jordan usando las

30
operaciones de filas se convierte en 1, y todos los elementos de

es columna se convierte en cero.

VB z x1 x2 h1 h2 h3 S

R0 z 1 -3 -2 0 0 0 0

R1 h1 0 2 1 1 0 0 18 18/2

R2 h2 0 2 3 0 1 0 42 42/2

R3 h3 0 3 1 0 0 1 24 24/3

1
R3
Operaciones de renglón, 
 3

VB z x1 x2 h1 h2 h3 S

R0 z 1 -3 -2 0 0 0 0

R1 h1 0 2 1 1 0 0 18

R2 h2 0 2 3 0 1 0 42

R3 h3 0 1 1/3 0 0 1/3 8

Operaciones de renglón,

0  3 R3 1  2 R3 2  2 R3
R 
, R , R 

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 -1 0 0 1 24

R1 h1 0 0 1/3 1 0 -2/3 2

R2 h2 0 0 7/3 0 1 -2/3 26

R3 h3 0 1 1/3 0 0 1/3 8

31
 Se determina el segundo elemento pivote, debido a que

todavía en el Ro presenta valores negativos.

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 -1 0 0 1 24

R1 h1 0 0 1/3 1 0 -2/3 2 2/(1/3)

R2 h2 0 0 7/3 0 1 -2/3 26 26/(7/3)

R3 h3 0 1 1/3 0 0 1/3 8 8/(1/3)

Operaciones de renglón, 3R

1

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 -1 0 0 1 24

R1 h1 0 0 1 3 0 -2 6

R2 h2 0 0 7/3 0 1 -2/3 26

R3 h3 0 1 1/3 0 0 1/3 8

Operaciones de renglón,

7 1
R2  R1 R3  R1
R0  R1
, 
, 
 3 3

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 0 3 0 -1 30

R1 h1 0 0 1 3 0 -2 6

R2 h2 0 0 0 -7 1 4 12

R3 h3 0 1 0 -1 0 1 6

32
 Se determina el tercer elemento pivote, debido a que sigue

presentando valor negativo en Ro.

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 0 3 0 -1 30

R1 h1 0 0 1 3 0 -2 6 NN

R2 h2 0 0 0 -7 1 4 12 12/4

R3 h3 0 1 0 -1 0 1 6 6

1
R2
Operaciones de renglón, 
 4

VB z x1 x2 h1 h2 h3 S

R0 z 1 0 0 3 0 -1 30

R1 h1 0 0 1 3 0 -2 6

R2 h2 0 0 0 -7/4 ¼ 1 3

R3 h3 0 1 0 -1 0 1 6

Operaciones de renglón,

0  R2 1  2 R2 3  R2
R , R 
, R 
Vemos que aquí termina la iteración, debido a que todos

los coeficientes de la fila z, son valores mayores o iguales a

cero.

33
 VB z x1 x2 h1 h2 h3 S

R0 z 1 0 0 5/4 1/4 0 33

R1 h1 0 0 1 -1/2 1/2 0 12

R2 h2 0 0 0 -7/4 1/4 1 3

R3 h3 0 1 0 3/4 -1/4 0 3

El problema termina, ya que en R0 todos los coeficientes

son positivos. Observamos que la función objetivo es 33, x1 = 3

y x2 = 12.

Para analizar las sensibilidades de b y c, se determina con

la última tabla desarrollada del método simple tabla.

Sensibilidad Independiente

Para calcular la sensibilidad de b1 primero se deberá

determinar el valor de  y para eso se determina la fila donde

la variable x1 , x2 , h3 y z es uno, en esa fila el valor de la

solución se le suma a la misma fila el valor de la columna h1 .

Se resuelve todas las desigualdades mayores e iguales a cero.

x1 3
3 
4

x2 1 0
12  
2

h3 7
3 
4

z 5
33  
4

34
 Lo que se obtiene    4;1,71 Luego se cambia 18 por

18   , resultando b1  14;19,71

Para calcular la sensibilidad de b2 primero se deberá

determinar el valor de  y para eso se determina la fila donde

la variable x1 , x2 , h3 y z es uno, en esa fila el valor de la

solución se le suma a la misma fila el valor de la columna h2 .

Se resuelve todas las desigualdades mayores e iguales a cero.

x1 1
3 
4

x2 1 0
12  
2

h3 1
3 
4

z 1
33  
4

Lo que se obtiene    12;12 Luego se cambia 42 por

42   , resultando b2  30;54

Para calcular la sensibilidad de b3 primero se deberá

determinar el valor de  y para eso se determina la fila donde

la variable x1 , x2 , h3 y z es uno, en esa fila el valor de la

solución se le suma a la misma fila el valor de la columna h3 .

Se resuelve todas las desigualdades mayores e iguales a

cero.

35
 x1 3  0( )

x2 12  0( )
0
h3 3  1( )

z 33  0( )

Lo que se obtiene    3;  Luego se cambia 24 por

24   , resultando b3  21; 

Sensibilidad Función Objetivo

Para calcular la sensibilidad de c1 primero se deberá

determinar el valor de  y para eso se determina la fila donde

la variable x1 y z son unos, en esa fila se suma los dos valores

de la misma posición de la columna h1 y h2 . Se resuelve todas

las desigualdades mayores e iguales a cero.

z x1 x2 h1 h2 h3 S

1 1 0 5 3 1 1 0 33  3
   
4 4 4 4

0 0

5
Lo que se obtiene    ;1 Luego se cambia 3 por
 3 

3   , resultando c1  1,33;4

Para calcular la sensibilidad de c1 primero se deberá

determinar el valor de  y para eso se determina la fila donde

la variable x2 y z son unos, en esa fila se suma los dos valores

36
 de la misma posición de la columna h1 y h2 . Se resuelve todas

las desigualdades mayores e iguales a cero.

z x1 x2 h1 h2 h3 S

1 0 1 5 1 1 1 0 33  12
   
4 2 4 2

0 0

1
Lo que se obtiene    ;2,5 Luego se cambia 2 por
2 

2   , resultando c2  1,5;4,5

V.2 Caso 2

V.2.1 Definición del problema de interés.

En este caso se va a subdividir en 2 problemas de interés.

Caso 2 A

Minimizar el costo de una comida completa, con los

requerimientos nutricionales de una dieta saludable.

Caso 2 B

Minimizar el contenido de grasa de una comida completa,

con los requerimientos nutricionales de una dieta saludable.

37
 V.2.2 Recolección de datos.

Los datos de la tabla1 es el menú del desayuno con sus

respectivos nutrientes proporcionados por el HNCH.

Tabla 1 Lista de alimentos servidos en el desayuno con sus respectivos nutrientes.

Fuente: Hospital Nacional Cayetano Heredia

38
 Los datos de la tabla 2 es el menú del almuerzo con sus respectivos

nutrientes proporcionados por el HNCH.

Tabla 2 Lista de alimentos servidos en el almuerzo con sus respectivos nutrientes.

39
 Los datos de la tabla3 es el menú de la cena con sus respectivos

nutrientes proporcionados por el HNCH.

Tabla 3 Lista de alimentos servidos en la cena con sus respectivos nutrientes.

Fuente: Hospital Nacional Cayetano Heredia

40
 Los datos de la tabla 4 muestra la conversión de los alimentos cocidos

a crudos.

Tabla 4 Lista de alimentos con el factor de conversión de alimentos cocidos a

crudos.

Peso Neto (g) Factor de Peso

Alimento Tamaño de conversión de peso Bruto (g)

porción de alimentos cocidos

a crudo[16][17]

Desayuno

Leche evap. 100 100

Quínua con Quinua 15 0.23 3.45

durazno Durazno 20 20

Azúcar rubia 15 15

Canela 0.5 0.5

Clavo 0.5 0.5

Jugo de Papaya 100 100

papaya con Plátano de isla 20 20

plátano Azúcar rubia 15 15

Pan con huevo Pan francés 60 60

duro y palta Huevo 50 1.04 52

Palta 40 40

Almuerzo

Sopa de Sémola 15 0.23 3.45

sémola Pollo 20 1.48 29.6

Apio 15 0.99 14.85

Poro 15 0.99 14.85

Nabo 15 1.07 16.05

Zapallo 30 1.14 34.2

Zanahoria 15 1.01 15.15

Sal 2 2

Pescado a la Pescado 100 1.15 115

chorrillana (jurel)

con yuca Cebolla 40 1.59 63.6

Tomate 30 1.59 47.7

41
 Ají panca 1 1

Vinagre 5 5

Pimienta 0.5 0.5

Comino 0.5 0.5

Arroz 100 0.51 51

Aceite 15 15

Sal 2 2

Yuca 100 0.98 98

Ajos 2 1.01 2.02

Mandarina 150 150

Limonada Limón 10 10

Azúcar 15 15

Cena

Adobo de Chancho 100 1.25 125

cerdo con Aji panca 5 5

camote Cebolla 20 1.59 31.8

Pan francés 10 10

Camote 100 0.98 98

Arroz 100 0.51 51

Sal 2 2

Ajos 2 1.01 2.02

Aceite 5 5

Gelatina 30 30

Maracuyá Maracuyá 30 30

Azúcar rubia 20 20

Fuente:

http://www.ins.gob.pe/repositorioaps/0/5/jer/doc_tec_norm/TAFERA_2_compressed.pdf

42
 Los datos de la tabla 5 muestran la lista de precios del mercado

mayorista con fecha octubre del 2017.

Tabla 5 Lista de precios del mercado mayorista.

Precio por kg, lt, unidad.

Alimento (según mercado mayorista)[15]

Desayuno

Leche evap. 2.77/lata (400g)

Quínua con Quinua 5.75

durazno Durazno 2.90

Azúcar rubia 2.63

Canela 4.7/20g

Clavo 3.6/10g

Jugo de Papaya 1.48

papaya con Plátano de isla 1.88

plátano Azúcar rubia 2.63

Pan con huevo Pan francés 0.2/30g

duro y palta Huevo 4.38

Palta 3.30

Almuerzo

Sopa de Sémola 7.3

sémola Pollo 5.38

Apio 1.54

Poro 1.54

Nabo 1.52

Zapallo 1.08

Zanahoria 0.88

Sal 0.9

Pescado a la Pescado 6.53

chorrillana (jurel)

con yuca Cebolla 1.88

Tomate 1.94

Ají panca 8

43
 Vinagre 2.6/0.5lt

Pimienta 6.4/60g

Comino 3.59/20g

Arroz 2.42

Aceite 6.18/lt

Sal 0.9

Yuca 1.35

Ajos 7.18

Mandarina 1.18

Limonada Limón 1.01

Azúcar 2.63

Cena

Adobo de Chancho 13.9

cerdo con Aji panca 8

camote Cebolla 1.88

Pan francés 0.2/30g

Camote 0.93

Arroz 2.42

Sal 0.9

Ajos 7.18

Aceite 6.18

Gelatina 2.10/250g

Maracuyá Maracuyá 1.57

Azúcar rubia 2.63

Fuente: http://sistemas.minag.gob.pe/sisap/portal/

44
 Los datos de la tabla 6 muestran las porciones de los alimentos al

consumir por día.

Tabla 6 Lista de porciones por alimento.

Alimento Límite

(porción/día)[18]

Desayuno

Leche evap. 4

Quínua con durazno 3

Jugo de papaya con 3

plátano

Pan con huevo duro y 3

palta

Almuerzo

Sopa de sémola 2

Pescado a la 2

chorrillana con yuca

Mandarina 4

Limonada 4

Cena

Adobo de cerdo con 2

camote

Gelatina 4

Maracuyá 4

Fuente: http://www.fao.org/docrep/014/am401s/am401s02.pdf

45
V.2.3 Formulación y planteamiento del modelo matemático.

Una vez obtenido los pesos brutos de los alimentos como

se observa en la tabla 4, conjuntamente con la tabla 5 de los

precios obtenidos por el mercado mayorista, se calcula el precio

por porción de cada uno de los alimentos, mediante la regla de

tres simple.

Mientras que los productos como vinagre y aceite las

cuales sus unidades están en gramos, para obtener sus

m
respectivos precios, se tuvo que aplicar la fórmula   y usar
V

como dato sus respectivas densidades.

Por ejemplo, la densidad del vinagre es   1.0056 g / cm 3 ,

se tiene como dato la masa del vinagre que es m= 5g aplicando

m 5
 tenemos V   4.97215cm 3 ahora convirtiendo
V 1.0056

cm3 a litro, se tiene 1 lt es 1000cm 3 por lo tanto

4.97215cm 3 es 0.0497215lt como el medio litro de vinagre es

2.6 soles, entonces 0.0497215 lt es 0.2585518 soles.

46
Los precios calculados por porción se encuentran en la tabla 7.

Tabla 7 Lista de precio por porción.

Alimento Precio

(S/. /porción)

Desayuno

Leche evap. 0.6925

Quínua con Quinua 0.01983

durazno Durazno 0.0583

Azúcar rubia 0.0374

Canela 0.1175

Clavo 0.09

0.32303

Jugo de Papaya 0.148

papaya con Plátano de isla 0.038

plátano Azúcar rubia 0.0675

0.2535

Pan con huevo Pan francés 0.4

duro y palta Huevo 0.23

Palta 0.132

0.762

Almuerzo

Sopa de Sémola 0.025

sémola Pollo 0.1592

Apio 0.462

Poro 0.462

Nabo 0.456

Zapallo 0.03693

Zanahoria 0.01333

Sal 0.0018

1.61626

Pescado a la Pescado 0.75095

chorrillana (jurel)

con yuca Cebolla 0.11956

Tomate 0.09254

47
 Ají panca 0.008

Vinagre 0.2585518

Pimienta 0.1175

Comino 0.09

Arroz 0.12342

Aceite 0.100734

Sal 0.0018

Yuca 0.1323

Ajos 0.0145

1.8098558

Mandarina 0.177

Limonada Limón 0.0101

Azúcar 0.03945

0.0495

Cena

Adobo de Chancho 1.7375

cerdo con Aji panca 0.04

camote Cebolla 0.0598

Pan francés 0.067

Camote 0.0744

Arroz 0.12342

Sal 0.0018

Ajos 0.0145

Aceite 0.0341

2.15252

Gelatina 0.252

Maracuyá Maracuyá 0.0471

Azúcar rubia 0.0526

0.0997

48
Tabla 8 Consolidado de los alimentos con sus requerimientos nutricionales.

Formulación y planteamiento del problema de programación lineal caso 2 A

Para conocer el costo mínimo de una dieta saludable de 2000 kcal, es

necesario conocer cuál sería la cantidad mínima y máxima que puede ingerir

una persona en una comida diaria. Dado lo anterior, para el estudio se

identifica cuánto sería la cantidad mínima y la máxima de nutrientes que se

deben consumir en el día, para así establecer un intervalo que no sea

perjudicial para la salud por consecuencia de excesos o deficiencia de

49
nutrientes. Los intervalos en porcentajes de los requerimientos nutricionales

se encuentran en la tabla 1, 2 y 3.

El menú del día consiste en desayuno, almuerzo y cena. Se ha

determinado que la comida debe proporcionar como mínimo 2000kcal de

energía, 75g de proteínas, 62g de lípidos, 325 g de carbohidratos, 17.8 g de

grasa poliinsaturada, 4.4g de grasa monoinsaturada, 25g de fibra, 600 ug de

vitamina A y 45 mg de vitamina C. Las cantidades máximas se encuentran

en la tabla 1, 2 y 3; los intervalos en porcentajes de los requerimientos

nutricionales.

Para evitar la demasiada cantidad de porción de comida, no debe

incluirse en ella más de 4 porciones de leche evaporada, 3 porciones de

quinua con durazno, 3 porciones de jugo de papaya con plátano, 3 porciones

de pan con huevo y palta, 2 porciones de sopa de sémola, 2 porciones de

pescado a la chorrillana, 4 porciones de mandarina, 2 porciones de adobo

con cerdo y camote, 4 porciones de gelatina y 4 porciones de maracuyá.

Los precios calculados y los nutrientes para cada tipo de comida se

encuentran en la tabla 7.

Además la cantidad de agua presente en los alimentos debe ser como

mínimo 1.5 lt de agua totales consumidos por día, y como máximo 2 lt de

agua por día.

En la porción de leche 0.2 lt es agua, en la porción de jugo de papaya

con plátano 0.2 lt es agua, en la sopa de sémola 0.1 lt es agua, en la porción

de limonada 0.25 lt es agua, en la porción de gelatina 0.125 lt es agua, en la

porción de maracuyá 0.25 lt es agua.

50
 Se desea determinar qué cantidad de cada tipo de comida se debe

incluir en una dieta saludable de 2000kcal para asegurar un mínimo costo.

Primero, se define las variables que intervienen en el problema.

xj= Número de porción de alimentos a consumir durante el día, donde

x1 =leche evaporada

x2 =quinua con durazno

x3 =jugo de papaya con plátano

x4 =pan con huevo duro y palta

x5 =sopa de sémola

x6 =pescado a la chorrillana

x7 =mandarina

x8 =limonada

x9 =adobo con cerdo y camote

x10 =gelatina

x11 =maracuyá

Como el objetivo es minimizar el costo, se plantea la función objetivo

con los precios obtenidos en la tabla 7.

Min Z= 0.6925 x1 + 0.32303 x2 + 0.2535 x3 + 0.762 x4 + 1.61626 x5 +

1.8098558 x6 + 0.177 x7 + 0.0495 x8 + 2.15252 x9 + 0.252 x10 +

0.0997 x11

51
En seguida se plantea las restricciones de los nutrientes, obtenidos en la tabla 8.

133x1  122.26 x 2  107.2 x3  289.1x 4  99.55 x5  825.6 x 6  52.5 x 7  60.6 x8  764.08 x9  166.32 x10  96.10 x11  2000
6.3 x  1.5 x  0.5 x  12.47 x  6.35 x  33.13 x  0.9 x  0.05 x  27.03 x  5.4 x  0.27 x  75
 1 2 3 4 5 6 7 8 9 10 11

7.7 x1  0.43 x 2  0.18 x3  9.32 x 4  1.1x5  20.46 x 6  0.45 x 7  0.02 x8  21.33 x9  0.03 x11  62

10.9 x1  29.22 x 2  27.5 x3  40.88 x 4  17.46 x5  124.78 x 6  12.9 x 7  15.85 x8  115.82 x9  45.9 x10  24.27 x11  325

0.34 x1  0.02 x3  1.88 x 4  60.12 x5  14.80 x 6  5.97 x9  17.8

2.36 x1  0.01x3  6.25 x 4  0.3 x5  1.22 x 6  7.52 x9  4.4
0.24 x1  0.6 x 2  2.68 x3  9.32 x 4  1.05 x5  2.35 x 6  0.75 x 7  2.5 x9  0.6 x11  25

65 x1  3.2 x 2 6.1x3  2.8 x 4  165.3 x5  26.235 x 6  51x 7  0.0 x5 8  68.2 x9  x11  600
3.06 x  48.54 x  3.32 x  10.48 x  58.1755 x  73.05 x  11.05 x  17.332 x  0.65 x  45
 2 3 4 5 6 7 8 9 11

0.2 x1  0.2 x3  0.1x5  0.25 x8  0.125 x10  0.25 x11  1.5



Por último se plantea los límites de las porciones:

0  x1  4
0  x2  3

0  x3  3

0  x4  3
0  x5  2


0  x6  2
0  x7  4

0  x8  4

0  x9  2
0  x10  4


0  x11  4

52
Formulación y planteamiento del problema de programación lineal caso 2 B

El menú del día consiste en desayuno, almuerzo y cena. Se ha

determinado que la comida debe proporcionar como mínimo 2000kcal de

energía, 75g de proteínas, 325 g de carbohidratos, 17.8 g de grasa

poliinsaturada, 4.4g de grasa monoinsaturada, 25g de fibra, 600 ug de

vitamina A y 45 mg de vitamina C. Las cantidades máximas se encuentran

en la tabla 1, 2 y 3; los intervalos en porcentajes de los requerimientos

nutricionales.

Para evitar la demasiada cantidad de porción de comida, no debe

incluirse en ella más de 4 porciones de leche evaporada, 3 porciones de

quinua con durazno, 3 porciones de jugo de papaya con plátano, 3 porciones

de pan con huevo y palta, 2 porciones de sopa de sémola, 2 porciones de

pescado a la chorrillana, 4 porciones de mandarina, 2 porciones de adobo

con cerdo y camote, 4 porciones de gelatina y 4 porciones de maracuyá.

Los contenidos grasos y los nutrientes para cada tipo de comida se

encuentran en la tabla 8.

Además la cantidad de agua presente en los alimentos debe ser como

mínimo 1.5 lt de agua totales consumidos por día, y como máximo 2 lt de

agua por día.

En la porción de leche 0.2 lt es agua, en la porción de jugo de papaya

con plátano 0.2 lt es agua, en la sopa de sémola 0.1 lt es agua, en la porción

de limonada 0.25 lt es agua, en la porción de gelatina 0.125 lt es agua, en la

porción de maracuyá 0.25 lt es agua.

53
 Se desea determinar qué cantidad de cada tipo de comida se debe

incluir en una dieta saludable de 2000kcal para asegurar una mínima

cantidad de grasa.

Primero, se define las variables que intervienen en el problema.

xj= Número de porción de alimentos a consumir durante el día, donde

x1 =leche evaporada

x2 =quinua con durazno

x3 =jugo de papaya con plátano

x4 =pan con huevo duro y palta

x5 =sopa de sémola

x6 =pescado a la chorrillana

x7 =mandarina

x8 =limonada

x9 =adobo con cerdo y camote

x10 =gelatina

x11 =maracuyá

Como el objetivo es minimizar el contenido de grasas de la dieta, se

plantea la función objetivo con la cantidad de grasa presentes en la tabla 8.

Min Z= 7.7 x1 + 0.42 x2 + 0.18 x3 + 9.32 x4 + 1.1 x5 + 20.46 x6 + 0.45

x7 + 0.02 x8 + 21.33 x9 + 0.03 x11

En seguida se plantea las restricciones de los nutrientes, presentes en

la tabla 8.

54
133x1  122.26 x 2  107.2 x3  289.1x 4  99.55 x5  825.6 x 6  52.5 x 7  60.6 x8  764.08 x9  166.32 x10  96.10 x11  2000
6.3x  1.5 x  0.5 x  12.47 x  6.35 x  33.13x  0.9 x  0.05 x  27.03x  5.4 x  0.27 x  75
 1 2 3 4 5 6 7 8 9 10 11

10.9 x1  29.22 x 2  27.5 x3  40.88 x 4  17.46 x5  124.78 x 6  12.9 x 7  15.85 x8  115.82 x9  45.9 x10  24.27 x11  325

0.34 x1  0.02 x3  1.88 x 4  60.12 x5  14.80 x 6  5.97 x9  17.8

2.36 x1  0.01x3  6.25 x 4  0.3x5  1.22 x 6  7.52 x9  4.4
0.24 x  0.6 x  2.68 x  9.32 x  1.05 x  2.35 x  0.75 x  2.5 x  0.6 x  25
 1 2 3 4 5 6 7 9 11

65 x1  3.2 x 2 6.1x3  2.8 x 4  165.3x5  26.235 x 6  51x 7  0.0 x5 8  68.2 x9  x11  600

3.06 x 2  48.54 x3  3.32 x 4  10.48 x5  58.1755 x 6  73.05 x 7  11.05 x8  17.332 x9  0.65 x11  45

0.2 x1  0.2 x3  0.1x5  0.25 x8  0.125 x10  0.25 x11  1.5

Por último se plantea los límites de las porciones:

0  x1  4
0  x2  3

0  x3  3

0  x4  3
0  x5  2


0  x6  2
0  x7  4

0  x8  4

0  x9  2
0  x10  4


0  x11  4

55
VI. Resultados
Caso 1 USANDO EL PROGRAMA LINGO

Caso 1 USANDO EL PROGRAMA EXCEL

56
 Aquí observamos que el valor óptimo se alcanza cuando las variables

x1  3 y x2  12 . Si reemplazo esta solución a la restricción 1, da 18; a la

restricción 2, da 42 y a la restricción 3, da 21. Esto hace que la variable de

holgura de las dos primeras restricciones sean cero, mientras que la

restricción 3 su variable de holgura es 3, es decir que hay un recurso en

carencia de 3 unidades que no se está usando.

En el costo reducido o costo de oportunidad de una variable x que

toma el valor 0 es lo que debe mejorar el coeficiente x en la función objetivo

para que el valor de x pase a ser no nulo. Si el problema es de minimización

la variable debería disminuir. Las variables que son no nulas tienen un costo

reducido nulo, ya que es el óptimo.

En el problema observamos que, si aumentamos en una unidad al

término independiente de la restricción 1, su precio sombra es de 1.25, esto

quiere decir que el valor de la función objetivo aumentaría de 33 a 34.5 y

sus respectivos x1  3.75 y x2  11.5 . De igual forma, si aumentamos en

una unidad al término independiente de la restricción 2, su precio sombra es

de 0.25, esto quiere decir que el valor de la función objetivo aumentaría de

33 a 33.25 y sus respectivos x1  2.75 y x2  12.5 . Finalmente si

aumentamos en una unidad al término independiente de la restricción 3, su

precio sombra es de 0, lo que significa que el resultado de la función

objetivo no varía.

57
 Para que los precios sombra sean válidas, los intervalos permitidos de

los términos independientes son:

b1  14;19.71, b2  30;54, b3  21; 

Para que no cambie la solución óptima de las variables, pero si la

función objetivo, los intervalos permitidos para los coeficientes de la

función objetivo son: c1  1.33;4, c2  1.5;4.5

58
Caso 2 A USANDO EL PROGRAMA LINGO

59
Caso 2 A USANDO EL PROGRAMA EXCEL

60
 Según los resultados, observamos que la columna value (LINGO) o

Final valor (Excel), contiene el valor óptimo de cada variable, está tomando

en cuenta 3 porciones de jugo de papaya con plátano, 3 porciones de pan

con huevo y palta, 1 porción de sopa de sémola, 2 porciones de pescado a la

chorrillana, 4 mandarina, 1 porción de adobo con camote y 4 porción de

maracuyá. La cual nos da un costo mínimo de 13.041 soles.

En la columna del costo reducido, vemos que la leche disminuirá en

0.353743531 soles, en la función objetivo para que el costo reducido sea

nulo, lo que equivale a un valor óptimo. De la misma forma la quinua con

durazno disminuirá en 0.1338325 soles, la limonada disminuirá en 0.04819

soles, y la gelatina disminuirá en 0.252 soles.

En la columna de slack or surplus, se observa que hay un excedente o

sobrante de 2697.8 g de energía, 83.16g de proteína, 42.46 g de lípidos,

472.91 g de carbohidratos, 26.53g de grasa poliinsaturadas, 28.38 g de grasa

monoinsaturadas, 560mg de vitamina C, 4porciones de leche evaporada, 3

porciones de quinua con durazno, 0.72 porción de sopa de sémola, 4

porciones de limonada, 0.513 porción de adobo de cerdo con camote y 4

porciones de gelatina.

Si disminuimos en 1 g al término independiente a la fibra, su precio

sombra es de 0.71883 soles, esto quiere decir que la función objetivo

disminuye de 13.04067 soles a 12.3218 soles. De igual forma para la

vitamina A, si se disminuye 1 ug de vitamina A, su precio sombra es de

61
0.0052116 lo que implica una disminución de precio en la función objetivo

de 13.04067 soles a 13.0354 soles.

Nos conviene aumentar una porción de pan con huevo y palta, cuyo

precio sombra es de 1.179069, eso hace que el precio de la función objetivo

disminuya de 13.04067 soles a 11.861601 soles.

Ahora, si aumentamos una porción de leche evaporada, una porción de

quinua con durazno, una porción de sopa de sémola, una porción de

limonada y una porción de gelatina; el precio de la función objetivo no

varía, ya que su precio sombra es cero. Esto es debido a que tiene un

excedente o sobrante de 4, 3, 1, 4 y 4 porciones respectivamente.

Por lo que nos conviene aumentar simultáneamente una porción de

jugo de papaya con plátano, una porción de pan con huevo y palta, una

porción de pescado a la chorrillana, una porción de mandarina y una porción

de maracuyá, lo que nos da un precio de la función objetivo disminuido de

13.04067 soles a 10.671145 soles.

Finalmente, los intervalos permitidos de los términos independientes o

las restricciones son:

b1  0;4697.86, b2  0;158.16, b3  0;104.46, b4  0;797.913,

b5  0;44.33, b6  0;32.78, b7  21.927;26.06, b8  433.02;698.52,
b9  0;605.9

62
para que no cambie la solución óptima de las variables, pero si la función

objetivo, los intervalos permitidos para los coeficientes de la función

objetivo son:

c1  0.338; , c2  0.189; , c3  0;0.463, c4  0;1.941,

c5  0.904;1.674, c6  0;1.826, c7  0;0.805, c8  3.412; ,
c9  2.137;3.412, c10  0; , c11  0;0.437

Y para las porciones serían:

x1  0; , x2  0; , x3  1;8, x4  2;4, x5  1; , x6  1;3,

x7  2;9, x8  0; , x9  1; , x10  0; , x11  2;9

63
Caso 2 B USANDO EL PROGRAMA LINGO

64
Caso 2 B USANDO EL PROGRAMA EXCEL

65
 Según los resultados, observamos que la columna value (LINGO) o

Final valor (Excel), contiene el valor óptimo de cada variable, está tomando

en cuenta 3 porciones de quinua con durazno, 3 porciones de jugo de papaya

con plátano, 3 porción de pan con huevo y palta, 2 porciones de sopa de

sémola, 0.825 porción de pescado a la chorrillana, 4 porción de mandarina,

2 porción de adobo de cerdo con camote, 4 porción de gelatina y 4 porción

de maracuyá. La cual nos da una mínima cantidad de grasa de 93.46038g.

En la columna del costo reducido, vemos que la leche disminuirá en

7.7 g de grasa, en la función objetivo para que el costo reducido sea nulo, lo

que equivale a un óptimo valor.

En la columna de slack or surplus, se observa que hay un excedente o

sobrante de 3224.179 g de energía, 88.79987g de proteína, 669.64991 g de

carbohidratos, 12.29787g de grasa poliinsaturadas, 31.02715 g de grasa

monoinsaturadas, 132.9578ug de vitamina A, 518.2097mg de vitamina C,

4 porciones de leche evaporada, 1.174468 porción de pescado a la

chorrillana y 4 porciones de limonada.

Si disminuimos en 1 g al término independiente de la fibra, su precio

sombra es de 8.706383g, esto quiere decir que la función objetivo

disminuye de 93.46038 g a 84.753997g.

Si aumentamos una porción de quinua con durazno, su precio sombra

es de 1.659532g, eso hace que la cantidad de grasa de la función objetivo

disminuya de 93.46038 g a 91.800848g.

Finalmente, los intervalos permitidos de los términos independientes o

restricciones son:

66
 b1  0;4558.89, b2  0;142.2, b4  0;811.05, b5  0;30.1,
b6  0;35.43, b7  23.06;27.76, b8  0;732.95, b9  0;563.21

para que no cambie la solución óptima de las variables, pero si la función

objetivo, los intervalos permitidos para los coeficientes de la función

objetivo son:

c1  0; , c2  0;2.089, c3  0;5.224, c4  0;23.33,

c5  0;9.142, c6  20.05; , c7  0;6.53, c8  0; ,
c9  0;21.77, c10  0; , c11  0;5.224

Y para las porciones serían:

x1  0; , x2  0;11, x3  0;6, x4  2;3, x5  1;3, x6  1; ,

x7  1;6, x8  0; , x9  1;2, x10  0; , x11  0;7

67
VII. Discusión
1. Al plantear un problema de programación lineal, damos por aceptado

que los valores de los parámetros se conocen con certidumbre; pero en

la realidad no siempre se cumple que los valores sean los mismos

durante un largo periodo de tiempo, debido a las variaciones en los

precios de los productos que ocasionan cambios en los coeficientes de

la función objetivo.

2. Para la minimización de costo, si realizamos los siguientes ajustes

como:

Disminuir el precio de la porción leche a 0.3387 soles, disminuir el

precio de la porción de quinua con durazno a 0.1895 soles y disminuir

el precio de la porción de limonada a 0.0013 soles; disminuir 1g en

fibra y vitamina A; aumentar una porción de jugo de papaya con

plátano, una porción de pan con huevo y palta, una porción de pescado

a la chorrillana, una porción de mandarina y una porción de maracuyá

entonces el precio mínimo de la función objetivo reducirá a 9.967145

soles. Esto quiere decir, una persona puede desayunar, almorzar y

cenar con 9.98 soles por día; con un costo promedio mensual de 299.4

soles, inferior al precio de la canasta básica de alimentos.

3. Para la minimización de la cantidad de grasa, si realizamos los

siguientes ajustes como:

Eliminar la porción de leche y limonada; disminuir 1 g en fibra;

aumentar una porción de quinua con durazno, una porción de jugo de

papaya con plátano, una porción de pan con huevo y palta, una

68
porción de sopa de sémola, una porción de mandarina, una porción de

adobo de cerdo con camote y una porción de maracuyá entonces la

cantidad mínima de grasa de la función objetivo reducirá a 53.39942g.

69
VIII. Conclusiones
1. La solución óptima de minimización de costo es de 13.04067 soles,

tomando como menú completo del día; 3 porciones de jugo de

papaya con plátano, 3 porciones de pan con huevo y palta, 1

porción de sopa de sémola, 2 porciones de pescado a la chorrillana,

4 mandarina, 1 porción de adobo con camote y 4 porción de

maracuyá.

2. La solución óptima de minimizar la cantidad de grasa es de

93.46038 g, tomando como menú completo del día; 3 porciones

de quinua con durazno, 3 porciones de jugo de papaya con plátano,

3 porción de pan con huevo y palta, 2 porciones de sopa de sémola,

1 porción de pescado a la chorrillana, 4 porción de mandarina, 2

porción de adobo de cerdo con camote, 4 porción de gelatina y 4

porción de maracuyá.

3. Para el problema de dieta al minimizar los costos, los valores

factible y óptimo fueron

b1  2000;2500, b2  50;75, b3  33.3;62.2, b4  275;325,

b5  13.3;17.8, b6  4.4;8.9, b7  21.927;26.06,
b8  433.02;698.52, b9  90;2000, b10  1.5;1.78

donde bi son los requerimientos nutricionales o lo que se conoce

como restricciones.

x1  0;4, x2  0;3, x3  1;3, x4  2;3, x5  0;2, x6  1;3,

x7  2;4, x8  0;4, x9  1;2, x10  0;4, x11  2;5

y xi son las porciones de los alimentos.

70
4. El Hospital Nacional Cayetano Heredia tiene una capacidad para

550 pacientes hospitalizados, de los cuales 150 a 200 pacientes

consume una dieta normal diaria. Con un análisis pos óptimo, el

hospital ahorraría aproximadamente de 219 000 soles anual.

71
IX. Recomendaciones
En mi opinión éste modelo puede ser implementado en la unidad de

nutrición para mejorar la calidad de atención al paciente, coadyuvar al

médico en el tratamiento y permitir la mejor distribución de recursos al bajar

los costos y minimizar las grasas lo que permitirá una redistribución de los

recursos.

Partiendo de una buena alimentación a un costo mínimo, se pueden realizar

menús completos para niños de escasos recursos, el gobierno y diferentes

tipos de organizaciones pueden utilizar el modelo para establecer una dieta

sana y económica para los colegios de zonas rurales.

72
X. Referencias bibliográficas

[1] Albers, D. J. y J. K. Reid, (1986). «An interview with George B. Dantzig:

the father of linear programming», The College Mathematics Journal,

17(4), pp. 292-314.

[2] Bazarra M., Jarvis J., Sherali H. (1999). Programación lineal y flujo de

redes. Ed. Limusa. 2da Edición.

[3] Bazaraa M. S., Sherali, H. D., and Shetty C. M. (1993). Nonlinear

Programming, Theory and Algorithms. 2da Edición. Wiley, New York.

[4] Castillo E., Cornejo A., Pedregal P., García R., y Alguacil N. (2002).

Formulación y Resolución de Modelos de Programación Matemática en

Ingeniería y Ciencia.

Recuperado de http://ingenieria-industrial.net/downloads/LibroCompleto.pdf

[5] Chávez A., Rojas M., y Cumsille P. Resolución de problemas de

Programación Lineal, mediante el método simplex. Recuperado de

http://repobib.ubiobio.cl/jspui/bitstream/123456789/282/3/Chavez_Abello_Rodrigo.pdf

[6] Haeussler, Paul. (2017). Cálculo Básico con Aplicación a la Ciencia de la

Vida. Ed. Pearson. 1ra Edición.

[7] Hillier Frederick S., Lieberman Gerard J., (2010) Introducción a la

Investigación de Operaciones. Ed. Mc. Graw Hill. 9na Edición.

[8] Luenberger D., Ye Y. (2016). Linear and Nonlinear Programming. Ed.

Springer. 4ta Edición.

73
[9] Martin, Q. (2011). Investigación de operaciones. Recuperado de

http://ocw.usal.es/ensenanzas-tecnicas/investigacion-operativa-i/contenidos/TemasIO-

I_PDF/Cap02%28PL%29_IO-I.pdf

[10] Mathur, K.,Solow, D. (1996). Investigación de Operaciones. Ed. Prentice

Hall.

[11] Soo Tan. (2010). Matemáticas Aplicadas a los Negocios, las Ciencias

Sociales y de la vida. Ed. Cengage. 5ta edición.

[12] Taha, Hamdy A. (2012). Investigación de Operaciones. Ed. Pearson. 9na

Edición.

[13]http://www.ins.gob.pe/repositorioaps/0/5/jer/tab_cien_cenan/Tabla%20de

%20Alimentos.pdf

[14]http://www.bvs.ins.gob.pe/insprint/cenan/tabla_dosificacion_alimentos_s

ervicios_alimentacion_col.pdf

[15]http://sistemas.minag.gob.pe/sisap/portal/

[16]http://www.ins.gob.pe/repositorioaps/0/5/jer/doc_tec_norm/TAFERA_2_

compressed.pdf

[17]http://www.ins.gob.pe/repositorioaps/0/5/jer/doc_tec_norm/Factores%20

de%20conversi%C3%B3n%20de%20cocido%20-%20crudo.pdf

[18]http://www.fao.org/docrep/014/am401s/am401s02.pdf

74
XI. Anexos

Teorema 1

Sea el modelo de programación lineal, en su forma estándar, donde A

es una matriz m x n, y el rango de A es m, se tiene:

(a) Si existe una solución posible, también existe una solución posible

básica.

(b) Si el problema tiene una solución posible óptima, entonces también

tiene una solución posible básica óptima.

Demostración

(a) Sean A1 ,... An las columnas de A y xT  x1 ,..., xn  una solución

posible, o sea x1 A1  ...  xn An  b

Supongamos que p de estos xi son positivos y asumamos que son los

p primeros, para mayor simplicidad. Luego obtendremos que

x1 A1 ...  x p Ap  b (1.1)

Separamos dos casos:

Caso 1: A1 ,... Ap son linealmente independiente, esto implica que p  m

. Ya que el rango de A es m, en el caso de que p = m, la afirmación ( a ) es

cierta, puesto que p = m nos asegura siempre encontrar una solución para

x1 ,...x p , además única. Ahora bien, si p < m, como el rango de A es m, es

posible encontrar (m – p) vectores columnas de A, entre las (n – p) columnas

restantes, de modo que junto a las p que se tienen, formen un conjunto de m

vectores linealmente independientes. Si asignamos el valor cero a las (m –

p) componentes de x asociadas con estas columnas, obtendremos una

solución básica.

Caso 2: A1 ,... Ap son linealmente dependientes. En este caso tendremos que

y1 A1  ...  y p Ap  0 (1.2)

en donde no todos los yi (i=1, …,p) son nulos, no es difícil ver que al

menos un yi es mayor que cero. Luego multiplicando (1.2) por  y

sustituyendo esta nueva expresión a (1.1) obtenemos que

x1   y1 A1  ...  x p   y p Ap  b .

Este sistema de ecuación es válido para cualquier valor de  . Sin

embargo, si queremos obtener soluciones posibles, o sea, que sean no

negativas, debemos tener precaución para escoger los valores de  . Ahora

bien, si  0 , obtendríamos la solución inicial de (1.1).

Si  0 y aumenta, la componente ( xi   yi ) aumentará, disminuirá

o se mantendrá igual según yi sea negativo, positivo o cero. Como al menos

una componente yi es positiva, sabemos que por lo menos una de estas

componentes debe crecer. Luego, si escogemos un  tal que

x 
 min  i / yi  0 habremos generado una solución posible con a lo
 yi 

más (p -1) componentes positivas.

(b) Sea xT  x1 ,..., xn  una solución posible óptima o sea que

cx T  z0 es el máximo de la función objetivo misma, y supongamos que

contiene exactamente p variables positivas x1 ,...x p . Por lo que tendremos

que x1 A1 ...  x p Ap  b nuevamente separamos en dos casos.

Caso 1: A1 ,... Ap son linealmente independientes. Esta situación es

semejante a la del caso (a), donde p  m . Cuando p  m , el rango de A

será m y como es linealmente independiente, eso implica que x T es una

solución posible básica y como cx T  z0 y es el máximo, esto implica que

x T es una solución óptima básica. Ahora bien, cuando p < m y el rango de A

es m, es posible encontrar (m – p) vectores columnas de A, entre las (n – p)

restantes, de manera que junto a las p que tenemos, formen un conjunto de

m vectores linealmente independientes. Si damos valor cero a las variables

asociadas de a dichas (m – p) columnas, habremos conseguido una solución

posible básica, pero solamente en los x p 1 vectores, ya que hasta x p esta la

solución óptima posible, es decir x1 A1  ...  x p Ap  0 Ap1  0 An p  b , por

lo que volveríamos al caso anterior, entonces es una solución óptima básica.

Caso 2: A1 ,... Ap son linealmente dependientes. Esta situación también es

similar a la anterior del caso 2 para (a), la diferencia es que ahora debemos

demostrar que para cualquier  todo vector ( x  y) que cumpla con la

restricción de no negatividad es una solución óptima. El valor de la función

objetivo asociado con la solución ( x  y) es (cx   cy ) . Para 

suficientemente pequeño, ( x  y) es solución posible para los valores de

 tanto negativas como positivas, donde debe cumplirse que cy = 0, pues si

cy  0 , un  pequeño y con signo apropiado, permitiría obtener una

solución posible tal que cx  y   cx , lo cual contradice la suposición

inicial que x es una solución óptima. Luego, procediendo igual que en el

caso 2 para (b) anterior, esto asegura que las nuevas soluciones posibles, con

un menor número de componentes positivas, también deben ser óptimas.

Teorema 2

Sea el modelo de programación lineal, en su forma estándar, donde A

es una matriz m x n de rango m y b un vector m. Sea F el politopo convexo

que consiste en todos los n – vectores x que satisface

Ax  b
x0

Un vector x es solución básica factible si y sólo si x es un punto

extremo de F.

Demostración

Demostrando si x es solución básica factible entonces es un punto

extremo.

Si x es solución básica factible, como máximo tiene m variables

mayores que cero. Para facilitar la notación supongamos que son las m

x 
primeras. Entonces, x   B 
0 

Supongamos que existe dos puntos x1 , x2  F , tales que

x  x1  1   x2 , 0    1

 y1   y2 
Sean x1   ´  y x2   ´ 
y 1 y 2
donde yi , i  1,2 es de dimensión m x 1, e y´i , i  1,2 es de dimensión

x   y1   y2 
(n – m) x 1 . Entonces, de la igualdad  B     ´   1    ´ 
0   y 1 y 2

se deduce 0  y 1  1    y 2
´ ´

Por ser y 1 , y 2  0,
´ ´
  0 y 1    0 , se tiene y´1  y´2  0

De lo anterior se deduce que las soluciones x, x1 y x2 son básicas y

asociadas a la misma base, por lo tanto, xB= x1 = x2

Concluimos que no existen dos puntos distintos x1 y x2 del conjunto

de soluciones que permitan escribir x como combinación lineal convexa

restringida y, en consecuencia, x es un punto extremo.

Demostrando si x es un punto extremo, entonces es solución básica factible.

Supongamos que x tiene k primeras componentes positivas y el resto

son cero. Entonces el sistema de restricciones se puede escribir de la

siguiente manera:

xa
i 1
i i b

Para ver que x es solución básica factible, es probar que los vectores

ai , i  1,..., k , son linealmente independientes. En caso contrario,

k
existirían escalares 1 ,...,  k no todos nulos, tales que  a
i 1
i i 0

Sea   1 ,  2 ,...,  k ,0,...,0

T

Si se definen x1  x  y x 2  x  
se puede elegir adecuadamente el valor de  para que los puntos sean

1 1
factibles. Además, se verifica que x1  x2 y x  x1  x2 de donde se
2 2

deduciría que x no es un punto extremo.

Teorema 3

Sea el modelo de programación lineal, en su forma estándar

Max (o Min) z  cT x

Ax  b
x0

El valor óptimo de la función objetivo se encuentra en un punto

extremo del conjunto F.

Demostración

Supongamos que tenemos una solución óptima x* que no es un punto

extremo y que z *  cT x* es el valor óptimo del problema. Entonces,

verifica que para todo xF

z  cT x  cT x*  z *

Sean x1 ,..., xk  el conjunto de los puntos extremos de F. Todo punto

de la región F, en particular el punto x* , se puede escribir como

combinación lineal convexa de los puntos extremos.

k k
x   i xi , i  0,
*
 i 1
i 1 i 1

k k
Entonces, z *  cT x*  cT  i xi   i cT xi
i 1 i 1
Dado que se verifica max c xi  c xi , i  1,..., k
T T
entonces
i

k k k
z *   i cT xi   i max cT xi  max cT xi  i  max cT xi  z *
i i i
i 1 i 1 i 1

Como consecuencia, z *  max cT xi y se concluye que el óptimo se

i

alcanza en un punto extremo.

Teorema 4

Sea S  x : Ax  b, x  0, donde A es una matriz m x n de rango m,

y b es un vector de dimensión m. Un punto x es punto extremo S si y sólo si

 B 1b
A puede descomponerse en B N  tal que x  donde B es una
0 

matriz de dimensión m x m invertible que satisface B 1b  0

Demostración

1
Si B b  0, x  0 . Además, Ax  0 , tal que x es un extremo de S.

Ahora mostraremos que x es de hecho un punto extremo.

Supongamos que x  1 x1  2 x2 , donde 1 , 2  0 y x1 , x2 son puntos

de S. Note que n – m -1 componentes de x son iguales a cero, los

componentes correspondiente de x1 y x2 también deben ser igual a cero.

Así, x1 y x2 puede escribirse como:

x  x 
x1  1  11 , x2   2  21  , donde 1 , 2  0
0  0 
Note que Ax1  Ax2  0 , se puede verificar fácilmente que x11  x21  B b .
1

Así, x1 y x2 son no distintas, lo que implica que x es un punto extremo. Ya

que x es un múltiplo positivo de x, es también un punto extremo.

Si suponemos que x es un punto extremo de S. Sin perder la

generalidad, supongamos que

x  x1 ,..., xk ,0,..., x j ,...,0

T

donde x  0 para i  1,..., k y para i  j . Decimos que a1 ,..., ak son

linealmente independiente.

Por contradicción, supongamos que este no es el caso, entonces

k
existirían escalares 1 ,..., k no todos ceros tal que  a
i 1
i i 0 . Sea

  1 ,..., k ,0,...,0T y elegimos   0 suficientemente pequeño tal que

ambos x1  x   y x2  x   son no negativos.

k
Note que Ax1  Ax  A  0   a   0
i 1
i i

Similarmente, Ax2  0 Ya que x1 , x2  0 , son ambos puntos de S.

Tenga en cuenta también que son distintos, ya que   0 y   0 .

1 1
Además, x  x1  x2 contradiciendo el supuesto que x es un
2 2

punto extremo. Así a1 ,..., ak son linealmente independientes, y además el

rango de A es igual a m, esto es claro que k  m . Entonces debe existir m –

k vectores de entre el conjunto de vectores ai : i  k  1,..., n; i  j que

junto con a1 ,..., ak , forme un conjunto de m vectores linealmente

independientes.

Sin perder la generalidad, supongamos que esos vectores son

ak 1 ,..., am . Denotemos a1 ,..., ak  para B, donde B es invertible.

 
Así 0  Ax  B x b x j , donde x es un vector del primer componente m de x

. Por los tanto, x  x j B 1b y por lo tanto el vector x es de la forma

  B 1b 
x  x j   . Note que x  0, x j  0, B 1b  0 , lo que queda

0 

demostrado.

Proposición 1

El conjunto de soluciones factibles de un problema de programación

lineal es un conjunto convexo.

Demostración

Sean x1 y x2 soluciones factibles, entonces

Ax1  b, Ax 2  b, x1  0, x2  0

Si formamos un vector x que sea combinación lineal de éstos dos:

x  x1  1   x2 , Ax  Ax1  1   Ax 2  b  1   b  b

Por lo que x es también solución factible.

Proposición 2

Si K es un poliedro convexo, entonces la función objetivo z alcanza un

mínimo en un vértice de K.

Demostración

Designemos por K el conjunto de las soluciones factibles de un

problema de programación lineal.

Sean x1 , x2 ,...x p los vértices de K y sea x0 una solución factible mínima,

esto significa que c T x0  c T x para cada x  K

x4

x3 x5

x2 x6

x1 x7

Se puede dar los casos siguientes:

a) Si x0 es un vértice de K, ya estaría demostrado.

b) Si x0 no es un vértice de K, entonces x0 se podrá poner como una

combinación lineal convexa de ellos:

p p
x0   i xi ;  i  0;  i 1
i 1 i 1

Sustituyendo: min z  m  cT x0  cT 1 x1   2 x2  ...   p x p 

Supongamos que cT x1  min cT xi

m  cT 1 x1   2 x1  ...   p x1   cT x1 1   2  ...   p   cT x1  m

por consiguiente c T x1  m , es decir, que existe un vértice de K en el que la

función objetivo z  cT x alcanza su valor mínimo.

Para probar la segunda parte de la propiedad supongamos que z

alcanza su valor mínimo en x1 , x2 ,...xq y que x es una combinación lineal

convexa de ellos:

q q
x   i xi ;  i  0;  i 1
i 1 i 1

cT x  cT 1 x1   2 x2  ...   q xq   1cT x1   2 cT x2  ...   q cT xq 

 m1  m 2 ...  m q   m1   2  ...   q   m

lo cual la proposición queda demostrada.

Proposición 3

Si tenemos un conjunto de k vectores A1 , A2 ,..., Ak , que sean

linealmente independientes y de forma que: x1 A1  x2 A2  ...  xk Ak  b con

las xi  0 , entonces, el punto X  x1 , x2 ,..., xk ,0,...,0 es un vértice del

T

conjunto convexo K de soluciones factibles.

Demostración

Supongamos que X no fuera vértice, entonces podría expresarse como

una combinación lineal convexa de dos puntos distintos de K.

X  X 1  1   X 2 ,   0,1, X 1 , X 2  K

Puesto que las coordenadas de las soluciones factibles son no

negativas y deberá ocurrir que la n – k coordenadas últimas de X1 y X2

fueran iguales a cero:

 X 1  x11, x12 ,..., x1k ,0,...,0
T

X 2  x21, x22 ,..., x2 k ,0,...,0

T

con X 1  X 2 . Además, por ser soluciones factibles, se cumple que

AX 1  b y AX 2  b , por lo que podemos escribir:

x11 A1  x12 A2  ...  x1k Ak  b

x21 A1  x22 A2  ...  x2 k Ak  b

Restando las expresiones anteriores obtenemos:

( x11  x21) A1  ( x12  x22 ) A2  ...  ( x1k  x2k ) Ak  0

y por ser los vectores A1 , A2 ,..., Ak linealmente independientes llegamos a

la conclusión de que:

x11  x21
x12  x22
...
x1k  x2 k

es decir, que X1=X2, lo que contradice el hecho de haber supuestos X 1  X 2 ,

por lo que necesariamente X debe ser el vértice de K.

Teorema 5

Sea P un problema primal de programación lineal, y D su dual. Sea x

una solución factible de P e y una solución factible de D. Entonces

bT y  c T x

Demostración

Si x e y son factibles respectivamente para P y D, entonces

 Ax  b, x  0, AT y  c

Obsérvese que debido a la no negatividad de x,

bT y  xT AT y  xT c  cT x

Teorema 6

Dados un par de problemas primal – dual, si uno de ellos admite

solución óptima, entonces el otro también la admite y los respectivos

valores óptimos son iguales.

Demostración

Sea x * solución óptima del primal y * solución óptima del dual.

 
 x* , *  S    S´   donde S es el conjunto de oportunidades

primal y S* es el conjunto de oportunidades dual.

   
x*  * / z x*  z *