2
$\begingroup$

I'm asked to solve the following optimization problem. So far I've only learned the simplex algorithm and I'm not sure what I'm doing wrong but the Z value only gets worse and never gets better.

The question is:

  1. A pound of feed A costs 0.4 dollars and a pound of feed B costs 0.8 dollars.
  2. Bag A provides 800 calories and bag B provides 1000 calories
  3. Bag A has 140 units of vitamins while bag B has 70
  4. I must have at least 8000 calories a day
  5. I must have at least 700 vitamins
  6. No more then 1/3 of my diet can come from bag A
  7. Minimize cost

These are what I think the equations should be:

$$ \begin{array}{ll} \min & Z = 0.4A + 0.8B\\ &800A+1000B \ge 8000\\ &140A+70B \ge 700\\ &2A-B\le0 \end{array} $$

First I got problem into standard equality form

I changed minimize to maximize by multiplying -1:

Maximize: Z = -0.4A - 0.8B $\Rightarrow$ Z+0.4A+0.8B = 0

I added a slack variable to the constraints to make them = $$ \begin{array}{ll} &800A+1000B - S_1 = 8000\\ &140A+70B - S_2 = 700\\ &2A-B + S_3 = 0 \end{array} $$

At this point I set up the following tableau

--- Z A B S1 S2 S3 RHS Ratio
Z 1 0.4 0.8 0 0 0 0 -------
S1 0 800 1000 -1 0 0 8000 -------
S2 0 140 70 0 -1 0 700 -------
S3 0 2 -1 0 0 1 0 -------

For my entering variable I choose A because Z is larger the smaller (0.4A+0.8B) are so maxing out A is better for that. So I calculate my ratio to determine the leaving variable

--- Z A B S1 S2 S3 RHS Ratio
Z 1 0.4 0.8 0 0 0 0 -------
S1 0 800 1000 -1 0 0 8000 10
S2 0 140 70 0 -1 0 700 5
S3 0 2 -1 0 0 1 0 -------

So I determine that S2 should be the leaving variable because it has the smallest ratio. perform row operations on that row

--- Z A B S1 S2 S3 RHS Ratio
Z 1 0.4 0.8 0 0 0 0 -------
S1 0 800 1000 -1 0 0 8000 ---
S2 0 1 0.5 0 -1/140 0 5 ---
S3 0 2 -1 0 0 1 0 -------

This is where my understanding fails to perform row operations and eliminate other values in column A I would need to subtract row S2 from them. This leads to a negative Z value since. Since I'm maximizing shouldn't RHS of the Z row only go Up? I'm not sure where I've gone wrong here any help would be appreciated.

$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

It seems like you forgot the negativity constraints $A,B,S_1,S_2,S_3\ge0$. You'll need to use artificial variables and the Big-M method to solve this problem. Additionally, because the values of your objective function are negative after the min to max transformation, the values will appear negative for $Z$. Recall this important fact: the following objective functions are equivalent $\min f(x) = -\max -f(x)$. So multiply your final result by $-1$ at the end of the Simplex method to get your desired positive outcome.

Your initial table, before the addition of artificial variables, will look like the following:

--- Z A B S1 S2 S3 RHS Ratio
Z 1 0.4 0.8 0 0 0 0 -------
? 0 800 1000 -1 0 0 8000 -------
? 0 140 70 0 -1 0 700 ------
S3 0 2 -1 0 0 1 0 -------

With the addition of artificial variables, it will look like the following:

--- Z A B S1 S2 S3 a1 a2 RHS Ratio
Z 1 0.4 0.8 0 0 0 -M -M 0 -------
? 0 800 1000 -1 0 0 1 0 8000 -------
? 0 140 70 0 -1 0 0 1 700 ------
S3 0 2 -1 0 0 1 0 0 0 -------

Once do row operations for $a_1$ and $a_2$, it will look like the following:

--- Z A B S1 S2 S3 a1 a2 RHS Ratio
Z 1 0.4-940M 0.8 -1070M -M -M 0 0 0 -8700M -------
a1 0 800 1000 -1 0 0 1 0 8000 -------
a2 0 140 70 0 -1 0 0 1 700 ------
S3 0 2 -1 0 0 1 0 0 0 -------

Where $M$ is an arbitrarily large number. I'll leave the working out the rest of the problem for you to do.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.