ProblemSet 2 -- Optimization

1. Blood typing

Human blood is generally classified in the “ABO” system, with four blood types: A, B, O, and AB. These four types reflect six gene pairs, with blood type A corresponding to gene pairs AA and AO, blood type B corresponding to gene pairs BB and BO, blood type O corresponding to gene pair OO, and blood type AB corresponding to gene pair AB. Let \(p\) be the proportion of gene A in the population, let \(q\) be the proportion of gene B in the population, and let \(r\) be the proportion of gene O in the population. For example, the quantity \(p\) represents the ratio of the total number of blood-type genes of type A to the total number of blood-type genes. Since each blood-type gene is either A, B or O, it is clear that \(p + q + r = 1\).

  1. cThe Hardy-Weinberg principle implies that:

    \((\clubsuit)\) The quantities \(p\), \(q\), and \(r\) remain constant from generation to generation, as do the frequencies of occurrence of the different genotypes AA, AO, … .

    Assuming the validity of \((\clubsuit)\), what is the probability that an individual has genotype AA? BB? OO? What is the probability of an individual having two different genes? Express your response using the quantities \(p\), \(q\) and \(r\).

  2. Still assuming the valiidty of \((\clubsuit)\), find the maximum percentage of the population that can have two different genes. Perform this computation in two different ways:

    • directly maximize a function of only two variables
    • use the method of Lagrange multipliers.

  3. Explain in words what the Lagrange multiplier represents in the second computation of part (b).

2. Newton’s method and root finding

  1. microprocessors

    One of the uses of Newton’s method is in implementing division on microprocessors, where only addition and multiplication are available as primitive operations. To compute \(x = a/b\), first the root of \(f(x) = \dfrac{1}{x} − b\) is found using Newton’s method, then the fraction is computed with one last multiplication by \(a\).

    Find the Newton iteration needed to solve \(f(x) = 0\) and explain why it is well-suited to this purpose. (Note: The point here is to approximate division, so you shouldn’t use division functions implemented in python!)

  2. experiments

    Apply Newton’s Method to compute \(1/b\), where \(b\) is: (i) the last 3 digits of your student number; and (ii) the area code of your phone number. For these experiments, report the number of iterations required for the approximation to be consistent to 10 digits.

3. A linear program

Consider the optimization problem: find the \(\max\) of \(f(x, y) = x + 2y\) subject to the following constraints:

\[\begin{align*} y &\le 9 \\ −y &\le −1 \\ 2x + y &≤ 25 \\ −2x − y &≤ −9 \\ −2x + y &≤ 1 \\ 2x − y &≤ 15. \end{align*}\]

  1. Draw the feasible region. Label the boundary curves and corner points.

  2. Find the maximum value of f subject to the constraints and the point where it occurs.

  3. Verify your answer using SciPy.

4. Bakers

A bakery wants to sell forty five Valentine’s Day gift bags. They have decided to offer two types of bags:

The bakery has 90 cookies and 115 cupcakes in total. Write the bakery’s optimization problem as a linear program. Solve this to determine how many baskets of both types should be made. If a fractional solution is obtained, round down to whole number solutions. What is the maximum profit?

You may solve this by drawing the feasible region or using python.