0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.