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

Экономика и Финансы Экономика и Финансы     Экономико-математическое моделирование Экономико-математическое моделирование

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

Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение
Совок большой.
Длина 21,5 см.
22 руб
Раздел: Совки, лопаты, грабли
Гуашь "Классика", 12 цветов.
Гуашевые краски изготавливаются на основе натуральных компонентов и высококачестсвенных пигментов с добавлением консервантов, не
177 руб
Раздел: 7 и более цветов

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ «Приднестровский государственный университет им. Т.Г. Шевченко» Рыбницкий филиал Кафедра физики, математики и информатики Курсовая работа по дисциплине: «Численные методы» на тему: «Использование линейного программирования для решения задач оптимизации» Выполнила: студентка II курса; 230й группы специальности: «Информатика с доп. специальностью английский язык» Нистор А.Г. Проверила: преподаватель Балан Л.А. г. Рыбница 2007 год Оглавление Введение I.Теоретический раздел 1.1 Понятие о линейном программировании. Формулировка задачи линейного программирования 1.2 Виды задач линейного программирования 1.3 Методы решения задач линейного программирования II. Практический раздел 2.1 Решение транспортной задачи 2.2 Решение производственной задачи Заключение   Введение Оптимизация как раздел математики существует достаточно давно и обозначает выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином &quo ;оптимизация&quo ; в литературе обозначают процесс или последовательность операций, позволяющих получить уточнённое решение. Хотя конечной целью оптимизации является отыскание наилучшего или &quo ;оптимального&quo ; решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. По этому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто. Практика порождает все новые и новые задачи оптимизации, причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Другими словами, жизнь заставляет развивать математический аппарат оптимизации. Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека. Нет, пока такой теории, которая учла бы любые особенности функций, описывающих постановку задачи. Следует отдавать предпочтение таким методам, которыми проще управлять в процессе решения задачи. Таким образом целью данной курсовой работы является : освоить навыки использования линейного программирования для решения задач оптимизации. Для этого были поставлены следующие задачи : 1)Изучить теоретические сведения, необходимые для решения задач оптимизации методом линейного программирования. 2)Изучить методы решения задач линейного программирования. 3)Решить поставленные задачи, используя рассмотренные методы линейного программирования. I. Теоретический раздел & bsp; 1.1 Понятие о линейном программировании. Формулировка задачи линейного программирования Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их.

Термин «программирование» нужно понимать в смысле «планирования». Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации. Формулировка задачи линейного программирования Нужно максимизировать при условиях при i = 1, 2, 3, . . ., m. Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя ее во всех остальных равенствах и неравенствах (а также в функции f). Такую задачу называют &quo ;основной&quo ; или &quo ;стандартной&quo ; в линейном программировании. & bsp; 1.2 Виды задач линейного программирования Поток и паросочетание Рассмотрим задачу о максимальном паросочетании: есть несколько юношей и девушек; для каждой пары известно, любят ли они друг друга. Нужно поженить максимальное число пар. Введем переменные xij — они соответствуют паре из i-того юноши и j-той девушки. Введем ограничения: x ij ≥ 0, x ij ≤ 1, , , . Можно показать, что среди оптимальных решений этой задачи найдется целочисленное. Переменные, равные 1, будут соответствовать парам, которые следует поженить. Вторая важная задача — максимальный поток. Пусть имеется граф (с ориентированными ребрами), в котором для каждого ребра указана его пропускная способность. И заданы 2 вершины: сток и исток. Нужно указать для каждого ребра, сколько через него будет протекать жидкости (не больше его пропускной способности) так, чтобы максимизировать суммарный поток из стока в исток (жидкость не может появляться или исчезать во всех вершинах, кроме стока и истока). Возьмем в качестве переменных xi — количество жидкости, протекающих через i-тое ребро. Тогда , , где ci — пропускная способность i-того ребра. Эти неравенства надо дополнить равенством количества втекающей и вытекающей жидкости для каждой вершины, кроме стока и истока. В качестве функции f естественно взять разность между количеством вытекающей и втекающей жидкости в истоке. Обобщение предыдущей задачи — максимальный поток минимальной стоимости. В этой задаче даны стоимости для каждого ребра и нужно среди максимальных потоков выбрать поток с минимальной стоимостью. Эта задача сводится к 2 задачам линейного программирования: сначала нужно решить задачу о максимальном потоке, а потом добавить к этой задаче ограничение , где m — величина максимального потока, и решить задачу с новой функцией f(x) — стоимостью потока. Все эти задачи могут быть решены быстрее, чем с помощью общих алгоритмов решения задач линейного программирования, за счет особой структуры уравнений и неравенств. Транспортная задача Имеется некий однородный груз, который нужно перевести с складов на m заводов. Для каждого склада i известно, сколько в нем находится груза ai, а для каждого завода известна его потребность bj в грузе. Стоимость перевозки пропорциональна расстоянию от склада до завода (все расстояния cij от i-го склада до j-го завода известны). Требуется составить наиболее дешевый план перевозки.

Решающими переменными в данном случае являются xij — количества груза, перевезенного из i-го склада на j-й завод. Ограничениями будут и . Целевая функция имеет вид: , которую надо минимизировать. Игра с нулевой суммой Есть матрица A размера . Первый игрок выбирает число от 1 до , второй — от 1 до m. Затем они сверяют числа и первый игрок получает aij очков, а второй ( − aij) очков (i — число, выбранное первым игроком, j — вторым). Нужно найти оптимальную стратегию первого игрока. Пусть в оптимальной стратегии число i нужно выбирать с вероятностью pi. Тогда оптимальная стратегия является решением следующей задачи линейного программирования: , , , (), в которой нужно максимизировать функцию . c в оптимальном решении будет математическим ожиданием выигрыша первого игрока в наихудшем случае. & bsp; 1.3 Методы решения задач линейного программирования Симплекс-метод Сведём задачу линейного программирования к просмотру крайних точек допустимого множества. Именно направленный перебор крайних точек допустимого множества и осуществляется в симплекс-методе, изложенном ниже. Рассмотрим связь между геометрическим понятием крайней точки и его аналитической интерпретацией. Для ограниченного множества , описанного с помощью системы неравенств крайними точками являются решения невырожденных подсистем вида:  (1) где - некоторое подмножество индексов и и матрица, составленная из строк-векторов аi, неособенная. Обозначим единственное решение системы (3) через x. Предположим теперь, что существуют и такие, что для  Поскольку для & bsp; то, очевидно, . В силу единственности решения (3) . С другой стороны, если -- крайняя точка, то можно обозначить через множество равенств Обозначим через матрицу, составленную из строк Если предположить, что , то существует нетривиальное нуль-пространство 2) & bsp; Выбирая достаточно малым по норме, можно добиться того, что для вектор или для и для достаточно малых . Аналогично можно показать, что при этом и . Так как  то получаем противоречие с определением крайней точки. Для направленного просмотра крайних точек допустимого многогранника применяют симплекс-метод, предложенный Дж. Данцигом и затем усовершенствованный многочисленными математиками. Основная идея метода заключается в разбиении множества переменных x = x1, x2, . . ., x на базисные и небазисные . Не умаляя общности, можно считать, что базисные переменные являются первыми в векторе x, т.е. x = (xB, x ). Система ограничений канонической формы задачи линейного программирования может быть соответственно переписана в виде: (3) Предположим, что матрица имеет полный ранг, т.е.  - невырожденная. Тогда из равенства (5) следует 4) & bsp; Целевая функция задачи ЛПР также может быть разбита на базисную и не базисную части: Подстановка (6) дает 5) & bsp; Предположим, что мы находимся в некоторой начальной точке со значением целевой функции Каким образом можно уменьшить далее значение целевой функции? Из соотношения (5) следует, что для этого достаточно сделать положительными те компоненты вектора , которым соответствуют отрицательные значения координат вектора модифицированных стоимостей сохраняя при этом неотрицательность базисных переменных .

РОБОТИЗАЦИЯ в психологическом аспекте использование интеллектуальных роботехнических комплексов, функциональные особенности коих состоят в достаточно гибком реагировании на изменения в рабочей зоне. В таких комплексах выделяются три основные взаимосвязанные подсистемы: 1) подсистема восприятия обеспечивает прием информации из рабочей зоны и может реализоваться на базе нескольких видов сенсоров: тактильного, локационного, силомоментного, визуального и звукового; 2) подсистема представления знаний является ведущей и обеспечивает накопление, корректировку и использование знаний в решении задач; 3) подсистема планирований и исполнения действий выполняет актуальное преобразование обобщенного плана действий в последовательность операций требуемой амплитуды и скорости. Приведенная структура функций говорит о потребности разработчиков этих комплексов иметь достоверные психологические знания об аналогичных процессах, реализуемых человеком. Все психологические явления, выявленные в экспериментальных исследованиях процессов сенсорно-познавательных, построения движений, применяются в новых разработках, а проблемы роботизации влияют на содержание исследований психологических

1. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

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

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

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

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

6. Графическое решение задачи линейного программирования в экономике
7. Решение задачи линейного программирования симплекс-методом
8. Решение задач линейной оптимизации симплекс – методом

9. Примеры решения задач по программированию

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

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

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

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

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

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

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

Пленка для горячего ламинирования, глянцевая, 154х216 мм, А5.
Пленка для горячего ламинирования, глянцевая, антистатичная. Размер: 154х216 мм. Толщина: 80 мкм. Формат: А5. В упаковке: 100 штук.
459 руб
Раздел: Тонеры, термопленки
Настольная игра "Имаджинариум".
Каждый игрок выбирает себе слона и набор карточек для голосования того же цвета, что и слон. Карточек для голосования семь. Вам пригодится
1671 руб
Раздел: Карточные игры
Настольная игра "Поле чудес".
101 слово в каталоге! Настольная игра-викторина для детей от 5-ти лет. В наборе: пластиковое поле-барабан, карточки.
572 руб
Раздел: Викторины

17. Решение транспортной задачи линейного программирования в среде MS Excel

18. Задачи линейного программирования

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

20. Периферийное устройство ПЭВМ, Характеристика этапов подготовки и решения задач на ПЭВМ в любой системе программирования. Электронная почта, особенности применения

21. Задача квадратичного программирования с параметром в правых частях ограничений и ее применение

22. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ ПЯТИТОЧЕЧНЫМ МЕТОДОМ АДАМСА – БАШФОРТА
23. Итерационные методы решения систем линейных уравнений с неединственными коэффициентами
24. Роман о повседневной жизни обыкновенных людей (по роману "Обыкновенная история")

25. Мелихово в творческой и повседневной жизни А.П. Чехова

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

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

28. Конфликты в повседневной жизни

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

30. 5 различных задач по программированию

31. Решение систем линейных дифференциальных уравнений пятиточечным методом Адамса – Башфорта

32. Паблик рилейшнз в повседневной жизни

Ручка-роллер для левшей STABILO ‘s move easy ergo + 3 стержня, чернила синие.
Корпус оранжево-черный, цвет чернил синий. В прозрачной тубе: ручка и 3 стержня синего цвета. Товары коллекции STABILO EASYergonomics
753 руб
Раздел: Ручки-роллеры
Спагетница "Феттуччине".
Если Вы являетесь поклонником итальянской кухни, то с помощью уникального приспособления, спагетницы «Фетуччине» Вы легко сможете
1658 руб
Раздел: Измельчители, приспособления для резки
Увлекательная настольная игра "Турбосчет".
Настольная игра "Турбосчёт" - весёлая и очень динамичная обучающая игра, которая мгновенно увлекает и детей, и взрослых. Правила
450 руб
Раздел: Математика, цифры, счет

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

34. Программирование решения задач

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

36. Решение системы линейных уравнений

37. Численное решение системы линейных алгебраических уравнений методом Гаусса

38. Численные методы решения систем линейных уравнений
39. Повседневная жизнь средневековой Руси (на основе нравоучительной литературы)
40. Задачи математического программирования

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

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

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

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

45. Применение подобия к решению задач

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

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

48. Применение программного комплекса AnsysIcem к решению задач химической промышленности

Расческа "Pferdefreunde", 17 см.
Коричневая расческа Pferdefreunde легко помещается в маленькой ладошке. Ее жесткость позволяет не травмировать кожу головы ребенка. Общие
564 руб
Раздел: Расчески, щетки для волос
Горшок детский с крышкой "Little king", голубой.
Горшок детский "Little king" с крышкой предназначен для постепенного обучения ребенка навыкам самостоятельной гигиены.
455 руб
Раздел: Горшки-стульчики
Батарейки "Duracell", AA LR6, 1,5В, 18 штук.
Алкалиновые. Напряжение: 1,5В. Типоразмер: AA LR6. В комплекте: 18 штук.
806 руб
Раздел: Батарейки

49. Применение методов линейного программирования в военном деле. Симплекс-метод

50. Применение линейного программирования для решения экономических задач (оптимизация прибыли)

51. Линейное и динамическое программирование

52. O Л. В. Канторовиче и линейном программировании

53. Линейное программирование

54. Линейное программирование симплекс-методом Данцига
55. Линейная алгебра и математическое программирование
56. Двойственность в линейном программировании

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

58. Линейное программирование

59. Структура и программирование ПЛИС фирмы Altera в САПР Quartus II, её применение в лабораторном стенде

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

61. Применение методов нейро-лингвистического программирования в обучении

62. Разработка программной и аппаратной поддержки к методическим указаниям "Программирование микроконтроллеров"

63. Языки и технология программирования. Начальный курс /Pascal/

64. Объектно-ориентированное программирование на С с использованием библиотеки OpenGL

Карандаши "ECO. Замок", 24 цвета, с точилкой.
Набор шестигранных цветных карандашей. Корпус покрыт лаком на водной основе – он безопасен как для окружающей среды, так и для детей.
533 руб
Раздел: 13-24 цвета
Настольная игра "Барабашка (Geistestesblitz)".
У вас в руках оказались фотокарточки, сделанные каким-то странным фотоаппаратом: фотографируя всего пять предметов, он постоянно путает их
1020 руб
Раздел: Внимание, память, логика
Пазлы Maxi "Карта мира" (40 элементов).
Пазл для малышей "Карта мира" состоит из крупных элементов. Размер собранной картинки - 59х40 см. Средний размер элементов - 8х7,4 см.
326 руб
Раздел: Пазлы (Maxi)

65. Объективное программирование

66. Обучение начальных курсов методам программирования на языке Turbo Pascal

67. Системное программирование

68. Математическое программирование

69. Системы программирования

70. Языки программирования
71. Понятие, назначение и составные элементы систем программирования
72. Лекции по высокоуровневым методам информатики и программированию

73. Курсовая работа по основам программирования. Игра "Паровоз"

74. VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования

75. Помощь в обучении программированию

76. Программирование на С++

77. Сравнительный анализ языков программирования JavaScript и VBScript

78. Возможности системы программирования Delphi для создания пользовательского интерфейса

79. Программирование на Delphi

80. Программирование логической игры на visual basic

Вешалка-плечики "Стандарт", 5 штук, дерево, перекладина, 45 см, цвет темно-коричневый.
Материал: натуральное дерево. Размер: 45 см. С перекладиной. Невыкручивающийся крючок. Лакированная. В комплекте: 5 штук. Цвет: темно-коричневый.
380 руб
Раздел: Вешалки-плечики
Зонт "Прозрачный купол", красная окантовка.
Небольшой милый зонтик-трость с глубоким прозрачным куполом из ПВХ плёнки. Длина дуги 56 см, диаметр 87см.
464 руб
Раздел: Зонты-трости
Глобус физико-политический, диаметр 250 мм, с подсветкой, на подставке из пластика.
Диаметр: 250 мм. Масштаб: 1:50000000. Материал подставки: пластик. Цвет подставки: прозрачный. Размер коробки: 260х260х360 мм. Мощность:
757 руб
Раздел: Глобусы

81. Учебник по программированию в среде С++ Builder

82. Учебник по технологии программирования

83. Практика оператора (WINDOWS 95, MICROSOFT WORD 97, MATHCAD, ЯЗЫКИ ПРОГРАММИРОВАНИЯ, ЭЛЕКТРОННЫЕ КНИГИ, VISIO, Norton Utilites 3.0 for Windows 95)

84. Отчет по практическим занятиям по курсу прикладные задачи программирования на тему Windows, Microsoft Word и Microsoft Excel

85. Руководство по программированию на HTML

86. Переходные процессы в линейных цепях
87. Расчёт частотных и временных характеристик линейных цепей
88. СИНГУЛЯРНОЕ РАЗЛОЖЕНИЕ В ЛИНЕЙНОЙ ЗАДАЧЕ МЕТОДА НАИМЕНЬШИХ КВАДРАТОВ

89. Программированное обучение и контроль по физиологии

90. Расчет линейных цепей методом топологических графов

91. Определение линейных и угловых перемещений параметрическими измерительными преобразователями

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

93. Измерение больших линейных геометрических размеров

94. Технология производства, прогнозирования, программирования и планирования урожаев

95. Линейный ускоритель

96. Программирование и планирование деятельности

Автомобиль-каталка "Джип" №2.
Игрушка без звукового модуля и гудка. Под сидением имеется отсек дл игрушек. Размер: длина - 62 см, ширина - 28 см, высота - 42 см.
1765 руб
Раздел: Каталки
Кондитерский шприц с насадками "Mayer & Boch" (16 предметов).
Набор состоит из 16 предметов: мешок кондитерский; 14 насадок; кондитерский мешок - уплотнитель (для прикручивания насадок к мешку).
706 руб
Раздел: Кондитерские принадлежности
Сетка магнитная для дверей от насекомых "Маскитоф".
Сетка для дверей "Маскитоф" встанет нерушимой преградой между Вашим домом и насекомыми. Чтобы избавиться от комаров и мух,
367 руб
Раздел: Сетки противомоскитные

97. Методы экономического программирования

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

99. Принципы измерения расстояний и линейных перемещений

100. Интегрирование линейного дифференциального уравнения с помощью степенных рядов


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