Deck 13: Nonlinear Programming

Question 1

Starting from the initial trial solution (x₁,x₂)= (0,0),interactively apply the gradient search procedure with $\varepsilon$ = 1 to solve (approximately)the following problem.Minimize g(x)= 2 + - - 2x₁x₂.

Answer 1

For convenience,we can convert from minimization to maximization by considering f(x)= -g(x).(Section 13.5 in the textbook also describes how the procedure can be adjusted to perform minimization directly.)Thus,the equivalent problem becomes Maximize f(x)= -2 - + 4x₁ + 2x₁x₂.Taking the partial derivatives,we have , .Since $\varepsilon$ = 1,we will stop the gradient search procedure when the current trial solution yields ≤ 1 for j = 1 and 2.Starting from (x₁,x₂)= (0,0),the gradient search procedure proceeds as summarized in the following table: At the beginning of iteration 4,both partial derivatives (0 and 1)are ≤ 1,so the procedure stops with x₁ = 1.5 and x₂ = 1 as the desired approximation of an optimal solution (which happens to be x₁ = 2 and x₂ = 2).To elaborate further on how the above table was obtained,at iteration 1, = f (4t,0)= -2(4t)² - 0² + 4(4t)+ 2(4t)(0)= -32t² + 16t.Because f (4t*,0)= and = -64t + 16 = 0,it follows that t* = 0.25.The calculations for iterations 2 and 3 follow the same pattern.

Question 2

Consider the following nonlinear programming problem.Maximize Z = ,subject to 2x₁ + x₂ + x₃ ≤ 4 and x₁ ≥ 0,x₂ ≥ 0,x₃ ≥ 0.
(a)Use the KKT conditions to determine whether = (1,1,1)can be optimal.
(b)If a specific solution satisfies the KKT conditions for this problem,can you draw the definite conclusion that this solution is optimal? Why?

Answer 2

The KKT conditions are 1 a) 2 a) 1 b) 2 b) 1 c) 2 c) 3) 4) 5)x₁ $\ge$ 0,x₂ $\ge$ 0,x₃ $\ge$ 0,6)u $\ge$ 0.(a)Consider (x₁ ,x₂,x₃ )= (1,1,1).From 2a),we have u = 2.Note that all the KKT conditions now are satisfied,so (x₁ ,x₂,x₃ )= (1,1,1)can be optimal.(b)No.The objective function is not concave (since 2 is convex instead),so the KKT conditions are necessary but not sufficient for optimality.

Question 3

The Build-Em-Fast Company has agreed to supply its best customer with three widgits during each of the next 3 weeks,even though producing them will require some overtime work.The relevant production data are as follows: The Build-Em-Fast Company has agreed to supply its best customer with three widgits during each of the next 3 weeks,even though producing them will require some overtime work.The relevant production data are as follows: The cost per unit produced with overtime for each week is $100 more than for regular time.The cost of storage is $50 per unit for each week it is stored.There is already an inventory of two widgets on hand currently,but the company does not want to retain any widgets in inventory after the 3 weeks.Management wants to know how many units should be produced in each week to minimize the total cost of meeting the delivery schedule.A special restriction for this problem is that overtime should not be used in any particular period unless regular time in that period is completely used up.Explain why the logic of separable programming implies that this restriction will be satisfied automatically by any optimal solution for the transportation problem formulation of the problem.(You only need to explain this logic without formulating the transportation problem.)

Answer 3

Since regular time production is cheaper than overtime,the objective of minimizing cost will force regular time to be used first in an optimal solution.To see why,consider any feasible solution (one that satisfies all the constraints of the problem)that violates the special restriction because overtime is used in a particular period even though regular time is not completely used up in that period.Therefore,because regular time is cheaper,increasing regular time in that period by a small amount and decreasing overtime by the same amount will yield a feasible solution with a better value of the objective function,so the original feasible solution cannot be optimal.

Question 4

Consider the following quadratic programming problem.Maximize Z = 126x₁ - 9 + 182x₂ - 13 ,subject to x₁ ≤ 4 2x₂ ≤ 12 3x₁ + 2x₂ ≤ 18 and x₁ ≥ 0 and x₂ ≥ 0.Starting from the initial trial solution (x₁,x₂)= (0,0),use three iterations of the Frank-Wolfe algorithm to obtain and verify the optimal solution.

Question 5

Consider the following convex programming problem.Maximize f(x)= 10x₁ - 2 - + 8x₂ - ,subject to x₁ + x₂ ≤ 2 and x₁ ≥ 0,x₂ ≥ 0.(a)Use the KKT conditions to demonstrate that (x₁,x₂)= (1,1)is not an optimal solution.
(b)Use the KKT conditions to derive an optimal solution.

Question 6

Business travelers tend to be less price sensitive than leisure travelers.Knowing this,airlines have discovered that extra profit can be generated by using separate pricing for these two types of customers.For example,airlines often charge more for a midweek flight (mostly business travelers)than for travel that includes a Saturday-night stay (mostly leisure travelers).Suppose an airline has estimated demand vs.price for midweek travel (mostly business travelers)and for travel that includes a Saturday-night stay (mostly leisure travelers)as shown in the table below.This flight is served by a Boeing 777 with capacity for 300 travelers.The fixed cost of operating the flight is $30,000.The variable cost per passenger (for food and fuel)is $30. (a)One function that can used to estimate demand (D)as a function of price (P)is a linear demand function,where D = a - bP.For positive values of a and b,this will give lower demand when the price is higher.However,a nonlinear demand function usually can provide a better fit to the data.For example,one such function is a constant elasticity demand function,where D = aP^b.For positive values of a and negative values of b,this also will give lower demand when the price is higher.Graph the above data and use the Add Trendline feature of Excel to find the constant elasticity demand function that best fits the data in the above table for midweek demand,Saturday-night stay demand,and total demand (b)For this part,assume that the airline charges a single price to all customers.Using the demand function for total demand determined in part a,formulate and solve a nonlinear programming model in a spreadsheet to determine what the price should be so as to achieve the highest profit for the airline.(c)Now assume that the airline charges separate prices for midweek and Saturday-night stay tickets.Using the two demand functions for midweek and Saturday-night stay tickets determined in part a,formulate and solve a nonlinear programming spreadsheet model to determine what the prices of the two types of tickets should be so as to maximize the profit for the airline.d)How much extra profit can the airline achieve by charging higher prices for midweek tickets than for Saturday-night stay tickets?