Найти наименьший эле-

мент D(K,L) в массиве D(I,J)

найти новое

допустимое базисное нет

решение D(K,L) 0?

да

Оптимум найден

Рис3.

READY.

20 PRINT «Решение транспортной задачи»

30 REM в задаче рассматриваются М строк и N столбцов

40 READ M, N

50 REM массивы A(I) и B(J) являются общим обозначением строк

51 REM И СТОЛБЕЦ; МАССИВЫ DA(I) И DB(J) ПРЕДНАЧНАЧЕНЫ ДЛЯ

52 REM ХРАНЕНИЯ ИХ КОПИЙ; МАССИВЫ IP(I) И IC(J) УКАЗЫВАЮТ

53 REM (ЕСЛИ ИХ ЭЛЕМЕНТЫ РАВНЫ 1), ЧТО СООТВЕТСТВУЮЩИЕ СТРОКИ

54 REM И СТОЛБЦЫ БЫЛИ УДАЛЕНЫ; МАССИВЫ TP(I) И TC(J) ЯВЛЯЮТСЯ

55 REM СЧЕТЧИКАМИ БАЗИСНЫХ ПЕРЕМЕННЫХ В СТРОКАХ И СТОЛБЦАХ

60 DIM A(M), DA(M), B(N), DB(N), IR(M), IC(N), TR(M), TC(N)

65 REM МАССИВЫ IU(I) И IV(J) УКАЗЫВАЮТ (ЕСЛИ ИХ ЭЛЕМЕНТЫ

66 REM РАВНЫ 1), ЧТО ЭЛЕМЕНТАМ МАССИВОВ U И V БЫЛИ ПРИСВОЕНЫ

67 REM ЗНАЧЕНИЯ

70 DIM U(M), V(N), IU(M), IV(N)

80 DIM RT(M+N), CT(M+N)

85 REM МАССИВЫ C(I, J) СОДЕРЖИТ СТОИМОСТИ, МАССИВ X(I, J) –

90 REM НЕИЗВЕСТНЫЕ; МАССИВ IX(I, J) ОБОЗНАЧАЕМ БАЗИС, ЕСЛИ ЕГО

95 REM ЭЛЕМЕНТЫ РАВНЫ 1

100 DIM C(M, N), X(M, N), IX(M, N), D(M, N), MM(M, N)

105 REM ПРОЧИЕ МАССИВЫ ЯВЛЯЮТСЯ РАБОЧИМИ

110 REM ПОДРОБНОСТИ ОПИСАНЫ В ТЕКСТЕ

140 REM ВВЕСТИ СТОИМОСТИ, ОБЩИЕ СТРОКИ И СТОЛБЦЫ

150 FOR I=1 TO M

160 FOR J=1 TO N

170 READ C(I, J)

180 NEXT J

190 NEXT I

200 FOR I=1 TO M: READ A(I): DA(I)=A(I): NEXT I

210 FOR J=1 TO N: READ B(J): DB(J)=B(J): NEXT J

490 REM НАЙТИ НАИМЕНЬШУЮ СТОИМОСТЬ В МАССИВЕ C(RI, CJ)

500 C=0: CT=0: CR=0

510 RI=0: CJ=0: Y=IE10

600 FOR I=1 TO M

605 REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТРОКИ

610 IF IR(I)=1 THEN GOTO 670

620 FOR J=1 TO N

625 REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТОЛБЦЫ

630 IF IC(J)=1 THEN GOTO 660

640 IF C(I, J)>Y THEN GOTO 660

650 Y=C(I. J): RI=I: CJ=J

660 NEXT J

670 NEXT I

680 REM МИНИМАЛЬНЫЙ ЭЛЕМЕНТ ПО ВСЕМ СТРОКАМ И СТОЛБЦАМ

681 REM ПЕРЕСЛАТЬ В МАССИВ Х(RI, CJ)

685 REM ПОМЕТИТЬ БАЗИС В МАССИВЕ IX

690 REM УДАЛИТЬ СТРОКУ ИЛИ СТОЛБЕЦ И ПОМЕТИТЬ ИХ

695 REM ОПРЕДЕЛИТЬ ДРУГУЮ СУММУ, ПОДСЧИТАТЬ КОЛИЧЕСТВО

696 REM УДАЛЕНИЙ СТРОК

700 IF DA(RI)<=DB(CJ) THEN GOTO 760

710 X(RI, CJ)=DB(CJ)

720 IX(RI, CJ)=1

730 DA(RI)=DA(RI)-DB(CJ):DB(CJ)=0

740 IC(CJ)=1: C0=C0+1: CT=CT+1

750 GOTO 810

760 IF DA(RI)=DB(CJ) AND CR=M-1 THEN GOTO 710

770 X(RI, CJ)=DA(RI)

780 IX(RI, CJ)=1

790 DB(CJ)=DB(CJ)-DA(RI): DA(RI)=0

800 IR(RI)=1: C0=C0+1: CR=CR+1

810 TR(RI)=TR(RI)+1: TC(CJ)=TC(CJ)+1

820 IF C0<M+N-1 THEN GOTO 510

830 CR=CR+1

840 REM В СТРОКЕ 760 БЫЛИ ПРИНЯТЫ МЕРЫ К ТОМУ, ЧТОБЫ

850 REM НЕ УДОЛЯТЬ ВСЕ СТРОКИ, ПОКА ОСТАЮТСЯ СТОЛБЦЫ

990 REM НАЙТИ U И V, ПОЛОЖИВ ИХ СНАЧАЛА РАВНЫМИ 0

1000 FOR I=1 TO M

1010 IU(I)=0: U(I)=0

1020 NEXT I

1030 FOR J=1 TO N

1040 IV(J)=0: V(J)=0

1050 NEXT J

1060 REM НАЙТИ СТРОКУ С НАИБОЛЬШЕЙ БАЗИСНОЙ ПЕРЕМЕННОЙ,

1070 REM НАПРИМЕР СТРОКУ L

1080 T=0: L=0

1100 FOR I=1 TO M

1110 IF TR(I)<T THEN GOTO 1130

1120 T=TR(I): L=I

1130 NEXT I

1140 U(L)=0: IU(L)=1: C0=1: CR=1: CT=0

1150 FOR J=1 TO N

1160 IF IX(L, J)=0 THEN GOTO 1190

1170 V(J)=C(L, J): IV(J)=1

1180 CT=CT+1: C0=C0+1

1190 NEXT J

1195 REM ОБРАБОТАТЬ БАЗИСНЫЕ ПЕРЕМЕННЫЕ В ПОМЕЧЕННЫХ

1196 REM СТРОКАХ ИЛИ СТОЛБЦАХ

1200 FOR I=1 TO M

1210 FOR J=1 TO N

1220 IF IX(I, J)=0 THEN GOTO 1310

1230 IF IU(I)=0 AND IV(J)=0 THEN GOTO 1310

1240 IF IU(I)=1 AND IV(J)=1 THEN GOTO 1310

1250 IF IU(I)=0 AND IV(J)=1 THEN GOTO 1290

1260 V(J)=C(I, J)-U(I): IV(J)=1

1270 CT=CT+1: C0=C0+1

1280 GOTO 1310

1290 U(I)=C(I, J)-V(9J): IU(I)=1

1300 CR=CR+1: C0=C0+1

1310 NEXT J

1320 NEXT I

1325 REM ПРОВЕРИТЬ, ВСЕ ЛИ СТРОКИ И СТОЛБЦЫ БЫЛИ ПОМЕЧЕНЫ

1330 IF C0<>M+N THEN GOTO 1200

1340 PRINT “ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ”

1341 PRINT “U(I)”;: FOR I=1 TO M: PRINT U(I);: NEXT I: PRINT ””

1342 PRINT “V(J)”;: FOR J=1 TO N: PRINT V(J):; NEXT J: PRINT “”

1390 REM ЭЛЕМЕНТЫ С’(IJ) ПОМЕЩАЮТСЯ В МАССИВ D(I, J);

1395 REM ПРОВЕРИТЬ, РАВНЫ ЛИ ОНИ 0 ДЛЯ БАЗИСА

1400 FOR I=1 TO M

1410 FOR J=1 TO N

1420 IF IX(I, J)=0 THEN GOTO 1460

1430 D(I, J)=C(I, J)-U(I)-V(J)

1440 IF D(I, J)<>0 THEN PRINT “ОШИБКА 1”

1450 GOTO 1470

1460 D(I, J)=C(I, J)-U(I)-V(J)

1470 NEXT J

1480 NEXT I

1490 REM НАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ В МАССИВЕ D(I, J) И

1495 REM ПРИПЕСАТЬ ЕМУ ИНДЕКСЫ (K, L)

1500 T=0: K=0: L=0

1510 FOR I=1 TO M

1520 FOR J=1 TO N

1530 IF IX(I, J)=1 THEN GOTO 1560

1540 IF D(I, J)>=T THEN GOTO 1560

1550 T=D(I, J): K=I: L=J

1560 NEXT J

1570 NEXT I

1575 REM ЕСЛИ Т ВСЕ ЕЩЕ БОЛЬШЕ 0, ТО ВСЕ D(I, J) ПОЛОЖИТЕЛЬНЫ

1576 REM И ДАННОЕ РЕШЕНИЕ ОПТИМАЛЬНО

1580 IF T=0 THEN GOTO 4000

1581 PRINT “”: PRINT “C’KL=”T;: PRINT “K=”K;: PRINT “L=”:PRINT “”

1582 PRINT “”: GOSUB 5000

1585 REM В ПОДПРОГРАММЕ, НАЧИНАЮЩЕЙСЯ СО СТРОКИ 5000,

1586 REM ПЕЧАТАЕТСЯ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ

1990 REM НАЙТИ СЛЕДУЮЩЕЕ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ;

1995 REM СНАЧАЛА ВСЕ ИНДИКАТОРЫ И СЧЕТЧИКИ ПОЛОЖИТЬ РАВНЫ 0

2000 FOR I=1 TO M: IU(I)=0: NEXT I

2010 FOR J=1 TO N: IV(J)=0: NEXT J

2015 FOR I=1 TO M+N: RT(I)=O: CT(I)=0: NEXT I

2020 FOR I=1 TO M: FOR J=1 TO N

2030 D(I, J)=0: MM(I, J)=0

2040 NEXT J: NEXT I

2050 T=1: IP=0

2060 RT(T)=K: CT(T)=L

2070 D(K, L)=1: MM(K, L)=1: IU(K)=1

2071 PRINT T, K; L

2100 FR=0: FC=0: RI=RT(T): CJ=0

2110 FOR J=1 TO N

2120 IF FC=1 THEN GOTO 2180

2130 IF IX(RI, J)=0 THEN GOTO 2180

2140 IF IV(J)=1 THEN GOTO 2180

2150 IF MM(RI, J)=1 THEN GOTO 2180

2155 IF TC(J)=1 AND J=L THEN GOTO 2170

2160 IF TC(J)=1 THEN IP=1: GOTO 2180

2170 FC=1: CJ=J: IV(J)=1: J=N

2180 NEXT J

2190 IF CJ<>0 THEN GOTO 2300

2200 IF IP>0 THEN IP=0

2210 D(RT(T), CT(T))=0: T=T-1

2220 GOTO 2500

2300 T=T+1

2310 RT(T)=RI: CT(T)=CJ

2320 D(RI, CJ)=-1: MM(RI, CJ)=1

2321 PRINT T, RI; CJ

2400 IF CT(T)=L AND T>2 THEN GOTO 3000

2500 FR=0: FC=0: RI=0: CJ=CT(T)

2510 FOR I=1 TO M

2520 IF FR=1 THEN GOTO 2580

2530 IF IX(I, CJ)=0 THEN GOTO 2580

2540 IF IU(I)=1 THEN GOTO 2580

2550 IF MM(I, CJ)=0 THEN GOTO 2580

2560 IF TR(I)=1 AND IP=0 THEN IP=1: GOTO 2580

2570 FR=1: RI=I: IU(I)=1: I=M

2580 NEXT I

2590 IF RI<>0 THEN GOTO 2700

2600 IF IP>0 THEN IP=0

2610 D(RT(T), CT(T)=0: T=T-1

2620 GOTO 2100

2700 T=T+1: IP=0

2710 RT(T)=RI: CT(T)=CJ

2720 D(RT(T), CT(T))=1: MM(RI, CJ)=1

2721 PRINT T, RI; CJ

2730 GOTO 2100

3000 W=1E10: L=0: KK=0

3010 FOR I=2 TO T STEP 2

3020 IF X(RT(I),CR(I))>=W THEN GOTO 3040

3030 W= X(RT(I), CT(I)): KK=RT(I): LL=CT(I)

3040 NEXT I

3100 FOR I=1 TO T

3110 X(RT(I), CT(I))=X(RT(I), CT(I))+W*D(RT(I), CT(I))

3120 NEXT I

3200 IX(K, L)=1: IX(KK, LL)=0

3210 TR(K)=TR(K)+1: TR(KK)=TR(KK)-1

3220 TC(L)=TC(L)+1: TC(LL)=TC(LL)-1

3221 PRINT “W=”W;: PRINT “KK=”KK;: PRINT “LL=”LL

3222 PRINT “ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО”

3250 GOTO 1000

4000 PRINT “ОКОНЧЕННОЕ РЕШЕНИЕ”

4010 GOSUB 5000

4500 END

5000 CC=0

5010 PRINT “ I J XIJ CIJ СТОИМОСТЬ”

5020 FOR I=1 TO M

5030 FOR J=1 TO N

1320 NEXT I

1325 REM ПРОВЕРИТЬ ВСЕ ЛИ СТРОКИ И СТОЛБЦЫ БЫЛИ ПОМЕЧЕНЫ

1330 IF C0<>M+N THEN GOTO 1200

1340 PRINT “ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ”

1341 PRINT “U(I)”;: FOR I=1 TO M: PRINT U(I);: NEXT I: PRINT “”

1342 PRINT “V(J)”;: FOR J=1 TO N: PRINT V(J);: NEXT J: PRINT ””

1390 REM ЭЛЕМЕНТЫ C’(IJ) ПОМЕЩАЮТСЯ В МАССИВ D(I, J);

1395 REM ПРОВЕРИТЬ, РАВНЫ ЛИ ОНИ 0 ДЛЯ БАЗИСА

1400 FOR I=1 TO M

1410 FOR J=1 TO N

1420 IF IX(I, J)=0 THEN GOTO 1460

1430 D(I, J)=C(I, J)-U(I)-V(J)

1440 IF D(I, J)<>0 THEN PRINT “ОШИБКА 1”

1450 GOTO 1470

1460 D(I, J)=C(I, J)-U(I)-V(J)

1470 NEXT J

1480 NEXT I

1490 REM НАЙТИ НАИМЕНЬШИЙ ЭЛЕМЕНТ В МАССИВЕ D(I, J) И

1495 REM ПРИПИСАТЬ ЕМУ ИНДЕКСЫ (K, L)

1500 T=0: K=0: L=0

1510 FOR I=1 TO M

1520 FOR J=1 TO N

1530 IF IX(I,J)=1 THEN GOTO 1560

1540 IF D(I,J)>=T THEN GOTO 1560

1550 T=D(I,J): K=I: L=J

1560 NEXT J

1570 NEXT I

1575 REM ЕСЛИ Т ВСЕ ЕЩЕ БОЛЬШЕ 0, ТО ВСЕ В(I,J) ПОЛОЖИТЕЛЬНЫ

1576 REM И ДАННОЕ РЕШЕНИЕ ОПТИМАЛЬНО

1580 IF Y=0 THEN GOTO 4000

1581 PRINT ””: PRINT “C’KL=”T;: PRINT “K=”K:;PRINT “L=”:PRINT “”

1582 PRINT “”: GOSUB 5000

1585 REM В ПРОГРАММЕ, НАЧИНАЮЩЕЙСЯ СО СТРОКИ 5000,

1586 REM ПЕЧАТАЕТСЯ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ

1990 REM НАЙТИ СЛЕДУЮЩЕЕ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ;

1995 REM СНАЧАЛА ВСЕ ИНДИКАТОРЫ И СЧЕТЧИКИ

1996 REM ПОЛОЖИТЬ РАВНЫМИ 0

2000 FOR I=1 TO M: IU(I)=0: NEXT I

2010 FOR J=1 TO N: IV(I)=0: NEXT J

2015 FOR I=1 TO M+N: RT(I)=0: CT(I)=0: NEXT I

2020 FOR I=1 TO M: FOR J=1 TO N

2030 D(I,J)=0: MM(I,J)=0

2040 NEXT J: NEXT I

2050 T=1: IP=0

2060 RT(T)=K: CT(T)=L

2070 D(K,L)=1: MM(K,L)=1: IU(K)=1

2071 PRINT T,K;L

2100 FR=0: FC=0: RI=RT(T): CJ=0

2110 FOR J=1 TO N

2120 IF FC=1 THEN GOTO 2180

2130 IF IX(RI,J)=0 THEN GOTO 2180

2140 IF IV(J)=1 THEN GOTO 2180

2150 IF MM(RI,J)=1 THEN GOTO 2180

2155 IF TC(J)=1 AND J=L THEN GOTO 2170

2160 IF TC(J)=1 THEN IP=1: GOTO 2180

2170 FC=1: CJ=J: IV(J)=1: J=N

2180 NEXT J

2190 IF CJ<>0 THEN GOTO 2300

2200 IF IP>0 THEN IP=0

2210 D(RT(T),CT(T))=0: T=T-1

2220 GOTO 2500

2300 T=T+1

2310 RT(T)=RI: CT(T)=CJ

2320 D(RI,CJ)=-1: MM(RI,CJ)=1

2321 PRINT T,RI;CJ

2400 IF CT(T)=L AND T>2 THEN GOTO 3000

2500 FR=0: FC=0: RI=0: CJ=CT(T)

2510 FOR I=1 TO M

2520 IF FR=1 THEN GOTO 2580

2530 IF IX(I,CJ)=0 THEN GOTO 2580

2540 IF IU(I)=1 THEN GOTO 2580

2550 IF MM(I,CJ)=0 THEN GOTO 2580

2560 IF TR(I)=1 AND IP=0 THEN IP=1: GOTO 2580

2570 FR=1: RI=I: IU=1: I=M

2580 NEXT I

2590 IF RI<>0 THEN GOTO 2700

2600 IF IP>0 THEN IP=0

2610 D(RT(T),CT(T))=0: T=T-1

2620 GOTO 2100

2700 T=T+1: IP=0

2710 RT(T)=RI: CT(T)=CJ

2720 D(RT(T),CT(T))=1: MM(RI,CJ)=1

2721 PRINT T,RI;CJ

2730 GOTO 2100

3000 W=1E10: L=0: KK=0

3010 FOR I=2 TO T STEP 2

3020 IF X(RT(I),CR(I))>=W THEN GOTO 3040

3030 W=X(RT(I),CT(I)): KK=RT(I): LL=CT(I)

3040 NEXT I

3100 FOR I=1 TO T

3110 X(RT(I),CT(I))=X(RT(I),CT(I))+W*D(RT(I),CT(I))

3120 NEXT I

3200 IX(K,L)=1: IX(KK,LL)=0

3210 TR(K)=TR(K)+1: TR(KK)=TR(KK)-1

3220 TC(L)=TC(L)+1: TC(LL)=TC(LL)-1

3221 PRINT “W=”W;: PRINT “KK=”KK;: PRINT “LL=”LL

3222 PRINT “ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО”

3250 GOTO 1000

4000 PRINT “ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ”

4010 GOSUB 5000

4500 END

5000 CC=0

5010 PRINT “ I J XIJ CIJ СТОИМОСТЬ”

5020 FOR I=1 TO M

5030 FOR J=1 TO N

5040 IF IX(I,J)=0 THEN GOTO 5110

5050 PP=C(I,J)*X(I,J)

5060 CC=CC+PP

5070 PRINT I;J;

5080 PB=430: PA=X(I,J): GOSUB 9000

5090 PA=C(I,J): GOSUB 9000: PA=PP: GOSUB 9000

5100 PRINT “”

5110 NEXT J: NEXTI

5200 PRINT “ОБЩАЯ СТОИМОСТЬ РАВНА “;CC

5250 RETURN

9000 PC=INT(PB/100)

9010 P$=’’

9020 IF PC=0 THEN PRINT “”: GOTO 9040

9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC

9050 PD=INT(PC/10):PC=PC-10*PD

9060 IF PD=0 THEN PD=1

9070 IF PA<0 THEN P$=P$+”-”

9080 PE=ABS(PA)

9090 PE=PE+5*10^(-1-PC)

9100 IF PE>=10^PD THEN PRINT PA;: RETURN

9110 P$=P$+MID$(STR$(INT(PE)),2,PD)

9120 PRINT RIGHT$(P$,PD+1)

9130 IF PC=0 THEN RETURN

9140 PRINT ”.”;

9150 PE=INT((PE-INT(PE))*10^PC)

9160 P$=”000000000”

9170 P$=P$+MID$(STR$(PE),2,PC)

9180 PRINT RIGHT$(P$,PC);: RETURN

10000 DATA 3,5

10010 DATA 1,0,3,4,2

10020 DATA 5,1,2,3,3

10030 DATA 4,8,1,4,3

10040 DATA 15,25,20

10050 DATA 20, 12,5,8,15

READY.

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ

ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ

U(I)-4 0 0

V(J) 5 4 1 3 3

C’KL=-3 K= 2 L= 2

I J XIJ CIJ СТОИМОСТЬ

1 1 3 1 3

1 2 12 0 0

2 1 17 5 85

2 4 8 3 24

2 5 0 3 0

3 3 5 1 5

3 5 15 3 45

ОБЩАЯ СТОИМОСТЬ РАВНА 162

1 2 2

2 2 1

3 1 1

4 1 2

W= 12 KK= 1 L= 2

ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО

ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ

U(I)-4 0 0

V(J) 5 1 1 3 3

C’KL=-1 K= 3 L= 1

I J XIJ CIJ СТОИМОСТЬ

1 1 15 1 15

2 1 5 5 25

2 2 12 1 12

2 4 8 3 24

2 5 0 3 0

3 3 5 1 5

3 5 15 3 45

ОБЩАЯ СТОИМОСТЬ РАВНА 126

1 3 1

2 3 5

3 2 5

4 2 1

W= 5 KK= 2 L= 1

ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО