Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Linear programming: simplex question (might belong in precal)

  1. Sep 18, 2008 #1
    1. The problem statement, all variables and given/known data

    Original question: The Cut-Right Company sells sets of kitchen knives. The Basic Set consists of 2 utility knives and 1 chef’s knife. The Regular Set consists of 2 utility knives, 1 chef’s knife, and 1 slicer. The Deluxe Set consists of 3 utility knives, 1 chef’s knife, and 1 slicer. Their profit is $30 on a Basic Set, $40 on a Regular Set, and $60 on a Deluxe Set. The factory has on hand 800 utility knives, 400 chef’s knives, and 200 slicers. Assuming that all sets will be sold, how may of each type should be produced in order to maximize profit? What is the maximum profit?

    2. Relevant equations

    s1, s2, s3 are slack variables
    x1, x2, x3 are all non-negative

    x1 = # of basic sets produced
    x2 = # of regular sets produced
    x3 = # of deluxe sets produced

    2*x1 + 2*x2 + 3*x3 + s1 = 800
    x1 + x2 + x3 + s2 = 400
    x2 + x3 + s3 = 200

    a is the profit function given by:
    a = 30*x1 + 40*x2 + 60*x3

    3. The attempt at a solution


    I circled the pivot element in row3,col3. It's a "1".

    I know I chose the pivot correctly(chose the most negative number in the bottom row, then found the column entry that is least when divided into the right-most column). Then I perform row operations to get all the rest of the numbers in the pivot column to be 0. Then I perform a row operation to turn the entry in the last row of the pivot column to 0. This makes the entire last row positive so the simplex algorithm is supposedly done--but it's not. The correct answer requires 200 deluxe sets and 100 basic sets be produced.

    I notice that I still have slack variables as basic variables. My guess is that I either performed the row operations incorrectly or there is some other step that I am overlooking. Ideas?
  2. jcsd
  3. Nov 25, 2008 #2

    Hopefully, I am not late to help.

    After performing the row (pivot) operations, remember to update the "a", your cost coefficient of the entering variable x3 into the 3rd row, i.e. now "a" for the 3rd row is updated from 0 to 60!
    I think this is what causes the error in your Simplex calculations.
    Redo your workings again, and I am sure you can get the correct optimal solution!

    If you still can't find it, you can pm me here.
    Last edited: Nov 25, 2008
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook