I. NOCIÓNS BÁSICAS DE PROGRAMACIÓN MATEMÁTICA
Un p oblema de op imización én dado po un pa (F, c), onde F é o conxun o de pun os ac ibles e c é a unción de cus o. O
p oblema consis e en a opa un pun o ac ible x
∈
F al que, pa a odo y
∈
F , se cump a que c(x) ≤ c(y). Dise que o pun o x nes as
condicións é unha solución óp ima do p oblema.
Nese con ex o, un p oblema de p og amación ma emá ica consis e en a opa unha solución ao p oblema:
Minimiza x
∈
Rn c(x)
suxei o a gi(x) ≤ 0, pa a cada i = 1, . . . , m
hj(x) = 0, pa a cada j = 1, . . . , l,
onde:
• x = (x1, . . . , xn)
∈
Rn son as a iables de decisión pa a as que buscamos unha con igu ación de alo es óp ima.
• A unción c ep esen a a unción de cus o a minimiza (ou bene icio a maximiza ) asociado a cada combinación das
a iables de decisión.
• As es icións son uncións que ep esen an que con igu acións de alo es das a iables x1, . . . , xn son ac ibles. O
conxun o de pun os x que as cump en denomínase exión ac ible. Dis ínguense dous ipos de es icións:
o Res icións de desigualdade, gi(x) ≤ 0, pa a cada i = 1, . . . , m.
o Res icións de igualdade, hj(x) = 0, pa a cada j = 1, . . . , l.
A PROGRAMACIÓN LINEAL
Un p oblema de p og amación lineal é un caso pa icula de p oblema de p og amación ma emá ica no que as uncións usadas
como unción obxec i o a minimiza e as es icións son lineais.
Os elemen os que o compoñen
son:
• Vec o de cus os, c
∈
Rn.
• Ma iz de es icións, A
∈
Rm×n,
cos seus elemen os da o ma aij.
• Vec o de lados de ei os, b
∈
Rm.
minimiza c1x1 + c2x2 + · · · + cnxn
suxei o a a11x1 + a12x2 + · · · + a1nxn ≤ b1
a21x1 + a22x2 + · · · + a2nxn ≤ b2 e, equi alen emen e minimiza c·x
. . . . . . . . . . . . . . . en o ma ma icial, suxei o a Ax ≤ b
am1x1 + am2x2 + · · · + amnxn ≤ bm x ≥0.
xi ≥ 0, i
∈
{1, . . . , n}.
Cómp e des aca que aínda que se o mulou o p oblema de p og amación lineal en e mos da minimización de cus os, a
maximización de bene icios amén admi e unha modelización análoga ao conside a o ec o c como un ec o de ganancias
asociadas a cada unha das a iables de decisión.
A PROGRAMACIÓN LINEAL NA HISTORIA
Os p oblemas de p og amación lineal o múlanse como modelos ma emá icos e xo den du an e a
Segunda Gue a Mundial, no século XX, co obxec i o de plani ica os p oblemas loxís icos e
es a éxicos do exé ci o ame icano. Po exemplo, usá onse pa a a plani icación do aslado de
opas dos Es ados Unidos a Eu opa ou deseña a die a dos soldados nunha con o na de escaseza
de ecu sos a mínimo cus o ou pa a de e mina o amaño dos con ois ame icanos.
A PROGRAMACIÓN LINEAL NA ACTUALIDADE
A p og amación lineal ecibiu un g an pulo g azas ao desen ol emen o de o denado es, o que pe mi iu
esol e p oblemas nes a clase cada ez máis g andes e usalos en con ex os moi di e en es. En e as
súas aplicacións, des aca o seu emp ego en eidos como o da enxeña ía, o da economía, ou o da bioloxía,
pa a deseña u as de ehículos, op imiza luxos en edes, deseña sis emas de con ol de á ico,
manexa de manei a óp ima ca ei as inancei as, op imiza o uso da in o mación en bioin o má ica ou
o seu emp ego como écnica de ap endizaxe au omá ica no eido da in elixencia a i icial.
INTRODUCIÓN Á PROGRAMACIÓN LINEAL
Resolución de p oblemas de p og amación lineal median e so wa e lib e
Lau a Da ila Pena, Alejand o Saa ed a Nie es e Balbina Casas Méndez
Depa amen o de Es a ís ica, Análise Ma emá ica e Op imización
II. FORMULACIÓN E RESOLUCIÓN DUN PROBLEMA DE PROGRAMACIÓN LINEAL
Nes a sección p opoñe emos un caso ealis a que pode se modelado usando écnicas de p og amación lineal. O obxec i o é
dob e, xa que ademais de ilus a o expos o na sección an e io , abo da ase a súa esolución. Dado que se a a dun p oblema
con dúas únicas a iables de decisión, se á ácil obse a a súa esolución dende o pun o de is a g á ico. Ademais, ilus a ase
o emp ego de so wa e lib e na esolución des a clase de p oblemas.
O PROBLEMA DA EMPRESA DE PINTURAS
Unha emp esa ab ica pin u a pa a ex e io es e pin u a pa a in e io es. A emp esa debe decidi a can idade (en oneladas)
que ai ab ica de cada ipo de pin u a, sabendo que po cada onelada de pin u a de ex e io es gaña á 5.000 eu os, e po
cada onelada de pin u a pa a in e io es gaña á 4.000 eu os. Non obs an e, debe espec a ce as es icións:
• Hai dúas ma e ias p imas A e B, das que só se dispón de 24 e 6 oneladas, espec i amen e.
• Cada onelada de pin u a de ex e io es equi e de 6 oneladas da ma e ia p ima A e 1 onelada da ma e ia p ima B.
• Cada onelada de pin u a de in e io es equi e de 4 oneladas da ma e ia p ima A e 2 oneladas da ma e ia p ima B.
• Ademais, unha enquisa de me cado indica que a demanda de pin u a pa a in e io es non pode se maio que 1
onelada máis que a de pin u a pa a ex e io es.
• Po úl imo, sábese que a demanda máxima de pin u a pa a in e io es é de 2 oneladas.
OBXECTIVO: Cal é a can idade óp ima que se debe p oduci de cada ipo de pin u as?
FORMULACIÓN DO PROBLEMA: Se deno amos po x a can idade de oneladas pa a p oduci de pin u a de ex e io es e po y
a can idade de oneladas de pin u a de in e io es, a ganancia pola p odución é 5x + 4y, de manei a que hai que de e mina
os alo es de x e y que maximicen a de andi a ganancia.
Á ez, as es icións amén se poden exp esa en e mos de x e y, de manei a que a o mulación comple a se poida ep esen a
como segue.
maximiza 5x + 4y
suxei o a 6x + 4y ≤ 24
x + 2y ≤ 6
−x + y ≤ 1
y ≤ 2
x ≥ 0, y ≥ 0.
II. i. RESOLUCIÓN MEDIANTE O PROGRAMA R
Nes a sección mos amos os pasos a segui pa a esol e un p oblema de p og amación lineal no so wa e , que pode ob e se
lib emen e dende h ps://cloud. -p ojec .o g/. Unha ez ins alado, necesi amos dispoñe do paque e lpSol eAPI, que se á o
que nos pe mi a a a ales p oblemas. Pa a iso, ab imos e esc ibimos a o de ins all.packages(“lpSol eAPI”). Es e
paque e só necesi a ins ala se a p imei a ez que o imos emp ega .
Paso 1: ca ga da lib a ía e cons ución do p oblema
Paso 2: coe icien es da unción obxec i o e das es icións
En p imei o luga ca gamos a lib a ía lpSol eAPI. Logo
cons uímos un p oblema de p og amación lineal con 4
es icións e 2 a iables, median e a unción make.lp().
In oducimos os coe icien es das a iables na unción obxec i o e nas
es icións u ilizando as uncións se .obj n() e se . ow(),
espec i amen e.
Paso 3: signo das es icións e lados de ei os
Paso 4: ipo de p oblema de op imización
Median e a unción se .cons . ype(), indicamos que as
es icións son de “≤”. Logo, in oducimos os alo es dos lados
de ei os das es icións u ilizando se . hs().
A con inuación, debemos indica que o obxec i o é maximiza , pa a o
cal emp egamos a unción lp.con ol().
Paso 5: esolución do p oblema
Paso 6: alo es das a iables, unción obxec i o e lados esque dos das
es icións no óp imo
Emp egamos a unción sol e() pa a esol e o noso
p oblema de op imización.
Que a saída sexa 0 signi ica que se a opou unha solución ac ible
óp ima ao noso p oblema.
Median e as uncións ge . a iables(), ge .objec i e() e
ge .cons ain s(), podemos ob e os alo es das a iables, a
unción obxec i o e os lados esque dos das es icións,
espec i amen e, no óp imo.
Rep esen ación g á ica
Pa a ep esen a o conxun o ac ible debemos emp ega a
unción plo .lpEx P (). Unha ez cons uído o conxun o
ac ible, de inimos as cu as de ni el da unción obxec i o e
ep esen ámolas sob e a g á ica que con én o conxun o ac ible
median e a unción con ou . Finalmen e, engadimos sob e
es a g á ica o pun o onde se alcanza a solución óp ima, (3, 1.5),
pa a o cal emp egamos a unción poin s.
II. ii. RESOLUCIÓN MEDIANTE A FOLLA DE CÁLCULO DE LIBREOFFICE
Nes a sección mos amos os pasos a segui pa a esol e un p oblema de p og amación lineal median e a olla de cálculo da
e amen a Lib eO ice , que pode ob e se lib emen e dende h ps://es.lib eo ice.o g/.
Paso 1: no o ichei o e in odución dos da os
do p oblema
En p imei o luga , ab imos unha olla de
cálculo no a en Lib eO ice e in oducimos os
da os do p oblema: coe icien es das
es icións e da unción obxec i o. É ú il i ula
as celas da olla e mesmo usa co es.
Paso 2: inicialización das a iables e unción
obxec i o
Inicializamos as a iables do noso p oblema a
0. Na cela B9, po exemplo, in oducimos a
unción obxec i o po medio do comando
SUMARPRODUTO.
Paso 3a: a unción dunha es ición
Na cela D4 in oducimos a unción que de ine
a p imei a es ición no amen e po medio do
comando SUMARPRODUTO.
Paso 3b: as uncións das es an es es icións
De o ma análoga in odúcense as uncións
que de inen as es an es es icións.
Paso 4: e amen a solucionado e
iden i icación de a iables, ipo de obxec i o e
es icións
A con inuación, no bo ón “Fe amen as” do
menú supe io seleccionamos
“Solucionado ” e apa ece un cad o de
diálogo. No cad o, indícase que a cela de
des ino (obxec i o) a ópase na cela B9, que
o ipo de obxec i o é de Máximo e que as
celas cambian es ( a iables) son B2 e C2.
En can o ás Condicións limi ado as
( es icións), indicamos que as e e encias
de celas ( uncións) es án en e as celas D4
e D7, odas as es icións son de ipo “≤” e os
alo es (lados de ei os das es icións)
a ópanse en e as celas E4 e E7.
Paso 5: opcións da e amen a sol e
Xa só nos queda en a en Opcións (pa e
in e io do cad o de diálogo), ma ca en
Supoñe a iábeis non nega i as e
selecciona un Solucionado linea .
Paso 6: isualización da solución óp ima
Unha ez acep adas as opcións
seleccionadas e as pulsa no bo ón de
Soluciona e Man e o esul ado, nas
celas co esponden es ás a iables do
p oblema podemos e a súa solución óp ima
(3 e 1,5), a cela da unción obxec i o mos a á
o seu alo óp imo (21) e nas celas dos lados
esque dos das es icións, os seus alo es no
óp imo.
Re e encias:
[1] Hillie , F. & Liebe man, G. (2010). In oducción a la in es igación de ope aciones. McG aw-Hill.
