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

СОДЕРЖАНИЕ 

     Введение.......................................................................................................................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) в жорданову таблицу, получаем: