Solusi Awal Masalah Transportasi

Transportation
Problem

Fungsi

•untuk memecahkan masalah pengiriman komoditas dari suatu sumber (mis. Pabrik) ke tujuan
(mis. Gudang)

•untuk mengatur distribusi dari sumber-sumber yang menyediakan produk yang sama, ke tempat-
tempat yang membutuhkan secara optimal.

•memecahkan masalah bisnis, pembelanjaan modal, alokasi dana untuk investasi, analisis lokasi,
keseimbangan lini perakitan dan perencanaan serta scheduling produksi.

Tujuan

•agar biaya distribusi dapat ditekan seminimal mungkin

•Memecahkan permasalahan distribusi (alokasi)

•Memecahkan permasalahan bisnis lainnya, seperti masalah-masalah yang meliputi pengiklanan,
pembelanjaan modal (capital financing) dan alokasi dana untuk investasi, analisis lokasi,
keseimbangan lini perakitan dan perencanaan scheduling produksi

Ciri-Ciri

Kendala

Example

Powerco has three electric power plants that supply the needs of four cities. Each power plant can
supply the following numbers of kilowatt-hours (kwh) of electricity: plant 1—35 million; plant 2—50
million; plant 3—40 million (see Table 1). The peak power demands in these cities, which occur at
the same time (2 P.M.), are as follows (in kwh): city1—45 million; city 2—20 million; city 3—30
million; city 4—30 million. The costs of sending 1 million kwh of electricity from plant to city
depend on the distance the electricity must travel. Formulate an LP to minimize the cost of
meeting each city’s peak power demand.

Constraint (Kendala)

Supply Constraint

Demand Constraint

General Description of a
Transportation Problem

1.

A set of m supply points from which a good is shipped. Supply point 𝑖 can supply at most si
units. In the Powerco example, 𝑚 = 3, 𝑠1 = 35, 𝑠2 = 50, and 𝑠3 = 40.

2.

A set of n demand points to which the good is shipped. Demand point j must receive at least
dj units of the shipped good. In the Powerco example, 𝑛 = 4, 𝑑1 = 45, 𝑑2 = 20, 𝑑3 = 30, and
𝑑4 = 30.

3.

Each unit produced at supply point 𝑖 and shipped to demand point 𝑗 incurs a variable cost of
𝑐𝑖𝑗. In the Powerco example, 𝑐12 = 6.

Let 𝑥𝑖𝑗 = 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑢𝑛𝑖𝑡𝑠 𝑠ℎ𝑖𝑝𝑝𝑒𝑑 𝑓𝑟𝑜𝑚 𝑠𝑢𝑝𝑝𝑙𝑦 𝑝𝑜𝑖𝑛𝑡 𝑖 𝑡𝑜 𝑑𝑒𝑚𝑎𝑛𝑑 𝑝𝑜𝑖𝑛𝑡 𝑗 then the general formulation of a
transportation problem is

If

then total supply equals total demand, and the problem is said to be a balanced transportation problem.

Balancing a Transportation Problem If Total Supply Exceeds Total Demand

◦ If total supply exceeds total demand, we can balance a transportation problem by creating a dummy

demand point that has a demand equal to the amount of excess supply.

Balancing a Transportation Problem If Total Supply Is Less Than Total Demand

◦ Creating a dummy supply point.

A transportation problem is specified by the supply, the demand, and the shipping costs, so
the relevant data can be summarized in a transportation tableau (see Table 2). The square,
or cell, in row 𝑖 and column 𝑗 of a transportation tableau corresponds to the variable 𝑥𝑖𝑗. If
𝑥𝑖𝑗 is a basic variable, its value is placed in the lower left-hand corner of the 𝑖𝑗th cell of the
tableau. For example, the balanced Powerco problem and its optimal solution could be
displayed as shown in Table 3. The tableau format implicitly expresses the supply and
demand constraints through the fact that the sum of the variables in row 𝑖
must equal 𝑠𝑖 and the sum of the variables in column 𝑗 must equal 𝑑𝑗.

Finding Basic Feasible Solutions
for Transportation Problems

We are now ready to discuss three methods that can be used to find a basic feasible solution for a
balanced transportation problem:

1.

Northwest corner method

2.

Minimum-cost method / Least Cost

3.

Vogel’s method

Northwest Corner Method

We illustrate the use of the Northwest corner method by finding a bfs for the balanced
transportation problem in Table 15. (We do not list the costs because they are not needed to
apply the algorithm.)

Minimum-Cost Method for Finding
a Basic Feasible Solution

The northwest corner method does not utilize shipping costs, so it can yield an initial bfs that has
a very high shipping cost. Then determining an optimal solution may require several pivots. The
minimum-cost method uses the shipping costs in an effort to produce a bfs that has a lower total
cost. Hopefully, fewer pivots will then be required to find the problem’s optimal solution

To begin the minimum-cost method, find the variable with the smallest shipping cost (call it 𝑥𝑖𝑗).

Vogel’s Method for Finding a
Basic Feasible Solution

Begin by computing for each row (and column) a “penalty” equal to the difference between the
two smallest costs in the row (column). Next find the row or column with the largest penalty.
Choose as the first basic variable the variable in this row or column that has the smallest shipping
cost.

Observe that Vogel’s method avoids the costly shipments associated with 𝑥22 and 𝑥23.
This is because the high shipping costs resulted in large penalties that caused Vogel’s
method to choose other variables to satisfy the second and third demand constraints.

Of the three methods we have discussed for finding a bfs, The Northwest corner method requires
the least effort, and Vogel’s method requires the most effort. Extensive research [Glover et al.
(1974)] has shown, however, that when Vogel’s method is used to find an initial bfs, it usually
takes substantially fewer pivots than if the other two methods had been used. For this reason, the
Northwest corner and minimum-cost methods are rarely used to find a basic feasible solution to a
large transportation problem.

Multiple Choice

Apakah termasuk balanced transportation problem?

• YA

• TIDAK

Multiple Choice

Manakah dari jawaban di bawah ini yang menunjukkan solusi awal dengan Northwest Corner?

Multiple Choice

Berapakah ongkos/biaya yang harus dibayarkan dengan solusi Northwest corner?

• 3260

• 3250

• 2100

• 2200

Multiple Choice

Manakah dari jawaban di bawah ini yang menunjukkan solusi awal dengan Least Cost?

Multiple Choice

Berapakah ongkos/biaya yang dibayarkan dengan solusi Least Cost?

• 2250

• 2200

• 2150

• 2100

Multiple Choice

Manakah dari jawaban di bawah ini yang menunjukkan solusi awal dengan Vogel Approximation Method (VAM)?

Multiple Choice

Manakah dari jawaban di bawah ini yang menunjukkan solusi awal dengan Vogel Approximation Method (VAM)?

• 1990

• 1980

• 1900

• 1890

Poll

Dari ketiga metode untuk mencari solusi awal masalah transportasi, apakah sudah ada yang optimal?

• ada yang optimal

• belum optimal semua

• belum tentu optimal

• tidak tahu

Poll

Apakah anda paham dengan penjelasan materi ini?

• paham sekali

• sedikit paham

• tidak paham

• bingung menerapkan ke soal