Linear Programming

Operations Management

Linear Programming

Linear Programming is considered a method used to optimize, that is minimize or maximize, operations or processes that includes some constraints.

​

Using this model, we will probably find multiple solutions; it is important to choose the optimal.

Linear Programming

All Operation Research models, Linear Programming included, consist of three basic components:

​

1. Decision variables that we seek to determine.
2. Objective (goal) that we need to optimize (maximize or minimize).
3. Constraints that the solution must satisfy.

Linear Programming

Any values that satisfy all the constraints determined in the model, constitute feasible solution. Otherwise, the solution is infeasible.

​

The goal of the problem is to find the optimum, the best feasible solution that maximize or minimize according to the environment.

​

The objective and the constraint function in all Linear Programming must be linear. Additionally, all the parameters of the model are known with certainty.

Linear Programming

Objective: Considered as the objective function is given by a linear model.

​

4x + 7y = u

​

Constraints: Also known as inequations are used also as linear into the model.

6x + 14y < 70

x > 0

y > 0

Linear Programming

6x + 14y < 70

4x + 7y = u

6x + 14y < 70

x > 0

y > 0

Linear Programming – Example 1

Reddy Mikks produces both interior and exterior paints from two raw materials, M1 and M2. The following table provides the basic data of the problem:

Linear Programming – Example 1

The daily demand for interior paint cannot exceed that for exterior paint by more than 1 ton. Also, the maximum daily demand for interior paint is 2 tons.

​

Reddy Mikks wants to determine the optimum (best) product mix of interior and exterior paints that maximizes the total daily profit.

Linear Programming – Example 1

For the Reddy Mikks problem, we need to determine the daily amounts of exterior and interior paints to be produced. Thus the variables of the models are defined as:

​

x1 = Tons produced daily of exterior paint.

x2 = Tons produced daily of interior paint.

​

The goal of Reddy Mikks is to maximize (i.e., increase as much as possible) the total daily profit of both paints.

Linear Programming – Example 1

The two components of the total daily profit are expressed in terms of the variables x1 and x2 as:

Profit from exterior paint = 5x1 (thousand) dollars.

Profit from interior paint = 4x2 (thousand) dollars.

​

Letting z represent the total daily profit (in thousands of dollars), the objective (or goal) is expressed as

​

Maximize z = 5x1 + 4x2

​

Linear Programming – Example 1

The complete Reddy Mikks model is:

Maximize z = 5x1 + 4x2

Subject to

​

6x1 + 4x2 < 24 (1)

x1 + 2x2 < 6 (2)

-x1 + x2 < 1(3)

x2 < 2 (4)

x1 > 0 (5)

x2 > 0 (6)

Linear Programming – Example 1

The complete Reddy Mikks model is:

Maximize z = 5x1 + 4x2

Solutions:

​

6x1 + 4x2 < 24 (1)

x1 + 2x2 < 6 (2)

-x1 + x2 < 1(3)

x2 < 2 (4)

x1 > 0 (5)

x2 > 0 (6)

Linear Programming

Operations Management

Linear Programming – Example 2

Ozark Farms uses at least 800 lb of special feed daily. The special feed is a mixture of corn and soybean meal with the following compositions:

Linear Programming – Example 2

The dietary requirements of the special feed are at least 30% protein and at most 5% fiber. The goal is to determine the daily minimum-cost feed mix.

The decision variables of the model are:

​

x1 = lb of corn in the daily mix

x2 = lb of soybean meal in the daily mix

Linear Programming – Example 2

The objective is to minimize the total daily cost (in dollars) of the feed mix – that is,

​

Minimize z = .3x1 + .9x2

​

The constraints represent the daily amount of the mix and the dietary requirements. Ozark Farms needs at least 800 lb of feed a day:

​

x1 + x2 > 800

​

​

Linear Programming – Example 2

The amount of protein included in x1 lb of corn and x2 lb of soybean meal is (0.09x1 + 0.6x2) lb.

This quantity should equal at least 30% of the total feed mix (x1 + x2)lb,

​

0.09x1 + 0.6x2 > .3(x1 + x2)

​

In a similar manner, the fiber requirement of at most 5% is represented

​

0.02x1 + 0.06x2 < 0.05(x1 + x2)

​

Linear Programming – Example 2

The constraints are simplified by moving the term in x1 and x2 to the left-hand side of each inequality, leaving only a constant on the right side. The complete model is

Minimize z = .3x1 + .9x2

Subject to

​

​

​

x1 + x2 > 800

0.09x1 + 0.6x2 > 240

0.02x1 + 0.06x2 < 40

x1 > 0

x2 > 0

Linear Programming – Example 2

The complete model is

Minimize z = .3x1 + .9x2

Subject to

​

​

​

x1 + x2 > 800

0.09x1 + 0.6x2 > 240

0.02x1 + 0.06x2 < 40

x1 > 0

x2 > 0

Linear Programming – Example 2

The complete model is

Minimize z = .3x1 + .9x2

Solutions

​

​

​

x1 + x2 > 800

0.09x1 + 0.6x2 > 240

0.02x1 + 0.06x2 < 40

x1 > 0

x2 > 0