Моделирование транспортной задачи

 

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 5) = 10. Прибавляем 10 к объемам грузов, стоящих в плюсовых клетках и вычитаем 10 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

Таблица 25 - решение 2-ой задачи

 

	1	2	3	4	5	6	Запасы
1	1[35]	2[10]	3	2.5	3.5	0[5]	50
2	0.4[5]	3	1[15]	2	3	0	20
3	0.7	1[35]	1	0.8	1.5[40]	0	75
4	1.2	2[5]	2	1.5[75]	2.5	0	80
Потребности	40	50	15	75	40	5

 

2. Проверим оптимальность опорного плана. Найдем потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

 

Таблица 26 - решение 2-ой задачи

 

	v1=1	v2=2	v3=1.6	v4=1.5	v5=2.5	v6=0
u1=0	1[35]	2[10]	3	2.5	3.5	0[5]
u2=-0.6	0.4[5]	3	1[15]	2	3	0
u3=-1	0.7	1[35]	1	0.8	1.5[40]	0
u4=0	1.2	2[5]	2	1.5[75]	2.5	0

Опорный план является оптимальным.

Минимальные затраты составят:

F(x) = 1*35 + 2*10 + 0*5 + 0.4*5 + 1*15 + 1*35 + 1.5*40 + 2*5 + 1.5*75  = 289.5 у.е.

Ответ : Х=

   

 

 

 

 

 

 

 

 

 

2.3 Программная реализация модели

 

 

Задача данного курсового проекта реализована в языке программирования Borland Delphi 7.

В первую очередь Delphi предназначен для профессионалов-разработчиков корпоративных информационных систем. Может быть, здесь следует пояснить, что конкретно имеется в виду. Не секрет, что некоторые удачные продукты, предназначенные для скоростной разработки приложений (RAD - rapid application development) прекрасно работают при изготовлении достаточно простых приложений, однако, разработчик сталкивается с непредвиденными сложностями, когда пытается сделать что-то действительно сложное. Бывает, что в продукте вскрываются присущие ему ограничения только по прошествии некоторого времени. Delphi такие ограничения не присущи. Хорошее доказательство тому - это тот факт, что сам Delphi разработан на Delphi. Именно отсюда можно сделать вывод. Однако Delphi предназначен не только для программистов-профессионалов. Я читал в электронной конференции совершенно неожиданные для меня письма, где учителя, врачи, преподаватели ВУЗов, бизнесмены, все те, кто используют компьютер с чисто прикладной целью, рассказывали о том, что приобрели Delphi for Windows для того, чтобы быстро решить какие-то свои задачи, не привлекая для этого программистов со стороны. В большинстве случаев им это удается.[9,44]

Delphi - это комбинация нескольких важнейших технологий:

2. Высокопроизводительный компилятор в машинный код
3. Объектно-ориентированная модель компонент
4. Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов
5. Масштабируемые средства для построения баз данных

 

В состав Borland Delphi 7 входят:

- компилятор

- генератор отчетов 

- среда визуального построителя приложений

- библиотека визуальных компонент

Так же Borland Delphi 7 обладает открытой компонентной архитектурой. Благодаря такой архитектуре приложения, изготовленные при помощи Delphi, работают надежно и устойчиво. Delphi поддерживает использование уже существующих объектов, включая DLL, написанные на С и С++, OLE сервера, VBX, объекты, созданные при помощи Delphi. Из готовых компонент работающие приложения собираются очень быстро. Кроме того, поскольку Delphi имеет полностью объектную ориентацию, разработчики могут создавать свои повторно используемые объекты для того, чтобы уменьшить затараты на разработку.

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

Классы объектов построены в виде иерархии, состоящей из абстрактных, промежуточных, и готовых компонент. Разработчик может пользоваться готовыми компонентами, создавать собственные на основе абстрактных или промежуточных, а также создавать собственные объекты.[7,101]

 

 

 

2.3.1 Структурная и функциональная схемы программы

 

                            Функциональная схема программы

Предварительный этап. С помощью метода северо-западного угла или метода минимального элемента определяется исходный опорный план исследуемой задачи T. Далее, согласно правилам, изложенным при описании 1-го этапа метода потенциалов, вычисляем величины , , , и составляем матрицу

.

Этап 1. На этапе 1 вычисляется матрица , необходимая для проверки плана на оптимальность.

Этап 2. На этапе 2 производится улучшение плана . Основой этапа является процесс составления цепочки из положительных элементов этого плана.

                     Структурная схема программы

 

 

 

 

2.3.2 Описание процедур, функций, модулей, таблица идентификаторов

 

 

TForm1.Button1Click - процедура, которая позволяет задать размер таблицы с клавиатуры.

TForm1.Button2Click - процедура, которая выполняет расчет всей задачи методом потенциалов.

TForm1.Button3Click - процедура, которая задает размер и данные малой таблицы произвольно.

TForm1.Button4Click - процедура которая задает размер и данные средней таблицы произвольно.

TForm1.Button5Click - процедура которая задает размер и данные большой таблицы произвольно.

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

TForm1.Memo1Change - процедура вывода результата.

TEqSolve.Create - процедура позволяющая создать систему уравнений и решить ее.

TForm1.Button6Click - процедура позволяющая ввести количество товара поставщика или количество требуемого товара на складе.

TForm1.Button7Click - процедура расчета.

TForm1.Button8Click - процедура отчистки таблицы.

TForm1.Ogr_Ed1_01KeyPress - процедура которая следит за тем, что бы пользователь вводил только целый тип данных.

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Анализ результатов расчета

 

 

Анализ результатов данной задачи приводит к тому, что оптимальный путь найден и удовлетворяет условию задачи. Эта задача была решена с помощью языка программирования Delphi 7.0 это значит. Сравнивая результат, полученный в программе и результат, полученный при решении вручную, оказываются одинаковы. Но для решения данной задачи в программе требуется несколько секунд, а для решения в ручную, на много больше времени.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

 

 

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

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

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

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

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:

- оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;

- оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

- задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции.

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

1. Гольштейн, Е.Г. Линейное программирование./ Гольштейн, Е.Г., Юдин, Д.Б. Теория, методы и приложения. - М., Наука, 1969. - с. 424;
2. Грешилов, А.А. Прикладные задачи математического программирования: учебное пособие для ВУЗов./ Грешилов, А.А.  - М., Логос, 2006. - с. 286;
3. Зайченко, Ю.П. Исследование операций./ Зайченко, Ю.П. - 2-ое издание, перер. и доп. - Киев., Высшая школа, 1979. - с. 392;
4. Таха. Введение в исследование операций./ Таха, Хэмди, А.  - 6-е изд. - М., Изд. дом «Вильямс», 2001. - с. 912.  

     5. Абанская А.В. Экономико-математическое моделирование - 2004.- 123 c.

     6. Гасс С. Линейное программирование - 2000.- 167 c.

     7. Дрогобыцкий И.Н. Экономико-математическое моделирование - 2006.- 88 c.

      8. Аверилл М.Лоу Имитационное моделирование - 2005.- 155 c.

      9. Колесов В.М. Моделирование систем. Объектно-ориентированный подход - 2006.- 199 c.

      10.  Колемаев В.А. Экономико-математическое моделирование - 2005.- 66

 

 

 

 

 

 

 

 

 

Приложение А

(справочное)

 

Техническое задание

 

 

Для реализации самой программы выбор пал на среду программирования Delphi. Delphi - это среда быстрой разработки, в которой в качестве языка программирования используется язык Delphi. Язык Delphi - строго типизированный объектно-ориентированный язык, в основе которого лежит хорошо мне знакомый Object Pascal.

Одна из причин, выбора именно этой среды - Borland Delphi 7 может работать в различных операционных системах, начиная от Windows 98 и заканчивая Windows XP. Это очень удобно - если учитывать, что можно работать над своей программой как в колледже, где установлена операционная система Windows 2000, так и в домашних условиях - в среде Windows XP. Так же среда Borland Delphi 7 не требует особых требований к ресурсам компьютера. Несмотря на все эти качества Delphi обеспечивает разработку высокоэффективных программ различного назначения, в том числе для работы с базами данных.