Linear Programming using the simplex method

In summary: Now you can write the constraint as,\(2x_1-x_2+s_1=0\)Where \(s_1\) is a slack variable, which takes care of the inequality.Kind Regards,Sudharaka.In summary, the Chemistry department at a local college needs to stock at least 900 small test tubes and 600 large test tubes. To take advantage of a special price, the department wants to buy at least 2700 test tubes. Since the small test tubes are broken twice as often as the large ones, the department will order at least twice as many small test tubes as large. To minimize cost, the department should order 900 small test tubes and 600 large test tubes. If the
  • #1
arl2267
15
0
The Chemistry department at a local college decides to stock at least 900 small test tubes and 600 large test tubes. It wants to buy at least 2700 test tubes to take advantage of a special price. Since the small test tubes are broken twice as often as the large, the department will order at least twice as many small test tubes as large.a) If the small test tubes cost 18 cents each and the large ones cost 15 cents each, how many of each size should be ordered to minimize cost?b) Suppose the minimum number of test tubes is increased to 3000. Use shadow costs to calculate the total cost in this case.

I understand how to set up the tableau, I just have a hard time forming the minimization problem and the constraints. Here is my attempt so far:

Minimum: w= 18x1+ 15x2
Subject to: 2x1+ x2 is greater than or equal to 900
x greater than or equal to 600

I'm pretty sure that's wrong, but if someone can help me with the equations, I can do the rest. Thanks.
 
Mathematics news on Phys.org
  • #2
arl2267 said:
The Chemistry department at a local college decides to stock at least 900 small test tubes and 600 large test tubes. It wants to buy at least 2700 test tubes to take advantage of a special price. Since the small test tubes are broken twice as often as the large, the department will order at least twice as many small test tubes as large.a) If the small test tubes cost 18 cents each and the large ones cost 15 cents each, how many of each size should be ordered to minimize cost?b) Suppose the minimum number of test tubes is increased to 3000. Use shadow costs to calculate the total cost in this case.

I understand how to set up the tableau, I just have a hard time forming the minimization problem and the constraints. Here is my attempt so far:

Minimum: w= 18x1+ 15x2
Subject to: 2x1+ x2 is greater than or equal to 900
x greater than or equal to 600

I'm pretty sure that's wrong, but if someone can help me with the equations, I can do the rest. Thanks.

Minimise: w= 18x1+ 15x2

Subject to:
x1 >= 900
x2 >= 600
x1+x2>=2700
2x1>=x2

CB
 
  • #3
CaptainBlack said:
Minimise: w= 18x1+ 15x2

Subject to:
x1 >= 900
x2 >= 600
x1+x2>=2700
2x1>=x2

CB

Hi arl2267, :)

I think CaptainBlack's answer can be improved improved a little. :) Adding the third and fourth constraints will give the first constraint. Hence the first constraint can be dropped to get,

\(\mbox{Minimize : }w= 18x_{1}+ 15x_{2}\)

\(\mbox{Subject to:}\)

\(x_2\geq 600\)
\(x_1+x_2\geq 2700\)
\(2x_1\geq x_2\)
\(x_1,\,x_2\geq 0\)

Kind Regards,
Sudharaka.
 
  • #4
Sudharaka said:
Hi arl2267, :)

I think CaptainBlack's answer can be improved improved a little. :) Adding the third and fourth constraints will give the first constraint. Hence the first constraint can be dropped to get,

\(\mbox{Minimize : }w= 18x_{1}+ 15x_{2}\)

\(\mbox{Subject to:}\)

\(x_2\geq 600\)
\(x_1+x_2\geq 2700\)
\(2x_1\geq x_2\)
\(x_1,\,x_2\geq 0\)

Kind Regards,
Sudharaka.

The non-negativity constraints are redundant as we already have lower bounds on x1 and x2.

Also, it is better to retain the redundant constraint on the minimum for x1 so that the model does not need to be redone when numbers are changed

CB
 
Last edited:
  • #5
Thank you both for your help! I really appreciate it.
 
  • #6
Wait, how am I supposed to enter 2x1>=x2 into a tableau? I haven't seen that before on any other of my problems.
 
  • #7
arl2267 said:
Wait, how am I supposed to enter 2x1>=x2 into a tableau? I haven't seen that before on any other of my problems.

Well, you can rearrange that to, \(2x_1-x_2\geq 0\).
 

FAQ: Linear Programming using the simplex method

1. What is linear programming?

Linear programming is a mathematical method used to optimize a linear objective function subject to linear constraints. It involves finding the maximum or minimum value of the objective function while satisfying all the constraints.

2. What is the simplex method?

The simplex method is a popular algorithm used to solve linear programming problems. It involves iteratively moving from one feasible solution to another, each time improving the objective function value, until an optimal solution is found.

3. How does the simplex method work?

The simplex method works by first converting a linear programming problem into a standard form, with all variables on one side of the equation and all constraints on the other side. It then uses a series of pivot operations to move from one basic feasible solution to another, until an optimal solution is found.

4. What are the steps involved in the simplex method?

The steps involved in the simplex method are:

  1. Convert the problem into standard form
  2. Select a basic feasible solution
  3. Calculate the objective function value at the basic feasible solution
  4. Determine the entering variable (the variable with the most negative coefficient in the objective function)
  5. Determine the leaving variable (the variable that will enter the basis when the entering variable leaves)
  6. Perform a pivot operation to move to the next basic feasible solution
  7. Repeat until an optimal solution is found

5. What are the limitations of the simplex method?

The simplex method is limited to solving linear programming problems with continuous variables. It also requires that the objective function and constraints be expressed in a standard form, which can be time-consuming and tedious for large problems. Additionally, the simplex method may take a long time to converge or may not converge at all for certain types of problems, such as degenerate problems.

Back
Top