Question

Explain graphically how to determine the shadow price of a binding constraint in an LP with two variables. Show also the formulation of your LP.

In the context of network models, briefly explain what a flow balance constraint is and write down one example for a network of your own choice.

Develop your own objective function and set of constraints for an LP with unbounded feasible region but finite optimal solution. Illustrate graphically.

Answer 1

Solution:

The Shadow Price of a constraint in Linear Programming indicates how much the value of an objective (optimal) function changes due to a marginal variation in the right-hand side of a constraint. It is assumed that the rest of the model’s parameters remain constant. It should be noted beforehand that the Shadow Price can be positive, zero, or negative

Computational tools like Excel’s Solver can be used for obtaining the Sensibility Analysis from a Linear Programming model; however, here we will be focusing on calculating the Shadow Price of a constraint graphically, which will help us later on to understand the concepts behind the Solver results.

Calculate the Shadow Price of a Constraint Graphically

We will now calculate the Shadow Price of a constraint for the following Linear Programming model:

The optimal solution of this model is X=100 and Y=350 with an optimal value V(P)=3,100 according to the graphical Geogebra solution or the Solver solution from Excel. The following diagram shows the optimal solution obtained graphically at vertex C, which corresponds to the intersection of constraint 1 (R1: red color) and constraint 3 (R3: black color), this being the optimal basic feasible solution.

Suppose we want to know how the optimal value will change (with respect to its current value) if the right-hand side of constraint 1 is raised by one unit but without having to re-solve the problem. The shadow price allows us to answer that question and can anticipate the new optimal value resulting from a marginal variation of the right-hand side of a constraint.

A marginal variation of a right-hand side means that the new optimal solution can still be found using the current active constraints, i.e., those that are satisfied with equality (this conserves the optimal basis).

For constraint 1 if we increase its right-hand side, it will be moved upward in a parallel manner. If we want to guarantee that the new optimal solution can still be found with R1 and R3 active, we reach the vertex where R2 and R3 currently intercept corresponding to the coordinate X=166.67 and Y=350 (this is the maximum variation). In the same fashion if we decrease the right-hand side of constraint 1 and try to maintain R1 and R3 active in the new optimal, the last point where this is guaranteed is at vertex B, whose coordinates are X=0 and Y=350 (this will be the smallest variation). With this information we calculate the shadow price of constraint 1:

This shadow price is valid if the right-hand side of constraint 1 (currently b1=1,600) varies between [1,400,1,733.33]. For example, if the right-hand side of R1 increases from 1,600 to 1,700 the new optimal value would be V(P)=3,100+100*1.5=3,250. Similarly if the right-hand side of R1 decreased from 1,600 to 1,550 the new optimal value would be V(P)=3,100-50*1.5=3,025.

Note that if the right-hand side variation of constraint 1 is outside of the interval [1,400,1,733.33], the shadow price cannot be used to predict the new optimal value. In an upcoming analysis we will finish calculating the shadow price of constraints 2 and 3 along with other Sensibility Analysis in solving Linear Programming models.

Flow balance constraint:

Flow balance constraint states that (flow out of node) - (flow into a node) = (net supply at a node).

There is one balance equation for each node in the network.

For example,

x₁₂ + x₂₃ = 20 for node 1

x₂₃ + x₂₄ + x₂₅ - x₁₂ = 0 for node 2

The flow variables x_ij only have 0, +1 and -1 as coefficients.

Further, each variable appears in exactly two balance equations, once with a +1 coefficient,
corresponding to the node from which the arc emanates; and once with a −1 coefficient, corresponding to the node upon which the arc is incident.

Examples of local area network (LAN)

Here are the examples of LAN:-

• Networking in home, office.
• Networking between two computers.
• Wi-Fi (When we consider wireless LAN)
• 
• Maximize :

• Z=x+y-50

  constraints:

  

  

  Meaning numbers of right side:

  

  

  2400 and 2100 are the largest value

  Similarly , we can have constraints of least value

  so, right side always indicates largest and smallest value

  Significance of technoligical coefficients:

  

  coefficients are 50 , 24

  

  coefficients are 30 and 33

  It help us to solve linear programming problems

  There are various techniques to solve LP ... coefficients plays a very siginificant role to solve such LP problems

• ***********************************************************************************************************