Студопедия

КАТЕГОРИИ:

АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Целочисленное программирование




КУРСОВАЯ РАБОТА

по дисциплине «Математические методы»

 

Тема: «Специальные задачи линейного программирования»

 

Выполнил:

студент 3 курса группы БП2-118

Ланин В.О.

 

Руководитель

Белгородцева Н.А.

Оценка:________________

Дата защиты:___________

 

 

2011


ФГОУ СПО «Омский государственный промышленно-экономический колледж»

Экономическое отделение

 

 

Задание для курсовой работы

студента Ланина Виталия Олеговича, группа БП2-118

                  

 

1. Тема курсовой работы: «Специальные задачи линейного программирования»

утверждена на заседании цикловой комиссии

протокол №    от « »        20г.

 

Срок сдачи курсового проекта « »        20г.      

 

Перечень вопросов, подлежащих исследованию или разработке:

А) Целочисленное программирование

- формулирование в Древней Греции Диофантом (II-III вв.) уравнения, в котором искомые переменные целые;

- какие задачи называют задачами целочисленного программирования;

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

- привести примеры задач целочисленного или дискретного программирования;

- методы отсечений и методы возврата, метод ветвей и границ;

Б) Метод ветвей и границ

- какая задача называется непрерывной;

- методом ветвей и границ решить задачу:

                                

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

В) Задача выбора вариантов

- какие переменные называют булевыми, в честь кого они получили такое название;

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

Для получения результата в виде максимально возможной прибыли необходимы два вида ресурсов: материальные и трудовые. Возможны четыре варианта расхода ресурсов и получения прибыли (табл.)

     Требуется выбрать, какие варианты принять для реализации при условии, чтобы общее число принятых вариантов не превышало трёх ( ).

Показатели

Варианты

Наличие

1 2 3 4
Прибыль, д. е./ед. 65 80 90 210 -
Материальные ресурсы 200 180 240 250 800
Трудовые ресурсы 10 15 22 28 50

Г) Дискретное программирование

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

Показатели

Изделия

Наличие

ресурса

спинка дивана подлокотники кресла Ножка стула
Цена, д. е./ед. 20 6 8 -
Древесина 10 5 3 206
Трудозатраты 2 7 4 100
Спрос 10 8 12 -
  х1 х2 х3 bi

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

Д) Методы решения дискретных задач

- как решаются задачи дискретного программирования методом ветвей и границ;

- решить систему методом сплошного перебора:

- какую последовательность действий предполагает метод фильтрующего ограничения;

- что такое фильтр;

- какой фильтр называют адаптивным;

 

 

Руководитель курсовой работы ___________________Подпись, дата

 

Зав. отделением                   ___________________Подпись, дата

 

Задание принял к исполнению ___________________Подпись, дата

 


Федеральное государственное образовательное учреждение

среднего профессионального образования

«Омский промышленно-экономический колледж»

 

 

РЕЦЕНЗИЯ №____

 

На курсовую работу

Студента             Ланина Виталия Олеговича                      гр. БП2-118

По                                   математическим методам                                          _                         

 

на тему «Специальные задачи линейного программирования»

« »        20г.

 

    Рецензент_________________________

 

 

____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________


План-график выполнения курсовой работы

 

 

Студент Ланин Виталий Олегович, группа БП2-118

                                                             

Тема курсовой работы «Специальные задачи линейного программирования»

 

 

утверждена на заседании цикловой комиссии от ____________ протокол №______

 

 

Этапы работы Сроки выполнения Вид отчётности Отметка о выполнении
Подбор и анализ литературы 20.02 – 5.03    
Написание основной части 6.03 – 20.03    
Написание заключительной части 20.03 – 2.04    
Анализ проделанной работы 2.04 – 3.04    
Проверка  4.04    

 

 

Дата__________________                      Подпись студента_______________

 

 

Дата__________________                      Подпись руководителя___________


 





Содержание

Содержание. 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 не претендует на авторское право материалов, которые вылажены, но предоставляет бесплатный доступ к ним. В случае нарушения авторского права или персональных данных напишите сюда...