17 Given the following binary programming problem with one c

17. Given the following binary programming problem with one constraint:

a.   <ART FILE=\"11_18eq01.EPS\" W=\"171.441pt\" H=\"26.847pt\" XS=\"100%\" YS=\"100%\"/>

Maximize profit = $8,000X₁ + 5,000X₂ + 12,000X₃

                              + 14,000X₄ + 5,000X₅ + 6,000X₆

                              + 9,000X₇ + 10,000X₈

subject to              $65,000X₁ + 41,000X₂ + 75,000X₃

                              + 100,000X₄ + 55,000X₅

                               + 69,000X₆ + 82,000X₇

                              + 70,000X₈

Solution

Let us introduce a slack variable in our constraint so that

65,000X₁ + 41,000X₂ + 75,000X₃ + 100,000X₄ + 55,000X₅ + 69,000X₆ + 82,000X₇ + 70,000X₈ + s = 500,000

Now in matrix notation, this can be written as

Now making the coefficient if X₁=1, we get

The second row gives the values of X1, X2, ... , X8 and max Z = 79261.54