Chapter 4 - Simplex method Flashcards

Question

Give the procedure of simplex by simplex tableau

Answer 1

The simplex tableau consists of 6 column parts: 1) Basic variable column 2) Equation number 3) Z column 4) A column per variable 5) Right side of equations 6) Ratio column The simplex tableau has rows per basic variable, Z included. First we use the optimality test. This is just checking to see if Z can be improved. Then if this is not an optimal solution ,we start the iteration. We determine an "entering basic variable" that is the variable from the objectice function with the highest rate of improvement. Then we but a "box" around the column in the tableau below this coefficient that represent the entering basic variable from the objective function. We call this the "pivot column". Now we determine the leaving basic variable by the minimum ratio test. To do this, we use each entry in the pivot column that is greater than 0, and use this coefficiant as a divider that we use to divide its corresponding "b" (right side) value. so, if the right side value is 12, and the element in the pivot column at one of the rows is 2, then the ratio is 6. Thus the name "minimum ratio test". The row that has the smallest number at "ratio" will be called the "pivot row". We draw a box around this as well. There will be a single number that now is in both boxes. this number is called the "pivot number". We use this pivot number in a single iteration. First we get it to be equal to 1 by dividng the row by itself. Then we use this row to eliminate the coefficients in the pivot column in the other rows, including the objective function row. Then we perform the optimality test.

Answer 2

The pivot column is the column below the "entering basic variable" from the first row (objective function row). The purpose of the pivot column is to identify all places where this variable is included in the constraints so that we can check for boundaries. We do this to include every case, so that we dont accidently miss one in the MRT.

Answer 3

Entering basic variable is chosen by inspection of the objective function. There is no way to tell what to do if they are equal. Therefore, we pick one arbitrarily.

Answer 4

We use a schematic approach that helps us make the correct calculations. the tableau relies on patterns instead of having to understand what you're doing. NB: I can definitely see how using the tableau will make you forget what the hell you're doing. Anyways, here is the approach: We need to transform the model into a system of linear equations. To do this, we use slack variables. Recall how n variables and r constraints will turn to become (n+r) variables and r constraints/equations. First we need to set up the tableau itself. This involves creating a table consisting of the following columns: 1) Basic variables 2) Equation number (used to explain gauss-ops) 3) Z-column 4) One column per variable we have that is not Z 5) The right hand side value of the equations (b-vector) 6) Ratio column, to display the results of the minimum ratio test Then we select basic variables and non-basic variables. We automatically choose the decision variables to be our nonbasic variables. Then we fill the values we have initially into the system. Then we perform the first optimality test. Check to see if Z = ... has positive parameters so that Z can be increased. If yes, then we start the iteration. If no, then the current set of decision variable-values is the optimal solution. Then we find the "entering basic variable". The entering basic variable will be the variable that has the coefficient with the largest value, so that increasing this variable will lead to the biggest possible increase in Z. We use this "entering basic variable" to mark a column on the simplex tableau, which we call the "pivot column". The pivot column will consist of all entries in the column BELOW the variable we have picked as the entering basic variable. Then we find the "leaving basic variable". We need this variable to make the "pivot row". We find this variable by applying the minimum ratio test with the values that are not 0 in the pivot column we just found. When we mark the pivot row, we will, because of the already-marked pivot column, get a single coefficient as the "pivot number". This is a number we want to transform to 1 by dividing this row on itself. Then we use this "1" to eliminate the number on all other places in the pivot column. So, the result should be that the pivot row is the only row that now has a value in the pivot-column position. Along with the system-solving, we update the basic-variables-set by exchanging the leaving-basic-variable and the entering-basic-variable. Now that we have solved the system, we can apply the optimality test again. Then the same process applies as before.

Answer 5

There is no way of predicting the better choice. Therefore, we can make arbitrary choice.

Answer 6

Basically, it means that no variable qualifies as the leaving basic variable. Recall that we pick "leaving basic variable" based on the one that reach its boundary first. If no one reach boundary first, it graphically means that we are just extending further and further out into the feasible region. Of course, this means that Z is unbounded. Typically, the model is wrong. We very rarely find cases where the actual real life scenario is unsolvable due to unbounded feasible region. Think about what unbounded Z actually means. When maximizing, it means that we have **unlimited** resources or something similar. This rarely makes sense.

Answer 7

A corner-point solution is just a point indicating that constraint boundaries are intersecting there. This point can be in or out of the feasible region. A Corner-point feasible solution is also an intersection between constraint boundaries, but this one is a valid solution, as it doesnt violate any constraints.

Answer 8

There are two definitions that are essentially the same: 1) If we have "n" decision variables, then any two CPFS' that share at least (n-1) constraint boundaries will always be adjacent. 2) Two BFS/CPFS' are adjacent if their set of non-basic (or set of basic) variables is identical but for one variable.

Answer 9

Because we are only interested in corner points. Due to the nature of corners (intersections) and slack variables, we can be certain that this is the case. Say we have 3 decision variables and 3 constraints, where each constraint place a limit on the decision variable. In the space, this will create a prism. When considering the furthest out point on this prism, we can see that it lies on the boundary of all 3 constraints. Therefore, at this point, all slack variables are equal to 0. Therefore, our augmented values set looks like this: {x,y,z,0,0,0} Moving there will require 3 iterations, as there are 3 edges we have to move along. {0,0,0,a,b,c} {x,0,0,0,b,c} {x,y,0,0,0,c} {x,y,z,0,0,0} Looks something like this.

Answer 10

We have at this point already found our "entering basic variable". This would be the variable with the largest growth factor in regards to Z. Let us say our entering basic variable is x_2. We essentially want to move from a current BFS to an adjacent BFS. However, we dont know how far to move. So, we do this: We use the slack variables to figure out what happens if we keep increasing the "entering basic variable". At some point, increasing the "entering basic variable" will make our "cursor" hit the adjacent BFS. At this point, since it is a BFS, we know that the point will be at a place where one or more boundaries are at the limit. Therefore, their corresponding slack variables will be 0. So, the question is, how can we figure out how far out this point is? Say we have these two relevant constraints: x_4 = 12 - 2x_2 x_5 = 18 - 2x_2 We utilize the fact that x_4 and x_5 must be nonnegative. x_4 = 12 - 2x_2 >= 0 which leads to 2x_2 <= 12 This gives us: x_2 <= 6 Same for the other one gives: x_2 <= 9 These numbers say the following: "as we increase a nonbasic variable, we reach a point where the slack variable is 0. If we keep increasing the variable, the slack variable will become negative. So, essentiually, it tells us that if we want x_4 to be nonnegative, we must keep x_2 smaller than or equal to 6. Since x_5 has the x_2 bound on 9, we naturally use the tightest one. IT IS VERY IMPORTANT to understand the connection between MRT and the variable placing the tightest constraint on it. In this example, it was the variable x_4 that placed the tightest bound. Therefore, we use x_3 as the leaving basic variable. Why is it the leaving basic variable? It is the leaving basic variable since it is the first variable to reach the value of 0 as x_2 is increased. We dont want to increase beyond this point.

Answer 11

We solve the system of equations. The set of their corresponding solved values is called a "basis".

Answer 12

Refers to the case where every equation only has a single basic variable, and this has the coefficient of 1.

Answer 13

If there are n decision variables, there will be at least "n" constraints in all BFS'. However, the maximum can be equal to the number of constraints + the number of decision variables.

Answer 14

Could be the amount of resources left.

Answer 15

En bindende restriksjon er en restriksjon som er på formen "likhet". Det er det vi får av å bruke slakk variabler slik at vi går fra ubundet til bundet.

Answer 16

For any LP problem with n decision variables, two CPF solutions are adjacent if they share (n-1) constraint boundaries. The line segment connecting two adjacent nodes is called an "edge".

Answer 17

We are interested in adjacency because of their relation to optimal solutions. The general property is that if any LP problem that possesses at least one optimal solution, if a CPF solution has no adjacent CPF solutions that are *better* (measured by Z), then it MUST be an optimal solution. This is basically the optimality test we perform.

Answer 18

Initialization: We pick (0,0) as starting point. This is our initial CPF solution that we examine. Because of the non-negativity constraints (Wyndor) we know that (0,0) is a CPF. Optimality test: We conclude that there are adjacent solutions that are better. Therefore, we move. Iteration 1) Move to a better adjacent CPF, by performing the following 3 steps: 1) Consider the two edges that emanate from the current CPF. Choose to move along the edge that improve Z the fastest. 2) Stop at the first new constraint boundary. IF we were to move further, we would no longer have a corner-point feasible solution to examine. 3) Solve for the intersection of the new set of constraint boundaries. We are at a point where we have a CPF solution lying on the boundaries of some of the constraints. We solve for the decision variables. ex: x_1 = 0, 2x_2 = 12 Gives: x_1 = 0, x_2 = 6 Thus, our new point is (0,6) Optimality test: Conclude that (0,6) is not optimal. Continue new iteration. ***********************@ This is what we do, geometrically: We pick an initial point that is a CPF solution. Then we progress by picking the "best" edge (according to Z), stopping at the first constraint boundary on this edge (further movement moves us outside of the feasible region), solve the system of equations (relevant constraints) to find the point we're at. Then we perform an optimality test to see if we need to iterate more or not.

Answer 19

maximum of n. Can be less. C

Answer 20

The feasible region MUST be bounded. This means that the area is fixed, so we cannot continue to move further and further out to infinity.

Answer 21

Multiple reasons. Firstly, computers cant do it graphically. Therefore, we need to use a language they can understand. Secondly, the scale of problems quickly makes it extremely difficult to solve graphically. Therefore, we need a systematic language (algebra) to solve such complex cases. The algebraic language of the simplex method is designed to make it manageable.

Answer 22

The algebraic procedure is essentially structured around solving systems of equations. This is why we take the problem (in standard form) and convert it to its corresponding equality form. We do this by using slack-variables to represent the inequality-slack. The transformed standard-form problem is now called "augmented form". Augment means "utvided". It is important to understand that the augmented form and the standard form represent exactly the same problem. However, the augmented form is much more easy to handle due to our knowledge of solving linear systems of equations.

Answer 23

This simply means that the solution lies on the boundary of the equation-constraint that this slack-variable is used in. Every slack variable is unique for a constraint initially. Also, a slack-variable-value greater than 0 means that the solution is feasible. Less than 0 means that solution is infeasible, as the solution lies on the "infeasible" side of the constraint boundary corresponding to the slack variable of interest.

Answer 24

There are 3 main requirements: 1) Maximize the objective function 2) All constraints must be on the form of <=, while the right hand side constant must be nonnegative. 3) All variables have nonnegativity constraints

Answer 25

It is the problem surrounding the choice of "initial BF solution". Why? Recall what we would do if we have a problem on our standard model: We have functional constraints on the form of: LHS <= RHS. Recall that RHS must be nonnegative. We introduce the slack variable, SV: LHS + SV = RHS To choose initial BFS, we picked the list of SV's to be basic variables with value equal to their corresponding RHS. Thus, the initial BFS consists of for instance (0, 0, RHS1, RHS2, RHS3). However, what happens if we have constraints on the form of: LHS = RHS Then there is no slack variable. The same is the case with constraints on the form: LHS >= RHS. Remember that we want to pick some initial point that is actually a BFS (Augmented CPFS).

Answer 26

We use the artificial-variable technique.

Answer 27

we construct an artificial problem that is more convenient for us. We do this by using a dummy variable (artificial variable) into each constraint that needs an initial basic variable for the resulting equation. In essence, we ENLARGE the FEASIBLE REGION by the addition of the artificial variables. It is only whenever ALL artificial variables are set to zero that we get the regular feasible region back. The main point is this: We create an enlarged feasible region, in which we find the initial BFS. Then the first goal of the simplex method is to convert the region back. When this is done, we progress the method like before. ********************************************* So, how does the method actually play out? Say we have a constraint like this: a_i1x_1 + a_i2x_2 + ... + a_inx_n = b_i (row i) This EQUALITY is actually the exact same as applying TWO inequalities: a_i1x_1 + a_i2x_2 + ... + a_inx_n <= b_i a_i1x_1 + a_i2x_2 + ... + a_inx_n >= b_i They are the same as they force the middle point. This is an important concept. Consider what actually happens to the feasible region whenever we have equality instead of inqeuality. In a 2D example, the feasible region will go from being an area, to become a line segment. What we do, is construct an artificial problem that enlarge the feasible region, but has the same objective function as the real problem by making one modification to the real problem. We apply the nonnegative artificial variable, x-bar, and use it just like a normal slack variable. However, the solution HAS to include this variable as 0 later. IMPORTANT: The artificial variable essentially change the equality to an inequality. The artificial variable assumes the role of the slack variable. Therefore, we can treat the artificial problem as a regular standard form problem with ineqialities. Of course, we need to somehow force the artificial variable-value equal to 0 in the final solution. We use Big M or two-phase to solve.

Answer 28

We multiply both sides of the inequality with (-1). This allows simplex to start, since the slack variables gets immediate values as the RHS values become the initial basic variables.

Answer 29

We first use a SURPLUS VARIABLE. This is the same principle as a slack variable, but we extract the surplus from the greater-than part and converts the inequality to an equality: 0.6x_1 + 0.4x_2 >= 6 0.6x_1 + 0.4x_2 - x_5 = 6 (x_5 is the surplus variable, negative since it extracts the surplus) Then we use an artificial variable, just like with other regular equalities: 0.6x_1 + 0.4x_2 - x_5 + bar(x_6) = 6 The bar(x_6) allows the remaining part of the equation to work as a smaller-or-equal-to inequality. However, me must be careful with the artificial variable. It must be equal to 0 in the optimal solution. What happens is that we get this result: ax_1 + bx_2 = 6 + x_5 - bar(x_6) Looking at the part (x_5 - bar(x_6)). This value can be anything since they are only restricted by nonnegativity. THis means that the LHS can be equal to ANY number. This will in effect REMOVE this constraint from play in the artificial problem. The feasible region is larger because this constraint no longer plays a role (artificial problem). Thus, we can choose the origin as the initial BFS.

Answer 30

NOTE that one could just change the roles of the positive and negative coefficients in row 0 for both the optimality test and step 1 of an iteration. However, this can be confusing, so we rather transform the problem. Min Z = ∑(c_j x_j)[j=1, n] ... is equivalent to: Max -Z = ∑((-c_j)x_j)[j=1, n] This works because the smaller Z is, the larger (-Z) will be.

Answer 31

Negative variables could represent decrease in production of some product that is already being produced. In most cases, negative variables doesnt make a lot of sense, but it makes sense in cases where we're talking zero sum games. Increase one variable means we must decrease some other variable.

Answer 32

As we know, determining "leaving basic variable" using the minimum ratio test requires the algebraic foundation of nonnegativity constraints. x_4 = 12 - 2x_2 >= 0 could represent such a case. We get that x_2 cannot grow beyond 6 as a direct result of x_4 being required to be nonnegative. However, if x_4 is not required to be nonnegative, what happens then? We solve this problem with one of two cases. One is for variables with a bound on the negative values allowed. THe other is for variables with NO bound on negative values allowed. CASE: Negative bound. The constraint will look like this: x_j >= L_j, where L_j is a negative constant. We can convert this constraint to a nonnegative constraint by making a change of variables: x'_j = x_j - L_j, so x'_j >= 0 In the model, we therefore replace x_j with x'_j + L_j (direct replacement), but now we have constant which we move to RHS and x'_j which is nonnegative. CASE: No negative bound on values allowed We replace x_j with the difference "x_j^(+) - x_j^(-)" Both are nonnegative. Their difference can be any number. At the solution, they have the following property: x_j^(+). = x_j, if x_j>= 0, 0 otherwise x_j^(-) = abs(x_j) if x_j <= 0, 0 otherwise

Answer 33

First of all, we need to convert problems that are not in standard form to artificial problems. We do this by including artificial variables that enlarge the feasible region, which allows us to pick the origin as the starting point. However, we cannot use solutions from the artificially induced feasible region. Therefore, we dont want to use artificial variables with values other than 0 in our final solution. As a result, we add M to represent a very large value, which we multiply with the artificial variables, which we then subtract from the objective function. Thus, the M values works as punishment for using the artificial values in the objective function. For instance, in a maximization problem: Z = 3x_1 + 5x_2 - Mx_5, where x_5 is the artificial variable. We subtract it from Z because it is a punishment to use x_5. The problem now is that this equation is not on the proper form from gaussian elimination, as it includes basic variables. The proper form from gaussain elimination is supposed to only include nonbasic variables. Therefore, we must perform som preliminary row operations (using the other constraints) to remove these basic variables. This will alter the RHS value of the objective function as well (most likely). We now perform simplex method until we have all artificial variables equal to nonbasic variables (zero) and we have an optimal solution as well. The reason why big-M works, is because of the large penalty on using non-zero artificial variables in the optimal solution. It will never happen. Therefore, we can be sure that the final solution is indeed both feasible and optimal. NB:Only feasible as long as the artificial variables are equal to 0.

Answer 34

These methods will yield solutions where at least one of the artificial variables have value greater than 0.

Answer 35

We enlarge the feasible region. The artificial variables are used on equalities, which essentially converts the equality into a regular inequality with a slack-variable. Therefore, when the artificial variable is used like a slack-variable, the enlarged feasible region is basically the inequality region.

Answer 36

Say we work in 2D. An equality is a line segment. As constraints, this means that our solutions (feasible) are restricted to this line segment. However, it is therefore difficult to start the simplex method, as we dont really know where to begin (origin is not feasible). The whole points is that when we have equality-constraints, we dont know where to start the simplex method. Consider the first image, where tf do we start? However, when we use the artificial variable (constant 'a' in the second picture), we can essentially extend the feasible region. By changing the artificial variable, we change the feasible region so that we can find the origin.

Answer 37

Using a surplus variable that removes the surplus, creating an equality. We place nonegativity constraint on the surplus variable (like all other variables) and therefore we subtract this variable from the constriant. ex: 0.6x_1 + 0.4x_2 >= 6 Add the surplus variable, x_5 0.6x_1 + 0.4x_2 - x_5 = 6 Now that we equality, we use artificial variable to create it feasible to start simplex: 0.6x_1 + 0.4x_2 - x_5 +bar(x_6) = 6

Answer 38

Minimization of some expressions is the same as maximizing the negative value of the expression

Answer 39

it becomes real whenever the artificial variables are equal to 0.

Answer 40

We just dont want artificial variables as nonbasic, because if they are equal to 0, then the feasible region is not enlarged, and we dont have a BFS.

Answer 41

We dont need to use the fucking M value

Answer 42

two-phase use 2 different objective functions. One of them (the first) use the artificial variables only. The second objective function use the original objective function. ex Min Z = bar(x_4) + bar(x_6) Min Z = 0.4x_1 + 0.5x_2 The two obj functions are used to their corresponding phase. PHASE 1: The objective of this first phase is to find some BFS for the real problem by using the artificial problem. PHASE 2: THe objective of the second phase is to run simplex on the real problem. We can drop the artificial variables, as we have found a BFS on the real problem. Consider radiation therapy example. We have 2 artificial variables. The entire point of phase 1 is to find a BFS where these artificial variables have value = zero. we find this by solving simplex. We find something like this then: (6, 6, 0.3, 0, 0, 0) Then we drop the artificial variables, and we get: (6, 6, 0.3, 0) IMPORTANT: The phase 2 objective function, which in radiation example is: min Z = 0.4x_1 + 0.5x_2, is obviously not in proper form from gauss elimination. This is because it has basic variables in it. We must therefore use the constraints, as they have been modified by the phase 1 (but removed the cols of artificial variables), to get the phase 2 objective function to only contain nonbasic variables. After this is done, we run simplex as usual. A note on NO FEASIBLE SOLUTIONS: If we are done with first phase, meaning that the first phase yields some "optimal" solution, we need to check to see if the artificial variables are basic or non basic. If at least one of the artificial variables are basic, we have no feasible solution.

Answer 43

One reason could be because of the fact that LP problems are such that small changes in parameters are easy to predict.

Answer 44

The shadow price of a resource i (denoted y*_i) measures the marginal value of this resource. marginal value of a resource is the additional amount of general gain we get from increasing this resource by a single unit. This means, we are considering changes in the b-values (RHS). For instance, what happens if we increase b_1 with one unit? what happens to Z then? This is what we call the shadow price. The simplex method identifies the shadow price of each y*_i by looking at the coefficient of the i-th slack variable in row 0 of the final simplex tableau. Economically, the shadow price also indicates the largest cost we would accept for the extra unit of the resource. As long as the cost for the resource is lower than the shadow price, we buy. NB: Marginal value is marginal. Marginal values refer to point-level accuracies. This means, if we find that the shadow price at some point is 10 by adding one unit of resource b_2, adding 2 units of b_2 will not necessarily give a gain of 20.

Answer 45

Free goods is a term used to represent goods/resources with a shadow price of 0. This happens when the constraint is not binding. For instance, if the constraint x_1 <= 4 is not the tightest constraint, increasing this will not actually do anything. Therefore, we call x_1 a free good. there is a surplus of x_1. THe opposite of free goods is "scarce goods". Scarce goods have positive shadow prices. They are connected to binding constraints. They are at the limit. Increasing the limit will benefit the objective function. Recall that "binding constraints" are constraints where the optimal solution is at an equality-situation.

Answer 46

Sensitivity analysis is about identifying sensitive parameters. Sensitive parameters are parameters that cannot be changed without changing the optimal solution. These parameters will have to be treated with special care and precise estimation.

Answer 47

Sensitive parameters are defined as "parameters that cannot be changed without changing the optimal solution". In the model: max Z = ∑(c_jx_j)[j=1, n] s.t. ∑(a_ij x_j)[j=1, n] <= b_i, for i=1, ..., I So, we have: c_j b_i a_ij All these parameters can influence the optimal result in certain situations.

Answer 48

We could remain at the optimal soltuion. We could get new optimal solution. We could get an infeasible solution. We could get sub optimal solution.

Answer 49

Solving the entire thing again but with the new variables. This can take a lot of time. We would rather use sensitivity analysis without solving the entire problem again.

Answer 50

Det er det verdiområdet der vi kan endre på c_j mens den optimale løsningen forblir den samme. Det er derfor en range av verdier, et intervall, for c_j. ex [-infinity, 2.5] Hvordan finner vi ut av det? Grafisk ser vi på løsningen vår, målfunksjonen og restriksjonene. Målfunksjonen går gjennom det optimale punktet. Det handler om å identifisere hvilke restriksjoner som først vil bli truffet som følge av at vi endrer på c_j. Husk parallelitet og skifting av målfunksjon så langt ut som mulig. Når målfunksjonen er paralell med en av restriksjonene, så betyr det at vi ikke kan endre c-verdi mer.

Answer 51

Vi må løse hele systemet på nytt

Answer 52

Because this is required in order to have a form that allows us to read out value from the system. If some variables are basic, we have to set up vector-parameterization which is only fuckery. Therefore, we go for the proper form from gaussian elimination and include only one non-zero variable in every row. for the objective function, this will be the z-value. because the nonbasic variables are all equal to 0, their coefficient gives the exact contribution to Z per unit we increase them with. Z = 30 + 3x_1 - 5/2 x_4 x_1 and x_4 are 0. Therefore it is easy to use them to find our which direction to work on next. Recall that when we choose an entering basic variable, we will solve the system of equations so that the other variables will adjust. The final simplex tableau holds an objective function that contains shadow prices. It is the final tableau because moving to adjacent BFS will decrease Z. At the optimal BFS, the variables that are included in the objective function are all equal to 0. This means that there are no slack there. Therefore, the coefficient of these variables would indicate the increase (marginal) in Z should we be able to relax the constraint a little.

Answer 53

They use some objective coefficient as a point, and then specify the allowable range for this coefficient to be that still maintains the current optimal solution. So, as long as the objective coefficient c_j is within the "allowable range", the optimal solution is the very same point.

Answer 54

Sensitivitetsanalyse innebærer at vi ser på hva som skjer med målfunksjonen vår dersom vi endrer på parameterverdier. Parameterverdier: b_i, c_j, a_ij Når vi endrer på paramterverdiene kan følgende skje: Vi kan få fortsatt optimal løsning Vi kan få en ulovlig løsning Fortsatt være lovlig, men suboptimal

Answer 55

Vi kan endre hva som er optimal løsning

Answer 56

Vi sammenligner målfunksjonens stigningstall med stigningstallet på restriksjonen. -C_1/5 = -1/2 c_1 = 5/2 Når stigningstallene er like (c_1 = 5/2) så er målfunksjonen parallell med den spesifikke restriksjonen. Vi vet at målfunksjonen tidligere har gått gjennom det optimale punktet. Når linjene er parallelle ligger de på en grense på sensitivitetsområdet. I dette tilfellet betyr det at vi kan ØKE c_1 opp til 5/2 og samme punkt vil fortsatt være det optimale punktet.

Answer 57

Paralellforskyve en restriksjon

Answer 58

verdiområde for b_j hvor variabelverdiene kan skifte verdi, men variablene i basis forblir de samme. Dette betyr egentlig bare at vi skyver på et hjørnepunkt. De samme slack-variablene har 0-verdi før og etter. Det betyr at så lenge vi er i denne sitasjonen, så kan vi øke Z med samme hastighet ved å øke b_j. Vi parallellforskyver restriksjonen med et antall enheter, og øker Z med et antall enheter multiplisert med en eller annen koeffisient (skyggepris).

Answer 59

Sensitivitetsområdet for b_i er det området der skyggeprisen for b_i er gyldig.

Answer 60

Skyggepris er maksimalt pris en beslutningstaker er villig til å betale for en ekstra enhet av ressursen

Answer 61

Redusert verdi/kostnad og skyggepris er basically det samme. Redusert verdi er det vi mister av Z ved å stramme inn en restriksjon. Å redusere RHS for Restriksjon 1 med en enhet (fra 25 til 24) har samme effekt på basisbariablene og målfunksjon som å sette s_1 = 1. Det gjør at målfunksjonen reduseres med 1/10. Dette kalles for redusert verdi. Samtidig, dersom det å redusere RHS med en enhet minker Z med 1/10, så vil en økning av RHS med en enhet øke Z med 1/10. Skyggepris for b_1, y*_1 er dermed lik 1/10. NB: Gjelder kun for det optimale tablået. Dersom det ikke er optimalt gir det null mening å skulle kunne hente skyggepris.

Answer 62

enklere å overholde. Vi kaller dette en relaksering.

Answer 63

vanskeligere å overholde. Vi kaller dette en innstramming.

Answer 64

større mulighetsrom og like god eller bedre Z

Answer 65

mindre mulighetsrom og like god eller dårligere Z

Answer 66

Dette er i forhold til c_j. Fra definisjonen går det at "sensitivitetsområdet for c_j er det området med verdier som denne koeffisienten kan ha som bevarer det foreløpige optimale løsningen, under antakelse om at ingen andre koeffisienter endres". Hva skjer her egentlig? La oss si vi har Z=c_1x_1 + c_2x_2 Det gir oss: x_2 = Z/c_2 - c_1/c_2 x_1 Det eneste vi bryr oss om er stigningstallet. Dette er fordi når stigningstallet er lik stigningstallet til en annen restriksjon, så ligger målfunksjonen parallell med retriksjonen. HUSK at vi oppnår optimal løsning ved å skifte målfunksjonen så langt ut i mulighetsområdet vi kan (maksimeringsproblem), så dette vil automatisk justere målfunksjonen. Når stigningstallene er like, ligger de derfor oppå hverandre. Dersom vi øker c_1 enda litt mer, vil slope bli brattere enn restriksjonen, som fører til at vi får ett nytt optimalt punkt. Vi vil flytte punktet helt til neste BFS faktisk. Poenget er å forstå hvordan paralellitet fungerer med målfunksjonen.

Answer 67

Hva ønsker vi å finne ut? vi ønsker å finne ut hvor mye c_j kan endre seg mens den samme optimale løsning forblir optimal. Dersom vi har en målfunksjon, kan vi illustrere det slik: z = c_1x_1 + c_2x_2 z = (c_1+∆)x_1 + c_2x_2 Det vi gjør er å introdusere en form for "ny" c_1 som inkluderer en delta verdi som står for den endring vi kan gjøre på c_1 som bevarer optimal løsning. Man kan plotte dette rett inn i tablået, og løse som vanlig. Men, dette er tidkrevende, og vi har enklere metoder. Vi går helt ned til siste "final" simplex tablå. Vi kan finne ut av hvilke delta-verdier vi skal ha med ved å bruke intuisjon. For det første, vi trenger bare delta-verdier i målfunksjonsraden og kun i kolonner som faktisk har ikke-null-koeffisienter. Så blir spørsmålet: Hva skal delta-koeff inneholde? Når vi ser på tablået, kan vi gjøre følgende tankegang: La oss si vi har en koeff i målraden for s_1. Dersom s_1 økes med en enhet, så vil følgende skje: 1) Vi ser direkte hva som skjer med målfunksjonsverdien 2) Vi vet at ved å endre s_1 og løse system, vil de andre variablene tilpasse seg. Vi kan da se direkte fra tablået hvordan x_1, x_2 etc vil bli påvirket. Ved å bruke målfunksjonen, kan vi bekrefte dette: ex: Z = c_1x_1+c_2x_2 ∆Z = c_1(∆x_1)+c_2(∆x_2) Dette vil gi en verdi på ∆Z som tilsvarer den som direkte kan hentes ut fra tablået. MEN, vi brukte jo en annen delta tidligere, som en del av den nye c_1. Hva skjer med den? Vi må inkludere den. ∆Z = (c_1+∆)(∆x_1) + c_2(∆x_2) ∆Z = c_1*∆x_1 + ∆*∆x_1 + c_2*∆x_2 STOPP: Hvilken del av uttrykket over er viktig? Svar: ∆*∆x_1 Det er nettopp dette som gir oss hvilken delta verdi vi skal ha med i koeffisienten til s_1. Koeffisienten til s_1 i målraden skal inneholde hele summen ∆Z = c_1*∆x_1 + ∆*∆x_1 + c_2*∆x_2

Answer 68

Ikke fullført enda. c_1: 0<= c_1 <= 7.5

Answer 69

Because if we are going to pick "entering basic variable", we need to be able to pick one purely on the basis of improving Z the most. If we have some basic variable in this function, we know that this variable will change if we change on of the non-basic ones. This gives us a fuckery.

Answer 70

We need them to have a basic variable for the constraint that is missing one. Recall that we use the slack-variables for this purpose. HOWEVER, when we have equality constraints, we cannot use slack variables. Therefore, there are no basic variables in these constraints. Because of this, we introduce the artificial variables (along with the huge penalty in the objective function for having the artificial variable > 0) so that we get a basic variable to start the algorithm.

Answer 71

In the final solution, if all artificial variables equal 0, we have feasible solution(s). However, if as much as one (or more) of the artificial variables are greater than 0, then there are no feasible solutions. We can see this either at the end of BIG M, or at the end of the first phase of the two-phase method.

Answer 72

The answer to this lies in adjacency. We only consider adjacent nodes. Adjacent nodes share (n-1) constraint boundaries in problems with n decision variables. This means that if two CPF solutions are adjacent, they share n-1 constraints, meaning that the variables that lie on the constraint boundary will REMAIN zero on the variables representing the slack. Also, we know that adjacent nodes share all but one of their non-basic variables. This means that as we move from adjacent node to adjacent node, the set of non-basic variables will change with one variable at a time. So, because we know that moving to an adjacent node will only change one variable from zero to some value, we know that once we have found our entering basic variable, we can assume that all other non-basic variables remain zero.

Answer 73

Technological coefficients. Because they are usually a result of the current employed technology.

Answer 74

The OG objective function does not contain this variable. However, changing the variable-value from 0 to 1 will still impact the objective function with a value equal to the coefficient of the variable we just changed. What happens here, is the indirect effect. When we change say x3 from 0 to 1, we will also make impacts at variables that are defined by that just-varied variable. For instance, if x1 is equal to 10 - 3x3, then this value is (before we change x3) x1=10. But, when we increase x3 to 1, we also change x1 to 10-3=7. This effect will happen to every variable that use the x3-variable in its 'definition'/constraint. When we add together all the indirect effects (remember to multiply with the original coefficients of the objective function), we should (if calculated correctly) get a number that is exactly equal to the coefficient of the x3 variable in the objective function row of the final simplex tableau. Therefore, the indirect effect is camouflaged inside of the tableau. END OF INDIRECT -- START OF DELTA We can use the indirect effect as a starting point to quickly determining the delta-values so that we can calculate the sensitive area of the objective function coefficients. EXAMPLE: Say we have the case like the image shows. The indirect effect applies like it always does. However, when we are trying to find the sensitive area of c_j, we usually approach it with a "new" cj that is equal to cj+∆. We replace ALL old coefficients from the beginning of the simplex method with this new one, and solve like normal, and watch the ∆-values propagate downward and get their final values that we can use directly. However, we can avoid solving the iterations AGAIN if we have done it once with the original values. The indirect effect from changing slack1, s1, comes in the form of BOTH x1 and x2. x1 will be changed by 2/5, and multiplied by 1 due to the objective function coeff. x2 will be changed by -1/5 and multiplied by 1.5 as 1.5 is the c2 coeff. The sum 2/5-1.5/5 = 0.1, which is what the tableau shows. BUT: Now we did not include the ∆'s when we multiplied by the coefficient weights of the objective function. What we really should do now, is this: ∆Z = ∆x1 c1new + ∆x2 c2 (we only change one c-coefficient at a time) ∆Z = ∆x1 (c1old+∆c1) + ∆x2c2 ∆Z = 2/5 (1 + ∆) - 1/5 (1.5) ∆Z = 2/5 + 2/5∆ - 3/10 ∆Z = 1/10 + 2/5∆ There, we have found the coefficient of the delta-value without iterating all the shit. So, when finding deltas for objective function coefficients, we are just looking at the indirect effect of what WOULD happen if we change the non-basic variables from 0 to 1. IMPORTANT: The reason why only the coeffiecients from a single row is included in the final delta coeff, is because we only associate a single delta in the objective function. If we look at c1, we give this one a delta. Therefore, it does not make sense to talk about delta for x2. Given these, deltas, we find the sensitivity area by comparing every delta-case with being greater than or equal to 0. Since there are 3 delta values, we get 2 inequalities to solve (dont need the RHS): 1) 1/10 + 2/5∆ >= 0 2) 1/4 - 1/5 ∆ >= 0 We get: ∆ >= -1/4 ∆ <= 1/2 Then we include the c1 value, which is 1: 0.75 <= c1 <= 1.5 This is the sensitivity area for c1. Same procedure for every other objective coefficient as well. We dont need RHS value for the sensitivity analysis, but the pattern is still the same. I believe the intuition goes like this: (c1+∆)x1 = c1x1 + ∆x1 Since x1=2, we get: 2+2∆ From c2x2, we get: 1.5 times 3 = 4 Therefore, the sum is: = 4 + 2 + 2∆ = 6 + 2∆

Answer 75

Recall the definition of allowable range for objective function variables: How much we can change them while retaining the optimal solution. So, we're asking ourselves: How much can we change a non-basis variable before the optimal solution is changed? These non-basic variables are equal to 0. We can lower it to infinity, and increase it to the corresponding z-value in the final tableau.

Answer 76

The hard way: We insert RHS+∆ and calculate entire simplex with this value. However, this is stupid, as we can calcualte simplex regularly and then find the sensitivity by inspection (almost). The key here is the term "shadow price". When we look at the final iteration of simplex tableau, and want to find the delta's for RHS column, we ask this: "How will this RHS-value be impacted by a change in the slack-variable corresponding to the constraint we are either relaxing or tightening?". Then we use the principle "relaxing slack variable s1 is the same as increasing RHS by the same amount". And we can see from the tableau that if we change s1 by a unit, its column will contain coefficients for every row saying how much the corresponding RHS will be affected by this change. This is essentially the principle of shadow prices. Therefore, a change in s1 (or any other slack variable) will impact RHS by some coefficient. BUT: Since we're looking at the effect of changing by ∆, and not necessarily by a single unit, we interchange ∆ with '1' in the calculations. Therefore, if the coefficient is 2/5, we instead of 2/5 get (2/5)∆ to accommodate for changing by ∆ rather than a unit. If the coefficient of s1 in the objective function row (final iteration simplex tableau) if 1/10, then we know that changing s1 by ∆ will change RHS by ∆*1/10. These are the values indicated by the image. Then the question is: "How do we use these deltas to find the allowable range?" From the example, we have 3 delta-cases: 1) 6.5 + 1/10 ∆ 2) 2 + 2/5 ∆ 3) 3 - 1/5 ∆ We actually dont need the first one, as it is the objective function. We care about the others, because they essentially represent x1 and x2, which are variables that have the non-negativity constraint. Therefore, we get the following: 2 + 2/5 ∆ >= 0 3 - 1/5∆ >= 0 Which gives us... ∆ >= -5 ∆ <= 15 -5 <= ∆ <= 15 Then we insert 25 (original RHS value) to find the allowable range: 20 <= RHS b1 <= 40

Answer 77

For any LP problem with n decision variables, two cornerpoint feasible solutions are said to be ADJACENT if they share (n-1) constraint boundaries. For the 2D case, this means that two CPF solutions are adjacent if they are placed so that they are both lying on the same constraint boundary, for instance both are on x=3 for the constraint given by x<=3. In 3D, we must have 2 common constraints. Consider a cube. THe corner at the top, furthest out, will lie on x,y and z boundaries. One of its adjacent CPFs will share 2 of these, either x and y, or xand z, or y and z.

Answer 78

The problem must be bounded. If the feasible region is bounded, we can guarantee CPF solutions.

Answer 79

Their coefficients are 0 in this function. This is because we are not rewarded for having slack. In fact, the reward is just nothing.

Answer 80

It does not apply if there are redundant equations.

Answer 81

we treat it as if it is a part of the functional constraints. Therefore, we get it on the shape z - ax1 - 10x2 .... Along with the other functional constraints.

Answer 82

Here is the case: There is a potential problem regarding ties for the leaving basic variable. If there is a tie, it means that two or more basic variables reach 0 at the same time. In such a case, we will pick one of them as leaving basic variable, and the other remains a basic variable. IF the one(s) not picked for leaving basic variable remains 0 until the next iteration, which it will due to how simplex works, and we pick this specific variable as the new leaving basic variable, then we will get a perpetual loop. This is because we pick a variable that is already 0 as the leaving basic variable. When we solve the system, with this as 0, we get no change. We can avoid perpetual loops by doing some randomization on how we pick leaving basic variable.

Answer 83

Degenerate is used in two ways: 1) Reference to basic variables with a value of 0 2) Reference to BF solutions corresponding to basic variables that have value 0. So, both are based on the same thing, but the "object" they refer to can be either the BF solution, or the specific variable.

Answer 84

Finding that initial BFS. We need to use the artificial variable technique to deal with this problem.

Answer 85

Overwhelming penalty of choosing to have a value that is greater than 0 for any of the introduced artificial variables.

Answer 86

It is always basic: This is because we use the artificial variable to extend the feasible region, making it inequality instead of equality essentially. If this artificial variable is equal to 0, then we are actually AT the equality constraint. If the artificial variable is greater than 0, then we are somewhere in the artificial feasible region.

Answer 87

x-art = 18 - 3x - 5y Thus: 3x + 5y + x-art = 18

Answer 88

We add the punishment to the objective function. HOWEVER: Now the objective function contains basic and non-basic variables. As we know, the objective function should only contain non-basic variables. Therefore, we need to convert it (along with the system of equations), into proper form from gaussian elimination. In other words, we algebraically eliminate the basic variable coefficients from the objective function.

Answer 89

Positive. This is the opposite of the maximization problem.

Answer 90

We always minimize it. This is because this objective function consist only of artificial variables. In the BFS that we want to start simplex on the original problem, we need to have ALL artificial variables equal to 0. Therefore, we must minimize the sum of them.

Answer 91

This is a scenario where we allow x1 to be negative. x1 could represent the amount of production we can slack production of product 1 by. In order to solve this kind of problem, we have to deal with negative variable values. This is because our standard model does not deal with this. The standard model assumes the origin is a possibility. There is also a problem with leaving basic variable. As we know, the procedure for leaving basic variable make use of the fact that all variables have non-negativity constraints. This is crucial to find the distance allowed to travel. We deal with negative variables by performing some substitution. This substitution specifically depends on whether the variables have a negative **bound** or not. **WITH BOUND** Consider xj >= Lj, where Lj is some negative constant. IN this case, we put Lj on the other side, xj-Lj>=0, and replace xj-Lj with x'j. x'j is non-negative. The important part here is how we enter this substitution into the model. Every place where we have xj, we need to substitute by x'j-Lj. This means that in the constraints, the RHS value will change. **WITHOUT BOUND** When there is no bound, we need to make a substitution with two variables. If xj is unbounded negative, we replace it with xj^(+) - xj^(-). This new sum, where both variables are non-negative, can take on any possible value. Why are the called positive and negative? If xj is greater than 0, then xj^(+) = xj If xj is smaller than 0, then xj^(-) = abs(xj)

Answer 92

We go from having equality, to getting equality. We NEVER explicitly say that we get inequality. The only point is that the feasible region acts liek it.