CUARTA UNIDAD

¿Qué es Programación Lineal?

“El éxito es un camino, no un destino. Hay que construirlo día a día con esfuerzo, fé, optimismo y objetivos “

Miguel Ángel Palacios

¿Qué debo recordar?¿Qué es la Programación Lineal?¿Cómo plantear la solución de un problema de programación lineal?¿Cuáles son los métodos de optimización lineal?¿Qué tipos de soluciones se presentan en los problemas de programación lineal con dos variables?

LECCIÓN 10

CONOCIMIENTOS PREVIOS

Para comprender, analizar y resolver los problemas de programación

lineal, tenemos que recordar algunos conceptos y gráficas referentes a

ecuaciones e inecuaciones lineales.

10.1 ECUACIONES DE LA RECTA

Punto pendiente

y – y, = m ( x – x, )

Pendiente con ordenada en el origen

y = m x + b m = pendiente

Pasa por dos puntos: P, ( X1, Y1 ) P2 ( X2 , Y2)

Y – Y1 = Y2 – Y1 ( X 2 – X 1 ) X 1 ≠ X 2

X2 – X 1

Forma Simétrica

X + Y = 1

a b

Forma General

AX + BY + C = 0 A ≠ 0 B ≠ 0

Ejemplo

Determinar la ecuación de la recta que pasa por los de puntos.

A (2; 8) y B (-1; -1)

Solución:

A( 2, 8 )y

x2-1 0B ( -1,-1)

Y – y1 =m(x – x1) ( 1)

m = y2 – y = -1 – 8 = 3 x2 – x1 -1 – 2

m = 3

Reemplazando el valor de m en (1)

Y – 8 = 3 (x – 2)Y – 8 =3x – 6. Ecuación de la recta

Rectas paralelas a los ejes

Una recta, paralela al eje X, tiene por ecuación y = b, donde bR y corta al

eje y en el punto ( o ; b). Así la recta de ecuación y = 4 corta al eje y en (0; 4)

Una recta, paralela al eje Y, tiene por ecuación x = c, donde c R y corta al

eje X en el punto ( c , o ). Así la recta de ecuación X = 3 corta al eje x en ( 3 , 0

)

Y

Y¨

X´ X

y=4

4

Rectas Secantes.- Dos rectas L1 y L2 son secantes sí y sólo sí se intersecan en

un solo punto.

Así

L1 = 2X + 3Y = 12 L2 = 4X – 3Y = 6

Para determinar las coordenadas del punto de intersección A, resolvemos el

sistema de ecuaciones.

10.2 GRÁFICA DE UNA INECUACIÓN LINEAL CON DOS VARIABLES

La gráfica de una recta de ecuación y = mx + b divide al plano en dos regiones

o semiplanos: una formada por los puntos que satisfacen la inecuación y < mx

+ b, y otra formada por los puntos que verifican y >mx + b con frontera la línea

recta.

Si se trata de una inecuación en sentido estricto (<,>), no incluye a los

puntos de la recta que limitan al semiplano.

Si es una inecuación en sentido amplio (≤,≥), los puntos de la recta

también

son soluciones de la inecuación.

Ejemplos :

EJEMPLO 1 .Representa gráficamente:

SOLUCIÓN:

Paso 1:x y 0 2-2 0

2x + 3 y = 12

4x - 3 y = 6

6x =18

x = 18

6

x = 3

2(3) + 3y = 12

6 - 3 y = 12

y = 12 – 6

3

y = 2 A (3, 2)

x

L1

0

2 A (3, 2)

L2

Primero se determina dos puntos de la recta: para determinar la frontera.

Los puntos por donde la recta pasa son: (0; 2) (-2, 0 )

Paso 2 .

Para obtener la región sombreada , se elige un punto cualquiera , puede ser (0,0), (1,0) ( 0,1) o cualquier otro y sustituir en la desigualdad dada, obteniéndose una proposición Verdadera o Falsa ..

Si la proposición es Verdadera, sombrear la región que se encuentra el punto elegido.

Si la proposición es Falsa, sombrear la región opuesta.

En este ejemplo elegimos el punto ( 1,0) sustituimos en la inecuación y > x + 2

0 > 1+ 2 obteniendo 0 > 3 ( falso ) , por consiguiente se sombrea la región que está por encima de la recta, por ser opuesta a la región del punto ( 1,0 ) Así se obtiene la gráfica para la inecuación: , que viene a ser la región sombreada.

EJEMPLO 2 : Representa gráficamente:

SOLUCIÓN:Paso 1 : x y

0 -11 2

Primero se determina dos puntos de la recta:

Los puntos por donde la recta pasa son: (0; -1) y (1; 2).

Paso 2 :

Siguiendo la regla y el procedimiento anterior se obtiene la gráfica para la inecuación:

EJEMPLO 3 : Graficar la inecuación : x 0

La gráfica de la ecuación x = 0 es el eje YLa gráfica de x >0 es el semiplano que está a la derecha del eje Y. ¨ y

EJEMPLO 4 : Representa gráficamente y 0

Graficamos la ecuación y = 0 , es el eje X.La gráfica de y>0 es el semiplano que está encima del eje X

TAREA N° 01 x

Representa en el plano cartesiano la solución de las siguientes inecuaciones.

1) y ≤ 3x + 4 2) y> 2x – 2 3) y – x ≤ -2

4) x + 2y ≥ 3 5) 4x + 3y < 2 6) x – 2y > 5

10.3 GRÁFICA DE UN SISTEMA DE INECUACIONES LINEALES CON DOS

VARIABLES

El conjunto solución de un sistema de inecuaciones lineales con dos variables x, y, es el conjunto de todos los puntos ( x, y) que satisfacen cada desigualdad del sistema .La solución gráfica del sistema es la intersección de todos los semiplanos que define cada desigualdad lineal.

EJEMPLO 1 .Representa gráficamente la solución de: ; ;

SOLUCIÓN:

Primero se grafican cada una de las rectas: (Eje Y) La recta pasa por los puntos: (0; 1) y (2; 2)La recta pasa por los puntos: (0; 3) y (3; 0)Luego se grafica: ; ;

El conjunto solución es el semiplano o región sombreada

EJEMPLO 2 :Representa la región solución de: ; ;

SOLUCIÓN:

Primero se grafican cada una de las rectas: La recta pasa por los puntos: (-4; 2) y (1; 0)La recta pasa por los puntos: (-1; -1) y (1; 0)La recta (Eje Y)Luego se grafica: ; ;

EJEMPLO 3 : Represente gráficamente la solución del sistema de inecuaciones lineales:

;

SOLUCIÓN:

Graficando en el plano coordenado las relaciones ;

La región sombreada no acotada representa la solución del sistema de inecuaciones.

EJEMPLO 4 :Represente gráficamente la solución del sistema de inecuaciones lineales:

SOLUCIÓN:

Graficando en el plano coordenado las relaciones ;

EJEMPLO 5 :Represente gráficamente la solución del sistema de inecuaciones lineales:

;

SOLUCIÓN:

Graficando en el plano coordenado las relaciones ;

No hay región sombreada dado que ningún punto cumple el sistema de inecuaciones.

TAREA 21) Determinar el conjunto solución del sistema :

4x + 3y 12x – 2y 0

2) Graficar el conjunto solución del sistema :x + y 60 x 3y 0

3) Determinar en forma gráfica el conjunto solución del siguiente sistema, e indique si el conjunto solución está o no acotado.

x+ y 7x – 2 0y – 7 0y- 3 0

4) Represente gráficamente la solución del sistema de inecuaciones :3x + 2y < 10 x + 2y 2

5) Representa gráficamente el conjunto solución del siguiente sistema. Encuentra las coordenadas de los vértices de la región del plano que se forma.

X + 3y 33 y 2x + 6x- 5 0

INTRODUCCIÓN A LA PROGRAMACIÓN LINEAL

11.1 RESEÑA HISTÓRICA DE LA PROGRAMACIÓN LINEAL

Jean Baptiste-Joseph Fourier (1768-1830), matemático francés fue uno de los

primeros en intuir, aunque de forma no tan precisa, los métodos de los

actualmente se conoce como Programación Lineal y la potencialidad que de

ellos se deriva. También se tiene al matemático Gaspar Monge (1746 – 1818),

quien en 1776 se interesó por problemas de este género. En 1939 el

matemático ruso Leonid Vitalevich Kantorovitch publica su obra titulada

Métodos matemáticos de organización y planificación de la producción, en la

que por primera vez se hace corresponder a una extensa gama de problemas

una teoría matemática precisa y bien definida, llamada hoy en día

Programación Lineal, por lo que se le considera uno de sus creadores.

Kantorovitch recibió el Premio Novel de Economía en 1975 por sus

aportaciones al problema de asignación óptima de recursos humanos. En

1941-1942 se formula por primera vez el problema de transporte, estudiado

independientemente por Koopmans y por Kantorovitch, razón por la cual se

suele conocer con el nombre de problema de Koopmans-Kantorovitch.

En los años posteriores a la Segunda Guerra Mundial, en Estados Unidos se

asumió que la eficaz coordinación de todas las energías y recursos de la

nación era un problema de tal complejidad, que su resolución y simplificación

pasaba necesariamente por los modelos de optimización que resuelve la

Programación Lineal.

Investigación de Operaciones en general y la Programación Lineal en particular recibieron un gran impulso gracias a la aparición y rápida evolución de las computadoras. Uno de los momentos más importantes fue la aparición del método Simplex. Este método, desarrollado por G.B. Dantzig en 1947, consiste en al utilización de un algoritmo para optimizar el valor de la función objetivo teniendo en cuenta las restricciones planteadas. En términos matemáticos muy precisos, el enunciado estándar al que cabe reducir todo problema de Programación Lineal. Dantzig, junto con una serie de investigadores del United

Dantzig, junto con una serie de investigadores del United Status Departamento

f Air Forc, formarían el grupo que dio en denominarse SCOOP (Scientific

Computation of Optimum Programs).

Los fundamentos matemáticos de la Programación Lineal se deben al

matemático norteamericano de origen húngaro John Von Neumann (1903-

1957), quien en 1928 publicó su famoso trabajo Teoría de juegos. En 1947

conjetura la equivalencia de los problemas de Programación Lineal y la teoría

de matrices desarrollada en sus trabajos. La influencia de este respetado

matemático, discípulo de David Hilbert en Gounga y desde 1930 catedrático de

la Universidad de Princeton de Estados Unidos, hace que otros investigadores

se interesaran paulatinamente por el desarrollo riguroso de esta disciplina. El

hombre de Programación Lineal no procede de la creación de programas en la

computadora, sino de un término militar, programa que significa realizar planes

o propuestas de tiempo para el entrenamiento, la logística, o el despliegue de

las unidades de combate.

El desarrollo de la Programación Lineal ha sido considerada como uno de los

avances científicos más importantes de mediados del siglo XX, su efecto desde

1950 ha sido extraordinario. En la actualidad es una herramienta de uso normal

que ha ahorrado miles o millones de dólares a muchas compañías o negocios.

Dantzig es considerado el padre de la programación lineal.

11.2 ¿Qué es Programación Lineal?

Es una herramienta para resolver problemas de optimización. La programación

lineal utiliza un modelo matemático para describir el problema.

El adjetivo lineal significa que todas las funciones matemáticas del modelo

deben ser funciones lineales. En este caso, la palabra programación no se

refiere a términos computacionales, es sinónimo de planeación. Por lo tanto, la

programación lineal involucra la planificación de las actividades para obtener un

resultado óptimo.

La programación lineal es una técnica que se utiliza en la resolución de

problemas donde se plantea optimizar, maximizar, minimizar funciones que se

encuentran sujetas a determinadas restricciones. Tales problemas incluyen

asignación de recursos, y siempre implican relaciones lineales entre las

variables de decisión, el objetivo y las restricciones.

Función Objetivo.- Es la función a optimizar

Restricciones de no negatividad.- Significa que las variables x e y son

mayores o iguales que cero.

Sistema de restricciones lineales.- Es el conjunto de todas las restricciones.

El desarrollo de la programación lineal ha sido clasificado como uno de los

avances científicos más importantes de mediados del siglo XX.

En la actualidad es una herramienta de uso normal que ha ahorrado millones

de dólares a muchas empresas.

11.3 ¿Qué aplicaciones tiene la Programación Lineal?

La programación lineal se aplica en diferentes campos, así tenemos en la

agricultura, industria, transporte, economía, salud, ciencias sociales, estrategia

militar, en las que se presentan situaciones donde se exige optimizar algunas

funciones que se encuentran sujetas por determinadas restricciones.

También produce algoritmos eficientes de cómputo para problemas con miles

de restricciones y variables. Debido a su gran eficiencia de cálculo, la

programación lineal forma la columna vertebral de los algoritmos de solución

para otros modelos de investigación de operaciones.

11.4 Cuáles son las características de Programación Lineal

La programación lineal tiene las siguientes características:

Se preocupa por alcanzar una posición óptima con relación a cierto

objetivo.

Su finalidad es minimizar los costos y maximizar los beneficios.

Supone la selección entre varias alternativas a la combinación apropiada

de éstas.

Considera ciertos límites o restricciones a la decisión.

Requiere que las variables sean cuantificables y que tengan relaciones

lineales entre sí.

11.5 Planteamiento del problema

Los problemas de optimización se plantean muy a menudo verbalmente. El

procedimiento para la solución consiste en realizar un modelo del problema con

un programa matemático y luego con las técnicas de programación lineal.

Se recomienda seguir los siguientes pasos para transformar un problema

verbal en un programa matemático.

Para plantear la solución de un problema de la programación lineal debemos:

Organizar la información mediante una tabla.

Asignar una variable a cada una de las incógnitas.

Determinar las restricciones que se crean convenientes.

Plantear la función objetivo.

Ejemplos :

Problema 1 : En un taller se dispone semanalmente de 30 Kg de algodón y 25

Kg de lana para la producción de dos tipos de tapices decorativos A y B, según

los siguientes requerimientos:

-Tapiz A: 250 g de algodón y 120 g de lana

-Tapiz B: 300 g de algodón y 200 g de lana

Si el tapiz A se vende a S/. 50 y el tapiz B S/. 80, determina las restricciones y

plantea la función objetivo que determina el máximo ingreso.

Del análisis de la información del problema tenemos:

Dos cantidades de productos: algodón y lana.

Dos tipos de tapices: A y B con distintas cantidades de cada producto.

Un precio de cada tipo de tapiz.

Se desea obtener el máximo ingreso por la venta de los tapices.

Organizamos la información en una tabla:

Organizamos la información en una tabla:

Requerimientos por tapiz Disponibilidad

por semanaA B

Algodón (kg) 250 g = 0.25 kg 300 g = 0.3 kg 30 kg

Lana (kg) 120 g = 0.12 kg 200 g = 0.2kg 25 kg

Precio (S/.) S/. 50 S/. 80

Asignamos una variable a cada una de las incógnitas:

x : número de tapices del tipo A y : número de tapices del tipo B

Determinamos las restricciones:

-De recursos: algodón 0,25x + 0,3y ≤ 30 lana 0,12 x + 0,2y ≤ 25

-De negatividad, x e y son valores enteros no negativos: x ≥ 0; y ≥ 0

Como 50x es el ingreso total por la venta de los tapices del tipo A y 80y

por los tapices del tipo B, entonces la función objetivo que determina el

máximo ingreso es: F (x, y) = 50x + 80y

Problema 2: Supongamos que se cuenta con dos alimentos: pan y queso; cada uno de ellos

contiene calorías y proteínas en diversas proporciones. Un kilogramo de pan

contiene 2,000 calorías y

50 gramos de proteínas, y un kilogramo de queso contiene 4,000 calorías y

200 gramos de proteínas. Supongamos que una dieta normal requiere cuanto

menos 6,000 calorías y 200 gramos de proteína diariamente. Por tanto, si el

kilogramo de pan cuesta $6.00 y $21.00 el queso, ¿Qué cantidades de pan y

queso debemos comprar para satisfacer los requisitos de la dieta normal,

gastando la menor cantidad de dinero?

La siguiente tabla reúne los datos del problema

Tabla 1

Pan(1 Kg.)

Queso(1 Kg.)

Requisitosde la dieta

normal

Precios ($)6 21

Calorías 2000 4000 6000

Proteínas(gramos)

50 200 200

Este problema presenta dos incógnitas:

1. Kgs. de pan a comprar

2. Kgs. de queso a comprar

Con esta notación convendremos en que:

X1 = nº de kilogramos de pan

X2 = nº de kilogramos de queso

El primer paso consiste en obtener una función del costo con las siguientes

incógnitas X1 y X2.

Tabla 2

Pan Queso

Si se compra Se gasta

$

1 kg. 6 x 1 2 kg. 6 x 2 n kg. 6 x n X1 kg. 6 X 1

Si se compra Se gasta

$

1 kg. 21 x 1 2 kg. 21 x 2 n kg. 21 x n X1 kg. 21 X 2

En la tabla 2, se presenta el razonamiento seguido para obtener la función del costo.

Para la compra de x1 Kg de pan, el costo 6 (precio de cada Kg.) por x1

(Nº de Kgs.) ósea 6x1. Igual razonamiento debe hacerse con el queso: si se compra x2 Kg. de queso a $ 21.00 el Kg. el costo es 21x2. Ahora bien, si se demandan simultáneamente x1 Kgs. de pan y x2 Kgs. de queso el gasto es:

G= 6x1 + 21x2

donde G representa el costo o importe de la compra.

Por el enunciando del problema, también es necesario precisar que se trata de comprar cantidades x1 de pan y x2 de queso, de tal manera que se satisfagan los requisitos de una dieta normal con el mínimo costo; esto significa que la función G debe ser mínima. Con este objeto, usará la siguiente notación:

(MIN) G = 6x1 + 21x2

que se lee “minimizar G”. , que es la función objetivo

Luego planteamos las restricciones como se ilustra en la tablas 3.l

Tabla 3

Planteo de la Restricción de CaloríasPan Queso

Si se compras Se obtiene (calorías)

1 kg. 2000 2 kg. 2000 x 2 n kg. 2000 n X1 kg. 2000 X 1

Si se compra Se obtiene (calorías)

1 kg. 4000 2 kg. 4000 x 2 n kg. 4000 n X2 kg. 4000 X2

En consecuencia, resulta que si se compra x1 Kgs. de pan y x2 Kgs. de

queso, el número de calorías contenido en dicha compra será de:

2000 x1 + 4000 x2El total de calorías debe ser, por lo menos, el fijado por la dieta (6000),

lo que. algebraicamente puede expresarse así:

2000 x1 + 4000 x2 ≥ 6000

”Por lo que toca al requisito de proteína, el planteo es semejante, como

aparece en la tabla 4.

Tabla 4

Planteo de la Restricción de Proteínas

Pan Queso

Si se compras Se obtiene (grs.de proteínas)

1 kg. 50 2 kg. 50 x 2n kg. 50 n

X1 kg. 50 X 1

Si se compra Se obtiene (grs.de proteínas)

1 kg. 200 2 kg. 200 x 2 n kg. 200 n X2 kg. 200 X2

En x1 Kg. de pan mas x2 Kg. de queso, están contenidos 50 x1 + 200 x2 gramos de proteínas. Dado que la dieta normal requiere de 200 grs. de proteínas cuando menos, la expresión completa es:

50 x1 + 200 x2 ≥ 200.

Con esto, el problema queda planteado, se trata de:

(MIN) G = 6x1 + 21x2 Con las restricciones :

2000 x1 + 4000 x2 ≥ 6000 50 x1 + 200 x2 ≥ 200.

Problema 3:

Un ebanista, dispone de las dispone de dos diferentes tipos de madera tiene 1 500 pies tabla de tipo de A, y 1 000 de tipo B; también dispone de 800 horas hombre para efectuar el trabajo. La demanda que ha estimado es la siguiente: cuando menos 40 mesas. 130 sillas, 30 escritorios y nomás de 10 estantes. Las cantidades de madera A y B, y las horas –hombre que requiere la elaboración de cada unidad de articulo, están indicadas en la tabla 5

Tabla 5

Artículo Madera Horas-Hombre

DemandaEstimada

UtilidadesPor unidadA B

Mesa5 2 3 Cuando menos 40 12

Silla1 3 2

Cuando menos 130

5

Escritorio9 4 5 Cuando menos 30 15

Estante12 1 10 No mas de 10 10

Total 1500 1000 800

El problema es: ¿Qué cantidad debe fabricar el ebanista de cada artículo, de manera que las utilidades obtenidas sean las máximas?

El planteamiento de este problema sigue una técnica similar a la anterior.

X1 = número de mesas que deben producirse.X2 = número de sillas que deben producirse.X3 = número de escritorios que deben producirse.X4 = número de estantes que deben producirse.

Una vez simbolizadas las incógnitas, el paso siguiente será obtener las función-objetivo. En este caso se trata de una función de utilidades que debe maximizarse.

U = 12x1 + 5x2 + 15x3 + 10x4.

Pero, dado que dichas utilidades deben ser las máximas posibles, se trata de

(MAX) U = 12x1 + 5x2 + 15x3 + 10x4.

El máximo de esta función de utilidades esta condicionado por las restricciones de recursos y de demandas.

Restricciones de recursos:

Trabajo. Se cuenta con 800 horas-hombres solamente, luego:

El total de horas-hombre invertidas en la producción de x1 mesa, x2 sillas, x3 escritorios y x4 libreros.

Y como existe la condición de que este total no debe ser mayor que 800, la expresión completa es:

3x1 + 2 x2 + 5x3 + 10x4. ≤ 800

Madera. Para el planteo de las restricciones de madera tipo A y tipo B; es aplicable el mismo razonamiento. Es decir:

5x1 + x2 + 9x3 + 12x4. ≤ 1500

Para madera del tipo B, la restricción es:

2x1 + 3 x2 + 4x3 + x4. ≤ 1000

Restricciones de demanda

En primer término, el número de mesas, X1, debe ser cuando menos de 40, es decir, igual o mayor de 40:

X1 ≥ 40.

El número de sillas, x2, debe ser cuando menos 130:

X2 ≥ 130.

El numero de escritorios; x3, cuando menos 30:

X3 ≥ 30.

El número de estantes, X4 , no debe ser mayor de 10, es decir: X 10

Se trata de :

MAX U = 12 X1 + 5X2 + 15 X3 + 10 X4

Con las restricciones :

X1 + 2 X2 + 5 X3 + 10 X4 800

5 X1 + X2 + 9 X 3+ 12 X4 1500

2X 1+ 3 X2 + 4 X3 + X4 1000

X1 40

debe ser igual o menor que 800 horas-hombre

X 2 130

X 3 30

X4 10 Con la condición de no negatividad de todas las variables

11.6 Determinación de la región factible

La solución de un problema de programación lineal debe estar en la región

determinada por las distintas desigualdades. Esta recibe el nombre de región

factible, y puede estar o no acotada. Si la región factible está acotada, su

representación gráfica es un polígono con un número de lados menor o igual

que el número de restricciones.

EJEMPLO 1 : Determinación de la región factible; teniendo en cuenta las siguientes inecuaciones:

; ;

;

SOLUCIÓN:

La región factible se determina graficando en el plano coordenado las relaciones: ; ; ;

La región sombreada acotada ACFD representa la región factible, es decir la región que cumple las inecuaciones dadas.

EJEMPLO 2.Determinación de la región factible; teniendo en cuenta las siguientes inecuaciones:

; ; ;

SOLUCIÓN:

La región factible se determina graficando en el plano coordenado las relaciones: ; ; ;

La región sombreada no acotada representa la región factible, es decir la región que cumple las inecuaciones dadas.

11.7 Determinación de la solución óptima

La solución óptima es aquella que maximiza o minimiza la función objetivo F(x,

y).

Se encuentra en la frontera de la región factible.

EJEMPLO

Si la función objetivo es F(x, y) = 40x + 60y Detremina la solución óptima.

Identificamos los vértices: A(0; 0), C(120; 0), F(105; 15) y D(0; 50)

Evaluamos la función objetivo en cada punto:

Punto A F(0; 0) = 40(0) + 60(0) = 0

Punto C F(120; 0) = 40(120) + 60(0) = 4800

Punto F F(105; 15) = 40(105) + 60(15) = 5100 máximo ingreso

Punto D F(0; 50) = 40(0) + 60(50) = 3000

La solución óptima se obtiene en el punto F, donde la función objetivo

F(x, y) = 40 x + 60y obtiene su máximo valor cuando x= 105 e y = 15.

LECCIÓN 12

MÉTODOS DE OPTIMIZACIÓN LINEAL

12.1 MÉTODO ALGEBRAICO O DE LOS VÉRTICES

Lo más importante del método algebraico es determinar los vértices

resolviendo los sistemas que se pueden formar con las restricciones.

Aplicamos este método resolviendo los siguientes problemas :

PROBLEMA 1

En la Urbanización Los Portales de Javier Prado.se van a construir casas de dos tipos : A y B. La empresa constructora COSAPI, dispone para ello de un máximo de S/ 1 800 000, siendo el costo de cada tipo de casa de S/. 30 000 y S/ 20 000, respectivamente. La zonificación urbana exige que el número total de casassea superior a 80. Sabiendo que el beneficio obtenido por la venta de una casa

de tipo A es de S/ 4 000 y de S / 3 000 por una del tipo B. ¿ Cuántas casas

deben construirse de cada tipo para obtener la máxima utilidad ?

SOLUCIÓN

Asignamos una variable a cada una de las incógnitas:

X : número de casa tipo A Y: número de casas tipo B

Determinamos las restricciones y la función objetivo:

X ≥ 0; y ≥ 0 X ≥ 0; Y ≥ 0

X + Y ≤ 80 X+ Y≤ 80

Solución óptima

Función Objetivo:F (x, y) = 4 000x + 3 000y

30 000X + 20 000Y ≤ 1 800 000 3x + 2y ≤ 180

Hallamos los puntos de corte de las rectas asociadas a las restricciones.

Para ello, calculamos las soluciones de los seis sistemas de dos

ecuaciones con dos incógnitas que se pueden formar con las cuatro

restricciones (ver margen) y obtenemos:

A (0; 0), B (0; 80), C(20; 60), D(60; 0), E(80; 0), F(0; 90)

Determinamos los vértices de la región factible. Para ello, evaluamos las

restricciones en todos los puntos obtenidos y verificamos si cumplen las

desigualdades:

X ≥ 0 Y ≥ 0 X + y ≤ 80 3x + 2y ≤ 180

A(0; 0) Sí cumple Sí cumple Sí cumple Sí cumple

B(0; 80) Sí cumple Sí cumple Sí cumple Sí cumple

C(20; 60) Sí cumple Sí cumple Sí cumple Sí cumple

D(60; 0) Sí cumple Sí cumple Sí cumple Sí cumple

E(80; 0) Sí cumple Sí cumple Sí cumple No cumple

F(0; 90) Sí cumple Sí cumple No cumple Sí cumple

Los puntos A, B, C y D cumplen todas las restricciones: estos son los vértices

de la región factible. E y F no pertenecen a la región factible.

Calculamos los valores de la función objetivo F(x, y) = 4 000x + 3 000y

en los vértices A, B, C, y D porque son los que cumplen todas las

restricciones:

Para el punto A: F (0; 0) = 4 000(0) + 3 000(0) = 0

Para el punto B: F (0; 80) = 4 000(0) + 3 000(80) = 240 000

Para el punto C: F (20; 60) = 4 000(20) + 3 000(60) = 260 000 MÁXIMA

UTILIDAD

Para el punto D: F (60; 0) = 4 000(60) + 3 000(0) = 240 000

La solución óptima que maximiza la función objetivo F(x, y) = 4 000x + 3

000y corresponde al vértice C (20; 60).Entonces, para obtener la máxima

utilidad deben construirse 20 casas del tipo A y 60 casas del tipo B.

Para aplicar el método algebraico es necesario seguir los siguientes pasos :

Hallar los puntos de corte de las rectas asociadas a las restricciones.

Evaluar las restricciones en todos los puntos de corte y verificar si

cumplen las desigualdades.

Calcular los valores de la función objetivo en cada punto que cumple

todas las condiciones para determinar la solución óptima.

PROBLEMA 2 :

Utiliza el método algebraico para determinar los valores x e y que hacen máxima la función objetivo F(x; y)=50x+90y, Con las siguientes restricciones:

SOLUCIÓN:

Primero graficamos en el plano coordenado las relaciones: ; ; ;

La región sombreada ABCD representa la región factible, es decir la región que cumple las restricciones. Para obtener el valor máximo de la función

objetivo F(x; y)=50x+90y calculamos los valores de dicha función en los vértices A, B, C y D.Para el vértice A: F(0; 0) = 50(0) + 90(0) = 0Para el vértice B: F(0; 60) = 50(0) + 90(60) = 5400Para el vértice C: F(40; 40) = 50(40) + 90(40) = 5600Para el vértice D: F(80; 0) = 50(80) + 90(0) = 4000El valor máximo de la función objetivo se obtiene en el punto C para x=40 y=40.

12.2 MÉTODO GRAFICO O DE LAS RECTAS DE NIVEL

Aplicamos este método resolviendo los siguientes problemas:

PROBLEMA 1:

Resolvemos el problema 1 del método algebraico, aplicando el método gráfico.

Organizamos la información en una tabla:

Tipo de casa A Tipo de casa B Disponibilidad

Inversión (en miles) 30 20 1 800

Por zonificación 1 1 80

Utilidad (en miles) 4 3

Asignamos una variables cada una de las incógnitas :

X =número de casa de tipo A Y =: número de casas tipo B

Determinamos las restricciones y la función objetivo:

X ≥ 0; y ≥ 0 x ≥ 0; y ≥ 0

X + y ≤ 80 x + y ≤ 80

30 x + 20y ≤ 1 800 3x + 2y ≤ 180

Para aplicar el método gráfico realizamos los siguientes pasos:

Representamos gráficamente el sistema de inecuaciones formado por

las restricciones y determinamos la región factible.

Representamos rectas de la forma 4x + 3y = k, rectas de nivel paralelas a la

función objetivo F (x, y) = 4x + 3y, donde k será el nivel de utilidad.

La solución óptima que se obtiene en el punto de la región factible que

hace a k, en nuestro caso es el vértice C (20; 60), para el que k = 260.

Función Objetivo:F (x, y) = 4x + 3y

Entonces, para obtener la máxima utilidad (S/. 260 mil) se deben construir 20

casas del tipo A y 60 del B.

En la práctica se representa una de las rectas de nivel (en el gráfico son las

rectas punteadas), que se desplaza paralela a sí misma hasta encontrar el

vértice (solución única) o un lado de la región factible (infinitas soluciones), que

cumplan la condición de máximo o mínimo.

PROBLEMA 2.

Utiliza el método gráfico para determinar el valor que maximiza la función objetivo F(x; y)=200x+300y en la región factible determinada por el polígono cuyos vértices son:

(0; 0), (7; 0), (6; 5), (4; 8) y (0; 7).

SOLUCIÓN:

Primero ubicamos los vértices del polígono en el plano coordenado y luego trazamos por cada uno de los vértices, las rectas de nivel: 200x+300y=k.

Se observa en el gráfico que el valor máximo de la función objetivo:

F(x; y)=200x+300y se obtiene en el vértice C(4; 8), es decir:

F(4; 8) = 200(4) + 300(8) = 320

F ( 4; 8) = 320

LECCIÓN 13

TIPOS DE SOLUCIONESLos problemas de programación lineal con dos variables pueden

presentar distintos tipos de soluciones.:

13.1 SOLUCIÓN ÚNICA

La solución es única cuando la solución óptima se encuentra sólo en uno de los

vértices.

Ejemplo:

Una fábrica prepara salsas para tallarines Extra y Gourmet. La primera

contiene 200 g de tomate y 25 g de carne por lata, la segunda 150 g de tomate

y 50 g de carne. Si se abastece de 4 toneladas de tomate y 1,25 toneladas de

carne, ¿cuántas latas deben fabricar de cada tipo para obtener la máxima

utilidad, ganando en la venta de cada una S/. 1,80 y S/. 2,30, respectivamente.

Asignamos una variable a cada una de las incógnitas :

x: número de latas de salsa Extra y: número de latas de salsa

Gourmet

Organizamos la información en una tabla:

Salsa extra Salsa Gourmet Disponibilidad

Tomate 200 g = 0,2 kg 150 g = 0,15 kg 41 = 4 000 kg

Carne 25 g = 0, 025 kg 50 g = 0, 05 kg 1,25 t = 1 250kg

Utilidad S/. 1,80 S/. 2,30

Determina las restricciones:

X ≥ 0; y ≥ 0 X ≥ 0; y ≥ 00,2x + 0,15y ≤ 4 000 4x + 3y ≤ 80 0000,025x + 0,05y ≤ 1 250 x + 2y ≤ 50 000

Planteamos la función objetivo que permita obtener la máxima utilidad:

F(x; y) = 1, 80x + 2,30y

Determinamos los vértices A (0; 0), B (0; 25 000), C (2 000; 24 000)

D (20 000; 0) y graficamos la región factible (figuradle margen).

Determinamos la solución óptima

En A: F (0; 0) = 1, 80(0) + 2, 30(0) = 0

En B: F (0; 25 000) = 1, 80(0) + 2, 30(25 000) = 57 500

En C: F (2 000; 24 000) = 1,80(2 000) + 2,30(24 000) = 58 800

En D: F (20 000; 0) 1,80(20 000) + 2,30(0) = 36 000

La máxima utilidad se obtiene en el vértice C (2 000; 24 000) solución única,

que indica que deben preparar 2 000 latas de salsa extra y 24 000 latas de

salsa gourmet. En tal caso, dicha utilidad es de S/. 58.800.

13.2 SOLUCIÓN MÚLTIPLE

La solución es múltiple cuando hay infinita soluciones que corresponden a los

puntos del segmento que tiene por extremos a dos vértices de la región

factible.

Ejemplo:1

Maximiza la función Objetivo F(x; y) para un problema donde las restricciones

son: x ≥ 0; y ≥ 0; x + y < 5; x – y ≤ 3

Determinamos los vértices y la región factible:

A (0; 0), B (0, 5), C(4; 1) y D(3; 0)

Calculamos el valor de la función objetivo en cada uno de los vértices:

En A: F(0; 0) = 0 + 0 = 0

En B: F(0; 5) = 0 + 5 = 5

En C: F(4; 1) = 4 + 1 = 5

En D: F(3; 5) = 3 + 0 = 3

La función objetivo alcanza el máximo valor en los vértices B y C, y también en

cualquiera de los puntos de BC. Por lo tanto, tiene infinitas soluciones.

Ejemplo 2

Un granjero tiene 480 hectáreas en la que puede sembrar ya sea maíz o trigo.

Calcula que dispondrá de 800 horas de trabajo durante la temporada. Los

márgenes de utilidad para cada uno de los productos son S/. 40 por hectárea y

los requerimientos laborales para trabajaren la siembra del maíz son 2 horas

por hectárea y para el trigo, 1 hora por hectárea. ¿Cuántas hectáreas de cada

cultivo debe plantar para maximizar su utilidad? ¿Cuál es la utilidad máxima?

SoluciónÓptima

x: número de hectáreas de maíz sembrado

y: número de hectáreas de trigo sembrado

Asignamos variables

Organizamos la información en una tabla

Maíz Trigo Disponibilidad

Superficie 1 hectáreas 1 hectáreas 480 hectáreas

Requerimiento laboral

2 horas 1 hora 800 horas

Utilidad S/. 40 S/. 40

Determinamos las restricciones: x ≥ 0; y ≥ 0; x + y ≤ 480; 2x + y ≤ 800

La función objetivo que maximiza la utilidad: F(x; y) = 40x + 40y

Sus vértices son: A (0; 0), B(0; 800), C(320; 160), D(400 + 0)

Graficamos, al margen, la región factible.

Calculamos el valor de la función objetivo en cada uno de los vértices:

En A: F (0; o) = 40(0) + 40(0) =0

En B: F (0; 480) = 40(0) + 40(480) =19 200

En C: F (320; 160) = 40(320) + 40(160) =19 200

En D: F (400; 0) = 40(400) + 40(0) =16 000

La máxima utilidad se obtiene en los vértices B y C, y también en cualquiera de

los puntos de BC. En todos estos casos, su máxima utilidad es S/. 19 200

13.3 SOLUCIÓN NO ACOTADA

Cuando la función objetivo no tiene valores extremos, la región factible es no

acotada.

Ejemplo

Maximiza la función objetivo F(x; y) = x + y para un problema cuyas

restricciones son: x ≥ 0; y ≥ 0; x - y ≥ 3; x - 2y ≤ 2

Resolvemos los sistemas que se forman y obtenemos (0; 0), (3; 0), 80; -

3), (0; -1), (2; 0), (4; 1)

La región factible se extiende infinitamente y su único vértice está en:

A(4; 1)

En este caso no existe un valor máximo para la función objetivo, por lo

que carece de solución.

Soluciones óptimas

13.3 SOLUCIÓN NO FACTIBLE

Cuando no existe la región factible por falta de zona común en el sistema de

inecuaciones, la solución es no factible.

Ejemplo

Sea un problema donde las restricciones son: x ≥ 0; y ≥ 0; x + y ≥ 5; 2x + y ≤ 3.

Maximiza la función objetivo F(x; y) = 3x + 2y.

Resolvemos el sistema y obtenemos:

(5; 0), 80; 0), (0; 5), (0; 3), (1,5; 0), (-2; 7)

Representamos gráficamente el sistema

Observamos que no existe región factible, ya que no hay zona común a

todas las inecuaciones.

Por lo tanto, este problema carece de solución.

LECCIÓN 14

PROBLEMAS DE APLICACIÓN

5.1 PROBLEMAS RESUELTOS

5.1.1. Modelo de problema de alimentación

Muchas formulaciones de programación lineal se presentan a partir de

situaciones en las cuales quienes toman las decisiones quieren minimizar el

costo para satisfacer un conjunto de requerimientos.

Ejemplo:

Se necesita una dieta que proporcione un mínimo de 2 400 calorías y 330 unidades de proteínas al mes, para ello se necesitan dos productos A y B. A cuesta S/. 12 el kg y contiene 40 calorías y 3 unidades de proteínas y B cuesta S/. 10 el kg y contiene 30 calorías y 6unidades de proteínas. Determine la cantidad de cada tipo de producto que debe mezclarse para que el costo sea mínimo.

SOLUCIÓN: Asignemos una variable a cada una de las incógnitas:

x: número de kg del producto A e y: número de kg del producto B. Organizamos la información en una tabla:

Producto A(x) Producto B(y) DisponibilidadCalorías 40 30 Mínimo 2400Proteínas 3 6 Mínimo 330Costo en S/. 12 10

Determinamos las restricciones del problema a partir de los datos de la tabla:

Planteamos la función objetivo que permita el costo mínimo:F(x; y) =12x +10y

Grafiquemos las relaciones que representan las restricciones:

Evaluando la función objetivo en los puntos A, B y C de la región factible, el costo mínimo se obtiene en el punto B. F(30; 40)=12(30)+40(40)=760, para ello se debe mezclar 30 kg del producto A y 40 kg del producto B.