Transportation problem: Difference between revisions

From Rosetta Code
Content added Content deleted
(+1)
Line 522: Line 522:


=={{header|1C}}==
=={{header|1C}}==
<lang>перем m,n; // Размер таблицы
<lang>перем m,n; // Table size
перем u,v;
перем u,v;
перем БазисныеЯчейки;
перем БазисныеЯчейки;
перем iЦикл, jЦикл;
перем iЦикл, jЦикл;
перем Цены, Спрос, Предложение, Отгрузки; // Массивы транспортной задачи
перем Цены, Спрос, Предложение, Отгрузки; // Arrays of the transportation problem
перем i1, j1;
перем i1, j1;
перем СпросОстаток, ПредложениеОстаток;
перем СпросОстаток, ПредложениеОстаток;
Line 550: Line 550:
Прервать;
Прервать;
ИначеЕсли ПредложениеОстаток[i]<0 Тогда
ИначеЕсли ПредложениеОстаток[i]<0 Тогда
ВызватьИсключение("Ошибка: остаток предложения меньше 0");
ВызватьИсключение("Error: balance of the offer less than 0");
КонецЕсли;
КонецЕсли;
чОбъем=СпросОстаток[j];
чОбъем=СпросОстаток[j];
Line 556: Line 556:
Продолжить;
Продолжить;
ИначеЕсли чОбъем<0 Тогда
ИначеЕсли чОбъем<0 Тогда
ВызватьИсключение("Ошибка: остаток спроса меньше 0");
ВызватьИсключение("Error: balance of the demand less than 0");
КонецЕсли;
КонецЕсли;
Если ПредложениеОстаток[i]<чОбъем Тогда
Если ПредложениеОстаток[i]<чОбъем Тогда
Line 583: Line 583:
КонецЦикла;
КонецЦикла;
Если чОбъем<>Предложение[i] Тогда
Если чОбъем<>Предложение[i] Тогда
ВызватьИсключение("Ошибка: отгрузки по строке не равны предложению в строке "+i);
ВызватьИсключение("Error: shipment on the line does not equal the proposal in the row "+i);
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецЦикла;
Line 592: Line 592:
КонецЦикла;
КонецЦикла;
Если чОбъем<>Спрос[j] Тогда
Если чОбъем<>Спрос[j] Тогда
ВызватьИсключение("Ошибка: отгрузки по столбцу не равны спросу в столбце "+j);
ВызватьИсключение("Error: shipment by the column does not equal to the demand in the column "+j);
КонецЕсли;
КонецЕсли;
КонецЦикла;
КонецЦикла;
Line 612: Line 612:
Для i=1 по m Цикл
Для i=1 по m Цикл
Если u[i]=НеОпределено Тогда
Если u[i]=НеОпределено Тогда
Сообщить("Не удалось вычислить потенциал u["+i+"]");
Сообщить("Failed to evaluate the potential u["+i+"]");
Возврат Ложь;
Возврат Ложь;
КонецЕсли;
КонецЕсли;
Line 618: Line 618:
Для j=1 по n Цикл
Для j=1 по n Цикл
Если v[j]=НеОпределено Тогда
Если v[j]=НеОпределено Тогда
Сообщить("Не удалось вычислить потенциал v["+j+"]");
Сообщить("Failed to evaluate the potential v["+j+"]");
Возврат Ложь;
Возврат Ложь;
КонецЕсли;
КонецЕсли;
Line 627: Line 627:
Функция ВычислениеПотенциаловПоВертикали(j)
Функция ВычислениеПотенциаловПоВертикали(j)
Если v[j]=НеОпределено Тогда
Если v[j]=НеОпределено Тогда
ВызватьИсключение("Ошибка получения потенциала v["+j+"]");
ВызватьИсключение("Failed to get the potential v["+j+"]");
КонецЕсли;
КонецЕсли;
Для i=1 по m Цикл
Для i=1 по m Цикл
Line 645: Line 645:
гл_сч=гл_сч-1;
гл_сч=гл_сч-1;
Если гл_сч=0 Тогда
Если гл_сч=0 Тогда
ВызватьИсключение("Зацикливание при вычислении потенциалов");
ВызватьИсключение("Looping in the calculation of potential");
КонецЕсли;
КонецЕсли;
Если u[i]=НеОпределено Тогда
Если u[i]=НеОпределено Тогда
ВызватьИсключение("Ошибка получения потенциала u["+i+"]");
ВызватьИсключение("Failed to get potential u["+i+"]");
КонецЕсли;
КонецЕсли;
Для j=1 по n Цикл
Для j=1 по n Цикл
Line 719: Line 719:
КонецЦикла;
КонецЦикла;
Если ок=0 Тогда
Если ок=0 Тогда
ВызватьИсключение("Не существует не базисной (нулевой) ячейки для ввода в базис");
ВызватьИсключение("There is no nonbasic (zero) cell entry into the basis");
КонецЕсли;
КонецЕсли;
Пока 1=1 Цикл
Пока 1=1 Цикл
Line 728: Line 728:
КонецЕсли;
КонецЕсли;
Если Отгрузки[i][j]<>0 Тогда
Если Отгрузки[i][j]<>0 Тогда
ВызватьИсключение("Ненулевые отгрузки для не базисной ячейки");
ВызватьИсключение("Nonzero shipment for nonbasic cell");
КонецЕсли;
КонецЕсли;
БазисныеЯчейки[i][j]=1;
БазисныеЯчейки[i][j]=1;
Line 749: Line 749:
гл_сч=гл_сч-1;
гл_сч=гл_сч-1;
Если гл_сч=0 Тогда
Если гл_сч=0 Тогда
ВызватьИсключение("Слишком большое число итераций при поиске цикла");
ВызватьИсключение("Too many iterations in the cycle search");
КонецЕсли;
КонецЕсли;
Для j=1 по n Цикл
Для j=1 по n Цикл
Line 792: Line 792:
Сообщить("Перераспределение по циклу "+iЦикл.Количество());
Сообщить("Перераспределение по циклу "+iЦикл.Количество());
Если jЦикл.Количество()<>iЦикл.Количество() Тогда
Если jЦикл.Количество()<>iЦикл.Количество() Тогда
ВызватьИсключение("Не одинаковые размерности для координат цикла");
ВызватьИсключение("Unequal dimension coordinates cycle");
КонецЕсли;
КонецЕсли;
Если iЦикл.Количество()<4 Тогда
Если iЦикл.Количество()<4 Тогда
ВызватьИсключение("Цикл имеет меньше 4 элементов");
ВызватьИсключение("Cycle is less than 4 items");
КонецЕсли;
КонецЕсли;
Тета=НеОпределено;
Тета=НеОпределено;
Line 817: Line 817:
КонецЦикла;
КонецЦикла;
Если Тета=НеОпределено Тогда
Если Тета=НеОпределено Тогда
ВызватьИсключение("Не удалось вычислить переменную тета.");
ВызватьИсключение("Failed to evaluate variable theta.");
КонецЕсли;
КонецЕсли;
Сообщить("Тета="+Тета);
Сообщить("Тета="+Тета);
Line 857: Line 857:
КонецЦикла;
КонецЦикла;
Если чПредложение>чСпрос Тогда
Если чПредложение>чСпрос Тогда
Сообщить("Предложение больше спроса на "+(чПредложение-чСпрос)+" единиц груза. Создайте фиктивного потребителя.");
Сообщить("Offering more than the demand for "+(чПредложение-чСпрос)+" units of cargo. Create a fictitious user.");
Возврат Ложь;
Возврат Ложь;
ИначеЕсли чПредложение<чСпрос Тогда
ИначеЕсли чПредложение<чСпрос Тогда
Сообщить("Предложение меньше спроса на "+(чСпрос-чПредложение)+" единиц груза. Создайте фиктивного поставщика.");
Сообщить("Offering less than the demand for "+(чСпрос-чПредложение)+" units of cargo. Create a fictitious vendor.");
Возврат Ложь;
Возврат Ложь;
КонецЕсли;
КонецЕсли;
РаспределениеМетодомСевероЗападногоУгла();
РаспределениеМетодомСевероЗападногоУгла();
чСумма=СтоимостьПеревозки();
чСумма=СтоимостьПеревозки();
Сообщить("Стоимость перевозки методом северо-западного угла: "+чСумма);
Сообщить("The cost of transportation by the north-west corner: "+чСумма);
Пока 1=1 Цикл
Пока 1=1 Цикл
ПроверкаПравильностиОтгрузок();
ПроверкаПравильностиОтгрузок();
Line 875: Line 875:
счБазисных=счБазисных+1;
счБазисных=счБазисных+1;
ИначеЕсли Отгрузки[i][j]<0 Тогда
ИначеЕсли Отгрузки[i][j]<0 Тогда
ВызватьИсключение("Отгрузки не должны быть отрицательными");
ВызватьИсключение("Shipments should not be negative");
Иначе
Иначе
БазисныеЯчейки[i][j]=0;
БазисныеЯчейки[i][j]=0;
Line 890: Line 890:
КонецЕсли;
КонецЕсли;
Если ПроверкаОптимальности()=Истина Тогда
Если ПроверкаОптимальности()=Истина Тогда
Сообщить("РЕШЕНИЕ ОПТИМАЛЬНО");
Сообщить("Solution is optimal.");
Прервать;
Прервать;
КонецЕсли;
КонецЕсли;
Сообщить("Решение не оптимальное");
Сообщить("Solution is not optimal.");
Если НайтиЦикл(i1, j1)= Ложь Тогда
Если НайтиЦикл(i1, j1)= Ложь Тогда
ВызватьИсключение("Не удалось найти цикл");
ВызватьИсключение("Unable to find a cycle");
КонецЕсли;
КонецЕсли;
ПерераспределениеПоЦиклу();
ПерераспределениеПоЦиклу();
чСумма=СтоимостьПеревозки();
чСумма=СтоимостьПеревозки();
Сообщить("***");
Сообщить("***");
Сообщить("Стоимость перевозки: "+чСумма);
Сообщить("The cost of transport: "+чСумма);
КонецЦикла;
КонецЦикла;
Возврат Истина;
Возврат Истина;

Revision as of 20:35, 18 January 2014

Transportation problem is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Transportation problem is to find the optimal transportation plan certain volumes of resources from suppliers to consumers, taking into account the cost of transportation. The plan is a table (matrix), whose rows and columns correspond to the suppliers and consumers, the cells are placed in cargo volume.

Example of the transportation problem:

Consumer 1,
need 20 kg 		Consumer 2,
need 30 kg 		Consumer 3,
need 10 kg
Supplier 1,
supply 25 kg 		$3 per kg $5 per kg $7 per kg
Supplier 2,
supply 35 kg 		$3 per kg $2 per kg $5 per kg


For the first time this problem mathematically studied the Soviet mathematician A. N. Tolstoy. In 1930 he published his work on finding the minimum total mileage in rail transportation, which used the redistributive cycles. The main contribution to the development of the mathematical apparatus of the transport problem introduced Soviet economist L. V. Kantorovich during the Great Patriotic War (published in 1939 and 1942). The way to solve the transportation problem by the potential method was it published in conjunction with M. K. Gavurin in 1949.

The program is to solve the classical transport problem using the method of potentials (with redistributive cycle) with the preparation of the initial transportation plan by the north-west corner of the features to be implemented in this task. The input is the number of suppliers and customers, inventory levels, needs and cost matrix transport cargo. The output of the program is the optimal plan. If necessary, enter a fictitious vendor or customer.

The solution for the above example would be the plan:

Consumer 1 Consumer 2 Consumer 3
Supplier 1 20 kg - 5 kg
Supplier 2 - 30 kg 5 kg

Glagol

<lang>ОТДЕЛ Транспорт+; ИСПОЛЬЗУЕТ 

 Вывод ИЗ "...\Отделы\Обмен\",
 Приём;

ПЕР 

 Поставщиков, Потребителей: ЦЕЛ;
 Запасы, Потребности: ДОСТУП К РЯД ИЗ ЦЕЛ;
 Расходы, План: ДОСТУП К РЯД ИЗ РЯД ИЗ ЦЕЛ;
 U, V: ДОСТУП К РЯД ИЗ ЦЕЛ;
 оцСв: ДОСТУП К РЯД ИЗ НАБОР значение: ЦЕЛ; поставщик, потребитель: ЦЕЛ КОН;
 начQ_поставщик, начQ_потребитель: ЦЕЛ;
 Q: ДОСТУП К РЯД ИЗ РЯД ИЗ УЗКЦЕЛ;
 Поправка, Разница: ЦЕЛ;

ЗАДАЧА ПринятьДанные; ПЕР 

 сч1, сч2: ЦЕЛ;
 сумма1, сумма2, разница: ЦЕЛ;
 памЗап, памПотр: ДОСТУП К РЯД ИЗ ЦЕЛ;

УКАЗ 

 Вывод.Цепь("Number of suppliers: ");
 Поставщиков := Приём.Число();
 Вывод.Цепь(".^Number of consumers: ");
 Потребителей := Приём.Число();
 СОЗДАТЬ(памЗап, Поставщиков);
 СОЗДАТЬ(памПотр, Потребителей);
 Вывод.Цепь(".^Inventories^^");
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   памЗап[сч1] := Приём.Число();
   Вывод.Цепь(" ")
 КОН;
 Вывод.Цепь("^Requirements:^");
 ОТ сч1 := 0 ДО Потребителей-1 ВЫП
   памПотр[сч1] := Приём.Число();
   Вывод.Цепь(" ")
 КОН;
 сумма1 := 0;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП УВЕЛИЧИТЬ(сумма1, памЗап[сч1]) КОН;
 сумма2 := 0;
 ОТ сч1 := 0 ДО Потребителей-1 ВЫП УВЕЛИЧИТЬ(сумма2, памПотр[сч1]) КОН;
 ЕСЛИ сумма1 > сумма2 ТО
   разница := сумма1 - сумма2;
   Вывод.ЧЦел("^Introduced a fictitious consumer.", сумма1, сумма2, разница, 0);
   УВЕЛИЧИТЬ(Потребителей);
   СОЗДАТЬ(Потребности, Потребителей);
   ОТ сч1 := 0 ДО Потребителей-2 ВЫП Потребности[сч1] := памПотр[сч1] КОН;
   Потребности[Потребителей-1] := разница;
   СОЗДАТЬ(Запасы, Поставщиков);
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП Запасы[сч1] := памЗап[сч1] КОН
 АЕСЛИ сумма2 > сумма1 ТО
   разница := сумма2 - сумма1;
   Вывод.ЧЦел("^Introduced a fictitious supplier.", сумма2, сумма1, разница, 0);
   УВЕЛИЧИТЬ(Поставщиков);
   СОЗДАТЬ(Запасы, Поставщиков);
   ОТ сч1 := 0 ДО Поставщиков-2 ВЫП Запасы[сч1] := памЗап[сч1] КОН;
   Запасы[Поставщиков-1] := разница;
   СОЗДАТЬ(Потребности, Потребителей);
   ОТ сч1 := 0 ДО Потребителей-1 ВЫП Потребности[сч1] := памПотр[сч1] КОН
 ИНАЧЕ
   СОЗДАТЬ(Запасы, Поставщиков);
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП Запасы[сч1] := памЗап[сч1] КОН;
   СОЗДАТЬ(Потребности, Потребителей);
   ОТ сч1 := 0 ДО Потребителей-1 ВЫП Потребности[сч1] := памПотр[сч1] КОН
 КОН;
 СОЗДАТЬ(Расходы, Поставщиков, Потребителей);
 Вывод.Цепь("^The matrix of costs:^");
 ЕСЛИ сумма1 > сумма2 ТО
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-2 ВЫП
       Расходы[сч1, сч2] := Приём.Число();
       Вывод.Цепь(" ")
     КОН;
     Расходы[сч1, Потребителей-1] := 0;
     Вывод.Цепь("^")
   КОН
 АЕСЛИ сумма2 > сумма1 ТО
   ОТ сч1 := 0 ДО Поставщиков-2 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       Расходы[сч1, сч2] := Приём.Число();
       Вывод.Цепь(" ")
     КОН;
     Вывод.Цепь("^")
   КОН;
   ОТ сч1 := 0 ДО Потребителей-1 ВЫП Расходы[Поставщиков-1, сч1] := 0 КОН
 ИНАЧЕ
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       Расходы[сч1, сч2] := Приём.Число();
       Вывод.Цепь(" ")
     КОН;
     Вывод.Цепь("^")
   КОН
 КОН;
 СОЗДАТЬ(План, Поставщиков, Потребителей);
 СОЗДАТЬ(U, Поставщиков);
 СОЗДАТЬ(V, Потребителей);
 СОЗДАТЬ(оцСв, Потребителей*Поставщиков-(Потребителей+Поставщиков-1));
 СОЗДАТЬ(Q, Поставщиков, Потребителей)

КОН ПринятьДанные;

ЗАДАЧА ВывестиПлан; ПЕР 

 сч1, сч2: ЦЕЛ;

УКАЗ 

 ОТ сч1 := 1 ДО Потребителей ВЫП Вывод.Цепь("-----") КОН;
 Вывод.Цепь("^");
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ План[сч1, сч2] = -1 ТО Вывод.Цепь("  -  ") ИНАЧЕ
       Вывод.ЧЦел("%4d ", План[сч1, сч2], 0, 0, 0);
     КОН
   КОН;
   Вывод.Цепь("^")
 КОН;
 ОТ сч1 := 1 ДО Потребителей ВЫП Вывод.Цепь("-----") КОН

КОН ВывестиПлан;

ЗАДАЧА ПосчитатьПоправку; ПЕР 

 сч1, сч2: ЦЕЛ;

УКАЗ 

 Поправка := -1;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ План[сч1, сч2] # -1 ТО
       ЕСЛИ Q[сч1, сч2] = -1 ТО
         ЕСЛИ Поправка = -1 ТО Поправка := План[сч1, сч2]
         АЕСЛИ Поправка > План[сч1, сч2] ТО Поправка := План[сч1, сч2] КОН
       КОН
     КОН
   КОН
 КОН;
 Разница := Разница * Поправка

КОН ПосчитатьПоправку;

ЗАДАЧА РасставитьНули(недостаток: ЦЕЛ); ПЕР 

 Связь: ДОСТУП К РЯД ИЗ РЯД ИЗ УЗКЦЕЛ;
 сч1, сч2: ЦЕЛ;
 естьБезСвязи: КЛЮЧ;

 ЗАДАЧА ЕстьНапротив(строка, столбец: ЦЕЛ): КЛЮЧ;
 ПЕР сч: ЦЕЛ;
 УКАЗ
   ОТ сч := 0 ДО Поставщиков-1 ВЫП
     ЕСЛИ (сч # строка) И (Связь[сч, столбец] = 1) ТО ВОЗВРАТ ВКЛ КОН
   КОН;
   ОТ сч := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ (сч # столбец) И (Связь[строка, сч] = 1) ТО ВОЗВРАТ ВКЛ КОН
   КОН;
   ВОЗВРАТ ОТКЛ
 КОН ЕстьНапротив;

 ЗАДАЧА СтолбецБезСвязи(номер: ЦЕЛ): КЛЮЧ;
 ПЕР сч: ЦЕЛ;
 УКАЗ
   ОТ сч := 0 ДО Поставщиков-1 ВЫП
     ЕСЛИ Связь[сч, номер] = 1 ТО ВОЗВРАТ ОТКЛ КОН
   КОН;
   ВОЗВРАТ ВКЛ
 КОН СтолбецБезСвязи;

УКАЗ 

 СОЗДАТЬ(Связь, Поставщиков, Потребителей);
 естьБезСвязи := ОТКЛ;
 ОТ сч1 := 0 ДО Потребителей-1 ВЫП
   ЕСЛИ План[0, сч1] = -1 ТО Связь[0, сч1] := -1 ИНАЧЕ Связь[0, сч1] := 1 КОН
 КОН;
 ОТ сч1 := 1 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ План[сч1, сч2] = -1 ТО Связь[сч1, сч2] := -1 ИНАЧЕ Связь[сч1, сч2] := 0 КОН
   КОН
 КОН;
 ОТ сч1 := 1 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ Связь[сч1, сч2] = 0 ТО
       ЕСЛИ ЕстьНапротив(сч1, сч2) ТО Связь[сч1, сч2] := 1
       АЕСЛИ НЕ естьБезСвязи ТО естьБезСвязи := ВКЛ КОН
     КОН
   КОН
 КОН;
 ЕСЛИ естьБезСвязи ТО
   ОТ сч1 := Поставщиков-1 ДО 1 ПО -1 ВЫП
     ОТ сч2 := Потребителей-1 ДО 0 ПО -1 ВЫП
       ЕСЛИ Связь[сч1, сч2] = 0 ТО
         ЕСЛИ ЕстьНапротив(сч1, сч2) ТО Связь[сч1, сч2] := 1
         АЕСЛИ НЕ естьБезСвязи ТО естьБезСвязи := ВКЛ КОН
       КОН
     КОН
   КОН
 КОН;
 ЕСЛИ естьБезСвязи ТО
   ОТ сч1 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ СтолбецБезСвязи(сч1) ТО План[0, сч1] := 0; УМЕНЬШИТЬ(недостаток) КОН;
     ЕСЛИ недостаток = 0 ТО сч1 := Потребителей КОН
   КОН
 КОН;
 КОЛЬЦО
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ недостаток = 0 ТО ВЫХОД ИНАЧЕ
         ЕСЛИ План[сч1, сч2] = -1 ТО
           План[сч1, сч2] := 0; УМЕНЬШИТЬ(недостаток);
         КОН
       КОН
     КОН
   КОН;
   ВЫХОД
 КОН

КОН РасставитьНули;

ЗАДАЧА ЗаполнитьОтУгла; ПЕР 

 ОсталосьВНаличии, ОсталосьПотребным: ДОСТУП К РЯД ИЗ ЦЕЛ;
 занято, недостаток: ЦЕЛ;
 сч1, сч2: ЦЕЛ;

УКАЗ 

 СОЗДАТЬ(ОсталосьВНаличии, Поставщиков);
 СОЗДАТЬ(ОсталосьПотребным, Потребителей);
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП ОсталосьВНаличии[сч1] := Запасы[сч1] КОН;
 ОТ сч1 := 0 ДО Потребителей-1 ВЫП ОсталосьПотребным[сч1] := Потребности[сч1] КОН;
 занято := 0;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ ОсталосьВНаличии[сч1] = 0 ТО План[сч1, сч2] := -1 ИНАЧЕ
       ЕСЛИ ОсталосьВНаличии[сч1] > ОсталосьПотребным[сч2] ТО
         ЕСЛИ ОсталосьПотребным[сч2] # 0 ТО План[сч1, сч2] := ОсталосьПотребным[сч2]; УВЕЛИЧИТЬ(занято)
         ИНАЧЕ План[сч1, сч2] := -1 КОН;
         УМЕНЬШИТЬ(ОсталосьВНаличии[сч1], ОсталосьПотребным[сч2]);
         ОсталосьПотребным[сч2] := 0
       ИНАЧЕ
         ЕСЛИ ОсталосьВНаличии[сч1] # 0 ТО План[сч1, сч2] := ОсталосьВНаличии[сч1]; УВЕЛИЧИТЬ(занято)
         ИНАЧЕ План[сч1, сч2] := -1 КОН;
         УМЕНЬШИТЬ(ОсталосьПотребным[сч2], ОсталосьВНаличии[сч1]);
         ОсталосьВНаличии[сч1] := 0
       КОН
     КОН
   КОН
 КОН;
 недостаток := (Поставщиков+Потребителей-1) - занято;
 ЕСЛИ недостаток > 0 ТО РасставитьНули(недостаток) КОН

КОН ЗаполнитьОтУгла;

ЗАДАЧА ОценитьБазисныеКлетки; ПЕР 

 сч1, сч2, сч3: ЦЕЛ;
 суммы: ДОСТУП К РЯД ИЗ РЯД 3 ИЗ ЦЕЛ;
 известно: ДОСТУП К РЯД ИЗ РЯД 2 ИЗ КЛЮЧ;

УКАЗ 

 СОЗДАТЬ(суммы, Поставщиков+Потребителей-1);
 СОЗДАТЬ(известно, Поставщиков+Потребителей-1);
 известно[0][0] := ВКЛ; известно[0][1] := ОТКЛ;
 ОТ сч1 := 1 ДО (Поставщиков+Потребителей-1)-1 ВЫП известно[сч1][0] := ОТКЛ; известно[сч1][1] := ОТКЛ КОН;
 сч3 := 0;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ План[сч1, сч2] # -1 ТО
       суммы[сч3][0] := сч1; суммы[сч3][1] := сч2; суммы[сч3][2] := Расходы[сч1, сч2];
       УВЕЛИЧИТЬ(сч3)
     КОН
   КОН
 КОН;
 U[0] := 0;
 ОТ сч1 := 1 ДО (Поставщиков+Потребителей-1)-1 ВЫП
   ЕСЛИ суммы[сч1][0] = 0 ТО известно[сч1][0] := ВКЛ КОН
 КОН;
 сч3 := 0;
 ПОВТОРЯТЬ
   сч1 := 0;
   ПОКА НЕ (известно[сч1][0] # известно[сч1][1]) ВЫП
     УВЕЛИЧИТЬ(сч1)
   КОН;
   ЕСЛИ известно[сч1][0] ТО
     V[суммы[сч1][1]] := суммы[сч1][2] - U[суммы[сч1][0]];
     известно[сч1][1] := ВКЛ;
     ОТ сч2 := 0 ДО (Поставщиков+Потребителей-1)-1 ВЫП
       ЕСЛИ (суммы[сч2][1] = суммы[сч1][1]) И (НЕ известно[сч2][1]) ТО известно[сч2][1] := ВКЛ КОН
     КОН
   ИНАЧЕ
     U[суммы[сч1][0]] := суммы[сч1][2] - V[суммы[сч1][1]];
     известно[сч1][0] := ВКЛ;
     ОТ сч2 := 0 ДО (Поставщиков+Потребителей-1)-1 ВЫП
       ЕСЛИ (суммы[сч2][0] = суммы[сч1][0]) И (НЕ известно[сч2][0]) ТО известно[сч2][0] := ВКЛ КОН
     КОН
   КОН;
   УВЕЛИЧИТЬ(сч3)
 ДО сч3 = Поставщиков+Потребителей-1

КОН ОценитьБазисныеКлетки;

ЗАДАЧА ОценитьСвободныеКлетки(): КЛЮЧ; ПЕР 

 сч1, сч2, сч3: ЦЕЛ;
 естьПолож: КЛЮЧ;

УКАЗ 

 естьПолож := ОТКЛ;
 сч3 := 0;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ План[сч1, сч2] = -1 ТО
       оцСв[сч3].значение := U[сч1]+V[сч2]-Расходы[сч1,сч2];
       оцСв[сч3].поставщик := сч1; оцСв[сч3].потребитель := сч2;
       ЕСЛИ оцСв[сч3].значение > 0 ТО естьПолож := ВКЛ КОН;
       УВЕЛИЧИТЬ(сч3)
     КОН
   КОН
 КОН;
 ЕСЛИ естьПолож ТО ВОЗВРАТ ОТКЛ ИНАЧЕ ВОЗВРАТ ВКЛ КОН

КОН ОценитьСвободныеКлетки;

ЗАДАЧА Цикл; ПЕР 

 сч1, сч2, сч3: ЦЕЛ;
 максЗн: ЦЕЛ;
 начало, циклНайден: КЛЮЧ;

 ЗАДАЧА НаЛинии(наКакой: ЦЕЛ; столб: КЛЮЧ): ЦЕЛ;
 ПЕР сч, сколько: ЦЕЛ;
 УКАЗ
   сколько := 0;
   ЕСЛИ столб ТО
     ОТ сч := 0 ДО Поставщиков-1 ВЫП
       ЕСЛИ (План[сч, наКакой] # -1) ИЛИ ((сч = начQ_поставщик) И (наКакой = начQ_потребитель)) ТО
         УВЕЛИЧИТЬ(сколько)
       КОН
     КОН
   ИНАЧЕ
     ОТ сч := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ (План[наКакой, сч] # -1) ИЛИ ((наКакой = начQ_поставщик) И (сч = начQ_потребитель)) ТО
         УВЕЛИЧИТЬ(сколько)
       КОН
     КОН
   КОН;
   ВОЗВРАТ сколько
 КОН НаЛинии;

 ЗАДАЧА^ ИскатьВСтолбце(номер, строка: ЦЕЛ): КЛЮЧ;

 ЗАДАЧА ИскатьВСтроке(номер, столбец: ЦЕЛ): КЛЮЧ;
 ПЕР
   сч: ЦЕЛ;
 УКАЗ
   ЕСЛИ (НЕ начало) И (номер = начQ_поставщик) И (столбец = начQ_потребитель) ТО циклНайден := ВКЛ КОН;
   ЕСЛИ начало ТО начало := ОТКЛ КОН;
   ЕСЛИ циклНайден ТО ВОЗВРАТ ВКЛ КОН;
   ОТ сч := 0 ДО Потребителей-1 ВЫП
     ЕСЛИ
       (сч # столбец) И
       ((План[номер, сч] # -1) ИЛИ ((номер = начQ_поставщик) И (сч = начQ_потребитель))) И
       (НаЛинии(сч, ВКЛ) > 1) И
       (Q[номер, сч] = 0)
     ТО
       Q[номер, сч] := -1;
       ЕСЛИ НЕ ИскатьВСтолбце(сч, номер) ТО Q[номер, сч] := 0 ИНАЧЕ ВОЗВРАТ ВКЛ КОН
     КОН
   КОН;
   ВОЗВРАТ ОТКЛ
 КОН ИскатьВСтроке;

 ЗАДАЧА ИскатьВСтолбце(номер, строка: ЦЕЛ): КЛЮЧ;
 ПЕР
   сч: ЦЕЛ;
 УКАЗ
   ЕСЛИ (НЕ начало) И (строка = начQ_поставщик) И (номер = начQ_потребитель) ТО циклНайден := ВКЛ КОН;
   ЕСЛИ начало ТО начало := ОТКЛ КОН;
   ЕСЛИ циклНайден ТО ВОЗВРАТ ВКЛ КОН;
   ОТ сч := 0 ДО Поставщиков-1 ВЫП
     ЕСЛИ
       (сч # строка) И
       ((План[сч, номер] # -1) ИЛИ ((сч = начQ_поставщик) И (номер = начQ_потребитель))) И
       (НаЛинии(сч, ОТКЛ) > 1) И
       (Q[сч, номер] = 0)
     ТО
       Q[сч, номер] := 1;
       ЕСЛИ НЕ ИскатьВСтроке(сч, номер) ТО Q[сч, номер] := 0 ИНАЧЕ ВОЗВРАТ ВКЛ КОН
     КОН
   КОН;
   ВОЗВРАТ ОТКЛ
 КОН ИскатьВСтолбце;

УКАЗ 

 максЗн := 0;
 ОТ сч1 := 0 ДО Потребителей*Поставщиков-(Потребителей+Поставщиков-1)-1 ВЫП
   ЕСЛИ оцСв[сч1].значение > максЗн ТО максЗн := оцСв[сч1].значение КОН
 КОН;
 сч3 := 0;
 ПОКА оцСв[сч3].значение # максЗн ВЫП УВЕЛИЧИТЬ(сч3) КОН;
 ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
   ОТ сч2 := 0 ДО Потребителей-1 ВЫП
     Q[сч1, сч2] := 0
   КОН
 КОН;
 Разница := оцСв[сч3].значение;
 начQ_поставщик := оцСв[сч3].поставщик; начQ_потребитель := оцСв[сч3].потребитель;
 начало := ВКЛ; циклНайден := ОТКЛ;
 ЕСЛИ ИскатьВСтроке(начQ_поставщик, начQ_потребитель) ТО КОН

КОН Цикл;

ЗАДАЧА ИзменитьПлан; ПЕР 

 сч1, сч2: ЦЕЛ;
 занято, недостаток: ЦЕЛ;

УКАЗ 

 ЕСЛИ Поправка = 0 ТО
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ План[сч1, сч2] = 0 ТО План[сч1, сч2] := -1; сч2 := Потребителей; сч1 := Поставщиков КОН
     КОН
   КОН;
   План[начQ_поставщик, начQ_потребитель] := 0
 ИНАЧЕ
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ Q[сч1, сч2] = 1 ТО
         ЕСЛИ План[сч1, сч2] = -1 ТО План[сч1, сч2] := 0 КОН;
         УВЕЛИЧИТЬ(План[сч1, сч2], Поправка);
       АЕСЛИ Q[сч1, сч2] = -1 ТО УМЕНЬШИТЬ(План[сч1, сч2], Поправка)
       КОН
     КОН
   КОН;
   занято := 0;
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ План[сч1, сч2] > 0 ТО УВЕЛИЧИТЬ(занято) КОН
     КОН
   КОН;
   ОТ сч1 := 0 ДО Поставщиков-1 ВЫП
     ОТ сч2 := 0 ДО Потребителей-1 ВЫП
       ЕСЛИ План[сч1, сч2] = 0 ТО План[сч1, сч2] := -1 КОН
     КОН
   КОН;
   недостаток := (Поставщиков+Потребителей-1) - занято;
   ЕСЛИ недостаток > 0 ТО РасставитьНули(недостаток) КОН
 КОН

КОН ИзменитьПлан;

УКАЗ 

 ПринятьДанные;
 ЗаполнитьОтУгла;
 Разница := -1;
 КОЛЬЦО
   ОценитьБазисныеКлетки;
   ЕСЛИ ОценитьСвободныеКлетки() ТО ВЫХОД КОН;
   Цикл;
   ПосчитатьПоправку;
   ИзменитьПлан
 КОН;
 ВывестиПлан

КОН Транспорт.</lang>

Input

Number of suppliers: 3.
Number of consumers: 3.
Inventories:
12 40 33
Requirements:
20 30 10
Introduced a fictitious consumer.
The matrix of costs:
3 5 7
2 4 6
9 1 8

Output

--------------------
  -    -    -    12
  20   -    10   10
  -    30   -     3
--------------------

1C

<lang>перем m,n; // Table size перем u,v; перем БазисныеЯчейки; перем iЦикл, jЦикл; перем Цены, Спрос, Предложение, Отгрузки; // Arrays of the transportation problem перем i1, j1; перем СпросОстаток, ПредложениеОстаток; перем гл_сч; перем гсч;

Функция РаспределениеМетодомСевероЗападногоУгла() 

   Для j=1 по n Цикл
       СпросОстаток[j]=Спрос[j];
   КонецЦикла;
   Для i=1 по m Цикл
       ПредложениеОстаток[i]=Предложение[i];
   КонецЦикла;
   Для i=1 по m Цикл
       Для j=1 по n Цикл
           БазисныеЯчейки[i][j]=0;
           Отгрузки[i][j]=0;
       КонецЦикла;    
   КонецЦикла;
   Для i=1 по m Цикл
       Для j=1 по n Цикл
           Если ПредложениеОстаток[i]=0 Тогда
               Прервать;
           ИначеЕсли ПредложениеОстаток[i]<0 Тогда
               ВызватьИсключение("Error: balance of the offer less than 0");
           КонецЕсли;
           чОбъем=СпросОстаток[j];
           Если чОбъем=0 Тогда
               Продолжить;
           ИначеЕсли чОбъем<0 Тогда    
               ВызватьИсключение("Error: balance of the demand less than 0");
           КонецЕсли;
           Если ПредложениеОстаток[i]<чОбъем Тогда
               чОбъем=ПредложениеОстаток[i];
           КонецЕсли; 
           СпросОстаток[j]=СпросОстаток[j]-чОбъем;
           ПредложениеОстаток[i]=ПредложениеОстаток[i]-чОбъем;
           БазисныеЯчейки[i][j]=1;
           Отгрузки[i][j]=чОбъем;
       КонецЦикла;    
   КонецЦикла;

КонецФункции

Функция ПроверкаПравильностиОтгрузок() 

   Для i=1 по m Цикл
       стр="Отгрузки: ";
       Для j=1 по n Цикл
           стр=стр+Отгрузки[i][j]+" ";
       КонецЦикла;    
       Сообщить(стр);
   КонецЦикла;        
   Для i=1 по m Цикл
       чОбъем=0;
       Для j=1 по n Цикл
           чОбъем=чОбъем+Отгрузки[i][j];
       КонецЦикла;    
       Если чОбъем<>Предложение[i] Тогда
           ВызватьИсключение("Error: shipment on the line does not equal the proposal in the row "+i);
       КонецЕсли;
   КонецЦикла;    
   Для j=1 по n Цикл
       чОбъем=0;
       Для i=1 по m Цикл
           чОбъем=чОбъем+Отгрузки[i][j];
       КонецЦикла;    
       Если чОбъем<>Спрос[j] Тогда
           ВызватьИсключение("Error: shipment by the column does not equal to the demand in the column "+j);
       КонецЕсли;
   КонецЦикла;    
   Возврат Истина;

КонецФункции

Функция ВычислениеПотенциалов() 

   перем i, j;
   Для i=1 по m Цикл
       u[i]=НеОпределено;
   КонецЦикла;
   
   Для j=1 по n Цикл
       v[j]=НеОпределено;
   КонецЦикла;
   u[1]=0;
   гл_сч=m*n;
   ВычислениеПотенциаловПоГоризонтали(1);
   Для i=1 по m Цикл
       Если u[i]=НеОпределено Тогда
           Сообщить("Failed to evaluate the potential u["+i+"]");
           Возврат Ложь;
       КонецЕсли;    
   КонецЦикла;
   Для j=1 по n Цикл
       Если v[j]=НеОпределено Тогда
           Сообщить("Failed to evaluate the potential v["+j+"]");
           Возврат Ложь;
       КонецЕсли;    
   КонецЦикла;
   Возврат Истина;

КонецФункции

Функция ВычислениеПотенциаловПоВертикали(j) 

   Если v[j]=НеОпределено Тогда 
       ВызватьИсключение("Failed to get the potential v["+j+"]");
   КонецЕсли;    
   Для i=1 по m Цикл
       Если БазисныеЯчейки[i][j]=0 Тогда
           Продолжить;
       КонецЕсли;
       Если u[i]<>НеОпределено Тогда
           Продолжить;
       Иначе
           u[i]=Цены[i][j]-v[j];
           ВычислениеПотенциаловПоГоризонтали(i);
       КонецЕсли;    
   КонецЦикла;

КонецФункции

Функция ВычислениеПотенциаловПоГоризонтали(i) 

   гл_сч=гл_сч-1;
   Если гл_сч=0 Тогда
       ВызватьИсключение("Looping in the calculation of potential");
   КонецЕсли;    
   Если u[i]=НеОпределено Тогда 
       ВызватьИсключение("Failed to get potential u["+i+"]");
   КонецЕсли;    
   Для j=1 по n Цикл
       Если БазисныеЯчейки[i][j]=0 Тогда
           Продолжить;
       КонецЕсли;
       Если v[j]<>НеОпределено Тогда
           Продолжить;
       Иначе
           v[j]=Цены[i][j]-u[i];
           ВычислениеПотенциаловПоВертикали(j);
       КонецЕсли;    
   КонецЦикла;

КонецФункции

Функция ПроверкаОптимальности() 

   перем чРешениеОптимально, чМинимальнаяДельта, i, j, Дельта;
   чРешениеОптимально=Истина;
   чМинимальнаяДельта=НеОпределено;
   Для i=1 по m Цикл
       стр="Дельта=";
       Для j=1 по n Цикл
           Если БазисныеЯчейки[i][j]=1 Тогда
               Дельта=0;
           Иначе
               Дельта = Цены[i][j]-u[i]-v[j];
           КонецЕсли;
           стр=стр+Дельта+" ";
           Если Дельта<0 Тогда
               чРешениеОптимально=Ложь;
           КонецЕсли;
           Если чМинимальнаяДельта=НеОпределено Тогда
               чМинимальнаяДельта=Дельта;
               i1=i;
               j1=j;
           Иначе
               Если Дельта<чМинимальнаяДельта Тогда
                   чМинимальнаяДельта=Дельта;
                   i1=i;
                   j1=j;
               КонецЕсли;        
           КонецЕсли;    
       КонецЦикла;    
   КонецЦикла;
   Возврат чРешениеОптимально;

КонецФункции

Функция СтоимостьПеревозки() 

   чСумма=0;
   Для i=1 по m Цикл
       Для j=1 по n Цикл
           чСумма=чСумма+(Отгрузки[i][j]*Цены[i][j]);
       КонецЦикла;    
   КонецЦикла;
   Возврат чСумма;

КонецФункции

Функция ПоискНулевойЯчейкиДляВводаВБазис() 

   ок=0;
   Для i=1 по m Цикл
       Для j=1 по n Цикл
           Если БазисныеЯчейки[i][j]=0 Тогда
               ок=1;
               Прервать;
           КонецЕсли;
       КонецЦикла;
       Если ок=1 Тогда
           Прервать;
       КонецЕсли;
   КонецЦикла;    
   Если ок=0 Тогда
       ВызватьИсключение("There is no nonbasic (zero) cell entry into the basis");
   КонецЕсли;
   Пока 1=1 Цикл
       i=ГСЧ.СлучайноеЧисло(1, m);
       j=ГСЧ.СлучайноеЧисло(1, n);
       Если БазисныеЯчейки[i][j]=1 Тогда
           Продолжить;
       КонецЕсли;
       Если Отгрузки[i][j]<>0 Тогда
           ВызватьИсключение("Nonzero shipment for nonbasic cell");
       КонецЕсли;
       БазисныеЯчейки[i][j]=1;
       Сообщить("В базис введена ячейка "+i+" "+j);
       Возврат Истина;
   КонецЦикла;

КонецФункции

Функция НайтиЦикл(i0, j0) 

   гл_сч = m*n;
   iЦикл.Очистить();
   jЦикл.Очистить();
   Если НайтиЦикл_ПоГоризонтали(i0, j0) Тогда
       Возврат Истина;
   КонецЕсли;
   Возврат Ложь;

КонецФункции

Функция НайтиЦикл_ПоГоризонтали(i0, j0) 

   гл_сч=гл_сч-1;
   Если гл_сч=0 Тогда
       ВызватьИсключение("Too many iterations in the cycle search");
   КонецЕсли;    
   Для j=1 по n Цикл
       Если j=j0 Тогда
           Продолжить;
       КонецЕсли;
       Если БазисныеЯчейки[i0][j]=0 Тогда
           Продолжить;
       КонецЕсли;
       Если НайтиЦикл_ПоВертикали(i0, j) Тогда
           iЦикл.Добавить(i0);
           jЦикл.Добавить(j);
           Возврат Истина;
       КонецЕсли;    
   КонецЦикла;
   Возврат Ложь;

КонецФункции

Функция НайтиЦикл_ПоВертикали(i0, j0) 

   Для i=1 по m Цикл
       Если (j0=j1) и (i=i1) Тогда
               iЦикл.Добавить(i);
               jЦикл.Добавить(j0);
               Возврат Истина;
       КонецЕсли;    
       Если i=i0 Тогда
           Продолжить;
       КонецЕсли;
       Если БазисныеЯчейки[i][j0]=0 Тогда
           Продолжить;
       КонецЕсли;
       Если НайтиЦикл_ПоГоризонтали(i, j0) Тогда
           iЦикл.Добавить(i);
           jЦикл.Добавить(j0);
           Возврат Истина;
       КонецЕсли;    
   КонецЦикла;    
   Возврат Ложь;

КонецФункции

Функция ПерераспределениеПоЦиклу() 

   Сообщить("Перераспределение по циклу "+iЦикл.Количество());
   Если jЦикл.Количество()<>iЦикл.Количество() Тогда
       ВызватьИсключение("Unequal dimension coordinates cycle");
   КонецЕсли;
   Если iЦикл.Количество()<4 Тогда
       ВызватьИсключение("Cycle is less than 4 items");
   КонецЕсли;    
   Тета=НеОпределено;
   Знак="+";
   Для й=0 по iЦикл.ВГраница() Цикл
       i=iЦикл[й];
       j=jЦикл[й];
       Если Знак="-" Тогда
           Объем=Отгрузки[i][j];
           Если Тета=НеОпределено Тогда
               Тета=Объем;
           Иначе
               Если Объем<Тета Тогда
                   Тета=Объем;
               КонецЕсли;    
           КонецЕсли;    
           Знак="+";
       Иначе
           Знак="-";
       КонецЕсли;    
   КонецЦикла;    
   Если Тета=НеОпределено Тогда
       ВызватьИсключение("Failed to evaluate variable theta.");
   КонецЕсли;
   Сообщить("Тета="+Тета);
   Если Тета=0 Тогда
       Возврат Ложь;
   КонецЕсли;
   Знак="+";
   Для й=0 по iЦикл.ВГраница() Цикл
       i=iЦикл[й];
       j=jЦикл[й];
       Если Знак="-" Тогда
           Отгрузки[i][j]=Отгрузки[i][j]-Тета;
           Знак="+";
       Иначе
           Отгрузки[i][j]=Отгрузки[i][j]+Тета;
           Знак="-";
       КонецЕсли;    
   КонецЦикла;
   Возврат Истина;

КонецФункции

Функция РешениеТранспортнойЗадачи() 

   ГСЧ = Новый ГенераторСлучайныхЧисел();
   БазисныеЯчейки = Новый Массив(m+1,n+1);
   Отгрузки = Новый Массив(m+1,n+1);
   СпросОстаток=Новый Массив(n+1);
   ПредложениеОстаток=Новый Массив(m+1);
   u=Новый Массив(m+1);
   v=Новый Массив(n+1);
   iЦикл = Новый Массив;
   jЦикл = Новый Массив;
   чСпрос=0;
   Для j=1 по n Цикл
       чСпрос=чСпрос+Спрос[j];
   КонецЦикла;    
   чПредложение=0;
   Для i=1 по m Цикл
       чПредложение=чПредложение+Предложение[i];
   КонецЦикла;
   Если чПредложение>чСпрос Тогда
       Сообщить("Offering more than the demand for "+(чПредложение-чСпрос)+" units of cargo. Create a fictitious user.");
       Возврат Ложь;
   ИначеЕсли чПредложение<чСпрос Тогда
       Сообщить("Offering less than the demand for "+(чСпрос-чПредложение)+" units of cargo. Create a fictitious vendor.");
       Возврат Ложь;
   КонецЕсли;        
   РаспределениеМетодомСевероЗападногоУгла();
   чСумма=СтоимостьПеревозки();
   Сообщить("The cost of transportation by the north-west corner: "+чСумма);
   Пока 1=1 Цикл
       ПроверкаПравильностиОтгрузок();
       счБазисных=0;
       Для i=1 по m Цикл
           Для j=1 по n Цикл
               Если Отгрузки[i][j]>0 Тогда
                   БазисныеЯчейки[i][j]=1;
                   счБазисных=счБазисных+1;
               ИначеЕсли Отгрузки[i][j]<0 Тогда    
                   ВызватьИсключение("Shipments should not be negative");
               Иначе
                   БазисныеЯчейки[i][j]=0;
               КонецЕсли;    
           КонецЦикла;    
       КонецЦикла;
       Пока счБазисных<(m+n-1) Цикл
           Сообщить("Решение вырождено");
           ПоискНулевойЯчейкиДляВводаВБазис();
           счБазисных=счБазисных+1;
       КонецЦикла;
       Если ВычислениеПотенциалов()=Ложь Тогда
           Продолжить;
       КонецЕсли;    
       Если ПроверкаОптимальности()=Истина Тогда
           Сообщить("Solution is optimal.");
           Прервать;
       КонецЕсли;
       Сообщить("Solution is not optimal.");
       Если НайтиЦикл(i1, j1)= Ложь Тогда
           ВызватьИсключение("Unable to find a cycle");
       КонецЕсли;
       ПерераспределениеПоЦиклу();
       чСумма=СтоимостьПеревозки();
       Сообщить("***");
       Сообщить("The cost of transport: "+чСумма);
   КонецЦикла;    
   Возврат Истина;

КонецФункции

&НаКлиенте Процедура КомандаРассчитать(Команда) 

   РешениеТранспортнойЗадачи();

КонецПроцедуры</lang>

Retrieved from "https://rosettacode.org/wiki/Transportation_problem?oldid=232158"