The optimal solution x = (2, 4, 0, 0, 0)T is the same for every value Furthermore, the value of the objective function (z = 8) remains unchanged because the variable is non-basic.

1.11. Application to an inventory problem

      Consider the problem of an automobile manufacturer that offers two models for sale, a small automobile and a large automobile. Suppose that there is sufficient demand that the manufacturer is certain to sell whatever is produced at the current sales price of 16,000 euros for large automobiles, and 10,000 euros for small ones. The manufacturer’s only problem is the limited supply of two raw materials, rubber and steel. Manufacturing a small automobile requires one unit of rubber and one unit of steel, whereas manufacturing a large automobile requires one unit of rubber and two units of steel. If the manufacturer has 400 units of rubber and 600 units of steel in stock, how many small and large vehicles should be produced from this inventory to maximize the turnover?

      Let x be the number of large automobiles manufactured, y the number of small automobiles manufactured and z the resulting turnover. The problem can therefore be expressed in the form:

      [1.21]

      1.11.1. Optimal solution

      It is relatively easy to find a graphical solution for systems like this with only two variables. This allows us to find the optimal solution x = 200 and y = 200, which corresponds to z = 5, 200, 000. In this particular example, the optimal solution is unique, corresponding to a vertex of the region bounded by the constraints.

1.11.2. Sensitivity to variation in stock

      Let us observe how the solution of the problem evolves when some of the starting data is modified, for example by increasing the stock of rubber or steel. Suppose that 700 units of steel are in stock instead of 600. The problem now becomes:

      [1.22]

      By solving graphically again, we find that the optimal solution is now x = 300 and y = 100, giving z = 5, 800, 000. In other words, increasing the available steel by 100 units increases the turnover by 600,000 euros. We say that the marginal price of a unit of steel is 6,000 euros.

      If the amount of steel in stock is increased to 800, the optimal solution becomes x = 400 and y = 0, and the turnover becomes z = 6, 400, 000. Increasing the steel in stock beyond 800 without also changing the rubber in stock no longer affects the optimal solution, because y is constrained to remain positive.

      Suppose now that the steel in stock remains fixed at 600, but the rubber in stock is increased by 400 to 500. The new problem is

      [1.23]

      Graphical solving shows that the optimal solution is now given by x = 100 and y = 400, which corresponds to z = 5, 600, 000. In other words, increasing the rubber by 100 units changes the turnover by 400,000 euros. We say that the marginal price of a unit of rubber is 4,000 euros.

      If the rubber in stock is increased to 600, the optimal solution becomes x = 0 and y = 600, and the turnover becomes z = 6, 000, 000. Increasing the amount of rubber in stock beyond 600, without also increasing the amount of steel in stock, no longer affects the optimal solution because x is constrained to remain positive.

1.11.3. Dual problem of the competitor

      Suppose now that the automobile manufacturer has a competitor who offers to repurchase all raw materials in stock to fulfill a large number of orders. The competitor must offer a certain price (assumed to be constant and denoted u) per unit of rubber and another price (denoted v) per unit of steel. For the offer to be accepted, the price paid by the competitor must at least be equal to the turnover that the manufacturer could achieve by manufacturing automobiles itself. The competitor’s problem can therefore be written as

      [1.24]

      Graphical analysis finds the optimal solution u = 4, 000 and v = 6, 000, which corresponds to a global price of p = 5, 200, 000. Observe (and we will see later that this is no coincidence) that the optimal solution of the competitor’s problem (the dual problem to the manufacturer’s primal problem) coincides with the marginal prices of the manufacturer’s problem, and the minimum price that the competitor can offer is equal to the manufacturer’s maximum turnover.

1.12. Using Matlab

      Matlab offers the linprog solver for optimizing LPs. The linprog solver takes the following input arguments:

      All linprog arguments use the following options, defined via the “optimoptions” input:

      The output arguments of the linprog solver are as follows:

      The