🏗️ $\Theta \rho ϵ\eta \Pi \alpha \tau \pi$🚧 (under construction)

When constructing the dual, we want to try to find some upper bound on the maximization goal, we do this by multiplying all of our equations by positive constants $y_1,y_2,y_3\ge 0$, we obtain $$\begin{gathered} {\displaystyle y_1(x_1-x_2-x_3+3x_4)\le y_1 \\ {y}_2(5x_1+x_2+3x_3+8x_4)\le y_2·55 \\ {y}_3(-x_1+2x_2+3x_3-5x_4)\le y_3·3 \\ } \end{gathered}$$ by summing all the equations we obtain the following equation: $${\displaystyle x_1(y_1+5y_2-y_3)+x_2(-y_1+y_2+2y_3)+x_3(-y_1+3y_2+3y_3)+x_4(3y_1+8y_2-5y_3)\le y_1+55y_2+3y_3}$$ We see that the LHS is upperbounded by the RHS, we know that by minimizing the upper-bound to be as small as possible this will force the solution to the dual to be equal to the solution of the primal, so we must minimize : $${\displaystyle y_1+55y_2+3y_3}$$ under the constraints: $$\begin{gathered} {\displaystyle \&y_1+5y_2-y_3\ge 4 \\ \&-y_1+y_2+2y_3\ge 1 \\ \&-y_1+3y_2+3y_3\ge 5 \\ \&3y_1+8y_2-5y_3\ge 3} \end{gathered}$$ this is the dual.

Now we want to use the simplex algorithm to solve the given question. Next we re-write our question in the slack form, which is the following:

The first stage of the simplex algorithm is to note that $x_i=0$ is a feasible solution, because $1,55,3>0$ and is a vertex of our polytope. Since we already have a vertex let's move to another vertex to increase our objective value $z$. Right now we know that $x_i=0$, so increase $z$ we may increase any such $x_i$ that has a positive coefficient, for example we pick $x_1$ and call it our "entering variable".

Given this choice, let's see how much we can increase the value of $x_1$, recall that we already know that $x_2,x_3,x_4=0$, by $\alpha$ we obtain the equation $x_5=1-x_1⟺x_1=1-x_5\le 1$, by $\beta$ we know $5x_1\le 55⟺x_1\le 11$ and through $\gamma$ we have that $0\le 3+x_1⟺-3\le x_3$, which doesn't add any new information. So the tightest obstacle is the one produced by $\alpha$ which states that $x_1\le 1$. Therefore we can safely increment $x_1=1$, instead of actually setting this value, we instead do something different, we instead take equation $\alpha$ and then solve the tighest obstacle for the nonbasic varaible $${\displaystyle x_1=1+x_2+x_3-3x_4-x_5}$$ Here we say that $x_1$ is the "entering varaible" because it has entered the LHS, and we say that $x_5$ is an "leaving variable" because $x_5$ has left the LHS. Now what we do is that we subsitute this value of $x_1$ in all the other parts of the slack form: $${\displaystyle \begin{array}{cc}\hfill z& :=4(1+x_2+x_3-3x_4-x_5)+x_2+5x_3+3x_4\hfill \\ \hfill & =4+5x_2+9x_3-9x_4-x_5\hfill \\ \hfill x_1& =1+x_2+x_3-3x_4-x_5\left(\alpha \right)\hfill \\ \hfill x_6& :=55-5(1+x_2+x_3-3x_4-x_5)-x_2-3x_3-8x_4\hfill \\ \hfill & =50-6x_2-8x_3+7x_4+5x_5\left(\beta \right)\hfill \\ \hfill x_7& :=3+(1+x_2+x_3-3x_4-x_5)-2x_2-3x_3+5x_4\hfill \\ \hfill & =4-x_2-2x_3+2x_4-x_5\left(\gamma \right)\hfill \end{array}}$$ At this point we see that after one interation we've increased $z=0$ to $z=4$, now we repeat this process. So we pick $x_2$ since it has a positive coefficient, then we can look at the rest of the constraints: $${\displaystyle \begin{array}{cc}\hfill z& =4+5x_2+9x_3-9x_4-x_5\hfill \\ \hfill x_1& =1+x_2+x_3-3x_4-x_5\left(\alpha \right)\hfill \\ \hfill x_6& =50-6x_2-8x_3+7x_4+5x_5\left(\beta \right)\hfill \\ \hfill x_7& =4-x_2-2x_3+2x_4-x_5\left(\gamma \right)\hfill \end{array}}$$ We see that $\alpha$ yields $0\le 1+x_2⟺-1\le x_2$ , $\beta$: $0\le 50-6x_2⟺x_2\le 12$, $\gamma$: $x_2\le 4$, the tighest obstcale is given by $\gamma$ with $x_2\le 4$ by re-arranging $\gamma$ we obtain that $${\displaystyle x_2=4-2x_3+2x_4-x_5-x_7}$$ we now substitute this in to obtain $${\displaystyle \begin{array}{cc}\hfill z& =4+5(4-2x_3+2x_4-x_5-x_7)+9x_3-9x_4-x_5\hfill \\ \hfill & =24-x_3+x_4-6x_5-5x_7\hfill \\ \hfill x_1& =1+(4-2x_3+2x_4-x_5-x_7)+x_3-3x_4-x_5\left(\alpha \right)\hfill \\ \hfill & =5-x_3-x_4-2x_5-x_7\hfill \\ \hfill x_6& =50-6(4-2x_3+2x_4-x_5-x_7)-8x_3+7x_4+5x_5\left(\beta \right)\hfill \\ \hfill & =26+4x_3-5x_4+11x_5+6x_7\hfill \\ \hfill x_2& =4-2x_3+2x_4-x_5-x_7\left(\gamma \right)\hfill \end{array}}$$ At this point there is one last varaible with a positive coefficient in $z$'s equation which is $x_4$, so we look at the equations again to find the tighest obstacle: $${\displaystyle \begin{array}{cc}\hfill z& =24-x_3+x_4-6x_5-5x_7\hfill \\ \hfill x_1& =5-x_3-x_4-2x_5-x_7\left(\alpha \right)\hfill \\ \hfill x_6& =26+4x_3-5x_4+11x_5+6x_7\left(\beta \right)\hfill \\ \hfill x_2& =4-2x_3+2x_4-x_5-x_7\left(\gamma \right)\hfill \end{array}}$$

• $\alpha$: $x_4\le 5$
• $\beta$: $5x_4\le 26⟺x_4\le \frac{26}{5}$
• $\gamma$: $0\le 4+2x_4⟺-2\le x_4$

We know that $5=\frac{25}{5}<\frac{26}{5}$ so then $\alpha$ produces the tightest constraint, solving for $x_4$ in that equation yields $${\displaystyle x_4=5-x_1-x_3-2x_5-x_7}$$ now we can substitute that value everwhere: $${\displaystyle \begin{array}{cc}\hfill z& =24-x_3+(5-x_1-x_3-2x_5-x_7)-6x_5-5x_7\hfill \\ \hfill & =29-x_1-2x_3-8x_5-6x_7\hfill \\ \hfill x_4& =5-x_1-x_3-2x_5-x_7\left(\alpha \right)\hfill \\ \hfill x_6& =26+4x_3-5(5-x_1-x_3-2x_5-x_7)+11x_5+6x_7\left(\beta \right)\hfill \\ \hfill & =1+5x_1+9x_3+22x_5+11x_7\hfill \\ \hfill x_2& =4-2x_3+2(5-x_1-x_3-2x_5-x_7)-x_5-x_7\left(\gamma \right)\hfill \\ \hfill & =14-2x_1-4x_3-6x_5-3x_7\hfill \end{array}}$$ which we can concicely write as $${\displaystyle \begin{array}{cc}\hfill z& =29-x_1-2x_3-8x_5-6x_7\hfill \\ \hfill x_4& =5-x_1-x_3-2x_5-x_7\left(\alpha \right)\hfill \\ \hfill x_6& =1+5x_1+9x_3+22x_5+11x_7\left(\beta \right)\hfill \\ \hfill x_2& =14-2x_1-4x_3-6x_5-3x_7\left(\gamma \right)\hfill \end{array}}$$ At this point we can see that there are no non-basic varaibles with positive coefficient and so our answer is given by $x_1,x_3,x_5,x_7=0$ and $x_4=5,x_6=1,x_2=14$ which gives optimal value $z=29$.

Suppose that the center point of some disk is given by $C=(c_1,c_2)$, and that it has radius $r>0$, if this disk is to lie within the polygon generated by the lines, then for any specific line inequality, every point in the disk must lie with

An equivalent criterion for this to be true is the simple requirement that the closest point on the line to be distance at least $r$ from $C$. If this holds true for every such line, then we know that the disk centered at $C$ with radius $r$ must be within the polygon.

We'll now focus on how we can determine if the closest point on any given line is at least distance $r$ away from $C$.

We are interested in $Z$ which represents the distance from $C$ to the closest point on the line, for now just observe that there is a similar triangle hidden in here:

Since the two triangles are similar then we have that $${\displaystyle \frac{c_2-a{c}_1+b}{Z}=\frac{x}{z}}$$ We also know some more information about this smaller triangle. Since it sits on the line $y=ax+b$ then we know that the left side of this triangle is equal to $za$, and therefore $z^2+{\left(az\right)}^2=x^2⟺x=z\sqrt{a^2+1}$ so that $\frac{x}{z}=\sqrt{a^2+1}$, and therefore $${\displaystyle \frac{c_2-a{c}_1+b}{Z}=\sqrt{a^2+1}⟺Z=\frac{c_2-a{c}_1+b}{\sqrt{a^2+1}}}$$ With respect to our original goal, we would require that $Z\ge r$.

Let's take a moment to note that we've just dealt with a line which would bound the disk below, if the line were to bound the disk by above then the value $c_2-a{c}_1+b$ would be a negative value, so that we would require $-Z\ge r$.

With all that said we maximize $r$ subject to $${\displaystyle \frac{c_2-a_i{c}_1-b_i}{\sqrt{a_i^2+1}}\ge r}$$ for $i\in [1,\dots k]$ and $${\displaystyle -\frac{c_2-a_j{c}_1-b_j}{\sqrt{a_j^2+1}}\ge r}$$ for $j\in [k+1,\dots ,n]$, where $c_1,c_2,\in \mathbb{R}$ and $r\in {\mathbb{R}}^{>0}$

Which yields a linear program, to which the solution produces a disk of maximum radius completely inside the polygon, as needed.

For any job $i$ we note that it's finishing time is $s_i+d_i$, the total duration for all jobs to be completed is simply $T:=max\left(\{s_i+d_i:i\in [1,\dots ,n]\}\right)$, but this is not a linear combination of our variables so instead of defining it, we simply declare it as a variable $T$ and assert that $T>0$ and add $n$ constraints of the form $T>s_i+d_i$

We also need to enforce certain constraints, which is to say that for any $p_{i,j}$ which is true we add the following inequality: $${\displaystyle s_i+d_i\le s_j}$$ which says that the finishing time of job $i$ comes before the start time of job $j$.

We also have $s_i>0$ for all $i\in [1,\dots ,n]$, and now along with these contraints we minimize $T$ which defines our linear programming problem.

For logical and we require both to be true, which means that $x=1$ and $y=1$ and in that case we require that $z=1$ in any other case we need that $z=0$. It can be seen that these constraints are equivalent to $z=min(x,y)$ under this view it's simpler to derive constraints. Firstly the minimum must be smaller than the two input values: $${\displaystyle z\le x\text{ and }z\le y}$$ note that this is not enough still because if $x,y=1$ then we can still pick $z=0$ and things are satisfied, so we need to enforce a lower bound on $z$, to construct this lower bound, we'll consider a few cases.

• $x,y=1$, we require that $z\ge 1$
• if $x=1,y=0$, $x=0,y=1$ or $x=0,y=0$, our initial constraints automatically force $z=0$ so no extra constraints are required.

From the above, we can throw in the constraint that $z\ge x+y-1$ which enforces $z\ge 1$ when $x,y=1$ and in the other cases it either enforces $z\ge 0$ or $z\ge -1$ which add no information since we know that $z\in \{0,1\}$

For logical or, we require that at least one of $x,y$ is equal to 1. Which means their sum is at least one, so we encode that with we see that this is equivalent to $z=max(x,y)$ but that $max$ is not a linear constraint, therefore we have to take a similar approach as above, similarly we require that $${\displaystyle z\ge x\text{ and }z\ge y}$$ symetrically when $x,y=0$ then $z=0$ is a possibility so we need to put an upper bound on $z$ and we'll just note that $z\le x+y$ works

Finally for $z=\neg x$ we need to take $1\mapsto 0$ and $0\mapsto 1$ which can be done with $${\displaystyle z=x-1}$$ note that equality can be represented by two opposite inequalities.

Let $m_1,m_2,m_3$ denote how many cubic meters of each material there are where $m_i\ge 0$, we'd like to maximize our profit which is given by the equation $${\displaystyle 1000m_1+1200m_2+12000m_3}$$

Our cargo plane can carry a maximum weight of 100 tons, since each material has a different density this means that $${\displaystyle 2m_1+m_2+3m_3\le 100}$$

It can store a maximum volume of 60 cubic meters, meaning that $${\displaystyle m_1+m_2+m_3\le 60}$$

We also know that there are only limited amounts of each material, we have that: $${\displaystyle m_1\le 40\text{ and }{m}_2\le 30\text{ and }{m}_3\le 20}$$

If someone claims they have an algorithm to solve a linear program and give you a maximum value, you can only check if it meets the constraints, but you can't be sure it's the best value. The dual of a linear program aims to minimize with respect to an upper bound of the original question. If a solution to both the primal and dual linear programs yields the same objective values, it's maximal. This dual verification serves as a certificate to confirm if a given value is the maximum.

It may turn out that the dual problem may be easier or quicker to solve as compared to the primal problem, this is one reason why one may prefer the dual over the primal.

To obtain the dual we take our original primal and introduce variables $y_1,y_2,y_3,y_4,y_5$, for each inequality in the primal, then we multiply the $i$-th inequality by $y_i$, then we sum all the inequalities to obtain a master sum: $${\displaystyle m_1(y_1+2y_2+y_3)+m_2(y_1+y_2+y_4)+m_3(y_1+3y_2+y_5)\le 60y_1+100y_2+40y_3+30y_4+20y_5}$$ We can see that this inequality is implied by the primal, and what we'd like to do is to choose values for $y_i$ which make the upper bound as small as possible, also we'd like to make sure that $${\displaystyle 1000m_1+1200m_2+12000m_3\le m_1(y_1+2y_2+y_3)+m_2(y_1+y_2+y_4)+m_3(y_1+3y_2+y_5)}$$ by doing this it makes sure that the upper bound will be an upper bound of what we were maximizing so that the primal doesn't find some smaller solution. With all that said the primal is thus given by minimizing $${\displaystyle 60y_1+100y_2+40y_3+30y_4+20y_5}$$ such that $$\begin{gathered} {\displaystyle y_1+2y_2+y_3\ge 1000 \\ {y}_1+y_2+y_4\ge 1200 \\ {y}_1+3y_2+y_5\ge 12000} \end{gathered}$$