Homework 4

Problem 1.

You are given \(n\) points \((x_{i}, y_{i})\), \(i = 1,\ldots,n\) in the plane. You want to find a line \(y = mx + b\) that approximately passes through these points. Write a linear program to find the line that minimizes the maximum absolute error:

Your LP does not have to be in standard form, in particular, you can use variables with values in \(\mathbb{R}\). Explain the meaning of the variables in your linear program.

Problem 2.

This is the same problem as Problem 1, but this time you should minimize the \(L_1\) error:

Problem 3.

A transport plane has three cargo compartments, one in the front, one in the middle, and one at the rear end of the plane. These compartments have the following capacity in terms of weight and volume:

There are four kinds of merchandise that you can transport:

The plane has to remain balanced, and so you have to load it such that each compartment carries the same percentage of its total weight capacity. For instance, if you have 5 tons in the front compartment, you must have 8 tons in the center and 4 tons in the rear compartment.

Write a linear program to select the merchandise that will maximize your profit under the given constraints. Explain clearly the meaning of each variable and each constraint. (You can assume that the merchandise can be partitioned in any way you want, for instance 5.123467 tons, or \(12/7\) tons, etc.)

Problem 4.

A car manufacturer makes both vans and flatbed trucks. There are four workshops: chassis assembly, sheet metal plating, upholstery, and painting. Each workshop works 60 hours per week.

The manufacturing of a van takes 5 hours of chassis assembly, 12 hours of plating, and 10 hours of painting. The manufacturing of a flatbed truck takes 10 hours of chassis assembly, 12 hours of upholstery, and 5 hours of painting.

The market for these models is not saturated (the manufacturer can sell as much as they can produce), each vehicle brings a profit of $1000, and the manufacturer wants to maximize their profit.

• Formalize this problem as a linear program.
• Graphically determine the optimum solution.

Problem 5.

Given a network circulation problem with supplies/demands for each vertex and lower bounds and capacities for each edge. Explain how to solve the problem using linear programming.

Problem 6.

Given a linear program in general form, that is using variables with arbitrary real values, and both equalities and inequalities for constraint. Describe how to transform this program into a linear program in slack form:

Keep the number of variables in the resulting linear program as small as possible.