## Description

Question 1. Assume there are 5 clients that need to be supplied from a

warehouse. The following table lists the location of each of these clients in

terms of respective x and y coordinate values.

Client number Location in x coordinates Location in y coordinates

1 12 11

2 20 15

3 32 24

4 46 42

5 88 65

The distance is defined in terms of the sum of rectilinear movements, in

horizontal and vertical directions. (For instance, if warehouse is located at

the point (x, y), then its distance from the first client is |12 − x| +|11 − y| .)

(a) You are expected to come up with a linear programming model to choose

the coordinates of the location of the warehouse such that the sum of

the distances to all clients is as small as possible.

(b) How you modify your model in part (a) if your objective is to minimize

the largest of the five distance values?

1

Question 2. Consider the following linear programming model (LP):

min c1x − c2y

s.t. x − 2y ≤ 4

−x + y ≤ 3

x ≥ 0

y ≥ 0

Find positive coefficients c1 and c2 such that LP will have a unique optimal

solution.

Question 3. Consider the following tableau that corresponds to a maximizing LP in standard form. For each of the following parts, you need to change

the value of a single cell so that the stated condition is satisfied. Please carry

out a pivot operation after your change to see that, indeed, your answer takes

you to the desired state. Typically, more than one answer is acceptable. For

any positive number, write +1, and for any negative number, write -1 to

make grading easier.

(a) The bfs is optimal and there exists an alternate optimal bfs.

(b) The bfs is optimal and there exists alternate optimal solutions but only

one bfs which is optimal.

(c) The bfs is not optimal and x5 will become nonbasic after the next pivot.

(d) The bfs is not optimal and x3 will become basic after the next pivot.

2

(e) The bfs is degenerate.

Question 4. Turkish Airlines wants to plan seat arrangements for its upcoming flights that use 8 planes. The company currently has 20 planes to

choose from. There are two flight classes, namely economy, and business.

The plane room capacity is defined based on economy seats. Each plane can

seat up to 200 economy-class passengers. A business seat uses more room

and thus takes 1.5 times more seat room than an economy seat. The price of

a business ticket is two times that of an economy ticket. According to recent

regulations, if the total economy class seats over all 8 planes is less than a

certain threshold T (a given parameter), the company pays a penalty of $S

(another given parameter). Assume the ticket price for an economy seat is

$p (another given parameter).

(a) Formulate an integer programming model that will help Turkish Airlines

maximize its profit (total sales revenue-penalty cost (if any)) while obeying the capacity and operational limitations. Your model should be in

linear form.

(b) Now assume Turkish Airlines set a goal of G dollars for its upcoming

year’s total sales revenue (ignoring the penalty cost, if any). Formulate

this variant under the requirement that the maximum number of business

seats in each plane is minimum. You may define additional variables if

you like.

(c) Write the following additional restrictions due to some operational limitations in linear form to be appended to the model in part (a).

i. If both 1 and 5 are selected, then plane 6 or 8 or both should also

be selected.

ii. If neither plane 9 nor plane 10 is selected, then plane 4 should be

selected.

iii. Either at most two planes from the set {6,9,10} or at least four

planes from the set {1,4,5,13,15} should be selected.

iv. If at least one of planes 14, 17, and 19 is selected, then exactly one

of planes 15 or 20 should be selected.

3