Question

Define a linear programming model and its components. Discuss which 3 properties a planning problem needs to meet to be modeled as an LP?

Define the feasible set and its corner points. Explain how one can find the combinations of the decision variables corresponding to the corner points. How one can use the corner points to find the optimal solution?

Define special situations: unbounded feasible set, infeasibility, alternate solutions, redundant constraints. Discuss what do these situations imply for the manager's planning problem. When do you need to and how do you avoid this situation?

Answer 1

linear programming model

leontief's I-O model can be interpreted as a simplified linear programming model. Suppose that the final demand F1 and F2 are given. The society likes to get thses final demands. Now if X1 is the total output of the first industry, then out of this a11x1 will be used up in the industry inself and a12X2 will be used up in the second industry. The amount left is, therefore, (X1 -a11X1 -a12X2) and it must be equal to the final consumption F1 if this final consumption is to be achieved. From this relation, we get one constraint (1-a11)X1 -a12X2 ≥ F1, which will be utilised in the linear progamming formulation. Similarly, for the second industry, we can get another constraint -a21X1 +(1-a22)X2 ≥ F2. The gross output levels X1 and X2 cannot be negative so that X1 ≥ 0 and X2 ≥ 0 are the non-negative conditions. Consider now the objective function. Here our problem is that the final demands F1 and F2 are specified. To get these specified final demands we have to choose gross oupputs X1 and X2 in such a manner that the total labour cost is minimised. The labour cost (in money terms) of X1 and X2 is equal to 11X1w+12X2w. This is the objective function to be minimised.

Thus, in the Leontief model, we get a typical linear programming problem, which can be stated as follows:

Minimise W = 11X1w + 12X2w

Subject to (1-a11)X1 -a12X2 ≥ F1

-a21X1 +(1-a22)X2 ≥F2

X1 ≥ 0 and X2 ≥ 0.

By following the rules regarding the primal problem and the dual problem, the dual of the above primal problem can be written as follows:

Maximise R = p1F1 + p2F2

Subject to (1 - a11)P1 - a21p2 ≥1,w

-a12p1 +(1-a22)p2 ≥12w

p1 ≥ 0, and p2 ≥ 0.

3 properties a planning problem needs to meet to be modeled as an LP

Divisibility : decision variables in a linear programming model are allowed to have any values, including non integer values that satisfy the constraints since each decision variable represents the level of some activity. it being assumed that the activities can be run even at fractional levels.

Additivity every function in a linear programing model is the sumof the individual contribution of the respective activities.

Certainity: the value assigned to each parameter of a linear programming model is assumed to be a known constant.

feasible set :We have seen from examples that optimization problems often have several constraints, leading to several inequalities or a system of linear inequalities. A point (x, y) satisfies a system of inequalities if it satisfies all
of the inequalities in the system. The solution set of a system of linear inequalities is the set of all points in the plane which satisfy the system of inequalities. This is also called the feasible set of the system of inequalities or the feasible region of the system. The graph of the feasible set for a system of inequalities is the set of all points in the intersection of the graphs of the individual inequalities.

corner points: The corner points are the vertices of the feasible region. Once you have the graph of the system of linear inequalities, then you can look at the graph and easily tell where the corner points are.

Use the corner points to find the optimal solution: The optimal solution of an optimization or optimal control problem must not lie in the interior of the feasible region in geeral. Take the simple problem: min f(x) with f(x) = - (x-1)^2 +1 on the interval [-3,4]. The global minimum is in x=4.
In addition there is a local minimum in x=-3. The same situation may be present for finite and infinite dimensional optimization problems. If you have a time optimal control problems in mind, then indeed the optimal control may lie an the boundary of the admissible set, for example, if the control function enters objective and state equations linearly. However, this is also not true in general. Depending on the other side conditions the optimal control may be singular intervalwise, i.e. it lies intervalwise in the interior of the set of admissible controls while other subarcs are bang-bang, i.e. lying on the boundary of the set of admissible controls. In case, the control enters objective and side constraints nonlinearly, everything may happen. Hence, this has nothing to do with time or convergence, it's just the optimal solution of the problem.

unbounded feasible set: A feasible region that can be enclosed in a circle. A bounded region will have both a maximum and minimum values. Unbounded Region. A feasible region that can not be enclosed in a circle.

infeasibility: A linear program is infeasible if there exists no solution that satisfies all of the constraints -- in other words, if no feasible solution can be constructed. ... Simplex-based LP software like lp_solve efficiently detects when no feasible solution is possible. The source of infeasibility is often difficult to track down.

alternate solutions: in other words we have alternative or multiple optimal solutions this essentially happens when a constraint touching an optimal solution point that is a binding constraint is parallel to the objective function line.

redundant constraints: A redundant constraint is a constraint that can be omitted from the system without changing the set of feasible solutions S. An implicit equality constraint is an inequality constraint that can be replaced by an equality constraint without changing S.

In order to apply the linear model, it’s a good idea to use the following step-by-step plan:

Step 1 – define the decision variables
Which choices and/or possibilities (variables) exist that decisions can be based on?

Step 2 – define the objective function
What’s the objective that you want to achieve? This could be the highest possible turnover or the lowest possible investment, for instance.

Step 3 – define the limiting conditions
These are all the limitations that influence the decisions that can be made. It helps to put the limiting conditions in a table to create a visual overview.

Step 4 – draw the feasible region
This is the region in which all previously set conditions are met. If you stay within this feasible area, the objective will have been achieved and you can make the optimal profit, for instance.

Step 5 – calculate the combination for optimal turnover
In this part, the optimal turnover is mathematically calculated. It can be found on one of the points on the edges of the feasible region. This can be calculated based on a system of mathematical equations.

Step 6 – draw the profit line
With this last step, you can calculate exactly what the total maximum turnover or profit is when choosing a specific option.