Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

ISyE/Math/CS/Stat 525 – Linear Optimization

Assignment 1 – Chapter 1

Instructions and policy: Undergraduate students should handle in the five exercises that are marked with [U]. Graduate students should handle in the five exercises that are marked with [G]. All other exercises are optional for keen students and should not be handled in. The assignment should be submitted electronically in Canvas. Late submission policy: 20% of total points will be deducted per hour. Each student is encouraged to solve all the exercises in the assignment to practice for the exams.

Students are strongly encouraged to work in groups of two on homework assignments. To find a partner you can post on the “Discussions” section in Canvas. Only one file should be submitted for both group members. In order to submit the assignment for your group please follow these steps in Canvas: Step 1. Click on the “People” tab, then on “Groups”, and join one of the available groups named “Assignments Group 1”, “Assignments Group 2”, . . . ; Step 2. When also your partner has joined the same group, one of the two can submit the assignment by clicking on the “Assignments” tab, then on the assignment to be submitted, and finally on “Submit assignment”. The submission will count for everyone in your group.

Groups must work independently of each other, may not share answers with each other, and solutions must not be copied from the internet or other sources. If improper collaboration is detected, all groups involved will automatically receive a 0. Students must properly give credit to any outside resources they use (such as books, papers, etc.). In doing these exercises, you must justify all of your answers and cite every result that you use. You are not allowed to share any content of this assignment.

Exercise 1 [U][G] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

A function f : R n → R is called convex if for every x, y ∈ R n, and every λ ∈ [0, 1], we have

f(λx + (1 − λ)y) ≤ λf(x) + (1 − λ)f(y).

Let f : R n → R be defined as f(x) =  fi(x) for x ∈ R n, where fi : R n → R is a convex function for each i = 1, . . . , m. Show that f is convex.

Exercise 2 [U] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

Consider the problem of minimizing a cost function of the form c 0 x + f(d 0 x), subject to the linear constraints Ax ≥ b. Here, d is a given vector and the function f : R 7→ R is described in the picture below.

Provide a linear programming formulation of this problem.

Exercise 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

Consider the following Linear Program:

min 3x1 + 2x2 + x3

s.t. x1 + x2 − x3 = 2

x1 + 2x2 ≤ 5

2x1 − x3 ≥ 4

x1 ≥ 0, x2 ≥ 0.

(a) Determine a matrix A and vectors b, c such that the problem can be written in the form:

min c'x

s.t. Ax ≥ b.

(b) Rewrite the problem in standard form.

Exercise 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

A farmer needs to buy five kinds of fertilizer for each of which he requires 185, 50, 50, 200, and 185 tons, respectively. The fertilizers can be purchased from four distinct dealers that can each provide at most 350, 225, 195, and 275 tons of fertilizer in total. The prices (in USD) per ton of fertilizer of each dealer are depicted in the subsequent table:

The farmer seeks to minimize his expenses. Formulate this problem as a Linear Program.

Exercise 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

An oil company buys fuels from large producers and sells fuels and gasolines (gasolines are mixtures of fuels) to smaller companies. The fuels properties, availability, cost and resale price are given in the following table:

Three types of gasoline A, B and C are produced, with a required octane number of at least 95 (A), 90 (B) and 85 (C). Note that the octane number of a mixture is simply the weighted average over the fuels contained. The gasolines will be sold at a price of $ 45.15 (A), $ 42.95 (B) and $ 40.99 (C) per barrel. Fuels that are not used to produce gasoline will be directly sold at the resale price.

(a) Formulate a linear program for the problem of maximizing the daily profit of the oil company. Declare your variables and briefly describe your constraints.

(b) Without solving the linear program that you derived in (a), can you say how many barrels per day will be bought of each fuel type?

Exercise 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

A paper manufacturer produces paper rolls of a standard width of 105 cm and length L cm. However, the customers demand rolls of length L cm but of a smaller width. The manufacturer is faced with the following orders.

To meet the demand, rolls of standard width are cut into rolls of smaller width. One roll can, for instance, be cut into two rolls of width 35 cm and one roll of width 30 cm. This cutting pattern yields a loss of 5Lcm2 of paper. The goal of the manufacturer is to minimize the loss of paper for the above demand. Formulate this problem as an Integer Linear Program (An Integer Linear Program is a linear program where each variables is required to be integer).

Exercise 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

Consider the following optimization problems involving absolute values. For each one, give an equivalent linear program using similar ideas to the ones seen in class, and prove the equivalence.

(a)

min   − 2x1 + 3|x2 − 10|

s.t.   |x1 + 2| + |x2| ≤ 5

(b)

max   x1 − |x2 + 3|

s.t.   |x1| + x2 ≤ 3

x2 ≥ 0

(c)

min   |x1| − |x2 − 1|

s.t.    3x1 + 2x2 ≥ 1

x2 ≥ 1

Exercise 8 [U][G] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

Consider an optimization problem (P) with absolute values in the following form:

min   c'x + d'y

s.t.   Ax + By ≤ b

yi = |xi |    ∀ i,

and assume that all entries of B and d are nonnegative.

(a) (3 points) Provide a linear programming reformulation of the above problem, using ideas similar to the ones discussed in class.

(b) (4 points) Show that the original problem and the reformulation are equivalent.

(c) (3 points) Provide an example to show that if B has negative entries, the problem may have a local minimum that is not a global minimum.

Exercise 9 [U][G] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

Consider a road divided into n segments that is illuminated by m lamps. Let pj be the power of the jth lamp. The illumination Ii of the ith segment is assumed to be  aijpj , where aij are known coefficients. Let Ii ∗ be the desired illumination of segment i.

We are interested in choosing the lamp powers pj so that the illuminations Ii are close to the desired illuminations I*i. Provide a reasonable linear programming formulation of this problem. Note that the wording of the problem is loose and there is more than one possible formulation.

Exercise 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0 points

Consider a school district with I neighborhood, J schools, and G grades at each school. Each school j has a capacity of Cjg for grade g. In each neighborhood i, the student populations of grade g is Sig. Finally, the distance of school j from neighborhood i is dij . Formulate a linear programming problem whose objective is to assign all students to schools, while minimizing the total distance traveled by all students. (You may ignore the fact that the numbers of students must be integer.)

Exercise 11 [G] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

Consider a set P described by linear inequalities constraints, that is, P = {x ∈ Rn | a'ix ≤ bi , i = 1, . . . , m}. A ball with center y and radius r is defined as the set of all points within (Euclidean) distance r from y. We are interested in finding a ball with largest possible radius, which is entirely contained within the set P. Provide a linear programming formulation of the problem.

Exercise 12 [U][G] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 points

A company produces and sells two different products. The demand for each product is unlimited, but the company is constrained by cash availability and machine capacity.

Each unit of the first and second product requires 3 and 4 machine hours, respectively. There are 20,000 machine hours available in the current production period. The production costs are $3 and $2 per unit of the first and second product, respectively. The selling prices of the first and the second product are $6 and $5.40 per unit, respectively. The available cash is $4,000; furthermore, 45% of the sales revenues from the first product and 30% of the sales revenues from the second product will be made available to finance operations during the current period.

(a) (4 points) Formulate a linear programming problem that aims at maximizing net income subject to the cash availability and machine capacity limitations. Recall that the net income is the sales revenue minus the production cost.

(b) (3 points) Solve the problem graphically to obtain an optimal solution.

(c) (3 points) Suppose that the company could increase its available machine hours by 2,000, after spending $400 for certain repairs. Should the investment be made?