Minimize c = x + y subject to
x + 5y ≥ 6
5x + y ≥ 6
x ≥ 0, y ≥ 0.
graph the two lines
x + 5y ≥ 6 (intercepts at (0,6/5)(6,0))
5x + y ≥ 6 (intercepts at ((6/5,0)(0,6)
x ≥ 0, y ≥ 0.
find intersection
5 x + 25 y = 30
5 x + y = 6
------------------
24 y = 24
y = 1
x = 6-5 = 1
so at (1,1)
evaluate c = x+y at three points
(0,6) (1,1) (6,0)
minimum is obviously 2 at (1,1)
There is a name for that - "linear programming"
It is similar to the previous problems. You could plot them on a graph, find the intersection(s) and evaluate the objective function Z=x+y.
The lines to plot are:
for x+5y≥6, put the inequality in the standard form: y≥(6-x)/5.
Similarly, for 5x+y≥6, plot it as y≥(6-5x).
There are lines x≥0 and y≥0, which come into play whne x≥6 or y≥6.
Plot the graph and find all possible intersections (there are three). The feasibility region is an open region in the first quadrant (towards the top-right).
Now evaluate the objective function Z=x+y at all three intersections and find the point that gives the smallest value of Z.
See:
http://img9.imageshack.us/img9/7284/1296278783.png
To solve this linear programming problem and minimize the objective function c = x + y, subject to the given constraints, we can use the Simplex method.
Step 1: Write the problem in standard form:
We are given the following constraints:
x + 5y ≥ 6 ........... (1)
5x + y ≥ 6 ........... (2)
x ≥ 0, y ≥ 0
To convert these constraints to standard form, we introduce slack variables, s1 and s2, for each of the inequalities.
So, the modified constraints become:
x + 5y + s1 = 6 ........... (1')
5x + y + s2 = 6 ........... (2')
x ≥ 0, y ≥ 0
Step 2: Create the initial Simplex tableau:
Using the modified constraints, we can create the initial Simplex tableau as follows:
| x | y | s1 | s2 | RHS |
-----------------------------------
Row1 | 1 | 5 | 1 | 0 | 6 |
Row2 | 5 | 1 | 0 | 1 | 6 |
-----------------------------------
Step 3: Perform the iterations using the Simplex method:
1. Choose the most negative coefficient in the objective function row (i.e., the one with the most negative value in the last column).
In this case, we choose to pivot on the cell with -1 in the objective function row and the first column (corresponding to y).
2. Perform row operations to make the pivot element equal to 1 and all other elements in the pivot column equal to 0.
- Divide the first row by 5 to make the pivot element 1.
- Perform the corresponding row operations to make the other elements in the pivot column equal to 0.
After this step, the tableau becomes:
| x | y | s1 | s2 | RHS |
-----------------------------------------
Row1 | 1/5 | 1 | 1/5 | 0 | 6/5 |
Row2 | 25/5| -4 | -1/5 | 1 | 24/5|
-----------------------------------------
3. Now, update the tableau by performing the column operations to make the elements in the pivot row equal to 0.
- Multiply the first row by 25 and add it to the second row to make the pivot element in the second row zero.
- Perform the corresponding column operations to make the other elements in the pivot row equal to 0.
After this step, the tableau becomes:
| x | y | s1 | s2 | RHS |
------------------------------------------------
Row1 | 0 | 9 | 6/5 | -5/5 | 150/5 |
Row2 | 25/5 | 0 | -5/5 | 6/5 | 24/5 |
------------------------------------------------
4. Repeat steps 1-3 until there are no negative coefficients in the objective function row.
In this case, all coefficients in the objective function row are non-negative, so the tableau is in its final form.
Step 4: Interpret the final tableau:
The final tableau represents the solution to the linear programming problem.
The optimal values for x and y are obtained from the last column (RHS).
In this case, x = 30 and y = 8/5 (or 1.6).
Therefore, the minimum value of c (x + y) subject to the given constraints is x + y = 30 + 1.6 = 31.6.