Библиотека Рефераты Курсовые Дипломы Поиск
Библиотека Рефераты Курсовые Дипломы Поиск
сделать стартовой добавить в избранное
Кефирный гриб на сайте za4eti.ru

Математика Математика

Решение оптимизационной задачи линейного программирования

Чашка "Неваляшка".
Ваши дети во время приёма пищи вечно проливают что-то на ковёр и пол, пачкают руки, а Вы потом тратите уйму времени на выведение пятен с
222 руб
Раздел: Тарелки
Горшок торфяной для цветов.
Рекомендуются для выращивания крупной рассады различных овощных и цветочных, а также для укоренения саженцев декоративных, плодовых и
7 руб
Раздел: Горшки, ящики для рассады
Забавная пачка "5000 дублей".
Юмор – настоящее богатство! Купюры в пачке выглядят совсем как настоящие, к тому же и банковской лентой перехвачены... Но вглядитесь
60 руб
Раздел: Прочее

Белорусский государственный университет информатики и радиоэлектроники Факультет информационных технологий и управления Кафедра информационных технологий автоматизированных систем «К защите допускаю» Н.В. Батин “ ” 2001г. КУРСОВАЯ РАБОТА по дисциплине «Системный анализ и исследование операций» на тему: «Решение оптимизационной задачи линейного программирования» Выполнил студент гр. 920603 Журавкин А.В. Руководитель работы Батин Н.В. Минск, 2001 СОДЕРЖАНИЕ: ВВЕДЕНИЕ . .3 1. Постановка задачи оптимизации . 8 2. Построение аналитической модели . 9 3. Обоснование и описание вычислительной процедуры .11 1. Приведение задачи линейного программирования к стандартной форме . .11 2. Основная идея симлекс-метода .12 3. Двухэтапный симплекс-метод 12 4. Решение задачи оптимизации на основе симплекс-таблиц 14 1. Приведение задачи к стандартной форме . .14 2. Определение начального допустимого решения 14 3. Построение искусственного базиса . 15 4. Первый этап двухэтапного симплекс-метода .16 5. Второй этап двухэтапного метода .19 5. Анализ модели на чувствительность .22 1. Статус ресурсов . 22 2. Ценность ресурсов 22 3. Анализ на чувствительность к изменениям правых частей ограничений . .23 4. Анализ на чувствительность к изменениям коэффициентов целевой функции . 25 6. Определение оптимального целочисленного решения 26 6.1. Метод Гомори для частично целочисленных задач . .26 ЗАКЛЮЧЕНИЕ . 33 СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ . .34 УСЛОВНЫЕ СОКРАЩЕНИЯ . 35 ПРИЛОЖЕНИЕ . .36 ВВЕДЕНИЕ В настоящее время оптимизация находит применение в науке, технике и в любой другой области человеческой деятельности. Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. Поиски оптимальных решений привели к созданию специальных математических методов и уже в 18 веке были заложены математические основы оптимизации (вариационное исчисление, численные методы и др). Однако до второй половины 20 века методы оптимизации во многих областях науки и техники применялись очень редко, поскольку практическое использование математических методов оптимизации требовало огромной вычислительной работы, которую без ЭВМ реализовать было крайне трудно, а в ряде случаев - невозможно. Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например: ( количество продукции - расход сырья ( количество продукции - качество продукции Выбор компромиcного варианта для указанных свойств и представляет собой процедуру решения оптимизационной задачи. При постановке задачи оптимизации необходимо: 1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого. Приведем примеры. Типичный пример неправильной постановки задачи оптимизации: «Получить максимальную производительность при минимальной себестоимости». Ошибка заключается в том, что ставится задача поиска оптимальности 2-х величин, противоречащих друг другу по своей сути.

Правильная постановка задачи могла быть следующая: а) получить максимальную производительность при заданной себестоимости; б) получить минимальную себестоимость при заданной производительности; В первом случае критерий оптимизации - производительность а во втором - себестоимость. 2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта. 3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий. 4. Учет ограничений. Обычно оптимизируемая величина связана с экономичностью работы рассматриваемого объекта (аппарат, цех, завод). Оптимизируемый вариант работы объекта должен оцениваться какой-то количественной мерой - критерием оптимальности. Критерием оптимальности называется количественная оценка оптимизируемого качества объекта. На основании выбранного критерия оптимальности составляется целевая функция, представляющая собой зависимость критерия оптимальности от параметров, влияющих на ее значение. Вид критерия оптимальности или целевой функции определяется конкретной задачей оптимизации. Таким образом, задача оптимизации сводится к нахождению экстремума целевой функции. В зависимости от своей постановки, любая из задач оптимизации может решаться различными методами, и наоборот – любой метод может применяться для решения многих задач. Методы оптимизации могут быть скалярными (оптимизация проводится по одному критерию), векторными (оптимизация проводится по многим критериям), поисковыми (включают методы регулярного и методы случайного поиска), аналитическими (методы дифференциального исчисления, методы вариационного исчисления и др.), вычислительными (основаны на математическом программировании, которое может быть линейным, нелинейным, дискретным, динамическим, стохастическим, эвристическим и т.д.), теоретико-вероятностными, теоретико-игровыми и др. Подвергаться оптимизации могут задачи как с ограничениями, так и без них. Линейное программирование - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого начала развиваться сама дисциплина «математическое программирование». Термин «программирование» в названии дисциплины ничего общего с термином «программирование (т.е. составление программ) для ЭВМ» не имеет, так как дисциплина «линейное программирование» возникла еще до того времени, когда ЭВМ стали широко применяться при решении математических, инженерных, экономических и др. задач. Термин «линейное программирование» возник в результате неточного перевода английского «li ear programmi g». Одно из значений слова «programmi g» - составление планов, планирование. Следовательно, правильным переводом «li ear programmi g» было бы не «линейное программирование», а «линейное планирование», что более точно отражает содержание дисциплины. Однако, термин линейное программирование, нелинейное программирование и т.д. в нашей литературе стали общепринятыми. Итак, линейное программирование возникло после Второй Мировой Войны и стал быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а так же математической «стройности».

Можно сказать, что линейное программирование применимо для построения математических моделей тех процессов, в основу которых может быть положена гипотеза линейного представления реального мира: экономических задач, задач управления и планирования, оптимального размещения оборудования и пр. Задачами линейного программирования называются задачи, в которых линейны как целевая функция, так и ограничения в виде равенств и неравенств. Кратко задачу линейного программирования можно сформулировать следующим образом: найти вектор значений переменных, доставляющих экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств. Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя;оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Так, по оценкам американских экспертов, около 75% от общего числа применяемых оптимизационных методов приходится на линейное программирование. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач линейного программирования и их многочисленных модификаций. Первые постановки задач линейного программирования были сформулированы известным советским математиком Л.В.Канторовичем, которому за эти работы была присуждена Нобелевская премия по экономике. Значительное развитие теория и алгоритмический аппарат линейного программирования получили с изобретением и распространением ЭВМ и формулировкой американским математиком Дж. Данцингом симплекс-метода. В настоящее время линейное программирование является одним из наиболее употребительных аппаратов математической теории оптимального принятия решения. Для решения задач линейного программирования разработано сложное програмное обеспечение, дающее возможность эффективно и надежно решать практические задачи больших объемов. Эти программы и системы снабжены развитыми системами подготовки исходных данных, средствами их анализа и представления полученных результатов. В развитие и совершенствование этих систем вложен труд и талант многих матеметиков, аккумулирован опыт решения тысяч задач. Владение аппаратом линейного программирования необходимо каждому специалисту в области математического программирования. Линейное программирование тесно связано с другими методами математического программирования (например, нелинейного программирования, где целевая функция нелинейна). Задачи с нелинейной целевой функцией и линейными ограничениями называют задачами нелинейного программирования с линейными ограничениями. Оптимизационные задачи такого рода можно классифицировать на основе структурных особенностей нелинейных целевых функций. Если целевая функция Е - квадратичная функция, то мы имеем дело с задачей квадратичного программирования; если Е – это отношение линейных функций, то соответствующая задача носит название задачи дробно-линейного программирования, и т.д

Соответственно процесс поиска решения задачи линейного программирования, оптимального в смысле достижения Min или Max линейного критерия, сводится к последовательному перебору конечного числаP вершин выпуклого многогранника и выбору экстремального из множества значений Z, достигаемого в них. Аналогичное утверждение доказано в линейной алгебре математически строго для n-мерного пространства. Алгоритм перебора вершин n-мерного выпуклого многогранника и выбора в них экстремального значения критерия оптимальности называется симплекс-метод. В разных модификациях он известен с 1940Pг. Этот алгоритм также позволяет ответить и на вопросы о совместимости системы ограничений и о существовании решений либо же об отсутствии таковых. То есть работоспособность аппарата линейного программирования абстрактно-математически подтверждена уже более, чем 50Pлет. А слоеный пространственно ориентированный торт нам потребовался только для наглядности, предметной образности изложения, а те, кому необходимы формально-математические доказательства изложенного и практические алгоритмы решения, могут найти их в специальной литературе

1. Линейное программирование: постановка задач и графическое решение

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

3. Математические модели задач и их решение на ЭВМ

4. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА

5. Итерационные методы решения систем линейных уравнений с неединственными коэффициентами

6. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА
7. Транспортная задача и задача об использовании сырья
8. Автоматизация решения систем линейных алгебраических уравнений

9. Разработка программы для решения систем линейных уравнений

10. Решение систем линейных алгебраических уравнений (прямые методы)

11. Решение системы линейных уравнений методом Гаусса и Жордана-Гаусса

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

13. Итерационные методы решения систем линейных алгебраических уравнений

14. Методы решения систем линейных уравнений

15. Прямые методы решения систем линейных алгебраических уравнений

16. Методы решения уравнений линейной регрессии

Перчатки одноразовые "Paclan", латексные, размер S, 100 штук.
Прочные эластичные перчатки из латекса, предназначены для полной защиты рук во время уборки, приготовления пищи. Перчатки легко
492 руб
Раздел: Перчатки
Кружка фарфоровая "FIFA 2018. Забивака. Удар!", 400 мл.
Объем: 400 мл. Материал: фарфор.
358 руб
Раздел: Кружки, посуда
Шампунь-гель детский "Weleda" для волос и тела (с календулой), 200 мл.
Бережно очищает и ухаживает за чувствительной кожей и волосами малышей, деликатно удаляет молочные корочки. Не вызывает раздражения
754 руб
Раздел: Гели, мыло

17. Решение оптимизационных управленческих задач на основе методов и моделей линейного программирования

18. Разработка программных средств анализа графика функции и решение оптимизационных задач

19. Решение задач линейного программирования

20. Решение задач линейной оптимизации симплекс – методом

21. Решение задачи методами линейного, целочисленного, нелинейного и динамического программирования.

22. Решение многокритериальной задачи линейного програмирования
23. Практикум по решению линейных задач математического программирования
24. Решение задач линейного программирования

25. Решение задачи линейного программирования графическим методом

26. Симплекс метод решения задачи линейного программирования

27. Задачи линейной алгебры. Понятие матрицы. Виды матриц. Операции с матрицами. Решение задач на преобразование матриц

28. Решение и постоптимальный анализ задачи линейного программирования

29. Графический метод и симплекс-метод решения задач линейного программирования

30. Решение задачи линейного программирования симплекс-методом

31. Применение линейного программирования для решения задач оптимизации

32. Задачи по семейному праву /условие-вопрос-решение/

Магнитная игра для путешествий "Волшебный лес".
Уникальная логическая игра-головоломка для отличного времяпрепровождения и тренировки ума. Имеет компактное игровое поле с магнитными
530 руб
Раздел: Игры на магнитах
Папка для тетрадей "Кошечка", А4.
Папка для тетрадей формата A4, закрывается на молнию. Отличается вместительностью и ярким дизайном (полноцветная печать на пластике). Для
359 руб
Раздел: Папки для тетрадей
Гибкий трек "Большое путешествие", 317 деталей.
Гибкий трек "Большое путешествие" от бренда 1Toy состоит из 317 деталей, в том числе лифта, 2 машинок, пещеры и перекрестка.
2695 руб
Раздел: Треки без запуска

33. Решение транспортной задачи методом потенциалов

34. По решению прикладных задач на языке FRED

35. 10 задач с решениями программированием на Паскале

36. Графы. решение практических задач с использованием графов (С++)

37. Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)

38. Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)
39. Решение задач - методы спуска
40. Построение решения задачи Гурса для телеграфного уравнения методом Римана

41. Методы и приемы решения задач

42. Решение задач на построение сечений многогранников

43. Графы. решение практических задач с использованием графов (С++)

44. Теория вероятности решение задач по теории вероятности

45. Задача по травматологии с решением

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

47. Задачирешениями) по сопромату

48. Задачи с решениями по ценным бумагам

Записная книга "Bazar", А5, бирюзовая.
Записная книга на резинке. Формат: А5 (130x210 мм). Количество страниц: 192. Основной блок: линейка. Дополнительные разделы: телефоны,
577 руб
Раздел: Записные книжки
Чехол для телефона - кошелек, 14.5x9х3.5 см.
В Вашей необъятной сумке невозможно разыскать телефон или кошелек? Направляясь на ланч или шоппинг, Вам приходится брать с собой массивный
396 руб
Раздел: Сумочки для телефонов
Велосипед трехколесный Moby Kids "Comfort. EVA", цвет: красный.
Детский трёхколёсный велосипед Moby Kids "Comfort 10х8 EVA". В данной модели предусмотрены дополнительные функции и аксессуары,
4216 руб
Раздел: Трехколесные

49. Задачи по теории принятия решений

50. Риск в задачах линейного программирования

51. Формулы для решения задач по экономике предприятия

52. Транспортная задача линейного программирования

53. Задачи линейной алгебры

54. Решение смешанной задачи для уравнения
55. К решению нелинейных вариационных задач
56. План-конспект урока Математическое моделирование при решении экологических задач

57. Решение задач с помощью ортогонального проектирования

58. Решения смешанной задачи для уравнения гиперболического типа методом сеток

59. Приложения определенного интеграла к решению некоторых задач механики и физики

60. Применение движений к решению задач

61. О методике решения задач на относительность движения при изучении основ кинематики в 9 классе общеобразовательной школы

62. Построения коллектива с акцентом на решение задач или на поддержание отношений в нем

63. Пример решения задачи по механике

64. Эвристические методы решения творческих задач

Комод четырехсекционный "Орнамент" (белый/мраморный).
Комод поможет вам поддерживать порядок и сделает интерьер уютнее. В нём найдётся место для канцтоваров, игрушек, сувениров, текстиля и
1302 руб
Раздел: Комоды
Карниз для ванной комнаты металлический, раздвижной, 210 см, с кольцами (металлик).
Карниз с 12 пластиковыми кольцами в наборе. Стальная труба с пластиковой фурнитурой. Силиконовые вставки в фурнитуру предотвращают
404 руб
Раздел: Штанги и кольца
Настольная игра "Остров обезьян".
В зависимости от количества участников выбирайте нужное число обезьянок для путешествия по лианам за фруктами. Их должно быть на одну
518 руб
Раздел: Игры с фигурками

65. Влияние использования схем, чертежей, иллюстраций на формирование ЗУН при обучении младших школьников решению задач на движение

66. Пути повышения эффективности обучения решению задач

67. Структура и динамика процессов решения задач

68. Развитие профессионального оперативного мышления будущего учителя в ходе решения психолого-педагогических задач

69. От решения задач к механизмам трансляции деятельности

70. Нечеткая логика при решении криминологических задач
71. Дифференциальные уравнения движения точки. Решение задач динамики точки
72. Решение обратных задач теплопроводности для элементов конструкций простой геометрическо формы

73. Решение задач по химии

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

75. Задачи по экономике с решениями

76. Математическая постановка транспортной задачи линейного программирования

77. Постановка и разработка алгоритма решения задачи Учёт основных средств

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

79. Настройка и решение обратной петрофизической задачи

80. Применение Информационной Системы «GeoBox» для решения задач автоматизации строительства скважин

Кружка "Лучший Папа", с рисунком.
Качественные керамические кружки с оригинальным рисунком, выполненным в процессе производства (подглазурное нанесение). Упаковка: белый
372 руб
Раздел: Кружки
Кондиционер для белья "Mitsuei", с ароматом белых цветов, 2 л.
Кондиционер для белья придает невероятную мягкость вашим вещам. Идеально подходит для всех видов ткани, даже для деликатных, таких как
371 руб
Раздел: Ополаскиватели, кондиционеры
Шторка антимоскитная универсальная, с магнитными замками ТД7-009.
Размеры: 100х220 см. Препятствует проникновению насекомых. Не нарушает естественную циркуляцию воздуха. Подходит для любых типов дверных
424 руб
Раздел: Сетки противомоскитные

81. Решение задачи одномерной упаковки с помощью параллельного генетического алго-ритма

82. Задачи по моделированию с решениями

83. Расчет экономической эффективности применения ПЭВМ для решения задачи

84. Решение задачи о кратчайшем маршруте

85. Общая схема решения задачи на персональном компьютере

86. Решение текстовых задач
87. Основные подходы к оценке стоимости бизнеса и перспективы их применения к решению задач управления инновационными предприятиями
88. Решение задач по дисциплине "Страхование"

89. Решение задач по управленческому учету

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

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

92. Алгоритмы численного решения задач

93. Использование информатики для решения экономических задач

94. Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации

95. Подготовка и решение на ПК задач с разветвлением

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

Игра "Городки".
Игра в городки заключается в выбивании фигур, построенных из пяти городков, с ограниченной площадки, называемой "городом",
378 руб
Раздел: Городки
Конструктор "Цветной", 65 деталей.
Конструктор - это игра развивающая кругозор, знакомящая с различными формами и цветами, а также развивающая воображение Вашего ребёнка.
584 руб
Раздел: Деревянные конструкторы
Настольная игра "Ответь за 5 секунд. Детская".
5 секунд на каждый вопрос. Попробуем? Назовите две вещи на букву Р! Два круглых предмета! Три способа поздороваться! Три ближайших улицы!
1490 руб
Раздел: Игры со словами

97. Принципы разработки алгоритмов и программ для решения прикладных задач

98. Разработка формата хранения данных программ и решение задач

99. Решение задач исследования операций

100. Решение задач моделирования и оптимизации с помощью программ Excel и Mathcad


Поиск Рефератов на сайте za4eti.ru Вы студент, и у Вас нет времени на выполнение письменных работ (рефератов, курсовых и дипломов)? Мы сможем Вам в этом помочь. Возможно, Вам подойдет что-то из ПЕРЕЧНЯ ПРЕДМЕТОВ И ДИСЦИПЛИН, ПО КОТОРЫМ ВЫПОЛНЯЮТСЯ РЕФЕРАТЫ, КУРСОВЫЕ И ДИПЛОМНЫЕ РАБОТЫ. 
Вы можете поискать нужную Вам работу в КОЛЛЕКЦИИ ГОТОВЫХ РЕФЕРАТОВ, КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ, выполненных преподавателями московских ВУЗов за период более чем 10-летней работы. Эти работы Вы можете бесплатно СКАЧАТЬ.