|
Дельта-метод решения транспортной задачи
Содержание.
Введение..............................................................................................
1.Транспортная задача линейного программирования
1.1 Постановка задачи и ее математическая модель...................
1.2 Открытая модель транспортной задачи....................................
1.3 Построение первоначального опорного плана........................
2. Дельта-метод решения транспортной задачи
2.1 Алгоритм решения транспортной задачи дельта-методом...
3. Проверка оптимальности методом потенциалов
3.1 Метод потенциалов..................................................................
3.2 Построение системы потенциалов.........................................
3.3 Проверка выполнения условия оптимальности для
незанятых клеток......................................................................
4. Пример построения первоначального опорного плана
дельта-методом
4.1 Построение математической модели
транспортной задачи..............................................................
4.2 Построение первоначального опорного плана
дельта-методом .....................................................................
5. Описание программы......................................................................
Список использованной литературы .............................................
Приложение.....................................................................................
Введение
Транспортная задача линейного программирования получила в настоящее время
широкое распространение в теоретических обработках и практическом применении
на транспорте и в промышленности. Особенно важное значение она имеет в деле
рационализации постановок важнейших видов промышленной и
сельскохозяйственной продукции, а также оптимального планирования грузопотоков
и работы различных видов транспорта
Цель заданной работы - освоить алгоритм построения первого опорного
плана закрытой транспортной задачи
дельта-методом и написать его программную реализацию.
1.Транспортная задача линейного программирования.
1.1 Постановка задачи и ее математическая модель.
Некоторый однородный продукт, сосредоточенный у m поставщиков Ai в
количестве ai (i=1,2,3,...,m) единиц соответственно, необходимо доставить n
потребителям Bj в количестве bj (j=1,2,3,...,n) единиц. Известна стоимость Cij
перевозки единицы груза от i-го поставщика к j-му потребителю.
Необходимо составить план перевозок, позволяющий вывезти все грузы,
полностью удовлетворить Cij xij потребности и имеющий минимальную стоимость.
Обозначим через xij количество единиц груза, запланированных к перевозке от i-
го поставщика к j-му потребителю; тогда условия задачи можно записать в виде
таблицы, которую в дальнейшем будем называть матрицей планирования.
Таблица 1
Поставщи
ки
Потребители
Запасы
B1
B2
...
Bn
A1
C11
x11
C12
x12
...
C1n
x1n
a1
A2
C21
x21
C22
x22
...
C2n
x2n
a2
...
...
...
...
...
...
Am
Cm1
xm1
Cm2
xm2
...
Cmn
xmn
am
Потребно
сти
b1
b2
...
bn
Составим математическую модель задачи. Так как от i-го поставщика к j-му
потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки
составит Cijxij.
Стоимость всего плана выразится двойной суммой:
Z = .
Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть вывезены, т.е.
(i = 1,2,3,..., m) (эти уравнения получаются из строк таблицы 1);
б) все потребности должны быть удовлетворены, т.е.
(j = 1,2,3,...,n) (уравнения получаются из столбцов таблицы 1).
Таким образом, математическая модель транспортной задачи имеет следующий
вид.
Найти наименьшее значение линейной функции:
Z = ( 1)
при ограничениях
, i = 1, 2, ..., m, ( 2 )
, j = 1,2,3,...,n , ( 3 )
xij ? 0 ( j = 1,2,3, ..., m; i = 1,2,3, ..., n).
В рассмотренной модели предполагается, что суммарные запасы равны
суммарным потребностям, т.е.
( 4 )
Такая модель называется закрытой.
Теорема 1. Любая транспортная задача, у которой суммарный объем запасов
совпадает с суммарным объемом потребностей, имеет решение.
Для доказательства теоремы необходимо показать, что при заданных условиях
существует хотя бы один план задачи и линейная функция на множестве планов
ограничена.
Доказательство. Пусть = M > 0 .
Тогда величины xij = aibj /M (i = 1,2,3, ... m ; j = 1,2,3, ..., n)
являются планом, так как они удовлетворяют системе ограничений
( 2 ) и ( 3 ) .
Действительно, подставляя значения в ( 2 ) и ( 3 ) , находим
= ai ,
= bj .
Выберем из значений Cij наибольшее C? = max Cij и заменим в линейной функции
( 1 ) все коэффициенты на C? тогда, учитывая ( 2 ) , получим
,
Aыберем из значений Cij наименьшее C??=min Cij и заменим в линейной функции
все коэффициенты на C?? ; тогда, учитывая ( 2 ) имеем
Объединяя два последних неравенства в одно двойное , окончательно получаем
C??M ? Z ? C? M ,
т. е. линейная функция ограничена на множестве планов транспортной задачи .
1.2 Открытая модель транспортной задачи
Транспортная задача, в которой суммарные запасы и потребности совпадают, т.
е. выполняется условие , называется закрытой моделью; в противном
случае ? открытой. Для открытой модели может быть два случая:
a) суммарные запасы превышают суммарные потребности ;
b) суммарные потребности превышают суммарные запасы .
Линейная функция одинакова в обоих случаях, изменяется только вид системы
ограничений.
Найти минимальное значение линейной функции
при ограничениях
, i = 1, 2, ..., m, (случай а)
, j = 1, 2, ..., n;
, i = 1, 2, ..., m, (случай б)
, j = 1, 2, ..., n,
xij ? 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).
Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности,
вводится фиктивный потребитель Bn+1, потребности которого bn+1 = . В
случае (б), когда суммарные потребности превышают суммарные запасы, вводится
фиктивный поставщик Am+1, запасы которого am+1 = .
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость
перевозки единицы груза от фиктивного поставщика полагают равными нулю, так
как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается
обычном способом. При равных стоимостях перевозки единицы груза от
поставщиков к фиктивному потребителю затраты на перевозку груза реальным
потребителям минимальны, а фиктивному потребителю будет направлен груз от
наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного
поставщика.
Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала
проверить, к какой модели она принадлежит, и только после этого составить
таблицу для ее решения.
1.3 Построение первоначального опорного плана .
Как и для других задач линейного программирования, итерационный процесс по
отысканию оптимального плана транспортной задачи начинается с опорного плана .
Рассмотрим систему ограничений ( 2 ) и ( 3 ) транспортной задачи. Она содержит
m?n неизвестных и m+n уравнений,
связанных соотношением (4). Если сложить почленно уравнения отдельно
подсистемы ( 2 ) и отдельно подсистемы ( 3 ), то получим два одинаковых
уравнения . В таблице такое сложение равнозначно соответственно почленному
сложению столбцов и почленно сложению строк .
Наличие в системе ограничений двух одинаковых уравнений говорит о ее
линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае
система ограничений должна содержать m+n-1 линейно независимых уравнений,
следовательно, невырожденный опорный план транспортной задачи содержит m+n-
1 положительных компонент или перевозок.
Таким образом, если каким-либо способом получен невырожденный опорный
план транспортной задачи, то в матрице
( Xij ) (i = 1, 2, ..., m; j = 1, 2, ... , n) значений его компонент (таблицы 1)
положительными являются только
m+n-1, а остальные равны нулю.
Если условие транспортной задачи и ее опорный план записаны в виде таблицы,
то клетки, в которых находятся отличные от нуля перевозки, называются
занятыми, а остальные ? незанятыми.
Занятые клетки соответствует неизвестным, и для невырожденного опорного
плана их количество равно
m+n-1. Если ограничения транспортной задачи записаны в виде ( 2 ) и (3) то, как
известно, базисным неизвестным, включенным в опорный план, соответствует
система линейно независимых векторов.
Всякий план транспортной задачи, содержащий более
m+n-1 занятых клеток, не являются опорным, так как ему соответствует линейно
зависимая система векторов. При таком плане в таблице всегда можно построить
замкнутый цикл, с помощью которого уменьшают число занятых клеток до m+n-1.
Циклом называется набор клеток вида ( i1 j1 )( i1 j2 )?( j2 i2 )( j1 im ), в котором две
и только две соседние клетки расположены в одном столбце или одной строке
таблицы, причем последняя клетка находится в той же строке или столбце, что и
первая.
Если к занятым клеткам, определяющим опорный невырожденный план,
следовательно, и ацикличный, присоединить какую-либо незанятую клетку, то план
становится не опорным, появляется единственный цикл, все вершины которого, за
исключением одной, лежат в занятых клетках.
Существует несколько простых схем построения первоначального опорного плана
транспортной задачи.
При составлении первоначального опорного плана методом северо-западного
угла стоимость перевозки единицы не учитывается, поэтому построенный план
далек от оптимального, получение которого связано с большим объемом
вычислительных работ. Поэтому рассмотренный метод используется при
вычислениях с помощью ЭВМ.
При использовании метода минимальной стоимости запасы поставщиков
перераспределяются потребителям по минимальным стоимостям , а в методе
двойного предпочтения перераспределения предпочтительно производятся через
те клетки ,чьи стоимости минимальны как для поставщиков , так и для
потребителей .
Стоимости планов , полученных методами минимальной стоимости и двойного
предпочтения меньше стоимости плана, полученного методом северно-западного
угла , значит они ближе к оптимальному.
Между собой методы минимальной стоимости и двойного предпочтения
равноценны, их легко программировать. Полученные планы доводят до
оптимального методом потенциалов .
2. Дельта-метод решения транспортной задачи.
При составлении плана перевозок с помощью решения транспортной задачи
линейного программирования большое значение имеет время , затраченное на её
реализацию.
Применение метода двойного предпочтения и метода потенциалов для решения
транспортной задачи с 10-15 поставщиками и 15-20 потребителями требует 4-5
часов непрерывных вычислений . Это происходит потому, что существующие
методы составления первоначального опорного плана позволяют получить план,
далёкий от оптимального. Как показала практика , использование дельта-метода
даёт возможность найти оптимальный план в 3-4 раза быстрее , причем чем
больше размеры таблицы, тем ощутимее разница во времени. Это объясняется
тем , что в результате применения дельта-метода всегда находится оптимальный
план. Если построенный план оказался неоптимальным , то это произошло в
результате допущенных в процессе построения плана ошибок . Алгоритм дельта-
метода рассмотрен ниже .
2.1Алгоритм решения транспортной задачи дельта-методом.
1. Преобразуем таблицу Сij в таблицу приращений , выбирая в каждом
столбце наименьшую стоимость и вычитая её из всех стоимостей столбца.
Значения ij записываем под соответствующими значениями ij .
2. Таблицу ij, преобразуем в таблицу ij , выбирая в каждой строке
наименьшее приращение и вычитая его из всех приращений
строки ; результаты записываем под значениями ij . Если в какой-нибудь
строке уже имеется нулевое приращение после первого преобразования , то в этой
строке приращения оставляем без изменения и преобразуем приращения строк , не
содержащих нулевых приращений .
3. Просматриваем столбцы , содержащие одно нулевое приращение , и в клетки ,
содержащие его , записываем потребности bj , не обращая внимания на величину
запасов поставщиков .
Затем просматриваем столбцы , содержащие два нулевых приращения , и в
клетки , содержащие их , заполняем , учитывая ранее произведённое закрепление и
запасы поставщиков . Затем переходим к столбцам , содержащим три , четыре и
т.д. нулевых приращения .
Процесс закрепления потребителей за поставщиками продолжаем до тех пор, пока
все объёмы потребностей не будут закреплены за поставщиками.
Подсчитываем для строк , i=1,2,...,m. Если все
i = 0, то построение плана закончено. Он же является оптимальным, т.к. все
грузы перевозятся с наименьшими приращениями стоимостей . В общем случае
получаем: а) для одних строк i= 0 (такие строки называются
нулевыми ) ; б) для других i 0 (такие строки называются
недостаточными и отмечаются знаком "+" ) .
3. Отмечаем знаком " V " столбцы , имеющие занятые клетки в избыточных
строках .
4. Для каждой недостаточной и нулевой строки сравниваем ij , стоящие в
отмеченных столбцах , выбираем наименьшее и проставляем в последнюю графу
таблицы .
5. В последней графе таблицы просматриваем ij , недостаточных строк
выбираем наименьшее и сравниваем его с i0j для нулевых строк . При этом
могут быть два случая:
а) для каждой нулевой строки min ij i0j ;
б) для некоторых нулевых строк min ij > i0j.
8. Если выполняется условие а) . то производится непосредственное
перераспределение потребности из избыточной строки в недостаточную клетку
отмеченного
столбца , которой соответствует min( xij ; ain ) , где xij - величина перевозки ,
стоящая в отмеченном столбце избыточной строки ; in - величина разностей ,
стоящих в избыточной и недостаточной строках .
9. Если для некоторой нулевой строки выполняется условие б) . то
перераспределение проверяем по цепочкам ,
идущим через эту нулевую строку из избыточной строки в недостаточную .Для
построения цепочки в нулевой строке в отмеченном столбце находим клетку , для
которой i0j < min ij , и отмечаем её знаком "+" ,в этом же столбце находим
занятую клетку , стоящую в избыточной строке , и отмечаем её знаком "-"- начало
цепочки .
Начиная движение по построенному звену цепочки от "-" к "+", попадаем к
занятой клетке и отмечаем её знаком "-" , далее по столбцу переходим в клетку
недостаточной строки и отмечаем её знаком "+" . Цепочка построена .
Если матрица содержит большое число нулевых строк , то цепочки
перераспределения могут проходить через несколько нулевых строк и их
количество значительно возрастает , поэтому руководствуемся следующим
правилом . При переходе из одной нулевой строки в другую определяем
полученную сумму приращений и сравниваем её с минимумом приращений в
выделенных столбцах данной строки . Если полученная сумма превышает этот
минимум , то продолжение цепочки по данной строке не рассматриваем . Очевидно
также , что если сумма приращений , полученная при переходе в недостаточную
строку , меньше , чем при переходе в любую другую нулевую строку , то не
следует рассматривать продолжение цепочки переходом в нулевую строку .
10. Составляем для каждой цепочки алгебраическую сумму приращений
ij ,считая их отрицательными , если же они стоят в клетке , отмеченной
знаком "-" , и положительными ,
если клетка отмечена знаком "+" . Полученную сумму сравниваем с min ij :
а) если ij min ij aeя всех построенных цепочек , то
отбрасываем их и производим непосредственное перераспределение ;
б) если ij < min ij , то перераспределение производим по
цепочке , для которой эта сумма наименьшая .
При этом возможный объём перераспределения по цепочке равен min ( xik jp ;
in ) , где xik jp - числа указывающие на перевозки , которые стоят в клетках,
отмеченных знаком "-" , 1 k m , 1 p n ; in -разности , стоящие в
избыточной и недостаточной строках , в которых начинается и заканчивается
цепочка , 1 r m . Следуя по цепочке , вычитаем величину перераспределений из
чисел , помещённых в клетках , отмеченных знаком "-" , и прибавляем к числам ,
которые стоят в клетках , отмеченных знаком "+" , на эту же величину изменяем
in . В результате получаем новое закрепление потребителей за поставщиками
11. После перераспределения проверяем возможность исключения отмеченных
столбцов . Столбцы исключаем из отмеченных в том случае , если занятая клетка
избыточной строки превратилась в незанятую или избыточная строка превратилась
в нулевую . В этом случае следующую итерацию следует начинать с п.6 алгоритма
.Если количество отмеченных столбцов осталось без изменения , то следующая
итерация начинается с п.7 алгоритма .
12. Процесс перезакрепления продолжается до тех пор , пока все строки не
превратятся в нулевые .При решении задачи дельта-методом количество итераций
зависит в основном от числа строк , поэтому при m n - поставщиков за потребителями . Дельта-метод позволяет
решать открытую модель , не приводя её к закрытой , однако это возможно только
в том случае , если вычисления абсолютно правильны и все перераспределения
произведены по наилучшим цепочкам .
13. Проверка оптимальности методом потенциалов
3.1 Метод потенциалов
Теорема 2. Если план X* = (x*ij) транспортной задачи является
оптимальным, то ему соответствует набор из m + n чисел Ui* и Vj* ,
удовлетворяющих условиям
Ui* + Vj* = Cij для xij* > 0
Ui* + Vj* ? Cij для xij* = 0
(i = 1, 2, 3, ..., m ; j = 1, 2, 3, ..., n) .
Числа Ui* и Vj* называются потенциалами соответственно поставщиков и
потребителей.
Доказательство. Транспортную задачу минимизации линейной функции Z =
при ограничениях
xi1 + xi2 + ... + xin = ai , i = 1, 2, ... , m,
x1j + x2j + ... + xmj = bj, j = 1, 2, ... , n,
xij ? 0 (i = 1, 2, ... , m; j = 1, 2, ... , n)
можно рассматривать как двойственную некоторой исходной задачи линейного
программирования, условия которой получаются по общей схеме, если каждому
ограничению вида xi1 + xi2 + ... + xin = ai в исходной задаче соответствует
переменная Ui (i = 1, 2, ..., m), а каждому ограничению вида x1j + x2j + xmj = bj ?
переменная Vj (j = 1, 2, ..., n), а именно: максимизировать линейную функцию f =
при ограничениях Ui + Vj ? Cij
(i = 1, 2, ..., m; j = 1, 2, ..., n).
План X* является оптимальным планом двойственной задачи, поэтому план
Y* = ( Ui*, Vj* ) является планом исходной задачи и на основании теоремы
двойственности
max f = min Z
или
,
где xij* ? 0.
На основании теоремы о двойственной задаче, получаем что
ограничения исходной задачи, соответствующие положительным компонентам
оптимального плана двойственной задачи, удовлетворяются как строгие равенства,
а соответствующие компонентам, равным нулю, ? как неравенства, т. е.
Ui* + Vj* = Cij для xij* ? 0 ,
Ui* + Vj* ? Cij для xij* = 0 .
Из доказанной теоремы следует: для того чтобы первоначальный опорный план
был оптимальным, необходимо выполнение следующих условий:
a) для каждой занятой клетки сумма потенциалов должна быть равна стоимости
единицы перевозок, стоящей в этой клетке:
Ui + Vj = Cij ; ( 5 )
b) для каждой незанятой клетки сумма потенциалов должна быть меньше или
равна стоимости единицы перевозки, стоящей в этой клетке :
Ui + Vj ? Cij . ( 6 )
Если хотя бы одна незанятая клетка не удовлетворяет условию ( 6 ), то опорный
план является неоптимальным и его можно улучшить, вводя в базис вектор,
соответствующий клетке, для которой нарушается условие оптимальности,(т. е. в
клетку надо переместить некоторое количество единиц груза).
Таким образом, для проверки на оптимальность необходимо сначала построить
систему потенциалов.
3.2 Построение системы потенциалов
Для построения системы потенциалов используем условие
Ui + Vj = Cij
где Cij? стоимость перевозки единицы груза занятой клетки в i-ой строке и j-м
столбце .
Систему потенциалов можно построить только для невырожденного опорного
плана. Такой план содержит m+n-1 линейно независимых уравнений вида (5) с n+m
неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система
является неопределенной и одному неизвестному (обычно Ui) придают нулевое
значение. После этого остальные потенциалы определяются однозначно.
Пусть известен потенциал Ui; тогда из равенства ( 5 ) следует
Vj = Cij - Ui .
Если известен потенциал Vj , то из того же равенства имеем
Ui = Cij - Vj .
Таким образом, для определения неизвестного потенциала от величины Cij
занятой клетки следует вычесть известный потенциал.
3.3 Проверка выполнение условия оптимальности для незанятых
клеток.
Просматриваем строки и для каждой незанятой клетки проверяем выполнение
условия ( 6 ), т. е. суммируем потенциалы, на пересечения которых стоит незанятая
клетка, то сумму сравниваем со стоимостью, стоящей в ней. Если для всех
незанятых клеток
Ui + Vj ? Cij , то по теореме потенциалов, план является оптимальным.
4. Пример построения первоначального опорного плана дельта-методом.
4.1 Построение математической модели транспортной задачи
Некоторый однородный продукт, сосредоточенный у трёх поставщиков Ai с
заданной матрицей запасов аi= (40,25,35),необходимо доставить четырём
потребителям Bj с матрицей потребностей bj =(30,40,10,20) единиц. Известна
таблица стоимостей Cij перевозки единицы груза от i-го поставщика к j-му
потребителю:
В1
В2
В3
В4
запасы
ai
А1
3
2
4
7
40
А2
2
6
8
1
25
А3
5
4
7
2
35
потребности
bj
30
40
10
20
100
Необходимо составить план перевозок, позволяющий вывезти все грузы,
полностью удовлетворить все потребности и имеющий минимальную стоимость.
Получим следующую математическую модель задачи.
Найти наименьшее значение линейной функции:
Z =
при ограничениях
, i = 1, ...,3,
, j = 1,...,4 ,
xij ? 0 ( j = 1,..., 4; i = 1,..., 3).
В рассмотренной модели суммарные запасы равны суммарным потребностям:
(100=100)
значит, мы имеем закрытую модель.
4.2 Построение первоначального опорного плана
дельта-методом.
Таблица 1.
Потреб.
Поставщ.
В1
В2
В3
В4
запасы
ai
i
min
ij
отмеч.
столб.
V
V
V
А1
3
1
- 2
0
40
4
0
10
7
6
40
-10
А2
2
0
30
6
4
8
4
1
0
25
-5
А3
5
3
2
+ 4
2
1
7
3
2
2
1
0
20
35
+15
1
потребности
bj
30
40
10
20
100
Выполняем пункты 1-7 алгоритма. Получим новое закрепление ; т.к.
в п.7 алгоритма выполняется условие а) то производим непосредственное
перераспределение груза из А1В2 в А3В2 . Размер груза равен min(40;10)=10. Новое
закрепление выписано в таблице 2.
Таблица 2.
Потреб.
Поставщ.
В1
A2
В3
В4
запасы
ai
i
min
ij
отмеч.
столб.
V
А1
+ 3
1
- 2
0
30
4
0
10
7
6
40
0
1
А2
- 2
0
30
6
4
8
4
1
0
25
-5
А3
5
3
2
+ 4
2
1
10
7
3
2
2
1
0
20
35
+15
2
потребности
bj
30
40
10
20
100
Заново прогоняем алгоритм , начиная с п.4 ; в п. 7 алгоритма у нас выполняется
условие в) , значит строим цепочку :
А2В1- А1В1- А1В2- А3В2=-0+1-0+1=2 ;
А2В1- А1В1- А1В3- А3В3=-0+1-0+2=3 ;
Первая цепочка имеет меньшее приращение стоимости, поэтому выбираем её.
Новое перераспределение выписано в таблице 3.
Таблица 3.
Потреб.
Поставщ.
A1
В2
В3
В4
запасы
ai
i
min
ij
отмеч.
столб.
А1
+ 3
1
5
- 2
0
25
4
0
10
7
6
40
0
А2
- 2
0
25
6
4
8
4
1
0
25
0
А3
5
3
2
+ 4
2
1
15
7
3
2
2
1
0
20
35
0
потребности
bj
30
40
10
20
100
В результате получим первоначальный опорный план со стоимостью Z= =
255 единиц.
Построим систему потенциалов для этого плана:
u1+v1=3 пусть u1=0 v1=3 u1+v4 =0 7
u1+v2=2 u2=-1 v2=2 u2+v2 =1 6
u1+v3=4 u3=2 v3=4 u2+v3 =3 8
u2+v1=2 v4=0 u2+v4 =-1 1
u3+v2=4 u3+v1 =5 5
u3+v4=2 u3+v3 =6 7
Построенная система потенциалов показывает, что полученный план является
оптимальным .
5.Описание программы
Программа transd написана на языке Паскаль (компилятор фирмы Borland -
Borland Pascal 7.0), служит для получения первоначального опорного плана
решения транспортной задачи дельта-методом с последующей проверкой на
оптимальность методом потенциалов.
Для хранения данных в памяти используется ее динамическое выделение
(процедура GetMData), максимальный размер блока памяти для программ,
выполняющихся в реальном режиме MS-DOS, составляет 64 Kb, поэтому
размерность массива из переменных типа integer (двухбайтовое знаковое целое)
максимально может быть равна 32767, - именно такое количество клеток перевозок
может содержать задача, разрешаемая с помощью программы transd, это
позволяет решить задачу, например, со 128 потребителями и 256 поставщиками,
единственным неудобством будет то, что таблицы не будут умещаться на экране
(но будут сохранены в файле - протоколе).
Освобождение памяти производится при помощи процедуры ClearData , запись
- процедурой WriteData.
При вводе данных используется процедура InputData . Процедуры FindMinCol и
FindMinStr находят минимальные приращения в столбцах и строках и отправляют
разности приращений в таблицу .
Analyz отмечает столбцы с занятыми клетками в избыточных строках .
Перераспределение по цепочке производится процедурой Direct CalcString .
Память для двухмерного массива стоимостей выделяется в виде одномерного
массива. Например матрица C размерностью m?n занимает в памяти m?n?SizeOf
(Integer) байт памяти. Доступ к элементу с координатами (i ; j) осуществляется как
C^ ?Pred(i)?n+j?. Данное неудобство обусловлено тем, что программа transd может
решать достаточно большие транспортные задачи. Кроме того динамически
выделяется память под вспомогательные массивы, хранящие временно
необходимые данные.
После ввода данных осуществляется запись данных на диск, при этом
используется файловая переменная A: типа file. Запись данных на диск
реализована в процедуре WriteData обратная ей процедура ReatData (считывание
ранее записанных данных) вызывается при выборе пункта меню 2 - Старые данные.
После выбора в меню режима работы и ввода данных
производится разрешение задачи с выводом промежуточных данных на экран (все
выведенные на экран таблицы дублируются в файле - протоколе). Для этого
служит процедура Out, которой передается строковой параметр для вывода
пояснений над таблицей. Процедура Out вызывает описанную в ней процедуру
OutTable, которая собственно и выводит таблицу на экран либо в файл (в
зависимости от того с каким файловым именем связана переменная TXT : ?
trans000.txt?? либо пустым именем, что соответствует выводу на экран).
Для удобства вывода числовых данных предусмотрены 2 функции: Bute2Str
(преобразование целого типа Bute в строку) и Int2Str (преобразование Integer в
строку).
После закрепления поставщиков за потребителями осуществляется расчет
потенциалов строк и столбцов.
Потенциал строки с наибольшим количеством занятых клеток принимается за 0.
Далее для нахождения потенциалов применяется перекрестная рекурсия.
Процедура Calc V (просчитывает потенциалы столбцов V по занятым клеткам
строки, номер которой передан процедуре) вызывает процедуру Calc U
(просчитывает потенциалы строк U по занятым клеткам столбца, номер которого
передан процедуре), к которой применено форвардное описание (директива
forward) и наоборот процедура Calc U вызывает процедуру Calc V. Это
продолжается до тех пор, пока все потенциалы не будут рассчитаны.
Список использованной литературы:
1. Ю. Н. Кузнецов В. И. Кузубов А. Б. Волощенко
"Математическое программирование"
2. Е. Г. Гольштейн Д. Б. Юдин
"Задачи линейного программирования транспортного типа"
3. В. С. Немчинолова
"Методы и алгоритмы решения транспортной задачи"
4. Ю. Н. Кузнецов
" Линейного программирования "
1
| |
