4736387694

4. Rozważmy następujący problem programowania liniowego: znalezc maksimum

(1)

(2)

(3)

(4)

i=1 3=1

na zbiorze ograniczonym warunkami

^2, ^Xi3 — ^a*’ dla * = 1₅ 2,..., m, ó=i

Xij < bj, dla j = 1, 2,..., n,

i=i

{= 0, dla pewnych i,j,

> 0, dla pozostałych i,j.

Udowodnić, że powyższe zagadnienie jest równoważne zagadnieniu maksymalnego przepływu w sieci G = (V, E, s, t, c), gdzie

U = {s, Si,..., s_m, ti,... ,t_n,t},

E = {(s, Si); i = 1,..., m}U{(tj, i); j = 1, —,n}U{(sj, t,); gdy % ± 0},

c(s, s*) = a*, dla i = 1,..., m, c(tj,t) = bj, dla j = 1,..., n, c(a) = oo, dla pozostałych krawędzi.

5. Pewna firma produkująca kosmetyki ma fabrykę w mieście A oraz magazyn w mieście B. Firma ma też do dyspozycji ciężarówki, które poruszają się po ustalonej trasie. Wiadomo ile kartonów może dziennie przewieźć każda z ciężarówek. Firma nie ma wpływu na ładowność oraz trasy przejazdu ciężarówek (które są stałe). W fabryce powinna być produkowana taka ilość kosmetyków, które mogą być w ciągu jednego dnia przewiezione z miasta A do miasta B. Trasy przejazdu ciężarówek oraz ich ładowność są podane poniżej w postaci grafu. Ile maksymalnie kosmetyków dziennie może wyprodukować fabryka?

14