Общая задача математического программирования

Основные задачи математического программирования

=== Скачать файл ===

Задачи м атематическо го программировани я. Переход от административных к экономическим методам управления производством, развитие рыночных отношений, распространение договорных цен — все это нацеливает экономические службы на поиск наилучших хозяйственных решений, обеспечивающих максимум результатов или минимум затрат. Необходимость поиска таких решений обуславливается, прежде всего, существованием ограничений на факторы производства, в пределах которых предприятия отдельные производители постоянно функционируют. Если бы эти ограничения отсутствовали, то нечего было бы выбирать, не было бы и вариантов решений. Известно, что определенный вид продукции можно произвести, используя различные технологические способы; в некоторых производствах возможна взаимозаменяемость материалов; один и тот же тип оборудования может быть использован для производства различных видов продукции и т. Как лучше организовать производство, по каким ценам выгодно производить продукцию, как лучше всего использовать производственные ресурсы, которые высвобождаются и т. На все эти вопросы позволяет получить ответ математическое программирование, являющееся действенным инструментом принятия решений. Математическое программирование представляет собой математическую дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их решения. В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f x1, х2, В зависимости от свойств функций f и gi математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач. Прежде всего задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования. Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ. Среди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой или максимум вогнутой функции, заданной на выпуклом замкнутом множестве. В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум или минимум квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных неравенств или линейных уравнений либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения. В задачах целочисленного программирования неизвестные могут принимать только целочисленные значения. Задача, процесс нахождения решения которой является многоэтапным, относится к задаче динамического программирования. Математическое программирование — это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями. Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными. Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ. Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач. В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:. Если целевая функция и функции ограничений — линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования. Виды задач линейного программирования. Линейное программирование ЛП — один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина 'математическое программирование'. Термин 'программирование' в названии дисциплины ничего общего с термином 'программирование то есть составление программы для ЭВМ' не имеет, так как дисциплина 'линейное программирование' возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. Термин 'линейное программирование' возник в результате неточного перевода английского 'linear programming'. Одно из значений слова 'programming' - составление планов, планирование. Следовательно, правильным переводом английского 'linear programming' было бы не 'линейное программирование', а 'линейное планирование', что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т. Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности. Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира. Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза транспортная задача ; в задачах оптимального распределения кадров и т. Задача линейного программирования ЛП , как уже ясно из сказанного выше, состоит в нахождении минимума или максимума линейной функции при линейных ограничениях. Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:. В большинстве инженерных задач построение математической модели не удается свести к задаче линейного программирования. Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования — это задачи нелинейного программирования НП. В данной работе будет рассматриваться такой метод решения задач НП, как метод множителей Лагранжа. Метод множителей Лагранжа позволяет отыскивать максимум или минимум функции при ограничениях-равенствах. Основная идея метода состоит в переходе от задачи на условный экстремум к задаче отыскания безусловного экстремума некоторой построенной функции Лагранжа. Динамическое программирование представляет собой математические аппарат, позволяющий быстро находить оптимальное решение в случаях, когда анализируемая ситуация не содержит факторов неопределенности, но имеется большое количество вариантов поведения, приносящих различные результаты, среди которых необходимо выбрать наилучший. Динамическое программирование подходит к решению некоторого класса задач путем разложения на части, небольшие и менее сложные задачи. В принципе, задачи такого рода могут быть решены путем перебора всех возможных вариантов и выбора среди них наилучшего, однако часто такой перебор весьма затруднен. В этих случаях процесс принятия оптимального решения может быть разбит на шаги этапы и исследован с помощью метода динамического программирования. Решение задач методами динамического программирования проводится на основе сформулированного Р. Таким образом, планирование каждого шага должно проводится с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию. Вместе с тем динамическое программирование не является универсальным методом решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Динамическое программирование применяется для решения таких задач, как: Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных — переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Числовая характеристика этого результата называется функцией Беллмана Fk S и зависит от номера шага k и состояния системы S. Все решения задачи разбиваются на два этапа. На первом этапе, который называют условной оптимизацией, отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, производится второй этап решения задачи, который называется безусловной оптимизацией. В общем виде задача динамического программирования формулируется следующим образом: Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:. Этот максимум или минимум определяется по всем возможным для k и S значениям переменной управления X. Для заданной математической постановки задачи ЛП, приняв дополнительно условие неотрицательности переменных, выполнить следующие действия:. Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов;. Из рисунка 1 следует, что опорной по отношению к построенному многоугольнику решений эта прямая становится в точке B, где функция F принимает максимальное значение. Таким образом, для того, чтобы получить максимальную прибыль в размере Канонический вид задачи ЛП. Запишем в канонической форме задачу распределения ресурсов. При этом в далее получаемом решении переменные х3 и х4 будут соответствовать объемам неиспользованного сырья S1 и S2, а х5 — неиспользованному машинному времени. Симплексный метод решения задачи ЛП. Для того, чтобы опорный план был оптимален, при максимизации целевой функции необходимо, чтобы коэффициенты в строке целевой функции были неотрицательными, то есть при поиске максимума мы должны освободиться от отрицательных коэффициентов в строке f x. В качестве разрешающего выбираем столбец с минимальным коэффициентом в строке f x. В данном примере это столбец х2. Для выбора разрешающей строки разрешающего элемента среди положительных коэффициентов разрешающего столбца выбираем тот элемент, для которого отношение коэффициентов в столбце свободных членов к коэффициенту в разрешающем столбце минимально. Разрешающий элемент рассчитывается по формуле:. В данном примере такой строкой будет строка х3, так как отношение коэффициента в столбце свободных членов к коэффициенту в разрешающем столбце минимально. Для перехода к следующей симплексной таблице следующему опорному плану с большим значением целевой функции делаем шаг модифицированного жорданова исключения с разрешающим элементом arl, при котором базисная переменная xr становится свободной и одновременно свободная переменная xi становится базисной. Следующим разрешающим столбцом будет столбец х1, а разрешающей строкой — х4. Далее действуем по тому же алгоритму. Следующим разрешающим столбцом будет столбец х5, а разрешающей строкой — х3. При этом переменным, которые стоят в верхней строке, в базисном решении присваивается значение 0 — это свободные переменные. Каждая из переменных, стоящая в левом столбце, приравнивается к числу, записанному в правом столбце той же самой строки — это базисные переменные. Постановка двойственной задачи ЛП. Определить значение двойственных оценок можно следующим образом. Очевидно, что при увеличении общего машинного времени не произошло бы увеличение целевой функции. Таким образом, если по данному ресурсу есть резерв, то дополнительная переменная будет больше нуля, а двойственная оценка данного ограничения равна нулю. Если ресурс использовался полностью, то его увеличение или уменьшение повлияет на объем выпускаемой продукции и, следовательно, на величину целевой функции. Значение двойственной оценки при этом находится в симплекс-таблице на пересечении строки целевой функции со столбцом данной дополнительной переменной. Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов. Формулировка и результаты решения исходной и двойственной задач распределения ресурсов приведены в таблице 4. Проверить результаты решения в табличном процессоре Excel. В состав рациона кормления входят три продукта: Содержание питательных веществ в граммах в 1 килограмме соответствующего продукта питания и минимально необходимое их потребление заданы таблицей:. Определить оптимальный режим кормления, из условия минимальной стоимости, если цена 1 кг продукта питания соответственно составляет: Осуществить математическую запись задачи ЛП. Обозначим через х1 — количество единиц сена, через х2 — количество единиц силоса а через х3 — количество единиц концентрата. Функция затрат на покупку этих продуктов выглядит так: Необходимые нормы потребления выражены в виде ограничений:. В качестве значений переменных выступает количество закупаемой продукции каждого вида. В качестве целевой ячейки выбираем ячейку, в которой находится значение целевой функции, выполняем максимизацию функции, изменяя ячейки со значениями количества продукции. В окне Параметры поиска решения можно изменять условия и варианты поиска решения исследуемой задачи, а также загружать и сохранять оптимизируемые модели. Теперь задача оптимизации подготовлена полностью. Привести математическую постановку двойственной задачи ЛП. Двойственная задача ЛП определяется по формуле:. К имеющимся данным добавляются значения двойственных переменных, ячейка, содержащая формулу целевой функции двойственной задачи, и ячейки, определяющие левые части ограничений двойственной задачи. К исходным данным при решении задачи ЛП добавим еще одно ограничение целочисленности для ячеек, содержащих искомое количество производимой продукции. После выполнения поиска получаем решение, приведенное в таблице Из полученного решения очевидно, что для минимизации затрат необходимо закупать 16 кг сена и 6 кг концентрата, закупка же силоса нецелесообразна. При этом потребление питательных веществ, таких как — белок, кальций и витамины не уменьшится. Для заданной матрицы издержек С, вектора — столбца запасов В в пунктах отправления и вектора - строки потребностей А в пунктах назначения решить транспортную задачу и составить отчет по следующим пунктам:. Осуществить математическую запись транспортнойзадачи. Обозначим через хij количество единиц сырья, перевозимого из i-го пункта его получения на j-тое предприятие. Тогда условие доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:. Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений, при котором целевая функция f x принимает минимальное значение. Находим оптимальный план поставок сырья и соответствующие ему транспортные расходы в таблице Изменим, данные для того, чтобы получить открытую задачу. Для этого уменьшим запасы и увеличим потребности, получим:. Для заданной математической постановки задачи НП целевой функции f x и ограничений - равенств выполнить следующие действия:. Найти все условные экстремумы функций методом множителей Лагранжа и выбрать среди них глобальный минимум максимум ;. Дифференцируем данную функцию по х1, х2, x3, и , получим систему уравнений:. Как известно, для того, чтобы найти экстремум функции многих переменных если он вообще существует необходимо приравнять к нулю все его частные производные и решить полученную систему уравнений. Точка экстремума заданной функции f x - х1, х2, x3 , является точкой глобального минимума при заданных ограничениях функции. Имеются четыре предприятия, между которыми необходимо распределить тыс. Значения прироста выпуска продукции на предприятиях в зависимости от выделенных средств X представлены в таблице. Составить оптимальный план распределения средств, позволяющий максимизировать общий прирост выпуска продукции. Предполагаем, что все средства ден. Определяем оптимальную стратегию инвестирования в третье и четвертое предприятия. При этом рекуррентное соотношение Беллмана будет иметь вид:. Определяем оптимальную стратегию инвестирования во второе и третье предприятия. Определяем оптимальную стратегию инвестирования в первое и остальные предприятия. По данным последней таблицы максимальных доход с четырех предприятий составил 87 д. При этом первое и второе предприятия не принесут никакого дохода, в них нецелесообразно вкладывать инвестиции. В 3-е предприятие нужно вложить 80 д. В 4-е предприятие нужно вложить 20 д. В предложенной из начального пункта 1 в конечный пункт Стоимость проезда между отдельными пунктами транспортной сети придумать самостоятельно и транспортной сети имеется несколько маршрутов по проезду представить в соответствующей таблице T i,j. Необходимо определить оптимальный маршрут проезда из пункта 1 в пункт 11 с минимальными транспортными расходами. Элементы матрицы маршрутов транспортной сети, а так же стоимость проезда из пункта i в пункт j tij представлена в таблице Из пункта 1 следует направиться в пункт 4, затем из него в пункт 6, затем в пункт 8 и из него в пункт В курсовой работе были рассмотрены решения задач нелинейного программирования, линейного программирования, динамического программирования. Рек к выполнению лаб. Все материалы в разделе 'Математика'. Понятие и виды задач математического линейного и нелинейного программирования. Динамическое программирование, решение задачи средствами табличного процессора Excel. Задачи динамического программирования о выборе оптимального распределения инвестиций. Буторина Курсовая работа Задачи м атематическо го программировани я Вариант 4 Новокузнецк Содержание Введение 1. Понятие математического программирования 2. Виды задач линейного программирования 3. Понятие нелинейного программирования 4. Ресурсы Запасы Продукция Р1 Р2 S1 18 0. Рисунок 1 — Графический метод. Исходная задача ЛП Двойственная задача ЛП Математическая постановка. Переменные Целевая функция Вид продукции Р1 Р2 Прибыль Значение 6, 4, 36,1 Прибыль от ед. Переменные имя x1 x2 f x значение 6,19 4,38 36,1 коэф-ты f x 3 4 макс Ограничения двойств. Продукты Питательные вещества белок кальций витамины 1. Концентраты 18 3 1 Норма потребления Переменные Целевая функция Вид продукта сено силос концентрат f x значение 16,77 0,00 6,45 76,13 затраты на ед. Переменные Целевая функция Вид продукта сено силос концентрат f x значение 16 0 6 76 затраты на ед. Пункты отправления Пункты назначения В1 В2 В3 В4 В5 Запасы А1 2 3 4 2 4 А2 8 4 1 4 1 А3 9 7 3 7 2 Потребности 60 70 Транспортная таблица А1 0 0 0 0 А2 0 0 0 0 А3 0 0 0 0 Потребности 60 70 Транспортные расходы Таблица издержек Пункты отправления Пункты назначения В1 В2 В3 В4 В5 Запасы А1 2 3 4 2 4 А2 8 4 1 4 1 А3 9 7 3 7 2 Потребности 60 Транспортная таблица А1 0 0 0 0 А2 0 0 0 0 А3 0 0 0 0 Потребности 60 Транспортные расходы Решения задач линейного программирования геометрическим методом. Решение задачи линейного программирования симплекс-методом. Решение задачи линейного программирования графическим методом. Решение задач линейного программирования. Практикум по решению линейных задач математического программирования. Экономико-математические методы и прикладные модели. Задачи линейного программирования 2. Динамическое программирование и вариационное исчисление. Решение задач нелинейного программирования.

Расписание автобусов коломна зарайск 2017

Рахат лукум hacizade заказать москва

25 число рождения значение

Общая задача математического программирования

Основные задачи математического программирования

=== Скачать файл ===

Классификация задач математического программирования

1.2. Общая задача математического программирования.

Общая постановка задачи о принятии решения

Report Page