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

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

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

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

Решение задач линейной оптимизации симплекс – методом. Курсовая работа по дисциплине «Численные методы оптимизации» Выполнил: ст.гр.4408 Калинкин А.А. Казанский Государственный Университет им. А.Н. Туполева. г. Казань 2001г. 1. Постановка задачи 1.1. Физическая (техническая) постановка задачи Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л. алкилата; 250 тыс. л. крекинг-бензина; 350 тыс. л. бензина прямой перегонки; 250 тыс. л. изопентона; В результате смешивания этих четырёх компонентов в разных пропорциях образуются три сорта авиационного бензина: Бензин А – 2 : 3 : 5 : 2 ; Бензин В – 3 : 1 : 2 : 1 ; Бензин С – 2 : 2 : 1 : 3 ; Стоимость 1 тыс.л. указанных сортов бензина: Бензин А – 120 руб. Бензин Б – 100 руб. Бензин С – 150 руб. Необходимо определить план смешения компонентов, при котором будет достигнута максимальная стоимость все продукции. При следующих условиях: Бензина каждого сорта должно быть произведено не менее 300 тыс.л. Неиспользованного крекинг бензина должно остаться не более 50 тыс.л. Сводная таблица условий задачи: Компоненты, используемые для производства трёх видов бензина. Сорта производимого бензина Объем ресурсов (тыс. л) А В С Алкилат 400 Крекинг-бензин 250 Бензин прямой перегонки 300 Изопентат 250 Цена бензина (рублей за 1 тыс.л.) 120 100 150 1.2. Математическая постановка задачи Исходя из условий задачи, необходимо максимизировать следующую целевую функцию: (1.2.1) при ограничениях                                                    (1.2.2) , где В этих выражениях:  - объемы бензина А-го, В-го и С-го сорта соответственно. Тогда объёмная доля первой компоненты (алкилата) в бензине А. объёмная доля первой компоненты (алкилата) в бензине В. объёмная доля первой компоненты (алкилата) в бензине С. и т.д. Целевая функция  выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию  (1.2.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2.2) на . 2. Приведение задачи к канонической форме Задача линейного программирования записана в канонической форме, если она формулируется следующим образом. Требуется найти вектор , доставляющий максимум линейной форме (2.1) при условиях (2.2) (2.3) где Перепишем исходную задачу (1.2.1) - (1.2.2): (2.4) при ограничениях  (2.5) , где  (2.6) В канонической форме задачи линейного программирования необходимо, чтобы все компоненты искомого вектора Х были неотрицательными, а все остальные ограничения записывались в виде уравнений. Т.е. в задаче обязательно будут присутствовать условия вида (2.3) и 8 уравнений вида (2.2), обусловленных неравенствами (2.5), (2.6). Число ограничений задачи, приводящих к уравнениям (2.2) можно уменьшить, если перед приведением исходной задачи (2.4) - (2.6) к канонической форме мы преобразуем неравенства (2.6) к виду (2.3). Для этого перенесем свободные члены правых частей неравенств (2.6) в левые части. Таким образом, от старых переменных  перейдем к новым переменным, где : , .

Выразим теперь старые переменные через новые ,  (2.7) и подставим их в линейную форму (2.4) и в неравенства (2.5), (2.6). Получим    , где . Раскрывая скобки и учитывая, что  (2.8), можем окончательно записать:                                          (2.9)                                    (2.10) , где  (2.11) Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче (2.9) - (2.11) с меньшим числом ограничений. Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные , и задача (2.9) - (2.11) запишется в следующей эквивалентной форме: (2.12)                                  (2.13) , где Задача (2.12), (2.13) имеет каноническую форму. 3. Нахождение начального опорного плана с помощью L-задачи Начальный опорный план задачи (2.1) - (2.3), записанной в канонической форме, достаточно легко может быть найден с помощью вспомогательной задачи (L-задачи): (3.1) (3.2) (3.3) Начальный опорный план задачи (3.1) - (3.3) известен. Он состоит из компонент и имеет единичный базис Б = = E. Решая вспомогательную задачу первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4), в силу ограниченности линейной формы сверху на множестве своих планов () получим, что процесс решения через конечное число шагов приведет к оптимальному опорному плану вспомогательной задачи. Пусть - оптимальный опорный план вспомогательной задачи. Тогда  является опорным планом исходной задачи. Действительно, все дополнительные переменные . Значит, удовлетворяет условиям исходной задачи, т.е. является некоторым планом задачи (2.12) - (2.13). По построению план является также опорным. 3.1. Постановка L-задачи Вспомогательная задача для нахождения начального опорного плана задачи (2.12) - (2.13) в канонической форме состоит в следующем. Требуется обратить в максимум при условиях , где . рассматривая в качестве исходного опорного плана план Здесь добавление только одной дополнительной переменной  (вместо пяти) обусловлено тем, что исходная задача уже содержит четыре единичных вектора условий А4, А5, А6, А7. 3.2. Решение L-задачи Решение L-задачи будем проводить в соответствии с первым алгоритмом симплекс-метода (описание алгоритма приводится в п.4). Составим таблицу, соответствующую исходному опорному плану (0-й итерации). Т.к. Б0 = - базис, соответствующий известному опорному плану, является единичной матрицей, то коэффициенты разложения векторов Аj по базису Б0 . Значение линейной формы  и оценки  для заполнения (m 1)-й строки таблицы определяются следующими соотношениями: , . Отсюда получим: ; ; ; . Весь процесс решения задачи приведен в табл. 3.2.1, которая состоит из 2 частей, отвечающих 0-й (исходная таблица) и 1-й итерациям. Заполняем таблицу 0-й итерации. Среди оценок  имеются отрицательные. Значит, исходный опорный план не является оптимальным. Перейдем к новому базису. В базис будет введен вектор А1 с наименьшей оценкой . Значения вычисляются для всех позиций столбца (т.к. все элементы разрешающего столбца положительны). Наименьший элемент  достигается на пятой позиции базиса. Значит, пятая строка является разрешающей строкой, и вектор А9 подлежит исключению из базиса.

Составим таблицу, отвечающую первой итерации. В столбце Бх, в пятой позиции базиса место вектора А9 занимает вектор А1. Соответствующий ему коэффициент линейной формы С41 = 0 помещаем в столбец Сх. Главная часть таблицы 1 заполняется по данным таблицы 0 в соответствии с рекуррентными формулами. Так как все , то опорный план  является решением L-задачи. Наибольшее значение линейной формы равно . Таблица 3.2.1 3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи Поскольку , где  - оптимальный опорный план L-задачи, то  является начальным опорным планом исходной задачи (2.12) - (2.13). 4. Решение исходной задачи I алгоритмом симплекс-метода Описание I алгоритма Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ν-й итерации имеет вид табл. 4.1. Таблица 4.1 C B 1 l m m 1 – – – Заполнение таблицы, соответствующей исходному опорному плану (0-й итерации). Пусть  некоторый опорный план задачи (2.1) - (2.3) с базисом . Тогда  – базисные компоненты, а  – небазисные компоненты. Вычисляем коэффициенты разложения векторов Аj по базису Б0  (в случае, если Б0 является единичной матрицей, ) и находим оценки . Далее определяем значение линейной формы Полученные результаты записываем в таблицу 4.1. В первом столбце таблицы указываются номера строк. Номера первых m строк совпадают с номерами позиций базиса. Во втором столбце Сх записываются коэффициенты линейной формы при базисных переменных. Столбец Бх содержит векторы базиса . В столбце В записываются базисные переменные  опорного плана. Столбцы содержат коэффициенты разложения соответствующих векторов условий  по векторам базиса. Все вышесказанное относится только к первым m строкам таблицы. Последняя (m 1)-я строка таблицы заполняется последовательно значением линейной формы F и оценками . Позиции таблицы, которые не должны заполняться, прочеркиваются. В результате заполнена таблица 0-й итерации кроме столбца . Столбцы В, А1, , A (все m 1 позиций) будем называть главной частью таблицы. Порядок вычислений в отдельной итерации. Пусть ν-я итерация закончена. В результате заполнена таблица ν за исключением последнего столбца . Каждая итерация состоит из двух этапов. I этап: проверка исследуемого опорного плана на оптимальность. Просматривается (m 1)-я строка таблицы ν. Если все , то опорный план, полученный после ν-й итерации, является оптимальным (случай 1), завершаем решение задачи. Пусть теперь имеются отрицательные оценки. Проверяем знаки элементов  столбцов  с . Наличие по крайней мере одного столбца , для которого  и все , свидетельствует о неразрешимости задачи (случай 2). Установив это, прекращаем вычисления. Если в каждом столбце , для которого , содержится хотя бы один положительный коэффициент , то опорный план является неоптимальным (случай 3).

Поэтому разработчики Maple были вынуждены реализовать в своей системе численные методы решения задач линейной алгебры, которые широко используются в основных сферах ее приложения — математическом моделировании систем и устройств, расчетах в электротехнике, механике, астрономии и т.д. Решение задач линейной алгебры в численном виде можно рассматривать как одну из форм визуализации результатов вычислений, относящихся к линейной алгебре. В ядро Maple, как отмечалось, введены очень скромные и минимально необходимые средства для решения задач линейной алгебры. Основной упор в их реализации сделан на подключаемые пакеты. Основным из них, унаследованным от предшествующих реализаций системы, является пакет решения задач линейной алгебры linalg. Это один из самых обширных и мощных пакетов в области решения задач линейной алгебры. Для их просмотра достаточно использовать команду: > with(linalg); Для большинства пользователей системой Maple набор функций пакета оказывается чрезмерно обширным и потому опущен. Укажем, однако, наиболее употребительные функции пакета linalg: • addcol — добавляет к одному из столбцов другой столбец, умноженный на некоторое число; • addrow — добавляет к одной из строк другую строку, умноженную на некоторое число; • angle — вычисляет угол между векторами; • augment — объединяет две или больше матриц по горизонтали; • backsub — реализует метод обратной подстановки при решении системы линейных уравнений (см

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

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

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

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

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

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

9. Системы принятия решений, оптимизация в Excel и базы данных Access

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

11. Численные методы интегрирования и оптимизации сложных систем

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

13. Предмет психологии, ее задачи и методы

14. Задачи и методы планирования производства

15. Новые представления о задачах и методах гипербарической медицины

16. Содержание, задачи и методы финансового планирования на предприятии

Сменный фильтр "Барьер-6" (2 штуки).
Сменная кассета Барьер-6 «для жесткой воды» благодаря повышенному содержанию ионообменной смолы более эффективно снижает
461 руб
Раздел: Фильтры для воды
Караоке песенки В. Шаинского.
Какая игрушка превратит любой день в праздник? Конечно, удивительный микрофон-караоке! Подпевая любимым мультяшкам, малыши смогут
301 руб
Раздел: Микрофоны
Дуст от муравьев "Чистый дом", 350 грамм.
Препарат для эффективного уничтожения всех типов муравьев в домах, на садовых участках, на террасах. Без запаха! Способ применения: дуст
347 руб
Раздел: От тараканов и прочих насекомых

17. Предмет, задачи и методы теории перевода

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

19. Цели, задачи и методы маркетинговых исследований

20. Предмет, задачи и методы возрастной физиологии

21. Задачи и методы квалиметрии

22. Предмет психологии, ее задачи и методы
23. Применение методов линейного программирования в военном деле. Симплекс-метод
24. Математические методы и языки программирования: симплекс метод

25. Решение проблем и принятие решений

26. Двойственный симплекс-метод и доказательство теоремы двойственности

27. Построение экономической модели c использованием симплекс-метода

28. Построение экономической модели c использованием симплекс-метода

29. Табличный симплекс-метод

30. Симплекс метод в форме презентации

31. Методы, применяемые на эмпирическом и теоретическом уровнях познания. Развитие методов познания

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

Лоток (сортер), 4 отделения, вертикальный, сборный.
- предназначен для сортировки и временного хранения документов различных размеров, писем, счетов и другой документации - устойчивый на
317 руб
Раздел: Подставки, лотки для бумаг, футляры
Ручки гелевые "Пчелка", 30 цветов.
Набор гелевых ручек. Количество цветов: 30 (4 классических, 6 пастельных, 5 смешанных, 6 неоновых, 10 блестящих). Прочный пластиковый
554 руб
Раздел: Цветные
Машина "Ракетовоз АРК".
Башня стрелы поворачивается, стрела поднимается, ракета запускается при нажатии на красную кнопку, стекло кабины открывается. Размер:
331 руб
Раздел: Прочее

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

34. Решение задач - методы спуска

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

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

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

38. Методы решения некорректно поставленных задач
39. Решения смешанной задачи для уравнения гиперболического типа методом сеток
40. Обучение общим методам решения задач

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

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

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

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

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

46. Аналитический метод в решении планиметрических задач

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

48. Методы решения логистических задач

Набор кастрюль Nadoba "Maruska" (малый).
Вся посуда серии Maruska изготовлена из высококачественной нержавеющей стали 18/10. Толщина стенок - 0,6 мм. Прочное трехслойное
3393 руб
Раздел: Наборы кастрюль
Набор крепированной бумаги, 10 рулонов.
Крепированная бумага прекрасно подходит для воплощения творческих идей не только детей, но и взрослых. Насыщенный цвет бумаги сделает
359 руб
Раздел: Самоклеящаяся, флуоресцентная, перламутровая и прочие
Настольная семейная игра "Кошки-мышки. Сырная охота".
Четыре маленьких мышонка карабкаются на гигантский сыр и соскальзывают вниз через отверстия. Цель погони - заполучить 5 лакомых кусочков
685 руб
Раздел: Игры на ловкость

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

50. Кислотно-каталитические процессы в нефтепереработке и в нефтехимии. Решение обратной задачи кинетики статистическими методами

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

52. Метод потенциалов для решения транспортной задачи в матричной форме. Задача оптимального распределения ресурсов

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

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

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

58. Решение систем линейных алгебраических уравнений методом Гаусса и Зейделя

59. Решение нелинейного уравнения методом касательных

60. Метод последовательных уступок (Теория принятия решений)

61. Приближенный метод решения интегралов. Метод прямоугольников (правых, средних, левых)

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

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

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

Набор "Стучалка", 6 гвоздиков.
Игрушка стучалка имеет вид скамейки, в которой забиты шесть разноцветных гвоздей. Все части набора деревянные, что не дает малышу
409 руб
Раздел: Стучалки, гвозди-перевертыши
Детское подвесное кресло Polini "Кокон" (цвет: оранжевый).
Подвесные детские качели яркого цвета создадут ощущение собственного укромного уголка. Надежные крепления кресла обеспечат безопасность
1225 руб
Раздел: Качели, кресла-качалки, шезлонги
Клей для дерева "Момент Столяр. ПВА Универсальный", 750 грамм.
Клей используется для склеивания, ремонта и изготовления изделий из различных видов дерева, а также ДСП, фанеры, картона и т.п. Клей
388 руб
Раздел: Для дерева

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

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

67. Современные методы решения экологических проблем на предприятии (на примере ООО "Волготрансгаз" - дочерней структуры ОАО "ГАЗПРОМ")

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

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

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

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

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

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

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

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

78. Оптимизация процесса обработки воды методом ультрафильтрации

79. Методы оптимизации портфеля бескупонных облигаций

80. Методы поиска технических решений

Держатель-рулетка для бейджей "Style", желтый.
Используется для ношения именных, магнитных или пропускных карточек. Крепление бейджа: карабин-петля. Подходит ко всем бейджам, имеющим
383 руб
Раздел: Бейджи, держатели, этикетки
Шары Ньютона "Эврика", металл (арт. 98085).
Движение – это жизнь! Небольшая настольная кинетическая скульптура в собранном виде демонстрирует закон сохранения энергии, открытый
891 руб
Раздел: Антистрессы
Пленка воздушно-пузырчатая 2-х слойная, плотность 75 г/кв.м.
Универсальный упаковочный материал. Препятствует повреждению товаров при ударе, предотвращает проникновение влаги и пыли, защищает от
423 руб
Раздел: Фольга

81. Обзор методов оптимизации кода для процессоров с поддержкой параллелизма на уровне команд

82. Методы решения уравнений, содержащих параметр

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

84. Метод касательных. Решения нелинейных уравнений. Паскаль 7.0

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

86. Принятие решений об оптимизации ассортимента
87. Политический риск и методы его оптимизации
88. Исследование методов оптимизации

89. Методы и алгоритмы компьютерного решения дифференциальных уравнений

90. Одномерная оптимизация функций методом золотого сечения

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

92. Разработка компьютерного лабораторного практикума "Теория оптимизации и численные методы"

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

94. Решение систем нелинейных алгебраических уравнений методом Ньютона

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

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

Кружка фарфоровая "FIFA 2018. Забивака. Удар!", 400 мл.
Объем: 400 мл. Материал: фарфор.
358 руб
Раздел: Кружки, посуда
Шампунь-гель детский "Weleda" для волос и тела (с календулой), 200 мл.
Бережно очищает и ухаживает за чувствительной кожей и волосами малышей, деликатно удаляет молочные корочки. Не вызывает раздражения
754 руб
Раздел: Гели, мыло
Развивающая настольная игра "Игротека 5+" (настольные игры "Турбосчет", "Зверобуквы",.
Это идеальная подборка для малышей-дошкольников. На скорость и на подумать. Благодаря увлекательным играм ребенок освоит: порядковый счет,
2048 руб
Раздел: Математика, цифры, счет

97. Резисторы и конденсаторы в «полупроводниковом» исполнении. Топологические решения и методы расчета

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

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

100. Математические методы в теории принятия решений


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