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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


дипломная работа Геометрическая интерпретация ОЗЛП как метод оптимизации

Информация:

Тип работы: дипломная работа. Добавлен: 29.08.2012. Сдан: 2011. Страниц: 21. Уникальность по antiplagiat.ru: < 30%

Описание (план):


ФЕДЕРАЛЬНОЕ АГЕНТСТВО  ПО ОБРАЗОВАНИЮ РФ
АРМАВИРСКИЙ МАШИНОСТРОИТЕЛЬНЫЙ ТЕХНИКУМ 
 

                    Допущен к защите
                    Зам. директора по УР
                    ___________И.  Г. Крупнова
                    «__» ________ 2006 г. 
                     

ДИПЛОМНЫЙ ПРОЕКТ 
 

    Тема: «Геометрическая  интерпретация ОЗЛП как метод оптимизации» 

            Специальность 2203 «Программное обеспечение вычислительной техники и автоматизированных систем» 

    Выполнила        студентка группы 4ТПс
                       Н.В.Овсянникова
    Руководитель  проекта      преподаватель
                       Е.П.Яковенко 

    Проверил       Р.Ф.Баева 
     
     
     

2006
       Содержание
 

    ВВЕДЕНИЕ

        Развитие  современного общества характеризуется  повышением технического уровня, усложнением  организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования и хозяйственного руководства. В этих условиях только научный подход к руководству экономической жизнью общества позволит обеспечить высокие темпы развития народного хозяйства.
        Одним из необходимых условий дальнейшего развития экономической науки является применение точных методов количественного анализа, широкое использование математики. В настоящее время новейшие достижения математики и современной вычислительной техники находят все более широкое применение в экономических исследованиях и планировании. Этому способствует развитие таких разделов математики, как математическое программирование, теория игр, теория массового обслуживания, а также бурное развитие быстродействующей электронно-вычислительной техники. Уже накоплен достаточный опыт постановки и решения экономических задач с помощью математических методов. Особенно успешно развиваются методы оптимального планирования, которые и составляют сущность математического программирования.
        Одной из основных становится задача создания единой системы оптимального планирования и управления народным хозяйством на базе широкого применения математических методов и электронно-вычислительной техники в экономике.
        Решение экстремальных экономических задач  можно разбить на три этапа:
        1) построение экономико-математической модели;
        2) нахождение оптимального решения  одним из математических методов; 
        3) практическое внедрение в народное  хозяйство. Построение экономико-математической  модели состоит в создании  упрощенной экономической модели, в которой в схематической форме отражена сущность изучаемого процесса. При этом особое внимание должно быть уделено отражению в модели всех существенных особенностей задачи и учету всех ограничивающих условий, которые могут повлиять на результат. Затем определяют цель решения задачи и дают математическую формулировку задачи.
        Методам линейного программирования посвящено  много работ зарубежных и, прежде всего американских ученых. В 1941 г. Хичкок поставил транспортную задачу. Основной метод решения линейного программирования - симплексный метод - был опубликован в 1949 г. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Гасса, Чарнеса, била и др. в настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно быть применено, а также по пути создания более удобных алгоритмов для решения задач на электронно-вычислительных машинах.
        Данный  дипломный проект посвящен задаче линейного  программирования о загрузке станков, где количество переменных на два  больше количества уравнений. Попытаемся решить ее несколькими способами  и сделаем выводы.
 

    1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

    1.1. Описание решаемой задачи

        Представим  себе группу из трех станков, каждый из которых может производить два  типа деталей, условно А и Б. Производительность каждого из станков по разным типам деталей, как правило, различна: станок № 1 производит в одну минуту 5 деталей А и 5 деталей Б, станок № 2 – 6 деталей А и 2 детали Б, станок № 3 – 5 деталей А и 3 детали Б. При решении задачи необходимо учитывать два ограничения:
        1) ни один из станков не должен простаивать;
        2) продукция должна быть комплектна: количество произведенных деталей А должно равняться числу деталей Б.
        Прежде всего, попытаемся получить глазомерное решение задачи. Все расчеты будем производить исходя из общей продолжительности времени работы в 6 ч.=360 мин. (одна смена).
        На  все указанное время загрузим станок № 1 деталями А, а станки № 2 и № 3 – деталями Б. Результат такого решения изобразим следующим образом: слева покажем время загрузки станков по различным деталям, а справа – соответствующее количество произведенной продукции (произведение времени работы на минутную производительность):
    Таблица 1 Глазомерное решение задачи  

Станки
        Детали
А Б А Б
№ 1 360 0 1800 0
№ 2 0 360 0 720
№ 3 0 360 0 1080
 
    Общее количество выпущенной продукции составит 1800+1800=3600 деталей. Это решение отвечает поставленным условиям: во-первых, все станки полностью загружены в течение рабочего времени; во-вторых, количество произведенных деталей А в точности равно числу полученных деталей Б.
        Однако  является ли это решение  наилучшим, нельзя ли добиться большей производительности в данных условиях?
 

         1.2. Экономическое  значение решаемой  задачи

        Для решения конкретных практических экономических  задач можно рекомендовать такую  последовательность:
    Уясняем задачу - ее экономический смысл. На этой основе устанавливаем цель решения.
    Оцениваем экономическую ситуацию – определяем, от чего зависит достижение установленной цели.
    Выбираем численный показатель, от которого достижение цели зависит в первую очередь.
    Строим математическую модель операции, устанавливающую количественные зависимости избранного показателя от условий задачи. Для этого подбираем соответствующий экономико-математический метод.
    С помощью математической модели и найденного экономическо-математического метода решаем задачу.
    Проверяем правильность найденного решения.
        Постановка  задачи: Представим себе группу из трех станков, каждый из которых может производить два типа деталей, условно А и Б. Производительность каждого из станков по разным типам деталей, как правило, различна: станок № 1 производит в одну минуту 5 деталей А и 5 деталей Б, станок № 2 – 6 деталей А и 2 детали Б, станок № 3 – 5 деталей А и 3 детали Б. При решении задачи необходимо учитывать два ограничения:
        1) ни один из станков не должен  простаивать;
        2) продукция должна быть комплектна: количество произведенных деталей  А должно равняться числу деталей  Б.
        Итак, по порядку:
    Экономический смысл задачи – правильно загрузить станки. Отсюда цель решения: определение максимальной прибыли для предприятия, которую можно получить при выбранной загрузки станков.
    Получение максимальной прибыли связано со временем работы каждого станка и с его производительностью.
    Основным показателем, от которого зависит достижение поставленной цели, является получение максимального количества продукции от каждого станка, приводящее к решению задачи – максимальной прибыли.
    Математическая модель задачи должна связать максимальную полученную прибыль с загрузкой станков.
        Формулировка  математической модели задачи:
      Переменные для решения задачи: хij – время работы i–го станка, занятого производством j–той детали.
      Определение функции цели (критерии оптимизации). Суммарная суточная прибыль от производства продукции равна L.
      Ограничения на переменные:
        - время работы каждого станка  не должно быть отрицательным,  т.е. хij?0;
        - станки не должны простаивать,  т.е. 
        х11 12=360,
        х21 22=360,
        х31 32=360,
        - количество произведенной продукции  на станке А должно равняться  количеству произведенной продукции на станке Б, т.е.
        11+6х21+5х31 =5х12+2х22+3х32.
    Найти максимум следующей функции:
        L=5х11+5х12+6х21+2х22+5х31+3х32>max
    При ограничениях вида:
        х11 12=360,
        х21 22=360,
        х31 32=360,
        11+6х21+5х31 =5х12+2х22+3х32.
    Прежде всего, попытаемся получить глазомерное решение задачи. Все расчеты будем производить исходя из общей продолжительности времени работы в 6 ч.=360 мин. (одна смена). Суть метода удобнее всего выразить с помощью наглядного геометрического представления, графика (рисунок 1). Здесь показан построенный по правилам математического программирования многоугольник ОАВСD (он выделен).
        
    Рисунок 1
    График  решения станковой задачи
 
    Многоугольник соответствует условиям нашей задачи и представляет собой область допустимых решений распределения времени работы станков № 2 и № 3 над деталью А. По соответствующим осям графика отмечена продолжительность работы этих станков. (В своих расчетах мы вполне можем обойтись двумя станками и одной деталью, так как по этим данным нетрудно рассчитать и все остальные.) В теории математического программирования убедительно показывается, что оптимальному решению соответствует одна из вершин многоугольника допустимых планов, а именно та, для которой общая производительность окажется максимальной. В нашем случае это вершина С. Как видно из графика, этой точке соответствует время работы над деталью А станка № 2, равное 360, станка № 3 – 90 мин. По этим данным нетрудно составить план распределения станков, причем время, отводимое на производство детали Б станками № 2 и № 3, получится как дополнение до 360 минут времени, снятого с графика, - станки не должны простаивать. Что касается станка № 1, то его время работы подбираем таким, чтобы общее количество деталей А и Б совпадало.
    Таблица 2 План распределения работы станков 

    Станок
    Продолжительность работы станка, мин     Производительность  станка (количество деталей за время  работы)
    А     Б     А     Б
    № 1
    0     360     0     1800
    № 2
    360     0     2160     0
    № 3
    90     270     430     810
      2610+2610
    Общее количество выпущенной продукции 5220 деталей
     
        Никакого  дополнительного расхода каких-либо ресурсов не потребовалось. Те же станки, те же детали, те же станочники работают то же время. Не меняется и производительность станков.
    Расчет легко проверить, ведь условия задачи выполняются 2610=2610, каждый станок загружен и не простаивает.
 

    1.3. Обоснование выбора методов решения задачи

        Линейное  программирование – это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на неизвестные которой наложены линейные ограничения. Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции. Казалось бы, что для исследования линейной функции многих переменных на условный экстремум достаточно применить хорошо разработанные методы математического анализа, однако невозможность их применения иллюстрируют простейшие примеры.
        Основная  задача линейного программирования (ОЗЛП) ставится следующим образом: имеется ряд переменных х1, х2, …, хn, требуется найти такие неотрицательные значения этих переменных, которые удовлетворяли бы системе линейных уравнений:
     а11x1+a12x2+a13x3+…+a1nxn=b1,
    а21x1+a22x2+a23x3+…+a2nxn=b2,
            ………………………………    (1)
    а31x1+a32x2+a33x3+…+a3nxn=b3,
        Которые, кроме того, обращали бы в минимум линейную функцию:
        L=c1x1+c2x2+…+cnxn  (2)
        Допустимое  решение ОЗЛП –это любая совокупность неотрицательных переменных, удовлетворяющая уравнениям (1).
        Оптимальное решение- это то из допустимых, при котором линейная функция (2) обращается в минимум.
        ОЗЛП  не обязательно должна иметь решение.
    Может оказаться, что уравнения (1) противоречат друг другу;
    Может оказаться, что они имеют решения, но не в области неотрицательных значений х1, х2, … , хn, в этих случаях ОЗЛП не имеет допустимых решений.
    Может оказаться, что допустимые решения ОЗЛП существуют, но среди них нет оптимального.
        Рассмотрим, прежде всего, вопрос о существовании  допустимых решений ОЗЛП. При решении  этого вопроса мы можем исключить  из рассмотрения линейную функцию  L, которую требуется минимизировать, т.к. наличие допустимых решений определяется только уравнениями (1).
        Ранг  матрицы- наибольший порядок отличного от 0 определителя, который можно получить вычеркивая из матрицы какие-то строки и столбцы.
        Для совместности системы линейных уравнений (1) необходимо и достаточно, чтобы  ранг матрицы системы был равен  рангу матрицы ее расширенной матрицы.
        Если  система уравнений ограничений  ОЗЛП совместна, то матрица системы  и ее расширенная матрица имеют  один и тот же ранг. Этот общий  ранг r называется рангом системы, он представляет собой ничто иное, как число линейно - независимых уравнений среди наложенных ограничений.
    Ранг системы r не может быть больше числа уравнений m
        R?m
        2) Ранг системы не может быть  больше общего числа переменных  n
        R?n
        Структура задачи линейного программирования существенно зависит от ранга  системы ограничений, при R=n, система уравнений ограничений ОЗЛП имеет единственное решение.
        Если  в этом решении хотя бы одна из величин  отрицательна, это значит, что полученное решение не допустимо и ОЗЛП не имеет решения.
        В дальнейшем будем рассматривать  случаи, когда R<n, т.е. когда число независимых уравнений, которым должны удовлетворять переменные х1, х2, … , хn, меньше числа самих переменных, тогда если система совместна – у нее существует бесчисленное множество решений, при этом n-R переменным мы можем придавать произвольные значения (так называемые свободные переменные), а остальные R переменных выразятся через них (эти R переменных мы будем называть базисными).
 

    1.4.Описание  выбранного алгоритма  решения

        Основную  задачу линейного программирования можно решать с помощью геометрической интерпретации, в том числе, когда число переменных на два больше, чем число независимых уравнений m, которым они должны удовлетворять.
        Свойство  решения ОЗЛП для  случая, когда m=n-2.
    Решение ОЗЛП, если оно существует, не может лежать внутри Области Допустимых Решений (ОДР), а только на ее границе.
    Решение ОЗЛП может быть и не единственным. Это произойдет в том случае, если основная прямая параллельна той стороне многоугольника допустимых решений, где достигается минимум L'. В этом случае минимум достигается на всей этой стороне и ОЗЛП имеет бесчисленное множество решений.
    ОЗЛП может не иметь решения, даже в случае, когда существует ОДР. Это бывает тогда, когда в направлении стрелок ОДР не ограничено.
    Решение ОЗЛП минимизирует функцию L (оптимальное решение) всегда достигается в одной из вершин ОДР.
        Решение, лежащее в одной из вершин ОДР называется опорным решением, а сама вершина – опорной точкой.
    Для того чтобы найти оптимальное решение, можно перебрать все вершины ОДР (опорные точки) и выбрать ту из них, где функция L достигает минимума.
    Если число свободных переменных в ОЗЛП равно двум, а число базисных m, и решение ОЗЛП существует, то оно всегда достигается в точке, где, по крайней мере, хотя бы две из переменных обращаются в нуль.
        Рассмотрим задачу линейного программирования, система ограничений которой задана виде неравенств.
        Найти минимальное значение линейной функции 
             (1.1)           Z=C1x1+C2x2+…+Cnxn
         При ограничениях
        а11x1+a12x2+…+a1nxn ? b1,
        а21x1+a22x2+…+a2nxn ? b2,
        (1.2)              …………………………
        аm1x1+am2x2+…+amnxn ? bm,
        (1.3)  хj?0 (j=1,2,… n).
        Совокупность  чисел х1, х2, … , хn, удовлетворяющих ограничениям(1.2) и (1.3), называется решением. Если система неравенств (1.2) при условии (1.3) имеет хотя бы одно решение, она называется совместной, в противном случае – несовместной.
        Рассмотрим  на плоскости х1Ох2 совместную систему линейных неравенств
        а11x1+a12x2+…+a1nxn ? b1,
        а21x1+a22x2+…+a2nxn ? b2,  х1 ? 0,
        …………………………  х2 ? 0.
        аm1x1+am2x2+…+amnxn ? bm,
          Это все равно, что в системе (1.2) – (1.3) положить n = 2. Каждое неравенство этой системы геометрически определяют полуплоскость с граничной прямой ai1x1+ai2x2=bi (i =1,2,…, m). Условия неотрицательности определяют полуплоскости соответственно с граничными прямыми х1 = 0, х2 = 0. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, координаты каждой из которых являются решением данной системы (рисунок 2). Совокупность этих точек (решений) будем называть многоугольником решений. Он может быть точкой, отрезком, многоугольником, неограниченной многоугольной областью.
        
    Рисунок 2
    Область допустимых решений
    Если в системе ограничений (1.2)-(1.3) n = 3, то каждое неравенство геометрически представляют полупространство трехмерного пространства, граничная плоскость которого ai1x1+ai2x2 +ai3x3=bi (i =1,2,…, m), а условия неотрицательности – полупространства с граничными плоскостями соответственно xj=0 (j=1, 2, 3). Если система ограничений совместна, то эти полупространства, как выпуклые множества, пересекаясь, образуют в трехмерном пространстве общую часть, которая называется многогранником решений. Многогранник решений может быть точкой, отрезком, лучом, многоугольником, многогранником, многогранной неограниченной областью.
        Пусть в системе ограничений (1.2)-(1.3) n > 3; тогда каждое неравенство определяет полупространство n –мерного пространства с граничной гиперплоскостью ai1x1+ai2x2+ainxn=bi (i =1,2,…, m), а условия неотрицательности – полупространства с граничными гиперплоскостями xj=0 (j=1, 2, …, n).
        Если  система ограничений совместна, то по аналогии с трехмерным пространством  она образует общую часть n –мерного пространства, называемую многогранником решений, так как координаты каждой точки являются решением.
        Таким образом, геометрически задача линейного  программирования представляет собой  отыскание такой точки многогранника  решений, координаты которой доставляют линейной функции минимальное значение, причем допустимыми решениями являются все точки многогранника решений.
 

    2. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ

        2.1. Описание реализации  алгоритма решения  задачи

        Составим  систему уравнений, описывающую условия задачи:
        х1112=360,
        х2122=360,
        х3132=360,
        11+6х21+5х31=5х12+2х22+32.
        И линейную функцию L, которую необходимо максимизировать.
        L=5х11+5х12+6х21+2х22+5х31+3х32
        Где хij- время работы i-го станка, занятого производством j-ой детали.
        Эта задача относится к задачам линейного программирования, т.к. имеется система линейных уравнений, которым должно удовлетворять решение, а также линейная функция, которую необходимо минимизировать (максимизировать).
        Основную  задачу линейного программирования можно решать с помощью геометрической интерпретации, когда число переменных (хij) на два больше, чем число независимых уравнений m, которым они должны удовлетворять.
        В нашей задаче число переменных n (6) на два больше, чем число независимых уравнений m (4), которым они должны удовлетворять: n-m=2.
                х1112=360,
        (2.1) х2122=360,
              х3132=360,
        11+6х21+5х31=5х12+2х22+32.
        Выберем  в качестве свободных переменных, например, x12 и x22 и выразим через них остальные (базисные) переменные: х11, х21, х32, х31. Из первого уравнения имеем:
        х11=360-х12    (2.2)
        Из  второго:
        х21=360-х22    (2.3)
        Из  третьего:
        х31=360-х32.    (2.4)
        Подставляя (2.2), (2.3.) и (2.4.) в последнее уравнение и разрешая его относительно  х32, имеем:
        х32=720-1,25х1222,   (2.5)
        х31=-360+1,25х1222.   (2.6)
        Геометрическая  интерпретация задачи представлена на рисунке 3 (прямые х12=0, х22=0 – оси координат; остальные ограничивающие прямые х31
    и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


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