Разработка алгоритма решения транспортной задачи - Курсовая работа

Допустим, что данный продукт потребляют в пунктах В1, …, Bn, а объем потребления в пункте Bj составляет bj единиц (j = 1, 2, …, n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны. Условия транспортной задачи удобно представить в следующем виде: Пусть xij - количество продукта, перевозимого из пункта Аі в пункт Bj. Меню содержит все функциональные возможности программы в соответствии с требованиями, которые были предъявлены к ней на этапе планирования данной программы, а также справочную систему «Help» для решения вопросов, возникших в ходе работы с программой. В программе во все поля ввода можно вводить только цифры, это обусловлено тем что все поля для ввода являются полями ввода количеств поставщиков и потребителей.В курсовом проекте были рассмотрены следующие вопросы: · Разработан алгоритм метода решения поставленной задачи; Задачей данного курсового проекта являлось разработать программный продукт «Решение транспортной задачи методом минимальной стоимости» с использованием таблиц в Delphi.Рисунок 1 - Вход в программу Рисунок 3 - Заполнение случайными числамиButton5.Enabled:= false;N7.Enabled:=false;N18.Enabled:=false; begin if (length(Edit1.Text)0) and (length(edit2.Text)0) then begin ac1:=true;Button1.Enabled:= true;CHECKBOX1.Enabled:= true; end else begin ac1:=false;Button1.Enabled:= false;CHECKBOX1.Enabled:= false; begin if (length(Edit1.Text)0) and (length(edit2.Text)0) then begin ac1:=true;Button1.Enabled:= true;CHECKBOX1.Enabled:= true; N5.Enabled:=true;N4.Enabled:=true;N11.Enabled:=true;end else begin ac1:=false;Button1.Enabled:= false;CHECKBOX1.

транспортный линейный программирование

Транспортная задача - это задача о наиболее экономичном плане перевозок груза. Транспортная задача является одной из самых распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например, А.Н. Толстым.

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

Первый точный метод решения транспортной задачи разработан советскими учеными Л.В. Канторовичем и М.К. Гавуриным.

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

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

Пусть в пунктах А1, А2, …, Ам производят некоторый однородный продукт, причем объем производства в пункте Аі составляет ai единиц (i = 1, 2, …, m). Допустим, что данный продукт потребляют в пунктах В1, …, Bn, а объем потребления в пункте Bj составляет bj единиц (j = 1, 2, …, n).

Предположим, что из каждого пункта производства возможна транспортировка продукта в любой пункт потребления. Транспортные издержки по перевозке из пункта Аі в пункт Bj единицы продукции равны cij (i = 1, 2, …, m; j = 1, 2, …, n).

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

Условия транспортной задачи удобно представить в следующем виде: Пусть xij - количество продукта, перевозимого из пункта Аі в пункт Bj. Требуется определить множество переменных xij>0 (i = 1, 2, …, m; j = 1, 2, …, n), удовлетворяющих условиям

(i = 1, 2, …, m), (1.1)

(j = 1, 2, …, n), (1.2) и таких, что целевая функция достигает минимума.

(1.3)

Таблица 1.1 - Табличная форма записи условий транспортной задачи

Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а условие (1.2) означает полное удовлетворение спроса во всех пунктах потребления.

Различают транспортные задачи с закрытой и открытой формой. Закрытая модель характеризуется равенством сумм запасов и потребностей.

В открытой форме эти суммы не равны.

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

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

Если , то вводят фиктивный (m 1) пункт назначения с запасами и полагают .

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

Решение транспортной задачи распадается на два этапа: нахождение опорного плана, улучшение опорного плана.

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

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

Формальное описание метода. Элементы матрицы нумеруют, начиная от минимального в порядке возрастания, а затем в этом же порядке заполняют матрицу .

Пусть элементом с минимальным порядковым номером оказался элемент .

Возможны три случая: · если , то оставшуюся часть -й строки заполняем нулями;

· если , то оставшуюся часть -го столбца заполняем нулями;

· если , то оставшуюся часть строки и столбца заполняем нулями.

Далее этот процесс повторяют с незаполненной частью матрицы.

Пусть элементом с -ым порядковым номером оказался . Тогда , , g = 1, …, (k - 1);

, l = 1, …, (k - 1).

Возможны два случая: · , тогда и оставшуюся часть строки заполняют нулями;

· , тогда и остаток столбца заполняют нулями.

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

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

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

Delphi - язык и среда программирования, относящаяся к классу RAD- (Rapid Application Development - «Средство быстрой разработки приложений») средств CASE - технологии. Delphi сделала разработку мощных приложений Windows быстрым процессом, доставляющим вам удовольствие. Приложения Windows, для создания которых требовалось большое количество человеческих усилий, например в С , теперь могут быть написаны одним человеком, использующим Delphi.

Delphi обладает широким набором возможностей, начиная от проектировщика форм и заканчивая поддержкой всех форматов популярных баз данных. Среда устраняет необходимость программировать такие компоненты Windows общего назначения, как метки, пиктограммы и даже диалоговые панели. Работая в Delphi, вы неоднократно видели одинаковые «объекты» во многих разнообразных приложениях. Диалоговые панели (например, Choose File и Save File) являются примерами многократно используемых компонентов, встроенных непосредственно в Delphi, которая позволяет приспособить эти компоненты к имеющейся задаче, чтобы они работали именно так, как требуется создаваемому приложению. Также здесь имеются предварительно определенные визуальные и невизуальные объекты, включая кнопки, объекты с данными, меню и уже построенные диалоговые панели. С помощью этих объектов можно, например, обеспечить ввод данных просто несколькими нажатиями кнопок мыши, не прибегая к программированию. Это наглядная реализация применений CASE-технологий в современном программировании приложений. Та часть, которая непосредственно связана с программированием интерфейса пользователя с системой, получила название визуальное программирование.

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

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

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

Задание на разработку программного продукта было выдано преподавателем колледжа ВКГТУ Осадчей Н.А.. Программный продукт должен быть разработан в срок с пятого сентября до двадцать шестого октября две тысячи пятого года.

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

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

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

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

Данная программа выполнена в соответствии с требованиями пользователя. Цветовая гамма форм приемлемая, не бросается в глаза, нет ярких контрастов, которые могут затруднять длительную работу с программой. Данный программный продукт обладает простым пользовательским интерфейсом. Основное меню программы загружается после закрытия окна загрузки и ввода пароля. Все окна программы плавно раскрываются из центра экрана. Меню содержит все функциональные возможности программы в соответствии с требованиями, которые были предъявлены к ней на этапе планирования данной программы, а также справочную систему «Help» для решения вопросов, возникших в ходе работы с программой. Помощь также соответствует всем требованиям основной программы, т.е. не имеет ярких контрастов, все объекты на форме расположены в удобном порядке.

Минимальная конфигурация, необходимая для нормального функционирования программного продукта содержит следующие параметры: · Процессор Celeron 1200 и выше;

· ОЗУ - 128 Мб и выше;

· Цветовая гамма - 32 бита;

· Занимаемое место на НЖМД -

· Монитор;

· Клавиатура;

· Манипулятор «Мышь»;

· 19,9 Mb свободного места на диске.

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

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

· Заполнить таблицу с условиями задачи. Выбрать путь заполнения вручную или выбрать путь заполнения случайными числами;

· Вывести в таблицу с результатом ответ на введенную транспортную задачу;

· Выйти из программы или начать алгоритм заново.

Выполнение алгоритма обусловлено тем, что средства управления таблицами по мере выполнения алгоритма становятся активными или дезактивируются.

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

Для того чтобы программа смогла решить транспортную задачу, необходимо ввести: · Количество поставщиков;

· Количество потребителей;

· Стоимость перевозок;

· Количество запасов на каждом из пунктов отправления;

· Количество потребностей на каждом пункте назначения.

Все перечисленные выше пункты списка являются числами.

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

При входе в программу появляется окошко, которое является окном запроса пароля.

В поле вводится пароль, заменяемый в самом поле ввода на знаки «*». После этого нажимается кнопка «Да», которая выполняет вход в программу. Нажатие кнопки «Нет» на данном этапе приведет к выходу из программы. При первом входе в программу пароля нет, то есть ничего в поле ввода пароля вводить не надо. Но при помощи кнопки «Смена пароля» можно ввести и изменить пароль. В поле ввода «Старый пароль» вводится старый пароль, в поля ввода «Новый пароль» и «Подтверждение» необходимо ввести тот пароль, который Вы хотели бы поставить при входе в программу (см. приложение А, рисунок 1).

После нажатия кнопки «Да» в окне входа в программу на экране появляется заставка, и далее появляется рабочее окно (см. приложение А, рисунок 2).

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

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

Если Вы остановите свой выбор на кнопке «Заполнить случайно», то это приведет к тому, что таблица исходных данных будет заполнена случайными числами, причем транспортная задача будет иметь закрытую форму. При нажатии кнопки «Заполнить случайно» автоматически независимый переключатель становится неактивным, а кнопка «Результат» активируется (см. приложение А, рисунок 3).

Если Вы щелкните по независимому переключателю, тем самым, поставив галочку, то дезактивируется кнопка «Заполнить случайно», а активной станет кнопка «Создать шапку таблицы». Ее нажатие приведет к созданию шапки таблицы и открытию полей таблицы для редактирования, а также станет активной кнопка «Принять данные» (см. приложение А, рисунок 4).

Необходимо ввести данные в таблицу и нажать кнопку «Принять данные». Если форма транспортной задачи представляет собой закрытую модель, то программа выдаст сообщение о принятии данных (см. рисунок А.5).

В случае, когда программа обнаружит, что суммы запасов и потребностей не равны, она выдаст запрос о том, что ей делать (см. приложение А, рисунок 6).

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

После того, как данные были приняты программой, активной становиться кнопка «Результат», а кнопка «Принять данные» дезактивируется.

Нажатие кнопки «Результат» приведет к появлению в таблице результата ответа на поставленную задачу, а в поле «Стоимость перевозок» появиться сумма затрат на перевозки (см. приложение А, рисунок 7).

Далее неактивной станет кнопка «Результат», а активируется кнопка «Заново». Нажатие кнопки заново приведет обращению рабочего окна в изначальную форму.

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

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

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

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

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

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

Площадь помещения для работающего на персональном компьютере из расчета на одного человека - не менее 6 квадратных метров, кубатура - 19,5 кубических метров, с учетом максимального числа одновременно работающих.

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

Конструкция рабочей мебели (столы, кресла, стулья) должны обеспечивать возможность индивидуальной регулировки соответственно росту работающего и создавать удобную позу. Часто используемые предметы труда (документы, клавиатура, дисплей, принтер) должны находиться в оптимальной рабочей зоне. Рабочее место для выполнения работ в положении сидя должно соответствовать требованиям ГОСТ и технической эстетики. В конструкции его элементов необходимо учитывать характер работы, психологические особенности и антропометрические данные человека.

Рабочий стол должен регулироваться по высоте в пределах 680-760 мм, при отсутствии такой возможности 720 мм, оптимальные размеры рабочей поверхности столешницы 1600?900 мм. Под столешницей рабочего стола должно быть свободное пространство для ног с размерами по высоте не менее 600 мм, по ширине - 500 мм, по глубине - 650 мм.

Рабочий стул (кресло) должен быть снабжен подъемно-поворотным устройством, обеспечивающим регуляцию высоты сидения и спинки, его конструкции должна предусматривать также изменение угла наклона спинки. Рабочее кресло должно иметь подлокотники. Регулировка каждого параметра должна легко осуществляться, быть независимой и иметь надежную фиксацию. Высота поверхности сидения должна регулироваться в пределах 400-500 мм. Ширина сидения должна составлять не менее 400 мм, глубина - не менее 380 мм.

Высота опорной поверхности спинки должна быть не менее 300 мм. Ширина не менее 380 мм, радиус ее кривизны в горизонтальной плоскости 400 мм. Угол наклона спинки должен изменяться в пределах 90-110 % к плоскости сидения.

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

На рабочем месте необходимо предусматривать подставку для ног. Ее длина должна составлять 400 мм, ширина 350 мм, регулировка высоты 0-150 мм, угла наклона 0-120°.

В целях профилактики переутомления и перенапряжения при работе на ЭВМ необходимо выполнять комплексы упражнений. С целью снижения или устранения нервно - психического, зрительного и мышечного напряжения необходимо проводить сеансы психофизиологической разгрузки и снятия усталости во время регламентированных перерывов, и после окончания рабочего дня. Снижение или устранение нервно-психического, зрительного и мышечного напряжения, предупреждение переутомления и снятие усталости во время регламентированных перерывов и после окончания рабочего дня проводится в специально оборудованном помещении - комнате психологической разгрузки. Эту комнату следует располагать на расстоянии не белее 75 м от рабочих мест. Требования к оборудованию комнаты психологической разгрузки изложены в "Межотраслевых методических рекомендациях по предупреждению переутомления работников физического и умственного труда".

При обычной работе с компьютером необходимо делать 15-минутные перерывы через каждые два часа, а при интенсивной работе - через каждый час.

Основным перерывом является перерыв на обед. Не следует превышать темп работы порядка 10 тысяч нажатий клавиш в час (примерно 1500 слов).

При вводе данных с клавиатуры рекомендуется не зажимать телефонную трубку между плечом и ухом, а также бросить курить (что вредно как для пользователя, так и для компьютера).

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

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

В курсовом проекте были рассмотрены следующие вопросы: · Разработан алгоритм метода решения поставленной задачи;

· Написанная программа, пригодная для использования

Задачей данного курсового проекта являлось разработать программный продукт «Решение транспортной задачи методом минимальной стоимости» с использованием таблиц в Delphi.

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

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

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