Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

E4004 2022 Midterm

Problem 1:    (40 points)

1.  Given A e Rm ×n  and b e Rm , show that the following mathematical program

min    lAx _ blo

北eR们

can be cast as a linear program, where lylo  := max{ly1 l, . . . , lym l}.

Write it in standard form.

2.  Consider the following linear program

max              c3 x3 + c5 x5

北1 ,北2 ,北3 ,北4 ,北5 ≥0

x1      +            +     x3                              _    2x5      =      3

subject to            ．           +    x2      +    2x3                             +    3x5      =    13

(                         +     x3        +    x4      +    2x5      =      8

Is x =  (7, 0, 2, 0, 3)T  a solution when  (c3 , c5 ) =  (1, 2)?  What about when (c3 , c5 ) = (2, 1)?

Problem 2:    (40 points)    A chocolate maker produces an assortment of chocolates.  An assortment is made up of three types of chocolates denoted 1, 2, and 3, which cost 40$/kg, 14$/kg, and 24$/kg respectively. Chocolate 1 must represent between 10% and 20% of the weight of an assortment. An assortment should weight between 1kg and 1.2kg and will be sold 80$/kg. Chocolate 1 and 2 together should not weight more than 800g. At least half of the weight of an assortment should contain chocolates 1 and 3. Formulate a linear program which solves the following problem:  which proportion of each type of chocolate should the maker use to maximize the profit from the sale of the assortment?

Problem 3:    (20 points)

1.  Given A e Rm ×n  and b e Rm , write the dual of the linear program

北eR们 , yeR‰                                                                                                                                                                   x, y > 0

and exhibit a dual feasible point.

2.  Consider a linear program in standard form that admits a solution at a vertex x e Rn such that xB  > 0 and xN  = 0, where N = {1, . . . , n}/B and a B is a basis of the columns of A. Assume the matrix AB  formed by the columns of A in the basis B is a square invertible matrix. Show that the dual is feasible and has a unique solution.