# Gomori algorithm: Stuck at second constrain because it gives me the same solution as when I applied the first costrain.

Here is the function to be maximised: $$f = x_1 + 2x_2$$.

Constrains: $$-5x_1+2x_2\le 10 \\ 3x_1+2x_2\le12 \\ x_1-4x_2\le 3$$ I need to find a solution to this problem with $$x_1,x_2 \in Z$$ using Gomori algorithm. First I applied simplex algorithm to find the solution to the problem, where $$x_1,x_2$$ are not necessarily integers: Last symplex table and solution

From there, I choose to change the row of symplex table with basal variable $$x_2$$: $$x_6 = \frac{-5}{8}+\frac{3}{16}x_3+\frac{5}{16}x_4$$. Because $$x_6 \ge 0 \Rightarrow 3x_3 +5x_4 \ge 10$$. I express $$x_3, x_4$$ from LPP canonical: $$x_3 = 5x_1-2x_2+10 \\ x_4 = -3x_1-2x_2+12$$

Then $$10 \le 3(5x_1-2x_2+10) +5(-3x_1-2x_2+12) \Rightarrow x_2\le 5$$

New problem with the additional constrain rewritten in canonical form $$LPP_1$$: $$f=x_1+2x_2 \rightarrow \max \\ -5x_1+2x_2= 10 \\ 3x_1+2x_2=12 \\ x_1-4x_2= 3 \\ x_2+x_6 = 5$$ The last Symplex table and solution:

So, now I have $$x* = (\frac{2}{3},5)^T$$. The first component is non integer, so I will make changes co a Symplex table row with basal variable $$x_1$$:

$$x_7 = -\frac{2}{3}+\frac{1}{3}x_4 -\frac{2}{3}x_6 \Rightarrow \frac{1}{3}x_4 -\frac{2}{3}x_6 \ge \frac{2}{3}$$. Then from the $$LPP_1$$ I will express $$x_4, x_6:$$

$$x_4 = -3x_1-2x_2+12 \\ x_6 = -x_2+5$$

From there: $$2 \le (-3x_1-2x_2+12) -2(-x_2+5) \Rightarrow x_1 \le 0 \Rightarrow x_1 = 0$$ How I go from there and isn't there any mistakes in my computations?

Maximum/minimum of the linear function for example $$z=x_1+2x_2$$, will occur at the vertices of the closed region indicated by these three lines. This is due to the theorem of linear programming. The max value is $$23/2$$ and it occurs at $$x=1/4,y=45/8.$$