Информационное обеспечение задачи

СОДЕРЖАНИЕ 

     Введение.......................................................................................................................3

     1. Постановка задачи..................................................................................................4

     2. Обзор и анализ существующих методов решения задачи...........…..….............5

     3. Описание выбранного алгоритма………………….…….....................................6

     4. Средства решения задачи

     4.1. Технические средства решения задачи……………………….………….7

     4.2. Инструментальные средства разработки………....……………………...7

     5. Информационное обеспечение задачи

     5.1. Входная информация……………………………………….……………..8

     5.2. Выходная информация………………………………………………..…...8

    6. Программное обеспечение задачи

     6.1. Структура программного продукта……………………………................9

     6.2. Описание программного продукта…………………………........….....…9

     6.3. Руководство пользователю…………………………………......................9

    Заключение…………………………………………………………............………..13

    Литература………………………………………….................................…………..14

    Приложения……………………….…....................................…….………………...15 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

ВВЕДЕНИЕ

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

Одним из вариантов  такой задачи является задача оптимального линейного раскроя материалов. Это  касается раскроя:      

проволоки;      

труб, швеллера,  уголков и т.п.;      

проводов;      

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

     Существующие  методы  раскроя материалов условно можно разделить на 3 группы:      

     нормативные;       

            технологические;     

            оптимизационные. 

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

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

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

1. ПОСТАНОВКА ЗАДАЧИ 

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

Пусть имеется 75 стержней длиной по 92 см. Их надо раскроить  на куски длиной по 12, 17 и 32 см. Куски образуют комплекты, в которых вторых кусков должно быть в 5 раз, а третьих в 3 раза больше чем первых. Требуется так разрезать стержни, чтобы получить максимальное количество комплектов. 

Перечень полноценных  вариантов: 
 

     Разработать программный продукт рассматриваемой  задачи, удовлетворяющий требованиям: наиболее полно удовлетворять информационные  и вычислительные потребности пользователя; надёжность; привлекательный и интуитивно понятный интерфейс программы; все результаты вычислений (включая промежуточные) должны выводиться на печать. 
 
 
 
 
 
 
 
 
 
 

     2. ОБЗОР И АНАЛИЗ СУЩЕСТВУЮЩИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ 

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

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

Последовательность  вычислений симплекс-методом можно  разделить на две основные фазы:

1. нахождение исходной вершины множества допустимых решений,

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

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

Задачи линейного программирования решаются различными методами в зависимости от поставленных условий, и разбивается на следующие типы:

      линейная  задача общего типа;

      транспортная  задача;

      линейная  задача целочисленная;

      дробно-линейная задача;

      линейная  задача, зависящая от параметров (параметрическая). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

3. ОПИСАНИЕ  ВЫБРАННОГО АЛГОРИТМА

     Одним из способов решения задачи является симплекс-метод.

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

     • необходимо выбрать наилучшее решение (оптимальный план) из множества возможных;

     • решение можно выразить как набор значений некоторых переменных величин;

     • ограничения, накладываются на допустимые решения специфическими условиями задачи, формируются в виде линейных уравнений или неравенств;

     • цель выражается в виде линейных функций зависящей от основных переменных.

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

     • определяются переменные величины, значение которых однозначно определяют возможные состояния задачи;

     • составляются соотношения, определяющие взаимосвязи в поставленной задаче;

     • определяется структура целевой функции;

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

       (1)

     Перенеся  систему (1) в жорданову таблицу, получаем: 

     Симплекс  таблица представляет собой жордановую таблицу, последней строкрй в  которой записывается ЦФ. Также если система ограничений не имеет канонического вида (т.е. выражена в виде неравенств), то перед ее переносом в таблицу следует привести ее к каноническому виду. Для приведения системы к каноническому виду добавляют базисные переменные. В зависимости от знака неравенства базисную переменную добавляют в левую часть (если она меньше правой), либо вычитают (если левая часть больше правой). Затем переносят из левой части в правою все, кроме базисных переменных. В случае, если мы вычитали из левой части базисную переменную, то после переноса она остается со знаком "–", от которого следует избавиться, умножив данное уравнение на "–1".

     К примеру перенесем следующую  систему с ЦФ в симплекс таблицу.

     F = B₁X₁ + B₂X₂ + B₃X₃ max

     После заполнения данной таблицы, приступают к ее анализу. Элементы столбца со свободными элементами, а также все  коэффициенты ЦФ должны быть положительными. Если эти условия выполняются, то свободный элемент в коэффициентах ЦФ и является решением. Если хотя бы одно из условий не выполняется, осуществляется преобразование таблицы.

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

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

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

     Если  в таблице после преобразований не осталось отрицательных элементов в свободных элементах. Либо их не было изначально, тогда избавляются от отрицательных значений в коэффициентах ЦФ. Для этого выбирают столбец с наименьшим отрицательным элементом (если их несколько), это будет –разрешающий столбец. Для нахождения разрешающей строки определяют наименьшее частное между элементами свободных членов и элементами разрешающего столбца. Затем приступают к преобразованиям, описанным выше.

     Данные  операции проводят до тех пор, пока в таблице не останется отрицательных значений в свободных элементах и в коэффициентах ЦФ.

4. СРЕДСТВА РЕШЕНИЯ ЗАДАЧИ 

4.1. ТЕХНИЧЕСКИЕ СРЕДСТВА РЕШЕНИЯ ЗАДАЧИ 

     Для решения данной задачи требуется  компьютер с минимальными требованиями:

     • процессор –100 МГц;

     • оперативная память – 64 МБ;

     • жесткий диск – 1 Гб;

     • мышь;

     • клавиатура;

     • подключение компьютера к сети необязательно.

     Данная  программа может эксплуатироваться  под управлением операционной системы MS Windows (не ниже Windows 98). 

     4.2. ИНСТРУМЕНТАЛЬНЫЕ СРЕДСТВА РАЗРАБОТКИ 

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

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

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

5. ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧИ 

5.1. ВХОДНАЯ ИНФОРМАЦИЯ 

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

1.Размерность симплекс-таблицы;

2.Базис; 

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

5.2. ВЫХОДНАЯ ИНФОРМАЦИЯ

     В качестве выходной информации представлено оптимальное решение задачи о раскрое материалов. 

6. ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ ЗАДАЧИ 

6.1. СТРУКТУРА ПРОГРАММНОГО ПРОДУКТА

6.2. ОПИСАНИЕ ПРОГРАММНОГО ПРОДУКТА 

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

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

1.Ввести  размерность симплекс-таблицы;

2.Ввести  базисные переменные;

3.Ввести  дополнительные переменные (S).

4.Выполнить расчет по введенным данным.

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

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

     6.3. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЮ 

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

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

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

     После этого необходимо заполнить таблиц в соответствии с условиями задачи.

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

ЗАКЛЮЧЕНИЕ 

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

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

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

ЛИТЕРАТУРА 

1. Партыка Т.Л., Попов И. И. Математические методы: учебник. 2-е изд., испр. и доп. – М.: ФОРУМ: ИНФРА-М, 2007. – 464 с.: ил.
2. Вентцель, Е.С. Исследование операций: Задачи, принципы, методология/ Е.С. Вентцель. – М.: Высшая школа, 2001. – 208 с.
3. Гольдштейн, Е.Г. Линейное программирование: Теория, методы и приложения / Е.Г. Гольдштейн, Д.Б. Юдин. – М.: Наука, 1969. – 736 с.  
4. Экономико-математическое моделирование. - works.tarefer.ru   
5. Коллекция рефератов Otherreferats. - otherreferats.allbest.ru