3848093747

7

1.1. Zagadnienie transportowe

Ograniczenia wynikające z dostępności nawozów u poszczególnych dostawców mają postać:

x\\ + %12 + ^13 + ^14    < 5000

3^21 + 3:22 + 3:23 + £24    < 6000

X31 + Z32 + Z33 + £34 < 2500

Ponieważ ze względu na minimalizację kosztów transportu dostarczanie odbiorcom więcej towaru niż zamówili jest nieuzasadnione, więc ograniczenia wynikające z zapotrzebowań odbiorców mają postać:

X\\    +£21    +£31    = 6000

X\2    +3:22    +3^32    = 40 00

X\3    +3^23    +3:33    = 2000

£14    +£24    +£34 = 2500

Naturalnie Xij > 0 dla i = 1,..., m, j = 1,..., n.

W ogólności, celem jest minimalizacja łącznego kosztu transportu (1.1), przy założeniu, że całkowita ilość nawozu pochodząca od ż-tego dostawcy nie przekracza zapasu u tego dostawcy (1.2), a całkowita ilość nawozu dostarczona do j-tego odbiorcy jest równa jego zamówieniu (1.3). Założenie o nieujemności zmiennych (1.4) jest naturalne.

zminimalizować	m n y! ^cij^xij	(i.i)
	i=lj=l
n ^y^jxij < ai,	i = 1,... ,m	(1.2)
3=1
II	j = l,...,n	(1.3)
Xij >0, i = 1,..	. ,m,j = 1,... ,n	(1.4)

Zadanie transportowe w postaci (1.1)-(1.4) nazywa się zwykłym zadaniem transportowym, aby odróżnić je od innych wariantów, o których powiemy w dalszej części tego rozdziału. Ograniczenia (1.2) nazywamy warunkami bilansowymi dostawców, a ograniczenia (1.3) warunkami bilansowymi odbiorców.

Zadanie (1.1)-(1.4) jest zadaniem programowania liniowego. Zauważmy, że macierz współczynników w ograniczeniach ma szczególną postać (1.5).

cn	Z„	... Zn
Zn	C„	... Z„
z»	Z„	... Cn
. ^En	E„	... E„

gdzie C_n oraz Z_n są n-elementowymi wektorami takimi, że Ck = 1 ,k = 1,..., n, Zk = 0, k = 1,..., n, a E_n jest macierzą kwadratową o wymiarze n taką, że ekk = 1 ,&ki = 0,k ^ l,k = 1,...,n,l = 1,...,n. Macierz ta ma (m + n) wierszy oraz (m • n) kolumn.

Twierdzenie 1.1