Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

7.2 Formulating LP Problems

Formulating a linear program involves developing a mathematical model to represent the managerial problem. Thus, in order to formulate a linear program, it is necessary to completely understand the managerial problem being faced. Once this is understood, we can begin to develop the mathematical statement of the problem. The stpng in formulating a linear program follow:

Completely understand the managerial problem being faced.
Identify the objective and the constraints.
Define the decision variables.
Use the decision variables to write mathematical expressions for the objective function and the constraints.

One of the most common LP applications is the product mix problem. Two or more products are usually produced using limited resources such as personnel, machines, raw materials, and so on. The profit that the firm seeks to maximize is based on the profit contribution per unit of each product. (Profit contribution, you may recall, is just the selling price per unit minus the variable cost per unit.1) The company would like to determine how many units of each product it should produce so as to maximize overall profit given its limited resources. A problem of this type is formulated in the following example.

History The Beginning of Linear Programming

Prior to 1945, some conceptual problems regarding the allocation of scarce resources had been suggested by economists and others. Two of these people, Leonid Kantorovich and Tjalling Koopmans, shared the 1975 Nobel Prize in Economics for advancing the concepts of optimal planning in their work that began during the 1940s. In 1945, George Stigler proposed the “diet problem,” which is now the name given to a major category of linear programming applications. However, Stigler relied on heuristic techniques to find a good solution to this problem, as there was no method available to find the optimal solution.

Major progress in the field, however, took place in 1947, when George D. Dantzig, often called the “Father of Linear Programming,” published his work on the solution procedure known as the simplex algorithm. Dantzig had been an Air Force mathematician during World War II and was assigned to work on logistics problems. He saw that many problems involving limited resources and more than one demand could be set up in terms of a series of equations and inequalities, and he subsequently developed the simplex algorithm for solving these problems.

Although early applications of linear programming were military in nature, industrial applications rapidly became apparent with the widespread use of business computers. As problems became larger, research continued to find even better ways to solve linear programs. The work of Leonid Khachiyan in 1979 and Narendra Karmarkar in 1984 spurred others to study the use of interior point methods for solving linear programs, some of which are used today. However, the simplex algorithm developed by Dantzig is still the basis for much of the software used for solving linear programs today.

Source: Trevor S. Hale.

Flair Furniture Company

The Flair Furniture Company produces inexpensive tables and chairs. The production process for each is similar in that both require a certain number of hours of carpentry work and a certain number of labor hours in the painting and varnishing department. Each table takes 4 hours of carpentry and 2 hours in the painting and varnishing shop. Each chair requires 3 hours in carpentry and 1 hour in painting and varnishing. During the current production period, 240 hours of carpentry time are available, and 100 hours in painting and varnishing time are available. Each table sold yields a profit of $70; each chair produced is sold for a $50 profit.

Flair Furniture’s problem is to determine the best possible combination of tables and chairs to manufacture in order to reach the maximum profit. The firm would like this production mix situation formulated as an LP problem.

We begin by summarizing the information needed to formulate and solve this problem (see Table 7.2). This helps us understand the problem being faced. Next, we identify the objective and the constraints. The objective is

Table 7.2 Flair Furniture Company Data

	HOURS REQUIRED TO PRODUCE 1 UNIT
DEPARTMENT	TABLES (T)	>CHAIRS (C)	>AVAILABLE HOURS THIS WEEK
Carpentry	4	3	240
Painting and varnishing	2	1	100
Profit per unit	$70	$50

Maximize profit

$Maximize profit$

The constraints are

The hours of carpentry time used cannot exceed 240 hours per week.
The hours of painting and varnishing time used cannot exceed 100 hours per week.

The decision variables that represent the actual decisions we will make are defined as

\begin{array}{l} T & = & number of tables to be produced per week \\ C & = & number of chairs to be produced per week \end{array}

$\begin{array}{l} T & = & number of tables to be produced per week \\ C & = & number of chairs to be produced per week \end{array}$

Now we can create the LP objective function in terms of T and C. The objective function is Maximize $profit = $ 70 T + $ 50 C .$ $profit = $ 70 T + $ 50 C .$

Our next step is to develop mathematical relationships to describe the two constraints in this problem. One general relationship is that the amount of a resource used is to be less than or equal to $(\leq)$ $(\leq)$ the amount of the resource available.

In the case of the carpentry department, the total time used is

\begin{array}{l} (4 hours per table)(Number of tables produced) \\ + (3 hours per chair)(Number of chairs produced) \end{array}

$\begin{array}{l} (4 hours per table)(Number of tables produced) \\ + (3 hours per chair)(Number of chairs produced) \end{array}$

So the first constraint may be stated as follows:

\begin{array}{l} Carpentry time used \leq Carpentry time available \\ 4 T + 3 C \leq 240 (hours of carpentry time) \end{array}

$\begin{array}{l} Carpentry time used \leq Carpentry time available \\ 4 T + 3 C \leq 240 (hours of carpentry time) \end{array}$

Similarly, the second constraint is as follows:

Painting and varnishing time used ≤ Painting and varnishing time available

An image shows the constraint as the sum of 2 times “T” and 1 times “C” is less than or equal to 100 hours of painting and varnishing time.

7.2-3 Full Alternative Text

Both of these constraints represent production capacity restrictions and, of course, affect the total profit. For example, Flair Furniture cannot produce 80 tables during the production period because if $T = 80,$ $T = 80,$ both constraints will be violated. It also cannot make $T = 50$ $T = 50$ tables and $C = 10$ $C = 10$ chairs. Why? Because this would violate the second constraint: that no more than 100 hours of painting and varnishing time can be allocated.

To obtain meaningful solutions, the values for T and C must be nonnegative numbers. That is, all potential solutions must represent real tables and real chairs. Mathematically, this means that

\begin{array}{l} T \geq 0 (number of tables produced is greater than or equal to 0) \\ C \geq 0 (number of chairs produced is greater than or equal to 0) \end{array}

$\begin{array}{l} T \geq 0 (number of tables produced is greater than or equal to 0) \\ C \geq 0 (number of chairs produced is greater than or equal to 0) \end{array}$

The complete problem may now be restated mathematically as

Maximize profit = $ 70 T + $ 50 C

$Maximize profit = $ 70 T + $ 50 C$

subject to the constraints

\begin{array}{l} 4 T + 3 C & \leq & 240 & (carpentry constraint) \\ 2 T + 1C & \leq & 100 & (painting and varnishing constraint) \\ T & \geq & 0 & (first nonnegativity constraint) \\ C & \geq & 0 & (second nonnegativity constraint) \end{array}

$\begin{array}{l} 4 T + 3 C & \leq & 240 & (carpentry constraint) \\ 2 T + 1C & \leq & 100 & (painting and varnishing constraint) \\ T & \geq & 0 & (first nonnegativity constraint) \\ C & \geq & 0 & (second nonnegativity constraint) \end{array}$

While the nonnegativity constraints are technically separate constraints, they are often written on a single line with the variables separated by commas. In this example, this would be written as

T, C \geq 0

$T, C \geq 0$

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 7.2 Formulating LP Problems

Create new playlist

Sign In

Sign Up

Table of Contents for
7.2 Formulating LP Problems