Студопедия КАТЕГОРИИ: АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Целочисленное программированиеСтр 1 из 4Следующая ⇒
КУРСОВАЯ РАБОТА по дисциплине «Математические методы»
Тема: «Специальные задачи линейного программирования»
Выполнил: студент 3 курса группы БП2-118 Ланин В.О.
Руководитель Белгородцева Н.А. Оценка:________________ Дата защиты:___________
2011 ФГОУ СПО «Омский государственный промышленно-экономический колледж» Экономическое отделение
Задание для курсовой работы студента Ланина Виталия Олеговича, группа БП2-118
1. Тема курсовой работы: «Специальные задачи линейного программирования» утверждена на заседании цикловой комиссии протокол № от « » 20г.
Срок сдачи курсового проекта « » 20г.
Перечень вопросов, подлежащих исследованию или разработке: А) Целочисленное программирование - формулирование в Древней Греции Диофантом (II-III вв.) уравнения, в котором искомые переменные целые; - какие задачи называют задачами целочисленного программирования; - какую задачу называют целочисленной задачей линейного программирования, а какую – целочисленной задачей нелинейного программирования; - привести примеры задач целочисленного или дискретного программирования; - методы отсечений и методы возврата, метод ветвей и границ; Б) Метод ветвей и границ - какая задача называется непрерывной; - методом ветвей и границ решить задачу:
После получения нецелочисленного решения составить две новые задачи с различными граничными условиями. В) Задача выбора вариантов - какие переменные называют булевыми, в честь кого они получили такое название; - составить математическую модель и решить задачу выбора вариантов: Для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл.) Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трёх ( ).
Г) Дискретное программирование Мебельная фабрика выпускает диваны, кресла и стулья. Требуется определить, сколько можно изготовить спинок диванов, подлокотников кресел и ножек стульев при известном удельном расходе ресурсов (табл.), чтобы доход был максимальным.
Причём выпуск спинок дивана может принимать любое значение, подлокотники изготавливаются парами, т. е. их количество должно быть кратно двум, а количество ножек стульев – четырём. Д) Методы решения дискретных задач - как решаются задачи дискретного программирования методом ветвей и границ; - решить систему методом сплошного перебора: - какую последовательность действий предполагает метод фильтрующего ограничения; - что такое фильтр; - какой фильтр называют адаптивным;
Руководитель курсовой работы ___________________Подпись, дата
Зав. отделением ___________________Подпись, дата
Задание принял к исполнению ___________________Подпись, дата
Федеральное государственное образовательное учреждение среднего профессионального образования «Омский промышленно-экономический колледж»
РЕЦЕНЗИЯ №____
На курсовую работу Студента Ланина Виталия Олеговича гр. БП2-118 По математическим методам _
на тему «Специальные задачи линейного программирования» « » 20г.
Рецензент_________________________
____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________ План-график выполнения курсовой работы
Студент Ланин Виталий Олегович, группа БП2-118
Тема курсовой работы «Специальные задачи линейного программирования»
утверждена на заседании цикловой комиссии от ____________ протокол №______
Дата__________________ Подпись студента_______________
Дата__________________ Подпись руководителя___________
Содержание Содержание. 7 Введение. 8 Обзор литературы.. 9 1. Целочисленное программирование. 10 2. Методы ветвей и границ. 13 3. Задача выбора вариантов. 17 4. Дискретное программирование. 21 5. Методы решения дискретных задач. 24 Заключение. 7 Список используемой литературы.. 7
Введение Переход к рыночной экономике и функционированию рыночного механизма регулирования включает в себя совершенствование этапа планирования, который становится тесно связанным с прогнозированием эффективных направлений экономического развития. Актуальными являются разработка математического описания экономических процессов и развитие методов оптимизации для решения возникающих сложных математических задач. Это особенно существенно для определения вариантов экономического развития на перспективу, когда необходимо учитывать крупные и продолжительные народнохозяйственные мероприятия: создание и развитие территориально-производственных комплексов, обеспечение скоординированных программ исследований и разработок, распределение ресурсов для выполнения отдельных комплексов работ при программно-целевом планировании, осуществление выпуска крупных изделий, производство которых требует значительного времени. Оптимальное решение является наилучшим только в рамках использования данной модели. Не следует считать, что это действительно самое лучшее решение анализируемой задачи. Целью данной работы является обзор и анализ методов решения специальных задач линейного программирования.
Обзор литературы
При написании курсовой работы мною была использована книга «Математические методы и модели для менеджмента» (Глухов В. В., Медников М. Д., Коробко С. Б.), имеющаяся в библиотеке колледжа. Именно в ней наиболее полно изложен материал о специальных задачах линейного программирования. Так же в издании имеется достаточное количество схем и примеров для структурирования прочитанной информации. Вторым, но не менее важным источником, служит книга «Методы оптимизации» (Харчистов Б.Ф.). В ней изложены основные понятия и теоретические положения курса "Методы оптимизации". Приведены алгоритмы, реализующие различные методы решения оптимизационных задач.
Целочисленное программирование Первые упоминания о линейных уравнениях возникли еще за несколько веков до нашей эры. В Древней Греции Диофант (II-III вв.) формулирует уравнения, в которых искомые переменные — целые. Например, для уравнения первой степени, а0 + a1x1 = 0, где a0, a1 — целые, решение x1 = -a0/a1 — целое, если a0 делится на a1 без остатка, т. е. такое уравнение не всегда разрешимо в целых числах. Из двух уравнений 3x1 - 27 = 0 и 5x2 + 21 = 0 только первое имеет целое решение: x1 = 27/3 = 9, а второе — нет, так как x2 = -21/5. Для уравнения с двумя неизвестными: a1x1 + a2x2 = 0, где a2, a1 — целые, решение будет x1 = -(a2/a1)x2. Например, 10x2 - 5x2 = 0 или x1 = 0,5x2 . (1) Из этого примера можно сделать следующие выводы: уравнение имеет бесчисленное множество решений, так как n > m; решение — целое, если x2 — четное. Для того чтобы из множества допустимых решений выбрать одно — оптимальное, необходимо, как нам уже известно, добавить к условию (1) целевую функцию. Задачи оптимизации, в которых решение должно быть в целых числах, называют задачами целочисленного программирования. Если в этой задаче целевая функция и ограничения — линейные зависимости, то ее называют целочисленной задачей линейного программирования;если же хотя бы одна зависимость будет нелинейной, то такая задача формулируется как целочисленная нелинейного программирования. Большинство практических задач принятия решения сводится к целочисленным задачам линейного программирования. Если к условию (1) добавить такие, например, граничные условия: 2 ≤ x1 ≤ 8; 1 ≤ x2 ≤ 3 то можно видеть, что такая система решения не имеет. Отсюда следует, что задача целочисленного программирования не всегда имеет решение, т. е. она не совместна. Под целочисленным или дискретным программированием понимают такие задачи (обычно линейные), в которых искомые переменные по смыслу могут принимать только целые значения: число рабочих, разделяемых по рабочим местам; количество единиц оборудования, устанавливаемых на заданной площади, и т. п. Аналитическая задача целочисленного программирования формулируется: max(min) L =
Если n1 = n, то задачу называют полностью целочисленной; если n1 < n, то — частично целочисленной. Предположим, что задача имеет многогранник решений (рис. 1). Если наложить требование целочисленности, то допустимое множество решений выразится в систему точек и уже не будет выпуклым. Если добавить новые ограничения, связывающие внешние целочисленные точки, а затем в качестве многогранника использовать все выпуклое множество, ограниченное осями координат и новым контуром, то получим новую задачу линейного программирования со следующими свойствами: ■ новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка целая; ■ так как целевая функция достигает оптимума в угловой точке, то построением многогранника обеспечивается целочисленность оптимального решения. Таким образом, решение задач целочисленного программирования трудоемко. Поэтому по возможности лучше не накладывать ограничений целочисленности переменных. В ряде случаев задачу целочисленного программирования решают следующим образом: 1) как непрерывную задачу линейного программирования; 2) округляют переменные; 3) проверяют допустимость округленного решения; 4) если решение допустимое, то оно принимается как целочисленное. При необходимости точного решения применяют специальные методы, где учитывается, что множество решений любой целочисленной задачи — конечно. Например, в задаче с переменными x1, x2: 0 < x1 ≤ 4; 0 < xj ≤ 5. Число возможных решений 4*5 = 20. Следовательно, возможен полный перебор всех возможных сочетаний целочисленных x1, x2 и выбор из них наилучших в смысле целевой функции. Трудоемкость этого метода возрастает с ростом числа переменных и области граничных условий, и для реальных задач он неприменим. Поэтому в реальных задачах применяют методы, в которых не рассматривают все возможные альтернативы. Распространены методы отсеченийи методы возврата, среди которых наиболее известен метод ветвей и границ. Метод отсечений для программной реализации сложен.
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2018-04-12; просмотров: 651. stydopedya.ru не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда... |