114 年 國立中央大學工業管理研究所碩士班《作業研究》

Solve the following linear programming (LP) problem and report your findings. For example, if the problem has no feasible solution, report "the problem is infeasible;" on the other hand, report an optimal solution if you can find one.
Note: You must show a detailed, step-by-step calculation process to receive full scores.

Minimize $x_1 + 1.5x_2 + 2.5x_3 + x_4 + 1.5x_5$
subject to
$3x_1 + 3x_2 + 6x_3 + 3x_4 + 9x_5 \geq 12$
$x_1 - x_2 + 1.5x_3 + 0.5x_4 + 0.5x_5 \geq 1.5$
$x_1, x_2, x_3, x_4, x_5 \geq 0$

The following is a simplex tableau for a minimization LP problem. As you know, such a tableau is simply a convenient way to express (or to represent) a normal LP model.

Part 2.1 (15 points)
What is the normal LP model that is expressed by the above simplex tableau?
Note: You must answer the complete LP model to receive full scores.
(請寫出上方表格所表示的LP模型。你必需寫出該模型完整的目標式及限制式,才能得到所有分數。)

Part 2.2 (15 points)
Please determine the status of the LP model that you answered in Part 2.1 and also provide sufficient reasons. For example, your answer may be that "the model can still be improved to lower its objective value,” or “the model has reached optimality," or "the model has no feasible solutions," or any other statuses. (接下頁)
注意:你的答案必須依據你在Part 2.1所回答的LP模型,而非依據題目所給的simplex tableau。同時,你必須給出明確的原因才能得到分數(提示:仔細檢視你在Part 2.1所回答的LP模型,看它是否有透露某些數學方面的訊息,以此來判定該模型的狀態)。

【模型背景描述】
A typical international supply chain (ISC) consists of a number of suppliers, manufacturing plants and distribution centers (DCs) which are located in different countries or even continents. To illustrate, the following figure shows an example of ISC which contains three suppliers S1, S2 and S3 located in China, U.S.A. and Mexico, respectively; this ISC has three manufacturing plants PL1, PL2 and PL3 located in Bangladesh, Mexico and Nicaragua, respectively; also, this ISC has two DCs (DC1 and DC2) located in New York and Los Angeles, respectively.

🖼️【此處有附圖，請對照原卷】

The following describes a basic (simplest) way as to how such an ISC may operate to produce products and then distribute them.

• A number of raw materials are used to make products. For simplicity, we would assume that all products are made with the same raw materials; furthermore, we would assume that all suppliers can supply all raw materials. Of course, there is a maximum quantity that each supplier j can supply each kind of raw material m, and we would denote such a quantity as $SC_{mj}$. Also, there is a specific quantity that each kind of raw material m must be used to make each unit of product i, and we would denote such a specific quantity as $R_{mi}$.

• For simplicity, assume that every manufacturing plant k can make every kind of product i. Obviously, k has a maximum capacity that it can produce i and we would use "units of finished i's" (i的完成品數量) to express this capacity (denoted as $UC_{ik}$). Also, k has a minimum quantity that it is obligated to produce i; this minimum quantity is denoted as $LC_{ik}$.

• In addition to $UC_{ik}$ and $LC_{ik}$, every manufacturing plant k has a maximum total capacity that it is allowed to use to make products and we would denote such a capacity as $CP_k$ (所有完成品的數量上限).

• When production processes are done, manufacturing plants will immediately transport finished products to DCs. Again, for simplicity, we would assume that every manufacturing plant k can transport every product i to every DC l, and we would not consider capacities in these transportation activities.

【模型開發】
There are two key decisions to be made for the above ISC.

• the amount of each kind of raw material m to be purchased from each supplier j for use of production at each manufacturing plant k (we would denote this decision variable as $G_{mjk}$)
• the units of each product i to be made at each manufacturing plant k and then transported to each DC l (we would denote this decision variable as $H_{ikl}$)

Note: When answering the following four questions (i.e., Parts 3.1 to 3.4), you MUST use and only use those decision variables and parameters that are given in each question. You will not receive any points if your answer includes any extra decision variables, parameters, definitions, assumptions, and so on.

Part 3.1: supply limits (10 points)
For each supplier j to supply each kind of raw material m:
Please use $G_{mjk}$ and $SC_{mj}$ only to derive a constraint ensuring that j will stay within its limits to supply m.

Part 3.2: production limits/obligations (10 points)
For every manufacturing plant k to make every kind of product i:
Please use $H_{ikl}$, $LC_{ik}$ and $UC_{ik}$ only to derive constraints ensuring that k will follow its production limits as well as production obligations to produce i.

Part 3.3: plants' maximum total capacities (10 points)
For every manufacturing plant k:
Please use $H_{ikl}$ and $CP_k$ only to derive a constraint ensuring that k will make products according to its maximum total capacity.

Part 3.4: raw material consumption (20 points)
For every manufacturing plant k to consume every kind of raw material m:
Please use $H_{ikl}$, $G_{mjk}$ and $R_{mi}$ to derive a constraint ensuring that the purchase of raw material m and the following production and transportation of product i is well governed (or controlled) by $R_{mi}$.