Solución a los ejercicios

Respuestas a ejercicios de 1.1.3

x_i es proporción de aleación i-esima en aleación final. a₁i es porcentaje de A en aleación i-esima (e.g a_1,1=10). a₂i es porcentaje de B en aleación i-esima. c_i es costo por libra de aleación i-esima. Y b=(30, 70)

Sea x'=|x| y dado que x puede ser negativo, sea x=x⁺−x⁻. Como x'=|x⁺−x⁻| y como x'≥ 0 se debe dar −x'≤ |x⁺−x⁻|≤ x'. Empleando estas sustituciones y sus análogas para y y z, se tiene:

minimizar	x'+y'+z'
sujeto a	x⁺−x⁻+y⁺−y⁻≤ 1
	2(x⁺−x⁻)+(z⁺−z⁻)=3
	−x'≤ x⁺−x⁻ ≤ x'
	−y'≤ y⁺−y⁻ ≤ y'
	−z'≤ z⁺−z⁻ ≤ z'
	x',y',x⁺,x⁻, y⁺, y⁻, z⁺, z⁻ ∈ R⁺

Introduciendo variables de holgura se obtiene una forma estándar:

minimizar	x'+y'+z'
sujeto a	x⁺−x⁻+y⁺−y⁻+h₁ = 1
	2(x⁺−x⁻)+(z⁺−z⁻)=3
	−x'+h₂ = x⁺−x⁻
	x⁺−x⁻ + h₃ = x'
	−y' + h₄ = y⁺−y⁻
	y⁺−y⁻ + h₅ = y'
	−z' + h₆ = z⁺−z⁻
	z⁺−z⁻ + h₇ = z'
	x',y',x⁺,x⁻, y⁺, y⁻, z⁺, z⁻, h₁, ... h₇ ∈ R⁺

Tras plantear con base en el ejercicio anterior:

d₁=\|x₁−3\|, d₂=\|x₂\|, d₃=\|x₁\|, d₄=\|x₂+3\|, d₅=\|x₁+2\|, d₆=\|x₂−1\|, d₇=\|x₁−1\|, d₈=\|x₂−4\|
x₁=x₁⁺−x₁⁻ ...
d₁=\|x₁⁺−x₁⁻−3\| ...
minimizar	d₁+d₂+... +d₈
sujeto a	−d₁≤ x₁⁺−x₁⁻−3 ≤ d₁
	...	d₁, x₁⁺, x₁⁻, ... ≥ 0

tras resolver este sistema se obtiene x₁=x₂=1 que da como suma de distancias 14.

Respuestas a ejercicios de 1.2.3

Dada la función objetivo c^Tx, su gradiente es c, así que se maximiza moviendo las curvas en el sentido de c y se minimiza moviendo las curvas en el sentido contrario al de c. En el ejemplo presentado al comienzo de esta guía, c=(−1,−3) lo cual explica porque para minimizar debe moverse la recta 0=−x₁−3x₂ en dirección nororiental.

A =

⎛
⎝

1	1	1	0
−1	2	0	1

⎞
⎠

B_1,2 =

⎛
⎝

1	1
−1	2

⎞
⎠

con solución (x₁,x₂,s₁,s₂)=(4/3, 14/3,0,0) que es factible (y óptima),

B_1,3 =

⎛
⎝

1	1
−1	0

⎞
⎠

con solución no factible (−8,0,14,0),

B_1,4 =

⎛
⎝

1	0
−1	1

⎞
⎠

con solución factible (6,0,0,14),

B_2,3 =

⎛
⎝

1	1
2	0

⎞
⎠

con solución factible (0,4,2,0),

B_2,4 =

⎛
⎝

1	0
2	1

⎞
⎠

con solución factible (0,6,0,−4) y

B_3,4 =

⎛
⎝

1	0
0	1

⎞
⎠

con solución factible (0,0,6,8).

m bolsos de mano, r bolso para rasuradora, c mochila. Maximizar utilidad. max 24m+22r+45c

max	24m+22r+45c
sujeto a	2m+r+3c≤ 42
	2m+r+2c≤ 40
	1m+0.5r+c≤ 45
	m≥ 0, r≥ 0, c≥ 0

Cada dirección cumple Ad=0 y d≥ 0 y d≠ 0. Sean d₁ y d₂ direcciones, entonces

A(αd₁+(1−α ) d₂)	=
α Ad₁+(1−α)Ad₂	=
0+0	= 0

Así que αd₁+(1−α ) d₂) también es dirección de la región factible, con lo que se concluye que el conjunto de direcciones es convexo.

Respuestas a ejercicios de 1.3.3

Caso 1. Para todo j∈{1,... n} c_j≥ 0
En este caso c^Tx se minimiza con x=0 que también cumple x≥ 0 y Ax≤ b.
Caso 2. Sea j∈{1,... n} tal que c_j<0
1. Si para todo i∈{1,... m} se da a_ij≤ 0 tome є>0 con e_j vector unitario con 0 en todas su componentes excepto en la j-esima que es un uno. Sea x=x₀+єe_j, entonces x≥ 0 y además Ax≤b porque
  a_ix=−|a_ij|є+ a_ix₀≤ a_ix₀ < b
  y además
  c^Tx = c^Tx₀−|c_j|є < c^Tx₀
2. Si existe i tal que a_ij>0. Sea
  
  є=
  
  min
  
  i
  {
  
  b_i−a_ix₀
  
  a_ij
  : a_ij>0 }
  entonces є>0 porque a_ix₀<b_i y a_ij>0.
  
  Sea x=x₀+єe_j entonces x≥x₀>0 y para cada i∈1... m se da
  a_ix=a_ix₀+a_ijє
  Si a_ij≤ 0 tenemos a_ix≤a_ix₀<b_i.
  
  Si a_ij> 0 como є≤ b_i−a_ix₀ /a_ij tenemos a_ix=a_ix₀+a_ijє≤ a_ix₀+b_i−a_ix₀=b_i.
  
  Entonces Ax≤b y nuevamente c^Tx<c^Tx₀.

Capítulo 6 Solución a los ejercicios

Respuestas a ejercicios de 1.1.3

Respuestas a ejercicios de 1.2.3

Respuestas a ejercicios de 1.3.3

Respuestas a ejercicios de 1.4.3

Respuestas a ejercicios de 1.5.3

Respuestas a ejercicios de 2.1.3

Respuestas a ejercicios de 3.1.3

Respuestas a ejercicios de 3.2.3

Respuestas a ejercicios de 3.3.3

Respuestas a ejercicios de 4.1.3

Respuestas a ejercicios de 5.1.3

Respuestas a ejercicios de 5.2.3