Turn on thread page Beta
    • Thread Starter
    Offline

    14
    ReputationRep:
    What does it mean? Can anyone explain? We were "taught" this in about an hour... I know what to do but I don't have a clue what is actually being done. Also, are there any methods of doing it faster, or avoiding mistakes? I find it so incredibly easy to make errors and incredibly hard to spot them.

    THanks for any help.
    Offline

    8
    ReputationRep:
    Don't use the tableau until you understand what it means.

    maximise f = x + y, subject to
    x + 2y <= 3
    3x + y <= 5
    x, y >= 0

    Introduce slack variables:

    maximise f = x + y, subject to
    x + 2y + a = 3
    3x + y + b = 5
    x, y, a, b >= 0

    First trial solution: (x, y, a, b) = (0, 0, 3, 5). Can we do any better? Yes: we can increase x while keeping y constant (and letting a and b decrease). This helps because f = x + y. We can increase x to 5/3 in this way.

    Second trial solution: (x, y, a, b) = (5/3, 0, 4/3, 0). Can we do any better? To investigate, we write f in terms of the variables that are currently zero, ie, in terms of y and b:

    f = x + y = (5 - y - b)/3 + y = 5/3 - y/3 - b/3.

    This proves that f can never be more than 5/3, because y, b >= 0. So the current trial solution is optimal.

    [If f had turned out to be something like 5/3 + y/3 - b/3 we would have needed another step.]
    • Thread Starter
    Offline

    14
    ReputationRep:
    (Original post by Jonny W)
    This proves that f can never be more than 5/3, because y, b >= 0. So
    Sorry, I didn't understand this part...
    Offline

    8
    ReputationRep:
    We say that (x, y, a, b) is feasible if

    x + 2y + a = 3 . . . (1),
    3x + y + b = 5 . . . (2),
    x, y, a, b >= 0 . . . (3).

    If (x, y, a, b) is feasible then

    f
    = x + y . . . by definition of f
    = (5 - y - b)/3 + y . . . by (2)
    = 5/3 - y/3 - b/3
    <= 5/3 . . . by (3).
    • Thread Starter
    Offline

    14
    ReputationRep:
    Thanks for your help

    (Original post by Jonny W)
    We say that (x, y, a, b) is feasible if

    x + 2y + a = 3 . . . (1),
    3x + y + b = 5 . . . (2),
    x, y, a, b >= 0 . . . (3).

    If (x, y, a, b) is feasible then

    f
    = x + y . . . by definition of f
    = (5 - y - b)/3 + y . . . by (2)
    = 5/3 - y/3 - b/3
    <= 5/3 . . . by (3).
    Oh ok, I get it now.. so what's going on in the table? What are the negative values, and are there any methods to make me work faster/with fewer misrtakes? I always make a mistake somewhere down the line with these...
    Offline

    0
    ReputationRep:
    In a nutshell the S.A. solves a system of simultaneous equations.

    The critical points for a feasible region lie at the vertices, ie where the boundary lines intersect.

    So first off you turn your inequalities into equations.

    Now you may end up with say 3 equations and 6 unknowns; no unique solution exists of course.

    So 3 variables will have to be Zero( You start with the given variables as zero´s) these are called your Non basic variables.

    The other 3 variables (the ones you made up to get the equations) are now called the basic variables and the will be equal to the LHS of the corresponding equations. The profit will of course be zero at the moment.

    The SA simply solves the S.E.s and changes which varibles will be zero in a fairly efficient fashion.

    Oops must dash
    Offline

    8
    ReputationRep:
    Learn how to read the current trial solution from the table. This trial solution should have n + m components (n = number of normal variables, m = number of slack variables). At least n (usually exactly n) of the components will be zero. You can check that this trial solution is feasible for the problem, and that the current objective value is -(the bottom right-most entry in the table).
    • Thread Starter
    Offline

    14
    ReputationRep:
    So it solves the n simultaneous equations to give n planes on a 3d graph... as there are 3 non basic variables... then solves those planes to find extreme vertices and checks which one gives the largest P value?
    Offline

    8
    ReputationRep:
    (Original post by mik1a)
    So it solves the n simultaneous equations to give n planes on a 3d graph... as there are 3 non basic variables... then solves those planes to find extreme vertices and checks which one gives the largest P value?
    There are m equations in (n + m) variables. To get a unique solution you set n of the variables equal to 0. Such a solution is called a basic feasible solution. The optimum occurs at one of these ((n + m) choose n) BFSs.

    You could calculate all the BFSs and pick the best. But that's inefficient.

    The simplex algorithm moves between the BFSs. At each step the algorithm either tells you how to move to a better BFS or proves that the current BFS is optimal.
    • Thread Starter
    Offline

    14
    ReputationRep:
    So the basic feasable solution is just where the non-basic variables are equal to 0?
    Offline

    2
    ReputationRep:
    wot level is this?
    Offline

    8
    ReputationRep:
    (Original post by mik1a)
    So the basic feasable solution is just where the non-basic variables are equal to 0?
    Yes, the variables you set equal to 0 are called the non-basic variables.
 
 
 
Turn on thread page Beta
Updated: June 15, 2004

University open days

  • University of East Anglia
    All Departments Open 13:00-17:00. Find out more about our diverse range of subject areas and career progression in the Arts & Humanities, Social Sciences, Medicine & Health Sciences, and the Sciences. Postgraduate
    Wed, 30 Jan '19
  • Solent University
    Careers in maritime Undergraduate
    Sat, 2 Feb '19
  • Sheffield Hallam University
    City and Collegiate Campus Undergraduate
    Sun, 3 Feb '19
Poll
The new Gillette ad. Is it:
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Equations

Best calculators for A level Maths

Tips on which model to get

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.