Masalah transportasi: seimbang dan tak seimbang

Masalah transportasi mengatur pengiriman dari beberapa sumber ke beberapa tujuan dengan biaya terkecil. Coffelt dan Hendrickson (§5.2) merumuskannya dengan tiga pertanyaan yang sama seperti di awal kelas: variabel keputusannya x_ij, banyak barang yang dikirim dari sumber i ke tujuan j; tujuannya meminimumkan jumlah c_ij × x_ij untuk semua rute; kendalanya pengiriman dari setiap sumber tidak melebihi pasokannya, setiap tujuan menerima paling sedikit permintaannya, dan semua x_ij nonnegatif.

Dengan m sumber dan n tujuan ada m × n variabel. Untuk linprog, variabel diratakan menjadi satu vektor, misalnya baris demi baris: x_11, x_12, …, x_1n, x_21, dan seterusnya. Kendala pasokan sumber i menjumlahkan n variabel berurutan; kendala permintaan tujuan j menjumlahkan satu variabel dari setiap baris.

Soal disebut seimbang bila total pasokan sama dengan total permintaan. Pada soal seimbang, semua pengiriman pasti habis, jadi kedua kelompok kendala bisa ditulis sebagai persamaan di A_eq. Bila pasokan melebihi permintaan, kendala pasokan harus tetap ≤ supaya kelebihannya boleh tinggal di sumber; memaksanya menjadi persamaan membuat soal tak layak. Bila permintaan melebihi pasokan, kendala permintaan ≥ tidak mungkin dipenuhi semuanya, dan linprog melaporkan status 2.

import numpy as np
# 2 pabrik, 2 kota: variabel [x11, x12, x21, x22]
A_eq = [[1, 1, 0, 0],   # pasokan pabrik 1
        [0, 0, 1, 1],   # pasokan pabrik 2
        [1, 0, 1, 0],   # permintaan kota 1
        [0, 1, 0, 1]]   # permintaan kota 2
b_eq = [30, 20, 25, 25]   # seimbang: 50 = 50