ТРА́НСПОРТНАЯ ЗАДА́ЧА

ТРА́НСПОРТНАЯ ЗАДА́ЧА, один из важ­ных ча­ст­ных слу­ча­ев об­щей за­да­чи ли­ней­но­го про­грам­ми­ро­ва­ния. Со­дер­жа­тель­но Т. з. фор­му­ли­ру­ет­ся сле­дую­щим об­ра­зом. В пунк­тах $A_1$,$...$,$A_m$ про­из­во­дит­ся не­ко­то­рый од­но­род­ный про­дукт, при­чём объ­ём про­из-ва это­го про­дук­та в пунк­те $A_i$ со­став­ля­ет $a_i$ еди­ниц, $i=1,...,m$. Этот про­дукт нуж­но дос­та­вить в пунк­ты по­треб­ле­ния $B_1$,$...$,$B_n$, при­чём объ­ём по­треб­ле­ния в пунк­те $B_j$ со­став­ля­ет $b_j$ еди­ниц, $j=1,...,n$. Пред­по­ла­га­ет­ся, что транс­пор­ти­ров­ка про­дук­та воз­мож­на из лю­бо­го пунк­та про­из-ва в лю­бой пункт по­треб­ле­ния и транс­порт­ные из­держ­ки, при­хо­дя­щие­ся на пе­ре­воз­ку еди­ни­цы про­дук­та из пунк­та $A_i$ в пункт $B_j$, со­став­ля­ют $c_{ij}$ де­неж­ных еди­ниц. За­да­ча со­сто­ит в ор­га­ни­за­ции та­ко­го пла­на пе­ре­во­зок, при ко­то­ром сум­мар­ные транс­порт­ные из­держ­ки бы­ли бы ми­ни­маль­ны­ми.

Фор­маль­но Т. з. ста­вит­ся сле­дую­щим об­ра­зом. Пусть $x_{ij}$ – ко­ли­че­ст­во про­дук­та, пе­ре­во­зи­мо­го из пунк­та $A_i$ в пункт $B_j$. Тре­бу­ет­ся най­ти со­во­куп­ность из $mn$ не­от­ри­ца­тель­ных ве­ли­чин $x_{ij}$, удов­ле­тво­ряю­щих ус­ло­ви­ям $$\sum^n_{j=1} x_{ij}=a_i,\quad i=1,...,m,\\ \sum^m_{j=1} x_{ij}=b_j\quad j=1,...,n, \tag{*}$$ и об­ра­щаю­щих в ми­ни­мум сум­му $$\sum_{i=1}^m\sum_{j=1}^n c_{ij} x_{ij}.$$

Груп­па ог­ра­ни­че­ний (*) оз­на­ча­ет, что объ­ём про­дук­та, вы­ве­зен­но­го из ка­ж­до­го пунк­та про­из-ва, ра­вен про­из­ве­дён­но­му, а объ­ём про­дук­та, вве­зён­но­го в ка­ж­дый пункт по­треб­ле­ния, сов­па­да­ет с по­треб­но­стью. При этих ог­ра­ни­че­ни­ях не­об­хо­ди­мым и дос­та­точ­ным ус­ло­ви­ем раз­ре­ши­мо­сти Т. з. яв­ля­ет­ся вы­пол­не­ние ус­ло­вия ба­лан­са