«Метод Фогеля Delphi»

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

1.2 Описание и анализ математической модели

В поставленной задаче обозначив через хij количество единиц груза, запланированных к перевозке от i-го поставщика к j-му потребителю, сведём задачу в так называемую матрицу планирования, представленную в таблице 1.1

Таблица 1.1

Поставщики Потребители Запасы

B1 … Bj … Bn

A1

x11 x1j x1n a1

c11 … c1j … c1n

… … … … … … …

Ai

xi1 xij xin ai

ci1 … cij … cin

… … … … … … …

Am

xm1 xmj xmn am

cm1 cmj cmn

Потребности

b1 … bj … bn ai

bj

Тогда математическая формулировка транспортной задачи сводится к минимизации линейной формы

(1.1)

при ограничениях:

ограничение по запасам:

(1.2)

ограничение по потребностям:

(1.3)

xij0 (1.4)

Различают задачи с закрытой моделью, когда ai=bj и открытой моделью, когда aibj, т.е. баланс между запасами и потребностями отсутствует.

Необходимым и достаточным условием разрешимости транспортной задачи является равенство суммарных запасов суммарным потребностям, т.е.

(1.5)

Если , то вводят фиктивный (n+1)-й пункт назначения с потребностью и полагают ci,n+1=0, .

Если , то вводят фиктивный (m+1)-й пункт отправления с запасами и принимают cm+1,j=0, .

Основные особенности транспортной задачи:

1) ограничения заданы в виде равенств;

2) каждая неизвестная входит лишь в 2 уравнения;

3) коэффициенты при неизвестных равны 1.

И хотя транспортная задача относится к задачам линейного программирования, в связи с вышеперечисленными особенностями для её решения созданы специальные алгоритмы.

Решение транспортной задачи разбивается на 2 этапа:

1) Определение начального опорного плана.

2) Улучшение опорного плана.

Опорный план называется невырожденным, если содержит ровно (m+n-1) перевозку. Если перевозок меньше, чем m+n-1, то это вырожденный опорный план.

Для решения транспортной задачи используют различные методы, такие как: метод северо-западного угла, метод минимальной стоимости, метод Фогеля и метод потенциалов.

В данном курсовом проекте для решения транспортной задачи используется метод минимальной стоимости, а оптимизация опорного плана производиться методом потенциалов.

Был выбран метод потенциалов, т.к. этот метод производит улучшение опорного плана.

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

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

Алгоритм метода потенциалов.

1) Любым методом построить опорный план, убедиться, что он невырожденный.

2) Каждому поставщику Ai поставить в соответствие некоторый потенциал ui, а каждому потребителю Bj – потенциал pj.

3) Для каждой перевозки опорного плана составить сумму потенциалов, приравнять её к стоимости перевозки: ui+ pj=сij. Таким образом будет получена система (m+n-1) уравнений с (m+n) неизвестными. Такая система имеет бесконечное множество решений.

4) Выделить одно из возможных решений системы, присвоив любому из неизвестных произвольное значение. Из полученных значений потенциалов составить матрицу :

5) Вычислить max( - cij). Если max( - cij)=0, то вычисления прекращаются и последний план является оптимальным. В противном случае в ячейку, соответствующую максимальной разности, ввести перевозку Q>0. Чтобы не нарушился баланс перевозок, нужно отнять и прибавить Q в строках и столбцах так, чтобы по стокам и столбцам суммы Q были равны 0.

6) Выписать все разности, содержащие Q и присвоить Q значение наименьшего из уменьшаемых. Пересчитать опорный план с учётом полученного значения Q, проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки. При этом стоимость перевозки в каждой следующей таблице не должна превышать стоимости из предыдущей таблицы.

7) Убедиться, что опорный план невырожден (или привести его к невырожденному виду) и перейти к п.2.

По окончании расчётов проверить правильность размещения перевозок в соответствии с отграничениями по запасам и по потребностям, посчитать стоимость перевозки.

Пример решения транспортной задачи методом Фогеля представленный в таблице 1.2

Таблица 1.2

1.3 Обоснование выбора инструментальных средств

Для написания программы, позволяющей решить данную проблему, был выбран язык Delphi (а именно Borland Delphi 7.0). Причины такого выбора представлены ниже:

• Delphi - один из самых распространенных языков программирования (наряду с несколькими другими) и является языком высокого уровня.

• Delphi имеет очень мощную модель объектно-ориентированного программирования.

• В высших учебных заведениях и колледжах очень популярен язык Delphi, так как он является модернизированным «потомком» языка Pascal, широко применяемого во многих школах и лицеях, в качестве обучающего языка программирования.

• Создаваемые с его помощью программы могут работать не только под управлением Windows, а сама она относится к классу инструментальных средств ускоренной разработки программ.

• Визуальное конструирование форм избавляет программиста от многих аспектов разработки интерфейса программы, так как Delphi автоматически готовит необходимые программные заготовки и соответствующий файл ресурсов. Программист использует специальное окно, которое называется окном формы, как прототип будущего окна программы и наполняет его компонентами, реализующими нужные интерфейсные свойства (разного рода списки, кнопки, полосы прокрутки и т.п.). После размещения на форме очередного компонента, Delphi автоматически вставляет в связанный с формой модуль ссылку на компонент, и корректирует специальный файл описания формы с расширением DFM, который после компиляции преобразуется в ресурсный файл Windows.

• Использование компонентов не только во много раз сокращает сроки разработки программ, но и существенно снижает вероятность случайных ошибок, от которых, увы, не защищен ни один крупный программный проект. Однако в их применении есть оборотная сторона. Как правило, даже простые в функциональном отношении компоненты представляют лишь «вершину айсбергов» так как они создаются по объектно-ориентированной технологии и многие их функциональные черты наследуются от многочисленных родительских компонентов. В результате даже несложные программы, созданные в Delphi, редко имеют объем меньше сотен килобайт.

• Во всех случаях Delphi имеет самый быстрый среди продуктов подобного рода оптимизирующий компилятор, позволяющий создавать быстрые и относительно компактные программы.

2 Технологическая часть

2.1 Назначение и цель создания

Главной задачей было изучение темы «Решение транспортной задачи методом Фогеля». Задача была предложена в качестве темы для курсового проекта по предмету «Моделирование производственных и экономических процессов». Так же целью создания программы было практическое закрепление навыков программирования и изучение языка Delphi.

2.2 Требование к системе

2.2.1 Требования к функциям системы

Программа предназначена для использования на ПК.

Для выполнения корректной работы этой программы необходимы:

1) Процессор не ниже Pentium 2;

2) Операционная система Windows 95, 98, 2000, XP;

3) Оперативная память не меньше 125 Мб;

4) Клавиатура, мышь;

5) Цветной монитор SVGA.

2.2.2 Требования к интерфейсу пользователя

Требования, предъявляемые к интерфейсу пользователя, приведены ниже:

• Программа содержит несколько рабочих форм, на которых расположены все функциональные элементы, что очень удобно и просто.

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

• В данной программе была создана детальная, предельно понятная справочная система, которая описывает все этапы работы с программой, от введения исходных значений, до выхода из программы.

2.2.3 Требования к защите информации

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

2.3 Перечень и описание входных данных

В качестве входных данных для программы выступают следующие элементы:

1) Количество поставщиков

2) Количество потребителей

3) Количество запасов и потребностей

4) Стоимости перевозок