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

 

Задача решается как транспортная задача, матрица стоимостей которой  составляется как сумма матриц:

 

С=()=(+), i=1,2,,…,m,    j=1,2,…,n. 

 

Вводится фиктивный потребитель. Затем задача решается обычным способом. Далее сокращается производство в пунктах, продукция которых  в оптимальном плане перевозок  поставляется фиктивному потребителю.

 

Задача о назначениях, или проблема выбора.

 

Имеется  m групп людей (станков) численностью  , которые должны выполнять n видов работ (операций) объемом . Известна производительность каждой i–й группы людей (станков) при выполнении каждого j–го вида работ (операций) , i=1,2,,…,m,    j=1,2,…,n.  . Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объем производства работ (операций) был максимальным.

 

Составим математическую модель данной задачи по аналогии с  транспортной задачей. Обозначим  - число людей (станков) i–й группы, занятых   j–го  вида   работ   (операций). Запишем   математическую   модель        

 

,                                        

 

      ,   i=1,2,…,m ,                                    

 

     ,   j=1, 2, … , n,                                   

 

     ,      i=1,2,,…,m,    j=1,2,…,n.                

 

   Для использования  алгоритмов, разработанных для транспортной  задачи, можно перейти от нахождения  максимума к нахождению минимума. Для этого нужно умножить коэффициенты  целевой функции на (-1), тогда целевая  функция будет иметь вид

 

     -.

 

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

 

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

 

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

 

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

 

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

 

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

 

 

 

Рисунок 1.1

 

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

 

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

 

 

 

 

 

Рисунок 1.2

 

 

 

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

 

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

 

Заметим, что если в процессе поиска строки не удается найти столбец, не являющийся “тупиковым путем”, то происходит возвращение к строке предыдущего поиска столбца. Если в  поисках столбца удается найти  только строки, соответствующие тупиковым  путям, то осуществляется возвращение  к строке предыдущего поиска строки. Однако в силу того, что ММ сохраняет  свое значение, ошибка не повторяется  в дальнейшем. Поскольку базис  задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано.

 

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

 

 

 

Рисунок 1.3

 

Литература:

 

1.               Жуковский Е.М. Тулупов Л.П.  Автоматизированные системы управления  перевозочными процессами на  железных дорогах // уч.пос. для  вузов, Москва, «Транспорт», 1991.

 

2.               Тастимбаев В.К. Недостаток действующих  АСУ на железнодорожном транспорте  журнал  «Магистраль».

 

3.              Тен Т.Л., Косова Е.Г. Проектирование  информационных систем в транспортных  организациях. Учебное пособие, Караганда, 2008г.