Скачать реферат, курсовой Реферат Транспортная задача бесплатно

Этот реферат, курсовую работу на тему "Реферат "Транспортная задача"" вы может совершенно бесплатно скачать с этого портала, как и другие работы. Эти работы помогут школьнику, студенту, абитуриенту. Необходимым условием при использовании Реферат "Транспортная задача" и других рефератов с нашего порталаявляется их использование только в личных целях без коммерческой выгоды.

-.

Можно также изменить критерий оптимальности. Например, вместо (i,j) использовать новый критерий оптимальности (i,j).

Постановка транспортной задачи на ЭВМ.

Программа решения транспортной задачи нетривиальна. Для облегчения понимания мы разбили эту программу на части. Приведем сначала блок-схему решения транспортной задачи (рис1.1).

Теперь приведем блок-схему определения первого допустимого базисного решения строки (500-840) (рис1.2).

В конце этой процедуры все элементы массива DA(I) и DB(J) должны быть равны 0. Переменные TR(I) и TC(I) должны быть равны количеству переменных соответственно в I-й строке и в J-м столбце.

В следующей процедуре (строки 1000 – 1585) вычисляются u и v и наименьшее значение сij, предположим сkl (рис1.3).

Ввести m,n

массивов хij; сij; аi,bj,ui, vj, а также

счетчикам и рабочим массивам

вычислить базисное допустимое

решение по правилу “самая

дешевая продукция реализу-

ется первой”

вычислить коэффициенты

и для базисного

допустимого решения

найти для небазисных перейти к базисному

переменных допустимому решению

все ли нет

?

Да

Оптимальное решение получено

Рис1.

Процедура перехода к новому базисному допустимому решению (начиная со строки 2000 до строки 3250) заслуживает внимательного изучения. Поясним ее подробнее. Сначала находим “цепь” w клеток, которая не является тупиковым путем” (строки 2050 – 2730).

Найти наименьший элемент C(I,J)

текущего массива C(RI,CJ)

нет

DA(RI)0

да

Проверить, что удалено не более М-1 Положим X(RI,CJ)=DB(CJ) и

строк. Положить X(RI,CJ)=DA(RI) и пометить этот элемент как

пометить этот элемент как базисный. базисный. Заменить DA(RI)

Заменить DB(CJ) на DB(CJ)-DA(RI). на DA(RI)-DB(CJ). Удалить

Удалить строку RI и подсчитать столбец и посчитать количество

количество удалений удалений

нет

Увеличить TR(RI) и TC(CJ) на 1

Количество базисных

переменных меньше

чем М N-1?

Введите следующую программу

для определения u и v

Рис2.

На шаге 1 мы находимся в клетке (K,L), T - счетчик шагов, IP индикатор “тупикового пути”, (RT(T), CT(T))(RI,CJ) – клетка, в которую мы попадаем на шаге Т. Массив D состоит из 1, соответствующих w; положим ММ=1, если клетка используется, IU=1 и IV=1, если строки и столбцы входят в цикл.

В команде 2100 на шаге Т ищется строка RT(T) для столбца, содержащего базисную переменную в неиспользованном столбце (строка 2140) в неотмеченной клетке (строка 2150). Если это единственная переменная в своем столбце, то производится присваивание IP=1 (строка 2170). Разумеется, это не делается в начальном столбце L. После того как подходящая переменная найдена в столбце CJ, поиск прекращается; при этом FC=1.

Затем T увеличивается для следующего шага, в переменную RT(T) заносится номер текущей строки, а в переменную СT(T) – номер только что найденного столбца CJ; соответствующему D присваивается значение –1, и найденная клетка помечается присвоением ММ значения 1 (строка 2320). Если мы снова оказались в столбце L, откуда начали, то цикл завершен (строка 2400). В противном случае ищем столбец СT(T)[ СJ] для строки, содержащей базисную переменную в неотмеченных строке и клетке; таким образом снова помечаются “тупиковые пути”. Как только искомый столбец найден, поиск прекращается присвоением FR=1. Затем T увеличивается для следующего шага, переменной RT(T) присваивается номер только что найденной строки RI, а CT(T) - -номер только что обрабатывавшегося столбца; для этой клетки осуществляются присвоения: D= 1, MM=1,после чего программа возвращается к поиску строки в строке 2100 программы.

Заметим, что если в процессе поиска строки не удается найти столбец (СJ=0 в строке 2190), не являющийся “тупиковым путем”, то происходит возвращение (строка 2210) к строке предыдущего поиска столбца. Если в поисках столбца удается найти только строки (RI=0 в строке 2590), соответствующие тупиковым путям, то осуществляется возвращение (строка 2610) к строке предыдущего поиска строки. Однако в силу того, что ММ сохраняет свое значение, ошибка не повторяется в дальнейшем (ММ=1 в строках 2150 и 2550). Поскольку базис задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано из строки 2400 в строку 3000.

В строках 3000 – 3040 программы содержится наименьшая базисная переменная из клеток, в которых D=-1. Здесь определяются значение w и положение переменной (KK,LL), которая будет удалена из базиса. В строках 3100 3120 клетки включаются в цепь. В конечном счете переменная (K,L) определяются как базисная, переменная (KK,LL) – как небазисная и определяется количество базисных переменных во всех строках и столбцах. Затем программа возвращается к вычислению симплекс-множителей u и v.

При работе программы печать (u и v) в строках 1340 – 1342 и наибольшего по модулю значения сij в строке 1581, а также печать в строках 2071, 2321 и 2721 могут быть подавлены. Последние три строки отражают цепи и обратный поиск. Печать в строке 3221, определяющая w и переменную для удаления из базиса, тоже могут быть подавлена.

Приводимые данные соответствуют примеру 1. читателю следует проследить за шагами решения. Принятый путь не соответствует нашему полученному вручную решению, но настолько же законен. На самом деле, первые два из полученных допустимых базисных решений вырождены.

Положим u и w, а также указатели

строк и столбцов равными 0

Базисных переменных (строка L).

Положить U(L)=0, пометить строкуL

IU(L)=1, подсчитать помеченные строки

Для занятых ячеек в строке L

Положить V(J)=C(L,J), пометить

столбцы IV(J)=1 и подсчитать

помеченные столбцы

Для занятых ячеек в помеченных

строках положить V(J)=C(I,J)-U(I).

Для занятых ячеек в помеченных

столбцах положить U(I)=C(I,J)-V(J).

Подсчитать помеченные столбцы и

строки

нет да

Все строки и столбцы найти и переслать

помечены? их в массив D(I,J)

мент 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

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)

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 NEXTJ

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 C0M 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 CJ0 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 RI0 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 NEXTI

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

1330 IF C0M 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 CJ0 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 RI0 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

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

Назад
В начало реферата

Если у вас есть аналогичные работы Реферат "Транспортная задача" сообщите нам об этом. Также нам будет интересны рефераты, дипломные работы по теме Реферат "Транспортная задача", а также курсовые работы. Присылайте их нам, помогите в учебе другим людям.

Скачайте и откройте один из архивов. После этого вам будет доступен для скачивания файл: Скачать реферат, курсовой Реферат Транспортная задача бесплатно . Если файл не скачивается, воспользуйтесь дополнительной ссылкой и распакуйте следующий архив.
	Скачать реферат, курсовой Реферат Транспортная задача бесплатно
	Зеркало: Скачать реферат, курсовой Реферат Транспортная задача бесплатно
	Зеркало 2: Скачать реферат, курсовой Реферат Транспортная задача бесплатно
	Файл: Скачать реферат, курсовой Реферат Транспортная задача бесплатно - был проверен антивирусом Kaspersky Antivirus . Вирусов не обнаружено!