Simplex Method Introduction

00:51:59
https://www.youtube.com/watch?v=NX8TM6jCHGk

ๆ‘˜่ฆ

TLDRIn this video, the Simplex method for solving linear programs is explored. The method is designed to efficiently find optimal solutions by moving from one basic feasible solution to another along the boundary of the feasible region, instead of evaluating all possible solutions. The video emphasizes the method's iterative nature, focusing on selecting variables to enter and exit the basis to improve or maintain the objective value. Introducing slack variables transforms inequalities into equalities, facilitating the choice of initial solutions. The video also walks through pivoting operations used to navigate the solution space, ensuring that the standard basis vectors appear beneath the basis variables. As the method proceeds, special emphasis is laid upon using tableaux to represent equations and constraints. Details are given about the conditions under which the algorithm reaches optimal solutions, including the structural similarity maintained in matrices, despite changes in variables' roles from basis to non-basis and vice versa. The session concludes with visualizing how the Simplex method navigates through possibilities to pinpoint the best outcome.

ๅฟƒๅพ—

  • ๐Ÿ“ˆ The Simplex method optimizes linear programs by moving between basic feasible solutions.
  • ๐Ÿ”„ It requires choosing an initial solution and then iteratively improving the objective value.
  • ๐Ÿ“Š Key operations involve transforming the tableau with pivoting steps.
  • ๐Ÿ”‘ Slack variables convert inequalities to equalities for matrix operations.
  • ๐Ÿ” The optimal solution is identified when no further improvement is possible.
  • ๐Ÿ“Œ Each step involves choosing which variables to enter or exit the basis.
  • ๐Ÿ“ The method relies on the tableau, an augmented matrix including the objective.
  • ๐Ÿงฎ Equations are manipulated until standard basis vectors align with the basis variables.
  • โš–๏ธ Moving sideways can sometimes be necessary for eventual improvement.
  • ๐ŸŒ The process is visualized as moving around the feasible region's boundary.

ๆ—ถ้—ด่ฝด

  • 00:00:00 - 00:05:00

    The video introduces the Simplex method for solving linear programs, contrasting it with the inefficient method of listing all basic feasible solutions. The Simplex approach involves moving from one basic feasible solution to another along the boundary of the feasible region, improving the objective value at each step. The video promises to address questions of starting point, direction of movement, and determining completion.

  • 00:05:00 - 00:10:00

    The video explains the introduction of a variable 'Z' to track the objective value in the augmented form of the problem, focusing on maximizing 'Z'. It outlines the setup of a matrix called the 'Tableau', which includes the objective function and constraints, preparing for the Simplex methodโ€™s iterative approach.

  • 00:10:00 - 00:15:00

    A starting basis is chosen for the Simplex method, typically including the objective variable 'Z' and slack variables. The non-basic variables are set to zero, forming the initial matrix with an identity section for slack variables. This initial setup corresponds to a basic feasible solution, often at the origin when variables are non-negative.

  • 00:15:00 - 00:20:00

    Discussion on recognizing an optimal solution using the initial setup, noting the objective value 'Z' and variables 'XS' and 'XT'. It specifies a basic feasible solution but also discusses its non-optimality and introduces the idea of adjusting the basis to improve the objective.

  • 00:20:00 - 00:25:00

    The process of choosing entering and exiting variables is elaborated. It requires calculating when a variable driven from zero is beneficial. The example illustrates pivoting in the Simplex method by selecting the variable 'XS' to enter and 'SD' to leave, using the tableau setup.

  • 00:25:00 - 00:30:00

    Continues with the pivoting process, where 'XS' enters the basis and 'SD' exits. Elementary row operations are performed to adjust the matrix so that the tableau reflects the new basis with minimal entries enabling passage to the next feasible solution.

  • 00:30:00 - 00:35:00

    The video follows through the first pivot, updating the tableau and interpreting results for a new solution. It identifies increases in the objective function and shifts in slack variables, demonstrating incremental improvement towards optimality.

  • 00:35:00 - 00:40:00

    Another iteration of the Simplex method is performed, where 'XT' enters the basis, necessitating another pivot to progress. This step aims to enhance the objective value further, ensuring the approach moves closer to the optimal solution by adjusting variables strategically.

  • 00:40:00 - 00:45:00

    Continues demonstrating the Simplex method with additional iterations, highlighting the strategic pivot adjustments. The method systematically updates the tableau to reflect approaching the optimal solution, efficiently managing constraints and objectives.

  • 00:45:00 - 00:51:59

    Concludes with the optimization result where no further improvements are possible by altering basic variables. Illustrates movements on a graph of the feasible region, showing how the Simplex method navigates through feasible solutions to reach the optimal point.

ๆ˜พ็คบๆ›ดๅคš

ๆ€็ปดๅฏผๅ›พ

Mind Map

ๅธธ่ง้—ฎ้ข˜

  • What is the Simplex method used for?

    The Simplex method is used to solve linear programming problems by optimizing the objective value through a series of iterative steps involving basic feasible solutions.

  • How does the Simplex method differ from listing all basic feasible solutions?

    Instead of listing all basic feasible solutions, the Simplex method starts at one solution and iteratively moves to others that improve the objective value, avoiding exhaustive enumeration.

  • What is a basic feasible solution?

    A basic feasible solution is a corner point of the feasible region in a linear program's solution space that satisfies all constraints.

  • How do you know where to start in the Simplex method?

    An initial basic feasible solution is chosen, often by selecting slack variables to represent the initial solution.

  • How does the Simplex method move from one solution to another?

    The method moves by choosing a non-basic variable to increase and a basic variable to decrease, aiming to improve the objective value at each step.

  • What are slack variables?

    Slack variables are added to linear programming constraints to turn inequalities into equalities, helping to find initial feasible solutions.

  • Why might the Simplex method move sideways without improving the solution?

    Sometimes, operations might not improve the objective value immediately but could lead to future improvements, necessitating sideways moves.

  • What indicates the optimal solution has been found in the Simplex method?

    The optimal solution is determined when no further improvements can be made to the objective value by changing the basic feasible solution.

  • What is a Tableau in the Simplex method?

    A Tableau is an augmented matrix representation of a linear program used in the Simplex method to perform row operations and track variables.

  • How is the objective function tracked in the Simplex method?

    The objective function is tracked by adding it to the tableau, often represented by a variable 'z', allowing for manipulation alongside constraints.

ๆŸฅ็œ‹ๆ›ดๅคš่ง†้ข‘ๆ‘˜่ฆ

ๅณๆ—ถ่ฎฟ้—ฎ็”ฑไบบๅทฅๆ™บ่ƒฝๆ”ฏๆŒ็š„ๅ…่ดน YouTube ่ง†้ข‘ๆ‘˜่ฆ๏ผ
ๅญ—ๅน•
en
่‡ชๅŠจๆปšๅŠจ:
  • 00:00:01
    okay welcome to another video today
  • 00:00:04
    we're getting into the heart of the
  • 00:00:06
    Simplex method so uh reviewing what we
  • 00:00:10
    covered in the previous videos we found
  • 00:00:13
    uh that if we have a linear program and
  • 00:00:15
    augmented form uh we can find all the
  • 00:00:18
    basic feasible Solutions um and that's
  • 00:00:21
    what we did in the last video but um
  • 00:00:25
    although there are only finitely many of
  • 00:00:27
    those uh basic feasible Solutions it
  • 00:00:30
    wouldn't be a good strategy to just try
  • 00:00:31
    to list them all it works for small
  • 00:00:34
    problems it's essentially what we did
  • 00:00:36
    when we did the graphical method um but
  • 00:00:38
    it's not how we want to work in practice
  • 00:00:41
    uh when we're solving a linear program
  • 00:00:44
    instead uh the whole idea behind uh the
  • 00:00:48
    Simplex method is instead of checking
  • 00:00:50
    all basic feasible Solutions um we start
  • 00:00:53
    at a basic feasible solution and then we
  • 00:00:58
    move to another basic feasible solution
  • 00:01:01
    sort of moving around the boundary of
  • 00:01:03
    the feasible region from kind of corner
  • 00:01:05
    to
  • 00:01:06
    corner and we always move in a direction
  • 00:01:09
    that improves our in objective value or
  • 00:01:12
    at least doesn't make it worse there's
  • 00:01:14
    sometimes where you sort of have to move
  • 00:01:15
    sideways and you see no improvement um
  • 00:01:17
    for that move but then you're able to
  • 00:01:19
    see some more Improvement in a later
  • 00:01:21
    move and we won't we won't worry about
  • 00:01:23
    that too much to begin with um but
  • 00:01:26
    there's this idea that we're going to
  • 00:01:28
    move from corner point to Corner point
  • 00:01:30
    or or basic feasible solution to basic
  • 00:01:32
    feasible solution in a way that moves us
  • 00:01:35
    around the boundary of our feasible
  • 00:01:37
    region until we find the best
  • 00:01:41
    solution okay so some questions that we
  • 00:01:44
    need to answer if we're going to do that
  • 00:01:45
    is uh how do we know where to start um
  • 00:01:49
    how do we know where to move next and
  • 00:01:51
    how do we know when we're done um we're
  • 00:01:53
    going to focus on two and three in this
  • 00:01:55
    video we're going to save uh one for
  • 00:01:57
    later we'll give a pretty simple answer
  • 00:01:59
    answer for number one uh for this video
  • 00:02:02
    um but we'll have to dive into that in
  • 00:02:04
    more deep deeply when our Simple
  • 00:02:07
    Solution doesn't work out so uh let's
  • 00:02:09
    look again at uh jepetto's problem in
  • 00:02:12
    augmented form um but let's also
  • 00:02:16
    introduce a a a variable z uh that
  • 00:02:21
    tracks our objective okay so uh we said
  • 00:02:24
    we want to maximize three times the
  • 00:02:26
    number of soldiers plus two times the
  • 00:02:28
    number of trains and we're going to say
  • 00:02:29
    that uh that value Z so Z is going to be
  • 00:02:32
    our objective value and our goal in this
  • 00:02:34
    case is to maximize uh
  • 00:02:37
    Z and we're going to do a little trick
  • 00:02:39
    in that we want all our variables on the
  • 00:02:41
    left side of the equation and so we'll
  • 00:02:43
    subtract 3xs and and 2xt over the other
  • 00:02:47
    side um so that we have this equation
  • 00:02:49
    here and we're going to treat this
  • 00:02:51
    equation just like we treat our
  • 00:02:54
    constraints um it's a little bit special
  • 00:02:56
    as a constraint because it's really our
  • 00:02:58
    objective uh we're going to put in the
  • 00:03:00
    top row of our system um but essentially
  • 00:03:03
    we're going to take that augmented
  • 00:03:04
    system now and add this to it so um if I
  • 00:03:08
    think of my variables now that I've
  • 00:03:11
    introduced uh Z is in my new variable
  • 00:03:14
    I'll always put it the left side just
  • 00:03:15
    kind of out of practice U my original
  • 00:03:18
    variables of Xs and XT and then I've got
  • 00:03:22
    three slack variables SF S C and S
  • 00:03:28
    D and then uh right hand
  • 00:03:32
    side okay so first I'll take uh this
  • 00:03:35
    objective and I'll actually put that in
  • 00:03:38
    the top row so I've got a coefficient of
  • 00:03:40
    one for
  • 00:03:42
    Z -3 for
  • 00:03:44
    XS -2 for XT none of my slack variables
  • 00:03:49
    show up and so they're all zeros and
  • 00:03:51
    then my right hand side uh because I
  • 00:03:53
    moved everything to the left side uh my
  • 00:03:56
    right hand side ends up being zero okay
  • 00:03:58
    and just to show that this uh top row is
  • 00:04:02
    actually the objective I sort of draw a
  • 00:04:04
    line to separate it out from the
  • 00:04:07
    rest I also like to uh draw a vertical
  • 00:04:10
    line to separate out my right hand side
  • 00:04:13
    and maybe also out of habit I like to
  • 00:04:15
    draw another line to separate out z z is
  • 00:04:19
    uh kind of a little bit of a different
  • 00:04:20
    variable um it's tracking our objective
  • 00:04:24
    now underneath that I put all my
  • 00:04:26
    constraints uh and so we had our
  • 00:04:29
    constraints from last time let me S pull
  • 00:04:32
    those up
  • 00:04:33
    here uh so and notice my Z doesn't show
  • 00:04:37
    up in any of my constraints and so
  • 00:04:39
    actually I'm going to get
  • 00:04:41
    zero uh in there for each of my um for
  • 00:04:46
    the coefficient of Z because it's not in
  • 00:04:48
    any of the constraints um but my first
  • 00:04:50
    constraint was 2x1 or 2xs 1xt uh one for
  • 00:04:55
    my first slack variable zero for my
  • 00:04:57
    other slack variables equals 100
  • 00:05:01
    one one 0 one 0 and 80 for my second
  • 00:05:06
    constraint and uh one 0 0 0 1 and 40 for
  • 00:05:13
    my third constraint and this uh this
  • 00:05:17
    constraint was the uh finishing
  • 00:05:19
    constraint the carpentry constraint and
  • 00:05:21
    the demand
  • 00:05:23
    constraint okay so I've got uh my
  • 00:05:27
    objective row I've got my three
  • 00:05:28
    constraint rows along with this new
  • 00:05:31
    variable z uh that's going to track um
  • 00:05:35
    essentially my objective so um and this
  • 00:05:38
    is actually we give this a name this is
  • 00:05:39
    this will uh be what we call the Tableau
  • 00:05:43
    um and we're using sort of the Tableau
  • 00:05:45
    method it's just a fancy way of of
  • 00:05:46
    talking about this a special augmented
  • 00:05:50
    uh Matrix here it really is um just a
  • 00:05:53
    matrix an augmented Matrix where we've
  • 00:05:55
    now added an extra row um for
  • 00:06:00
    for the objective okay so similar to
  • 00:06:03
    what we did in the last uh video now
  • 00:06:05
    we're going to choose a basis okay and
  • 00:06:08
    this is really the where do we start
  • 00:06:10
    question of where should we start
  • 00:06:12
    because we know that each choice of a
  • 00:06:14
    basis corresponds to a basic feasible
  • 00:06:18
    solution or a corner point so uh to
  • 00:06:21
    begin with and for all the examples or
  • 00:06:23
    the first several examples that we see
  • 00:06:25
    this week our choice for a basis um will
  • 00:06:29
    be pretty easy and that our initial
  • 00:06:36
    basis uh we'll choose we'll always
  • 00:06:40
    choose Z to be in our basis um some
  • 00:06:42
    books actually kind of implicitly choose
  • 00:06:44
    Z in in to be in the basis and don't
  • 00:06:47
    explicitly say that it's in the basis
  • 00:06:49
    but I I like thinking of Z is always in
  • 00:06:51
    our basis and then we're going to choose
  • 00:06:54
    each of the slack variables to be in our
  • 00:06:57
    basis to begin with so s f s c and SD so
  • 00:07:04
    these are going to be all of our basic
  • 00:07:05
    variables and all the other variables so
  • 00:07:08
    maybe I'll make a note note of it
  • 00:07:13
    nonbasic then uh would
  • 00:07:16
    be uh my two original variables Xs and
  • 00:07:21
    XT so uh the non-basic variables we're
  • 00:07:24
    going to set each of these to
  • 00:07:26
    zero and then uh we're g to essentially
  • 00:07:30
    read off the values of these ones here
  • 00:07:32
    now kind of the first step would be
  • 00:07:36
    forming the B Matrix here and sort of
  • 00:07:39
    solving to get that into the identity it
  • 00:07:42
    turns out we've already got an identity
  • 00:07:45
    Matrix or our standard basis vectors
  • 00:07:47
    underneath SF SC and SD okay so if we
  • 00:07:52
    set these two to be equal zero it's
  • 00:07:54
    essentially the same as Crossing off
  • 00:07:57
    these two columns and ignoring them
  • 00:07:59
    because
  • 00:07:59
    the value of those variables is zero and
  • 00:08:02
    then uh this first row well actually our
  • 00:08:04
    objective row if we cross if we set XS
  • 00:08:07
    to zero and XT to zero uh then we get
  • 00:08:11
    one we get Z equals that's zero that's
  • 00:08:14
    zero these are all zeros for their
  • 00:08:16
    coefficient and then our right hand side
  • 00:08:18
    says equals zero and so our initial
  • 00:08:27
    solution has Z equal Z that we can know
  • 00:08:32
    from this first line and actually I'll
  • 00:08:34
    kind of denote this row as the Z it's
  • 00:08:36
    our objective row and so I'll write that
  • 00:08:39
    there um this next row if I set uh Xs
  • 00:08:42
    and XT to be zero um and so essentially
  • 00:08:45
    hide those I can read off that
  • 00:08:47
    SF is uh is the only other thing that
  • 00:08:50
    has a has a coefficient in that row and
  • 00:08:53
    it has a coefficient one so 1 * SF equal
  • 00:08:56
    100 and so we'll actually call this the
  • 00:08:59
    f SF row and that one tells us that SF
  • 00:09:03
    equals
  • 00:09:05
    100 SC similarly we can read off from
  • 00:09:09
    this row these these get zeroed out and
  • 00:09:11
    we get SC equals 80 and SD equal 40 okay
  • 00:09:19
    and this is actually one of our um basic
  • 00:09:21
    feasible solutions from last time and
  • 00:09:24
    then we can tack on that XS equals 0 and
  • 00:09:27
    XT equal 0 cuz they are the non-basic
  • 00:09:31
    variables so that is our initial
  • 00:09:35
    solution first qu uh next question is is
  • 00:09:38
    it an optimal solution um we know
  • 00:09:40
    because we've solved this problem uh
  • 00:09:43
    graphically that it's not um this this
  • 00:09:47
    corresponds to the origin in the
  • 00:09:48
    original units or in the original
  • 00:09:50
    variables it's not optimal but how do we
  • 00:09:53
    know that well let's look at our
  • 00:09:55
    objective
  • 00:09:57
    so is it
  • 00:10:02
    optimal and then so uh we can say no but
  • 00:10:06
    why is that well Z if we if we read off
  • 00:10:10
    this first row Z minus
  • 00:10:13
    3xs minus
  • 00:10:16
    2xt = Z or actually moving these back
  • 00:10:19
    over to the other side Z = 3 XS +
  • 00:10:26
    2xt now Xs and XT are currently
  • 00:10:30
    non-basic variables meaning that they're
  • 00:10:32
    currently set to zero but the question
  • 00:10:35
    is if we brought one of those variables
  • 00:10:38
    into the basis and made them not zero
  • 00:10:42
    would we improve our objective and and
  • 00:10:44
    in this case both of them once we move
  • 00:10:46
    them over to the right side have
  • 00:10:48
    positive coefficients they're negative
  • 00:10:50
    coefficients when they're on the left
  • 00:10:51
    side but they're positive coefficients
  • 00:10:53
    once we move them over the right side
  • 00:10:54
    and so increasing either XS or XT from
  • 00:10:58
    zero would increase Z as well okay this
  • 00:11:01
    is the key idea of um Xs and XT are
  • 00:11:05
    currently zero but if we increase them
  • 00:11:07
    from zero brought them into the basis
  • 00:11:09
    made them non zero um would that improve
  • 00:11:13
    uh and the answer is yes um so I'll
  • 00:11:17
    maybe write that out we
  • 00:11:19
    can
  • 00:11:22
    increase
  • 00:11:24
    Z
  • 00:11:27
    by increasing
  • 00:11:30
    XS or
  • 00:11:34
    XT okay so that that's going to be the
  • 00:11:38
    next step we're going to change our
  • 00:11:39
    basis uh we're going to choose one uh
  • 00:11:42
    either XS or XT um of our variables to
  • 00:11:45
    come into our basis we'll choose another
  • 00:11:48
    variable then we'll have to leave the
  • 00:11:49
    basis um because if we remember uh when
  • 00:11:53
    choosing our basis we want essentially
  • 00:11:55
    uh the basis to match the number of um
  • 00:11:58
    constraints now we sort of add added an
  • 00:12:01
    extra row added Z in there so we're
  • 00:12:03
    going to we're going to always look for
  • 00:12:04
    having four variables in our basis and
  • 00:12:07
    so and you can actually think of each of
  • 00:12:09
    these uh four variables as corresponding
  • 00:12:13
    to one of the rows okay so there's one
  • 00:12:15
    variable to per row and you'll notice
  • 00:12:18
    that if I look at the columns for these
  • 00:12:20
    variables the standard basis vectors
  • 00:12:23
    show up in the columns for Z SF s c and
  • 00:12:26
    SD and that's going to be the
  • 00:12:28
    characteristic
  • 00:12:30
    um feature of our basis is that the
  • 00:12:33
    standard basis vectors are going to show
  • 00:12:35
    up underneath our basis variables okay
  • 00:12:38
    and so when we bring a new variable into
  • 00:12:41
    the basis we're going to do elementary
  • 00:12:43
    row operations in order to change
  • 00:12:46
    whatever the current column is into uh
  • 00:12:50
    the standard basis
  • 00:12:51
    Vector okay
  • 00:12:54
    so let's uh choose XS or XT to our our
  • 00:13:00
    basis um now either of them should
  • 00:13:03
    improve our objective there's a couple
  • 00:13:05
    of rules of thumb uh that your book
  • 00:13:08
    talks about um of how to choose they're
  • 00:13:11
    mostly just heris and as long as you
  • 00:13:13
    choose one that one variable that
  • 00:13:15
    improves it um and as long as you're
  • 00:13:18
    kind of careful not to get stuck in a
  • 00:13:20
    loop uh where you're sort of uh
  • 00:13:23
    switching back and forth between between
  • 00:13:24
    variables um it really doesn't matter
  • 00:13:27
    which variable you choose as as long as
  • 00:13:29
    you choose one that improves um your
  • 00:13:31
    objective so um I tend to follow the
  • 00:13:35
    simple
  • 00:13:36
    heuristic of choosing whichever has the
  • 00:13:39
    larger coefficient meaning that the
  • 00:13:41
    smallest change in either XS or XT
  • 00:13:44
    results into a larger change in Z no
  • 00:13:47
    guarantee that that's going to get you
  • 00:13:48
    there in the fewest number of steps
  • 00:13:50
    actually in this case uh we'll find that
  • 00:13:52
    it will take us more steps using this
  • 00:13:54
    heuristic which is fine more more
  • 00:13:56
    example more um more uh kind
  • 00:13:59
    uh yeah more video to show you so um
  • 00:14:02
    looking at this uh the three coefficient
  • 00:14:04
    is bigger than the two coefficient so
  • 00:14:06
    we're going to choose XS to enter our
  • 00:14:09
    basis okay uh you're going to want a
  • 00:14:12
    couple extra sheets of paper for this
  • 00:14:14
    and so here I'm going to jump onto a new
  • 00:14:17
    sheet of
  • 00:14:19
    paper so we're going to
  • 00:14:23
    choose
  • 00:14:25
    XS to enter the basis
  • 00:14:31
    okay which means that our new
  • 00:14:34
    basis
  • 00:14:35
    um is going to have XS in it but we've
  • 00:14:38
    got to get rid of something else and so
  • 00:14:41
    uh let's look at our
  • 00:14:44
    constraints uh that are up here and
  • 00:14:47
    think about okay if XS which is
  • 00:14:49
    currently zero starts increasing from
  • 00:14:51
    zero uh when does one of the other
  • 00:14:56
    variables uh the other variables SF f s
  • 00:14:59
    c and SD are going to have to uh kind of
  • 00:15:02
    compensate for that um in order to
  • 00:15:05
    maintain the inequalities here might
  • 00:15:07
    remember we don't have inequalities
  • 00:15:08
    anymore we got equalities so if uh XS
  • 00:15:12
    increases uh SFS C and SD are going to
  • 00:15:15
    have to compensate and the question is
  • 00:15:17
    um as they're compensating uh which one
  • 00:15:20
    of those gets driven to zero first okay
  • 00:15:24
    so let's actually write out uh what each
  • 00:15:27
    of these constraints are um maybe not in
  • 00:15:30
    augmented form but actually in as
  • 00:15:32
    formulas and let's look at those so our
  • 00:15:35
    first constraint uh up here is
  • 00:15:38
    essentially saying
  • 00:15:40
    2xs + 1
  • 00:15:44
    XT plus
  • 00:15:47
    SF uh equals
  • 00:15:51
    100 okay sorry let me bring that up and
  • 00:15:54
    I'll kind of just hide some of the work
  • 00:15:56
    we had below um my our next constru
  • 00:15:59
    straint is uh XS +
  • 00:16:04
    xt+ S
  • 00:16:08
    C equals 80 and then we've got uh
  • 00:16:13
    XS plus SD equal
  • 00:16:17
    40 okay let's uh look at this first
  • 00:16:20
    constraint the first thing we can do is
  • 00:16:23
    we know that we're going to increase XS
  • 00:16:25
    but XT is going to stay nonbasic
  • 00:16:29
    okay and so we're going to cross out
  • 00:16:31
    these
  • 00:16:33
    XTS and we're going to put zero there
  • 00:16:36
    and that's because
  • 00:16:39
    XT is
  • 00:16:41
    non Basic and it's going to stay
  • 00:16:44
    non-basic so we can essentially ignore
  • 00:16:47
    that okay now I want to essentially
  • 00:16:51
    figure out what value of XS would make
  • 00:16:55
    SF go to zero okay and so if I want to
  • 00:16:59
    find out when does SF go to zero well
  • 00:17:01
    let's just actually set SF to zero and
  • 00:17:04
    if SF goes to zero uh then um I'll
  • 00:17:09
    essentially hide that and then I'd be
  • 00:17:11
    left with 2xs equals 100 uh and so this
  • 00:17:15
    is essentially saying or uh if SF equals
  • 00:17:22
    z then XS equals if SS equals zero then
  • 00:17:28
    X has to be equal to
  • 00:17:32
    50
  • 00:17:33
    okay let's do the same thing here uh
  • 00:17:37
    let's figure out if SC equals zero so if
  • 00:17:41
    I plug in zero for SC then
  • 00:17:47
    XS equals 80 and then finally
  • 00:17:52
    if SD equals
  • 00:17:55
    z then um X s equal
  • 00:18:02
    40 okay so I've sort of figured out what
  • 00:18:06
    value of XS would correspond to each of
  • 00:18:09
    those slack variables going to
  • 00:18:12
    zero uh and the thing is I'm sort of
  • 00:18:15
    slowly raising XS from zero and I need
  • 00:18:19
    to stop as soon as one of these gets
  • 00:18:22
    driven all the way down to zero because
  • 00:18:23
    if I go any more that variable would
  • 00:18:26
    then go negative okay and remember if we
  • 00:18:28
    want to stay in our feasible region all
  • 00:18:31
    of our variables need to need to remain
  • 00:18:34
    non negative so we can't go negative we
  • 00:18:36
    can go to zero but we can't go past zero
  • 00:18:38
    okay and so looking at these the first
  • 00:18:41
    one that gets driven to
  • 00:18:43
    zero is this
  • 00:18:45
    one so this is
  • 00:18:50
    the first
  • 00:18:56
    variable that goes to zero
  • 00:19:03
    okay and so
  • 00:19:06
    SD is going to be what we'll call our
  • 00:19:08
    exiting variable okay XS is entering SD
  • 00:19:12
    is going to exit then it's the first one
  • 00:19:14
    that gets driven to
  • 00:19:16
    zero okay and
  • 00:19:19
    so we'll say
  • 00:19:22
    [Music]
  • 00:19:24
    SD uh is
  • 00:19:26
    our exiting
  • 00:19:33
    variable and that X SD leaves the basis
  • 00:19:38
    okay um so uh that will tell us that
  • 00:19:42
    then our new
  • 00:19:46
    basis will be Z is still going to be
  • 00:19:49
    there and let's see let's look at what
  • 00:19:52
    our our old
  • 00:19:54
    basis uh was that we're going to
  • 00:19:57
    essentially take s D Spot in that basis
  • 00:20:00
    and and put XS in that spot I'm going to
  • 00:20:03
    actually give pretend like this basis
  • 00:20:06
    has an ordering because it sort of does
  • 00:20:07
    it has the ordering of our columns and
  • 00:20:10
    so our basis is going to be
  • 00:20:13
    zsf S C and now
  • 00:20:18
    XS okay that's going to be our new basis
  • 00:20:21
    and now the trick is we need to do um
  • 00:20:24
    Elementary row operations so that we get
  • 00:20:27
    our standard basis vector below each of
  • 00:20:29
    these in our Tableau or our augmented
  • 00:20:33
    Matrix so I'm going to go ahead and set
  • 00:20:36
    this up again so uh Z
  • 00:20:39
    XS XT
  • 00:20:42
    SF S C
  • 00:20:45
    SD right hand
  • 00:20:50
    side objective
  • 00:20:52
    row draw some lines in there
  • 00:20:56
    okay so what we want uh for this to
  • 00:21:01
    happen
  • 00:21:02
    is uh let's see we want XS to enter our
  • 00:21:08
    basis okay and so what we want to get is
  • 00:21:11
    we want to get it so that and it's
  • 00:21:13
    entering in the place of X SD SD had the
  • 00:21:17
    fourth standard basis Vector so back
  • 00:21:21
    here maybe I'll flip it up like this
  • 00:21:24
    hold my page a little bit so that we can
  • 00:21:26
    see this of where we were and where we
  • 00:21:29
    are okay this is going to help yep so SD
  • 00:21:33
    had the
  • 00:21:35
    00001 standard basis Vector in it and so
  • 00:21:38
    that's the standard basis Vector that
  • 00:21:40
    we're going to eventually want in the XS
  • 00:21:43
    column okay and so uh Xs and let's
  • 00:21:48
    actually label the rows that will help
  • 00:21:50
    us maybe a little bit s c SF those ones
  • 00:21:54
    stay in there and Z is always the
  • 00:21:57
    objective row
  • 00:21:59
    okay so this is what we want here okay
  • 00:22:03
    looking at what we have if we look at uh
  • 00:22:07
    the bottom row it's got a one here we
  • 00:22:09
    want a one here and so actually our
  • 00:22:12
    bottom row in this case is good to go if
  • 00:22:14
    there wasn't a one here we'd want to
  • 00:22:17
    multiply or divide this row by whatever
  • 00:22:20
    made uh this turn into a one okay and
  • 00:22:23
    we'll see that an example of that in a
  • 00:22:24
    bit um but this is a one and so we don't
  • 00:22:29
    actually have to do anything to the
  • 00:22:30
    bottom row and so let's copy the bottom
  • 00:22:32
    row up to here and so this bottom row is
  • 00:22:34
    then zero
  • 00:22:37
    zero I'm trying to make this line up a
  • 00:22:40
    little bit z z one um 40 okay so I just
  • 00:22:46
    copied my bottom row
  • 00:22:48
    down okay now I look at uh this entry
  • 00:22:52
    here and it's a one I want it to be a
  • 00:22:55
    zero so if I want to zero this out then
  • 00:22:58
    I'm going to use a multiple of this row
  • 00:23:00
    add it up to zero that out okay uh this
  • 00:23:03
    value is one this value is one if I I
  • 00:23:06
    take uh this row minus this row that
  • 00:23:09
    should zero this out okay uh and so I'm
  • 00:23:12
    going to do uh this this row minus this
  • 00:23:15
    row and so uh 0 - 0 is 0o uh 1 - 0 is 1
  • 00:23:22
    0 - 0 is 0 1 - 0 is 1 0 - 1 is -1 and 80
  • 00:23:30
    - 40 is 40 so I did uh sort of this row
  • 00:23:36
    minus this row okay uh now looking up at
  • 00:23:40
    the top row or not well not the top row
  • 00:23:43
    the second row I've got a two here I
  • 00:23:46
    want to turn that two into a zero and so
  • 00:23:49
    I'm going to take -2 times the bottom
  • 00:23:51
    row add it up to the top row okay and so
  • 00:23:55
    -2 * 0 add it up and I'll still have
  • 00:23:59
    zero up here uh -2 * 0 add it up and
  • 00:24:04
    that leaves this as a one -2 * 0 we'll
  • 00:24:07
    leave this as a one -2 * 0 we'll leave
  • 00:24:10
    this as a Zer -2 * 1 uh we'll change
  • 00:24:15
    this into a -2 and -2 * 40 plus 100 will
  • 00:24:21
    give us 20
  • 00:24:23
    here okay so doing row
  • 00:24:26
    operations um
  • 00:24:29
    essentially maybe I'll kind of here's
  • 00:24:31
    maybe the way that I keep track of my
  • 00:24:33
    row operations of I took negative one
  • 00:24:36
    times this row and added up there I took
  • 00:24:40
    negative two times that row and added it
  • 00:24:43
    up there and then I need to cancel this
  • 00:24:47
    three out now to turn that into the zero
  • 00:24:49
    that I want there and so I'm going to
  • 00:24:51
    take uh
  • 00:24:54
    three times the bottom row add it up to
  • 00:24:57
    the top row
  • 00:24:59
    okay so this is going to remain a
  • 00:25:02
    one uh 3 * 1 + -3 that's going to get me
  • 00:25:07
    the zero that I want uh 3 * 0o uh we'll
  • 00:25:11
    leave this as a -2 3 * 0 will leave this
  • 00:25:15
    as a zero 3 * 0 + 0 will leave this 0 3
  • 00:25:21
    * 1 + 0 will turn this into a three and
  • 00:25:24
    3 * 40 + 0 is 120
  • 00:25:30
    okay so this is
  • 00:25:33
    our uh augmented Matrix or Tableau after
  • 00:25:38
    this process that we just did is called
  • 00:25:40
    pivoting so in pivoting uh you
  • 00:25:42
    essentially um change one of your
  • 00:25:45
    columns into a standard basis Vector in
  • 00:25:47
    this case we chose to change our XS
  • 00:25:50
    column into the standard basis Vector
  • 00:25:54
    00001 okay that brought XS into our
  • 00:25:57
    basis
  • 00:25:59
    I'll maybe show you yeah that brought
  • 00:26:01
    excess into our basis
  • 00:26:05
    okay so this is now our updated uh
  • 00:26:09
    Matrix uh it's row equivalent to what we
  • 00:26:12
    had before so has the same Solutions and
  • 00:26:15
    everything but we've sort of uh changed
  • 00:26:19
    uh where our nice uh kind of standard
  • 00:26:22
    basis vectors are in here okay so here's
  • 00:26:26
    our new basis I will say that non-basic
  • 00:26:33
    variables are XT and
  • 00:26:39
    SD uh SD because it left and XT because
  • 00:26:42
    it's still
  • 00:26:43
    non-basic okay and so those are both
  • 00:26:45
    going to be uh zero in our solution and
  • 00:26:48
    so reading off our new
  • 00:26:52
    solution um each basis each choice of
  • 00:26:55
    basis corresponds to a corner Point uh
  • 00:26:57
    BF best basic feasible solution and so
  • 00:27:00
    that new
  • 00:27:03
    solution uh we read it off um so
  • 00:27:06
    essentially the right hand side encodes
  • 00:27:10
    the values of Z SF s c and Xs okay and
  • 00:27:15
    that's because I'm essentially putting
  • 00:27:17
    in zeros for XT and SD and then if I put
  • 00:27:22
    zeros in for those then the only things
  • 00:27:24
    that have uh a coefficient in this first
  • 00:27:27
    row is the Z in the second row is SF and
  • 00:27:30
    in the third row SC and then in the last
  • 00:27:33
    row
  • 00:27:34
    Xs and so the new solution is z our
  • 00:27:37
    objective value has now increased to 120
  • 00:27:40
    okay that's going in the right direction
  • 00:27:42
    we went from zero objective to now
  • 00:27:45
    120 um
  • 00:27:47
    SF we can read off this value is now 20
  • 00:27:51
    we've got 20 units of finishing
  • 00:27:53
    slack we've got 40 units of carpent tree
  • 00:27:58
    slack and we are making now um 40
  • 00:28:05
    soldiers okay 40 soldiers
  • 00:28:09
    and zero trains and we've got
  • 00:28:13
    no slack for demand we are making all
  • 00:28:16
    the soldiers that demand tells us will
  • 00:28:19
    sell okay so this is essentially one
  • 00:28:23
    step of the Simplex algorithm okay to
  • 00:28:25
    kind of review uh
  • 00:28:29
    what happened in this one step is we
  • 00:28:32
    checked is it optimal we said no uh we
  • 00:28:35
    can improve it by bringing in XS or XT
  • 00:28:39
    into our basis we chose XS to enter our
  • 00:28:43
    basis we found which of the current
  • 00:28:47
    basis variables gets driven to zero
  • 00:28:49
    first and in this case it was SD so SD
  • 00:28:52
    exited our basis and then we had a new
  • 00:28:56
    basis and we pivoted on that new
  • 00:28:59
    basis okay uh pivoted on excess to get
  • 00:29:03
    to that uh Tableau that represents that
  • 00:29:05
    new basis and with that we got a new
  • 00:29:08
    solution okay now we now we repeat the
  • 00:29:11
    process um so let's ask uh the same
  • 00:29:14
    question again uh which is is it
  • 00:29:24
    optimal okay uh and so let's look at
  • 00:29:27
    this top row this top row Says
  • 00:29:30
    Z -
  • 00:29:34
    2xt + 3 SD equals
  • 00:29:39
    120 okay I'm going to go ahead and move
  • 00:29:42
    uh everything but Z to the other side
  • 00:29:44
    and so my formula for Z is I'll add 2xt
  • 00:29:48
    to the other side and minus 3 SD to the
  • 00:29:52
    other side uh plus
  • 00:29:56
    120 and so these two variables are
  • 00:29:59
    currently zero there are non-basic
  • 00:30:02
    variables and so if I look at them if I
  • 00:30:04
    were to increase SD from zero it's got a
  • 00:30:07
    negative coefficient so it would
  • 00:30:09
    decrease our objective not good
  • 00:30:13
    okay we might have had a hint that this
  • 00:30:15
    was going to happen because SD just left
  • 00:30:17
    our basis and we improved when it left
  • 00:30:19
    so we wouldn't want to immediately bring
  • 00:30:21
    it back in it wouldn't it wouldn't
  • 00:30:22
    provide any Improvement right now on the
  • 00:30:25
    other hand XT has a positive coefficient
  • 00:30:28
    okay uh so bringing XT into our basis
  • 00:30:32
    increasing it from zero should increase
  • 00:30:35
    our
  • 00:30:37
    objective okay so
  • 00:30:40
    uh yeah we want to
  • 00:30:43
    [Music]
  • 00:30:44
    choose so is it
  • 00:30:47
    optimal not
  • 00:30:52
    optimal XT can improve
  • 00:30:59
    uh the
  • 00:31:03
    objective okay so here's here's actually
  • 00:31:07
    the way I do it uh and so we've sort of
  • 00:31:09
    done it the long way but what you want
  • 00:31:11
    to do is scan this top row here and for
  • 00:31:14
    a maximization problem you want to look
  • 00:31:16
    for negative coefficients okay uh for
  • 00:31:19
    these variables here looks like XT has a
  • 00:31:21
    negative coefficient which means that
  • 00:31:23
    once we move it over the other side it
  • 00:31:24
    would be a positive coefficient and
  • 00:31:26
    would increase our OB object
  • 00:31:30
    objective then what I do is I go ahead
  • 00:31:32
    and circle that column okay XT is going
  • 00:31:35
    to be our entering
  • 00:31:37
    variable and now we need to do this
  • 00:31:40
    process again okay here's the thing to
  • 00:31:43
    get these numbers over here uh you'll
  • 00:31:47
    notice that these numbers over here are
  • 00:31:48
    exactly the right hand side numbers
  • 00:31:51
    divided by the coefficients of
  • 00:31:54
    XS okay and so that's all it is and then
  • 00:31:57
    we just chose the smallest positive one
  • 00:32:00
    so let's actually do that uh kind of as
  • 00:32:02
    a shortcut here so what we're going to
  • 00:32:03
    do is we're going to take our right hand
  • 00:32:05
    side and we're going to divide it by
  • 00:32:07
    whatever coefficient is in uh this XT
  • 00:32:11
    column and so we're going to do 20 over
  • 00:32:15
    one uh we'll do 40
  • 00:32:19
    over one and we'll do 40 over
  • 00:32:23
    z uh yeah if we got a zero or a negative
  • 00:32:26
    value here we ignore those rows okay um
  • 00:32:30
    it's not going to uh that uh that uh
  • 00:32:35
    that variable is not going to be driven
  • 00:32:37
    to zero okay
  • 00:32:39
    so so we're going to ignore that one and
  • 00:32:42
    now we choose the smaller of the two
  • 00:32:43
    okay so uh either SF or SC is going to
  • 00:32:48
    leave leave it turns out that uh By the
  • 00:32:51
    time
  • 00:32:53
    uh XT uh
  • 00:32:58
    yeah as we raise XT uh SF goes to zero
  • 00:33:01
    when XT is 20 and SC goes to zero when
  • 00:33:05
    XT is 40 and so we got to do the one
  • 00:33:07
    that goes drives it to zero first and so
  • 00:33:10
    SF is going to be
  • 00:33:12
    [Music]
  • 00:33:13
    our exiting
  • 00:33:20
    variable okay
  • 00:33:24
    so I'll move this up here XT
  • 00:33:28
    is
  • 00:33:32
    entering
  • 00:33:33
    SF is
  • 00:33:37
    exiting which gives us a new
  • 00:33:45
    basis uh let's see uh
  • 00:33:50
    Z XT is going to replace SF
  • 00:33:58
    uh SC is going to stay in and Xs is
  • 00:34:01
    going to stay
  • 00:34:02
    in and then our non-basic
  • 00:34:06
    variables are going to be
  • 00:34:10
    um well we just had SF leave and
  • 00:34:14
    SD um left in the previous
  • 00:34:17
    iteration
  • 00:34:19
    okay let's do another pivot uh this time
  • 00:34:24
    uh so looking up at this we sort of
  • 00:34:25
    circled a row as our sort of exiting
  • 00:34:28
    variable we circled a column as our
  • 00:34:30
    entering variable this point here is
  • 00:34:33
    going to see be uh kind of what I'd say
  • 00:34:36
    we pivot on this point okay meaning that
  • 00:34:39
    we want to turn this into a one
  • 00:34:41
    thankfully it's already already a one
  • 00:34:42
    and we're going to want to turn
  • 00:34:44
    everything else in this column into
  • 00:34:46
    zeros so that's the
  • 00:34:50
    goal I'm get myself a new sheet of paper
  • 00:34:53
    here and Slide the
  • 00:34:57
    okay actually
  • 00:35:00
    yeah so let's go ahead and set this up
  • 00:35:04
    and line it up right below here so
  • 00:35:08
    Z XS
  • 00:35:10
    XT
  • 00:35:12
    SF S C
  • 00:35:16
    SD right hand side normally once I get
  • 00:35:20
    kind of uh the pattern down I'll sort of
  • 00:35:23
    line these up so I don't have to write
  • 00:35:25
    my variables out again and I'll just
  • 00:35:27
    kind of have one Tableau directly below
  • 00:35:29
    the next
  • 00:35:30
    Tableau and so if you have like a nice
  • 00:35:32
    grid paper or something like that um
  • 00:35:35
    that can be kind of nice here okay so
  • 00:35:39
    I'm going to want to turn this value
  • 00:35:41
    into one turns out it's already a one
  • 00:35:43
    and so I can leave this row alone and so
  • 00:35:46
    let me draw this line here and then so
  • 00:35:49
    this uh second row is going to stay as Z
  • 00:35:52
    0 1 1 0 -2 20
  • 00:35:58
    okay now I like to think as little as
  • 00:36:02
    possible when I'm doing uh these row
  • 00:36:04
    operations because it's easy to kind of
  • 00:36:06
    get messed up and so I I like to fill in
  • 00:36:10
    right from the beginning as many entries
  • 00:36:11
    as I I can just because I know what my
  • 00:36:16
    next Tableau is going to look like okay
  • 00:36:18
    and as long as you're sort of following
  • 00:36:20
    the right rules um these these values
  • 00:36:22
    are going to kind of fill in the right
  • 00:36:24
    way um one is I know that I want this C
  • 00:36:27
    to become 0 1 0 0 okay that's what I
  • 00:36:33
    want it to come become I also know that
  • 00:36:37
    my other basic variables which let me
  • 00:36:39
    write that basis along the side here
  • 00:36:42
    zero uh x t s c and
  • 00:36:46
    Xs those other basic variables are going
  • 00:36:49
    to have the other standard basis vectors
  • 00:36:52
    uh beneath them and so my Z column
  • 00:36:56
    actually never changes throughout this
  • 00:36:57
    whole process um the Z column never
  • 00:37:00
    changes if you wanted to sort of omit
  • 00:37:02
    that Z column you could um but it's just
  • 00:37:05
    really There To Remind us that we've
  • 00:37:08
    introduced this Z variable it will
  • 00:37:10
    always say one z0
  • 00:37:12
    Z okay uh this SC column is going to
  • 00:37:15
    have the 0 0 one0 it's going to only
  • 00:37:20
    have a one in the row that it
  • 00:37:22
    corresponds to the SC row and then XS is
  • 00:37:25
    g to have a one right here but zeros
  • 00:37:29
    everywhere else okay and then from there
  • 00:37:33
    now I just see that I only have one two
  • 00:37:35
    three four five six seven eight nine
  • 00:37:38
    things that are gonna actually have to
  • 00:37:39
    think about okay so that's sort of a
  • 00:37:42
    nice shortcut is put my standard basis
  • 00:37:45
    vectors exactly where they need to be
  • 00:37:47
    okay uh so this row already had a one
  • 00:37:50
    there it didn't need to be multiplied it
  • 00:37:52
    was able to stay the same okay now I
  • 00:37:54
    need to take multiples of this row add
  • 00:37:57
    up and down in order to cancel out uh
  • 00:38:00
    the different values and so let's go up
  • 00:38:04
    first uh and so I've got a one here I
  • 00:38:07
    got a negative -2 here so I'm going to
  • 00:38:10
    take
  • 00:38:11
    uh two times that row added up in order
  • 00:38:15
    to
  • 00:38:16
    cancel so uh 2 * 1 added to the -2 will
  • 00:38:22
    give me zero that's what I want that's
  • 00:38:24
    why I chose two uh 2 * 1 plus the zero
  • 00:38:28
    is going to make this into a two uh 2 *
  • 00:38:32
    -2 is -4 plus the three uh becomes - 1 2
  • 00:38:37
    * 20 is 40 plus the 120 is
  • 00:38:44
    160 okay now I want to zero this value
  • 00:38:48
    out here and so I'm going to actually
  • 00:38:52
    take this row times Nega 1 add it down
  • 00:38:55
    and so take1 1 times that row add it
  • 00:38:59
    down um so -1 * 1 + 1 is z that gave me
  • 00:39:04
    what I wanted uh -1 * 1 + 0 is 1 uh 1
  • 00:39:11
    * that's going to give me my 1 -1 * 2 is
  • 00:39:16
    pos2 plus the - 1 is postive 1
  • 00:39:20
    and uh 1 * 20 + 40 is positive 20
  • 00:39:28
    okay looking at my last row I want a
  • 00:39:30
    zero here I've got a zero there so I
  • 00:39:33
    actually can leave this last row alone
  • 00:39:35
    nothing changes in this last row zero
  • 00:39:38
    one
  • 00:39:40
    40 okay the last row didn't
  • 00:39:43
    change okay um so there I go I pivoted
  • 00:39:47
    this was a little bit quicker now this
  • 00:39:49
    time and as you get the practice it it
  • 00:39:51
    it'll move a little bit faster you're
  • 00:39:53
    just doing Elementary row operations of
  • 00:39:55
    taking multiples of a row and adding it
  • 00:39:58
    or subtracting it to the other rows and
  • 00:40:00
    it's you're always going to essentially
  • 00:40:02
    use your pivot row as your I like to
  • 00:40:05
    think of it as a tool okay it's going to
  • 00:40:08
    be what you're going to be adding and
  • 00:40:09
    subtracting to your other rows to make
  • 00:40:11
    things
  • 00:40:12
    happen Okay uh new solution we've got a
  • 00:40:15
    new basis now let's go ahead and read
  • 00:40:17
    off our new
  • 00:40:23
    solution our objective value Z increased
  • 00:40:27
    to 160 that's good we should always see
  • 00:40:30
    this uh our objective value
  • 00:40:33
    improving XT we can read it off this row
  • 00:40:37
    XT =
  • 00:40:39
    20
  • 00:40:42
    SC equal 20 and
  • 00:40:47
    Xs equal 40 I'm reading those off the
  • 00:40:50
    right hand side um because the other
  • 00:40:55
    variables uh
  • 00:40:57
    SF and SD are both
  • 00:41:03
    zero okay that's so that's my new
  • 00:41:05
    solution my new basic feasible solution
  • 00:41:07
    it is feasible uh because I should
  • 00:41:09
    verify all my entries are positive okay
  • 00:41:13
    um all the variable values are positive
  • 00:41:15
    so I'm at a feasible
  • 00:41:18
    Point okay am I optimal Let's uh do what
  • 00:41:22
    we did last time so I said we want to
  • 00:41:24
    scan the top row for negatives
  • 00:41:28
    okay uh so it was this sort of -2 that
  • 00:41:30
    tipped us off that we should choose XT
  • 00:41:32
    as our entering variable now as I scan
  • 00:41:35
    the top row I see a negative one here
  • 00:41:38
    okay so we're not yet
  • 00:41:49
    optimal no um essentially that top row
  • 00:41:53
    says that Z equal -2 SF plus
  • 00:41:59
    SD plus 160 and so if I increase SD now
  • 00:42:06
    um kind of one pivot into the future it
  • 00:42:08
    will actually improve it and so although
  • 00:42:10
    in our first iteration we sort of moved
  • 00:42:13
    SD out of the basis um now we're going
  • 00:42:16
    to move it back into the basis okay and
  • 00:42:19
    as long as it's sort of one pivot later
  • 00:42:21
    on down the road that's sort of fine um
  • 00:42:24
    and and it's actually going to lead to
  • 00:42:26
    an improvement
  • 00:42:29
    okay um so we're going to have
  • 00:42:34
    SD as our entring
  • 00:42:38
    variable we'll Circle this column here
  • 00:42:41
    we can see that it's got a negative one
  • 00:42:43
    in the top row negative coefficient in
  • 00:42:45
    the top row it indicates Improvement for
  • 00:42:48
    a maximization
  • 00:42:50
    problem now let's go ahead and compute
  • 00:42:52
    our ratios we take this number divided
  • 00:42:54
    by the value in our pivot column
  • 00:42:58
    if we have a negative in our PIV pivot
  • 00:43:00
    column ignore that one we can't pivot on
  • 00:43:02
    a negative okay um so then we get 20
  • 00:43:07
    over one and 40 over one and so choose
  • 00:43:11
    the smaller of the two and so we're
  • 00:43:14
    going to
  • 00:43:15
    choose this
  • 00:43:19
    one
  • 00:43:21
    okay so which variable is that that's SC
  • 00:43:24
    so SC is going to be exiting
  • 00:43:31
    okay now let's go ahead I want to pause
  • 00:43:34
    the video a little bit and rearrange my
  • 00:43:37
    paper okay I folded my paper over to
  • 00:43:40
    kind of hide the stuff that we just
  • 00:43:41
    wrote in the middle there so that I can
  • 00:43:43
    have my two tablos right next to each
  • 00:43:45
    other I also went ahead and kind of uh
  • 00:43:48
    set up the uh the edges the labels on my
  • 00:43:51
    taows um but so this is our pivot uh
  • 00:43:55
    column uh this is our pivot row we want
  • 00:43:59
    a one here and Zer everywhere else in
  • 00:44:01
    that column so we want to turn this SD
  • 00:44:03
    column into zero 0 one
  • 00:44:08
    0 okay uh turns out we got a one here uh
  • 00:44:12
    so we don't need to do anything to this
  • 00:44:14
    row if it were a two we'd divide by two
  • 00:44:17
    if it were a half we'd multiply by two
  • 00:44:19
    essentially we'd multiply or divide this
  • 00:44:21
    row by whatever we needed to in order to
  • 00:44:24
    turn this into a one got a little lucky
  • 00:44:27
    it's already one again and so we're
  • 00:44:29
    going to have uh we're going to leave it
  • 00:44:31
    alone and we're going to get zero uh 0 0
  • 00:44:35
    neg1 1 and
  • 00:44:40
    20 um and now let's go ahead and fill in
  • 00:44:42
    the columns that we know are going to be
  • 00:44:44
    what they're going to be so our basis
  • 00:44:46
    columns are going to still be one zer0
  • 00:44:49
    for um Z my second basis column is going
  • 00:44:52
    to be
  • 00:44:54
    XT my third basis column is this SD and
  • 00:44:57
    my last basis column is
  • 00:45:01
    XS that's going to give me those okay
  • 00:45:04
    and you can verify that actually because
  • 00:45:06
    you'll notice that um this row has zeros
  • 00:45:10
    in both in all three of these places
  • 00:45:12
    then as we add or subtract multiples of
  • 00:45:15
    this this row here this SD row it's
  • 00:45:17
    actually not going to change any of the
  • 00:45:19
    entries in these three columns because
  • 00:45:22
    it's got zeros here so that's why I can
  • 00:45:24
    kind of quickly fill those values in
  • 00:45:29
    okay now let's kind of go ahead and
  • 00:45:31
    think about what we need to do uh to
  • 00:45:35
    cancel out various values let's go up to
  • 00:45:37
    the top row we've got a one here a
  • 00:45:39
    negative one here if I add this row up
  • 00:45:42
    um that will cancel out the one here and
  • 00:45:44
    so I'm going to
  • 00:45:46
    do one times this row add it up to that
  • 00:45:51
    row and so that's going to be 1 * - 1
  • 00:45:54
    plus the 2 is going to give positive 1 1
  • 00:45:59
    * 1 + 0 is going to be 1 1 * 1 +
  • 00:46:06
    negative 1 is going to give me the zero
  • 00:46:07
    that's there 1 * 20 + 160 is going to
  • 00:46:12
    make it
  • 00:46:14
    180 okay next we'll go ahead and zero
  • 00:46:17
    out this entry here uh I need to add two
  • 00:46:20
    times this row up to that Row in order
  • 00:46:23
    to cancel it and so I'll go remind
  • 00:46:27
    myself that I'm going to take two times
  • 00:46:28
    that add it up to there um so 2
  • 00:46:32
    * -1 + one is going to be uh negative
  • 00:46:41
    1 2 * 1 + 0 will be 2 2 * 1 + -2 is
  • 00:46:47
    going to give us the zero that we want 2
  • 00:46:50
    * 20 uh plus 20 is going to give us 60
  • 00:46:55
    and that's good for that row now if we
  • 00:46:57
    think about what we need to do uh to
  • 00:46:59
    cancel out this one here we're going to
  • 00:47:02
    take this row times neg1 and add it down
  • 00:47:07
    to
  • 00:47:09
    here okay and so uh neg 1 * uhga - 1 + 0
  • 00:47:16
    is going to be positive 1 -1 * 1 + 0 is
  • 00:47:23
    going to
  • 00:47:23
    be 1 -1 * 1 + 1 is going to give us our
  • 00:47:28
    zero that we want and -1 * 20 + 40 is
  • 00:47:33
    going to give us
  • 00:47:35
    20 okay so we F finished pivoting there
  • 00:47:38
    we now have our standard basis vectors
  • 00:47:41
    here here here and here okay um and now
  • 00:47:46
    we can read off our new
  • 00:47:49
    solution so our new
  • 00:47:55
    solution uh reading it off sort of for
  • 00:47:58
    our first row corresponds is our
  • 00:48:00
    z um z r uh equals
  • 00:48:05
    180 second row tells us that XT equal 60
  • 00:48:10
    third row tells us that SD equal 20
  • 00:48:15
    fourth row tells us that XS = 20 and
  • 00:48:20
    then because they're non-basic we know
  • 00:48:22
    that um
  • 00:48:24
    SF and S are both
  • 00:48:29
    zero okay that's our new solution ask
  • 00:48:32
    the same question again is it optimal
  • 00:48:34
    okay and we're going to scan this top
  • 00:48:36
    row there's no negatives so the question
  • 00:48:40
    to is it
  • 00:48:43
    optimal the answer is
  • 00:48:46
    now
  • 00:48:48
    yes okay and that's because if we look
  • 00:48:50
    at the top row and sort of move things
  • 00:48:52
    over to the other side Z is going to be
  • 00:48:55
    netive s F minus S C + 180 and so if I
  • 00:49:02
    were to increase either SF or SC from
  • 00:49:05
    zero both of those would have a negative
  • 00:49:08
    effect on Z okay z uh yeah the best we
  • 00:49:12
    can do for Z is actually 180 increasing
  • 00:49:15
    either of these would uh decrease our
  • 00:49:18
    objective
  • 00:49:19
    value and so that is our optimal
  • 00:49:22
    solution here uh and sort of the end of
  • 00:49:25
    the Simplex algorithm okay to wrap this
  • 00:49:28
    up I want to kind of pictorially show
  • 00:49:30
    you what sort of happened uh in our
  • 00:49:33
    feasible region so I'm going to kind of
  • 00:49:35
    sketch a quick uh sketch of our feasible
  • 00:49:40
    region um let's
  • 00:49:49
    see okay not going to be perfectly uh
  • 00:49:53
    accurate with this this sketch here um
  • 00:49:55
    but we started off uh if we think of our
  • 00:49:58
    variables as
  • 00:50:00
    Xs and XT and we just sort of plotted in
  • 00:50:04
    the original variables we started off
  • 00:50:06
    with both Xs and XT at zero and so we
  • 00:50:09
    started at0 0 in the original
  • 00:50:12
    coordinates um then after one step we
  • 00:50:16
    moved to the point where we were at
  • 00:50:21
    40 okay and then in another step we
  • 00:50:24
    moved up here to where we were at 40 20
  • 00:50:29
    and then in the final step we moved up
  • 00:50:31
    to here where we are now at
  • 00:50:36
    uh no no no
  • 00:50:39
    no oh
  • 00:50:42
    2060 y so XS is 20 XT is 60 yep yep so
  • 00:50:49
    we went from 40 20 to 2060 there yeah
  • 00:50:52
    and so uh what the Simplex method does
  • 00:50:55
    is it is mov moves us around the
  • 00:50:57
    boundary um sort of uh if we had made
  • 00:51:01
    the opposite Choice uh in the first step
  • 00:51:04
    we actually could have gone from here to
  • 00:51:05
    here to here and gotten there in two
  • 00:51:07
    steps instead of three steps um but
  • 00:51:09
    really you don't know that um from the
  • 00:51:11
    beginning and in practice we're dealing
  • 00:51:14
    with higher dimensional spaces and it's
  • 00:51:15
    more like uh kind of branching uh
  • 00:51:18
    through um kind of a bunch of edges on a
  • 00:51:22
    hypergraph or something like that but um
  • 00:51:25
    visually you kind of want to think about
  • 00:51:26
    is that we're moving from here to here
  • 00:51:28
    to here each time um because our
  • 00:51:31
    objective vector or kind of the director
  • 00:51:34
    direction of improvement um was sort of
  • 00:51:36
    in the three two was sort of in this
  • 00:51:39
    direction here um we were always moving
  • 00:51:42
    in a direction that offered us some
  • 00:51:45
    improvement
  • 00:51:47
    okay uh so that'll wrap up this video uh
  • 00:51:51
    the next video we'll sort of talk about
  • 00:51:53
    the Simplex method from a bird's eye
  • 00:51:54
    view and do some more practice
ๆ ‡็ญพ
  • Simplex Method
  • Linear Programming
  • Basic Feasible Solution
  • Slack Variables
  • Pivoting
  • Feasible Region
  • Optimization
  • Objective Function
  • Tableau Method
  • Iterative Process