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

Компьютеры, Программирование Компьютеры, Программирование

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

Браслет светоотражающий, самофиксирующийся, желтый.
Изготовлены из влагостойкого и грязестойкого материала, сохраняющего свои свойства в любых погодных условиях. Легкость крепления позволяет
66 руб
Раздел: Прочее
Ручка "Шприц", желтая.
Необычная ручка в виде шприца. Состоит из пластикового корпуса с нанесением мерной шкалы. Внутри находится жидкость желтого цвета,
31 руб
Раздел: Оригинальные ручки
Фонарь садовый «Тюльпан».
Дачные фонари на солнечных батареях были сделаны с использованием технологии аккумулирования солнечной энергии. Уличные светильники для
106 руб
Раздел: Уличное освещение

Федеральное агентство по образованию РФ Федеральное государственное образовательное учреждение Среднего профессионального образования Барнаульский строительный колледж Курсовая работа. По дисциплине: «Математические методы» На тему: «Решение задач линейного программирования симплекс методом» Выполнил: Нунгесер М.В. Специальность: ПОВТ Группа: 0881 Преподаватель: Клепикова Н.Н. Барнаул 2010 Содержание:Введение Линейное программирование Симплекс метод Постановка задачи Разработка алгоритма Решение задачи Программная реализация на языке Delphi Приложение Заключение Список используемой литературы Введение В последние годы в прикладной математике большое внимание уделяется новому классу задач оптимизации, заключающихся в нахождении в заданной области точек наибольшего или наименьшего значения некоторой функции, зависящей от большого числа переменных. Это так называемые задачи математического программирования, возникающие в самых разнообразных областях человеческой деятельности и прежде всего в экономических исследованиях, в практике планирования и организации производства. Изучение этого круга задач и методов их решения привело к созданию новой научной дисциплины, получившей позднее название линейного программирования. В конце 40-х годов американским математиком Дж. Данцигом был разработан эффективный метод решения данного класса задач – симплекс-метод. К задачам, решаемых этим методом в рамках математического программирования относятся такие типичные экономические задачи как «Определение наилучшего состава смеси», «Задача об оптимальном плане выпуска продукции», «Оптимизация межотраслевых потоков», « Задача о выборе производственной программы», «Транспортная задача», «Задача размещения», «Модель Неймана расширяющейся экономики» и другие. Решение таких задач дает большие выгоды как народному хозяйству в целом, так и отдельным его отраслям. Решение задач математического программирования при помощи симплекс-метода традиционными способами требует затрат большого количества времени. В связи с бурным развитием компьютерной техники в последние десятилетия естественно было ожидать, что вычислительная мощность современных ЭВМ будет применена для решения указанного круга задач. Линейное программированиеЛинейное программирование - математическая дисциплина, посвящённая теории и методам решения задач об экстремумах линейных функций на множествах -мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно - основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно -линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Математическая формулировка задачи линейного программирования Нужно определить максимум линейной целевой функции (линейной формы)при условиях Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от них можно избавиться, последовательно выражая одну переменную через другие и подставляя её во всех остальных равенствах и неравенствах (а также в функции f).

Такую задачу называют «основной» или «стандартной» в линейном программировании. Наиболее известным и широко применяемым на практике для решения общей задачи линейного программирования (ЛП) является симплекс метод. Симплекс метод Симплекс метод - метод линейного программирования, который реализует рациональный перебор базисных допустимых решений, в виде конечного итеративного процесса, необходимо улучшающего значение целевой функции на каждом шаге. Применение симплекс-метода для задачи линейного программирования предполагает предварительное приведение ее формальной постановки к канонической форме с неотрицательными переменными: (X1, ., X ), где требуется минимизация линейной целевой функции при m линейных ограничениях типа равенств. Среди переменных задачи выбирается начальный базис из m переменных, для определенности (X1, ., Xm), которые должны иметь неотрицательные значения, когда остальные ( -m) свободные переменные равны 0. Целевая функция и ограничения равенства преобразуются к диагональной форме относительно базисных переменных, переменных, где каждая базисная переменная входит только в одно уравнение с коэффициентом 1. Данная формальная модель задачи линейного программирования обычно задается в форме, так называемой симплекс-таблицы, удобной для выполнения операций симплекс-метода: Симплекс-таблица 1 X1 X2 . Xm Xm 1 . X X0 A0,0 0 0 . 0 A0,m 1 . A0, X1 A1,0 1 0 . 0 A1,m 1 . A1, X2 A2,0 0 1 . 0 A2,m 1 . A2, . . . . . . . . . Xm Am,0 0 0 . 1 Am,m 1 . Am, Верхняя строка симплекс-таблицы представляет целевую функцию задачи. Каждая строка симплекс-таблицы, кроме первой, соответствует определенному ограничению-равенству задачи. Свободные члены ограничений составляют крайний левый столбец таблицы. Слева от таблицы записаны текущие базисные переменные (X1, ., Xm). Сверху от таблицы приведен набор всех переменных задачи, где Xm 1, ., X - свободные переменные задачи. На начальном шаге алгоритма симплекс-метода должно быть выбрано базисное допустимое решение (X1, ., Xm) &g ;= 0 при Xj = 0 (j = m 1, .,  ), следовательно, все свободные члены ограничений Ai,0 &g ;= 0 (i = 1, ., m). Когда это условие выполнено, симплекс-таблица называется прямо-допустимой, так как в этом случае базисные переменные, равные Ai,0, определяют допустимое решение прямой задачи линейного программирования. Если все коэффициенты целевой функции A0,j &g ;= 0 (j = 1, ., m), то симплекс-таблица называется двойственно-допустимой, поскольку соответствующее решение является допустимым для двойственной задачи линейного программирования. Если симплекс-таблица является одновременно прямо и двойственно допустимой, т.е. одновременно все Ai,0 &g ;= 0 и A0,j &g ;= 0, то решение оптимально. Действительно, поскольку допустимыми являются лишь неотрицательные значения управляемых параметров, то изменение целевой функции за счет вариации свободных переменных, через которые она выражена, возможно только в сторону увеличения, т.e. будет ухудшаться. Если среди ее коэффициентов имеются A0,j &l ; 0, то значение целевой функции еще можно уменьшить (т.e. улучшить), увеличивая значение любой свободной переменной Xj с отрицательным коэффициентом A0,j при побочном уменьшении базисных переменных, чтобы оставались справедливы ограничения задачи.

Теоретически можно использовать любую свободную переменную Xj с A0,j &l ; 0, но на практике обычно действуют в соответствии со стратегией наискорейшего спуска, выбирая минимальный элемент A0,p &l ; 0 из всех отрицательных A0,j &l ;& bsp0:A0,p = mi A0,j &l ; 0. jСтолбец p симплекс-таблицы, соответствующий выбранному коэффициенту A0,p &l ; 0, называется ведущим столбцом. Свободная переменная ведущего столбца должна быть введена в базис вместо одной из текущих базисных переменных. Очевидно, из базиса следует исключить такую переменную Xq, которая раньше других обращается в нуль при увеличении переменной Xp ведущего столбца. Её индекс легко определить, если среди положительных элементов ведущего столбца p найти элемент, минимизирующий отношение (Ai,0 / Ai,p): Aq,0Ai,0 ------ = mi ------ , i = 1,.,m. Aq,p i Ai,p Элемент Aq,p называется ведущим элементом, cтрока q симплекс-таблицы, содержащая ведущий элемент, называется, соответственно, ведущей строкой. Переменная ведущей строки Xq заменяется в базисе переменной ведущего столбца Xp и становится свободной переменной с значением 0, в то время как новая базисная переменная Xp достигнет максимально возможного значения, равного: max Xp = ( Aq,0 / Aq,p). После указанного взаимообразного обмена переменными Xp и Xq между наборами свободных и базисных переменных нужно модифицировать исходную каноническую модель задачи путем приведения ее к диагональной форме относительно нового множества базисных переменных. Для указанного преобразования можно формально использовать процедуру исключения Гаусса, которая, как известно, состоит из двух элементарных операций, применяемых к системе алгебраических уравнений ( в данном случае ограничений - равенств): умножение уравнения E1(X) = 0 на константу K1 и замена уравнения E1(X) = 0 уравнением K1 E1(X) = 0; сложение уравнений E1(X) = 0 и E2(X) = 0 c последующей заменой уравнения E2(X) = 0 уравнением E1(X)   E2(X) = 0. Исключения Гаусса позволяют привести систему уравнений к диагональной форме относительно желаемого множества переменных. В данном случае исключение Гаусса применяется так, чтобы все элементы симплекс-таблицы в ведущем столбце, кроме ведущего элемента Aq,p, стали нулевыми, а ведущий элемент стал равным единице: Ai,p = 0, если i не равно q и Ai,p = 1, если i = q. Указанные шаги симплекс-метода повторяются, пока не будет получена симплекс-таблица, которая одновременно является прямо и двойственно допустимой. Если положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой перебор базисных допустимых решений. Однако, трудные для симплекс метода задачи на практике встречаются крайне редко, что объясняет широкое распространение и большую популярность данного метода линейного программирования по сравнению с другими подходами.

Иными словами, линейное программирование это метод математического представления планирования возможно лучшего размещения ограниченных ресурсов в случаях, когда применяемая модель использует линейные функции. Линейное программирование как техника решения подобных проблем была разработана Джорджем Дантцигом в 1947 году как способ помочь решению военных проблем, возникших у военно-воздушных сил США. Его открытие простой метод в сочетании с вычислительными способностями компьютеров обеспечивал ответ на множество прежде неразрешимых проблем планирования, возникавших у властей и у бизнеса. Модель может быть выражена как максимизация линейных ограничений. Рассмотрим формулирование следующего совсем упрощенного примера, в котором рекламодатель может использовать приемы линейного программирования с целью нахождения лучшей комбинации размещения в трех различных СМИ. Если рекламодатель желает максимизировать количество невзвешенных показов путем покупки рекламы в одном ежемесячном журнале (v1) и двух еженедельных изданиях (v2 и v3), то тогда функция может быть выражена следующим образом: совокупная невзвешенная стоимость показов (Total unweighted exposure value UEV) = aUEV + bUEV + cUEV, где a, b и c номер размещения в v1, v2 и v3, соответственно

1. Решение задач симплекс-методом

2. Совершенствование методов проектирования кораблей и обоснование проектных решений

3. Теория принятия решений: математические методы для выбора специалиста на должность администратора сети

4. Методы проведения экспертиз при разработке управленческих решений

5. Математические методы в решении экономических задач

6. Алгоритм решения обратной задачи вихретокового контроля (ВТК)
7. Алгоритм решения задач
8. Математические методы и модели в конституционно-правовом исследовании

9. Методы размещения и трассировки печатных плат на примере модуля памяти

10. Анализ и методы оценки конкурентоспособности товаров и услуг регионального рынка (На примере производства полиграфической продукции в Н. Новгороде)

11. Методы алгебраических и дифференциальных уравнений для анализа и качественного исследования социально-экономических явлений (По дисциплине: Математические методы моделирования процессов управления в социальной сфере)

12. Конспект лекций по курсу ЭММ (Экономико-математические методы и модели)

13. План чтения лекции по учебной дисциплине «Математические методы»

14. Методы диагностики потенциальных факторов риска (рискогенных сотрудников) в работе с персоналом

15. Математические методи в психології

16. Билеты по предмету Математические методы в экономике за осенний семестр 2000 года

Корзина для белья "Виолетта" (30 литров).
Корзина для белья решит проблему хранения большого количества грязного белья. Благодаря своей прямоугольной форме она может быть легко
396 руб
Раздел: Корзины для белья
Головоломка Кубик Рубика "3х3".
Головоломка Кубик Рубика "3х3" - это: - Улучшенный механизм на базе шара, кубик крутится плавнее, мягче и при этом точнее.
1048 руб
Раздел: Головоломки
Развивающая игра "Магнитные истории. В гостях у сказки".
Четыре сказки, четыре смены декораций, четыре комплекта сказочных героев! Настоящий игровой сборник "Русские народные сказки"
453 руб
Раздел: Магнитный театр

17. Лекции Математические методы исследования экономики

18. Экономико-математические методы анализа

19. Математические методы описания моделей конструкций РЭА

20. Использование метода стандартизации при оценке здоровья населения и показателей работы учреждений здравоохранения. Динамические ряды

21. Математические методы в психологии

22. Почему психолог должен знать математические методы?
23. Экономико-математические методы управления денежными потоками
24. Исследование несостоятельности (банкротства) предприятия с применением статистических и математических методов анализа

25. Статистические методы изучения взаимосвязей производственных показателей фирмы (на примере производительности труда и заработной платы)

26. Экономико-математические методы

27. Розвиток економетричних моделей та методів в розвинутих країнах та приклади їх застосування в Україні

28. Математические методы в экономике

29. Математические методы в экономике

30. Математические методы и модели исследования операций

31. Математические методы экономических исследований

32. Математические методы и модели в экономике

Мощный стиральный порошок с ферментами для стирки белого белья "Super Wash", 1 кг.
Этот порошок идеально подходит для белого белья. Ферменты в составе средства, расщепляют любые сложные загрязнения и они с легкостью
314 руб
Раздел: Стиральные порошки
Закаточная машинка автомат ТМ "Лось", окрашенная.
Закаточная машинка ЛОСЬ марки ЗМ-2/8 предназначено для герметической укупорки стеклянных банок (отечественного производства емкостью 0,5
445 руб
Раздел: Консервирование
Мат для швабры Vileda "Ultra MaX" для швабры.
Насадка изготовлена из микрофибры, крепится на кнопках. • Эффективно и быстро, без чистящих средств удаляет любые загрязнения. • Насадку
889 руб
Раздел: Тканевые, микрофибра

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

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

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

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

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

38. Билеты, решения и методичка по Информатике (2.0)
39. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)
40. Решение задач - методы спуска

41. Решение систем дифференциальных уравнений методом Рунге-Куты 4 порядка

42. Использование численных методов для решения дифуpов (2-го порядка) (, демонстрация применения интерполяции в среде MATHCAD-а)

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

44. Построение решения задачи Гурса для телеграфного уравнения методом Римана

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

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

47. Составление и решение нестандартных уравнений графоаналитическим методом

48. Метод прогонки решения систем с трехдиагональными матрицами коэффициентов

Качели со столиком, арт. 15-10960.
Летом на даче не обойтись без качелей со столиком. Ведь они предназначены для самых маленьких. Качели можно подвесить с помощью
770 руб
Раздел: Качели
Фотобумага "Lomond" для струйной печати, А4, 230 г/м, 50 листов, односторонняя, матовая.
Формат: А4 (210х297 мм). Плотность - 230 г/м2. Матовая. Односторонняя. Упаковка - 50 листов.
370 руб
Раздел: Фотобумага для цветной печати
Канистра-бочонок со сливом, 20 л.
Изготовлена из пищевого полиэтилена. Пригодна для хранения питьевой воды. Имеет герметичную крышку, позволяющую полностью избежать
443 руб
Раздел: Баки, канистры

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

50. Система поддержки принятия маркетинговых решений в торговом предприятии на основе методов Data Mining

51. Методология и методы принятия решения

52. Сущность и методы принятия управленческих решений

53. Анализ инвестиционной ситуации. Принятие решений по инвестиционным проектам. Методы оценки эффективности инвестиционных проектов

54. Решение творческих задач методом блочных альтернативных сетей: объектно-ориентированные представления
55. Метод касательных решения нелинейных уравнений
56. Методы решения некорректно поставленных задач

57. Построение приближенного решения нелинейного уравнения методом Ван-дер-Поля

58. Приближенное решение уравнений методом хорд и касательных

59. Решение задачи Дирихле для уравнения Лапласа методом сеток

60. Нестандартные методы решения тригонометрических уравнений: графический и функциональный

61. Методы принятия управленческого решения

62. Управленческие ситуации и методы их решения

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

64. Кинезиология как Метод решения психологических проблем

Глобус Земли физико-политический, рельефный, с подсветкой, 320 мм.
Глобус Земли физико-политический, рельефный, с подсветкой, питание от сети. Диаметр: 32 см. Материал: пластмасса. Крым в составе РФ.
1452 руб
Раздел: Глобусы
Качели подвесные Edu-play "До-Ре-Ми".
Качели подвесные Edu Play "До-Ре-Ми". Легкие по весу, простые в сборке. Устанавливать возможно дома и на улице. Надежные канаты
2535 руб
Раздел: Качели
Фоторамка "Вращающийся куб".
Декоративная фоторамка, выполненная в виде куба. На гранях куба вы сможете разместить шесть фотографии формата 10 см х 10 см. Куб
330 руб
Раздел: Мультирамки

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

66. Сравнительная характеристика методов принятия решений относительно инвестиционных программ

67. Решение геоэкологических проблем с помощью нестандартных геофизических методов

68. Методы решения задач

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

70. Приближённые методы решения алгебраического уравнения
71. Решение систем линейных дифференциальных уравнений пятиточечным методом Адамса – Башфорта
72. Модели и методы решения проблемы выбора в условиях неопределенности

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

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

75. Поиск решений системы линейных уравнений методом Гаусса

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

77. Решение задач методом северо-западного угла, рапределительного, минимального и максимального элемента по строке

78. Решение прикладных задач методом дихотомии

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

80. Решение систем нелинейных уравнений методом Бройдена

Блюдо "Пасхальное", диаметр 25 см.
Блюдо. Диаметр: 25 см. Высота: 3 см. Материал: фарфор. В ассортименте, без возможности выбора.
515 руб
Раздел: Прочее
Органический солнцезащитный крем Mommy care для тела, 100 мл, арт. MC_1115.
Органический солнцезащитный крем для тела идеален даже для городских условий, а такие натуральные компоненты, как ромашка, кунжутное
1140 руб
Раздел: Солнцезащитная косметика
Гирлянда электрическая, 1200 см (белая).
Гирлянда состоит из белых мини ламп, которые будут мигать в 8 режимах. Питание от бытовой электросети 220 В. Длина гирлянды: 1200
472 руб
Раздел: Гирлянды с мини-лампами

81. Решение экономических задач программными методами

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

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

84. Методы принятия решений в маркетинге

85. Исследование методов решения системы дифференциальных уравнений с постоянной матрицей

86. Итерационные методы решения систем нелинейных уравнений
87. Логические задачи и методы их решения
88. Метод Рунге-Кутты четвертого порядка с автоматическим выбором шага интегрирования решения задачи Коши

89. Методы приближённого решения матричных игр

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

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

92. Нахождение корня нелинейного уравнения. Методы решения системы нелинейных уравнений

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

94. Методы экономического обоснования принимаемых решений по выходу на внешний рынок

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

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

Банка для сыпучих продуктов "Лавандовый букет", 9,5x13 см, 500 мл.
Банка для сыпучих продуктов прекрасно впишется в кухонный интерьер. Материал: доломит. Объем: 500 мл. Размер: 9,5x13 см.
307 руб
Раздел: Керамические
Циркуль металлический "Stop System" с грифелем 2 мм.
Эксклюзивная инновация. Кронцепция Stop System фиксирует штанги циркуля в нужном положении, предотвращая их нежелательное смещение, и
357 руб
Раздел: Циркули, чертежные инструменты
Игра "Зайкина горка" №1, классические цвета.
«Зайкина горка» – это увлекательное занятие: лабиринт для разноцветных шариков. Веселые шарики катаются по лабиринту горки и развлекают
530 руб
Раздел: Сортеры, логические игрушки

97. Методы планирования управленческих решений

98. Методы принятия управленческих решений

99. Методы разработки управленческих решений


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