Principles of Mathematics in Operations Research

13.7 Problems 187

of solutions in a general instance r.

Use generating functions to

a) Prove the binomial theorem

u«>-£ (I)

i=0 x '

and extend to the multinomial (you may not use the generating functions)

theorem

<*+•••*>•=. E (,„.".„»)

i\,.. .,ik € £+

i\-\ \-ik = n

b) Prove that

{l + x + x^2 +x^3 + ...)n = J2

»=0

n — 1 + ^>

c) Find the probability of having a sum of 13 if we roll four distinct dice.

d) Solve the following difference equation: an — 5a„_i—6an_2, Vn = 2, 3, 4,...

with ao — 2 and a\ = 5 as boundary conditions.

13.4. Consider the following air defense situation. There are i = 1,..., / en-
emy air threats each to be engaged to one of the allied z — 1,..., Z high value
zones with a value of wz. The probability that a threat (i) will destroy its tar-
get (z) is qiz. More than one threats can engage to a single zone. On the other
hand, there are j = 1,..., J allied air defense systems that can engage the
incoming air threats. The single shot kill probability of an air defense missile
fired by system j to a threat i is Pji. Let the main integer decision variable
be Xji indicating the number of missiles fired from system j to threat i.
a) Write down the nonlinear constraint if there is a threshold value di, the
minimum desired probability for destroying target i. Try to linearize it using
one of the functions defined in this chapter.
b) Let our objective function that maximizes the expected total weighted sur-
vival of the zones be
maxE waz (0), where a
z = Y\i 1 - qiz [U.j{l - Pji)
Xji) = Hi Piz-

Then, 7Z = log(az) = J2% l°g(Az) = Si $iz and we have the second objective

function: m&xJ2z Wzlz (0')- Isn't this equivalent to max^T^ wz J2i $iz (0")>

where Siz = log 1 - qiz (FT/^1 ~ Pji)Xji)? SincePiz = 1~9« \Ilj(l ~ Pji)Xsi)

and we have

m&x5iz — maxlog(/3iz) = max/3i2 = min(l - @iz) = minlog(l - j3iz),