Описание алгоритма реализации модели

 

Определившись с методами, которые мы будем использовать в решении задачи, приступим к непосредственному получению результата. Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ “Метод ограничений”/ Условия транспортной задачи заданы транспортной таблицей (2.1).

 

Таблица 2.1 - Условие транспортной задачи

ai/ bj		B1	B2	B3	B4
		25	25	15	25
A1	40	10	15	5	5
A2	30	10	12	6	6
A3	30	5	5	3	2

 

В данном случае Σa_i=100 = Σb_j=100 имеем дело с закрытой моделью транспортной задачи.

Вводим количество поставщиков и потребителей, затем строим матрицу элементы которой отображают стоимость перевозки. Если задача по условию не является сбалансированной, то для этого добавляем фиктивный пункт производства и потребителя. В нашем случаи задача является сбалансированной, для ее решения строим матрицу Х_ij - план перевозок_. Элементы этого типа характеризуют количество товаров, которое будет перемещаться от i-го поставщика к j-му потребителю. Выводим целевую функцию (см рисунок 2.1)

Рисунок 2.1 - блок-схема подпрограммы проверки на условие баланса.

Происходит начальное вычисление опорного плана.

Построение плана выполняется сверху-вниз по столбцам матрицы Co начиная с левого, для O матрицы Co, при этом учитывается пропускная возможность коммуникаций.

На этапе разметки отмечают символом "+" столбцы с нулевыми невязками и существенные нули матрицы С. Точкой отмечают существенные неполные нули, а двумя точками - полные. Несущественные нули остаются без разметки. С точки зрения коммуникации они являются неполными.

Целью поиска является отыскать неполный нуль (без разницы существенный или несущественный), расположенный в строке с полной невязкой. Алгоритм поиска по колонкам известен.

Элемент который стоит на пересечении выделенной строки и выделенного столбца называется дважды выделенным.

Выбирается корректирующий элемент h. Корректирующий элемент получаем как минимальный положительный элемент среди невыделенной части матрицы, либо как минимальный модуль двух выделенных отрицательных элементов

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

Прибавляется h к выделенным элементам и вычитается из невыделенных. Если дважды выделенный элемент становится равным нулю, то его выделяют "*"Знак выделения над столбцом снимается.

Рисунок 2.2 - Общий алгоритм вычисления опорного плана

 

Вычисление невязки.

На основании матрицы С₀ строится начальный план. Заполнение плана осуществляется по нулям матрицы С₀, двигаясь по столбцам сверху вниз, слева направо.

После заполнения элемента плана объемы производства и потребления корректируются. Коррекции предшествует построение цепочки. Цепочка содержит обязательно нечетное число нулей и в принципе может состоять из одного нуля. Построение цепочки начинается с последнего найденного нуля со штрихом. Затем по столбу к нулю со звездочкой, а уже от него по строке к нулю со штрихом. Для коррекции плана выбирается корректирующий элемент _. Он выбирается из невязки строки сначала, из невязки конца цепочки и элементов конца Х, соответствующих нулям со звездочкой, которые вошли в цепочку. Элемент  прибавляется к элементу Х_ij, если ему в цепочку соответствовал элемент С_ij =0', и отнимается от элемента Х_ij, если в цепочке ему соответствовал элемент С_ij =0^*. Для коррекции плана рассчитывается невязка по строкам и столбцам, а так же суммарная невязка.

Рассчитываются невязки по столбцам и строкам.

 

Невязка по строке , i=1,m, j=1,n (2.19)

Невязка по строке , i=1,m, j=1,n (2.20)

 

Затем рассчитывается суммарная невязка плана

 

∆ (2.21)

 

Если суммарная невязка плана = 0, то это говорит о получении оптимального решения. Если  не равно 0, то переходим к этапу разметки. Выводим L - общая стоимость перевозок (см рисунок 2.3).

 

Рисунок 2.3 - блок - схема подпрограммы вычисления невязки.

Описание программы.

Описание работы программы:

пользователь вводит количество поставщиков и потребителей;

пользователь вводит все данные о поставщиках и потребителях;

пользователь вводит ограничения;

строит матрицу С_ij, элементы которой отображают определенную скидку;

Все используемые в программе переменные и подпрограммы, кратко описаны в таблицах 2.1

Описание блок-схемы:

блок-схема проверка на условие баланса представлена на рисунке 2.1;

блок - схема общего алгоритма вычисления опорного плана представлена на рисунке 2.2;

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

 

Таблица 2.1 -Используемые переменные

Имя	Тип	Описание
Cont	TZLPTableContext	В каждой конкретной библиотеке будет свой тип контекста
Значение функции	Integer	Код возврата: ResultError = - 1 - ошибка в алгоритме; ResultFinish = 0 - успешное окончание расчетов; ResultNoSolution = 1 - нет решения;
SourceF	TFunction	Целевая функция
Limitations	TLimitations	Ограничения
MinMax	TFunctionType	Функция на минимум или максимум. ftMin - минимум; ftMax - максимум.
Len	Integer	Длина массива ограничений
Factors	TDynIntegerArray	Массив ограничений: последовательность из Len целых чисел (Integer)
Значение функции	TIntegerMatrix	матрица из целых чисел

 

123	Поделиться:

Воспользуйтесь поиском по сайту: