Home page     Downloads      Privacy policy     Disclaimer & terms of use     Contact us     Advertise with us     About us      Link to us

Home Linear Programming Technique Linear Programming and Minimization of Contribution Margin - Graphical Method
 

Linear Programming - Minimization of Cost - Simplex Method:

Linear programming simplex method can be used in problems whose objective is to minimize the variable cost.

An example can help us explain the procedure of minimizing cost using linear programming simplex method.

Example:

Assume that a pharmaceutical firm is to produce exactly 40 gallons of mixture in which the basic ingredients, x and y, cost $8 per gallon and $15 per gallon, respectively, No more than 12 gallons of x can be used, and at least 10 gallons of y must be used. The firm wants to minimize cost.

The cost function objective can be written as:

C = 8x + 15y

C = Cost

The problem illustrates the three types of constraints, =, ≤, and ≥, as follows:

x + y = 40

x ≤ 12

y ≥ 10

The optimum solution is obvious. Since x is cheaper, as much of it as possible should be used, i.e., 12 gallons. Then enough y, or 28 gallons, should be used to obtain the desired total quantity of 40 gallons.

Simplex Method:

In more realistic problems, a solution may not be obvious, especially if there are many ingredients each having constraints. A simple procedure is needed to generate an optimal solution no matter how complex the problem. The steps towards a solution in the cost minimization problem are similar to those taken in the contribution margin maximization example where the simplex method is used and slack variables are introduced in order to arrive at the first feasible solution which give a zero contribution margin.

I addition to the slack variables, a different type of variable known as and artificial variable is introduced. Artificial variables allow two types of restrictions or constraints to be treated: the equal-to type and the greater-than-or-equal-to type. Artificial variables are of value only as computational devices in maximization and minimization problems.

In this minimization problem, an artificial variable, a1, is introduced in the first constraint, which is of the equal-to type. A new equality is written as follow:

x + y + a1 = 40 gallons

The new ingredient, a1, must be thought of as a very expensive item which would not be part of the optimum solution. I a costs $999 per gallon, for example, 40 gallons would cost $39,960. This high cost is noted by the coefficient m in the objective function. (For a maximization problem, the notion of a very low contribution margin is denoted by the symbol -m.) This symbol is added merely to intimate the simplex method, since the constraint is already an equality.

The second constraint is the less-than-or-equal-to type, and a slack variable, s1, is added to form an equation: x + s1 = 12 gallons. The s1 represents the difference between 12 gallons of x and the actual number of gallons of x in the final solution.

The third constraint is the greater-than-or-equal-to type, and a variable s2, is introduced to form and equation: y - s2 = 10 gallons. The variable s2 must be thought of as the amount by which the actual number of gallons of y in the final solution must be reduced to arrive at 10 gallons. For example, if y should be 18 gallons, than s2 would be 8 gallons (18 - 8 = 10 gallons). However, if y appears in the first solution as 0, than 0 - s2 = 10 or s2 = -10. This equation is not feasible because -10 gallons of an ingredient is not possible. To prevent s2 from entering the first solution, in which only slack and artificial variables are introduced, a second artificial variable, a2, is utilized. Thus, y - s2 +a2 +10 gallons. Similar to a1, a high cost (m) is assigned to a2 in the objective function.

As a rule, there must be the same number of entries in the variable (mix) column as there are constraints. Before a2 is introduced in this example, there are three constraints, one artificial variable (a1), and two slack variables (s1 ands2), of which s2 has a negative coefficient. The introduction of the artificial variable, a2, gives a set of four variables, from which the three with positive coefficients (s1, a1, and a2) can be chosen to enter into the variable column of the first tableau.

The new cost equation is:

 C = 8x + 15y - 0s2 + ma1 +0s1 + ma2

For minimizing cost, the objective function must be multiplied by -1. This transformed function enters the first tableau as the objective row. the resulting equation is:

 C = - 8x - 15y + 0s2 - ma1 - 0s1 - ma2

The new constraints for the simplex solution are:
 
 

x + y +a1

x + s1

y - s2 + a2

=

=

=

40

12

10

The first tableau can be set up as shown below:
 
  Mix 0 -8 -15 0 -m 0 -m
Quantity x y s2 a1 s1 a2
-m a1 40 1 1 0 1 0 0
0 s1 12 1 0 0 0 1 0
-m a2 10 0 1 -1 0 0 1
    -50m -m+8 -2m+15 m 0 0 0
First simplex tableau and first solution

Explanation and Computations for the First Tableau:

The explanation of the arrangement is identical with that given for the first tableau of the maximization model. Observe that variables not included in a constraint are assigned zero coefficients in the problem rows. The index row is computed as follows:
 
Steps 1 and 2 Step 3
-m (40) + 0 (12) + (-m) (10) = -50m -50m - 0 = -50m
-m (1) + 0 (1) + (-m) (0) = -m -m - (-8) = -m + 8
-m (1) + 0 (0) + (-m) (1) = -2m -2m - (-15) = -2m + 15
-m (0) + 0 (0) + (-m) (-1) = m m - 0 = m
-m (1) + 0 (0) + (-m) (0)= -m -m - (-m) = 0
-m (0) + 0 (1) + (-m) (0) = 0 0 - 0 = 0
-m (0) + 0 (0) + (-m) (1)= -m -m - (-m) = 0

In the simplex method the optimum solution has not been reached if the index row carries any negative values (except for the quantity column which denotes total cost of this solution) at the completion of an iteration. Consequently, since negative values appear in the index row, the optimum solution has not been found, and a second tableau must be set up.

Explanation and Computation for the Second Tableau:

Since the objective is to minimize cost, the key column is found by selecting that column with the negative value having the highest absolute value in the index row, i.e., that variable whose value will most decrease cost. The index row shows only two negative values: -m + 8 and -2m + 15. Observe that the quantity column value in the index row, -50m, is not considered. This figure denotes total cost of this solution and is negative by convention. The negative number with the highest absolute value in the index row is -2m + 15; therefore, y is the key column. The row to be replaced, the key row, is a2, determined as follows:

a1 row, 40/1 = 40

s1 row, 12/0 is not considered (not defined mathematically)

a2 row, 10/1 = 10

Again, as in the maximization discussion, the smallest positive ratio identifies the equation which operates as the limiting constraint.

Since the key number (the crossing cell of the key column y and the key row a2) is 1, the values of the main row (y) do not change, as indicated by the following computations: 10/1 = 10; 0/1 = 0; 1/1 = 1; -1/1 = -1; 0/1 = 0; 0/1 = 0; and 1/1 = 1.

The values in the other rows are determined as follows:
 
a1 Row s1 Row
40 - 1 (10) = 30 12 - 0 (10) = 12
1 - 1 (0) = 1 1 - 0 (0) = 1
1 - 1 (1) = 0 0 - 0 (1) = 0
0 - 1 (-1) = 1 0 - 0 (-1) = 0
1 - 1 (0) = 1 0 - 0 (0) = 0
0 - 1 (0) = 0 1 - 0 (0) = 1
0 - 1 (1) = -1 0 - 0 (1) = 0
 

Index Row

Step 1 and 2 Step 3
-m (30) + 0 (12) + (-15) (10) = -30m - 150 (-30m - 150) - 0 = -30m - 150
-m (1) + 0 (1) + (-15) (0) = -m (-m) - (-8) = -m + 8
-m (0) + 0 (0) + (-15) (1) = - 150 (-15) - (-15) = 0
-m (1) + 0 (0) + (-15) (-1) = -m + 15 (-m + 15) - 0 = -m + 15
-m (1) + 0 (0) + (-15) (0) = -m (-m) - (-m) = 0
-m (0) + 0 (1) + (-15) (0) = 0 (0) - 0 = -m + 0
-m (-1) + 0 (0) + (-15) (1) = m - 15 (m - 15) - (-m) = 2m - 15

 

  Mix 0 -8 -15 0 -m 0 -m
Quantity x y s2 a1 s1 a2
-m a1 30 1 0 1 1 0 -1
0 s1 12 1 0 0 0 1 0
-15 y 10 0 1 -1 0 0 1
    -30m - 150 -m + 8 0 -m + 15 0 0 2m - 15
Second simplex tableau and second solution

Since negative values appear in the index row, excluding the quantity column, the optimum solution has not yet been found, and a third tableau must be set up.

Explanation and Computations for the Third Tableau:

Since -m + 8 is the negative number with the highest absolute value in the index row of the second tableau, x is the key column.

The row to be replaced, the key row, is s1, determined as follows:

a1 row, 30/1 = 30

s1 row, 12/1 = 12

y row, 10/0 not defined mathematically

The following computations determine the values in the x row that replaces the s1 row, as well as the values in the other rows:
 
x Row a1 Row y Row
12/1 = 12 30 - 1 (12) = 18 10 - 0 (12) = 10
1/1 = 1 1 - 1 (1) = 0 0 - 0 (1) = 0
0/1 = 0 0 - 1 (0) = 0 1 - 0 (0) = 1
0/1 = 0 1 - 1 (0) = 1 -1 - 0 (0) = -1
0/1 = 0 1 - 1 (0) = 1 0 - 0 (0) = 0
1/1 = 0 0 - 1 (1) = -1 0 - 0 (1) = 0
0/1 = 0 -1 - 1 (0) = -1 1 - 0 (0) = 0
   

Index Row

-m (18) + (-8) (12) + (-15) (10) = -18m - 246 (-18m - 246) - 0 = -18m - 246
-m (0) + (-8) (1) + (-15) (0) = -8 -8 - (-8) = 0
-m (0) + (-8) (0) + (-15) (1) = -15 -15 - (-15) = 0
-m (1) + (-8) (0) + (-15) (-1) = -m + 15 (-m + 15) - 0 = -m + 15
-m (1) + (-8) (0) + (-15) (0) = -m -m - (-m) = 0
-m (-1) + (-8) (1) + (-15) (0) = m - 8 (m - 8) - 0 = m - 8
-m (-1) + (-8) (0) + (-15) (1) = m - 15 (m - 15) - (-m) = 2m - 15
 
  Mix 0 -8 -15 0 -m 0 -m
Quantity x y s2 a1 s1 a2
-m a1 18 0 0 1 1 -1 -1
-8 x 12 1 0 0 0 1 0
-15 y 10 0 1 -1 0 0 1
    -18m - 246 0 0 -m + 15 0 m - 8 2m - 15
Third simplex tableau and third solution

Since a negative value, -m + 15 appears in the index row, excluding the quantity column, the optimum solution has not been found, and a fourth tableau must be set up.

Explanation and Computations for the Fourth Tableau:

Since -m +15 is the only negative number in the index row of the third tableau, excluding the quantity column, s2 is the key column.

The smallest positive ratio in the following computation identifies the row to be replaced as a1

a1 row, 18/1 = 18

x row, 12/0 is not defined mathematically

y row, 10/-1 = -10

The values in the s2 row (replacing the a1 row), the x row, and the index row are determined as follows:
 
s2 Row x Row y Row
18/1 = 18 12 - 0 (18) = 12 10 - (-1) (18) = 28
0/1 = 0 1 - 0 (0) = 1 0 - (-1) (0) = 0
0/1 = 0 0 - 0 (0) = 0 1 - (-1) (0) = 1
1/1 = 1 0 - 0 (1) = 0 -1 - (-1) (1) = 0
1/1 = 1 0 - 0 (1) = 0 0 - (-1) (1) = 1
-1/1 = -1 1 - 0 (-1) = 1 0 - (-1) (-1) = -1
-1/1 = -1 0 - 0 (-1) = 0 1 - (-1) (-1) = 0
   

Index Row

Step 1 and 2 Step 3
0 (18) + (-8) (12) + (-15) (28) = -516 -516 - 0 = -516
0 (0) + (-8) (1) + (-15) (0) = -8 -8 - (-8) = 0
0 (0) + (-8) (0) + (-15) (1) = -15 -15 - (-15) = 0
0 (1) + (-8) (0) + (-15) (0) = 0 0 - 0 = 0
0 (1) + (-8) (0) + (-15) (1) = -15 -15 - (-m) = m - 15
0 (-1) + (-8) (1) + (-15) (-1) = 7 7 - 0 = 7
0 (-1) + (-8) (0) + (-15) (0) = 0 0 - (-m) = m

 

  Mix 0 -8 -15 0 -m 0 -m
Quantity x y s2 a1 s1 s2
0 s2 18 0 0 1 1 -1 -1
-8 x 12 1 0 0 0 1 0
-15 y 28 0 1 0 1 -1 0
    -516 0 0 0 m - 15 7 m
Fourth simplex tableau and the optimal solution

No negative values remain in the index row of the fourth tableau, except the minimum cost figure which is negative (-516) by convention. The following optimum solution has been reached:
 
12 gals. of x @ $ 8 per gal. = $96  
28 gals. of y @ $15 per gal. = 420  
----- --------  
40 gals. of mixture $516 The lowest cost combination
  =====  

New Page 3

You may also be interested in other articles from "linear programming technique" chapter

  1. Linear Programming-Maximization of Contribution Margin-Graphical Method
  2. Linear Programming-Maximization of Contribution Margin-Simplex Method
  3. Linear Programming-Minimization of Cost-Graphical Method
  4. Linear Programming-Minimization of Cost-Simplex Method
  5. Shadow Prices
  6. Dynamic Programming
  7. Linear Programming Techniques-General Observations
  8. Linear Programming Questions and Answers
  9. Linear Programming Problems, Graphical and Simplex Method

 

Downloadable Materials

Learn Accounting Easily With AccountingCoach Pro

View Online or Download all of the materials to Your Computer and Print Immediately

What is Included in Accounting Book
Downloadable Self-Study Materials ( Available in Word Editable Format)
Help in preparation of Online Exams (Available in Word Editable Formatt)
Solved Accounting Problems
Bookkeeping and Financial Statements

Back to Home Page | Back to Linear Programming Technique Page

Managerial Accounting

 
Introduction to Managerial Accounting
Business and Quality Improvement Programs
Cost Terms, Concepts and Classification
Job Order Costing system
Process Costing System
Process Costing System - Addition of Materials & Beginning Inventory
Controlling and Costing Materials
Materials and Inventory Cost Control
By Products and Joint Products Costing
Cost-Volume-Profit-Relationship
Variable Costing System
Activity Based Costing System
Budgeting and Planning
Standard Costing and Variance Analysis
Gross Profit Analysis
Linear Programming Technique
Segment Reporting and Transfer Pricing
Capital Budgeting Decisions
Service Department Costing
Cash Flow statement
Financial statement Analysis
Pricing Products and Services
Managerial Accounting Terms and Definitions
Managerial / Cost Accounting Formulas

Financial Accounting

 
Bookkeeping and Bookkeeping Terms
Accounting Principles and Accounting Equation
Journal
Ledger
Accounting For Bills of Exchange
Subdivision of Journal
Final Accounts
Capital and Revenue Items
Single Entry System/Accounting From Incomplete Records
Accounting For Non-Trading Concerns
Accounting for Consignment / Consignment Accounts
Accounting for Joint Ventures
Accounting for Depreciation

About us !

 
Also see formula of gross margin ratio method with financial analysis, balance sheet and income statement analysis tutorials for free download on Accounting4Management.com.Accounting students can take help from Video lectures, handouts, helping materials, assignments solution, Online Quizzes, GDB, Past Papers, books and Solved problems. Also learn latest Accounting & management software technology with tips and tricks.

Home page   Download Material   Privacy policy   Disclaimer & terms of use   Contact us   Advertise with us   About us   Useful links   Link to us

Copyrights of all content on this web site are owned by Accounting For Management except where indicated in source or copyright statements. Accounting For Management must be contacted for permission to copy or redistribute any material published on this website.
Copyright 2014 Accounting For Management. All rights reserved.