2.1. Thus, the amount of product shipped for all combinations needs to be determined. As there are two plants and two markets, this results in four variables, and a total cost given by:
(2.16)
where the coefficients are calculated according to Eq. (2.15). The next step is to formulate the constraints. The constraints are that (i) there cannot be more supply than amount in stock and (ii) the market demands needs to be satisfied. Mathematically, this can be written as
(2.17a)
(2.17b)
Additionally, note that transport can only be positive. This results in the LP problem of the form:
the solution of which features the minimal cost of
(2.19)
2.4.2 Considering Demand Uncertainty
In reality, the data in Table 2.1 is time‐varying. Thus, the case of demand uncertainty is considered:
Given a set of plants
Based on the LP problem (2.18), the following mp‐LP problem is formulated:
Note that the objective function does not change as the distances between the destinations do not change. However on the contrary to problem (2.18), problem (2.20) now features the uncertain demands as parameters
Remark 2.5
The numbering of the constraints is according to their occurrence in problem (2.20), e.g.
Table 2.3 The solution of problem (2.20).
|
|
2.4.3 Interpretation of the Results
In Table 2.3, it is shown that the solution to problem (2.20) is given by three critical regions. This means that for different demand values, there is a change in which of the constraints in problem (2.20) is active.
The first critical region: For the first critical region, the third and fourth constraints, together with the non‐negativity of , are active. These are the constraints that define the market demand, given from the deterministic values in Eq. (2.17b). Thus, the solution within the first critical region is only concerned with fulfilling the market demand, as the supply limits are not relevant (see second and third critical regions). Consequently, the optimal solution goes along the cheapest transportation routes, which are Seattle to Chicago (cost in objective function: 178) and San Diego to Topeka (cost in objective function: 151). The amount that is transported is thereby given by the market demand, i.e. and .
The second critical region: The second critical region is obtained, when the market demand of Chicago, , exceeds the supply of Seattle, which is 350. This is apparent in the new active set, which includes the supply constraint of Seattle (the first constraint). Then, in order to fulfill the demand, there needs to be a supply from San Diego, and thus , , while the demand from Topeka can still be fulfilled from San Diego with .
The third critical region: Similarly to the second critical region, the third critical region results when San Diego is unable to meet all the demands from Topeka, as the supply limit of 600 is reached. Then, the supply constraint from San Diego becomes active (the second constraint), and in order to fulfill the demand, material will be transported from Seattle to Topeka, and thus , , while the demand from Chicago is met from Seattle with .
Infeasible region: As soon as the sum of the demand, , is greater than the available supply, , there is no possibility to meet all the demands with the supply given. Thus, there is no feasible solution for .
2.5 Literature Review
The idea to consider the variation of a parameter in an LP problem was reportedly first put forth in the unpublished master thesis by William Orchard‐Hays in 1952, as reported in [14], where the variation of the right‐hand side of the constraints was considered:
(2.21)
Subsequently, several researchers proposed algorithms for the treatment of the single parameter case [15–20], but it was not until 1972 when the seminal paper by Gal and Nedoma described for the first time a rigorous strategy for the general
