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

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

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

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

Министерство образования РФ и РТ. Казанский Государственный Университет им. А.Н. Туполева. Курсовая работа по дисциплине «Численные методы оптимизации» Решение задач линейной оптимизации симплекс – методом. Выполнил: ст.гр.4408 Калинкин А.А. Проверил: Мурга О.К. г. Казань 2001г. Содержание 1. Постановка задачи 1.1. Физическая постановка задачи 1.2. Математическая постановка задачи 2. Приведение задачи к канонической форме 3. Нахождение начального опорного плана с помощью L-задачи 3.1. Постановка L-задачи 3.2. Решение L-задачи 3.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи 4. Решение исходной задачи I алгоритмом симплекс-метода 5. Формирование М-задачи 6. Решение М-задачи вторым алгоритмом симплекс-метода 7. Формирование двойственной задачи 8. Формирование оптимального решения двойственной задачи на основе теоремы о двойственности 9. Анализ результатов и выводы 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 тыс.л. Сводная таблица условий задачи: Сорта Объем Компоненты, используемые для производимого ресурсов производства трёх видов бензина бензина. (тыс. л) А В С Алкилат Крекинг-бензин Бензин прямой перегонки Изопентат Цена бензина (рублей за 1 120 100 150 тыс.л.) 1.2. Математическая постановка задачи Исходя из условий задачи, необходимо максимизировать следующую целевую функцию: , где - объемы бензина А-го, В-го и С-го сорта соответственно. Тогда объёмная доля первой компоненты (алкилата) в бензине А. объёмная доля первой компоненты (алкилата) в бензине В. объёмная доля первой компоненты (алкилата) в бензине С. и т.д. Целевая функция выражает стоимость всей продукции в зависимости от объема производимого бензина каждого сорта. Таким образом, для получения максимальной стоимости продукции необходимо максимизировать целевую функцию (1.2.1) с соблюдением всех условий задачи, которые накладывают ограничения (1.2.2) на . 2. Приведение задачи к канонической форме Задача линейного программирования записана в канонической форме, если она формулируется следующим образом. Требуется найти вектор (2.1) при условиях Перепишем исходную задачу (1.2.1) - (1.2.2): , где (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.9) (2.11) Путем несложных преобразований задачу (1.2.1), (1.2.2) свели к задаче (2.9) - (2.11) с меньшим числом ограничений. Для записи неравенств (2.10) в виде уравнений введем неотрицательные дополнительные переменные , и задача (2.9) - (2.11) запишется в следующей эквивалентной форме: Задача (2.12), (2.13) имеет каноническую форму. 3. Нахождение начального опорного плана с помощью L-задачи Начальный опорный план задачи (2.1) - (2.3), записанной в канонической форме, достаточно легко может быть найден с помощью вспомогательной задачи (L-задачи): (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.3. Формирование начального опорного плана исходной задачи линейного программирования из оптимального плана L-задачи Поскольку - оптимальный опорный план L-задачи, то является начальным опорным планом исходной задачи (2.12) - (2.13). 4. Решение исходной задачи I алгоритмом симплекс-метода Описание I алгоритма Симплекс-метод позволяет, отправляясь от некоторого исходного опорного плана и постепенно улучшая его, получить через конечное число итераций оптимальный план или убедиться в неразрешимости задачи. Каждой итерации соответствует переход от одной таблицы алгоритма к следующей. Таблица, отвечающая опорному плану в ?-й итерации имеет вид табл. 4.1. Таблица 4.1 C c] c] c] c] c] 1 c] c] c] c] c] c] c] c] c] c] c] c] c] c] c] l c] c] c] c] c] c] c] c] c] c] c] c] c] c] c] c] m c] c] c] c] c] m 1 – – c] c] Заполнение таблицы, соответствующей исходному опорному плану (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. Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

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

4. Применение новейших экономико-математических методов для решения задач

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

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

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

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

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

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

13. Записать задачу двойственную к данной, решить одну из пары задач и отыскать оптимальное решение второй

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

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

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

Нож-скальпель, 2 запасных лезвия.
Нож канцелярский (скальпель) предназначен для аккуратной и точной работы по бумаге. Резиновый грип препятствует скольжению
349 руб
Раздел: Ножи, ножницы, резаки
Подставка под ноги "Мишки" антискользящая.
Подставка для ног от торговой марки Tega поможет крохе самостоятельно воспользоваться умывальником, унитазом или достать до высокого
449 руб
Раздел: Подставки под ноги
Рюкзак детский, 30x24x10 см.
Рюкзак детский с вместительным основным отделением и дополнительными карманами. Лямки регулируются. Размер: 30х24х10 см. Материал:
419 руб
Раздел: Без наполнения

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

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

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

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

21. Технология составления и решения моделей в MS Excel

22. Методы принятия решений в маркетинге
23. Линейное программирование симплекс-методом Данцига
24. МЕТОДЫ ДИАГНОСТИКИ ИНФЕКЦИОННЫХ БОЛЕЗНЕЙ (КЛИНИЧЕСКИЙ И ЭПИЗООТОЛОГИЧЕСКИЙ МЕТОДЫ)

25. Амортизация основных фондов: методы амортизации, сопоставительный расчет амортизационных отчислений различными методами

26. Методи лінгвістичних досліджень.Описовий метод. Порівняльно-історичний метод

27. Линейное программирование как метод оптимизации

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

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

30. Лабораторная работа №7 по "Основам теории систем" (Решение задачи коммивояжера методом ветвей и границ)

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

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

Набор детской посуды "Авто", 3 предмета.
Набор посуды для детей включает в себя три предмета: суповую тарелку, обеденную тарелку и кружку. Набор упакован в красочную, подарочную
397 руб
Раздел: Наборы для кормления
Диванчик раскладной "Кошечка".
Диван "Кошечка" - красивый, функциональный, надежный детский диван. Он способен украсить детскую комнату и может использоваться
2791 руб
Раздел: Прочие
Карандаши цветные "Triocolor", 24 цвета.
Трехгранная эргономичная форма корпуса. Яркие, насыщенные цвета, линии мягко ложатся на бумагу. Грифель устойчив к механическим
337 руб
Раздел: 13-24 цвета

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

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

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

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

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

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

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

42. Использование Excel для решения статистических задач

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

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

45. Решение математических задач с помощью алгоритмического языка Turbo Pascal, Microsoft Excel, пакета MathCAD и разработка программ в среде Delphi

46. Решение математической задачи с помощью математических исследований и помощью специального офисного приложения MS Excel

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

48. Решение финансовых задач при помощи Microsoft Excel

Наушники "Philips SHE3550", черные.
Маленькие громкие динамики наушников-вкладышей "Philips SHE3550" обеспечивают плотное прилегание и чистый звук с мощными басами.
803 руб
Раздел: Гарнитуры и трубки
Таблетки для посудомоечной машины "All in 1", 21 штука.
Для безупречного мытья посуды в посудомоечной машине воспользуйтесь таблетками Meine Liebe All in 1. Это моющее средство придаст вашей
413 руб
Раздел: Для посудомоечных машин
Глобус физический рельефный диаметром 320 мм, с подсветкой.
Диаметр: 320 мм. Масштаб: 1:40000000. Материал подставки: пластик. Цвет подставки: черный. Мощность: 220 V. Шар выполнен из толстого
1270 руб
Раздел: Глобусы

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

50. Метод Рунге-Кутты четвертого порядка с автоматическим выбором шага интегрирования решения задачи Коши

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

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

53. Графический метод решения химических задач

54. Примеры решения задач по курсу химии
55. Применение методов экономической статистики при решении задач
56. Примеры решения задач по статистике

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

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

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

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

61. Формирование структуры электронного учебника и решение задач на ней

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

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

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

Аэрозоль Gardex "Extreme" от клещей, 150 мл.
Аэрозоль является эффективным средством, парализующим клещей после соприкосновения с одеждой. Действие активного вещества сохраняется до
305 руб
Раздел: Аэрозоль, спрей
Фигурка "Zabivaka Знаменосец", 9 см.
Фигурка "Zabivaka Знаменосец" в подарочной коробке (64 наклейки флагов 32-х стран-участниц в комплекте). Этот обаятельный,
389 руб
Раздел: Игрушки, фигурки
Набор цветной самоклеющейся бумаги №6, А4, 20 цветов, 20 листов.
Набор цветной самоклеющейся бумаги для детского творчества. Обычные цвета, металлик, флюоресцентные.
310 руб
Раздел: Самоклеящаяся, флуоресцентная, перламутровая и прочие

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

66. Возможности радиолокационного тренажера NMS-90 и его использование для решения задач расхождения судов в условиях ограниченной видимости

67. Решение обратной задачи вихретокового контроля

68. Маркетинг: решение исследовательских задач

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

70. Формулы для решения задач по экономике предприятия
71. Приложения определенного интеграла к решению некоторых задач механики и физики
72. Решение смешанной задачи для уравнения

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

74. Решение задач по прикладной математике

75. Алгоритмы декомпозиции и перебора L-классов для решения некоторых задач размещения

76. О некоторых трудностях, возникающих при решении геометрических задач

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

78. Обучение решению математических задач с помощью графов

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

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

Таблетки для посудомоечных машин "Babyline", для всей семьи, 25 штук.
Babyline рад представить Вам свою новинку: таблетки для посудомоечных машин для всей семьи! Теперь Вам не нужно мыть и полоскать детскую
342 руб
Раздел: Для посудомоечных машин
Музыкальный коврик "На ферме".
Новый музыкальный коврик разработан специально для малышей. Он большой, яркий, обучающий и интерактивный! 27 весёлых зверюшек, 40 загадок
681 руб
Раздел: Развивающие коврики не интерактивные
Швабра для пола, с отжимом.
Швабра может использоваться для мытья пола, стен и окон. Пригодна для чистки ковров. Моющая губка - 27 см. Ручка - телескопическая, длина
331 руб
Раздел: Швабры и наборы

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

82. Этапы решения мыслительной задачи

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

84. Решение управленческих задач

85. Алгоритм решения обратной задачи вихретокового контроля (ВТК)

86. Электрофизиологические корреляты центральных программ при решении простых моторных задач у лиц с различным профилем асимметрии
87. Решение задач по химии
88. Решение многокритериальной задачи линейного программирования

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

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

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

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

93. Решение инженерно-технических задач в среде Mathcad

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

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

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

Качели детские подвесные "Вятушка".
Подвесные качели "Вятушка" станут необходимым атрибутом активного отдыха. Качели имеют цельный, жесткий трубчатый каркас с
557 руб
Раздел: Качели
Набор эмалированных кастрюль "Mayer & Boch" (3 предмета).
Набор эмалированных кастрюль с крышками из термостойкого стекла. Кастрюли - 3 штуки, стеклянные крышки - 3 штуки. Материал: углеродистая
844 руб
Раздел: Наборы кастрюль
Асборн - карточки. Дорисуй, найди, раскрась.
В этом наборе вы найдёте 50 многоразовых двусторонних карточек с яркими добрыми картинками животных, а также фломастер на водной основе.
389 руб
Раздел: Прочие

97. Решение текстовых задач

98. Основные подходы к оценке стоимости бизнеса и перспективы их применения к решению задач управления инновационными предприятиями

99. Решение задач по дисциплине "Страхование"

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


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