Разработка программы на Delphi для решения транспортной задачи - Программирование, компьютеры и кибернетика курсовая работа

Главная

Программирование, компьютеры и кибернетика
Разработка программы на Delphi для решения транспортной задачи

Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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


1. Выбрать и обосновать наиболее эффективный метод решения задачи.
2. Разработать алгоритм и программу для решения задачи в общем виде.
3. Проверить правильность алгоритма на предлагаемой задаче.
Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000,2000,1600 т каждому. Расстояние от элеватора до хлебозаводов указано в следующей таблице:
Затраты на перевозку 1 т продукта на 1 км составляют 25 д.е.
Спланируйте перевозки зерна из условия минимизации транспортных расходов.
1. Проверить на сбалансированность.
Транспортная задача является сбалансированной, если суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. .
Если суммарные запасы поставщиков превосходят суммарные запросы потребителей, т.е. то необходимо ввести фиктивного (n+1)-го потребителя с запросами равными разности суммарных запасов поставщиков и запросов потребителей, и нулевыми стоимостями перевозок единиц груза;
Найдем начальное решение методом наименьшего элемента, который позволяет построить опорное решение, достаточно близко к оптимальному.
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы.
Данный метод позволяет построить опорное решение, которое достаточно близко к оптимальному, так как использует матрицу стоимостей транспортной задачи , i=1,2,…,m; j=1,2…,n. Данный метод состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости , и исключается из рассмотрения только одна строка(поставщик) или один столбец (потребитель). Очередную клетку, соответствующую , заполняют также. Поставщик исключается из рассмотрения, если его запасы заканчиваются. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик не исключен, но его запасы равны нулю, то на том шаге, когда от него требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь затем поставщик исключается из рассмотрения. Аналогично поступают с потребителем;
2. Проверить полученный опорный план на невырожденность.
План называется вырожденным, если количество базисных клеток в нем меньше, чем m + n - 1.Опорный план - невырожден, если число ненулевых перевозок равно n+m-1, поэтому и первоначальный план также должен удовлетворять этому требованию;
3. Найти потенциалы опорного решения.
Метод потенциалов предназначен для окончательной оптимизации решения транспортной задачи.
Если допустимое решение , i=1,2,…,m; j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков i=1,2,…,m и потребителей j=1,2,…,n, удовлетворяющее следующим образом:
Группа равенств (2.1) используется как система уравнений для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных i=1,2,…,m и j=1,2,…,n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.
Группа неравенств (2.2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде:
Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.
Опорное решение является оптимальным, если для всех векторов условий (клеток таблицы) оценки неположительные.
Оценки для свободных клеток транспортной таблицы используются при улучшении опорного решения. Для этого находят клетку (l,k) таблицы, соответствующую . Если , то решение оптимальное. Если же , то для соответствующей клетки (l,k) строят цикл и улучшаю решение, перераспределяют груз по этому циклу;
Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов:
Так как ? A i > ? B i , то вводим «Фиктивный» пункт потребления - хлебозавод №4 с потребностью в зерне :
B4 = ?A i - ?B i = 5400 - 4600 = 800 т. и с нулевыми расстояниями до элеваторов.
Занесем исходные данные в распределительную таблицу.
2 Отыщем начальное решение. Методом минимального элемента.
Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
3 Проверим полученный опорный план на невырожденность.
Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 5. Следовательно, опорный план является невырожденным.
4 Найдем потенциалы опорного решения.
U i , V i . по занятым клеткам таблицы, в которых U i + V i = С ij , полагая, что u 1 = 0;
Получим v 1 =20; v 2 =30; v 3 =50; v 4 =0; u 2 = -10
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию U i + V i <= С ij .
Q = 20*1000 + 30*800 + 50*1600 + 0*800 + 20*1200 = 148000 тон/км.
Так как затраты на перевозку 1 т продукта на 1 км составляют 25 д.е., то денежные затраты составляют:
Как видно из решения программы грузооборот составит:
Рассчитаем перевозки зерна из условия минимизации транспортных расходов.
Так как затраты на перевозку 1 т продукта на 1 км составляют 25 д.е., то денежные затраты составляют:
- количество неизвестных (decision variable) - 200;
- количество формульных ограничений (explicit constraint) на неизвестные - 100;
- количество предельных условий (simple constraint) на неизвестные - 400.
Для решения данной транспортной задачи будем проводить MSExcel 2007. Запустим файл «TZ.xlsm». После запуска файла нужно включить макросы «Параметры» => «Включить содержимое» (см. рисунок 4).
По умолчанию в MSExcel 2007 надстройка «Поиск решения» отключена. Чтобы активизировать ее необходимо перейти на вкладку «Пуск », нажать кнопку «Параметры Ecxel» => «Надстройки» и установить флажок рядом с пунктом «Поиск решения». Нажать «ОК» (см. рисунок 5).
Далее переходим к вводу данных задачи.
В ячейки «E7-G8» вводим расстояния до хлебозаводов, в ячейки «E12-G12» вводим потребности хлебозаводов, в «I7;I8» вводим запасы в элеваторах и в ячейку «F26» вписывается значение затрат на 1 единицу. В ячейки «H7» и «H8» вставляем нули, так как данная задача несбалансированна и запасы превышают потребности и вводится фиктивный потребитель, ячейка «H12» считается автоматически, как только будут заполнены ячейки с потребностями и запасами «=(I7+I8)-(E12+F12+G12)» (см. рисунок 6).
На вкладке «Данные» нажимаем надстройку «Поиск решения» (см. рисунок 7).
Устанавливаем целевую ячейку «F28», так как нам нужно найти минимальные затраты ставим галочку на «Минимальное значение»
Расчеты и изменения будут происходить в ячейках «E18-H19», поэтому и указываем эти ячейки в графе «Изменения ячейки»
В ячейках «E18-H19 »введем параметр > 0, так как оптимальный план не может иметь отрицательных значений.
Рис.7 Параметры функции «Поиск решения»
После того, как выставлены все ограничения, нажимаем на кнопку «Выполнить». Программа рассчитает оптимальный грузооборот и выведет его в ячейку «F28». А в ячейку «H28» будут минимальные расходы на грузоперевозки (см. рисунок 8).
Если необходимо изменить исходные данные и пересчитать целевую функцию - можно воспользоваться макросом для поиска решения, нажав на сочетание клавиш Alt+F8 выполнить «Makros1».
Как видно из ячейки «F28» грузооборот составит:
А в ячейке «H28» рассчитаются денежные затраты :
Программа реализует интуитивно понятный интерфейс и разработана для решения, как транспортной задачи заданного условия варианта, так и для решения транспортных задач с другими исходными данными, удовлетворяющих условиям программы. Оболочка программы реализована на Delphi, однако расчеты производятся в файле Excel, выполненном ранее.
Программные и аппаратные требования.
Microsoft Windows XP, Windows 7, Windows 8,Server 2003, Server 2008) или более поздняя версия
Необходимо скопировать файлы «TZ.xlsm» и «Var16.exe» в одну папку.
Для корректной работы программы нужно запустить «TZ.xlsm». По умолчанию в MSExcel 2007 надстройка «Поиск решения» отключена. Чтобы активизировать ее необходимо перейти на вкладку «Пуск », нажать кнопку «Параметры Ecxel» => «Надстройки» и установить флажок рядом с пунктом «Поиск решения». Нажать «ОК» (см. рисунок 9).
После чего перейти на вкладку «основные» активировать для показа на ленте вкладку «Разработчик» (см. рисунок 10).
Еще в «центре обеспечения безопасностью» нажать «Параметры безопасности» (см. рисунок 11).
В параметрах макросов включить все макросы и доверить доступ VBA (см. рисунок 12).
Также потребуется добавить компонент «Solver» перейдя во вкладку «Разработчик» => «Visual Basic» => «Tools» => «Reference» (см. рисунок 13).
Рис.13 Включение компонента «Solver»
Файл «TZ.xlsm» использует следующий макрос:
SolverOk SetCell:="$F$28", MaxMinVal:=2, ValueOf:="0", ByChange:="$E$18:$H$19"
Далее запускаем программу «Var16.exe». Появляется окно с заполненными данными согласно варианту: поставщики (Элеватор 1, Элеватор 2) их запасы, потребители (Хлебозавод 1, Хлебозавод 2, Хлебозавод 3) их потребности и затраты на 1 единицу (см. рисунок 14).
При нажатии на кнопку «Считать» программа произведет расчеты и будет выведен результат в строку «Оптимальный грузооборот» и «Минимальные затраты». Так же рассчитается оптимальный план перевозок (см. рисунок 15).
В программе предусмотрена возможность ввода других данных: расстояний, потребностей, запасов и затрат на 1 единицу. Для верного вычисления результатов должно соблюдаться условие - сумма всех запасов должна быть больше, чем сумма всех потребностей. Если условие не выполнится, то при нажатии на кнопку «Считать» появиться ошибка (см. рисунок 16).
При нажатии на кнопку «Выход» будет выполнен выход их программы. И при ее следующем запуске будут введены начальные данные из условия задачи.
Как видно из решения данной задачи оптимальный грузооборот составит:
А минимальные денежные затраты составят:
В программе используются следующие компоненты:
Button- простая командная кнопка, используется для реализации в программе команд с помощью обработчика события OnClick этого компонента.
Label предназначен для отображения статического текста, то есть надписей и меток на Форме.
Edit представляет собой однострочное текстовое поле, служащее для ввода данных пользователем.
Memo - простой текстовый редактор. Memo позволяет вводить многострочный текст с клавиатуры, загружать его из файла, редактировать и сохранять в файл текстового формата.
Переменные в модуле были задействованы
ap: variant. Переменная Ap - ссылка объекта, возвращенная функцией 'Excel.Application'
Функция возвращает ссылку на объект, представляющий собой переменную типа variant
Тип Variant обеспечивает гибкий универсальный тип данных
procedure TForm1.FormCreate(Sender: TObject);
filename:string - переменная filename связывает путь и имя файла
Эта процедура выполняется сразу же после открытия формы и идет заполнение данных согласно варианту.
Memo1.Lines.Add ('Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000,2000,1600 т каждому. Расстояние от элеватора до хлебозаводов указано в таблице. Затраты на 1т/км - 25 д.е');
Присвоение плану перевозок и ячеек с ответами значение «0»
Создается единичный OLE объект. И программа открывает Excel файл, который производит все вычисления
Ap := CreateOleObject('Excel.Application'); Функция возвращает ссылку на объект, представляющий собой переменную типа variant. Результатом выполнения данной процедуры будет запуск приложения Excel на выполнение.
filename:=ExtractFilePath(Application.ExeName)+'\TZ.xlsm';
ExtractFilePath - Извлекает из полного имени файла исполняемый файл.
procedure TForm1.Button1Click(Sender: TObject);
переменные zap,pot: real - для записывания результата суммы запасов, и суммы потребностей.
Процедура нажатия на кнопку считать. Сразу после нажатия выполняется условие проверки на баланс. Если сумма запасов больше или равна сумме потребностей, то программа продолжит выполнение дальше. А если сумма запасов меньше сумме потребностей программа выдаст ошибку.
zap:=strtofloat(edit9.Text)+strtofloat(edit10.Text);
pot:=strtofloat(edit14.Text)+strtofloat(edit15.Text)+strtofloat(edit16.Text);
if (zap>=pot) then - условный оператор выполняющий условие
MessageBox(0,'Задача не может быть решена','Ошибка', MB_OK);
После проверки на баланс и при выполнении условия происходит записывание данных из программы в Exel файл
Ap.Range['E7']:=strtofloat(Edit1.Text);
Ap.Range - для задания объекта, ассоциированного с областью ячеек.
Ap.run('makros1')- Непосредственное выполнение макроса.
После вычислений происходит считывание данных из Exel файла и запись готовых ответов в программу.
procedure TForm1.Button2Click(Sender: TObject);
Ap.DisplayAlerts := False - отмена запроса о сохранении Exel файла
Ap.Workbooks.close - Закрытие рабочей книги
Ap.Application.Quit - Закрытие Exel файла
Application.Terminate - Закрытие программы
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
В этой процедуре при нажатии на крестик происходит закрытие программы и Exel файла.
Ap.DisplayAlerts := False - отмена запроса о сохранении Exel файла
Ap.Workbooks.close - Закрытие рабочей книги
Ap.Application.Quit - Закрытие Exel файла
Application.Terminate - Закрытие программы
1. Данилин Г.А. Математическое программирование с EXCEL: Учебное пособие для студентов всех специальностей МГУЛа / Г.А. Данилин, В.М. Курзина, П.А. Курзин и др. - М.: МГУЛ. 2005.
2. Корняков В.Н. Программирование документов и приложений MS Office в Delphi. -- СПб.: БХВ-Петербург, 2005. - 496 с : ил.
3. Таха, Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. -- М.: Издательский дом "Вильяме", 2005. -- 912 с: ил.
Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7. курсовая работа [1000,7 K], добавлен 23.06.2012
Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения. курсовая работа [2,0 M], добавлен 12.02.2013
Написание программы для работы с клиентами средствами языка Delphi, которая предусматривает ввод, редактирование и удаление информации. Разработка алгоритма решения задачи, описание переменных, вспомогательных процедур, входных и выходных данных. курсовая работа [355,7 K], добавлен 21.09.2010
Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи. курсовая работа [713,3 K], добавлен 19.10.2012
Задачи, решаемые методом динамического программирования. Основные этапы нахождения деревянного алгоритма решения задачи. Выполнение алгоритма Прима. Построение Эйлерового цикла. Решение задач средствами Excel. Алгоритм основной программы - Derevo. курсовая работа [586,3 K], добавлен 04.04.2015
Оптимизация затрат на доставку продукции потребителям. Характеристика транспортной задачи, общий вид решения, обобщение; содержательная и математическая постановка задачи, решение с помощью программы MS Excel: листинг программы, анализ результатов. курсовая работа [514,8 K], добавлен 04.02.2011
Решение задачи средствами Паскаль и блок-схемы выполненных процедур, составление программы. Результаты решения задачи по перевозке грузов. выполнение задачи средствами MS Excel, создание таблиц. Порядок и особенности решения задачи в среде MathCAD. курсовая работа [2,5 M], добавлен 27.02.2011
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Разработка программы на Delphi для решения транспортной задачи курсовая работа. Программирование, компьютеры и кибернетика.
План Написания Сочинения Огэ 15.3
Курсовая Работа На Тему Методичні Питання Розрахунку Цін На Товари В Умовах Ринку
Курсовая Работа На Тему Необходимость И Сущность "Бивалютной Корзины"
Реферат по теме Russia and the international economy
Курсовая работа: Управление рисками в инновационной деятельности
Социальные Функции Физической Культуры И Спорта Реферат
Реферат: Letter Living Conditions Of England In
Реферат: Билеты по философии (БрГТУ)
Контрольная Работа По Немецкому 7
Диссертация Уголовно Исполнительное Диссертация
Реферат: Понятие об ощущениях
Курсовая работа по теме Анализ структуры и текучести кадров ОАО 'Иркутскэнерго'
Почему Люди Боятся Перемен Сочинение Вывод
Реферат: Современный художник Солдатенко Андрей
Сочинение На Тему Герой Труда 5 Класс
Эссе Традиции
Реферат по теме Имена прилагательные, характеризующие внешность человека по физическим особенностям, в ярославских говорах
Ответ на вопрос по теме шпоры
Реферат по теме Процесс принятия внешнеполитических решений: Деятельность СНБ в период администрации Дж Буша
Курсовая работа по теме Проектирование привода к пресс-валкам
Результаты маркетингового исследования рекламной деятельности компании ООО "Промклимат" - Маркетинг, реклама и торговля контрольная работа
Эмбриональное развитие - Биология и естествознание реферат
Специфика теории и практики управления в СССР - Менеджмент и трудовые отношения курсовая работа