![](https://csdnimg.cn/release/download_crawler_static/2311377/bg12.jpg)
You can think of x
i
as a job we either accept or decline, and −c
i
as the (positive) revenue we
generate if we accept job i. We can think of Ax b as a set of limits on m resources. A
ij
, which
is positive, is the amount of resource i consumed if we accept job j; b
i
, which is positive, is the
amount of resource i available.
Find a solution of the relaxed LP and exam i ne its entries. Note the associated lower bound L.
Carry out threshold rounding for (say) 100 values of t, uniformly spaced over [0, 1]. For each value
of t, note the objec ti ve value c
T
ˆx and the maximum const r aint violation max
i
(Aˆx − b)
i
. Pl ot the
objecti ve value and the maximum violation versus t. Be sure to indicat e on the plot the values of
t for which ˆx is feasible, and those for which it is not.
Find a value of t for which ˆx is feasible, and gives minimum objecti ve value, and note the associated
upper bound U. Give the gap U −L between the upper bound on p
⋆
and the lower bound on p
⋆
. If
you define vectors obj and maxviol, you can find the upper bound as U=min(obj(find(maxviol<=0))).
3.19 Optimal operation of a hybrid vehicle. Solve the instance of the hy br i d vehicle operation problem de-
scribed in exercise 4. 65 in Convex Optimization, with problem data given i n the file hybrid_veh_data.m,
and fuel use function F (p) = p + γp
2
(for p ≥ 0).
Hint. You will actually formulate and solve a relaxation of the original problem. You may find that
some of the equality constraints you relaxed to inequality constraints do not hold for the solut i on
found. This is not an error: it just means that there is no incentive (in terms of the objec ti ve) for
the inequality to be tight. You can fix this in (at least) two ways. One is to go back and adjust
certain variables, without affecting the objective and maintaining feasibility, so that the relax e d
constraints hold with equality. Another simple method is to add to the objective a term of the
form
ǫ
T
X
t=1
max{0, −P
mg
(t)},
where ǫ is small and positive. This makes it more attractive to use the brakes to extract powe r
from the wheels, even when the battery is (or will be) full (which removes any fuel incentive).
Find the optimal fuel consumption, and compare to the fuel cons umpt i on with a non-hybrid ver-
sion of th e same vehicle (i.e., one without a battery). Plot the braking power, engine power,
motor/generator power, and battery energy versus time.
How would you use optimal dual variables for this problem to find ∂F
total
/∂E
max
batt
, i.e., the partial
derivative of optimal fuel consumption with respect to battery capacity? (You can just assume
that this partial derivative exists.) You do not have to gi ve a long derivation or proof; you can
just state how you would fine thi s derivative from optimal dual variables for the problem. Verify
your method numerically, by changing the battery capacity a small amount and re-running the
optimization, and comparing this to the prediction made using dual variables.
3.20 Optimal vehicle speed scheduling. A vehicle (say, an airplane) travels along a fixed path of n
segments, be tween n + 1 waypoints labeled 0, . . . , n. Segment i starts at waypoint i − 1 and
terminates at waypoi nt i. The vehicle starts at time t = 0 at waypoint 0. It travels over each
segment at a constant (nonnegative) speed; s
i
is the speed on segment i. We have lower and upper
limits on the speeds: s
min
s s
max
. The vehicle does not st op at the waypoints; it sim pl y
proceeds to the next segment. The travel dist anc e of s egm ent i is d
i
(which is positive), so the
travel time over segment i is d
i
/s
i
. We let τ
i
, i = 1, . . . , n, denote the time at which the vehicle
18