Geometric Programming Techniques and Examples
Translated by
ScribdTranslationsGeometric Programming Techniques and Examples
Translated by
ScribdTranslationsBolivarian Republic of Venezuela
Ministry of Popular Power for Defense
National Experimental University of the Armed Forces
UNEFA
Merida Center - Merida Headquarters
GEOMETRIC PROGRAMMING
Members:
Jose Wladimir Davila Peña ID: 19.751.566
Javier Enrique Hernandez
Jose Sulbaran C.I: 18.966.052
Section: ING-S-6S-D-01
GEOMETRIC PROGRAMMING
Geometric programming has been widely used in recent years
as a tool for the formulation of numerous optimization models that
emerged in different fields of application. Consequently, they have
developed and compared several numerical methods for solving problems
geometric programming
UNRESTRICTED GEOMETRIC PROGRAMMING:
Given a problem of the form:
Min Z=ax₁ cx₂ d + bx₁ ex₂ f + ... + nx₁ ᶢx ₂ ᶻ
Step 1: Change the variable and transform the problem into the form:
Min Z= U₁ + U₂ +…+ A
Where
Uj = ajx₁ b^j1 x₂ b² ... x₁ ᵝ ʲᵏ
αji= Exponents
terms of monomials.
Step 2: Form the dual function:
H(ɤ)= (a₁ (a₂ /y²)y²...(an/yⁱ)yⁱ
Step 3: We form the simultaneous linear equation system, using the
following formulas:
Step 4: Solve the equation system from step 3 to obtain the values ɤj.
Σ(aji y = 0), Σ(yj = 1)
Step 5: Substitute the values of ɤj in the dual function to find out if the value of h
obtained is correct, it must match the objective function.
Step 6: find the values of Uj using the expression:
Uj=ɤj.h(ɤ); and here we can obtain the value of Z.
Step 7: We equalize the values of Uj to each corresponding term.
objective function to find the values of X.
Step 8: Substitute the values found into the objective function and compare them with h.
EXERCISE NO. 1
Min Z= 2X₁ ³X₂ ¯³ + 4X₁ ¯²X₂ + X₁ X₂
Min Z=U₁ + U₂ + U₃
Where: U₁ = 2X₁ ³X₂ ¯³ h(ɤ)= 6.7266
U₂ =4X₁ ¯²X₂
U₃ = X₁ X₂
3ɤ1 - 2ɤ2 + ɤ3 = 0
-3ɤ1 +ɤ2 +ɤ3 = 0
ɤ1 + ɤ2 + ɤ3 = 1
ɤ ₁ = 0.25; γ₂ = 0.50, ɤ ₃ 0.25⑤ →
U₁ =ɤ ₁ h(ɤ) = 0.25 * 6.7266 → U₁ 1.6816
U₂ =ɤ ₂ * h(ɤ)=0.50*6.7266 → U₂ =3,3633
U₃ =ɤ ₃ * h(ɤ)=0.25*6.7266 → U₃ =1.6816
2X₁ ³X₂ ¯³ = 1.6816
4X₁ ¯²X₂ 3.3633
X₁ X₂ 1.6816
Of X₁ X₂ = 1.6816; X₁ = 1.6816/X₂ substituting this value in:
2X₁ ³X₂ ¯³ = 1.6816 → 2(1.6816/X₂ ) ³.(X₂ X = 1.6816₂ 1.3347
X₁ 1.26₁ = 1.2599
Z = 2(1.2599)³ * (1.3347)¯³ + 4(1.2599)¯² (1.3347) + (1.2599)(1.3347)
Z= 6,727.
EXERCISE N°2
Min X₁ ³X₂ ¯³ + 2X₁ ¯²X₂ + 2X₁ X₂
Min Z= U₁ + U₂ + U₃
Where: U₁ = X₁ ³X₂ ¯³
U₂ =2X₁ ¯²X₂
U₃ = 2X₁ X₂
3ɤ1 - 2ɤ2 + ɤ3 = 0
-3ɤ1 +ɤ2 +ɤ3 =0
ɤ1 + ɤ2 + ɤ3 = 1
ɤ ₁ = 0.25;ɤ ₂ = 0.5625, ɤ ₃ =0.1875 → h(ɤ) = 4.4994
U₁ =ɤ ₁ * h(ɤ)= 0.25*4.4994 → U₁ = 1.1248
U₂ =ɤ ₂ h(ɤ)=0.5625*4.4994 → U₂ =2.5309
U₃ =ɤ ₃ * h(ɤ)=0.1875*4.4994 → U₃ 0.8449
X₁ ³X₂ ¯³=1.1248
2X₁ ¯²X₂ 2.5309
2X₁ X₂ 0.8449
From 2X₁ X₂ =0.8449; X₁ = 0.8449/2X₂
Substituting X₁ in 2X₁ ¯²X₂ = 2.5309
2(0.8449 / 2X)₂ ) * (X₂ = 2.5309 → X₂ = 0.6089; therefore
X₁ = 0.8449/2(0.6089) 0.6937 → X₁ 0.6937
Z = (0.6937)³ * (0.6089)¯³ + 2(0.6937)¯²(0.6089) + 2(0.6089)
Z= 4.8541.
GEOMETRIC PROGRAMMING WITH CONSTRAINTS
Given a problem of the form:
Min Z = ax₁ cx₂ d + bx₁ ex₂ f+…+nx₁ ᶢx ₂ ᶻ
S.A.: R₁ X₁ ᶢX ₂ f +...+ RnX₁ kX₂ j ≤ r
Step 1: We transform the problem into the form:
My Z=U₁ + U₂ +...+ A
S.A.: Un+₁ + Un+₂ +…+ Un ≤ 1
Uj = ajx₁ b^j1 x₂ b^j² ... x₁ ᵝ ʲᵏ
Step 2: Form the Dual Function.
H(ɤ)= (a₁ (a₂ ₁ ^ƛ
Step 3: Form the system of simultaneous linear equations with the following
formulas.
(aji y = 0), (yj = 1)
Step 4:
a) Solve the system of equations to find the values of ɤ j.
b) Find the values of ƛ where ƛ ₁ =∑ɤj for each constraint.
Step 5: We replace the values of ƛ and ɤ in the dual function to find h, that is
value must match the value of the primal objective function.
Step 6: Find the values of Uj depending on the case.
a) For the Objective function. Uj=h( ɤ )ɤ j ; j=1,2,3,…n
b) For the restrictions Uj= ɤ j/ƛ i; j=n+1, n+2,…,n
Step 7: We equalize the values of Uj to each term that corresponds to it.
objective function to find the values of X.
Step 8: Substitute the found values in the objective function and compare them with h.
EXERCISE No. 1
Min Z= 5X₁ ¯³X₂ X₃ + X₁ X₂ X₃
S.A.: 4 X₁ X₃ ¯² + 6 X₂ ¯²X₃ ¯¹ ≤ 1 divide the constraint by 2
2 X₁ X₃ ¯² + 3 X₂ ¯²X₃ ¯¹ ≤ 1
Min Z= U₁ + U₂
S.A.: U₃ + U₄
Where: U₁ = 5X₁ ¯³X₂ X₃
U₂ = X₁ X₂ X₃
U₃ = 2 X₁ X₃ ¯²
U₄ =3 X₂ ¯²X₃ ¯¹
-3γ1 + γ2 + γ3 + 0γ4 = 0
ɤ1 + ɤ2 + 0ɤ3 - ɤ4 = 0
ɤ1 + ɤ2 - 2ɤ3 - ɤ4 = 0
ɤ1 + ɤ2 + 0ɤ3 + 0ɤ4 = 1
ɤ ₁ = 0.3125;ɤ ₂ = 0.6875, ɤ ₃ =0.25,ɤ ₄ =0,50 ; ƛ= 0,750
10.2150
U₁ = 10,2150*0,3125 → U₁ = 3.1921
U₂ U = 10.2150 * 0.6875₂ = 7.0228
U₃ (0.25/0.75) → U₃ 0.333
U₄ (0.50/0.75) → U₄ =0.666
5X₁ ¯³X₂ X₃ 0.3125
X₁ X₂ X₃ =0.6875
2 X₁ X₃ ¯²=0.25
3 X₂ ¯²X₃ ¯¹=0.50
From 5X₁ ¯³X₂ X₃ 0.3125 → X₂ X₃ = (0.3125/5)X₁ ³
The X₁ X₂ X₃ =0.6875 → X₂ X₃ = (0.6875/X₁ substituting
(0.3125/5)X₁ ³ = (0.6875/X₁ X₁ =1.8211
Substituting the value of X₁ in 2 X₁ X₃ ¯²=0.25 we obtain X₃ .
X₃ ¯² = (0.25/2X₁ ) where X₃ ¯²= (0.25/2(1.8211)) → X₃ 3.8169
Replacing the value of X₃ in 3 X₂ ¯²X₃ ¯¹=0.50
3 X₂ ¯² = (0.50/X₃ ¯¹) → X₂ 1.2537
Z = 5(1.8211)^{-3}*(1.2537)(3.8169) + (1.8211)(1.2537)(3.8169)
Z=10.2166.
EXERCISE NO. 2
Min Z = 4 X₁ X₂ X₃ + 2X₁ ¯¹X₂ X₃
S.A.: 4X₁ X₃ ¯² + 6X₂ ¯²X₃ ¯¹ ≤2se divides the restriction by 2.
2X₁ X₃ ¯² + 3X₂ ¯²X₃ ¯¹ ≤1
Min Z= U₁ + U₂
S.A.: U₃ + U₄
Where: U₁ 4 X₁ X₂ X₃
You₂ =2X₁ ¯¹X₂ X₃
U₃ =2X₁ X₃ ¯²
U₄ =3X₂ ¯²X₃ ¯¹
ɤ1 - ɤ2 + ɤ3 + 0ɤ4 = 0
ɤ1 + ɤ2 + 0ɤ3 - 2ɤ4 = 0
ɤ1 + ɤ2 - 2ɤ3 - ɤ4 = 0
ɤ1 + ɤ2 + 0ɤ3 + 0ɤ4 = 1
ɤ ₁ = 0.375;ɤ ₂ = 0.625, ɤ ₃ =0.250,ɤ ₄ =0,500 ; ƛ= 0,750
h(ɤ) → 16.6842
U₁ 6,263325₁ = 6.2565
U₂ = 16,6842 * 0,625 → U₂ = 10.4276
U₃ (0.25/0.75) → U₃ =0.333
U₄ (0.50/0.75) → U₄ 0.666
4 X₁ X₂ X₃ 0.375
2X₁ X inverse₂ X₃ 0.625
2X₁ X₃ ¯²= 0.250
3X₂ ¯²X₃ ¯¹= 0.500
Of 4 X₁ X₂ X₃ = 0.375 we solve for X₂ X₃ (0.375 / 4X₁ )
From 2X₁
¯¹X₂ X₃ = 0.625 we solve for X₂ X₃ = (0.375/2X₁ We isolate from
both equations the following:
(0.375/4X₁ = (0.375/2X₁ ¯¹) and we find X₁ Where
X₁ = 2.2738
Of 2X₁ X₃ ¯² = 0.250 we solve for X₃ and we substitute the value of X₁ ;
2(0.2738)X₃ ¯² = 0.250; X₃ =1.48
We calculate the value of X₂
4 X₁ X₂ X₃ = 0.375 → 4(0.2738) X₂ (1,48)=0.375 → X₂ = 0.2313.
Z = 4(0.2738)*(0.2313)(1.48) + 2(0.2738)⁻¹(0.2313)(1.48)
Z= 16.6868
CONCLUSION
Geometric Programming solves a special case of problems of
Non-linear programming. This method solves by considering a dual problem.
associating the following two types of Non-linear Programming: Problem
unrestricted geometric: Restricted geometric problem.
Allowing to achieve excellent results with very few steps and easy.
understanding at first glance, although it has some deficiencies that only
can be used for the objective function to minimize.
Despite this, it is very comprehensive, just like the other methods.
Both linear programming and non-linear ones seek the same goal: to bring closer to
an optimization of resources
Common questions
Powered by AIEnsuring that the values from the dual function match the primal objective function values is crucial because it confirms that the solution is optimal. This comparison serves as a validation step to verify that the constructed dual model correctly represents the primal problem and that the calculated solutions for the variables satisfy the original problem's conditions. Hence, it's a standard check in geometric programming to affirm solution reliability and correctness .
In constrained geometric programming, the problem is structured with an objective function and additional constraints. The methodology first transforms the objective function into a form with auxiliary variables. Constraints are handled by modifying these new variables into conditions that must satisfy specified limits. The dual formulation then involves setting up a system of linear equations based on constraints, aimed at finding values for dual variables that ensure consistency between the objective function’s value and primal constraint limits .
The process involves several steps: first, the problem is expressed as a series of monomial terms. Each of these is transformed into simpler expressions involving dual variables by forming the dual function. This function involves ratios of original problem coefficients divided by the dual variables, aggregated into a form suitable for solving using linear equations. Dual variables are then determined via a system of linear equations to ensure the solution satisfies the problem's constraints .
Geometric programming differs from classical linear programming primarily in how it handles non-linear terms using a dual variable technique to linearize them. Unlike linear programming that strictly deals with linear constraints and objective functions, geometric programming simplifies non-linear posynomial functions making certain complex optimization problems more solvable. However, its applicability is more limited to specific cases where posynomial structures are present .
Constraints necessitate the need for dual variables corresponding to each constraint, transforming the objective function such that the dual variables maintain relationship definitions within a new linear term system. These constraints complicate the steps by introducing additional linear equations that must be satisfied for an optimal solution. The model must ensure consistency between objective and constraint fulfillment, which involves solving these additional systems simultaneously .
Iterative strategies involve recalibrating initial guesses of dual variables, using methods such as gradient descent or other iterative linear solvers to refine the solution progressively until convergence criteria are met. These strategies ensure adjustments towards minimizing the objective value while meeting constraint criteria, iterating with fine-tuned adjustments based on differential evaluations of dual vs objective function consistency, thereby ensuring stable and integer convergence to optimality .
Dual functions serve a critical role in simplifying complex geometric programming problems by converting the original non-linear problem into a liner form. This transformation allows the problem to be tackled through linear equation solutions, making it computationally feasible. The dual function mirrors the structure of the primal problem but works in a space defined by dual variables, ensuring that these solutions adhere to both primal and dual feasibility conditions, thus certifying optimality of the derived solution .
The document identifies a few challenges associated with geometric programming: one is its somewhat limited applicability, specifically to problems requiring minimization of the objective function. Another noted issue is that while it can achieve good results quickly, it requires an understanding of dual variable transformations and solving corresponding linear equations, which can be complex for those not familiar with mathematical optimization techniques .
A typical unrestricted geometric programming problem is represented as a minimization problem with a posynomial objective function. Solving involves changing variables to a more workable form, mapping original terms into auxiliary terms using dual variables, and formulating a dual function. This is solved via a system of linear equations, finding dual variables that satisfy both the primal function's structure and obtain the minimal possible value of the objective. Exercise examples provided in the document exemplify this structured solution approach .
Geometric programming is primarily used for formulating optimization models across various fields. It's a mathematical technique that simplifies solving problems involving certain posynomial functions, making it valuable in domains requiring optimization solutions. The document highlights its application through solving specific mathematical problems, illustrating its utility in attaining efficient and effective solutions .