• 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 
 • 






1. .
2.


:
)
.
)
.
3.
:
) .
) ..
4. :
) .
)
Pascal.
) .
1. .

, .
蠠 ,


堠 .
, , ,
,


.
.
1 , J1 J2 ... Jj ... Jn R1 R2 ... Ri ... Rm C1,1 C2,1 ... Ci,1 ... Cm,1 C1,2 C2,2 ... Ci,2 ... Cm,2 ... ... ... ... ... ... C1,j C2,j ... Ci,j ... Cm,j ... ... ... ... ... ... C1,n C2,n ... Ci,n ... Cm,n b1 b2 ... bi ... bm a1 a2 ... aj ... an

,
1.
i,j, ,

, ,
Ri Jj . i,j
蠠 . , , ,


,



.  



(
)
,

(
).  

.
,
,
,


.

( ), Xi,j i,
Jj, Xi,j * Ci,j , .

( ) ,
,


,

.


,

.




,

.
,
,

.

, ,

.

.  



,
堠 .
,
,
, , (bi), (aj ) (Ci,j )
.

Sbi (i=1...m) Saj
(j=1...n),

(-) . Saj
¹ Sbi , ().
,
.
,
.
,
.

.
2.



: m
1, 2 , ..., m ,
-

1, 2,
... , m .
n 1 , 2
, ... , n
b1 , b2
, ... , bn .
i,j


i

j .
i,j,

.
ꠠ (,
),
,

.

,
..

.
.

.

. , - ,
,

.
,
- .

:

.
2 1 2 3 4 5 i 1 10 8 5 6 9 48 2 6 7 8 6 5 30 3 8 7 10 8 7 27 4 7 5 4 6 8 20 蠠 bj 18 27 42 12 26 125



(-
).
. 1 󠠠
18 .
48, -
1 ,
18 (1,1).
1 ,
1
30
.
2 (27 ), 27 (1,2); 3
1 3.
3
39 .
30
2,
, 蠠 9
3.
18
3 12
4;
6
5,

20
4
.
;


.
,

ࠠ ,
. ,
, .

:

Òàáëèöà
¹3 1 2 3 4 5 i 1 10 18 8 27 5 3 6 9 48 2 6 7 8 30 6 5 30 3 8 7 10 9 8 12 7 6 27 4 7 5 4 6 8 20 20 蠠 bj 18 27 42 12 26 125

,
,


i,j .

,
Ai Bj, ,
.
,
Bj.
- . , ,

4.

, Ci,j Ci,k Ai Bj
Bk . , ,
, . , ,
2: C2,1 = C2,4,
b1 b4, 4
(2,1).
Òàáëèöà
¹4 1 2 3 4 5 i 1 10 8 5 42 6 6 9 48 2 6 4 7 8 6 5 26 30 3 8 7 27 10 8 7 0 27 4 7 14 5 4 6 6 8 20 蠠 bj 18 27 42 12 26 125

- . ,
Bi Aj Cj,i.
, ,
.
, F0 = 1039,
F0 = 723.
,

, .
m + n - 1.
,
,

m + n - 1. 젠 ࠠ
.


. ,
, 4:
m + n - 1 = 4 + 5 - 1 = 8,
7,
3 2 0. (3,5).

-
Ci,j, ,
.




,
- . , , 18
(1,1)
(2,1)


18
(2,3)
(1,3).
.
( 1039)
(
913)

126
.
18



:
5 1 2 3 4 5 i 1 10 8 27 5 21 6 9 48 2 6 18 7 8 12 6 5 30 3 8 7 10 9 8 12 7 6 27 4 7 5 4 6 8 20 20 蠠 bj 18 27 42 12 26 125



.

,
,

90.

:

1.) 2.) 3.)
,
, ().

+ ,
,
- ,
.
. -
, , ,
,
. ,



:


,


.
,
.

:
.



.

,
,

+,
-. g.



g.

k
kg. ,

, . ,

kg.
, ,


,
.


, , ,
.


,

,
,


. , ,
,
-:
()
,



.


m + n - 1 .
,

.
,


,

,

.
, , ,

.
k, ,
,
(
, ).



;




.

,
:


.


,
.

.

.




.



å xi,j = ai ( i=1..m ; j=1..n );
å xi,j =bj
( j=1..n ; 1..m ),
å ai
= å bj òî
åñòü çàêðûòàÿ
çàäà÷à.

Ai Bj C i,j ;
.
(xi,j ),

.



.

Ai

( )
- ai ;


Bj
(
) bj .
(). ai + bj = či,j (
i=1..m ;j=1..n) či,j
Ai Bj . , 蠠
ai bj
; , ꔠ

-
.
,
(ai bj )

.
(ai bj ) či,j
C i,j.
. , (xi,j) ( (m + n -1).
xi,j >0.

(ai bj ) ,
:
či,j = ai + bj = i,j , 蠠 xi,j >0.
( xi,j = 0),



.

,


.
:

ꠠ (xi,j > 0)
ai + bj = či,j=
i,j ,

( xi,j =0)
ai + bj = či,j≤ i,j ,

.
,

,

.
:
či,j=
i,j (
) (1)
či,j≤ i,j (
) (2)
,

( ai bj ) Ai Bj ( i=1,...,m ; j=1,...,n ).


: . ,

頠 .

,
-
,
(1).

,
; , . ,
.


:

(ai bj )
(1),


: gi,j= i,j - či,j.



:
.


()
.
 
󠠠

(,
). m + n - 1 , m , n
.
(ai bj ), ,

:
ai + bj = i,j (3)
(3)
m + n - 1,
m +
n. ,

(, ). m + n -
1 (3)

ai , bj ,
: či,j= ai + bj
.
Òàáëèöà
¹6 1 2 3 4 5 ai 1 10 č = 7 8 č = 6 5 42 6 6 9 č = 6 0 2 6 4 7 č = 5 8 č = 4 6 č = 5 5 26 -1 3 8 č = 8 7 27 10 č = 6 8 č = 7 7 0 1 4 7 14 5 č = 6 4 č = 5 6 6 8 č = 6 0 bj 7 6 5 6 6
,

či,j £ i,j
, £
³

, , .

(
),


,
. ࠠ

.
6
či,j ³ i,j
, .
, či,j - i,j ìàêñèìàëüíà.
 íàøåì
ñëó÷àå â
îáîèõ êëåòêàõ
ðàçíîñòü
îäèíàêîâà (ðàâíà
1), ïîýòîìó, äëÿ
ïîñòðîåíèÿöèêëà
âûáåðåì,
íàïðèìåð,
êëåòêó (4,2):
Òàáëèöà
¹7 1 2 3 4 5 ai 1 10 8 5 42 6 6 9 0 2 6 + 4 7 8 6 5 - 26 -1 3 8 7 - 27 10 8 7 + 0 1 4 7 - 14 5 + û 4 6 6 8 0 bj 7 6 5 6 6

14, , ,
- .
14
-
+ .

ai bj è öèêë ðàñ÷åòîâ
ïîâòîðÿåòñÿ.
,


.
1.
, m + n - 1
(
).
2.

(ai bj )
,


.

, ,
.
3.
蠠 či,j = ai + bj
. , , .
4.
,
,

(

).
5.


, ,

, ,

.
2
:

: F0
= 723,
F1 = 709,
F2 = Fmin = 703.
,
,
Fmin = 703.
.
 

,
:
å i = å bj ( i=1,...,m ; j=1,...,n ) (4)

, ,

. 堠

(4) .  


.

2- :
1.


å i > å bj ( i=1,...,m
; j=1,...,n );
2.

å i < å bj ( i=1,...,m
; j=1,...,n );



,
.
:

.
 
A1,
A2, ... , Am a1, a2, ... , am; B1, B2, ... , Bn
b1,
b2, ... , bn,
å i > å bj ( i=1..m ; j=1..n ).

(X),

,
.
-
-,
.
n
å Xi,j
≤ ai (i=1,
... , m);
j=1
m
å Xi,j
= bj (j=1,
... , n).
i=1

,



.

, ,
-. ,
,


. , n
1, B2, ... , Bn,

, ,
Bn+1,
,

bn+1 = å i - å bj ( i=1,...,m
; j=1,...,n ) ,



bn+1
.
B n+1
b n+1

.

.


,
Am+1 am+1



.
4. :
.
m
1, 2 , ..., m ,
-
1, 2, ... , m . n
1 , 2
, ... , n
b1 , b2 , ... , bn . i,j


i 
j .
i,j, 堠
.

(,
),
,
.
,
( ).
Pascal:
Program
transportnaj_zadatsha;
Uses Crt;
Label l1;
Const N=6;
n1=7; n2=7;
Sa:longint=0;
Sb:longint=0;
Type
predpr=Array [1..N] of longint;
rasp=Array [1..N,1..N] of longint;
Var
A,B,alfa,betta,B_d,x:predpr;
c,p:rasp;
f,f0,x_min,Sp:longint;
Nt,x_p,r,r_min,ki,kj,Na,Nb,h,l,i,j:byte;
d:char;
u:Array[1..N*N] of byte;
Procedure Nul
(var a:predpr); { }
var i:byte;
Begin
for i:=1 to N do a[i]:=0;
End;
Procedure
PrintS (x,y:byte; s:string; c:byte);
Begin { s}
TextColor(c);
GotoXY(x,y);
Write(s);
End;
Procedure
Print (x,y:byte; n:byte; a:longint; c:byte);
Begin { a}
TextColor(c);
GotoXY(x,y); Write(' ':n);
GotoXY(x,y); Write(a);
End;
Procedure Rid
(var x:longint; y:byte); { x}
var
i:integer;
s:string;
c:char;
j,k:byte;
Begin
s:=''; i:=1;
TextColor(11);
Repeat
c:=ReadKey;
Case ord(c) of
48..57: begin s:=s+c;
Write(c);
inc(i);
end;
8: if i>1 then begin dec(i);
Delete(s,i,1);
Write(chr(8),'
',chr(8));
end;
end;
j:=WhereX;
GotoXY(60,1); ClrEOL;
if i>y then begin
TextColor(4);
Write(' ');
for k:=1 to y-1 do Write('9');
TextColor(11);
end;
GotoXY(j,1);
Until (ord(c)=13) and (i<y+1);
val(s,x,i);
End;
Procedure
goriz (a,b,c,d,e:char);
{ goriz, wertic}
var
i,j:byte; {
Tabl }
Begin
Write(a);
for i:=1 to n2 do Write(b);
Write(c);
for i:=1 to Nb do begin
for j:=1 to n1 do Write(b);
if i<>Nb then Write(d) else
Write(c);
end;
for i:=1 to 4 do Write(b);
Write(e);
End;
Procedure
wertic;
var i:byte;
Begin
Write('',' ':n2,'');
for i:=1 to Nb-1 do Write(' ':n1,'');
WriteLn(' ':n1,'',' ' :4,'');
End;
Procedure
Tabl;
Begin
ClrScr;
TextColor(1);
h:=6+Na*3;
l:=14+Nb*7;
GotoXY(1,3);
for i:=3 to h do wertic;
GotoXY(1,2);
goriz('+','-','-','-','+');
for i:=1 to Na+1 do begin
GotoXY(1,i*3+2);
if (i=1) or (i=Na+1)
then goriz('','-','+','+','')
else goriz('+','-','+','+','');
end;
GotoXY(1,h+1);
goriz('+','-','-','-','+');
TextColor(9);
for i:=1 to Na do begin
GotoXY(5,i*3+3);
Write('A',i);
end;
for i:=1 to Nb do begin
GotoXY(i*(n1+1)+n2-2,3);
Write('B',i);
end;
l:=Nb*(n1+1)+n2+3;
h:=Na*3+6;
PrintS(4,3,'\Bj',9);
PrintS(4,4,'Ai\',9);
PrintS(1,1,' N1',14);
PrintS(l,4,'alfa',9);
PrintS(3,h,'betta',9);
End;
Procedure W_W
(var a:predpr; b:byte; c:char); { }
var
i,l,m:byte;
{- }
Begin
{. .}
for i:=1 to b do begin
TextColor(3);
GotoXY(32,1);
ClrEOL;
Write(c,i,'= ');
Rid(a[i],n1);
TextColor(14);
Case c of
'A': GotoXY(n2-trunc(ln(a[i])/ln(10)),i*3+4);
'B': GotoXY(n2+i*(n1+1)-trunc(ln(a[i])/ln(10)),4);
end;
Write(a[i]);
end;
End;
Function
FF:longint; {
}
var i,j:byte;
f:longint;
Begin
f:=0;
for i:=1 to Na do
for j:=1 to Nb do
if p[i,j]>0 then
inc(f,c[i,j]*p[i,j]);
GotoXY(65,Nt+2);
TextColor(10);
Write('F',Nt,'=',f);
FF:=f;
End;
Function
a_b:boolean; { }
var
k,i,j:byte; {alfa betta}
Z_a,Z_b:predpr;
d:boolean;
Begin
Nul(Z_a); Nul(Z_b);
alfa[1]:=0; Z_a[1]:=1; k:=1;
Repeat
d:=1=1;
for i:=1 to Na do
if Z_a[i]=1 then
for j:=1 to Nb do
if (p[i,j]>-1) and
(Z_b[j]=0) then begin
Z_b[j]:=1;

betta[j]:=c[i,j]-alfa[i];
inc(k);
d:=1=2;
end;
for i:=1 to Nb do
if Z_b[i]=1 then
for j:=1 to Na do
if (p[j,i]>-1) and
(Z_a[j]=0) then begin
Z_a[j]:=1;

alfa[j]:=c[j,i]-betta[i];
inc(k);
d:=1=2;
end;
Until (k=Na+Nb) or d;
if d then begin
i:=1;
While Z_a[i]=1 do inc(i);
j:=1;
While Z_b[j]=0 do inc(j);
p[i,j]:=0;

Print((j+1)*(n1+1)+n2-8,i*3+4,1,p[i,j],7);
end;
a_b:=d;
End;
Procedure
W_p; { }
var
i,j,h,l,k:byte;
c_max:longint;
Begin
k:=0;
for i:=1 to Na do begin
h:=i*3+4;
for j:=1 to Nb do begin
l:=j*(n1+1)+n2-5;
GotoXY(l,h);
Write(' ':n1);
if p[i,j]>0 then begin
inc(k);

Print(l-trunc(ln(p[i,j])/ln(10))+5,h,1,p[i,j],14);
end
else if p[i,j]=0 then begin

Print(l+n1-2,h,1,p[i,j],14);
inc(k);
end;
end;
end;
While a_b do inc(k);
if k>Na+Nb-1 then PrintS(40,1,'k >
n+m-1',12);
End;
Function
kkk(var ki,kj:byte):integer; { . k}
var
i,j:byte; {
}
k,k_min:integer;
b:boolean;
Begin
b:=1=1;
for i:=1 to Na do
for j:=1 to Nb do
if p[i,j]=-1 then begin
k:=c[i,j]-alfa[i]-betta[j];
if b then begin
b:=1=2;
ki:=i; kj:=j; k_min:=k;
end else
if k<k_min then begin
k_min:=k;
ki:=i; kj:=j;
end;
TextColor(6);
GotoXY(j*(n1+1)+n2-5,i*3+4);
Write('(',k,')');
end;
if k_min<0 then
PrintS(kj*(n1+1)+n2,ki*3+4,'X',12);
kkk:=k_min;
End;
Procedure
div_mod(c:byte; var a,b:byte);
{}
Begin {
}
b:=c mod Nb; a:=c div Nb +1; { }
if b=0 then begin
b:=Nb; dec(a);
end;
End;
Procedure
Rek(Xi,Yi:byte; var z:boolean; var c:byte);
var i,j:byte;
Begin { .}
z:=1=2; { }
Case c of
1: for i:=1 to Na do
if i<>Xi then
if p[i,Yi]>-1 then begin
if u[(i-1)*Nb+Yi]=0 then begin

u[(Xi-1)*Nb+Yi]:=(i-1)*Nb+Yi;
c:=2;
Rek(i,Yi,z,c);
if z then exit;
end;
end
else if (i=ki) and (Yi=kj) then
begin

u[(Xi-1)*Nb+Yi]:=(ki-1)*Nb+kj;
z:=not z;
exit;
end;
2: for i:=1 to Nb do
if i<>Yi then
if p[Xi,i]>-1 then begin
if u[(Xi-1)*Nb+i]=0 then begin

u[(Xi-1)*Nb+Yi]:=(Xi-1)*Nb+i;
c:=1;
Rek(Xi,i,z,c);
if z then exit;
end;
end
else if (Xi=ki) and (i=kj) then
begin

u[(Xi-1)*Nb+Yi]:=(ki-1)*Nb+kj;
z:=not z;
exit;
end;
end;
u[(Xi-1)*Nb+Yi]:=0;
c:=c mod 2 +1;
End;
Procedure
kontur; {
}
var
i,j,k,mi,mj,l:byte;
z:boolean;
p_m:longint;
Begin
for i:=1 to N*N do u[i]:=0;
l:=1;
Rek(ki,kj,z,l);
i:=ki; j:=kj;
k:=u[(i-1)*Nb+j];
div_mod(k,i,j);
mi:=i; mj:=j; l:=1;
Repeat
inc(l);
k:=u[(i-1)*Nb+j];
div_mod(k,i,j);
if l mod 2=1 then
if p[i,j]<p[mi,mj] then begin
mi:=i; mj:=j;
end;
Until (i=ki) and (j=kj);
i:=ki; j:=kj; l:=0;
p_m:=p[mi,mj];
Repeat
if l mod 2=0 then begin
inc(p[i,j],p_m);

PrintS((n1+1)*j+n2-1,i*3+3,'(+)',12);
end else begin
dec(p[i,j],p_m);

PrintS((n1+1)*j+n2-1,i*3+3,'(-)',12);
end;
if l=0 then inc(p[i,j]);
k:=u[(i-1)*Nb+j];
div_mod(k,i,j);
inc(l);
Until (i=ki) and (j=kj);
p[mi,mj]:=-1;
End;
Procedure
Pauza;
var d:char;
Begin
TextColor(6);
GotoXY(40,1);
Write(' ');
d:=ReadKey;
GotoXY(40,1);
ClrEOL;
End;
BEGIN
Nul(alfa); Nul(betta);
Nt:=1;
ClrScr;
TextColor(10);
Repeat
Write('
(2<=Na<=',N-1,') ');
ReadLn(Na);
Write('
(2<=Nb<=',N-1,') ');
ReadLn(Nb);
Until (Na>1) and (Na<=N-1) and
(Nb>1) and (Nb<=N-1);
Tabl;
(*******************
******************)
PrintS(1,1,'
:',3);
W_W(A,Na,'A');
W_W(B,Nb,'B');
TextColor(3);
GotoXY(1,1); ClrEOL;
Write(' ');
for i:=1 to Na do
for j:=1 to Nb do begin
TextColor(3);
GotoXY(29,1); ClrEOL;
Write('A',i,' - B',j,' ');
Rid(c[i,j],5);

Print((n1+1)*j+n2-4,i*3+3,1,c[i,j],11);
end;
(**********************************************************)
GotoXY(1,1);
ClrEOL;
TextColor(14);
Write(' N1');
for i:=1 to Na do Sa:=Sa+A[i];
for i:=1 to Nb do Sb:=Sb+B[i];
if Sa<>Sb then begin { }
PrintS(20,1,' (
)',7);
d:=ReadKey;
if Sa>Sb then begin
inc(Nb);
B[Nb]:=Sa-Sb;
for i:=1 to Na do c[i,Nb]:=0;
end else begin
inc(Na);
A[Na]:=Sb-Sa;
for i:=1 to Nb do c[Na,i]:=0;
end;
Tabl;
for i:=1 to Na do
for j:=1 to Nb do
Print((n1+1)*j+n2-4,i*3+3,1,c[i,j],11);
for i:=1 to Na do

Print(n2-trunc(ln(A[i])/ln(10)),i*3+4,1,A[i],14);
for i:=1 to Nb do
Print(n2+i*(n1+1)-trunc(ln(B[i])/ln(10)),4,1,B[i],14);
PrintS(20,1,' ',7);
end
else PrintS(20,1,' ',7);
(**************
c ****************)
for i:=1 to Nb do B_d[i]:=B[i];
for i:=1 to Na do begin
for j:=1 to Nb do x[j]:=j;
for j:=1 to Nb-1 do begin
x_min:=c[i,x[j]];
r_min:=j;
for r:= j+1 to Nb do
if (x_min>c[i,x[r]]) or
((x_min=c[i,x[r]]) and
(B[x[r]]>b[x[r_min]])) then
begin
x_min :=c[i,x[r]];
r_min:=r;
end;
x_p:=x[r_min];
x[r_min]:=x[j];
x[j]:=x_p;
end;
Sp:=0;
for j:=1 to Nb do begin
p[i,x[j]]:=B_d[x[j]];
if p[i,x[j]]>A[i]-Sp then
p[i,x[j]]:=A[i]-Sp;
inc(Sp,p[i,x[j]]);
dec(B_d[x[j]],p[i,x[j]]);
end;
end;
(***********************************************************)
for i:=1 to Na do
for j:=1 to Nb do if p[i,j]=0 then
p[i,j]:=-1;
W_p;
f:=FF; f0:=F;
While a_b do;
for i:=1 to Na do
Print(l+1,i*3+3,3,alfa[i],14);
for i:=1 to Nb do
Print(i*(n1+1)+n2-4,h,6,betta[i],14);
Pauza;
(*******
******)
While kkk(ki,kj)<0 do begin
kontur;
pauza;
for i:=1 to Na do
for j:=1 to Nb do
PrintS((n1+1)*j+n2-1,i*3+3,' ',14);
inc(Nt);
GotoXY(1,1);
Write(' N',Nt);
W_p;
f0:=f; f:=FF;
if a_b then Goto l1;
for i:=1 to Na do
Print(l+1,i*3+3,3,alfa[i],14);
for i:=1 to Nb do
Print(i*(n1+1)+n2-4,h,6,betta[i],14);
Pauza;
end;
(***********************************************************)
PrintS(40,1,' ',12);
PrintS(60,1,'(any key)',6);
for i:=1 to Na do
for j:=1 to Nb do if p[i,j]=-1 then
begin
h:=i*3+4;
l:=j*(n1+1)+n2-5;
GotoXY(l,h);
Write(' ':n1);
end;
GotoXY(40,1);
l1:
d:=ReadKey;
END.

Turbo Pascal 7.0.
:
. . . . . . . . . . . . . . .

      ©2010