// Решение транспортной задачи для 1С:Предприятие 8.2 (релиз 8.2.14.532) // Поиск начального решения производится методами северо-западного угла, минимальной стоимости и Фогеля // (можно выбрать любой из трех методов). Тестовые примеры (код и алгоритм изменены) были взяты отсюда: // http://code.activestate.com/recipes/576575-stepping-stone-algorithum-for-solving-the-tranship/ // Подробное описание алгоритма см. тут: http://cyclowiki.org/wiki/Транспортная_задача перем m,n; //Размер таблицы перем u,v; //Потенциалы перем БазисныеЯчейки; //Базисные ячейки (занятые перевозками) перем iЦикл, jЦикл; //Массивы с координатами цикла перем Цены, Спрос, Предложение, Отгрузки; // Массивы транспортной задачи перем i1, j1; //Ячейка начала цикла пересчета перем СпросОстаток, ПредложениеОстаток; //Массивы для метода "северо-западного угла" перем гл_сч; перем Фогель_i, Фогель_j; перем гсч; //Генератор случайных чисел Функция Пример1() m=4; n=6; Цены = Новый Массив(m+1, n+1); Цены[1][1]=2; Цены[1][2]=1; Цены[1][3]=3; Цены[1][4]=3; Цены[1][5]=2; Цены[1][6]=5; Цены[2][1]=3; Цены[2][2]=2; Цены[2][3]=2; Цены[2][4]=4; Цены[2][5]=3; Цены[2][6]=4; Цены[3][1]=3; Цены[3][2]=5; Цены[3][3]=4; Цены[3][4]=2; Цены[3][5]=4; Цены[3][6]=1; Цены[4][1]=4; Цены[4][2]=2; Цены[4][3]=2; Цены[4][4]=1; Цены[4][5]=2; Цены[4][6]=2; Спрос = Новый Массив(n+1); Спрос[1]=30; Спрос[2]=50; Спрос[3]=20; Спрос[4]=40; Спрос[5]=30; Спрос[6]=11; Предложение = Новый Массив(m+1); Предложение[1]=50; Предложение[2]=40; Предложение[3]=60; Предложение[4]=31; КонецФункции Функция Пример2() m=4; n=6; Цены = Новый Массив(m+1, n+1); Цены[1][1]=1; Цены[1][2]=2; Цены[1][3]=1; Цены[1][4]=4; Цены[1][5]=5; Цены[1][6]=2; Цены[2][1]=3; Цены[2][2]=3; Цены[2][3]=2; Цены[2][4]=1; Цены[2][5]=4; Цены[2][6]=3; Цены[3][1]=4; Цены[3][2]=2; Цены[3][3]=5; Цены[3][4]=9; Цены[3][5]=6; Цены[3][6]=2; Цены[4][1]=3; Цены[4][2]=1; Цены[4][3]=7; Цены[4][4]=3; Цены[4][5]=4; Цены[4][6]=6; Спрос = Новый Массив(n+1); Спрос[1]=20; Спрос[2]=40; Спрос[3]=30; Спрос[4]=10; Спрос[5]=50; Спрос[6]=25; Предложение = Новый Массив(m+1); Предложение[1]=30; Предложение[2]=50; Предложение[3]=75; Предложение[4]=20; КонецФункции Функция Пример3() m=3; n=5; Цены = Новый Массив(m+1, n+1); Цены[1][1]=5; Цены[1][2]=3; Цены[1][3]=6; Цены[1][4]=2; Цены[1][5]=0; Цены[2][1]=4; Цены[2][2]=7; Цены[2][3]=9; Цены[2][4]=1; Цены[2][5]=0; Цены[3][1]=3; Цены[3][2]=4; Цены[3][3]=7; Цены[3][4]=5; Цены[3][5]=0; Спрос = Новый Массив(n+1); Спрос[1]=16; Спрос[2]=18; Спрос[3]=30; Спрос[4]=25; Спрос[5]=1; Предложение = Новый Массив(m+1); Предложение[1]=19; Предложение[2]=37; Предложение[3]=34; КонецФункции //Функция распределяет Отгрузки[i][j простейшим методом "северо-западного угла" //Также заполняет БазисныеЯчейки[i][j] значениями 1 или 0 (если есть ненулевая //отгрузка, то ячейка - базисная). Функция РаспределениеМетодомСевероЗападногоУгла() Для 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 Тогда ВызватьИсключение("Ошибка: остаток предложения меньше 0"); КонецЕсли; чОбъем=СпросОстаток[j]; Если чОбъем=0 Тогда Продолжить; ИначеЕсли чОбъем<0 Тогда ВызватьИсключение("Ошибка: остаток спроса меньше 0"); КонецЕсли; Если ПредложениеОстаток[i]<чОбъем Тогда чОбъем=ПредложениеОстаток[i]; КонецЕсли; СпросОстаток[j]=СпросОстаток[j]-чОбъем; ПредложениеОстаток[i]=ПредложениеОстаток[i]-чОбъем; БазисныеЯчейки[i][j]=1; Отгрузки[i][j]=чОбъем; КонецЦикла; КонецЦикла; КонецФункции //Метод минимальных тарифов - сначала отгружает по путям с на именьшей стоимостью. Функция РаспределениеМетодомМинимальныхТарифов() Для j=1 по n Цикл СпросОстаток[j]=Спрос[j]; КонецЦикла; Для i=1 по m Цикл ПредложениеОстаток[i]=Предложение[i]; КонецЦикла; Для i=1 по m Цикл Для j=1 по n Цикл БазисныеЯчейки[i][j]=0; Отгрузки[i][j]=0; КонецЦикла; КонецЦикла; Для й=1 по m*n Цикл // Максимальное число итераций мин_тариф=НеОпределено; i_мин=НеОпределено; j_мин=НеОпределено; ВесьГрузРаспределен=Истина; Для i=1 по m Цикл Для j=1 по n Цикл Если БазисныеЯчейки[i][j]=1 Тогда Продолжить; КонецЕсли; Если ПредложениеОстаток[i]=0 Тогда Продолжить; ИначеЕсли ПредложениеОстаток[i]<0 Тогда ВызватьИсключение("Ошибка: остаток предложения меньше 0"); КонецЕсли; Если СпросОстаток[j]=0 Тогда Продолжить; ИначеЕсли СпросОстаток[j]<0 Тогда ВызватьИсключение("Ошибка: остаток спроса меньше 0"); КонецЕсли; ВесьГрузРаспределен=Ложь; ц=Цены[i][j]; Если мин_тариф=НеОпределено Тогда мин_тариф=ц; i_мин=i; j_мин=j; Иначе Если ц<мин_тариф Тогда мин_тариф=ц; i_мин=i; j_мин=j; КонецЕсли; КонецЕсли; КонецЦикла; КонецЦикла; i=i_мин; j=j_мин; Если ВесьГрузРаспределен=Истина Тогда Возврат Истина; КонецЕсли; Если мин_тариф=НеОпределено Тогда ВызватьИсключение("Не удалось определить минимальный тариф"); КонецЕсли; //Минимальный тариф найден в ячейке i, j чОбъем=СпросОстаток[j]; Если ПредложениеОстаток[i]<чОбъем Тогда чОбъем=ПредложениеОстаток[i]; КонецЕсли; //Сообщить("Объем в ячейке ="+чОбъем); СпросОстаток[j]=СпросОстаток[j]-чОбъем; ПредложениеОстаток[i]=ПредложениеОстаток[i]-чОбъем; БазисныеЯчейки[i][j]=1; Отгрузки[i][j]=чОбъем; КонецЦикла; ВызватьИсключение("Не удалось распределить методом минимальных тарифов"); КонецФункции //Получение начального решения методом Фогеля (альтернатива двум предыдущим методам) Функция РаспределениеМетодомФогеля() Для j=1 по n Цикл СпросОстаток[j]=Спрос[j]; КонецЦикла; Для i=1 по m Цикл ПредложениеОстаток[i]=Предложение[i]; КонецЦикла; Для i=1 по m Цикл Для j=1 по n Цикл БазисныеЯчейки[i][j]=0; Отгрузки[i][j]=0; КонецЦикла; КонецЦикла; Для й=1 по 100 Цикл макс1=НеОпределено; макс1_i=НеОпределено; Для i=1 по m Цикл Если ПредложениеОстаток[i]=0 Тогда Продолжить; КонецЕсли; дельта=Фогель_РазницаМеждуМинимальнымиЦенамиПоСтроке(i); Если макс1_i=НеОпределено Тогда макс1=дельта; макс1_i=i; Иначе Если макс1<дельта Тогда макс1=дельта; макс1_i=i; КонецЕсли; КонецЕсли; КонецЦикла; макс2=НеОпределено; макс2_j=НеОпределено; Для j=1 по n Цикл Если СпросОстаток[j]=0 Тогда Продолжить; КонецЕсли; дельта=Фогель_РазницаМеждуМинимальнымиЦенамиПоСтолбцу(j); Если макс2_j=НеОпределено Тогда макс2=дельта; макс2_j=j; Иначе Если макс2<дельта Тогда макс2=дельта; макс2_j=j; КонецЕсли; КонецЕсли; КонецЦикла; Если (макс1=НеОпределено) и (макс2=НеОпределено) Тогда //Всё отгрузили Прервать; ИначеЕсли (макс1=НеОпределено) Тогда макс1=макс2-1; ИначеЕсли (макс2=НеОпределено) Тогда макс2=макс1-1; КонецЕсли; Если макс1>макс2 Тогда //Предпочтительна строка макс1_i зн=Фогель_ПерваяМинимальнаяЦенаПоСтроке(макс1_i); i=макс1_i; j=Фогель_j; Иначе //Предпочтителен столбец макс2_j зн=Фогель_ПерваяМинимальнаяЦенаПоСтолбцу(макс2_j); i=Фогель_i; j=макс2_j; КонецЕсли; чОбъем=СпросОстаток[j]; Если ПредложениеОстаток[i]<чОбъем Тогда чОбъем=ПредложениеОстаток[i]; КонецЕсли; СпросОстаток[j]=СпросОстаток[j]-чОбъем; ПредложениеОстаток[i]=ПредложениеОстаток[i]-чОбъем; БазисныеЯчейки[i][j]=1; Отгрузки[i][j]=чОбъем; КонецЦикла; КонецФункции //Вычисляет первую минимальную цену в указанной строке //Обходит стороной ячейки, где остаток спроса = 0. //Возвращает минимальную цену, а j минимальной ячейки - в переменной Фогель_j Функция Фогель_ПерваяМинимальнаяЦенаПоСтроке(i) мин1=НеОпределено; Фогель_j=НеОпределено; Для j=1 по n Цикл Если СпросОстаток[j]=0 Тогда Продолжить; ИначеЕсли СпросОстаток[j]<0 Тогда ВызватьИсключение("Ошибка: остаток спроса меньше 0"); КонецЕсли; ц=Цены[i][j]; Если мин1=НеОпределено Тогда мин1=ц; Фогель_j=j; Иначе Если мин1>ц Тогда мин1=ц; Фогель_j=j; КонецЕсли; КонецЕсли; КонецЦикла; Возврат мин1; КонецФункции //Вычисляет первую минимальную цену в указанной строке //Обходит стороной ячейки, где остаток спроса = 0, а также Фогель_j. //Возвращает вторую минимальную цену. Функция Фогель_ВтораяМинимальнаяЦенаПоСтроке(i) мин2=НеОпределено; Если Фогель_j=НеОпределено Тогда Возврат НеОпределено; КонецЕсли; Для j=1 по n Цикл Если j=Фогель_j Тогда Продолжить; КонецЕсли; Если СпросОстаток[j]=0 Тогда Продолжить; КонецЕсли; ц=Цены[i][j]; Если мин2=НеОпределено Тогда мин2=ц; Иначе Если мин2>ц Тогда мин2=ц; КонецЕсли; КонецЕсли; КонецЦикла; Возврат мин2; КонецФункции //Вычисляет первую минимальную цену по указанному столбцу. //Обходит стороной ячейки, где остаток предложения = 0. //Возвращает минимальную цену, а i минимальной ячейки - в переменной Фогель_i Функция Фогель_ПерваяМинимальнаяЦенаПоСтолбцу(j) мин1=НеОпределено; Фогель_i=НеОпределено; Для i=1 по m Цикл Если ПредложениеОстаток[i]=0 Тогда Продолжить; ИначеЕсли ПредложениеОстаток[i]<0 Тогда ВызватьИсключение("Ошибка: остаток предложения меньше 0"); КонецЕсли; ц=Цены[i][j]; Если мин1=НеОпределено Тогда мин1=ц; Фогель_i=i; Иначе Если мин1>ц Тогда мин1=ц; Фогель_i=i; КонецЕсли; КонецЕсли; КонецЦикла; Возврат мин1; КонецФункции //Вычисляет вторую минимальную цену по указанному столбцу. //Обходит стороной ячейки, где остаток предложения = 0, а также Фогель_i. //Возвращает минимальную цену, а i минимальной ячейки - в переменной Фогель_i Функция Фогель_ВтораяМинимальнаяЦенаПоСтолбцу(j) мин2=НеОпределено; Если Фогель_i=НеОпределено Тогда Возврат НеОпределено; КонецЕсли; Для i=1 по m Цикл Если i=Фогель_i Тогда Продолжить; КонецЕсли; Если ПредложениеОстаток[i]=0 Тогда Продолжить; КонецЕсли; ц=Цены[i][j]; Если мин2=НеОпределено Тогда мин2=ц; Фогель_i=i; Иначе Если мин2>ц Тогда мин2=ц; Фогель_i=i; КонецЕсли; КонецЕсли; КонецЦикла; Возврат мин2; КонецФункции Функция Фогель_РазницаМеждуМинимальнымиЦенамиПоСтроке(i) ц1=Фогель_ПерваяМинимальнаяЦенаПоСтроке(i); Если ц1=НеОпределено Тогда Возврат 0; КонецЕсли; ц2=Фогель_ВтораяМинимальнаяЦенаПоСтроке(i); Если ц2=НеОпределено Тогда Возврат 0; КонецЕсли; Возврат ц2-ц1; КонецФункции Функция Фогель_РазницаМеждуМинимальнымиЦенамиПоСтолбцу(j) ц1=Фогель_ПерваяМинимальнаяЦенаПоСтолбцу(j); Если ц1=НеОпределено Тогда Возврат 0; КонецЕсли; ц2=Фогель_ВтораяМинимальнаяЦенаПоСтолбцу(j); Если ц2=НеОпределено Тогда Возврат 0; КонецЕсли; Возврат ц2-ц1; КонецФункции //Проверяет правильность отгрузок: отгрузки по каждой строке должны быть равны предложению, //а отгрузки по каждому столбцу - спросу потребителя. Функция ПроверкаПравильностиОтгрузок() Для i=1 по m Цикл стр="Отгрузки: "; Для j=1 по n Цикл стр=стр+Отгрузки[i][j]+" "; КонецЦикла; Сообщить(стр); КонецЦикла; Для i=1 по m Цикл чОбъем=0; Для j=1 по n Цикл чОбъем=чОбъем+Отгрузки[i][j]; КонецЦикла; Если чОбъем<>Предложение[i] Тогда ВызватьИсключение("Ошибка: отгрузки по строке не равны предложению в строке "+i); КонецЕсли; КонецЦикла; Для j=1 по n Цикл чОбъем=0; Для i=1 по m Цикл чОбъем=чОбъем+Отгрузки[i][j]; КонецЦикла; Если чОбъем<>Спрос[j] Тогда ВызватьИсключение("Ошибка: отгрузки по столбцу не равны спросу в столбце "+j); КонецЕсли; КонецЦикла; Возврат Истина; КонецФункции //Вычисление потенциалов u[i] и v[j] Функция ВычислениеПотенциалов() перем i, j; Для i=1 по m Цикл u[i]=НеОпределено; КонецЦикла; Для j=1 по n Цикл v[j]=НеОпределено; КонецЦикла; u[1]=0; гл_сч=m*n; // Максимальное число итераций ВычислениеПотенциаловПоГоризонтали(1); //Начало рекурсии //Проверка Для i=1 по m Цикл Если u[i]=НеОпределено Тогда Сообщить("Не удалось вычислить потенциал u["+i+"]"); Возврат Ложь; КонецЕсли; КонецЦикла; Для j=1 по n Цикл Если v[j]=НеОпределено Тогда Сообщить("Не удалось вычислить потенциал v["+j+"]"); Возврат Ложь; КонецЕсли; КонецЦикла; Возврат Истина; КонецФункции Функция ВычислениеПотенциаловПоВертикали(j) Если v[j]=НеОпределено Тогда ВызватьИсключение("Ошибка получения потенциала v["+j+"]"); КонецЕсли; Для i=1 по m Цикл Если БазисныеЯчейки[i][j]=0 Тогда Продолжить; КонецЕсли; Если u[i]<>НеОпределено Тогда Продолжить; Иначе u[i]=Цены[i][j]-v[j]; ВычислениеПотенциаловПоГоризонтали(i); КонецЕсли; КонецЦикла; КонецФункции Функция ВычислениеПотенциаловПоГоризонтали(i) гл_сч=гл_сч-1; Если гл_сч=0 Тогда ВызватьИсключение("Зацикливание при вычислении потенциалов"); КонецЕсли; Если u[i]=НеОпределено Тогда ВызватьИсключение("Ошибка получения потенциала u["+i+"]"); КонецЕсли; Для j=1 по n Цикл Если БазисныеЯчейки[i][j]=0 Тогда Продолжить; КонецЕсли; Если v[j]<>НеОпределено Тогда Продолжить; Иначе v[j]=Цены[i][j]-u[i]; ВычислениеПотенциаловПоВертикали(j); КонецЕсли; КонецЦикла; КонецФункции //По известным потенциалам u и v, а также ценам, вычисляет //оптимальное ли решение (возвращает Истина или Ложь). //Если решение не оптимально, находит ячейку i1,j1 с минимальной отрицательной дельтой, //откуда будем строить цикл. Функция ПроверкаОптимальности() перем чРешениеОптимально, чМинимальнаяДельта, 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 Тогда ВызватьИсключение("Не существует не базисной (нулевой) ячейки для ввода в базис"); КонецЕсли; Пока 1=1 Цикл //Случайные значения для предотвращения зацикливания, согласно рекомендации Данцига //Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 стр. 312 i=ГСЧ.СлучайноеЧисло(1, m); j=ГСЧ.СлучайноеЧисло(1, n); Если БазисныеЯчейки[i][j]=1 Тогда //Пропускаем базисные ячейки Продолжить; КонецЕсли; Если Отгрузки[i][j]<>0 Тогда ВызватьИсключение("Ненулевые отгрузки для не базисной ячейки"); КонецЕсли; //Если НайтиЦикл(i, j)=Истина Тогда // //Пропускаем ячейки, которые образуют цикл // Продолжить; //КонецЕсли; БазисныеЯчейки[i][j]=1; Сообщить("В базис введена ячейка "+i+" "+j); Возврат Истина; //Удалось ввести ячейку в базис КонецЦикла; КонецФункции //Поиск цикла для перераспределения поставок. //Заполняет массивы iЦикл и jЦикл с координатами вершин цикла. //Возвращает Истина, если цикл найден и Ложь, если не удалось найти цикл. Функция НайтиЦикл(i0, j0) гл_сч = m*n; // максимальное число итераций iЦикл.Очистить(); jЦикл.Очистить(); Если НайтиЦикл_ПоГоризонтали(i0, j0) Тогда Возврат Истина; //Цикл найден успешно КонецЕсли; Возврат Ложь;//Цикл не найден КонецФункции Функция НайтиЦикл_ПоГоризонтали(i0, j0) гл_сч=гл_сч-1; Если гл_сч=0 Тогда ВызватьИсключение("Слишком большое число итераций при поиске цикла"); КонецЕсли; Для 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Цикл.Количество()); Если jЦикл.Количество()<>iЦикл.Количество() Тогда ВызватьИсключение("Не одинаковые размерности для координат цикла"); КонецЕсли; Если iЦикл.Количество()<4 Тогда ВызватьИсключение("Цикл имеет меньше 4 элементов"); КонецЕсли; Тета=НеОпределено; Знак="+"; Для й=0 по iЦикл.ВГраница() Цикл i=iЦикл[й]; j=jЦикл[й]; Если Знак="-" Тогда Объем=Отгрузки[i][j]; Если Тета=НеОпределено Тогда Тета=Объем; Иначе Если Объем<Тета Тогда Тета=Объем; КонецЕсли; КонецЕсли; Знак="+"; Иначе Знак="-"; КонецЕсли; КонецЦикла; Если Тета=НеОпределено Тогда ВызватьИсключение("Не удалось вычислить переменную тета."); КонецЕсли; Сообщить("Тета="+Тета); Если Тета=0 Тогда Возврат Ложь; КонецЕсли; Знак="+"; Для й=0 по iЦикл.ВГраница() Цикл i=iЦикл[й]; j=jЦикл[й]; Если Знак="-" Тогда Отгрузки[i][j]=Отгрузки[i][j]-Тета; Знак="+"; Иначе Отгрузки[i][j]=Отгрузки[i][j]+Тета; Знак="-"; КонецЕсли; КонецЦикла; Возврат Истина; КонецФункции //Главная функция - точка входа Функция РешениеТранспортнойЗадачи() //Раскомментируйте нужный пример //Пример1(); Пример2(); //Пример3(); ГСЧ = Новый ГенераторСлучайныхЧисел(); БазисныеЯчейки = Новый Массив(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]; КонецЦикла; Если чПредложение>чСпрос Тогда Сообщить("Предложение больше спроса на "+(чПредложение-чСпрос)+" единиц груза. Создайте фиктивного потребителя."); Возврат Ложь; ИначеЕсли чПредложение<чСпрос Тогда Сообщить("Предложение меньше спроса на "+(чСпрос-чПредложение)+" единиц груза. Создайте фиктивного поставщика."); Возврат Ложь; КонецЕсли; //Добавление возмущений (эпсилон) во избежание зацикливания транспортной задачи. См. литературу: //Дж. Данциг «Линейное программирование, его применения и обобщения» М:Прогресс, 1966 стр. 303 //С.Гасс. «Линейное программирование (методы и приложения)», М:1961 стр. 195 //В данном случае закомментировано, поскольку применен метод случайного включения нулевой перевозки //в базис, который также, согласно Данцигу, страхует от зацикливания. //epsilon = 0.0001; //epsilon1= 0; // //Для j=1 по n Цикл // Спрос[j]=Спрос[j]+epsilon; // epsilon1=epsilon1+epsilon; //КонецЦикла; //Предложение[1]=Предложение[1]+epsilon1; РаспределениеМетодомСевероЗападногоУгла(); чСумма=СтоимостьПеревозки(); Сообщить("Стоимость перевозки методом северо-западного угла: "+чСумма); РаспределениеМетодомМинимальныхТарифов(); чСумма=СтоимостьПеревозки(); Сообщить("Стоимость перевозки методом минимальных тарифов: "+чСумма); РаспределениеМетодомФогеля(); чСумма=СтоимостьПеревозки(); Сообщить("Стоимость перевозки методом Фогеля: "+чСумма); Пока 1=1 Цикл ПроверкаПравильностиОтгрузок(); счБазисных=0; Для i=1 по m Цикл Для j=1 по n Цикл Если Отгрузки[i][j]>0 Тогда БазисныеЯчейки[i][j]=1; счБазисных=счБазисных+1; ИначеЕсли Отгрузки[i][j]<0 Тогда ВызватьИсключение("Отгрузки не должны быть отрицательными"); Иначе БазисныеЯчейки[i][j]=0; КонецЕсли; КонецЦикла; КонецЦикла; Пока счБазисных<(m+n-1) Цикл Сообщить("Решение вырождено"); ПоискНулевойЯчейкиДляВводаВБазис(); счБазисных=счБазисных+1; КонецЦикла; Если ВычислениеПотенциалов()=Ложь Тогда Продолжить; КонецЕсли; Если ПроверкаОптимальности()=Истина Тогда Сообщить("РЕШЕНИЕ ОПТИМАЛЬНО"); Прервать; // Решение найдено КонецЕсли; Сообщить("Решение не оптимальное"); Если НайтиЦикл(i1, j1)= Ложь Тогда ВызватьИсключение("Не удалось найти цикл"); КонецЕсли; ПерераспределениеПоЦиклу(); чСумма=СтоимостьПеревозки(); Сообщить("***"); Сообщить("Стоимость перевозки: "+чСумма); КонецЦикла; Возврат Истина; КонецФункции &НаКлиенте Процедура КомандаРассчитать(Команда) РешениеТранспортнойЗадачи(); КонецПроцедуры