ART TEACHES MATHEMATICS IN THE MODERN WORLD: LESSON 5 SIMPLEX ALGORITHM/METHOD (PART I)

01:10:47
https://www.youtube.com/watch?v=m2LRVEkEfLs

Sintesi

TLDRThis mathematics class discusses solving maximization problems using the simplex method, particularly for linear programming with multiple decision variables. The simplex method, developed by George B. Dantzig, offers an advantage over the graphical method, which can only handle two variables. The focus is on modifying the linear program to prepare it for the simplex tableau, including using slack variables to convert inequalities to equalities. The initial simplex tableau is explained, along with the initial solution method where decision variables start at zero, reflecting all resources as unused. The lesson intends to extend in future discussions to optimizing and finding non-zero values for decision variables, moving towards solving the problem completely.

Punti di forza

  • 📘 Introduction to the simplex method for linear programming.
  • 📊 Simplex method handles any number of decision variables.
  • ➕ Use of slack variables to convert inequalities to equalities.
  • 🔍 Initial solution starts with all decision variables at zero.
  • 🖋 George B. Dantzig's contribution with the simplex method.
  • 👨‍🏫 Explanation of a simplex tableau structure.
  • 🔄 Differences between graphical and simplex method outlined.
  • 🔢 Step-by-step guide to setting up the initial simplex tableau.
  • 📝 Modify objective functions and constraints for simplex.
  • 🤖 Mention of computerized solutions for more efficient calculations.

Linea temporale

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

    The instructor introduces the simplex method as a solution for linear programming maximization problems with less than or equal to constraints, contrasting it with the graphical method's limitations. He notes the complexity of manual calculation while suggesting computer programs to simplify the process.

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

    To use the simplex method, constraints with less than or equal to signs are modified by adding slack variables to turn them into equalities. Two examples, s1 and s2, are introduced, and modified constraints are explained.

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

    The objective function is adjusted by adding slack variables with zero coefficients. This maintains the representation of original decision variables and additional slack variables. The instructor explains how slack variables reflect unused resources and impact the initial solution.

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

    Initial setup for simplex tableau is detailed, noting the number of columns and rows depends on variables and constraints. The first row in the tableau represents coefficients, while the basis and solution columns form the core framework of the solution.

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

    Each variable in the objective function is listed in a second row, with their coefficients placed above them. The concept of slack variables and non-negativity constraints is incorporated into the tableau to maintain the validity of solutions.

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

    Constructing the simplex tableau continues with determining the basis column, which includes slack variables due to their specific column characteristics, while coefficients of these variables in equations mark their C_J values. The tableau setup shows the equations for these variables.

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

    Determining Z_J and C_J - Z_J rows in the tableau involves calculations based on the multiplication of specific columns and row values. The first simplex tableau complete, and its initial solution is introduced, correlating slack variables to resource availability.

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

    The initial solution specifies which variables (s1 and s2) have non-zero values, representing unused resources. Decision variables a and b start at zero since no production occurs initially, reflecting a scenario before manufacturing starts, according to the initial tableau setup.

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

    The simplex tableau shows a value of zero for the objective function indicating no activity initially, paralleling concepts in graphical methods where such an initial point is not emphasized. The focus shifts to optimizing via simplex method for subsequent steps.

  • 00:45:00 - 00:50:00

    A summary of initial simplex tableau implications follows. With no initial production, the resources remain unused, marking s1 and s2 as the active variables. The challenge will be progressing beyond this point to reach an optimal solution in later tableaux.

  • 00:50:00 - 00:55:00

    Upcoming lessons will continue solving the linear program using subsequent tableau iterations, projecting improvements over initial solutions. The instructor hints at identifying more active decision variables in future steps and the adjustment of slack variables.

  • 00:55:00 - 01:00:00

    The instructor mentions more technical aspects of setting the objective function and detecting maximum values for next discussions. These involve the evolution of active variables and criteria for achieving the optimal solution using simplex method.

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

    Students are encouraged to engage via comments for uncertainties about the current lesson, as the instructor wraps up this session and suggests the content of future classes to further explore and advance in simplex method applications.

  • 01:05:00 - 01:10:47

    The session concludes with reminders to students to subscribe and stay engaged for ongoing educational content, followed by unrelated background music.

Mostra di più

Mappa mentale

Mind Map

Domande frequenti

  • What is the simplex method used for?

    The simplex method is used for solving linear programming problems involving maximization by handling any number of decision variables, unlike the graphical method which only works with two.

  • What are the common constraints in simplex method problems?

    Simplex method problems usually involve constraints with less than or equal inequality signs, including explicit and implicit constraints such as non-negativity constraints.

  • Who developed the simplex method?

    The simplex method was devised by George B. Dantzig.

  • What is the initial solution in simplex method?

    The initial solution corresponds to an initial simplex tableau where all decision variables are zero, representing unused resources and a zero value for the objective function.

  • How are slack variables used in the simplex method?

    Slack variables are added to convert inequalities into equalities which helps in the calculation and provides a means to track unused resources.

Visualizza altre sintesi video

Ottenete l'accesso immediato ai riassunti gratuiti dei video di YouTube grazie all'intelligenza artificiale!
Sottotitoli
en
Scorrimento automatico:
  • 00:00:01
    [Music]
  • 00:00:17
    hi
  • 00:00:17
    welcome back to my class in mathematics
  • 00:00:20
    in the modern world
  • 00:00:22
    for today we will take a
  • 00:00:25
    simplex method for solving maximization
  • 00:00:29
    problem
  • 00:00:30
    where the explicit con constraints
  • 00:00:34
    all the explicit constraints involve
  • 00:00:38
    less than or equal to inequality sign
  • 00:00:42
    the advantage of the simplex method over
  • 00:00:46
    the graphical method is that the simplex
  • 00:00:49
    method can be used to solve
  • 00:00:52
    a linear program with any number of
  • 00:00:56
    decision variables
  • 00:00:58
    whereas the graphical method is
  • 00:01:03
    can be used only or is limited to
  • 00:01:06
    solving limited uh sorry is limited to
  • 00:01:09
    solving
  • 00:01:10
    linear programming problem with
  • 00:01:14
    two decision variables or linear
  • 00:01:17
    programming problems that involve
  • 00:01:18
    two decision variables but the graphical
  • 00:01:22
    sorry the simplex method is a
  • 00:01:24
    generalized technique
  • 00:01:27
    devised by german mathematician
  • 00:01:30
    george b danzig that can be used
  • 00:01:33
    to solve linear program with
  • 00:01:36
    any number or unlimited number of
  • 00:01:39
    decision variables
  • 00:01:41
    however when you solve a linear program
  • 00:01:45
    by
  • 00:01:47
    simplex method manually
  • 00:01:50
    the solution can be tedious
  • 00:01:54
    and lengthy but there is
  • 00:01:57
    a program which you can download
  • 00:02:01
    from the internet program for the
  • 00:02:04
    simplex algorithm
  • 00:02:06
    or simplex method wherein you will just
  • 00:02:09
    enter the number of decision variables
  • 00:02:14
    the objective function the coefficients
  • 00:02:18
    of the decision variables in the
  • 00:02:20
    objective function
  • 00:02:22
    as well as in the constraints and the
  • 00:02:25
    inequality symbol
  • 00:02:27
    and in a matter of seconds the you will
  • 00:02:30
    have the solution
  • 00:02:32
    but for our lesson we will solve
  • 00:02:36
    a linear program manually
  • 00:02:40
    and i will solve one of the
  • 00:02:44
    examples we had in
  • 00:02:47
    for graphical method and we will solve
  • 00:02:51
    this example
  • 00:02:52
    by simplex method consider
  • 00:02:56
    the following example
  • 00:03:00
    this is a maximization problem linear
  • 00:03:02
    program for maximization problem
  • 00:03:06
    the objective is maximize c equals 6a
  • 00:03:09
    plus 70. our objective is to find the
  • 00:03:14
    maximum value of c
  • 00:03:16
    and to find the maximum value of c is to
  • 00:03:19
    find the values
  • 00:03:20
    of a and b that will give the maximum
  • 00:03:24
    value
  • 00:03:24
    of the objective function c defined by
  • 00:03:27
    this
  • 00:03:29
    linear function
  • 00:03:33
    the variables a and b are known as the
  • 00:03:35
    decision variables
  • 00:03:38
    and we find the values of the decision
  • 00:03:41
    variables a and b
  • 00:03:42
    that will give the maximum value of c
  • 00:03:45
    subject to st subject to
  • 00:03:49
    the following constraints for our first
  • 00:03:52
    example
  • 00:03:54
    install the linear program using the
  • 00:03:56
    simplex method
  • 00:03:59
    we will have this example in which we
  • 00:04:01
    will have this linear program
  • 00:04:03
    in which all the explicit constraints
  • 00:04:06
    involve less than or equal to question
  • 00:04:11
    and these first two constraints are
  • 00:04:14
    known as the
  • 00:04:14
    explicit constraints we have 9a plus 5b
  • 00:04:19
    less than equal to 45.
  • 00:04:22
    the second explicit constraint
  • 00:04:26
    we have 7a plus and b less than equal to
  • 00:04:29
    70.
  • 00:04:31
    and this last constraint
  • 00:04:34
    is known as the implicit constraint
  • 00:04:37
    or non-negativity constraints
  • 00:04:41
    in which we require all the decision
  • 00:04:43
    variables
  • 00:04:46
    to be greater than or equal to zero that
  • 00:04:48
    means the values of the variables in
  • 00:04:50
    linear programming
  • 00:04:52
    should be positive or zero or
  • 00:04:55
    non-negative
  • 00:04:58
    now the first step in the simplex method
  • 00:05:01
    or
  • 00:05:02
    simplex algorithm is to modify
  • 00:05:05
    the linear program to modify
  • 00:05:10
    the linear program is to remove
  • 00:05:14
    all the inequality inequality science
  • 00:05:18
    and to prepare the the linear program
  • 00:05:22
    for the simplex w
  • 00:05:25
    and a simplex w is a table
  • 00:05:29
    that we use as a device in the
  • 00:05:32
    solution of linear program by
  • 00:05:36
    simplex algorithm or simplex method
  • 00:05:40
    now to modify a
  • 00:05:43
    less than equal to
  • 00:05:46
    explicit constraint we add a slab
  • 00:05:50
    variable slump variable is tell
  • 00:05:55
    s l a c k
  • 00:05:58
    variable
  • 00:06:04
    slab
  • 00:06:10
    variable
  • 00:06:14
    to modify a less than equal to
  • 00:06:18
    explicit constraint we add a slack
  • 00:06:21
    variable to the
  • 00:06:25
    explicit cons constraint that contains
  • 00:06:29
    less than equal to constraint uh sorry
  • 00:06:32
    less than equal to
  • 00:06:32
    inequality and we add one slack variable
  • 00:06:36
    to each less than equal to
  • 00:06:38
    constraint since our linear program has
  • 00:06:43
    two less than equal to constraints
  • 00:06:46
    we will use two slab variables
  • 00:06:50
    to modify these less than equal to
  • 00:06:54
    constraint
  • 00:06:55
    we add one slack variable to the first
  • 00:06:58
    less than equals to constraint
  • 00:07:00
    and we denote the first log variable
  • 00:07:03
    by s sub one
  • 00:07:09
    for the second less than equal to
  • 00:07:13
    explicit constraint we add another is
  • 00:07:16
    not variable
  • 00:07:18
    and to differentiate the second slot
  • 00:07:21
    variable
  • 00:07:21
    from the first we use a subscript two
  • 00:07:27
    for the second less than equal to
  • 00:07:29
    constraint we add a
  • 00:07:30
    second slack variable denoted by
  • 00:07:34
    s sub 2.
  • 00:07:41
    now we will add the
  • 00:07:46
    snap variable to the left-hand side
  • 00:07:50
    of this inequality
  • 00:07:54
    constraint less than equal to constraint
  • 00:07:57
    and after adding the slack variable with
  • 00:08:00
    coefficient of 1
  • 00:08:03
    we remove the inequality sign
  • 00:08:07
    we only retain the
  • 00:08:11
    equal to sign
  • 00:08:18
    okay we modify the first less than equal
  • 00:08:21
    to constraint
  • 00:08:22
    by adding the first slap variable
  • 00:08:27
    s1 with coefficient of positive one
  • 00:08:30
    to the left-hand side and after the
  • 00:08:33
    addition of this
  • 00:08:34
    slack variable we remove the
  • 00:08:37
    less than sign
  • 00:08:41
    we only retain the equal sign
  • 00:08:44
    hence the modified first explicit
  • 00:08:47
    constraint will be
  • 00:08:52
    9a
  • 00:08:56
    plus 5b
  • 00:09:03
    plus now we add the first slack variable
  • 00:09:06
    s1
  • 00:09:09
    it's understood the coefficient of s1 is
  • 00:09:12
    1
  • 00:09:13
    and we remove the inequality sign
  • 00:09:17
    we simply write equals
  • 00:09:20
    45.
  • 00:09:26
    okay then i equals
  • 00:09:34
    45
  • 00:09:36
    we all we now modify the second less
  • 00:09:39
    than equal to constraint by addition of
  • 00:09:41
    the second
  • 00:09:42
    slap variable as 2 with coefficient of
  • 00:09:45
    positive 1
  • 00:09:47
    to the left-hand side and we remove the
  • 00:09:50
    inequality sign less than and we write
  • 00:09:53
    equals 70.
  • 00:09:55
    we do that 7a
  • 00:10:03
    plus 10 b
  • 00:10:09
    now we add the second slap variable
  • 00:10:12
    s2 plus
  • 00:10:16
    s2 we remove
  • 00:10:19
    the less than sign we retain equals
  • 00:10:22
    equals
  • 00:10:24
    70.
  • 00:10:30
    now we also
  • 00:10:34
    modify the objective function
  • 00:10:38
    after modifying the explicit constraints
  • 00:10:40
    we now have
  • 00:10:42
    four variables one
  • 00:10:46
    a b s one
  • 00:10:49
    s two and that's four variables
  • 00:10:52
    of which the original variables
  • 00:10:55
    a and b are called decision variables
  • 00:10:59
    and the variables that we have added to
  • 00:11:01
    modify the
  • 00:11:02
    less than equal to constraints s1 and s2
  • 00:11:06
    are known as slab variables
  • 00:11:10
    we also modify the objective function
  • 00:11:15
    we write maxine maximizing
  • 00:11:26
    equals six a
  • 00:11:32
    plus seventy
  • 00:11:38
    now the slack variables are added to the
  • 00:11:41
    objective function
  • 00:11:43
    and each with coefficient of zero
  • 00:11:48
    we have added s1 in the first less than
  • 00:11:51
    equal to constraint
  • 00:11:53
    and we added s1 with coefficient of one
  • 00:11:57
    we also add s1 to the objective function
  • 00:12:00
    but with coefficient
  • 00:12:02
    of zero plus
  • 00:12:06
    zero s1
  • 00:12:09
    and we also add the second slot variable
  • 00:12:12
    s2 which we have added to the
  • 00:12:16
    second less than equal to explicit
  • 00:12:19
    constraint
  • 00:12:20
    to the objective function with
  • 00:12:22
    coefficient
  • 00:12:23
    of zero we write plus
  • 00:12:26
    zero st
  • 00:12:34
    again to modify a less than equal to
  • 00:12:37
    cost string
  • 00:12:39
    before constructing the
  • 00:12:43
    simplest w we
  • 00:12:49
    add a stock variable one
  • 00:12:52
    is locked variable to each less than
  • 00:12:55
    equal to
  • 00:12:56
    constraint for less than equal to
  • 00:12:59
    constraint
  • 00:13:00
    we add a slack variable
  • 00:13:03
    with coefficient of one
  • 00:13:07
    and you add one
  • 00:13:10
    slack variable to the left side
  • 00:13:14
    left-hand side of the less than equal to
  • 00:13:17
    constraint
  • 00:13:18
    for each less than equal to constraint
  • 00:13:21
    and you add
  • 00:13:22
    to modify the objective function you add
  • 00:13:26
    the same
  • 00:13:26
    slack variable with coefficient of zero
  • 00:13:31
    like in this example we added s1
  • 00:13:36
    to the left side of this less than equal
  • 00:13:39
    to constraint
  • 00:13:41
    with coefficient of one and we remove
  • 00:13:45
    the less than sign for the second
  • 00:13:48
    less than equal to constraint we add a
  • 00:13:51
    second
  • 00:13:51
    slack variable denoted by s2 the
  • 00:13:54
    subscript to means second
  • 00:13:56
    slack variable and we add s2 to the
  • 00:14:00
    left-hand side
  • 00:14:01
    of the of this less than equal to a
  • 00:14:04
    string
  • 00:14:05
    we write plus s2 we coefficient
  • 00:14:08
    of one and we remove
  • 00:14:11
    the inequality sign less than we simply
  • 00:14:15
    write equals
  • 00:14:16
    70. now
  • 00:14:20
    to modify the objective function we add
  • 00:14:23
    the two is not
  • 00:14:24
    variables but with coefficients of
  • 00:14:28
    zero so we are plus zero s one
  • 00:14:33
    plus we add the second step variable we
  • 00:14:35
    coefficient of zero
  • 00:14:37
    because we have plus zero s3
  • 00:14:44
    now the for maximization
  • 00:14:48
    problems the
  • 00:14:51
    explicit constraints usually
  • 00:14:55
    represent the constraints on
  • 00:14:59
    the availability of scars or
  • 00:15:02
    limited resources and
  • 00:15:07
    for the initial initially in
  • 00:15:10
    a production or a manufacturing
  • 00:15:15
    company before the production
  • 00:15:19
    or manufacturing starts the values of
  • 00:15:23
    the decision variables
  • 00:15:24
    are initially zero that means
  • 00:15:28
    all of the resources are unused
  • 00:15:31
    hence in a linear program
  • 00:15:34
    if all the decision variables a
  • 00:15:38
    and b are zero
  • 00:15:42
    s1 would take the value 45
  • 00:15:47
    and s2 would take the value 70.
  • 00:15:51
    if a and b are 0 initially in a
  • 00:15:54
    production or manufacturer
  • 00:15:57
    thus this means that the first resource
  • 00:16:00
    s1
  • 00:16:01
    45 units the first resource
  • 00:16:04
    is equal to 45 units and everything all
  • 00:16:07
    of the first resource
  • 00:16:08
    is unused and as to will take the value
  • 00:16:12
    70 initially
  • 00:16:14
    or in the initial solution that means
  • 00:16:18
    all of the second resource
  • 00:16:21
    consists of 70 units and all of the
  • 00:16:24
    second resource
  • 00:16:25
    is unused
  • 00:16:29
    now in the objective function the
  • 00:16:31
    coefficients of
  • 00:16:33
    the slack variables are zero
  • 00:16:36
    because if
  • 00:16:40
    our objective is maximization of profit
  • 00:16:44
    the unused resource
  • 00:16:47
    source will not contribute to property
  • 00:16:51
    so that so we multiply these
  • 00:16:54
    values of s1 and s2 representing
  • 00:16:57
    unused resource by zero
  • 00:17:01
    so that they will not contribute to the
  • 00:17:04
    objective function which is a
  • 00:17:07
    profit function punch profit fund
  • 00:17:10
    profit function for a production problem
  • 00:17:14
    where the objective is
  • 00:17:16
    maximization of profit
  • 00:17:20
    now
  • 00:17:23
    for preparing the initial simplex w
  • 00:17:28
    the first table in the simplex
  • 00:17:33
    in the solution for using the simplex
  • 00:17:35
    algorithm
  • 00:17:37
    the all the variables must appear in
  • 00:17:40
    every equation you can see in the first
  • 00:17:44
    equation line
  • 00:17:44
    eight now we have four variables
  • 00:17:48
    a b s one and s two
  • 00:17:52
    and all of these four variables should
  • 00:17:55
    appear
  • 00:17:57
    in each equation in the first equation
  • 00:18:00
    9a plus 5b plus s1 equals 45.
  • 00:18:05
    the variable s2 is missing hence we add
  • 00:18:09
    s2 to the left-hand side of the first
  • 00:18:13
    equation with coefficient
  • 00:18:15
    of zero and that explains why
  • 00:18:19
    i have a space here and that is
  • 00:18:23
    for us to write to add as to
  • 00:18:28
    the coefficient of zero
  • 00:18:34
    now nothing is changed in the first
  • 00:18:36
    equation because zero times
  • 00:18:38
    s2 is zero and we still have the
  • 00:18:41
    original
  • 00:18:42
    equation 9 8 plus 5b plus s1 equals 45
  • 00:18:46
    we simply want every variable
  • 00:18:50
    in the modified linear program to appear
  • 00:18:54
    in each equation now in the second
  • 00:18:57
    equation we have seven a plus five b
  • 00:19:01
    plus has to equal seventy and you can
  • 00:19:04
    see that
  • 00:19:05
    the variable the snap variable s1 is
  • 00:19:08
    missing
  • 00:19:09
    the left-hand side of the second
  • 00:19:12
    equation
  • 00:19:13
    thus we are s1 to the second equation
  • 00:19:18
    we add s1 at the left-hand side of the
  • 00:19:21
    second equation
  • 00:19:22
    with coefficient of zero and
  • 00:19:26
    that explains why we have this space
  • 00:19:29
    here for us to add the variable
  • 00:19:32
    s1 with coefficient
  • 00:19:36
    of zero
  • 00:19:39
    now you can see that all the four
  • 00:19:41
    variables
  • 00:19:43
    appear in each equation now
  • 00:19:47
    just supposing that the second equation
  • 00:19:50
    has no 10b
  • 00:19:54
    it is simply 7a plus s2
  • 00:19:58
    equals 70 but the variable b
  • 00:20:01
    must appear in the second equation
  • 00:20:04
    so what you do is you add the variable b
  • 00:20:09
    with coefficient of zero
  • 00:20:13
    that means whenever a variable is
  • 00:20:15
    missing in
  • 00:20:16
    an equation you add the missing variable
  • 00:20:20
    in the equation with coefficient of zero
  • 00:20:24
    but this is 10d
  • 00:20:30
    now all the variables appear in
  • 00:20:34
    these two equations variables a
  • 00:20:37
    b s one and s two now we also modified
  • 00:20:41
    the implicit constraints
  • 00:20:43
    because we now have four variables
  • 00:20:46
    a b s one s two where a and b
  • 00:20:50
    are the original variables known as
  • 00:20:53
    decision variables
  • 00:20:55
    and s one and s two are the slop
  • 00:20:58
    variables
  • 00:20:59
    all the variables must be
  • 00:21:04
    positive or zero thus we modify the
  • 00:21:07
    implicit constraints
  • 00:21:09
    we write a variable
  • 00:21:12
    a b it's the snack variables
  • 00:21:16
    s1 s2
  • 00:21:20
    should be all positive
  • 00:21:23
    greater than 0 or
  • 00:21:26
    0 and this is the complete
  • 00:21:31
    modified
  • 00:21:35
    linear program
  • 00:21:38
    this is the modified linear program
  • 00:21:42
    and in constructing the first table
  • 00:21:44
    known as
  • 00:21:45
    simplex tableau we will use
  • 00:21:50
    this modified linear program as basis
  • 00:21:56
    now we are ready to construct the first
  • 00:21:59
    table in the solution by simplex
  • 00:22:03
    algorithm or simplex method
  • 00:22:06
    and we call this first table the
  • 00:22:09
    initial simplex w
  • 00:22:14
    a the blue is a paper consisting of
  • 00:22:18
    rows rows
  • 00:22:23
    and columns
  • 00:22:28
    the number of columns
  • 00:22:32
    in a simplex w is equal to
  • 00:22:36
    the number of variables
  • 00:22:40
    plus three
  • 00:22:45
    number of columns
  • 00:22:54
    is equal to number of
  • 00:22:57
    variables
  • 00:23:02
    plus three
  • 00:23:06
    again in a simplex w
  • 00:23:09
    the number of columns
  • 00:23:14
    is equal to the number of variables
  • 00:23:17
    plus three three here is a constant
  • 00:23:21
    it's always plus three in our modified
  • 00:23:26
    linear program
  • 00:23:27
    we now have one two
  • 00:23:31
    three four variables
  • 00:23:34
    two of which are decision variables
  • 00:23:38
    and two of which are
  • 00:23:41
    slack variables since our
  • 00:23:45
    simplest w for this particular linear
  • 00:23:48
    program we have
  • 00:23:52
    number of variables four
  • 00:23:56
    plus a constant three
  • 00:24:01
    is seven seven columns
  • 00:24:07
    and i have constructed seven columns
  • 00:24:11
    one two
  • 00:24:15
    three four
  • 00:24:19
    five six
  • 00:24:22
    and seven column we have seven columns
  • 00:24:26
    in the simplex w now
  • 00:24:30
    the number of rows
  • 00:24:34
    in a simplex w is equal to the number of
  • 00:24:39
    explicit constraints
  • 00:24:43
    or the number of equations
  • 00:24:46
    in the modified linear program
  • 00:24:50
    excluding the objective function
  • 00:24:53
    plus four
  • 00:24:58
    number of rows
  • 00:25:04
    equals number of equations
  • 00:25:15
    plus four
  • 00:25:22
    again in a simplex tableau
  • 00:25:26
    the number of rows
  • 00:25:31
    number of rows equals number of
  • 00:25:34
    equations
  • 00:25:35
    or you count the number of explicit
  • 00:25:38
    constraints
  • 00:25:39
    in the original linear program or the
  • 00:25:42
    number of
  • 00:25:42
    equations in the modified linear program
  • 00:25:46
    excluding the objective function
  • 00:25:50
    plus a constant 4 4 is a constant
  • 00:25:54
    which means it's always plus four
  • 00:25:58
    in our modified linear program we count
  • 00:26:01
    the number of equations
  • 00:26:04
    excluding the objective function
  • 00:26:07
    so this is one equation
  • 00:26:11
    and two we have two equations
  • 00:26:16
    plus say constant four
  • 00:26:20
    equals six six
  • 00:26:24
    rows i have constructed six rows
  • 00:26:30
    this is the first row the second
  • 00:26:34
    the third the fourth
  • 00:26:38
    the fifth row and the
  • 00:26:41
    sixth row thus our simplex w
  • 00:26:47
    has seven columns and six
  • 00:26:50
    rows now
  • 00:26:54
    for the first column we merge
  • 00:26:58
    the first top
  • 00:27:01
    cells we merge this two
  • 00:27:04
    we merge these two cells
  • 00:27:09
    and we call this column the
  • 00:27:12
    c sub j column
  • 00:27:17
    where c sub j and where c
  • 00:27:20
    stands for coefficient
  • 00:27:24
    in the second column
  • 00:27:27
    we also merge the first
  • 00:27:30
    top cells we merge these two cells
  • 00:27:37
    and we call this the basis column
  • 00:27:46
    basis the first column is the
  • 00:27:50
    c sub j column where c stands for
  • 00:27:52
    coefficient
  • 00:27:54
    the second column is known as the basis
  • 00:27:56
    column
  • 00:27:58
    and it's called the basis column because
  • 00:28:02
    uh the solution uh
  • 00:28:06
    for each the solution that corresponds
  • 00:28:09
    for
  • 00:28:09
    each simplex tabloon is based on the
  • 00:28:13
    variables
  • 00:28:14
    that will appear in the basis column
  • 00:28:17
    or the basis column as well as the last
  • 00:28:21
    column
  • 00:28:22
    form the basis for our solution for the
  • 00:28:25
    solution corresponding for
  • 00:28:27
    each simplex w
  • 00:28:31
    now look at the last column
  • 00:28:34
    we also merge the first step to cells
  • 00:28:39
    and we we call it
  • 00:28:42
    we denote it by s
  • 00:28:45
    merge these two top cells in the last
  • 00:28:48
    column
  • 00:28:54
    and denote the last column by capital
  • 00:28:58
    s capital s stands for solution
  • 00:29:02
    which means that the values
  • 00:29:05
    of the variables in the solution
  • 00:29:08
    corresponding for a simplex w
  • 00:29:11
    will appear in the solution column
  • 00:29:15
    or s column and the variables
  • 00:29:18
    in the solution for each simplex tableau
  • 00:29:22
    will appear in the basis column
  • 00:29:26
    and the variable that appears the value
  • 00:29:29
    of the variable
  • 00:29:30
    that appears in the basis column
  • 00:29:34
    is the corresponding value in the
  • 00:29:38
    solution calling or s calling
  • 00:29:44
    now in the second row
  • 00:29:47
    is the first row is the second row
  • 00:29:53
    we write the variables in the modified
  • 00:29:58
    linear program we write the variables
  • 00:30:01
    that appear in the objective function
  • 00:30:03
    the variables are a b
  • 00:30:07
    s1 and s3
  • 00:30:10
    we write a
  • 00:30:13
    b
  • 00:30:18
    s1 and s2
  • 00:30:24
    again in the second row
  • 00:30:28
    from the top of the simplest w
  • 00:30:31
    you will write the variables
  • 00:30:35
    in the order that they appear in the
  • 00:30:38
    objective function
  • 00:30:40
    the variables are a b s one
  • 00:30:43
    s two you write this variables
  • 00:30:47
    in this order in the second row
  • 00:30:51
    of the simplex w
  • 00:30:56
    now at the top most row
  • 00:30:59
    or the first row of the simplest w
  • 00:31:04
    we write the coefficients
  • 00:31:07
    that's why we have c is the c's of j
  • 00:31:10
    column and that's the c sub j row
  • 00:31:14
    again in the top most row or first row
  • 00:31:18
    of the simplex w you write the
  • 00:31:20
    coefficients
  • 00:31:22
    of the variables in the second row
  • 00:31:26
    the coefficients of these variables in
  • 00:31:28
    the objective function
  • 00:31:30
    the coefficient of a in the objective
  • 00:31:34
    function
  • 00:31:34
    is 6. we write 6
  • 00:31:38
    above a
  • 00:31:43
    the coefficient of b in the objective
  • 00:31:46
    function
  • 00:31:46
    a7 we write 7
  • 00:31:50
    in this cell above b
  • 00:31:56
    the coefficient of s1 in the objective
  • 00:32:00
    function is 0
  • 00:32:03
    we write 0 in this cell above s1
  • 00:32:10
    the coefficient of s2
  • 00:32:14
    in the objective function is 0
  • 00:32:17
    and we write 0 in this cell
  • 00:32:20
    above s2
  • 00:32:28
    now in the cells
  • 00:32:32
    below this now we call these
  • 00:32:36
    columns the variable columns
  • 00:32:41
    these columns these columns contain the
  • 00:32:45
    variables
  • 00:32:47
    and in the cells below this
  • 00:32:51
    a variables a b s one s two we write the
  • 00:32:55
    coefficients of these variables
  • 00:32:58
    in the explicit constraints
  • 00:33:01
    in the modified explicit constraints
  • 00:33:05
    okay we start with the first modified
  • 00:33:08
    explicit constraint the coefficient
  • 00:33:12
    of a in the first equation or the first
  • 00:33:15
    modified
  • 00:33:16
    explicit constraint is 9
  • 00:33:20
    and we write 9 below a in this cell
  • 00:33:27
    the coefficient of b in the
  • 00:33:30
    first modified
  • 00:33:34
    explicit constraint is
  • 00:33:37
    and we write 5 below b
  • 00:33:44
    the coefficient of the first left
  • 00:33:47
    variable s1
  • 00:33:48
    in the first equation or the first
  • 00:33:52
    modified explicit constraint is
  • 00:33:56
    positive one when a
  • 00:33:58
    [Music]
  • 00:34:01
    when there is no number before the
  • 00:34:04
    variable is understood that
  • 00:34:06
    the coefficient the numerical
  • 00:34:08
    coefficient of that variable
  • 00:34:10
    is one thus the numerical coefficient
  • 00:34:14
    of s1 is one and we write one
  • 00:34:18
    below s1
  • 00:34:24
    and the coefficient of s2 in the first
  • 00:34:29
    equation or the first explicit
  • 00:34:31
    constraint
  • 00:34:32
    coefficient of s2 is zero so we write
  • 00:34:36
    zero below s
  • 00:34:45
    and 45 is known as the constant term
  • 00:34:49
    of equation 1 because
  • 00:34:53
    45 is not multiplied by any variable
  • 00:34:56
    it's just a constant 45. now this 45 we
  • 00:35:00
    write
  • 00:35:00
    in the s column or solution column
  • 00:35:06
    immediately before capital s we write 45
  • 00:35:10
    we know as
  • 00:35:16
    now in we now consider the second
  • 00:35:19
    equation
  • 00:35:20
    or the second modified explicit
  • 00:35:24
    constraint
  • 00:35:26
    the coefficient of a in the
  • 00:35:29
    second equation is seven
  • 00:35:33
    and we write seven
  • 00:35:36
    below nine
  • 00:35:42
    the coefficient of the second decision
  • 00:35:46
    variable
  • 00:35:46
    b in the second equation or the second
  • 00:35:50
    modifying
  • 00:35:51
    explicit constraint is 10
  • 00:35:56
    and and we write 10 below
  • 00:36:00
    5
  • 00:36:04
    this means that 10 is the coefficient of
  • 00:36:08
    the variable b the second variable the
  • 00:36:11
    second decision variable b
  • 00:36:13
    in the second equation or in the
  • 00:36:16
    second modified explicit constraint
  • 00:36:22
    the coefficient of s1 the first snap
  • 00:36:25
    variable
  • 00:36:26
    in the second equation or
  • 00:36:30
    second modified explicit constraint
  • 00:36:34
    is zero and we write
  • 00:36:38
    zero below one
  • 00:36:46
    the coefficient of the second is left
  • 00:36:49
    variable
  • 00:36:50
    s2 in the second equation
  • 00:36:54
    or the second explicit constraint
  • 00:36:58
    is one again when
  • 00:37:01
    there is no number before the variable
  • 00:37:04
    it's understood that the numerical
  • 00:37:07
    coefficient
  • 00:37:08
    of that variable is one thus
  • 00:37:12
    the coefficient of s2
  • 00:37:15
    in the second equation is one
  • 00:37:19
    and we write one below
  • 00:37:23
    zero
  • 00:37:29
    seventy is the constant term of
  • 00:37:32
    equation two it is a constant term
  • 00:37:36
    because 70
  • 00:37:37
    is not multiplied by any variable
  • 00:37:41
    it is just a constant 70 and we write 17
  • 00:37:46
    below 45 in the simplex w
  • 00:37:50
    we know below 45 we write 70.
  • 00:37:58
    these are the coefficients of the
  • 00:38:01
    variables
  • 00:38:02
    a b s ads1 s2 in the first
  • 00:38:06
    modified explicit constraint and the
  • 00:38:09
    constant term
  • 00:38:10
    of the first equation or the first
  • 00:38:12
    modified
  • 00:38:14
    explicit constraint is 45 7
  • 00:38:19
    0 1 here
  • 00:38:22
    7 and 0
  • 00:38:25
    1 are the coefficients of the volumes
  • 00:38:30
    a b s one s two
  • 00:38:34
    in the second equation or the second
  • 00:38:38
    modified explicit constraint and
  • 00:38:42
    seventy is the constant term
  • 00:38:45
    or the right-hand side of equation two
  • 00:38:48
    or the right-hand side of the second
  • 00:38:50
    modified
  • 00:38:51
    explicit constraint
  • 00:38:57
    now after you are done with all the
  • 00:39:00
    equations
  • 00:39:02
    the next row is denoted by
  • 00:39:05
    z
  • 00:39:09
    z sub j
  • 00:39:13
    and after this row the last row is
  • 00:39:15
    denoted by
  • 00:39:16
    c
  • 00:39:20
    minus z
  • 00:39:26
    again after you have written all the
  • 00:39:29
    coefficients of the
  • 00:39:31
    of all the equations in the modified
  • 00:39:34
    explicit constraints the next row
  • 00:39:37
    is denoted by z
  • 00:39:40
    the last row is denoted by c sub chain
  • 00:39:43
    minus c sub j or the last two rows
  • 00:39:48
    are denoted by z sub j
  • 00:39:51
    second to the last row is denoted by z
  • 00:39:54
    sub j
  • 00:39:56
    and the last row is denoted by
  • 00:39:59
    c sub j minus z
  • 00:40:02
    sub g now the entries
  • 00:40:06
    in the basis column this the entry for
  • 00:40:09
    this cell
  • 00:40:10
    and for this cell are to be determined
  • 00:40:13
    and the entries for the
  • 00:40:16
    c sub j column the entries here in this
  • 00:40:19
    cell
  • 00:40:20
    and in this cell are also to be
  • 00:40:22
    determined
  • 00:40:24
    and also the entries in c
  • 00:40:27
    sub j row
  • 00:40:33
    up to this cell are to be determined
  • 00:40:38
    and the entries in the
  • 00:40:41
    c minus z sub j
  • 00:40:44
    row are to be determined also except for
  • 00:40:48
    this cell
  • 00:40:49
    this cell would be an empty cell
  • 00:40:54
    now we start with the entries of the
  • 00:40:57
    basis column
  • 00:40:59
    as i said earlier the variables that
  • 00:41:02
    will
  • 00:41:04
    be in the solution corresponding to the
  • 00:41:07
    simplex w will appear in the basis
  • 00:41:11
    column
  • 00:41:12
    for the initial simplex w
  • 00:41:16
    the variable that will the variables
  • 00:41:19
    that will appear
  • 00:41:20
    in the basis column are those variable
  • 00:41:24
    with
  • 00:41:26
    entry of one in each column
  • 00:41:30
    and one is the only non-zero column
  • 00:41:35
    sorry one is the only non-zero entry
  • 00:41:39
    in its column again the variable that
  • 00:41:42
    will appear in the basis column is the
  • 00:41:44
    variable width
  • 00:41:46
    one positive one as
  • 00:41:49
    the only non-zero entry in
  • 00:41:52
    its column okay we start with
  • 00:41:55
    variable a in the column of a
  • 00:41:59
    consider this cell and this cell a has
  • 00:42:02
    no
  • 00:42:03
    1 as m3 in its column
  • 00:42:06
    therefore variable a will not appear in
  • 00:42:08
    the basis column
  • 00:42:10
    similarly the variable b
  • 00:42:14
    has no one there is no
  • 00:42:18
    number one in its column
  • 00:42:22
    therefore the variable b will not appear
  • 00:42:25
    in the basis column
  • 00:42:27
    now consider s1 the variable s1 has
  • 00:42:31
    one in its column
  • 00:42:34
    and one is the only non-zero entry
  • 00:42:38
    in the column of s1 the other
  • 00:42:42
    entry is 0
  • 00:42:46
    so s1 will enter the basis column
  • 00:42:50
    in the row where s1 has 1.
  • 00:42:55
    the variable s1 has an entry one in this
  • 00:42:58
    row
  • 00:42:59
    so we write s1 in this cell
  • 00:43:08
    it's the same with variable s3
  • 00:43:12
    the variable s2 has one
  • 00:43:16
    in its column and one
  • 00:43:19
    is the only non zero entry
  • 00:43:23
    of s2 in its column
  • 00:43:27
    because the other entry is 0
  • 00:43:31
    thus the variable s2 will enter
  • 00:43:34
    the basis column in the row
  • 00:43:38
    where s2 has one
  • 00:43:42
    again s2 will enter the basis column
  • 00:43:45
    because s2 has an entry of
  • 00:43:49
    positive 1 in its calling
  • 00:43:52
    that's the first condition and the
  • 00:43:53
    second condition is that
  • 00:43:56
    this entry one is the only non-zero
  • 00:43:59
    entry
  • 00:44:00
    of in the column of s2
  • 00:44:04
    therefore s2 will enter the basis column
  • 00:44:08
    in this row because
  • 00:44:11
    s2 has entry one in this row
  • 00:44:15
    so we write s2 in this cell
  • 00:44:25
    next we determine the entries in
  • 00:44:28
    c sub j column
  • 00:44:32
    the entries in c sub j column
  • 00:44:36
    are the coefficients of the variables
  • 00:44:39
    in the basis column
  • 00:44:43
    again the entries in c sub j column
  • 00:44:47
    are the coefficients of the variables in
  • 00:44:50
    the basis
  • 00:44:51
    column the coefficient of s1
  • 00:44:55
    is says one in the objective function
  • 00:44:58
    its
  • 00:44:58
    coefficient in the objective function is
  • 00:45:00
    given in the entry above
  • 00:45:02
    it 0
  • 00:45:05
    0 is the coefficient of s1 in the
  • 00:45:08
    objective function
  • 00:45:10
    and we write 0 in
  • 00:45:13
    c sub j column just before
  • 00:45:16
    s1
  • 00:45:21
    the entry here is the coefficient of s2
  • 00:45:25
    the second stack variable in the
  • 00:45:27
    objective function
  • 00:45:30
    and the coefficient of s2 in the
  • 00:45:34
    objective function is given by the entry
  • 00:45:37
    immediately above it zero
  • 00:45:41
    the coefficient of s2 in the objective
  • 00:45:43
    function
  • 00:45:44
    is and we write 0 in c sub j
  • 00:45:48
    column just before s2
  • 00:45:56
    again the variables that will
  • 00:45:59
    enter the basis column are those
  • 00:46:02
    variables
  • 00:46:03
    with one as
  • 00:46:06
    the we are the variables with one the
  • 00:46:11
    variables that will enter the basis
  • 00:46:13
    column are the
  • 00:46:14
    variables with 1
  • 00:46:17
    in its column and
  • 00:46:20
    1 is the only non-zero entry
  • 00:46:24
    in its column just like s1
  • 00:46:27
    and s2 they both have one in their
  • 00:46:30
    columns
  • 00:46:31
    and one is the only non-zero entry
  • 00:46:35
    the only entry that is not zero in
  • 00:46:38
    their columns and the
  • 00:46:42
    entries in c sub j column are
  • 00:46:45
    simply the coefficients of the variables
  • 00:46:48
    in the basis column
  • 00:46:50
    in the objective function the
  • 00:46:53
    coefficient of
  • 00:46:54
    s1 in the objective function is 0 we
  • 00:46:57
    write 0 here
  • 00:46:58
    the coefficient of s2 in the objective
  • 00:47:01
    function is 0
  • 00:47:03
    as indicated by this entry above s
  • 00:47:09
    now we determine the entries
  • 00:47:12
    in the last two rows
  • 00:47:16
    the entries in z
  • 00:47:19
    z sub j rom are obtained by multiplying
  • 00:47:24
    the entries of c sub j
  • 00:47:28
    column by the corresponding entries
  • 00:47:31
    of each of the variable columns
  • 00:47:34
    including the
  • 00:47:35
    solution column again
  • 00:47:39
    the entries in z
  • 00:47:43
    sub j row the entries
  • 00:47:47
    in this cell are obtained by multiplying
  • 00:47:51
    the
  • 00:47:51
    entries of
  • 00:47:54
    c sub j column by
  • 00:47:58
    the corresponding entries
  • 00:48:01
    of each variable column including the
  • 00:48:04
    solution column
  • 00:48:06
    and adding the products okay we start
  • 00:48:10
    with this entry
  • 00:48:11
    multiply zero by nine
  • 00:48:15
    zero plus zero multiplied by seven
  • 00:48:20
    zero so zero multiply the entries of c
  • 00:48:25
    subject column by the corresponding
  • 00:48:27
    entries of
  • 00:48:29
    the variable column a and 0 multiplied
  • 00:48:33
    by nine
  • 00:48:34
    plus zero multiplied by seven is
  • 00:48:38
    zero
  • 00:48:44
    for the entry in this cell multiply
  • 00:48:48
    the entries of c sub j
  • 00:48:51
    column by the corresponding entry of the
  • 00:48:54
    v
  • 00:48:54
    column and add the products
  • 00:48:58
    0 multiplied by 5 plus
  • 00:49:02
    zero multiplied by ten is
  • 00:49:06
    zero
  • 00:49:10
    the entry for this cell multiply the
  • 00:49:13
    entries
  • 00:49:14
    of c sub j column by the corresponding
  • 00:49:18
    entries of s1 column
  • 00:49:21
    and add the products 0 multiplied by 1
  • 00:49:26
    you leave the product in your mind or in
  • 00:49:29
    your head
  • 00:49:31
    that's zero plus zero
  • 00:49:34
    multiplied by zero you have zero plus
  • 00:49:38
    zero
  • 00:49:38
    is zero
  • 00:49:43
    and the entry for this cell
  • 00:49:47
    is obtained by multiplying the entries
  • 00:49:49
    of c
  • 00:49:50
    sub j column by the corresponding
  • 00:49:53
    entries
  • 00:49:54
    of a of s2 column
  • 00:49:59
    multiply zero by zero
  • 00:50:02
    plus zero multiplied by one
  • 00:50:06
    you get zero
  • 00:50:11
    we do the same for the solution column
  • 00:50:15
    but only for z sub j row
  • 00:50:19
    the entry in this cell is obtained by
  • 00:50:21
    multiplying
  • 00:50:23
    the entries of c sub j column
  • 00:50:27
    by the corresponding entries of the
  • 00:50:30
    solution column that is 0 multiplied by
  • 00:50:35
    45 0
  • 00:50:38
    plus 0 multiplied by
  • 00:50:42
    70 0 so you have
  • 00:50:45
    in your mind 0 plus 0 0 multiplied by 45
  • 00:50:50
    plus 0 multiplied by 70
  • 00:50:54
    is zero
  • 00:51:00
    now the
  • 00:51:04
    entries in the last row the entries
  • 00:51:07
    in c sub j
  • 00:51:10
    minus z sub chain this is the
  • 00:51:15
    c sub j row this is the c sub j row
  • 00:51:20
    and this is the z sub j row
  • 00:51:23
    this is the c sub j row
  • 00:51:27
    and this is the z sub j row
  • 00:51:30
    and we get the difference of the
  • 00:51:32
    corresponding entries
  • 00:51:34
    of the two rows the topmost row
  • 00:51:37
    and the second to the last row we have
  • 00:51:41
    six
  • 00:51:41
    minus zero is six
  • 00:51:48
    seven minus zero is
  • 00:51:53
    seven
  • 00:51:57
    zero minus zero is zero and
  • 00:52:04
    lastly zero minus zero
  • 00:52:08
    is zero
  • 00:52:11
    this cell will be left empty
  • 00:52:16
    again to get the entries
  • 00:52:19
    of the second to the last row the
  • 00:52:23
    entries of
  • 00:52:24
    z sub j row multiply
  • 00:52:27
    the entries of the c sub j column
  • 00:52:32
    by the corresponding entries of each
  • 00:52:35
    variable
  • 00:52:35
    column and add the products
  • 00:52:39
    like for variable column a
  • 00:52:42
    multiply the entries sub c sub j
  • 00:52:45
    column by the corresponding entries
  • 00:52:49
    of a variable a column and add the
  • 00:52:52
    products
  • 00:52:53
    that is zero multiplied by nine plus
  • 00:52:56
    zero multiplied by
  • 00:52:58
    seven equals zero
  • 00:53:01
    for the next entry zero multiplied by
  • 00:53:03
    five
  • 00:53:04
    plus zero multiplied by ten zero
  • 00:53:08
    zero multiplied by one plus zero
  • 00:53:11
    multiplied by
  • 00:53:12
    zero is zero zero multiplied by
  • 00:53:15
    zero plus zero multiplied by one
  • 00:53:18
    is zero the entries of the last row
  • 00:53:23
    the c minus c sub j
  • 00:53:26
    minus z sub j rho are obtained by
  • 00:53:30
    getting the difference of the entries of
  • 00:53:32
    the topmost row
  • 00:53:35
    or the c sub j row
  • 00:53:39
    minus the corresponding entry
  • 00:53:42
    in the z sub j row we have six
  • 00:53:46
    minus zero is six seven
  • 00:53:49
    c sub j seven minus z sub j zero
  • 00:53:53
    seven minus zero is seven
  • 00:53:57
    zero minus zero is zero
  • 00:54:00
    and zero minus zero is zero
  • 00:54:03
    now this is the complete initial simplex
  • 00:54:07
    w
  • 00:54:09
    for each simplex w there is a
  • 00:54:13
    corresponding solution and
  • 00:54:16
    for hence for the initial simplex w
  • 00:54:20
    we will call the corresponding solution
  • 00:54:22
    the initial solution
  • 00:54:37
    again for the initial simplex w
  • 00:54:41
    we call the solution initial solution
  • 00:54:45
    for the second simplex w we will call
  • 00:54:48
    the solution
  • 00:54:49
    second solution and for the
  • 00:54:53
    third simplex w we will call the
  • 00:54:55
    solution the third solution
  • 00:54:59
    now the variables that appear in the
  • 00:55:01
    solution
  • 00:55:03
    are those variables in the basis column
  • 00:55:09
    in the basis column we have variables s1
  • 00:55:11
    and s2
  • 00:55:13
    so these variables are
  • 00:55:17
    will be in the initial solution and they
  • 00:55:19
    will have
  • 00:55:20
    values that are not zero
  • 00:55:24
    s1 and s2
  • 00:55:30
    again the variables in the solution
  • 00:55:34
    with values that are not zero
  • 00:55:38
    are those variables that appear in the
  • 00:55:41
    basis
  • 00:55:42
    column in the basis column we have
  • 00:55:45
    s1 and s2 so this variables will have
  • 00:55:48
    values that are not
  • 00:55:50
    zero in the initial solution
  • 00:55:53
    and the values of the variables
  • 00:55:56
    in the basis column are the
  • 00:55:58
    corresponding entries
  • 00:55:59
    in the solution column
  • 00:56:03
    thus in the initial solution the value
  • 00:56:06
    of
  • 00:56:06
    s1 is the corresponding
  • 00:56:09
    entry in the solution
  • 00:56:13
    column or s column which is 45
  • 00:56:17
    s1 equals 45
  • 00:56:23
    similarly the value of s2 in the initial
  • 00:56:26
    solution
  • 00:56:28
    is the corresponding entry of s2
  • 00:56:31
    in the solution column or s
  • 00:56:34
    column which is 70.
  • 00:56:42
    now the variables that are not in the
  • 00:56:46
    basis column we only
  • 00:56:47
    we have four variables a b
  • 00:56:50
    s one and s two the variables that do
  • 00:56:53
    not appear
  • 00:56:54
    in the basis column their values are
  • 00:56:57
    zero
  • 00:56:59
    since both the decision variables a
  • 00:57:03
    and b are not in the
  • 00:57:06
    basis column their values are zero
  • 00:57:10
    initially a equals zero
  • 00:57:14
    and b equals zero
  • 00:57:21
    now the value of the objective function
  • 00:57:25
    given by z
  • 00:57:34
    the value of the objective function is
  • 00:57:35
    the entry
  • 00:57:37
    in the the last entry
  • 00:57:41
    in the solution column this is the
  • 00:57:44
    solution
  • 00:57:45
    column the entries are 45 70
  • 00:57:49
    and zero and the last entry in the
  • 00:57:52
    solution column
  • 00:57:53
    is 0 and that is the value of c
  • 00:57:57
    for the initial simplex w
  • 00:58:03
    again there is a
  • 00:58:07
    solution that corresponds for each
  • 00:58:09
    simplex w
  • 00:58:11
    for the initial simplex w we call the
  • 00:58:15
    solution
  • 00:58:16
    initial solution and the variables
  • 00:58:21
    with values that are not
  • 00:58:24
    zero in the solution are those variables
  • 00:58:28
    that appear
  • 00:58:29
    in the basis column in this example
  • 00:58:34
    s1 and s2 are variables
  • 00:58:37
    that we see in the objective function so
  • 00:58:40
    they will have values
  • 00:58:42
    in the initial solution and their values
  • 00:58:44
    are not
  • 00:58:45
    zero and the values of the variables in
  • 00:58:49
    the solution
  • 00:58:51
    are given by the corresponding entries
  • 00:58:55
    in the solution column
  • 00:58:58
    for the variable s1 the first left
  • 00:59:01
    variable s1
  • 00:59:02
    the value of s1 is the corresponding
  • 00:59:05
    entry
  • 00:59:06
    in the solution column which is 45
  • 00:59:10
    thus s1 equals 45
  • 00:59:14
    and s2 appears in the
  • 00:59:18
    basis column hence s2
  • 00:59:21
    is a variable in our solution and the
  • 00:59:23
    value of
  • 00:59:24
    s2 is not 0. specifically
  • 00:59:27
    the value of s2 is the corresponding
  • 00:59:30
    entry
  • 00:59:32
    in the solution column the corresponding
  • 00:59:35
    entry of
  • 00:59:36
    s2 in the solution column is
  • 00:59:40
    70 thus s2 equals
  • 00:59:43
    70. now all the rest
  • 00:59:47
    of the variables that do not appear in
  • 00:59:50
    the basis column
  • 00:59:52
    have values of 0. we have 4
  • 00:59:56
    variables a b the decision variables
  • 00:59:59
    s1 and s2 the snap variables you can see
  • 01:00:03
    that a
  • 01:00:03
    and b do not appear in the basis column
  • 01:00:07
    that means their values in the solution
  • 01:00:10
    in this initial solution r0
  • 01:00:14
    a equals zero and b
  • 01:00:17
    equals zero now
  • 01:00:20
    the value of the objective function
  • 01:00:25
    denoted by c is the last entry
  • 01:00:29
    in the solution column
  • 01:00:32
    this is the solution column and the last
  • 01:00:35
    entry
  • 01:00:36
    in its column is zero
  • 01:00:39
    that is the value of the objective
  • 01:00:42
    function
  • 01:00:43
    denoted by c in the initial
  • 01:00:46
    solution now what does this
  • 01:00:51
    initial solution means if this is a
  • 01:00:57
    production problem
  • 01:01:00
    our decision variables a and b have
  • 01:01:03
    values
  • 01:01:03
    of zero that means that
  • 01:01:07
    initially nothing is produced
  • 01:01:11
    our we are looking for the values of a
  • 01:01:14
    and b
  • 01:01:15
    that will maximize the value of c if
  • 01:01:17
    this is a production problem
  • 01:01:20
    values of 0 for a and b means that
  • 01:01:24
    initially nothing is produced because
  • 01:01:27
    the production has not yet started
  • 01:01:30
    and if nothing is produced it means that
  • 01:01:33
    all of the
  • 01:01:34
    resources are unused that's
  • 01:01:38
    why the snap variables s1 and
  • 01:01:41
    s2 have values and
  • 01:01:44
    s1 is equal to 45 all of the first
  • 01:01:48
    resource
  • 01:01:49
    and s2 is equal to 70 all of the first
  • 01:01:52
    resource
  • 01:01:54
    the value of c is equal to zero
  • 01:01:57
    because initially the values of
  • 01:02:01
    a and b are zero when you substitute
  • 01:02:05
    in the objective function you have six
  • 01:02:08
    multiplied by zero plus seven multiplied
  • 01:02:10
    by zero
  • 01:02:11
    even if you substitute the values of s1
  • 01:02:14
    and s2 they will be multiplied by
  • 01:02:16
    zero and the value of the objective
  • 01:02:18
    function denoted by
  • 01:02:20
    c will be zero
  • 01:02:23
    hence the initial the significance of
  • 01:02:26
    the
  • 01:02:27
    initial solution that corresponds for
  • 01:02:30
    the initial simplex w
  • 01:02:32
    is that the values of the decision
  • 01:02:34
    variables will all be zero which
  • 01:02:36
    indicate
  • 01:02:37
    that initially nothing is produced
  • 01:02:40
    and the slack variables will have values
  • 01:02:44
    that are not zero
  • 01:02:46
    which means that everything
  • 01:02:49
    is unused and since nothing is produced
  • 01:02:53
    the value of the objective function will
  • 01:02:56
    be
  • 01:02:58
    zero in the graphical method
  • 01:03:02
    the initial solution corresponds to the
  • 01:03:06
    origin but in the graphical network we
  • 01:03:10
    exclude the origin in the evaluation of
  • 01:03:13
    the objective function
  • 01:03:15
    because we know that we are
  • 01:03:18
    well aware that in the origin at the
  • 01:03:21
    origin
  • 01:03:22
    the values of the variables are zero
  • 01:03:25
    and when the bias of the variables are
  • 01:03:27
    zero and you substitute them in the
  • 01:03:29
    objective function
  • 01:03:31
    it will give you a value of 0 for the
  • 01:03:34
    objective function
  • 01:03:36
    that's why we exclude them in the
  • 01:03:39
    evaluation
  • 01:03:40
    of the objective function in the
  • 01:03:43
    graphical solution
  • 01:03:45
    but in the simplex algorithm or simplex
  • 01:03:48
    method we always have to start
  • 01:03:50
    with the initial simplex w
  • 01:03:54
    that will give us the initial
  • 01:03:58
    solution in the next
  • 01:04:01
    meeting sorry in the next lesson
  • 01:04:05
    we will proceed with our
  • 01:04:08
    solution to this linear program
  • 01:04:12
    using the simplex method
  • 01:04:15
    in the second simplex w
  • 01:04:18
    we will see an improvement in the value
  • 01:04:21
    of the
  • 01:04:22
    objective function and
  • 01:04:26
    one or one of these decision variables
  • 01:04:29
    will
  • 01:04:30
    have a non-zero value and
  • 01:04:34
    if one of these variables will have an
  • 01:04:36
    answer above you
  • 01:04:38
    one of the slack variables will be zero
  • 01:04:41
    or
  • 01:04:42
    will have a lesser value and
  • 01:04:45
    i will tell you about the criteria for
  • 01:04:49
    determining which of the decision
  • 01:04:51
    variables
  • 01:04:52
    in the second simplex w will have a
  • 01:04:55
    non-zero value
  • 01:04:57
    and which of the slot variables
  • 01:05:01
    will will have a zero value or lesser
  • 01:05:05
    value
  • 01:05:06
    in the second simplest way
  • 01:05:10
    or in the second solution corresponding
  • 01:05:13
    to the second simplex w
  • 01:05:15
    and i will also tell you about the
  • 01:05:18
    criteria
  • 01:05:20
    that will be used as basis to
  • 01:05:23
    tell us when the optimal solution is
  • 01:05:27
    reached or to the the basis the criteria
  • 01:05:30
    that will tell us that we have
  • 01:05:34
    obtained the maximum value of
  • 01:05:38
    c in the objective function
  • 01:05:41
    if you have any question about the
  • 01:05:43
    lesson today you ask your
  • 01:05:45
    question in the comments below
  • 01:05:50
    thank you for being in my class today
  • 01:05:52
    and don't forget to subscribe
  • 01:05:55
    thank you
  • 01:06:05
    [Music]
  • 01:06:20
    [Applause]
  • 01:06:21
    [Music]
  • 01:06:30
    so
  • 01:06:34
    [Applause]
  • 01:06:37
    [Music]
  • 01:06:58
    is
  • 01:07:02
    and i try not to
  • 01:07:09
    [Music]
  • 01:07:13
    don't kiss know that it's true
  • 01:07:33
    if you don't trust my resistance
  • 01:07:42
    [Music]
  • 01:07:53
    well i know five years is a long time
  • 01:07:58
    and the time's strong
  • 01:08:01
    but i think that you might people
  • 01:08:06
    are basically the same
  • 01:08:11
    [Music]
  • 01:08:43
    i don't want us
  • 01:08:56
    [Music]
  • 01:09:04
    oh
  • 01:09:06
    [Music]
  • 01:09:18
    is
  • 01:09:22
    all i wanna do is
  • 01:09:25
    all i wanna do
  • 01:09:33
    to is
  • 01:09:38
    [Music]
  • 01:09:49
    what i want to do
  • 01:10:03
    all i want to do
  • 01:10:21
    [Music]
  • 01:10:23
    [Applause]
  • 01:10:25
    [Music]
  • 01:10:28
    is
  • 01:10:32
    [Music]
  • 01:10:42
    foreign
  • 01:10:47
    you
Tag
  • Simplex Method
  • Linear Programming
  • Maximization Problem
  • Slack Variables
  • Decision Variables
  • George B. Dantzig