Using the bounding method. Given $\max \{c^Tx \ | \ Ax = b, x \ge 0 \}$ we want to find multipliers $y\in \mathbb{R}^n$ s.t. $y^TAx = y^Tb$, we have equalities, so $y^T$ can be both positive and negative.
We want to find an upper bound: $c^Tx\le y^TAx$. Since $x\ge 0$ we can rewrite as $c^T\le y^TA$. Taking the transpose of both sides using the rule $(AB)^T=B^TA^T$ will yield:
$y^TA \ge c^T \implies (y^TA)^T \ge (c^T)^T \implies A^Ty \ge c$
Since we want to find the best upper bound and have the relation: $c^Tx \le y^TAx = y^Tb$, we want to minimize $y^Tb$ s.t. $A^Ty \ge c$, hence we have the dual:
$\min \{y^Tb \ | \ A^Ty \ge c \}$ or $\min \{y^Tb \ | \ y^TA \ge c \}$
The primal problem:
$\begin{aligned} \text{max} & \qquad 2x_1+3x_2 & \\ \text{s.t} & \qquad 2x_1+3x_2 \le 30 & \\ & \qquad x_1+2x_2 \ge 10 & \\ & \qquad x_1-x_2 \le 1 & \\ & \qquad -x_1+x_2 \le 1 & \\ & \qquad x_1 \ge 0 & \end{aligned}$
The dual problem:
$\begin{aligned} \text{min} & \qquad 30y_1+10y_2+y_3+y_4 & \\ \text{s.t} & \qquad 2y_1+y_2+y_3-y_4 \ge 2 & \\ & \qquad 3y_1+2y_2-y_3+y_4 = 3 & \\ & \qquad y_1,y_3,y_4 \ge 0 & \\ & \qquad y_2 \le 0 & \end{aligned}$
Since $x_1 = 27/5, x_2 = 32/5 $ are both above $0$ we have the two first constraints:
$\begin{aligned} \text{s.t} & \qquad 2y_1+y_2+y_3-y_4 = 2 & \\ & \qquad 3y_1+2y_2-y_3+y_4 = 3 & \\ \end{aligned}$
Now we can test which constraints are binding in the primal problem.
x1 = 27/5.
x2 = 32/5.
print("1. constraint: ",round(2*x1+3*x2,4),"= 30")
print("2. constraint:",round(-x1-2*x2,4),"= -10")
print("3. constraint:",x1-x2," = 1")
print("4. constraint: ",x2-x1," = 1")
We can see that the second and third constraints are non-binding, then $y_2,y_3 = 0$ and we have the following system of equations:
$\begin{aligned} & \qquad 2y_1+y_2+y_3-y_4 = 2 & \\ & \qquad 3y_1+2y_2-y_3+y_4 = 3 & \\ & \qquad y_2=0 \\ & \qquad y_3=0 \end{aligned}$
Then we have that:
$\begin{aligned} & \qquad 2y_1+y_2= 2 \implies y_2 = 2-2y_1& \\ & \qquad 3y_1+2y_2 = 3 \\ \end{aligned}$
We insert $y_2$ in the second equation:
$\begin{aligned} & \qquad 3y_1+2(2-2y_1) = 3 \implies 3y_1+4-4y_1 = 3 \\ & \qquad \implies -y_1=-1 \implies y_1 = 1 \end{aligned}$
Then we have that:
$\begin{aligned} & \qquad y_2 = 2-2*1=0 \end{aligned}$
So the optimal solution to the dual is:
$y_1=1, y_2 =0, y_3=0, y_4=0$
The primal problem:
$\begin{aligned} \text{max} & \qquad 5x_1+4x_2+3x_3 & \\ \text{s.t} & \qquad 2x_1+3x_2+x_3 \le 5 & \\ & \qquad 4x_1+x_2+2x_3 \le 11 & \\ & \qquad 3x_1+4x_2+2x_3 \le 8 & \\ & \qquad x_1,x_2,x_3 \ge 0 & \end{aligned}$
The dual problem:
$\begin{aligned} \text{min} & \qquad 5y_1+11y_2+8y_3& \\ \text{s.t} & \qquad 2y_1+4y_2+3y_3 \ge 5 & \\ & \qquad 3y_1+y_2+4y_3 \ge 4 & \\ & \qquad y_1+2y_2+2y_3 \ge 3 & \\ & \qquad y_1,y_2,y_3 \ge 0 & \end{aligned}$
If the Complementary slackness theorem holds and the objective value for the primal and dual is the same, then the solution $(2,0,1)$ is optimal. We check that it does:
Since $x_1,x_3 >0$ we have the two constraints:
$\begin{aligned} & \qquad 2y_1+4y_2+3y_3 = 5 & \\ & \qquad y_1+2y_2+2y_3 = 3 & \\ \end{aligned}$
Now we can test which constraints are binding in the primal problem.
x1 = 2.
x2 = 0.
x3 = 1
print("1. constraint:",2*x1+3*x2+x3," = 5")
print("2. constraint:",4*x1+x2+2*x3,"= 11")
print("3. constraint:",3*x1+4*x2+2*x3," = 8")
We can see that the second constraint is non-binding, then $y_2=0$ and we have the following system of equations:
$\begin{aligned} & \qquad 2y_1+4y_2+3y_3 = 5 & \\ & \qquad y_1+2y_2+2y_3 = 3 & \\ & \qquad y_2 = 0 & \end{aligned}$
Then we have that:
$\begin{aligned} & \qquad 2y_1+3y_3 = 5 & \\ & \qquad y_1+2y_3 = 3 & \end{aligned}$
Solved as before will give $y_1=1, y_3=1$.
Then the solution is:
$y_1^*=1, y_2^*=0, y_3^*=1$
We need to check if it is feasible. We have already checked the conditions for the primal problem and we have already checked the first and thrid constraint in the dual, so we need to check the second constraint of the dual. It needs to be non-binding since $x_2=0$:
$\begin{aligned} & \qquad 3y_1^*+y_2^*+4y_3^* > 4 & \\ \implies & \qquad 3*1+0+4*1 > 4 \\ \implies & \qquad 7 > 4 \end{aligned}$
So its non-binding.
We check that the objective values are the same:
For the primal: $5*2+4*0+3*1 = 13 $
For the dual: $5*1+11*0+8*1 = 13 $
Then the solution is optimal.
from pyscipopt import *
import numpy as np
m = Model("activity")
c = [5,4,3]
ir = range(1,4)
x = {}
# Variables
for i in ir:
x[i] = m.addVar(vtype = "C", name = "x(%s)" % i)
# Objective
m.setObjective(quicksum(c[i-1]*x[i] for i in ir),"maximize")
# Constraints
c1 = m.addCons(2*x[1]+3*x[2]+x[3] <= 5)
c2 = m.addCons(4*x[1]+x[2]+2*x[3] <= 11)
c3 = m.addCons(3*x[1]+4*x[2]+2*x[3] <= 8)
m.optimize()
print("obj =", m.getObjVal())
print()
print("The primal values")
for i in ir:
print("x[%s] = %s" % (i,m.getVal(x[i])))
print()
print("The dual values:")
print("y[%s] =" %1,m.getDualsolLinear(c1))
print("y[%s] =" %2,m.getDualsolLinear(c2))
print("y[%s] =" %3,m.getDualsolLinear(c3))
The primal problem:
$\begin{aligned} \text{min} & \qquad 3x_1+2x_2-4x_3& \\ \text{s.t}& \qquad 2x_1+x_2+x_3 \ge 3 & \\ & \qquad x_1+x_2+2x_3 \le 5 & \\ & \qquad x_i \ge 0 & \forall i \in \{1,2,3\} \end{aligned}$
Rewrite:
$\begin{aligned} \text{max} & \qquad -3x_1-2x_2+4x_3& \\ \text{s.t}& \qquad -2x_1-x_2-x_3 \le -3 & \\ & \qquad x_1+x_2+2x_3 \le 5 & \\ & \qquad x_i \ge 0 & \forall i \in \{1,2,3\} \end{aligned}$
The dual problem:
$\begin{aligned} \text{min} & \qquad -3u_1+5u_2& \\ \text{s.t} & \qquad -2u_1+u_2 \ge -3 & \\ & \qquad -u_1+u_2 \ge -2 & \\ & \qquad -u_1+2u_2 \ge 4 & \\ & \qquad u_1,u_2 \ge 0 & \end{aligned}$
Now we want to find a solution to the primal. Since $u_1,u_2>0$ then we have the two constraints:
$\begin{aligned} & \qquad -2x_1-x_2-x_3 = -3 & \\ & \qquad x_1+x_2+2x_3 = 5 & \\ \end{aligned}$
We check which constraints are binding in the dual:
u1 = 10/3
u2 = 11/3
print("1. constraint:",round(-2*u1+u2,4)," = -3")
print("2. constraint:",round(-u1+u2,4,),"= -2")
print("3. constraint:",round(-u1+2*u2,4)," = 4")
We see that the second constraint is non-binding, hence $x_2=0$. And we have the following system of equations:
$\begin{aligned} & \qquad -2x_1-x_2-x_3 = -3 & \\ & \qquad x_1+x_2+2x_3 = 5 & \\ & \qquad x_2 = 0 & \end{aligned}$
Hence we have:
$\begin{aligned} & \qquad -2x_1-x_3 = -3 & \\ & \qquad x_1+2x_3 = 5 \implies x_1=5-2x_3& \end{aligned}$
Then we can insert $x_1$ in the first equation:
$\begin{aligned} & \qquad \implies -2(5-2x_3)-x_3 = -3 \implies -10+3x_3=-3 \implies 3x_3=7 \implies x_3 = 7/3 \end{aligned}$
And we can find $x_1$:
$\begin{aligned} \qquad x_1=5-2x_3=5-2*7/3 = 1/3 \end{aligned}$
Then the solution of the primal is: $x_1=1/3, x_2=0, x_3=7/3$
from pyscipopt import *
import numpy as np
m = Model("activity")
c = [-3,-2,4]
ir = range(1,4)
x = {}
# Variables
for i in ir:
x[i] = m.addVar(vtype = "C", name = "x(%s)" % i)
# Objective
m.setObjective(quicksum(c[i-1]*x[i] for i in ir),"maximize")
# Constraints
d1 = m.addCons(-2*x[1]-x[2]-x[3] <= -3)
d2 = m.addCons(x[1]+x[2]+2*x[3] <= 5)
for i in ir:
m.addCons(x[i]>=0)
m.optimize()
print("obj =", m.getObjVal())
print()
for i in ir:
print("x[%s] = %s" % (i,m.getVal(x[i])))
Let $I=\{1,2,3,4\}$ be the projects.
Let $J=\{1,2,3,4,5\}$ be the years.
Let $x_{i}$ be the amount invested in project $i\in I$.
Let $y_j$ be the amount invested in the bank at year $j\in J\backslash\{5\}$ with $y_5$ being the total amount available at the start of year 5.
Then we can formulate the problem.
The LP:
$\begin{aligned} \text{max} & \qquad y_5 & \\ \text{s.t}& \qquad x_1+x_2+x_4+y_1\le 10000 & \text{budget}\\ & \qquad 0.5x_1+0.6x_2-x_3+0.4x_4+1.065y_1 = y_2 & \\ & \qquad 0.3x_1+0.2x_2+0.8x_3+0.6x_4+1.065y_2 = y_3 & \\ & \qquad 1.8x_1+1.5x_2+1.9x_3+1.8x_4+1.065y_3 = y_4 & \\ & \qquad 1.2x_1+1.3x_2+0.8x_3+0.95x_4+1.065y_4 = y_5 & \\ & \qquad x_i, y_j \ge 0 & \forall i \in I, \ \forall j \in j \end{aligned}$
The objective is the amount of DKK available at the start of year 5.
The first constraint is the budget constraint. The rest of the constraints ensures that we reinvest any fund avaible and we dont have negative values.
from pyscipopt import *
import numpy as np
m = Model("investor")
ir = range(1,5)
jr = range(1,6)
x = {}
y = {}
A = [[0.5,0.6,-1,0.4],
[0.3,0.2,0.8,0.6],
[1.8,1.5,1.9,1.8],
[1.2,1.3,0.8,0.95]]
# Variables
for i in ir:
x[i] = m.addVar(vtype = "C", name = "x(%s)" % i)
for j in jr:
y[j] = m.addVar(vtype = "C", name = "y(%s)" % j)
# Objective
m.setObjective(y[5],"maximize")
# Constraints
m.addCons(x[1]+x[2]+x[4]+y[1] <= 10000)
for j in range(0,4):
m.addCons(quicksum(A[j][i]*x[i+1] for i in range(0,4))+1.065*y[j+1] == y[j+2])
for i in ir:
m.addCons(x[i]>=0)
for j in jr:
m.addCons(y[j]>=0)
m.optimize()
print("obj =", m.getObjVal())
print()
for i in ir:
print("x[%s] = %s" % (i,m.getVal(x[i])))
print()
for j in jr:
print("y[%s] = %s" % (j,round(m.getVal(y[j]),4)))
Last task from the first test. Let $J=\{1,2,3,4\}$ be the set of choices, let $I=\{1,2,3\}$ be the set of outcomes.
Let $x_j$ be the amount deposited in choice $j\in J$.
Let $r_{ij}$ be the return for outcome $i\in I$ for choice $j\in J$.
Let the return be denoted by $z\in \mathbb{R}$, then we can bound our return by the worst outcome, by bounding it for each of the outcome $i\in I$. This means that our return, cannot exceed the worst outcome, since it is bounded by all three.
Then the LP looks as follows:
$\begin{aligned} \text{max} & \qquad z & \\ \text{s.t} & \qquad z \le \sum\limits_{j=1}^4r_{ij}x_j, & \qquad i\in I \\ & \qquad \sum\limits_{j=1}^4x_j\le 1500 & \\ & \qquad x_i \ge 0, & \forall j \in j \\ & \qquad z \in \mathbb{R} \end{aligned}$
The first constraint bounds our return by all outcomes. The second is the budget constraint.
from pyscipopt import *
import numpy as np
m = Model("gambler")
ir = range(1,4)
jr = range(1,5)
x = {}
r = [[-3,4,-7,15],
[5,-3,9,4],
[3,-9,10,-8]]
# Variables
z = m.addVar(vtype = "C", name = "z")
for j in jr:
x[j] = m.addVar(vtype = "C", name = "x(%s)" % j)
# Objective
m.setObjective(z,"maximize")
# Constraints
m.addCons(quicksum(x[j] for j in jr) <= 1500)
for i in ir:
m.addCons(z <= quicksum(r[i-1][j-1]*x[j] for j in jr))
for j in jr:
m.addCons(x[j]>=0)
m.optimize()
print("obj =", m.getObjVal())
print()
for j in jr:
print("x[%s] = %s" % (j,m.getVal(x[j])))