Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
888411 OPERATIONS
RESEARCH FOR DIGITAL
INNOVATION
LINEAR PROGRAMMING I
Introduction to Linear Programming
The most common type of application involves the general problem of allocating
limited resources among competing activities in a best possible way
Introduction to Linear Programming
The adjective linear means that all the mathematical functions in this model are
required to be linear functions.
Introduction to Linear Programming
The adjective linear means that all the mathematical functions in this model are
required to be linear functions.
PROTOTYPE EXAMPLE
The WYNDOR GLASS CO. produces high-quality glass products, including windows and
glass doors. It has three plants. Aluminum frames and hardware are made in Plant 1, wood
frames are made in Plant 2, and Plant 3 produces the glass and assembles the products.
Plant 1 Plant 2 Plant 3
PROTOTYPE EXAMPLE
top management has decided to revamp the company’s product line. Unprofitable products are
being discontinued, releasing production capacity to launch two new products having large sales
potential:
Product 1: An 8-foot glass door with aluminum framing
Product 2: A 4 x 6 foot double-hung wood-framed window
Product 1 Product 2
PROTOTYPE EXAMPLE
Product 1 need only plant 1 and 3. Product 2: need only plant 2 and 3.
The marketing division has concluded that the company could sell as much of either
product as could be produced by these plants
Determine what the production rates should be for the two products in order to maximize
their total profit, subject to the restrictions imposed by the limited production capacities
available in the three plants.
PROTOTYPE EXAMPLE
The OR team also identified the data that needed to be gathered:
• Number of hours of production time available per week in each plant for these
new products.
• Number of hours of production time used in each plant for each batch
produced of each new product.
• Profit per batch produced of each new product
Obtaining reasonable estimates of these quantities required enlisting the help of key
personnel in various units of the company
PROTOTYPE EXAMPLE
PROTOTYPE EXAMPLE: Formulation as a Linear Programming Problem
Let assign variables as follows:
The objective is to choose the values of and so as to maximize = +
PROTOTYPE EXAMPLE: Formulation as a Linear Programming Problem
Objective Function
Functional Constraints
Nonnegativity Constraints
https://www.geogebra.org/m/epfhezbp
PROTOTYPE EXAMPLE: Graphical Solution
Find the feasible region. The resulting region of permissible values of
PROTOTYPE EXAMPLE: Graphical Solution
Find slope-intercept form of the objective function.
PROTOTYPE EXAMPLE: Graphical Solution
Move the ruler with fixed slope through the feasible region in the direction of improving Z.
(When the objective is to minimize Z, move the ruler in the direction that decreases Z.)
Stop moving the ruler at the last instant that it still passes through a point in this region.
This point is the desired optimal solution.
PROTOTYPE EXAMPLE: Conclusion
This solution indicates that the Wyndor Glass Co. should produce products 1 and
2 at the rate of 2 batches per week and 6 batches per week, respectively, with a resulting
total profit of $36,000 per week. No other mix of the two products would be so profitable—
according to the model.
Are we finished?
No! this is just the step 2 out of 6 steps
Let’s Try!
https://www.geogebra.org/graphing
Suppose that the profit per batch of product 2 is change to $2,000. What is the optimal
produce rate for product 1 and product 2 to gain maximize profit?
The Weakness of Graphical method in Linear programming
It can be used to solve any linear programming problem with two decision variables. With
considerable difficulty, it is possible to extend the method to three decision variables but
not more than three.
The algorithm for this method is take too much resource from computer.
The Linear Programming Model
The Linear Programming Model
Let assign variables as follows:
The Linear Programming Model: A Standard Form of the Model
Objective Function
Functional Constraints
Nonnegativity Constraints
The Linear Programming Model: A Standard Form of the Model
The Linear Programming Model: Other Forms
How we use Graphical method?
What is the weakness of graphical method?
Recap questions:
Terminology for Solutions of the Model
A solution: any specification of values for the decision variables (1, 2, … , ), regardless of
whether it is a desirable or even an allowable choice.
A feasible solution is a solution for which all the constraints are satisfied.
An infeasible solution is a solution for which at least one constraint is violated.
Terminology for Solutions of the Model
An optimal solution is a feasible solution that has the most favorable value of
the objective function.
It is possible to have no feasible solution or have more than one optimal solution.
Terminology for Solutions of the Model
Is it possible to have feasible region but have no optimal solution?
Terminology for Solutions of the Model
A corner-point feasible (CPF) solution is a solution that lies at a corner of the
feasible region.
Terminology for Solutions of the Model
Relationship between optimal solutions and CPF solutions: Consider any linear
programming problem with feasible solutions and a bounded feasible region. The problem
must possess CPF solutions and at least one optimal solution.
Furthermore, the best CPF solution must be an optimal solution. Thus, if a problem has
exactly one optimal solution, it must be a CPF solution. If the problem has multiple
optimal solutions, at least two must be CPF solutions.
Assumptions of Linear Programming
We need to see why the OR team for the Wyndor Glass Co. concluded that a linear
programming formulation provided a satisfactory representation of the problem.
• Proportionality
• Additivity
• Divisibility
• Certainty
Assumptions of Linear Programming: Proportionality
Proportionality assumption: The contribution of each activity to the value of
the objective function is proportional to the level of the activity .
Similarly, the contribution of each activity to the left-hand side of each functional
constraint is proportional to the level of the activity .
Assumptions of Linear Programming: Proportionality
-1
Assumptions of Linear Programming: Proportionality
Assumptions of Linear Programming: Proportionality
-1
Assumptions of Linear Programming: Proportionality
This violation of proportionality might occur because of economies of scale that can
sometimes be achieved at higher levels of production.
Assumptions of Linear Programming: Proportionality
-1
Assumptions of Linear Programming: Proportionality
It might be possible to sell product 1 at the rate of 1 per week with no advertising, whereas
attaining sales to sustain a production rate of 2 might require a moderate amount of advertising.
Assumptions of Linear Programming: Additivity
Additivity assumption: Every function in a linear programming model (whether
the objective function or the function on the left-hand side of a functional constraint)
is the sum of the individual contributions of the respective activities.
Assumptions of Linear Programming: Additivity
This case would arise if the two products were complementary in some way that increases profit.
Assumptions of Linear Programming: Additivity
This case would arise if the two products were competitive in some way that decreased their
joint profit.
Assumptions of Linear Programming: Additivity
Assumptions of Linear Programming: Additivity
extra time is wasted switching the production processes back
and forth between the two products.
Assumptions of Linear Programming: Additivity
Because each product goes through a sequence of production operations, individual production
facilities normally dedicated to that product would incur occasional idle periods. During these
otherwise idle periods, these facilities can be used by the other product.
Assumptions of Linear Programming: Divisibility
Divisibility assumption: Decision variables in a linear programming model are
allowed to have any values, including noninteger values, that satisfy the functional
and nonnegativity constraints. Since each decision variable represents the level of some
activity, it is being assumed that the activities can be run at fractional levels.
In certain situations, the divisibility assumption does not hold because some of or all
the decision variables must be restricted to integer values.
Assumptions of Linear Programming: Certainty
Certainty assumption: The value assigned to each parameter of a linear programming
model is assumed to be a known constant.
The Assumptions in Perspective
• It is very common in real applications of linear programming that almost none of the four
assumptions hold completely.
• This is especially true for the certainty assumption, so sensitivity analysis normally is a must to
compensate for the violation of this assumption.
• However, it is important for the OR team to examine the four assumptions for the problem
under study and to analyze just how large the disparities are.
• If any of the assumptions are violated in a major way, then use other models.
• For some applications, the powerful linear programming approach is used for the initial analysis,
and then a more complicated model is used to refine this analysis.
Additional Examples: Radiation therapy
Mary has just been diagnosed as having a cancer at a fairly advanced stage. Specifically,
she has a large malignant tumor in the bladder area.
Mary is to receive the most advanced medical care
available to give her every possible chance for survival.
This care will include extensive radiation therapy
The two decision variables 1 and 2 represent the dose (in kilorads) at the entry point for beam 1
and beam 2, respectively. Because the total dosage reaching the healthy anatomy is to be
minimized, let Z denote this quantity.
Additional Examples: Radiation therapy
Additional Examples: Radiation therapy
Additional Examples: Radiation therapy
Additional Examples: Regional Planning
The SOUTHERN CONFEDERATION OF KIBBUTZIM currently is planning agricultural production
for the coming year.
Sugar beets Cotton Sorghum
Additional Examples: Regional Planning
Additional Examples: Regional Planning
Additional Examples: Regional Planning
What are assumptions of linear programming?
Why, in some case, we still use linear programming model
even though many assumptions are violated?