Efstratios N. Pistikopoulos - Multi-parametric Optimization and Control

(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:

(2.18)

the solution of which features the minimal cost of , and the corresponding transport amounts as

(2.19)

In reality, the data in Table 2.1is time‐varying. Thus, the case of demand uncertainty is considered:

Given a set of plants with a constant supply and a set of markets with an uncertain demand bound between 0 and 1000 cases, and the distances between and , minimize the total transportation cost as a function of the demand.

Based on the LP problem ( 2.18), the following mp‐LP problem is formulated:

(2.20)

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 bound between 0 and 1000. The solution of problem ( 2.20) is reported in Table 2.3, which was obtained based on the solution strategies presented in Chapter 4.

The numbering of the constraints is according to their occurrence in problem ( 2.20), e.g. is constraint number 5.

Table 2.3The solution of problem ( 2.20).

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 .

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 solution of mp‐LP problems of type ( 2.2) based on the connected‐graph theorem [2]. All these developments were captured in the excellent textbook by Gal and Davis from 1979 [21], for which a second edition appeared in 1995 [22].

The algorithm from [2] remained the state‐of‐the‐art for over 25 years (see, e.g. [23,24]), until geometrical algorithms for general mp‐LP problems were developed starting in 2000, 5with the application of multi‐parametric programming to model‐predictive control [26,27]. Although the initial focus was put on mp‐QP problems, quickly publications concerning combination of model predictive control and mp‐LP problems were put forth [28–31], many of which were captured in this excellent review [32]. This new string of developments resulted in a deeper interest in the theoretical properties of mp‐LP problems, specifically in the case of degeneracy (see section 2.2), as well as the question of the presence of parameters in the left‐hand side of the constraints, i.e.