I'm somewhat stuck on an example in Linear Programming.
I managed to wrap my head around maximisation for a problem with $\le$ constraints, using both graphical and simplex solutions. However, I have encountered issues with minimisation and $\ge$ constraints.
For minimising, the notes say
"Minimising $2x + 4y$ is the same as maximising $-2x – 4y$. Therefore minimising a function is the same as maximising the negative of the function. So the only change in Simplex is that the coefficients of the objective are entered as positive values, rather than negative values".
To find the pivot column, do I still look for the most negative value? What if the function has no negative values in the objective row?
Secondly, for $\ge$ constraints, I know to add artificial variables, but I'm not 100% sure how to proceed after forming the tableau.
The exact problem I'm having difficulty with is:
MINIMISE $\ 2x + 5y, \text{ s.t.}\\
3x + 4y \ge 12,\\
5x + 2y \ge 8, \\
x, y \ge0$
I know I begin by adding (or subtracting in this case) slack and artificial variables, i.e.
$$3x + 4y – s_{_1} + a_{_1}= 12 \\
5x + 2y – s_{_2} + a_{_2} = 8$$
Then forming a tableau
$$\begin{array}{ccccccc}
& x & y & s_{_1} & s_{_2} & a_{_1} & a_{_2}\\
12 & 3 & 4 & -1 & 0 & 1 & 0\\
8 & 5 & 2 & 0 & -1 & 0 & 1\\
0 & 2 & 5 & 0 & 0 & 0 & 0 \end{array}$$
From here I'm unsure of how to choose the pivot column/pivot itself. Any help would be greatly appreciated.
EDIT: Solved it, will provide details on request, different method to one provided in answers.
Best Answer
If you have figured the simplex method for maximization problem, you can convert the minimization problem into a dual maximization problem using augmented matrix and get one such as below:
MAXIMIZE $\ 12a + 8b, \text{ s.t.}\\ 3a + 5b \le 2,\\ 4a + 2b \le 5,\\ a,b \ge 0$
The solution is same as
MINIMISE $\ 2x + 5y, \text{ s.t.}\\ 3x + 4y \ge 12,\\ 5x + 2y \ge 8, \\ x, y \ge0$
I tested in EXCEL and the solution for both the problems is $x=4$ and $y=0$
Take the first formulation and use simplex method to find the value of $s_1$ and $s_2$ in the final row of the tableu and those will be your x and y and I hope you can take it from there as I believe that you have mastered the maximization problem.
You can refer to the notes below
college.cengage.com/mathematics/larson/elementary_linear/4e/shared/downloads/c09s4.pdf