运输多面体

英文

transportation polytope

简介

一种与运输问题关联的多面体.它由如下方程和不等式组的解集所确定：对于给定两个非负向量a=(a₁，a₂，…，a_m)和b=(b₁，b₂，…，b_n)，

用M(a，b)表示这个运输多面体，它的阶为m×n.若M(a，b)的一个顶点，即mn维空间中的一个向量恰有m+n-1个非0分量，则称它为非退化的.若一个运输多面体，它的所有顶点全是非退化，则它本身是非退化的;否则，就是退化的.若a=(n，…，n)∈E_m和b=(m，…，m)∈E_n，则这时M(a，b)被称为中心运输多面体.设x=(x_ij)_{1≤i≤m，1≤j≤n}为M(a，b)的一个顶点，记

K(a，b，x)={(i，j)|x_ij>0，1≤i≤m，1≤j≤n}.

两个运输多面体M(a⁰，b⁰)和M(a¹，b¹)，a⁰，a¹∈E_m，b⁰，b¹∈E_n，若对于顶点x⁰∈M(a⁰，b⁰)和顶点x¹∈M(a¹，b¹)，有

K(a⁰，b⁰，x⁰)=K(a¹，b¹，x¹)，

则此两顶点是等价的.若对每个M(a⁰，b⁰)的顶点都有M(a¹，b¹)的一个顶点与它等价，并且对M(a¹，b¹)的一个顶点也有M(a⁰，b⁰)的一个顶点与它等价，则M(a⁰，b⁰)和M(a¹，b¹)为等价运输多面体.若a=b，则这时的M(a，b)称为对称运输多面体.对于运输多面体M(a，b)，若

其中M={1，2，…，m}，N={1，2，…，n}，

则两个运输多面体M(a⁰，b⁰)和M(a¹，b¹)是等价多面体当且仅当对任何(I，J)∈A_m×n，均有

其中，signμ表示取值μ的符号.对于一个运输多面体M(a，b)，若|A(a，b)|=k，则称它为k退化运输多面体.一个1退化运输多面体使得μ_L，P(a，b)=0，则称它为(L，P)退化的.