Augmented Form for Simplex Method

00:22:41
https://www.youtube.com/watch?v=secIq0HDi3Q

摘要

TLDRDenne video introducerer Simplex-metoden til løsning af lineære programmer ved hjælp af et eksempel, kaldet Gepetto-problemet. Videoen dækker konvertering af lineære programmer til standardform og augmented form ved hjælp af slack- og overskudsvariable. Dette gøres for at ændre uligheder til ligheder, hvilket er nødvendigt for anvendelsen af Simplex-metoden. Der forklares forskelle mellem maksimering og minimering af problemer, og hvordan slack- og overskudsvariable indikerer den mulige løsningens status i forhold til begrænsninger.

心得

  • 📊 Lineære programmer kan have uligheder, som ændres til ligheder med slack-variabler.
  • 🔄 Augmented form bruges i Simplex-metoden til at håndtere uligheder.
  • 📈 Gepetto-problemet er et eksempel på lineær optimering.
  • 🚌 Standardform bruges til at skrive problemer, men augmented form er behov for beregninger.
  • 🔧 Slack- og overskudsvariable styrer hvilken side af en begrænsning en løsning ligger på.

时间轴

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

    Introduktion til Simplex-metoden og formulation af Jepettos problem med to beslutningsvariable og forskellige begrænsninger. Skitsering af det mulige område for løsninger som en del af forberedelserne til at anvende Simplex-metoden.

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

    Transformation af lineære programmer til augmented form ved at introducere slack- og surplusvariable for at konvertere uligheder til ligheder. Dette lettes af de yderligere variable, der justerer ulighederne til lighed, hvilket er nødvendigt for Simplex-metoden.

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

    Udforskning af hvordan slack- og surplusvariable virker indenfor constraints ved at identificere hvilke side af en constraint en løsning befinder sig på. Detaljeret analyse af forskellige punkter inden for og uden for det mulige område for at forstå virkningen af disse variable.

  • 00:15:00 - 00:22:41

    Avanceret forståelse af slack- og surplusvariable og deres betydning i vurderingen af begrænsningsgrænser. Anvendelse af punkter på, indenfor og udenfor grænserne for at afkode begrænsningerne og forbedre problemforståelsen for Simplex-anvendelse.

显示更多

思维导图

Mind Map

常见问题

  • Hvad er slack-variabler?

    Slack-variabler tilføjes til mindre-end eller lig-med uligheder i lineære programmer for at konvertere dem til ligheder.

  • Hvordan ændres uligheder til ligheder i lineære programmer?

    Uligheder ændres til ligheder ved at tilføje slack- eller overskudsvariable.

  • Hvad er gepetto-problemet?

    Gepetto-problemet er et eksempel på et lineært program brugt til at demonstrere Simplex-metoden.

  • Hvorfor kan vi ikke have strenge uligheder i lineære programmer?

    Strenge uligheder kan ikke bruges fordi løsningerne i lineære programmer ligger på grænserne af det tilladte område.

  • Hvad bruges Simplex-metoden til?

    Simplex-metoden bruges til at løse lineære optimeringsproblemer.

查看更多视频摘要

即时访问由人工智能支持的免费 YouTube 视频摘要！
字幕
en
自动滚动:
  • 00:00:02
    okay welcome to another operations
  • 00:00:03
    research video uh today is the first day
  • 00:00:06
    where we start uh thinking about how to
  • 00:00:08
    solve linear programs using the Simplex
  • 00:00:11
    method it's going to be a a series of
  • 00:00:13
    videos kind of diving into the Simplex
  • 00:00:15
    method um and here we've got a jepetto's
  • 00:00:19
    problem again we introduced jepetto's
  • 00:00:21
    problem in a previous video but it will
  • 00:00:23
    be featuring prominently uh over the
  • 00:00:26
    next couple videos as we discuss and
  • 00:00:29
    think about the Simplex method so uh
  • 00:00:33
    here's the description of it feel free
  • 00:00:34
    to pause and read it um I'll also have a
  • 00:00:37
    scan version of this uh linked on Moodle
  • 00:00:41
    as
  • 00:00:42
    well uh here's essentially the
  • 00:00:46
    formulation for the linear program uh we
  • 00:00:49
    got two decision variables the number of
  • 00:00:51
    soldiers and the number of trains which
  • 00:00:53
    we'll use as x with a subscript of s and
  • 00:00:55
    x with a subscript of T change those up
  • 00:00:58
    a little bit from the previous videos uh
  • 00:01:01
    and then we've got our objective here
  • 00:01:03
    and three constraints dealing with the
  • 00:01:05
    finishing carpentry and demand um for
  • 00:01:08
    the products and then also the non-
  • 00:01:10
    negativity
  • 00:01:12
    constraints I've gone ahead and sketched
  • 00:01:14
    the feasible region here um this region
  • 00:01:17
    right here is the feasible region that's
  • 00:01:20
    uh below and to the left of each of
  • 00:01:23
    those constraint lines while still being
  • 00:01:25
    in the first quadrant I haven't shaded
  • 00:01:27
    it in because we're going to uh be
  • 00:01:29
    adding to this uh sketch in a little bit
  • 00:01:32
    so I encourage you uh maybe pause the
  • 00:01:34
    video uh and copy down a a version of
  • 00:01:38
    this sketch so that you two can add to
  • 00:01:40
    it um as well so feel free to kind of
  • 00:01:44
    also sketch it up in Desmos if you want
  • 00:01:47
    um but it' be nice to have a paper and
  • 00:01:49
    pencil one so you can annotate it as
  • 00:01:51
    well
  • 00:01:54
    so first topic we want to introduce uh
  • 00:01:57
    on our way to the Simplex method is
  • 00:02:00
    a little bit about the way that we write
  • 00:02:03
    our um linear
  • 00:02:05
    programs uh so we'll introduce this idea
  • 00:02:08
    of standard form and then augmented form
  • 00:02:11
    so uh a linear program can have equality
  • 00:02:15
    constraints uh greater than or equal to
  • 00:02:17
    constraints or less than or equal to to
  • 00:02:20
    constraints um but oftentimes eventually
  • 00:02:22
    we're going to want to put it into
  • 00:02:23
    augmented form where they all become
  • 00:02:26
    equality constraints uh note that we
  • 00:02:28
    never have strict in qualities in our
  • 00:02:31
    constraints um and maybe I'll leave that
  • 00:02:33
    to you to think about why we can't do
  • 00:02:35
    that um especially since um as I
  • 00:02:38
    introduced last time all our Solutions
  • 00:02:40
    are going to be on the boundary and what
  • 00:02:42
    would it mean if our boundary wasn't
  • 00:02:43
    included in the sort of allowable um
  • 00:02:47
    feasible feasible space
  • 00:02:51
    okay so uh two formats for either
  • 00:02:57
    maximization or minimization format form
  • 00:03:00
    that we'll call standard form um for a
  • 00:03:02
    standard form for maximization all the
  • 00:03:05
    constraints are less than or equal to um
  • 00:03:08
    so we're trying to make something as big
  • 00:03:10
    as possible but we're limited by some
  • 00:03:12
    less than or equal to constraints um you
  • 00:03:15
    can think of this as maximizing profit
  • 00:03:19
    uh under limited uh resources so treto's
  • 00:03:23
    problem is a great example of that we
  • 00:03:25
    want to maximize profit but we've got a
  • 00:03:27
    limited amount of some various resources
  • 00:03:29
    and those limited resources make up our
  • 00:03:33
    constraints um for a minimization
  • 00:03:35
    problem on the other hand the standard
  • 00:03:37
    format uh will have all greater than or
  • 00:03:40
    equal to constraints um you can think of
  • 00:03:43
    the prototype for this one being
  • 00:03:44
    minimizing cost but you've got some
  • 00:03:47
    required activities uh that make up your
  • 00:03:50
    constraints and so uh you might think of
  • 00:03:54
    BJ's steak and potato diet problem um he
  • 00:03:58
    wanted to minimize the cost for uh his
  • 00:04:02
    diet that was strictly Stak in potatoes
  • 00:04:05
    um but he had some greater than or equal
  • 00:04:08
    to constraints um that he needed to M
  • 00:04:11
    meet his minimum requirements for um I
  • 00:04:15
    think it was protein and uh carbs and so
  • 00:04:19
    uh yeah there was some minimum
  • 00:04:22
    requirements while still minimizing cost
  • 00:04:25
    okay and so that that's maybe another
  • 00:04:29
    example of standard form
  • 00:04:31
    there so these are usually the formats
  • 00:04:35
    uh that we use when we're formulating
  • 00:04:38
    the problem when we're writing it up um
  • 00:04:40
    when we're entering it into the computer
  • 00:04:42
    often uh standard form is what we want
  • 00:04:44
    it to be in but when we go to solve it
  • 00:04:48
    or at least under the hood when the
  • 00:04:49
    computer goes to solve it it will take
  • 00:04:52
    whatever we give it in standard form or
  • 00:04:54
    even if we don't give it to it in
  • 00:04:56
    perfect standard form and modify it into
  • 00:04:59
    to an augmented format and this
  • 00:05:01
    augmented format is the format that
  • 00:05:04
    we'll put our our problems into in order
  • 00:05:07
    to use the Simplex method in augmented
  • 00:05:09
    format we'll change all the constraints
  • 00:05:12
    to be equality
  • 00:05:14
    constraints so how do we do that how do
  • 00:05:16
    we change uh inequality constraints uh
  • 00:05:20
    into equality constraints and the the
  • 00:05:23
    way we do that is by
  • 00:05:25
    introducing uh new variables slack and
  • 00:05:28
    surplus variables and these slack and
  • 00:05:30
    surplus variables um kind of play a role
  • 00:05:35
    um for a less than or equal to
  • 00:05:37
    constraint we add a non- negative uh
  • 00:05:41
    slack variable to the left hand side to
  • 00:05:44
    change it into an equality constraint
  • 00:05:46
    and so I often think of uh if we've got
  • 00:05:50
    a less than or equal to constraint we do
  • 00:05:53
    a plus a slack and then that becomes an
  • 00:05:57
    equality this variable essenti takes up
  • 00:06:00
    the slack in our constraint because uh
  • 00:06:04
    with a less than or equal to constraint
  • 00:06:06
    uh we're either if we're strictly less
  • 00:06:08
    than it then we have some slack some
  • 00:06:11
    extra room and this variable s is
  • 00:06:14
    essentially going to take up all that
  • 00:06:16
    extra room in order to make the
  • 00:06:19
    inequality into an
  • 00:06:21
    equality uh if we are have a greater
  • 00:06:24
    than constraint then we're usually above
  • 00:06:26
    or at the uh boundary if we're above
  • 00:06:29
    that boundary we've got some Surplus and
  • 00:06:32
    so we're going to subtract off a non-
  • 00:06:35
    negative amount of surplus uh and so a
  • 00:06:38
    greater than constraint goes to we're
  • 00:06:41
    going to
  • 00:06:42
    subtract a surplus variable and change
  • 00:06:45
    it into Ane
  • 00:06:47
    equality and then if we have inequality
  • 00:06:49
    constraint we don't need to do anything
  • 00:06:52
    uh to change it to put it into augmented
  • 00:06:54
    format uh later on we'll we'll deal with
  • 00:06:59
    having to make add some extra variables
  • 00:07:00
    even to our equality constraints to to
  • 00:07:03
    get started with the Simplex method but
  • 00:07:05
    we won't worry about that now okay um so
  • 00:07:08
    let's uh actually add those variables
  • 00:07:12
    and change the constraints for jepetto's
  • 00:07:15
    uh
  • 00:07:17
    problem so in jepetto's problem we've
  • 00:07:20
    got all less than or equal to
  • 00:07:22
    constraints and so for each constraint
  • 00:07:25
    We'll add a
  • 00:07:27
    new uh slack Vari variable to take up
  • 00:07:31
    the extra slack and so uh this
  • 00:07:34
    constraint here uh for finishing we're
  • 00:07:38
    going to have
  • 00:07:40
    2xs plus
  • 00:07:42
    XT and then we're going to introduce a
  • 00:07:45
    slack variable to pick up any extra that
  • 00:07:48
    might make this actually be less than
  • 00:07:51
    100 and so I'm going to call my slack
  • 00:07:54
    variables um I usually have an S as the
  • 00:07:57
    variable and then I'll give an a
  • 00:07:58
    subscript that relates to the constraint
  • 00:08:01
    because you want to think of these slack
  • 00:08:03
    variables and surplus variables as being
  • 00:08:05
    related to this the constraint and so
  • 00:08:08
    I'm going to call this SF for the slack
  • 00:08:11
    for the finishing constraint and then
  • 00:08:13
    that becomes equal to
  • 00:08:17
    100 okay if it helps you think about it
  • 00:08:20
    this SF what is that well if we kind of
  • 00:08:23
    move everything over the other side SF
  • 00:08:27
    is 100 minus
  • 00:08:31
    2xs -
  • 00:08:33
    XT it is every bit of extra that uh this
  • 00:08:39
    constraint was uh that the left hand
  • 00:08:41
    side was less than 100 so that is
  • 00:08:45
    essentially what goes in there and as
  • 00:08:47
    long as SF is bigger than or equal to
  • 00:08:52
    zero this constraint is
  • 00:08:54
    satisfied
  • 00:08:56
    okay so uh let's go ahead and do that
  • 00:08:58
    with the rest and then we'll kind of
  • 00:09:00
    illustrate uh pictorially down below
  • 00:09:03
    what we're meaning about for each of
  • 00:09:07
    these okay so this
  • 00:09:10
    one uh let's see uh so we're going to
  • 00:09:13
    take this constraint it's a less than or
  • 00:09:15
    equal to constraint and so we're going
  • 00:09:17
    to copy down the left
  • 00:09:21
    side and then we're going to introduce a
  • 00:09:24
    slack variable and it's going to be a
  • 00:09:26
    different slack variable than the first
  • 00:09:28
    constraint um so I'm going to introduce
  • 00:09:30
    a new slack variable I'll do plus s c uh
  • 00:09:34
    C being carpentry so this is the slack
  • 00:09:37
    variable for the carpentry constraint
  • 00:09:39
    and then that inequality becomes an
  • 00:09:42
    equality uh with the right hand side of
  • 00:09:46
    80 uh last constraint becomes x
  • 00:09:52
    s uh plus s I'll do use D for demand
  • 00:09:58
    equal
  • 00:10:00
    equals 40 and now I've got not two
  • 00:10:03
    variables but now I've got five
  • 00:10:06
    variables and so my variables are now
  • 00:10:09
    XS XT
  • 00:10:13
    SF s c and SD and all of those should be
  • 00:10:18
    greater than or equal to
  • 00:10:20
    zero okay so that's how you transform
  • 00:10:23
    them for slack variables or for less
  • 00:10:26
    than or equal to constraints you add
  • 00:10:28
    slack for greater than or equal to
  • 00:10:30
    constraints you subtract the Surplus
  • 00:10:33
    beautiful thing is that both slack and
  • 00:10:35
    surplus start with s and so I'll use S
  • 00:10:37
    to denote either slack or Surplus
  • 00:10:39
    variables the difference will only be
  • 00:10:42
    whether we add or subtract them to to
  • 00:10:44
    the uh constraints to make them into
  • 00:10:48
    equalities
  • 00:10:51
    so here's the important part about slack
  • 00:10:54
    and surplus variables is that they
  • 00:10:56
    encode which side of the constraint
  • 00:10:58
    we're on
  • 00:11:01
    if the slack variable or the the Surplus
  • 00:11:04
    variable is positive bigger than zero
  • 00:11:08
    then we're on the con correct side of
  • 00:11:10
    the constraint and away from the
  • 00:11:12
    constraint so we're not on the boundary
  • 00:11:14
    of the constraint that constraint isn't
  • 00:11:16
    going to be a limiting
  • 00:11:18
    factor uh if s is less than zero then
  • 00:11:21
    we're actually on the wrong side of the
  • 00:11:23
    constraint and the original constraint
  • 00:11:25
    is
  • 00:11:26
    violated and then the third option is if
  • 00:11:29
    we're equal to zero then we are exactly
  • 00:11:31
    on the boundary of the constraint the
  • 00:11:33
    original constraint is satisfied and
  • 00:11:36
    that constraint is limiting meaning that
  • 00:11:38
    we we can't uh do any more of uh some of
  • 00:11:42
    our variables without going outside of
  • 00:11:45
    the that constraint and so that
  • 00:11:46
    constraint is actually limiting us okay
  • 00:11:50
    so let's actually look at uh jepetto's
  • 00:11:53
    problem and let's think about where
  • 00:11:57
    those variables are or or kind of the
  • 00:12:00
    different um sides of that and so let's
  • 00:12:02
    choose one of the constraints I'm going
  • 00:12:04
    to choose the finishing constraint first
  • 00:12:06
    uh which this is the this line
  • 00:12:08
    represents the boundary of the finishing
  • 00:12:10
    constraint and so along that line I'm
  • 00:12:13
    going to kind of turn the paper just a
  • 00:12:14
    little bit so I can WR sideways along
  • 00:12:16
    that line along that line that is where
  • 00:12:19
    SF equals
  • 00:12:23
    zero okay on this side of the line the
  • 00:12:27
    correct side of the line we've got s f
  • 00:12:30
    is positive bigger than zero and then
  • 00:12:34
    over here on this side of the line we
  • 00:12:36
    have
  • 00:12:37
    SF is less than Z negative okay and so
  • 00:12:42
    if we're on the correct side of the
  • 00:12:43
    constraint we're that slack variable is
  • 00:12:47
    positive if we're on the constraint
  • 00:12:50
    boundary uh that that slack variable is
  • 00:12:52
    zero and if we're on the wrong side of
  • 00:12:55
    the constraint uh that slack variable is
  • 00:12:58
    negative
  • 00:12:59
    okay and we could do the same thing uh
  • 00:13:02
    for each of the other constraints as
  • 00:13:04
    well the demand constraint and the
  • 00:13:06
    carpentry constraint along this line SC
  • 00:13:10
    is zero if we're below that line SC is
  • 00:13:14
    positive if we're above that line SC is
  • 00:13:18
    negative similar with demand if we're to
  • 00:13:22
    if we're on it SD is uh zero if we're to
  • 00:13:25
    the left of it SD is positive and if
  • 00:13:28
    we're to the right of it s s d is
  • 00:13:30
    negative okay let's actually choose a
  • 00:13:34
    point in space and I'm going to choose a
  • 00:13:37
    point that's maybe not on any of um any
  • 00:13:41
    of the constraints so actually I'm going
  • 00:13:43
    to choose this point right here and
  • 00:13:45
    that's the point uh
  • 00:13:48
    2020 um and so let's look at uh the
  • 00:13:54
    point 2020 where XS equals 20 and X x t
  • 00:13:59
    = 20 and let's figure out um what are
  • 00:14:04
    the values of our slack variables at
  • 00:14:07
    that
  • 00:14:08
    point so at that point if I plug in 20
  • 00:14:12
    and 20 into each of these equations I'll
  • 00:14:15
    notice once I fill those in I've only
  • 00:14:17
    got one of the slack variables in each
  • 00:14:19
    of those equations and so I can solve
  • 00:14:21
    for each of them and so uh then if I
  • 00:14:24
    look at finishing
  • 00:14:30
    uh I'll
  • 00:14:32
    have two
  • 00:14:36
    times okay
  • 00:14:38
    resuming actually got a phone call in
  • 00:14:39
    the middle middle of uh recording okay
  • 00:14:42
    so if we plug in 20 we've got two times
  • 00:14:46
    uh
  • 00:14:47
    XS uh which is 20 + XT is 20 +
  • 00:14:53
    SF equal
  • 00:14:55
    100 and so this is going to be 40 + 20
  • 00:14:59
    is 60 and if I subtract that over the
  • 00:15:02
    other side that will tell me that the
  • 00:15:05
    first constraint uh has 40 units of
  • 00:15:10
    slack which means that if we were to
  • 00:15:12
    choose to make uh 20 soldiers and 20
  • 00:15:16
    trains then we'd have 40 extra hours of
  • 00:15:19
    finishing labor okay and so uh you can
  • 00:15:22
    think of these slack variables as having
  • 00:15:25
    whatever um units the constraint had and
  • 00:15:30
    so that first constraint was talking
  • 00:15:31
    about hours of finishing labor and so
  • 00:15:33
    we've got 40 extra hours of finishing
  • 00:15:37
    labor if we look at
  • 00:15:42
    carpentry uh let's see we got
  • 00:15:45
    uh XS plus XT plus SC so 20 + 20 + SC c
  • 00:15:53
    equal 80 20 + 20 is 40 I'm going to
  • 00:15:56
    subtract those over the other side and I
  • 00:15:58
    get
  • 00:15:59
    SC is also equal to 40 and so if we make
  • 00:16:03
    20 soldiers and 20 trains we've got um
  • 00:16:06
    20 spare units of carpentry
  • 00:16:11
    labor and then if I look at
  • 00:16:14
    demand that's XS is 20 plus
  • 00:16:20
    SD is uh has to be equal to 40 and so if
  • 00:16:23
    I subtract 20 from both sides that will
  • 00:16:27
    give SD equals 20 and so what you'll
  • 00:16:31
    notice about each of these is because I
  • 00:16:32
    chose a point on the interior of the
  • 00:16:35
    feasible region there's a positive
  • 00:16:38
    amount of slack in each of those
  • 00:16:41
    constraints okay let's uh choose another
  • 00:16:45
    point but this time we'll choose a point
  • 00:16:47
    that's on the
  • 00:16:49
    boundary and so uh let's choose this
  • 00:16:52
    point up here uh the 20 and
  • 00:16:57
    uh uh let's see yeah yeah let's choose
  • 00:17:00
    this point up here
  • 00:17:04
    2060 and let's do that same computation
  • 00:17:08
    uh compute how much slack there is I
  • 00:17:10
    encourage you to actually pause the
  • 00:17:12
    video at this point do these same uh
  • 00:17:15
    computations using 20 and 60 for Xs and
  • 00:17:18
    XT instead uh and pause the video try it
  • 00:17:22
    and then unpause the video and we'll do
  • 00:17:24
    it
  • 00:17:25
    together so finishing
  • 00:17:30
    we'll have 2 * 20 +
  • 00:17:35
    60 plus SF equals
  • 00:17:40
    100 and if we add up these numbers on
  • 00:17:42
    the left hand side that's 100 plus SF
  • 00:17:45
    equals 100 so that tells us that SF
  • 00:17:48
    equals
  • 00:17:49
    zero for
  • 00:17:54
    carpentry we get uh 20 +
  • 00:17:59
    60 + SC = 80 uh 20 + 60 is 80 subtract
  • 00:18:07
    80 from both sides and we get that
  • 00:18:10
    s uh C equals
  • 00:18:13
    z and then our
  • 00:18:18
    demand we'll have
  • 00:18:20
    20 uh plus SD = 40 and so SD
  • 00:18:27
    equal 20
  • 00:18:30
    so interpreting this uh at the point
  • 00:18:33
    2060 where we're making 20 soldiers and
  • 00:18:36
    60 trains we've got no slack in our
  • 00:18:40
    finishing hours we are using all of the
  • 00:18:42
    finishing hours that we have available
  • 00:18:44
    we have no slack in our carpentry hours
  • 00:18:47
    we're using all the carpentry labor that
  • 00:18:50
    we have we have 20 units of slack in our
  • 00:18:53
    demand for for soldiers means that
  • 00:18:56
    there's 20 20 units of UN demand for
  • 00:18:59
    soldiers um which in this case is is
  • 00:19:02
    perfectly fine but we have some slack in
  • 00:19:05
    that constraint um constraints with
  • 00:19:08
    positive amounts of slack actually don't
  • 00:19:10
    affect the optimal Solution that's uh
  • 00:19:12
    this constraint over here and we can
  • 00:19:14
    notice that the point 2060 is not on
  • 00:19:17
    that constraint and so we're going to
  • 00:19:18
    have a positive amount of uh slack for
  • 00:19:21
    that uh the slack variable that
  • 00:19:24
    corresponds to that
  • 00:19:26
    constraint okay let's do one last
  • 00:19:30
    example uh let's choose this point over
  • 00:19:34
    here
  • 00:19:35
    4040 um now you'll notice 4040 is
  • 00:19:38
    actually outside of our feasible region
  • 00:19:45
    now and so if we look at
  • 00:19:49
    finishing again I encourage you to pause
  • 00:19:52
    and try it
  • 00:19:53
    yourself uh we'll have 2 *
  • 00:19:57
    40 plus
  • 00:20:01
    40 plus SF =
  • 00:20:06
    100 and that will give us 2 * 40 is 80 +
  • 00:20:09
    40 is 120 if we subtract 120 from both
  • 00:20:13
    sides that gives us that SF equals
  • 00:20:19
    -20 okay and then
  • 00:20:24
    carpentry we'll have uh 40 + 40 + SC =
  • 00:20:34
    80 uh 40 + 40 is 80 I subtract 80 from
  • 00:20:38
    both sides of that equation and we'll
  • 00:20:40
    get SC equals 0 and then
  • 00:20:46
    demand we'll have 40 + S D equals 40
  • 00:20:53
    subtracting 40 from both sides and we'll
  • 00:20:56
    get that SD equal
  • 00:20:59
    Z okay so the point 4040 is on the
  • 00:21:03
    constraints for demand and carpentry
  • 00:21:06
    it's on the boundaries of those two
  • 00:21:07
    constraints but it's on the wrong side
  • 00:21:10
    of the finishing constraint and so this
  • 00:21:11
    is outside the feasible region because
  • 00:21:13
    we've got one of our slack variables
  • 00:21:16
    with a negative
  • 00:21:18
    value okay and that's really the
  • 00:21:20
    powerful thing about uh these slack
  • 00:21:23
    variables uh two things is one they
  • 00:21:26
    change our inequalities into equality
  • 00:21:29
    when we're doing the linear algebra um
  • 00:21:31
    linear algebra is much more much nicer
  • 00:21:33
    with equalities rather than inequalities
  • 00:21:36
    so first off we can kind of manipulate
  • 00:21:38
    these with matrices which would which is
  • 00:21:40
    what we'll do a little later on the down
  • 00:21:43
    the line and of course computers love
  • 00:21:45
    thinking in terms of matrices okay so
  • 00:21:48
    equalities much nicer than inequalities
  • 00:21:50
    the other thing is that these slack
  • 00:21:52
    variables encode which side of the
  • 00:21:55
    constraint we're on if the slack
  • 00:21:57
    variable con corresponding to a variable
  • 00:22:00
    is positive we're on the right side of
  • 00:22:02
    the constraint and away from the
  • 00:22:04
    constraint if the slack variable is zero
  • 00:22:06
    we're on the boundary of that constraint
  • 00:22:09
    that con that resource whatever it is is
  • 00:22:11
    actually limiting our production um if
  • 00:22:14
    we're have a slack variable that's
  • 00:22:16
    negative then we're on the wrong side of
  • 00:22:18
    the constraint um
  • 00:22:21
    so that essentially sums
  • 00:22:24
    up uh this idea of augmented form and
  • 00:22:28
    inter introducing slack variables it's a
  • 00:22:30
    pretty powerful idea uh when we get into
  • 00:22:33
    the Simplex
  • 00:22:34
    method so that's it for this video uh
  • 00:22:38
    catch you in the next one
标签
  • Simplex-metode
  • Slack-variabler
  • Lineære programmer
  • Gepetto-problem
  • Augmented form