1. Identify the decision variables.
2. Identify the problem constraints and express the constraints as a series of linear equations / inequalities.
3. Identify the objective functions as a linear equation, and state whether the objective is maximization or minimization.
LP Geometry in two-dimensions:
Geometric procedure for solving a linear programming problem is only suitable for very small problems. It provides a great deal of insight into the linear programming problem. We will also introduce the idea of all the possible cases that may arise for a minimization problem : Unique finite optimal solution, Alternative finite optimal solution, Unbounded optimal solution, Empty feasible regions.
Basic Feasible Solutions: In this section, the notion of basic feasible solutions will be introduced and its correspondence to extreme points of a polyhedra will be shown.
Let S = {x : Ax ≤ b, x ≥ 0} be a nonempty polyhedral set. Any point in S can be represented as a convex combination of its extreme points plus a non-negative combination of its extreme directions. Let x1, x2, … xk denote the extreme points and d1, d2, ……., dl denote the extreme directions of the set S. Then for any x Є S there exists λ1, λ2, …. , λk and µ 1, µ 2, …, µ l such that x = (λ1x1 + λ2x2 + … + λkxk) + (µ 1d1 + µ 2d2 + … + µ ldl) where ∑ λj = 1, λj ≥ 0, j = 1,2,…. k; µ j ≥ 0, j = 1,2,…,l.
Simplex method is used to solve the linear programming problem. The simplex method is a procedure that moves from an extreme point (basic feasible solution) to another extreme point with a better (improved) objective function value. This has been covered in detail in the tutorial document which will cover the Simplex Algorithm, the algebra behind the Simplex Algorithm and the Simplex Method in Tableau Format.
A Review of some of the examples and topics situations covered in the above tutorial
1. Consider a small manufacturer making n A1; A2; .... ; nproducts require some part of m R1; R2; .... ; RmAj
requires aijRii i = 1; 2; ...; mpjThe manufacturer needs to decide on number of units of each product Aj he needs to manufacture in order to maximize his profit.
2. Consider a company making a single product. The estimated demand for the product for the next four months are 1000, 800, 1200 and 900 respectively. Company has a regular time capacity of 800 per month and overtime capacity of 200 per month. Cost of regular time production is Rs. 20 per unit. Cost of overtime production is Rs. 25 per unit. Inventory holding cost is Rs. 3 per unit per month. Demand has to be met every month. Formulate as a linear programming problem.
3. Consider a restaurant that is open seven days a week. Based on past experience, the number of workers needed on a particular day is given to you. Every worker works five consecutive days, and then takes two days off, repeating this pattern indefinitely. How can we minimize the number of workers that staff the restaurant? We explain how to structure out the problem into (1) Decision Variable (2) Objective function (3) Constraints
A Summary/Recap of some of the problems solved in the tutorial document above.
1. Feed is manufactured for cattle, sheep, and chickens. This is done by mixing the following main ingredients: corn, limestone, soybeans, and fish meal. These ingredients
contain the following nutrients: vitamins, protein, calcium, and crude fat. The contents of the nutrients in each kilogram of the ingredients are given in a table. It is required to produce 10, 6, 8 (metric) tons of cattle feed, sheep feed, and chicken feed. Amount of the ingredients available are namely, 6 tons of corn, 10 tons of limestone, 4
tons of soybeans, and 5 tons of fish meal. The price per kilogram of these ingredients is respectively 0.20, 0.12, 0.24 and 0.12. You are provided with another table containing the minimal and maximal units of the various nutrients that are permitted is summarized for a kilogram of the cattle feed, the sheep feed, and the chicken feed. Formulate into a linear programming model so that the total cost is minimized.
2. The company operates three plants, namely A, B, and C. The capacities (in thousands of square feet) and unit manufacturing costs (in rupees per thousand square feet) of these
plants are provided in a table T1. The product is distributed within 3 marketing regions. Their requirements (in thousands of square feet) are given in another table T2. The transportation costs (in rupees) per thousand square feet from plants to marketing regions are given in another table t3. Formulate a linear programming problem to determine the quantities the company should transport from each plant to each marketing region in order to minimize the total manufacturing and transportation cost for the year.
3. Two types of devices are to be produced from device 3. Device 1 requires 9 hours of labor and 10 feet of rubber material. The unit profit from Device 1 is Rs. 325. To produce
one device 2, 6 hours of labor and 21 feet of rubber material is required. The unit profit from device 2 is Rs. 400. There are a total of 200 devices 3, 1600 hours of labor, and
3000 feet of rubber material available. If the profit is to be maximized, then formulate the above as a linear programming problem.
4. A steel manufacturer produces three sizes of beams: small, medium and large. These beams can be produced on any one of the three machine types: A, B, and C. The length in
feet of the beams that can be produced on the machines per hour are summarized in a table. The hourly operating costs of the machines are Rs. 50, 30 and 25 respectively and each machine can be used up to 20 hrs per week. Assume that 1000, 700, 650 feet of beams of different sizes are required weekly. Formulate linear program for this machine scheduling problem.
Identifying the decision variables, constraints, objective functions are the key steps over here.
5. You are given a table containing quantities of gasoline, kerosene and jet fuel are produced per barrel of each type of oil (light and heavy crude oil). The cost per barrel of light and heavy crude oil is 10 and 8 respectively. It is required to deliver 500000 barrels of gasoline, 300000 barrels of kerosene and 450000 barrels of jet fuel. Formulate a linear program to find the number of barrels of crude oil and minimizes the total cost.
6.cut. Let the iron roll be 15cm wide and following sizes should be made from it.
• 7 cm = 286 numbers
• 6 cm = 112 numbers
• 5 cm = 345 numbers
• 4 cm = 209 numbers
Only one dimension cutting is allowed. Formulate a LP such that wastage of the material
Game theory problem: two manufacturers A and B are competitors for the same product. Each wants to maximize their market share and adopt 2 strategies. The gain or pay-off for A when A adopts i and B adopts strategy j is given by aij. A 2×2 matrix would like (4 −2
−1 6 ).
During a given time period T, both A and B have to mix their strategies. If A plays strategy 1, then B would play strategy 2 to gain, which A does not want. Each therefore wants to mix their strategies so that they gain maximum (or the other loses maximum). So, for time period T, what is the proportion that A plays strategy 1 and 2. Assume A and B are equally intelligent.
8. Consider the following problem
Find the basic feasible solutions of the following LP.
20x1 + x2 ≤ 100 and x1, x2 ≥ 0
10. Solve the following problem using simplex method.
-x1 + x2 ≤ 1 and x1, x2 ≥ 0
11. Solve the following problem using simplex tableau format:
4. Popular Cases which may arise for a Linear Programming minimization problem:
Unique finite optimal solution – (a)= bounded region, (b)= unbounded region.
Alternative finite optimal solution – (a)= bounded region, (b)= unbounded region.
Unbounded optimal solution
Empty feasible region
5. Representation theorem:
Let S = {x : Ax ≤ b, x ≥ 0} be a nonempty polyhedral set. Any point in S can be represented as a convex combination of its extreme points plus a non-negative combination of its extreme directions. Let x1, x2, ... xk denote the extreme points and d1, d2, ......., dldirections of the set S. Then for any x Є S there exists λ1, λ2, .... , λk and μ1, μ2, ..., μl
x = (λ1x1 + λ2x2 + ... + λkxk) + (μ1d1 + μ2d2 + ... + μldl) where ∑ λj = 1, λj ≥ 0, j = 1,2,.... k; μj ≥ 0, j = 1,2,...,l.
6. Basic Feasible Solutions:
In this section, the notion of basic feasible solutions will be introduced and its correspondence to extreme points of a polyhedra was be shown.
Consider the linear program with the constraints: Ax = b; x ≥ 0; Am X nbmrank(A) = mmatrix). Let A = [B,N];B is m X m invertible matrix, and N is m X (n - m) matrixthe solution to the equations
Ax = b; x ≥ 0; where xB = B-1b and xN = 0 is called a basic solution of the system.
If xB ≥ 0, then x is called a basic feasible solution (BFS) of the system.
A basic feasible solution x is called a degenerate basic feasible solution if at least one component
of xB is zero.
Note:
• B is called the basis matrix.
• Variables in xB are called basic variables.
• Variables in xN are called non basic variables.
• In general the possible number of basic feasible solutions is bounded by the number of ways of extracting m columns out of n columns and it is bounded by
most BFS. Hence there are finite number of BFS.
7. Some of the Results regarding BFS:
• The collection of extreme points corresponds to the collection of basic feasible solutions, and both are non-empty if the feasible region is non-empty.
• If an optimal solution exists, then an optimal extreme point exists.
• For every extreme point there corresponds a basis and conversely for every basis there corresponds a unique basis. If an extreme point has more than one basis representing it, it is a degenerate extreme point.
8. The Simplex Method:
Simplex method is used to solve the linear programming problem. The simplex method is a procedure that moves from an extreme point (basic feasible solution) to another extreme point with a better (improved) objective function value. We also cover, The Simplex Method in Tableau Format.
