PowerPoint Presentation · 2016-06-30 · Title: PowerPoint Presentation
PowerPoint Presentation (3036922)_2
-
Upload
naga-lakshmaiah -
Category
Documents
-
view
216 -
download
0
Transcript of PowerPoint Presentation (3036922)_2
-
8/22/2019 PowerPoint Presentation (3036922)_2
1/164
optimization methods using calculus have several limitations
and thus not suitable for many practical applications.
Linear programming is Most widely used constrained form of
optimization method which deals with nonnegativesolutions(x1= 0 , x2= 1/2 x3= 5) to determine system of linear
equations with corresponding finite value of the objective
function.
Linear Programming is required that all the mathematical
functions in the model be linear functions.
Linear Programming
-
8/22/2019 PowerPoint Presentation (3036922)_2
2/164
The term linear implies that the objective function and
constraints are linear functions of nonnegative decision
variables (e.g., no squared terms, trigonometric functions, ratios
of variables)
Linear programming (LP) techniques consist of a sequence of
steps that will lead to an optimal solution to problems, in cases
where an optimum exists
The term Linear is used to describe the proportionate
relationship of two or more variables in a model. The given
change in one variable will always cause a resulting proportional
change in another variable.
-
8/22/2019 PowerPoint Presentation (3036922)_2
3/164
Applications of Linear Programming
The number of applications of linear programming has been so large,
some of them are:
Scheduling of flight times of aero planes
Distribution of resources
Selection of shares and stocks
Assignment of jobs to people and many other problems
Scheduling of production in many manufacturing units or industries.
Use of available resources in an organization
Engineering design problems
Shipping & transportation
Product mix
Marketing research
Food processing etc.,
-
8/22/2019 PowerPoint Presentation (3036922)_2
4/164
Methods of Solving Linear Programming Problems
Trial and error: possible for very small problems; virtually
impossible for large problems.
Graphical or Geometrical approach : It is possible to solve a 2-
variable problem graphically to find the optimal solution (notshown).
Simplex Method: This is a mathematical approach developed by
George Dantzig. Can solve small problems by hand.
Computer Software : Most optimization software actually uses
the Simplex Method to solve the problems.
-
8/22/2019 PowerPoint Presentation (3036922)_2
5/164
Linearity: is a requirement of the model in both objective function
and constraints
Proportionality: Relationship between Outputs and inputs are
proportional
Additivity: Every function is the sum of individual contribution of
respective activities a1x1+a2x2
Divisibility: All decision variables are continuous (can take on any
non-negative value including fractional ones) x1=12, x2=3.8
Certainty or Deterministic: All the coefficients in the linear
programming models are assumed to be known exactly. a1=5, a2=2
Limitations of Linear Programming
The following will be the assumptions of linear programming
problem that limit its applicability.
-
8/22/2019 PowerPoint Presentation (3036922)_2
6/164
The conditions ofLP problems are
1. Objective function must be a linear function of
decision variables.
2. Constraints should be linear function of decision
variables.
3. All the decision variables must be nonnegative.
For example
example shown above is in general form
-
8/22/2019 PowerPoint Presentation (3036922)_2
7/164
There are mainly four steps in the mathematical formulation of
linear programming problem as a mathematical model.
Mathematical formulation of linear programming problem
Identify the decision variables and assign symbols x and y
to them. These decision variables are those quantities whose
values we wish to determine.
Identify the set of constraints and express them as linear
equations / in equations in terms of the decision variables.These constraints are the given conditions.
-
8/22/2019 PowerPoint Presentation (3036922)_2
8/164
Identify the objective function and express it as a linear
function of decision variables. It might take the form of
maximizing profit or production or minimizing cost.
Add the non-negativity restrictions on the decision
variables, as in the physical problems, negative values of
decision variables have no valid interpretation
Mathematical formulation of linear programming problem. .
-
8/22/2019 PowerPoint Presentation (3036922)_2
9/164
There are many real life situations where an LPP may be
formulated. The following examples will help to explain
the mathematical formulation of an LPP.
-
8/22/2019 PowerPoint Presentation (3036922)_2
10/164
Examples
-
8/22/2019 PowerPoint Presentation (3036922)_2
11/164
Example
A company makes cheap tables and chairsusing only wood and labor.
To make a chair requires 10 hoursof laborand20 board feet of wood.
To make a table requires 5 hours of laborand30 board feet of wood.
The profit per chair is $8 and $6 per table.
If it has 300 board feet of wood and 110 hoursof laboreach day, how many tables and chairsshould it make to maximize profits?
Objective
Constraints (Scarce Resources)
-
8/22/2019 PowerPoint Presentation (3036922)_2
12/164
Setting Up the Problem
Profits: $6 per table and $8 per chair
Total Profits = 6T + 8 C
Constraints: 300 feet of wood per day and
110 hours labor per day
Wood Use: 30 feet per table
20 feet per chair
Labor Use: 5 hours per table
10 hours per chair
-
8/22/2019 PowerPoint Presentation (3036922)_2
13/164
Writing the Equations
Objective: Maximize Z = 6T + 8CMaximum Profits = ($6 x # of tables) + ($8 x # of chairs)
Subject to: 30T + 20C < 300 board feet (wood constraint) 5T + 10C < 110 hours (labor constraint)
T,C > 0 (non-negativity)
Resources Requirements
Tables Chairs
Amount Available
Unit profit $6 $8
Wood(board feet)
Labor(hours)
30 20
5 10
300 board feet
110 hours
-
8/22/2019 PowerPoint Presentation (3036922)_2
14/164
Writing the Equations
Maximize Z = 6 T + 8 C
Subject to:
30 T + 20 C < 300 (wood constraint)
5 T + 10 C < 110 (labor constraint)
T, C > 0 (non-negativity)
Resources Requirements
Tables Chairs
Amount Available
Unit profit $6 $8
Wood(board feet)
Labor(hours)
30 20
5 10
300 board feet
110 hours
-
8/22/2019 PowerPoint Presentation (3036922)_2
15/164
Inequalities
A resource may constrain a problem bybeing . . .
Equal-to =
Equal-to or greater-than => or >
Equal-to or less-than =< or
Less-than 0
-
8/22/2019 PowerPoint Presentation (3036922)_2
17/164
SURPLUS VARIABLES
If the labor constraint was greater than orequal to the 110 hours; expressed as
5 T + 10 C > 110 hours
Then a surplus variable would be needed tomake it an equality.
5 T + 10 C - SL = 110 hours
SL represents the excess labor need, if any, above 110 hrs.
(Surplus variables cannot be negative so SL> 0)
-
8/22/2019 PowerPoint Presentation (3036922)_2
18/164
Reformulation of the examplewith Slack Variables added
Maximize Z = 6T + 8C
Subject to: 30T + 20C < 300 board feet of wood
5T + 10C < 110 hours of labor
Maximize Z = 6T + 8C
Subject to: 30T + 20C + SW = 300 board feet of wood
5T + 10C + SL = 110 hours of labor
T, C,SW, SL > 0
The L.P. model adds any needed slack and surplus variables. But, if theyare needed, they will appear in the program output. Below is how theprogram adds the slack variables.
-
8/22/2019 PowerPoint Presentation (3036922)_2
19/164
A company manufactures two products X and Y who se
prof i t co ntr ibut ions are Rs.10 and Rs. 20 respectively. Product X
requires 5 hou rs on machine I, 3 hours on machine II and2
hours on machine III. The requirement of product Y is 3 hou rs
on m achine I, 6 hours onmachine II and 5 hours on machine III.
The available capacities for the planning period for machine I, II
and III are 30, 36 and 20 hours respectively. Find the optimal
product mix.
-
8/22/2019 PowerPoint Presentation (3036922)_2
20/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
21/164
A diet is to contain at least 4000 units of carbohydrates, 500
units of fat and 300 units of protein. Two foods A and B are available.
Food A costs 2 dollars per unit and food B costs 4 dollars per unit. Aunit of food A contains 10 units of carbohydrates, 20 units of fat and
15 units of protein. A unit of food B contains 25 units of
carbohydrates, 10 units of fat and 20 units of protein. Formulate the
problem as an LPP so as to find the minimum cost for a diet that
consists of a mixture of these two foods and also meets the
minimum requirements.
The above information can be represented as
-
8/22/2019 PowerPoint Presentation (3036922)_2
22/164
Let the diet contain x units ofA and y units ofB.
Total cost = 2x + 4y
The LPP formulated for the given diet problem is
Minimize Z = 2x + 4y
subject to the constraints
-
8/22/2019 PowerPoint Presentation (3036922)_2
23/164
In the production of2 types of toys, a factory uses 3 machines A, B
and C. The time required to produce the first type of toy is 6 hours, 8 hours
and 12 hours in machines A, B and C respectively. The time required to
make the second type of toy is 8 hours, 4 hours and 4 hours in machines A,
B and C respectively. The maximum available time (in hours) for the
machines A, B, C are 380, 300 and 404 respectively. The profit on the first
type of toy is 5 dollars while that on the second type of toy is 3 dollars. Find
the number of toys of each type that should be produced to get maximum
profitThe data given in the problem can be represented in a table as follows.
-
8/22/2019 PowerPoint Presentation (3036922)_2
24/164
Let x = number of toys of type-I to be
produced
y = number of toys of the type - II to be
produced
Total profit = 5x + 3y
The LPP formulated for the given
problem is:
Maximize Z = 5x + 3y
subject to the constraints
-
8/22/2019 PowerPoint Presentation (3036922)_2
25/164
Standard form ofLP problems
Standard form of LP problems must have following three
characteristics:
1. Objective function should be ofmaximization type
2. All the constraints should be ofequality type
3. All the decision variables should be nonnegative
-
8/22/2019 PowerPoint Presentation (3036922)_2
26/164
Standard form
Standard form is a basic way of describing a LP problem.
It consists of 3 parts:
A linear function to be maximized
maximize c1x1 + c2x2 + + cnxn
Problem constraints
subject to a11x1 + a12x2 + + a1nxn< b1
a21x1 + a22x2 + + a2nxn< b2
am1x1 + am2x2 + + amnxn < bm
Non-negative variables
e.g. x1, x2>
0
-
8/22/2019 PowerPoint Presentation (3036922)_2
27/164
The problems is usually expressed in matrix form and then it
becomes:
maximize cTx
subject to ax < b, x > 0
where
X- Vector of decision variables
C- Objective function coefficients
a- Constraint coefficients
b- Right hand side of the constraint
-
8/22/2019 PowerPoint Presentation (3036922)_2
28/164
Other forms, such as minimization problems, problems withconstraints on alternative forms, as well as problems involving
negative variables can always be rewritten into an equivalent
problem in standard form.
-
8/22/2019 PowerPoint Presentation (3036922)_2
29/164
Any linear programming problem can be expressed in
standard form by using the following transformations.
1. The maximization of a function f (x1, x2, . . . , xn) is equivalent
to the minimization of the negative of the same function. For
example, the objective function
Consequently, the objective function can be stated in the
minimization form in any linear programming problem
-
8/22/2019 PowerPoint Presentation (3036922)_2
30/164
2. The decision variables represent some physical dimensions,
and hence the variables xj will be nonnegative. However, a
variable may be unrestricted in sign in some problems. In suchcases, an unrestricted variable (which can take a positive,
negative, or zero value) can be written as the difference of two
nonnegative variables. Thus if xj is unrestricted in sign, it can be
written as
xj = xj xj , where
It can be seen that xj will be negative, zero, or positive,
depending on whether xj is greater than, equal to, or less than
xj
-
8/22/2019 PowerPoint Presentation (3036922)_2
31/164
3. If a constraint appears in the form of a less than or equal
to type of inequality as
it can be converted into the equality form by adding anonnegative slack variable xn+1 as follows:
-
8/22/2019 PowerPoint Presentation (3036922)_2
32/164
Similarly, if the constraint is in the form of a greater than or
equal totype of inequality as
it can be converted into the equality form by subtracting a
variable as
where xn+1 is a nonnegative variable known as a surp lus
variable.
-
8/22/2019 PowerPoint Presentation (3036922)_2
33/164
Converting linear program in standard form into linear
program in slack form:
N
Each constraint aijxj bi is represented
j=1
N
as xN+i= bi - aijxj and xN+i 0.j=1
xN+i are basic variables, orslackvariables. The original set of
xi are non-basic variables.
-
8/22/2019 PowerPoint Presentation (3036922)_2
34/164
General form Vs Standard form
General form Violating points for standard
form ofLPP:
1.Objective function is of
minimization type.
2.Constraints are ofinequality
type.
3.Decision variable, x2, is
un restr icted, thu s, may take
negative values also.
How to transform a general form of a LPP to the standard form ?
-
8/22/2019 PowerPoint Presentation (3036922)_2
35/164
General form Transformation Standard form
General form
1.Objective function
Standard form
2. First constraint.
1.Objective function
3.Second constraint 3.Second constraint
2. First constraint.
-
8/22/2019 PowerPoint Presentation (3036922)_2
36/164
4.Third constraint 4.Third constraint
5. Constraints for decision
variables, x1and x2
5. Constraints for decision
variables, x1and x2
-
8/22/2019 PowerPoint Presentation (3036922)_2
37/164
Feasible solution. In a linear programming problem, any
solution that satisfies the constraints
is called a feasible solution
Basic solution. A basic solution is one in which n m variables are set
equal to zero. A basic solution can be obtained by setting n m variables to
zero and solving the constraint
simultaneously.
Basic Definitions
Basis. The collection of variables not set equal to zero to obtain the basic
solution is called the basis.
-
8/22/2019 PowerPoint Presentation (3036922)_2
38/164
Basic feasible solution. This is a basic solution that satisfies
the nonnegativity conditions of Eq.
Non-degenerate basic feasible solution. This is a basic
feasible solution that has got exactly m positive xi .
Optimal solution. A feasible solution that optimizes the
objective function is called an optimal solution
Optimal basic solution. This is a basic feasible solution for
which the objective function is optimal.
-
8/22/2019 PowerPoint Presentation (3036922)_2
39/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
40/164
Pivotal Operation
Operation at each step to eliminate one variable at a time, from
all equations except one, is known as pivotal operation.
Number of pivotal operations are same as the number of
variables in the set of equations.
-
8/22/2019 PowerPoint Presentation (3036922)_2
41/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
42/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
43/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
44/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
45/164
Note: Pivotal equation is transformed first and using the
transformed pivotal equation other equations in the system
are transformed.
The set of equations (A3, B3and C3) is said to be in Canonical
form which is equivalent to the original set of equations (A0,
B0and C0)
-
8/22/2019 PowerPoint Presentation (3036922)_2
46/164
Three pivotal operations were carried out to obtain the
canonical form of set of equations in last example having
three variables.
-
8/22/2019 PowerPoint Presentation (3036922)_2
47/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
48/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
49/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
50/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
51/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
52/164
Basic variable, Nonbasic variable,
Basic solution, Basic feasible solution
-
8/22/2019 PowerPoint Presentation (3036922)_2
53/164
Find all the basic solutions corresponding to the
system of equations
-
8/22/2019 PowerPoint Presentation (3036922)_2
54/164
Case 1
C 2
-
8/22/2019 PowerPoint Presentation (3036922)_2
55/164
Case 2
Case 3
-
8/22/2019 PowerPoint Presentation (3036922)_2
56/164
and x4 = 0 (nonbasic or independent variable). Since this
basic solution has all xj0 (j = 1, 2, 3, 4), it is a basic feasible
solution
From case 3
The solution obtained by setting the independent variable
equal to zero is called a basic solution
-
8/22/2019 PowerPoint Presentation (3036922)_2
57/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
58/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
59/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
60/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
61/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
62/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
63/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
64/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
65/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
66/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
67/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
68/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
69/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
70/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
71/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
72/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
73/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
74/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
75/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
76/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
77/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
78/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
79/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
80/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
81/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
82/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
83/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
84/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
85/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
86/164
Flowchart for finding
the optimal solution
by the simplex
algorithm.
-
8/22/2019 PowerPoint Presentation (3036922)_2
87/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
88/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
89/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
90/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
91/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
92/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
93/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
94/164
Note that while comparing ( 3 4M) and ( 5 3M), it is decided
that ( 3 4M)
-
8/22/2019 PowerPoint Presentation (3036922)_2
95/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
96/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
97/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
98/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
99/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
100/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
101/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
102/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
103/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
104/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
105/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
106/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
107/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
108/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
109/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
110/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
111/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
112/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
113/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
114/164
Carry out one iteration of the Revised Simplex Method
-
8/22/2019 PowerPoint Presentation (3036922)_2
115/164
Where c1=1, c2=9 and c3=1 are the cost coefficients of the given
objective function and
b=9
15
14
-
8/22/2019 PowerPoint Presentation (3036922)_2
116/164
Solution:
Standard from:
Coefficients of
S1 S2 S3 in the
-
8/22/2019 PowerPoint Presentation (3036922)_2
117/164
S1,S2,S3 in the
objective function CB
Initially B-1 is Unit matrix
Standard form constraints are written in matrix form
and represented each column as P1, P2, P3 and P4
-
8/22/2019 PowerPoint Presentation (3036922)_2
118/164
P1 P2 P3 P4
1 2 3 1
3 2 2 1
2 3 1 1Where c1,c2,c3 are the cost
coefficients of the given objective
function
-
8/22/2019 PowerPoint Presentation (3036922)_2
119/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
120/164
XB =
-
8/22/2019 PowerPoint Presentation (3036922)_2
121/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
122/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
123/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
124/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
125/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
126/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
127/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
128/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
129/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
130/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
131/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
132/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
133/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
134/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
135/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
136/164
The Practical Importance of Duality
D lit i i li ( d li ) ti i ti d l i
-
8/22/2019 PowerPoint Presentation (3036922)_2
137/164
Duality arises in nonlinear (and linear) optimization models in a
wide variety of settings.
Models of electrical networks. The current flows are primal
variables and the voltage differences are the dualvariables
that arise in consideration of optimization (and equilibrium) in
electrical networks.
Models of economic markets. In these models, the primal
variables are production levels and consumption levels, and the
dual variables are prices of goods and services
Structural design. In these models, the tensions on the beams are
primal variables, and the nodal displacements are the dual
variables.
Nonlinear (and linear) duality is very useful. For example,
dual problems and their solutions are used in connection with:
-
8/22/2019 PowerPoint Presentation (3036922)_2
138/164
Identifying near-optimal solutions. A good dual solution can be
used to bound the values of primal solutions, and so can be used
to actually identify when a primal solution is near-optimal.
Proving optimality. Using a strong duality theorem, one can prove
optimality of a primal solution by constructing a dual solution with
the same objective function value.
Sensitivity analysis of the primal problem. The dual variable on a
constraint represents the incremental change in the optimal
solution value per unit increase in the RHS of the constraint
Convergence of improvement algorithms. The dual problem isoften used in the convergence analysis of algorithms.
Other uses, too . . . .
-
8/22/2019 PowerPoint Presentation (3036922)_2
139/164
Dual Problem. As a definition, the dual problem can be
formulated by transposing the rows and columns including
the right-hand side and the objective function, reversing the
inequalities and maximizing instead of minimizing. Thus bydenoting the dual variables as y1, y2, . . . , ym, the dual
problem becomes
Primal Problem
-
8/22/2019 PowerPoint Presentation (3036922)_2
140/164
Dual Problem
-
8/22/2019 PowerPoint Presentation (3036922)_2
141/164
Rules for PrimalDual Relations
General Rules for Constructing Dual
-
8/22/2019 PowerPoint Presentation (3036922)_2
142/164
1. The number of variables in the dual problem is equal to the
number of constraints in the original (primal) problem. The
number of constraints in the dual problem is equal to thenumber of variables in the original problem.
2. Coefficient of the objective function in the dual problem come
from the right-hand side of the original problem.
3. If the original problem is a maxmodel, the dual is a minmodel; if
the original problem is a minmodel, the dual problem is the max
problem.
4. The coefficient of the first constraint function for the dual
problem are the coefficients of the first variable in the
constraints for the original problem, and the similarly for other
constraints.
5. The right-hand sides of the dual constraints come from the
objective function coefficients in the original problem.
General Rules for Constructing Dual ( Continued)
6 The sense of the ith constraint in the dual is = if and only if the ith
-
8/22/2019 PowerPoint Presentation (3036922)_2
143/164
6. The sense of the ith constraint in the dual is if and only if the ith
variable in the original problem is unrestricted in sign.
7. If the original problem is man (min ) model, then after applying Rule 6,assign to the remaining constraints in the dual a sense the same as
(opposite to ) the corresponding variables in the original problem.
8. The ith variable in the dual is unrestricted in sigh if and only if the ith
constraint in the original problem is an equality.
9. If the original problem is max (min) model, then after applying Rule 8,
assign to the remaining variables in the dual a sense opposite to (the
same as) the corresponding constraints in the original problem.
Max model Min modelxj 0 jth constraint xj
0 jth constraint xj free jth constraint =
ith const yi 0ith const yi 0ith const = yi free
-
8/22/2019 PowerPoint Presentation (3036922)_2
144/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
145/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
146/164
Write the dual of the following linear programming problem:
Maximize f = 50x1 + 100x2
-
8/22/2019 PowerPoint Presentation (3036922)_2
147/164
1 2
subject to
-
8/22/2019 PowerPoint Presentation (3036922)_2
148/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
149/164
If a linear programming problem has an optimal solution,
then its dual has an optimal solution and the optimal
values of the two problems coincide
-
8/22/2019 PowerPoint Presentation (3036922)_2
150/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
151/164
Duality Theorems
Theorem 1 The dual of the dual is the primal
-
8/22/2019 PowerPoint Presentation (3036922)_2
152/164
Theorem 1 The dual of the dual is the primal.
Theorem 2 Any feasible solution of the primal gives an f value
greater than or at least equal to the value obtained by any
feasible solution of the dual.
Theorem 3 If both primal and dual problems have feasible
solutions, both have optimal solutions and minimum
f = maximum .
Theorem 4 If either the primal or the dual problem has an
unbounded solution, the other problem is infeasible.
Dual Simplex Method
Computationally, the dual simplex algorithm also involves a
-
8/22/2019 PowerPoint Presentation (3036922)_2
153/164
sequence of pivot operations, but with different rules
(compared to the regular simplex method) for choosing thepivot element
-
8/22/2019 PowerPoint Presentation (3036922)_2
154/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
155/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
156/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
157/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
158/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
159/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
160/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
161/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
162/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
163/164
-
8/22/2019 PowerPoint Presentation (3036922)_2
164/164