Augmented Form Example

00:08:16
https://www.youtube.com/watch?v=rcGrYJYONEc

概要

TLDRThis video tutorial covers the transition from a non-standard problem in linear programming to an augmented form. It focuses on the challenges faced when variable constraints don't fit the typical assumptions required by linear programming solvers, such as the simplex method, where all variables need to be non-negative. The instructor explains two primary techniques for altering variable constraints to meet these requirements:\ 1. Handling variables constrained to be non-positive by introducing their 'negative twin', thereby converting the constraint to a non-negativity condition.\ 2. Dealing with unrestricted (free) variables by splitting them into two non-negative components, X Plus and X Minus, ensuring the overall problem conditions are met. Additionally, slack variables are introduced to transform inequality constraints into equalities, maintaining the form required for augmented models. The video provides detailed steps to manipulate a given example, demonstrating how to redefine constraints and add slack variables to achieve the required standard, augmented form.

収穫

  • 🔀 Convert non-standard problems to augmented forms in linear programming.
  • ➕ Use 'negative twin' technique for non-positive variables.
  • 🔄 Split free variables into \( X^+ \) and \( X^- \) for non-negativity.
  • 🤖 Simplex method assumes non-negative variables for computation.
  • 📚 Slack variables are added to inequalities to form equalities.
  • 🔍 Substitution in constraints requires careful handling of operations.
  • 🔢 Replacing constraints involves redefining variables to fit non-negative conditions.
  • 📈 Augmented form standardizes constraints as equalities.
  • ⚙️ Employing new variables maintains the original problem equivalency.
  • 📝 Variable naming affects clarity and distinction in problem-solving.

タイムライン

  • 00:00:00 - 00:08:16

    In this video, the speaker demonstrates converting an arbitrary problem into augmented form, explaining two tricks for handling variables that don't fit typical constraints. The first trick is flipping variables constrained to be non-positive by using their negative counterparts, ensuring they are non-negative. The second trick addresses unrestricted or free variables by replacing them with two new variables, X Plus and X Minus, which cover positive and negative values respectively, maintaining non-negativity for both. The speaker explains how these adjustments work harmoniously with linear programming methods, ensuring that only one of the two new variables will be nonzero. By introducing slack variables, the speaker shows how constraints can be modified to become equality constraints. This transforms the original constraints into a system where all constraints are equalities, and all variables are non-negative.

マインドマップ

Mind Map

よくある質問

  • What is the purpose of using negative variables in linear programming?

    Using negative variables helps to adjust constraints and ensure non-negativity of variables, which is required for certain problem-solving methods like the Simplex method.

  • How do you handle a variable that is unconstrained or free in linear programming?

    For unconstrained variables, the technique involves using two variables, X Plus and X Minus, to represent any real number. Both are constrained to be non-negative.

  • What is a slack variable?

    A slack variable is added to an inequality constraint to transform it into an equality constraint, effectively capturing the unused capacity of a limit.

  • How are slack variables named in this video?

    The video uses the letter 'S' followed by a number to denote slack variables, instead of additional X variables.

  • What do X Plus and X Minus represent in linear programming?

    X Plus represents the positive part and X Minus represents the negative part of an original variable that is free or unconstrained.

  • Why is it important for variables to be non-negative in linear programming?

    Non-negativity of variables is an assumption of the simplex method and other solvers, required for proper problem-solving.

ビデオをもっと見る

AIを活用したYouTubeの無料動画要約に即アクセス！
字幕
en
オートスクロール:
  • 00:00:02
    okay for this video I want to do an
  • 00:00:04
    example
  • 00:00:07
    of turning an arbitrary problem into a
  • 00:00:12
    uh into augmented form and so we've got
  • 00:00:14
    a problem here it's not even in standard
  • 00:00:17
    form um and it's got some extra weird
  • 00:00:20
    things going on and so I want to
  • 00:00:22
    introduce two tricks um and then also um
  • 00:00:26
    show you how to turn this into augmented
  • 00:00:27
    form so most of the time when we're
  • 00:00:30
    dealing with standard and augmented form
  • 00:00:34
    our variables are constrained to be non-
  • 00:00:36
    negative most actual solvers sort of
  • 00:00:40
    assume that we've got um zero is the
  • 00:00:43
    lower Bound for all of our variables
  • 00:00:46
    um and and the way we'll run Simplex
  • 00:00:49
    method will'll assume that we have zero
  • 00:00:51
    as the lower Bound for our variables um
  • 00:00:53
    if that's not the case then we need to
  • 00:00:56
    do something and so uh here's the trick
  • 00:00:58
    uh there's two potential ways that that
  • 00:01:00
    could go wrong one is if we get a a
  • 00:01:04
    variable that's constrained to be
  • 00:01:05
    nonpositive less than or equal zero uh
  • 00:01:08
    then we can essentially flip the
  • 00:01:10
    variable by introducing by replacing
  • 00:01:13
    that variable with its negative twin if
  • 00:01:16
    you want to think of it that way and
  • 00:01:18
    it's negative twin will then always be
  • 00:01:21
    uh greater than or equal to zero okay um
  • 00:01:25
    the other thing that we could end up
  • 00:01:27
    with is having a variable that is
  • 00:01:29
    unrestrict restricted or a free variable
  • 00:01:31
    where it has no lower bound and no upper
  • 00:01:34
    bound uh if that's the case uh we use
  • 00:01:37
    this special trick where we replace the
  • 00:01:40
    variable with X Plus and x minus um X
  • 00:01:45
    Plus is going to hold the positive
  • 00:01:47
    amount of that variable uh assuming the
  • 00:01:49
    variable is positive and x minus will
  • 00:01:51
    hold the negative amount of that
  • 00:01:53
    variable uh if that variable ends up
  • 00:01:55
    being negative um both X Plus and x
  • 00:01:58
    minus and are con strained to be
  • 00:02:00
    positive um you'd think that there's
  • 00:02:02
    maybe some kind of uh ill definedness to
  • 00:02:07
    to this procedure because um for example
  • 00:02:11
    if if you wanted XJ to be five you could
  • 00:02:15
    have uh X plus uh to be five and x minus
  • 00:02:19
    to be zero or you could have X Plus to
  • 00:02:21
    be 10 and x minus to be five um sort of
  • 00:02:24
    thing um but due to how LPS are solved
  • 00:02:29
    uh only only one of those two variables
  • 00:02:31
    will be
  • 00:02:32
    nonzero and the other one will always be
  • 00:02:35
    zero and
  • 00:02:36
    so it it it's kind of a weird thing to
  • 00:02:39
    do but uh it turns out to work in the
  • 00:02:42
    case of linear programs even though we
  • 00:02:45
    sort of have an X Plus and an x
  • 00:02:48
    minus okay so using these two tricks as
  • 00:02:52
    well as the other uh kind of ways of
  • 00:02:55
    introducing slack variables um maybe
  • 00:02:58
    I'll just quick remind us if we have a
  • 00:03:01
    less than or equal to constraint we then
  • 00:03:04
    add a slack variable uh to make it into
  • 00:03:07
    an INE equality constraint if we have a
  • 00:03:09
    greater than or equal to constraint we
  • 00:03:11
    subtract a slack variable to turn it
  • 00:03:14
    into an INE
  • 00:03:16
    equality okay so uh let's go ahead and
  • 00:03:20
    put this problem here in augmented form
  • 00:03:24
    um we don't have to touch the objective
  • 00:03:26
    so we'll leave the objective alone um
  • 00:03:28
    but we will
  • 00:03:30
    modify um each of the three constraints
  • 00:03:33
    um before we get to the two constraints
  • 00:03:35
    that we have here um let's actually look
  • 00:03:38
    at our two variables first off we've got
  • 00:03:41
    X1 which is constrained to be less than
  • 00:03:44
    or equal to zero let's go ahead and
  • 00:03:50
    replace
  • 00:03:52
    X1
  • 00:03:53
    with negative X1 and we'll give it a
  • 00:03:57
    star to kind of denote that it's the
  • 00:04:00
    modified version I guess because it's
  • 00:04:02
    going to be the negative version we
  • 00:04:03
    could put a minus sign on that and then
  • 00:04:06
    X2 is unrestricted and so we'll
  • 00:04:11
    replace X2 with the combo of variables
  • 00:04:16
    X2 + - X2
  • 00:04:20
    minus okay and so let's just do those
  • 00:04:23
    Replacements into these two constraints
  • 00:04:25
    and see what we have so we've got -3 *
  • 00:04:29
    X1 but we're replacing X1 with X1
  • 00:04:35
    Star Plus X2 and we're replacing X2 with
  • 00:04:40
    x2+ - X2
  • 00:04:44
    minus okay and that's going to be uh
  • 00:04:47
    greater than or equal to -2 so we'll
  • 00:04:50
    we'll introduce the slack variables in a
  • 00:04:53
    separate step we'll we'll do this in a
  • 00:04:54
    couple
  • 00:04:56
    steps now let's take the second
  • 00:04:58
    constraint which is 2X 1 2 * we're
  • 00:05:02
    replacing X1 with negative X1
  • 00:05:07
    star and then we have plus 5x2 so five
  • 00:05:11
    times and always put in parentheses what
  • 00:05:14
    when you're doing this
  • 00:05:15
    substitution um X2 + - X2
  • 00:05:20
    minus I'll put the these ones in
  • 00:05:23
    parentheses up here as well and that's
  • 00:05:25
    going to be less than or equal to
  • 00:05:28
    one and that's with now we've got the
  • 00:05:31
    variables X1 star x2+ and X2 minus and
  • 00:05:37
    all of those are constrained to be
  • 00:05:39
    greater than or equal to
  • 00:05:42
    zero Okay so we've dealt with our
  • 00:05:46
    variables uh having sort of weird bounds
  • 00:05:48
    to them now let's go ahead and introduce
  • 00:05:52
    our slack variables in order to um
  • 00:05:55
    essentially turn these inequalities into
  • 00:05:58
    equalities
  • 00:06:01
    so uh I'll take this one and bring it
  • 00:06:04
    down
  • 00:06:05
    here so I'll
  • 00:06:08
    have3 uh I guess times negative X1 star
  • 00:06:11
    will give us positive3 X1 star um plus
  • 00:06:15
    X2 + - X2 minus and then we've got a
  • 00:06:20
    greater than or equal to I'm going to
  • 00:06:22
    replace my greater than or equal to with
  • 00:06:24
    a minus and since it's the first slack
  • 00:06:27
    variable I'll call it S1
  • 00:06:30
    um your book tends to just add X3 and X4
  • 00:06:33
    and X5 I like giving my slack variables
  • 00:06:36
    a different name and denoting them with
  • 00:06:38
    an S so that's my first slack variable
  • 00:06:42
    and then it's going to be equal
  • 00:06:43
    to
  • 00:06:46
    -2 uh let's do the next
  • 00:06:51
    constraint uh so 2 * X1 star is going to
  • 00:06:54
    be -2 X1
  • 00:06:57
    star + 5 5 X2 + -
  • 00:07:03
    5x2 minus uh now we got a less than or
  • 00:07:07
    equal to constraint so we'll do plus we
  • 00:07:09
    need to introduce a different slack
  • 00:07:11
    variable and so we'll call this one
  • 00:07:13
    S2 uh and that'll then change our
  • 00:07:16
    inequality into an equality and our
  • 00:07:18
    right hand side is
  • 00:07:21
    one okay and so if I wanted this uh this
  • 00:07:25
    problem in augmented form uh uh these
  • 00:07:30
    would be my constraints in augmented
  • 00:07:34
    form notice that my constraints are all
  • 00:07:36
    equality constraints and uh I've got
  • 00:07:39
    non- negativity for all of my new
  • 00:07:42
    variables so this problem is equivalent
  • 00:07:46
    to the original problem um we're sort of
  • 00:07:48
    having to use three variables to to do
  • 00:07:51
    it um but it gives us an equivalent
  • 00:07:54
    problem actually we're using five
  • 00:07:55
    variables right because now we've got um
  • 00:07:58
    in addition to the these ones here we've
  • 00:08:00
    also got S1 and S2 are now two new
  • 00:08:05
    variables and they're Al both they're
  • 00:08:07
    also both non-
  • 00:08:11
    negative so that's it for this video see
  • 00:08:13
    you in the next one
タグ
  • linear programming
  • augmented form
  • standard form
  • slack variables
  • simplex method
  • non-negative variables
  • negative twin
  • unrestricted variables