«Метод Фогеля Delphi» - Курсовая работа

Содержание

Введение 4

1 Аналитическая часть 5

1.1 Описание и постановка задачи 5

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

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

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

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

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

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

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

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

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

2.4 Руководство к использованию и эксплуатации 10

2.5 Результаты экспериментальной проверки 14

3 Охрана труда и техника безопасности 15

Заключение 17

Список литературы 18

Приложения А Текст программы 19

Введение

Исторически математическая экономика началась с моделей простого и расширенного воспроизводства. В них отражались потоки денег и потоки товаров и продуктов. Это, например, модель Ф. Кенэ. Позднее эти модели подробно и более глубоко изучались в экономической кибернетике - здесь можно указать на работы О. Ланге. Рассмотрены схемы денежных и материальных потоков, обеспечивающих простое и расширенное воспроизводство, их идентификацию, модели математической статистики. Далее возникли концепции производственных функций, предельных и маргинальных значений, предельных полезностей и субъективных полезностей. Дальнейшее развитие - в рамках линейного и выпуклого программирования, выпуклого анализа, развитие тонких техник моделирования: имитационное моделирование, экспертные системы, нейронные сети.

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

Выдержка из текста работы

1 Аналитическая часть

1.1 Описание и постановка задачи

Транспортная задача – это задача о наиболее экономном плане перевозок однородного продукта из пунктов производства (станций отправления) в пункты потребления (станции назначения).

Общая формулировка.

Некоторый однородный продукт производится в m пунктах производства A1, А2,…,Am. Задан объём производства ai пункта Ai ( ). Произведённый продукт должен быть перевезён в n пунктов потребления B1, B2, …,Bn. Известен спрос bj пункта Bj ( ). Заданы также транспортные издержки Cij, связанные с перевозкой единицы продукта из пункта Ai в пункт Bj. Требуется составить план перевозок, обеспечивающий при минимальных транспортных расходах удовлетворение спроса всех пунктов потребления за счёт продукта, произведённого во всех пунктах производства.

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) Стоимости перевозок

Заключение

В процессе выполнения курсового проекта была написана программа для решения транспортной задачи методом Фогеля, с использованием ЭВМ. Был глубоко изучен язык программирования DELPHI, многие его компоненты и закреплены навыки объектно-ориентированного программирования. Так же была изучена тема «Решение транспортной задачи методом Фогеля».

Курсовой проект состоит из двух частей – пояснительной записки, в корой рассмотрены все теоретические сведения, и программы, позволяющей автоматизировать процесс построения опорного плана методом Фогеля.

Список литературы

. Исследование операций под редакцией Кремера

2. А.И. Ларионов, А.В. Юрченко – Экономико-математические методы в планировании

3. Н.Ш. Кремер - Математическое моделирование и модели в планировании

4. С. Вентцель - Исследование операций

5. А. Калихман - Сборник задач по математическому программированию

6. Н.А.Осадчая – Моделирование производственных и экономических процессов, курс лекций, колледж ВКГТУ, Усть-Каменогорск, 2007 / с.

7. Гофман В.Э., Мещеряков Е., Никифоров В.В., Хомоненко А.Д. Delphi 7 в подлиннике;

8. Баженова И.Ю. Delphi 7: Самоучитель программиста;

9. Белов В.В., Чистякова В.И. Программирование в Delphi: процедурное, объектно-ориентированное;

10. А.Н. Вальвачев, К.А. Сурков, Д.А. Сурков, Ю.М. Четырько. Программирование на языке Delphi. Учебное пособие. — 2005.;

11. Фленов Михаил - Библия Delphi 2007