OPERATIONS RESEARCH I

Goal Setting

NatoinaU
l nvierstiy
Engniernig
 Objectives

1. Correctly define a problem of

goal programming

2. Programming for goals with

weights
3. Goal-oriented programming with priorities
GOAL SETTING

EXAMPLE 1 (Tax Planning):

Abancay it is a small city with a population of
approximately 20,000 inhabitants. The annual tax base
the property tax amounts to $550 million. The
annual collections for food and medicine as well as
for sales general it is of $35 y $55 millions
respectively.

The annual consumption of local gasoline is estimated at 7.5.

millions of gallons. The city council wishes to develop
the tax rates based on four main goals:
Tax revenues must be at least $16 millions
to meet financial commitments from the city.

2. Taxes on food and medicine should not exceed

10% of all the taxes collected.

3. General sales taxes should not exceed

20% from all the collected taxes.

The gasoline tax should not exceed 2 cents.

per gallon.
SOLUTION:

Definition of Decision Variables:

Xp: number of property tax rates

Xa: amount of tax rates on food and the
medicines
Xv: amount of rates tax related about the sales
generals
Xg quantity of rates taxes about the gasoline in
cents per gallon.
Restrictions:

The goals of the municipal council are expressed as:

Tax revenues: They are calculated as follows:

550xp(Associating the property tax with variable xp)

35xa(Associating the collections for food and
the medicines to the variable xa)
55xv(Associating the revenues from the sales to the
variable xv)
0.075xg(Associating the revenues from consumption of
gasoline in cents per gallon (7.5/100=0.075) to the
variable xg)
>=16 (Like in the problem us dice For the less "
we use the greater than or equal restriction.
Leaving the restriction for the property tax:
550x + 35x + 55x + 0.075x >=16
Restrictions:

Taxes on food and medicine: They are calculated as follows

form:

They tell us that taxes on food and medicines (35xa) they should not
exceed 10% of all the taxes collected
All collected taxes are:
550xp+ 35xa+ 55xv+ 0.075xg
Its 10% is:
0.1(550xp+ 35xa+ 55xv+ 0.075xg)
As they must not exceed, use the less than or equal to (<=) restriction and
the restriction would be as follows:
35xa <= 0.1(550xp+ 35xa+ 55xv+ 0.075xg)
35xa<= 55xp+ 3.5xa+ 5.5xv+ 0.0075xg
0 <= 55xp-31.5xa+ 5.5xv+ 0.0075xg
Restrictions:

Sales taxes: They are calculated as follows:

They tell us that sales taxes (55xvshould not exceed 20%

from all collected taxes
All collected taxes are:
550 timesp+ 35xa+ 55xv+ 0.075xg
Its 20% is:
0.2(550xp+ 35xa+ 55xv+ 0.075xg)
Since they should not exceed, the less than or equal to (<=) restriction should be used and
the restriction would be as follows:
55xv<= 0.2(550xp+ 35xa+ 55xv+ 0.075xg)
55xv<= 110xp+ 7xa+ 11xv+ 0.015xg
0 <= 110xp+ 7xa- 44xv+ 0.015xg
Restrictions:

Gasoline tax: It is calculated as follows:

They tell us that taxes on gasoline (xgthey should not exceed 2

cents per gallon
Like the variablexgit's in cents we have:

xg <= 2

No negativity: These variables such as tax rates cannot

be negative:

XpXa, Xv, Xggreater than or equal to zero

These restrictions are then simplified as:
550xp+ 35xa+ 55xv+0.075xg >= 16
55xp- 31.5xa+ 5.5xv+0.0075xg>= 0
110xp + 7xa- 44xv+0.015xg >= 0
xg <= 2
Xp, Xa, Xv, Xg>=0

Each a of the inequalities del model represents one meta what the
the municipal council aims to satisfy. It is very likely, however,
that the best that can be done is a compromise solution that
involves these conflicting goals.
The way goal setting determines a solution
commitment is to turn every inequality into a flexible goal in the
what restriction could be violated, if it is
necessary. Based on the Abancay model, the flexible goals are
they express as follows:

550xp+ 35xa+ 55xv+0.075xg+S1 - S1 = 16- +

55xp- 31.5xa+ 5.5xv+0.0075xg+S2 - S2 =- 0 +

110xp+ 7xa- 44xv+0.015xg+S3 - S3 = 0 - +

xg+S4 - S4 = 2 - +

Xp, Xa, Xv, Xg>=0

Si-y SI >=0;
+
i=1, 2, 3, 4
The variables no negatives S i y S-i , i= 1+2, 3, 4 are variables
of deviation represented by the deviations below and above
arriving from the right side of the restriction.
The variables of deviation Si y Si ,- their + dependents by
definition y of there what no they can be the variables basics to
same time (according to the simplex method theory).
This means what in any iteration simplex no more right away of
the two deviation variables can take a positive value. If
the original inequality is of the type <= and its Si >=0,
-
then
he satisfies the meta i-th in case contrary, no be satisfies the
year.
In essence, the definition of S-i and +Si , allows to satisfy or violate the
meta i-th at will. This is the type of flexibility that
characterizes a the programming of goals when he search one solution
commitment. Logically, one good solution commitment search
minimize the amount by which each goal is violated.
Objective Function:

In the Abancay model, given that the first three constraints

are of the type >= and the fourth is of the type <=, the variables of
deviation S1 ,- S2 ,- S3 y - S 4 represent
+
the amounts for which
the respective goals are violated. Therefore, the solution
commitment seeks to satisfy the following as much as possible
four objectives:

Minimize G1 = s1 -

Minimize G2 = s2 -

Minimize G3 = s3 -

Minimize G4 = s4 +
In cute:

We present the model as follows:

Min S11+ S 21+ S31+ S 42

st
550 timesp+ 35xa+ 55xv+0.075xg+S11S1216
55xp31.5 timesa+ 5.5xv+0.0075xg+S21S22= 0
110xp+ 7xa- 44xv+0.015xg +S31- S32= 0
xg +S41- S42 =2

Because Lindo does not recognize the signs + and - in the variables. It was replaced with
minus sign '-' for 1 and plus sign '+' for 2.
In beautiful

We obtain the following result:

Interpretation:

Like the values of S12=0, S22=1.6, S32=3.2, y S41They are older or

Those equal to zero satisfy the goals. And the objective function is zero.
all the goals are met

In conclusion, the tax rates that meet the goals are:

For the properties (xp) = 0.029

For food and medicines (xa) = 0
For sales (xv) = 0
For gasoline (xg) = 2
Are you functions if minimize hold a the equations of
model restriction.
How can we optimize a multi-objective model with goals
conflictive? To this end, two methods were developed for the
following cases:

Goal programming with weights (Weighted method).

(2) Goal programming with priorities (Preventive Method).

Both methods are based on the conversion of multiple objectives.

in a single function.
 GOAL PROGRAMMING ALGORITHMS

In the weighting method, the unique objective function is the sum

weighted of the functions what represent the goals del problem.
The preventive method starts by prioritizing goals in order of
importancia. Luego, the model optimizes the goals of a in one in
the order of priority so that it does not degrade a solution further
high priority.

Usually, the two proposed methods do not exhibit the same

solution.
None of the methods, however, is superior to the other because the
two techniques presuppose different preferences in decision making
decisions.
WEIGHT METHOD

Suppose what the model of programming of goals he/she has n goals y what
the meta-ith is given as:
Minimize Gi, i = 1, 2,…, n
The combined objective function used in the weighted method
define then as:
Minimize z = w1G1+ w2G2+ … + wnGn
The parameters wii = 1, 2,...,n are positive weights that reflect
the preferences of decision-making regarding the
importance relative of each meta. For example, w i = 1 for all
the I, means what all the goals they have one same importance.
The determination of the specific values of these weights is
subjective.
EXAMPLE 2: TopAd, one new agency of advertising with 10 employees,
signed a contract for promote one new product. The agency can
advertising on radio and television. The following table
provides the quantity of people achieved daily for each
type of announcement advertising, like this how the requirements of costs
and labor. The contract prohibits TopAd from using more than 6
minutes of advertising on the radio.
Radio Television
Exhibition (in millions of
people/min 4 8
Cost (in thousands of dollars)/min 8 24
Employees assigned/min 1 2

In addition, radio and television commercials must reach the

less than 45 million people. TopAd has a budget goal
from $100,000 for the project.
How many minutes of radio and television ads should be used?
TopAd?
SOLUTION:
Sean x1 y x2 the minutes assigned to radio announcements and
television. The formulation of goal programming for the
the problem is presented as:

MinimizeG1 = -Si Meet- ( the exposure goal

MinimizeG2 = +Si (Meet
+
the budget target)

Subject to:
4x1+ 8x2+ s1 - -s1 +
= 45 (Exposure goal)
8x1+ 24x2+ s2 - -s2 = 100(Budget
+
target)
x1+ 2x2 ≤ 10 (Staff limit)
x1 <= 6 (Radius limit)
x1, x2, s1-, s1 ,
+
s2 ,- s2 greater
+
than or equal to 0
The management of TopAd estimate what the meta of exhibition It is two times
more important than the budget goal. Therefore, the function
combined objective becomes:

Minimize z = 2G1+ G2= 2s1 + s-2 +

The optimal solution is Z= 10, x1= 5 minutes, x22.5 minutes, s1 =- 5

millions of people1 =0, -s2 =0 -

The fact that the optimal value of z is not zero indicates that at least
one of the goals is not met.
Specifically, s1 =5 means
-
that the exposure target (of to
less 45 million people) fails by 5 million people. For
Another part, the budget goal (not to exceed $100,000) is not
viola because s+2 =0.
Comments. The programming of goals search only one solution
efficient, more than optimal, to the problem.
For example, the solution x1 = 6 and x2 = 2 produces the same
(4 x 6 + 8 x 2) = 40 million people) but
slope less (8 x 6 + 24 x 2) = $96,000). In essence, the what
goal programming finds a solution that
satisfy the goals of the model without taking into account the
optimization. The failure to find the optimal solution raises
doubts about the viability of goal programming as a
optimization technique.
PREVENTIVE METHOD

In this type of method, the decision-maker classifies the

Goals of the problem in order of importance. Given a situation...
goals, the objectives of the problem are written as
Minimize G1 = ρ1(Highest priority)
.
.
.
Minimize Gn = ρn(Minimal priority)
The variable ρiit is the component of the deviation variables, si o-
si+what represent the meta i. For example, in the model of TopAd,
ρi= s1 y- ρ2= s2 . +
PREVENTIVE METHOD

The solution procedure begins with the optimization of the

top priority,G1, and ends with the optimization of the priority
minimum, GnThe preventive method is designed so that a
a lower priority solution should never degrade a higher priority solution
priority.
The literature on goal programming presents a method
special simplex that guarantees the non-degradation of solutions of
high priority. The method uses the elimination rule of
columns what exige delete a variable xj no basic with a cost
reduced different from zero - cj ≠ 0) of the optimal table of
goals Gk before solving the problem of the G goalk+1The rule
recognize that such non-basic variables, if they rise above
from level zero in the optimization of subsequent goals, they can
degrade (but never improve) the quality of a higher goal
priority.
PREVENTIVE METHOD

The procedure requires including the objective functions of all

the goals in the simplex table of the model.
The proposed modification to remove columns complicates without
need the programming of goals. In this presentation
we demonstrate that the same results can be achieved from one
simplest way by following these steps:

Step 0. Identify the goals of the model and classify them in order
of priority:
G1 = ρ1G2 = ρ2Gn = ρn
Establish 1.
PREVENTIVE METHOD

General step: Solve the PLi that minimizes Gi, y what ρi = ρi what *

define the value optimal corresponding of the variable of

deviation ρi. Yes=n, stop; the PLn solve the problem of

in goals. Otherwise, add the restriction ρi = ρi to the *

restrictions of the problem Gi to ensure that the value of ρIno

degrades into future problems. Set i = i + 1, and repeat the
step.
The successive addition of the special constraints ρi = ρI can *

not being so 'elegant' theoretically as the elimination rule of

columns; however, the same result is achieved. But the most
It is important that it is easier to implement and understand.
Comentarios:
Some people they can argue what the rule of removal of
columns offers one advantage computational because makes the problem
successively smaller by eliminating variables, while
our procedure makes it bigger by adding new ones
restrictions. Considering the nature of the restrictions
additional (ρi = ρi We *can modify the simplex algorithm to

implement the additional constraint by implicitly substituting ρi

= ρi*.
The substitution (that affects only a the restriction in the what
appears ρireduce the number of variables as the
algoritmo se mueve de una meta a la siguiente. De otra
manner we can to use the method simplex limited
replacing ρI = ρi with *ρi <= ρi with in *which case the
additional restrictions are taken into account in a manner
implicit. In this regard, the rule for column removal,
Apart from its theoretical appeal, it does not seem to offer an advantage.
particular computational.
EXAMPLE 3

The problem of example 2 is solved by the method

estimate. Suppose that the exposure target has the
highest priority.

Step 0. G1 is greater than G2

Minimizers1 (Meet the
-
exposure goal)
G2: Minimize2 (Meet +the budget goal)

Step 1. Solve the PLi

 Minimize G1 = s1 -

Subject to
4x1+ 8x2+ s1 - -s1 +
= 45 (Goal of
exhibition

8x1+ 24x2 + s2-- s2 = + 100 (Goal of

budget

x1+ 2x2 ≤10 (Personal limit)

x1 <= 6 (limit of
radio
x1, x2, s1-, s1 ,+ s2 ,- s2 +
>= 0
The optimal solution (determined by LINDO) is x1= 5 minutes, x2 =
2.5 minutes, s1 5 - million people, with the variables
remaining equal to zero. The solution shows that 5 millions of
people violate the exposure goal, G1The restriction
additional that is added to the problem G2is -
s 1 = 5 (or, what is the
same1 <= 5).
-

Step 2. The objective function of the LP2it

Minimize G2= s2 +

The restrictions are the same as in step 1 plus the

additional restriction1 =- 5.

Generally, the additional restriction s1 5 can- also

explain when substituting in the first restriction.
The result is that the right side of the restriction of the
The exposure limit will change from 45 to 40, which reduces the LP.2a:

Minimize G2= s2 +

Subject to
4x1+ 8x2s1 +
= 40 (Exposure target)

8x1+ 24x2 + s2 - s- 2 = 100

+
(Budget target)

x1+ 2x2 <=10 (Personal limit)

x1 <= 6 (Radio limit)

x1, x2, s1+, s2 ,- s2 >=

+
0
The new formulation has one less variable than that of the
PL1which is the general idea anticipated by the rule of
column deletion.
In reality, the optimization of PL2 it is not necessary in

this problem because the optimal solution to the problem G1or

for results2 =0; +that is to say, it is already optimal for the PL.2Tales
savings opportunities from calculations should be taken advantage of
always what him present during the course of implementation
of the preventive method.
Example 4 (Column Elimination Rule)

In this example, we demonstrate that a better one can be obtained.

solution for the problem of examples 2 and 3 if the is used
preventive method to optimize objectives instead of
satisfy the goals. Later on, the same example is resolved.
applying the column elimination rule.

The goals of example 2 can be stated as:

Priority 1: Maximize exposure (P1)

Priority 2: Minimize the cost2)
Mathematically, the two objectives are given as
Maximize P1= 4x1+ 8x2(Exhibition)
Minimize P2= 8x1+ 24x2(Cost)
The limits specific for the goals of exhibition y of cost
(= 45 and 100) in examples 2 and 3 are eliminated because we will leave
that the simplex method determines these limits optimally.
Therefore, the new problem is formulated as:
Maximize P1= 4x1+ 8x2
Minimize P2= 8x1+ 24x2
Subject to
x1+ 2x2 <= 10
x1 <=6
x1, x2 greater than or equal to 0

First we solve the problem following the procedure

presented in example 3.
Step 1. Solve the PL1
Maximize P1= 4x1+ 8x2
Subject to
x1+ 2x2 <= 10
x1 <=6
x1, x2 greater than or equal to 0
The solution optimal (obtained for BEAUTIFUL it is x1=0, x2=5 with P1 =
40, which shows that the maximum exposure we can
to obtain is 40 million people.
Step 2. Add the restriction 4x1 + 8x2 >= 40 for
to ensure us About the metaG1 no degrades. Therefore,
we solve the PL2like:

Minimize P2= 8x1+ 24x2

Subject to
x1+ 2x2 <= 10
x1 <=6
4x1+ 8x2 >=40 (Additional Restriction)
x1, x2>= 0
The optimal solution of the LP2is P2$96,000, x1 = 6 minutes, and x2
= 2 minutes. This results in the same exposure (P1= 40
millions of people) but a one cost smaller what the del example
3, where we seek to satisfy instead of optimizing the goals.

The same problem is now solved with the elimination rule.

of columns. The rule states that we should include the target rows.
associated with all the goals in the simplex table, as it
will demonstrate next

PL1 Maximization of the exhibition) The table simplex of the PL1

include both target rows P1y P2The condition of optimality
only applies to the target row P1The row P2 plays a role
passive in the PL1, but it must be updated (through the
simplex row operations) with the rest of the table
simplex in preparation for LP optimization2.
The PL1it is solved in two iterations as follows:

Basic Iteration X1 X2 S1 S2 Solution

P1 -4 -8 0 0 0
P2 -8 -24 0 0 0
1 S1 1 2 1 0 10
S2 1 0 0 1 6
P1 0 0 4 0 40
P2 4 0 12 0 120
2 X2 1/2 1 1/2 0 5
S2 1 0 0 1 6

The last table results in the optimal solution.1= 0,x2 =

5 yP1= 40.
The column elimination rule requires that it be removed.
any variable no basic xj with zj - cj ≠ 0 a to leave of the
optimal table of the PL1before optimizing the PL2.
The reason is that if these variables are not verified, they could
to become positive in problems of optimization of low
priority the which can degrade the quality of solutions
high priority.

PL2 (Cost Minimization). The elimination rule of

columns remove s1 (with zj - cj = 4 in the PL1In row P2

we can see that if it is not eliminated1it will be the input variable

at the beginning of the iterations P2 and the result will be the

optimal solution1 = x2= 0, which will degrade the target value

optimal of problem P1 since P1 = 40 until P1 = 0

(¡compruébelo!).
The problem P2 it is of the minimization type. After the
removal of1, the variablex1with zj - cj= 4 (> 0) can
improve the value of P2The following table shows the
iterations the PL2The row P has been removed.1 because it doesn't have
no purpose in the optimization of the PL2.
Iteration Basic X1 X2 S1 S2 Solution
P1 40
P2 4 0 0 120
1 X2 1/2 1 0 5
S2 1 0 1 6
P1 40
P2 0 0 -4 96
2 X2 0 1 -1/2 2
X1 1 0 1 6

The optimal solution (x1= 6, x2= 2) with a total exposure

de P = 40 y un costo total de P = 96 es la misma que se
 THANK YOU

If we take care of the environment

Environment, we take care of our
future