某公司仓库A存货物12吨，仓库B存货物8吨，现按7吨，8吨和5吨把货物分别运给甲，乙，丙三个商店，从仓库A运

Question

某公司仓库A存库12吨,仓库B存货8吨,现按7吨,8吨和5吨把货物分别调运给甲，乙，丙三个商店，从仓库A运货物到商店甲，乙，丙，每吨货物的运费分别8，6，9元，从仓库B运货物分别3，4，5元。问如何安排调运方案，才能使总费运最少？

Answer 1

这是线性规划问题：

设A调给a甲乙丙分别a1,a2,a3吨;B调给甲乙丙分别b1,b2,b3吨。总运费为W。则：

a1+a2+a3=12——1

b1+b2+b3=8——2

a1+b1=7——3

a2+b2=8——4

a3+b3=5——5

W=8a1+6a2+9a3+3b1+4b2+5b3——6

由6得,5a1+2a2+4a3+3(a1+b1)+4(a2+b2)+5(a3+b3)

带入3，4，5，得，W=5a1+2a2+4a3+78，再将1式带入，得W=3a1+2a3+102

所以只需要求w=3a1+2a3的最小值.整理得,l:a3=-3/2a1+w/2,而由1得，a3<=a1+12,(且由5式得知，a3<=5.)所以问题转化为在此限制条件下l在什么位置时其纵截距最小。如下图。（则直线l可以在两条虚线之间取。故l的位置应尽可能低；所以取（0，6）点时最佳；但由a3<=5.故只能取a3=5)在（1，5）点取得最小值。此时：a1=1,a2=6,a3=5,b1=6,b2=2,b3=0.算得W=115.