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

Find the optimal solution to the following linear programming (LP) problem by using one of
these two methods: the dual simplex method, or the dual simplex tableau method. You must show a
detailed calculation process to receive full points. Note: You will receive 0 points if you use any other
method to solve this problem.

Maximize $-10x_1 - 15x_2 - 25x_3 - 10x_4 - 15x_5$
subject to
$x_1 + x_2 + 2x_3 + x_4 + 3x_5 \ge 4$
$-6x_1 + 6x_2 - 9x_3 - 3x_4 - 3x_5 \le -9$
$x_1, x_2, x_3, x_4, x_5 \ge 0$

Consider the following LP problem where $s_1, s_2$ and $s_3$ are so-called slack variables; that is,
as you know, they are variables added to the constraints of the original problem for the purpose of
changing the "<" or ">" sign in the original constraints to an " = " sign.
Minimize $x_1 + 5x_2 + 5x_3$
subject to
$x_1 + s_1 = 4$
$x_2 + s_2 = 4$
$-x_1 + 2x_3 + s_3 = 4$
$x_1, x_2, x_3, s_1, s_2, s_3 \ge 0$

Suppose we want to use the first three columns of the coefficient matrix in the above constraints
as a basis (that is, this basis will consist of $[1, 0, -1]^T$ which is the vector formed by using the coeffi-
cients associated with $x_1$, $[0, 1, 0]^T$ which is the vector formed by using the coefficients associated
with $x_2$, and $[0, 0, 2]^T$ which is the vector formed by using the coefficients associated with $x_3$). What
is the basic feasible solution associated with such a basis? Or, explain why there is no basic feasible
solution associated with that basis. (求解與上述指定基底相對應的「基本可行解」,或說明該基
本可行解根本就不存在。) Note: You must use LP-related mathematics to solve this problem; oth-
erwise, you will receive 0 points. (必需以LP相關的數學計算來求解本問題,否則沒有分數。)

This question is about developing a mixed-integer programming (MIP) model which will help a truck driver make optimal decisions.
Consider the situation where a truck driver makes money by traveling along a route, picking up
goods from some of the nodes on that route, and then dropping the goods off at some other nodes.
Two of the major decisions that this truck driver must make are route selection and node selection.

Route selection
Route selection is about selecting a route along which the truck will travel to pick up and deliver
goods. There are several routes that the truck driver can select, and the rule is that the driver can select
only one of them. The following figure shows the case where there are a total of three routes and the
driver will select one of them. Note: In the general situation, the number of routes is an arbitrary (任
意) integer (as long as it is positive) and these routes may have different number of nodes.
🖼️【此處有附圖，請對照原卷】(圖示了三條路線，每條路線從 start node 到 end node，中間經過一些節點 m)

We will define a decision variable (決策變數) as follows to handle route selection.
$r_i$ is a binary decision variable which indicates whether the truck driver selects route $i$ or not in the
MIP model: $r_i = 1$ indicates the situation where the driver selects route $i$; $r_i = 0$ indicates the
situation where the driver does not select route $i$.

3.a (20%):
Let the total number of routes be $R$ ($R$ is a given number; for example, $R = 3$ in the above
figure). Please develop a linear constraint (線性限制式,亦即連結式子中的決策變數所使用的符
號,不是加號就是減號) to make sure this route selection requirement will always be met: The truck
driver can only select one route.

Node selection
After making the route selection decision, the next decision that the truck driver must make is
node selection, which means the driver must decide where (i.e., at which nodes) to stop along the
selected route so that the truck can be refueled (加油). The driver must select these nodes very care-
fully to make sure that the truck always carries enough fuel in its tank (油箱) to reach the end node,
or at least the truck can reach the next node where it can get another refuel. (Since refueling the truck
takes time and other fixed costs, it is obvious that the driver would not want to stop the truck unless
it is necessary.) The following figure shows the modeling approach that we will use to handle node
selection.
🖼️【此處有附圖，請對照原卷】(圖示了一條路線，從 start node 到 end node，中間經過節點 m，並定義了變數 $s_{i,m}$)

In the above, $s_{i,m}$ is another binary decision variable in the MIP model defined as follows.
$s_{i,m}$ is a binary decision variable indicating whether the truck should stop at node $m$ on route $i$ or not:
the truck will stop at node $m$ if $s_{i,m} = 1$ and the truck will not stop at that node if $s_{i,m} = 0$.

3.b (15%):
When deciding where to stop the truck, the driver only needs to consider those nodes which are
located on the selected route (that is, some route $i$ such that $r_i = 1$) and the reason should be quite
obvious. So in the MIP model, we want the value of $s_{i,m}$ to always be 0 if route $i$ is not selected; on
the other hand, the value of $s_{i,m}$ can be 1 or 0 if route $i$ is selected. Please develop a linear constraint
to enforce such a relationship between $r_i$ and $s_{i,m}$
for any node $m$ which is located on route $i$.

Fuel management
To make sure the truck will never run out of fuel before reaching the end node (永遠有足夠的
油可以抵達終點), we will need the following parameters (給定參數, 亦即它們的數值是已知的).
Fuel$_{i,m,n}$ the amount of fuel that the truck needs to travel from node $m$ to node $n$ on route $i$ (note:
this implies that $(m, n)$ is an edge on route $i$ as shown in the figure below)
TankCap the capacity of the tank onboard the truck (油箱容量)
BigNum a very big positive number (the value of BigNum can be preset to "999,999,999,999," for
example)

We also need the following decision variables.
$g_{i,m}$ nonnegative decision variable (that is, $g_{i,m} \ge 0$) used to record the amount of fuel that will be
pumped into the tank of the truck when it stops at node $m$ on route $i$.
$f_{i,m}$ nonnegative decision variable (that is, $f_{i,m} \ge 0$) used to record the amount of fuel carried in the
tank of the truck when it leaves node $m$ on route $i$.
The following figure shows how these parameters and decision variables are associated with the
nodes on route $i$.
🖼️【此處有附圖，請對照原卷】(圖示了路線 i，從 start node 到 end node，節點 m，變數 $f_{i,m}, g_{i,m}$ 和參數 Fuel$_{i,m,n}$)

Obviously, we need the following equation as a constraint to make sure that the truck will never
carry fuel more than the capacity of its tank.
$f_{i,m} \le \text{TankCap}$, for any node $m$ located on route $i$.

Also, we need the following constraint to control the value of $g_{i,m}$, so that fuel may be pumped
into the truck's tank only from nodes which are located on the selected route. (In the following con-
straint, if route $i$ is not selected causing $r_i = 0$, then $g_{i,m}$ will also be 0, which means no fuel can be
pumped into the truck's tank from node $m$. On the other hand, if route $i$ is selected, we will have
$r_i = 1$ which will allow the MIP model to determine an appropriate value for $g_{i,m}$.)
$g_{i,m} \le r_i \times \text{BigNum}$, for any node $m$ located on any route $i$.

3.c (15%):
Please derive a linear constraint to calculate the value of $f_{i,n}$, that is, the amount of fuel in the
tank of the truck when it is leaving node $n$ on route $i$.
$f_{i,n} = \underline{\hspace{2em}}$, for any edge $(m, n)$ along any route $i$.
Hint: You will need to use $f_{i,m}$, $g_{i,n}$, $r_i$ and Fuel$_{i,m,n}$ to complete the above constraint.