4

I have the following linear programming problem I would like to be verified:

enter image description here

I have sketched the problem in the following picture:

enter image description here

Here is my attempted solution:

I figured that I have ten variables (corresponding to the colored lines, between each building): $x_1, x_2, ..., x_{10}$ which are the amounts (in tons) of raw materials from Source 1 --> Plant A, Source 1 --> Plant B, Source 2 --> Plant A, Source 2 --> Plant B, Plant A --> Market 1, Plant A --> Market 2, ............, Plant B --> Market 3.

The formulation I get is the following:

$$\text{minimize}\;\;\; 1x_1 + 1.5x_2 + 2x_3 + 1.5x_4 + 4x_5 + 2x_6 + 1x_7 + 3x_8 + 4x_9 + 2x_{10}$$ $$\text{subject to}\;\;\;x_1 + x_2 = 10$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_3 + x_4 = 15$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_5 + x_8 = 8$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_6 + x_9 = 14$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_7 + x_{10} = 3$$ $$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;x_1 \ge 0, x_2 \ge 0, \cdots, x_{10} \ge 0.$$

I would appreciate if someone could verify the correctness of my answer :) Thank you for any help!

jjepsuomi
  • 8,619
  • 1
    It looks correct and well presented to me. You might consider to reduce the number of variables. Example: $x_8 = 8 - x_5$. You put the source and market constraints as equalities. In real situations, they might be inequalities. – Axel Kemper Aug 26 '13 at 07:25

2 Answers2

2

I think the term $1x_9$ is wrong in the minimisation, it should be $4x_9$. Rest is correct. Proceed further.

ADDED Now that you have edited it, it is corret.

Shobhit
  • 6,902
1

Your answer looks correct although I would advise you for the sake of clarity to introduce new variables separately for markets, plants and sources (so for instance $x_i$ for the sources $y_i$ for the plants etc.). Also, instead of writing equality signs in some of the constraints, it might be neater to write inequality signs,(for instance, the 3 market centers require... actually means at least) although it doesn't really matter for the outcome and your answer would also be considered correct. Good job :-)

dreamer
  • 3,379