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

Обновлено: 08.07.2024

Математическое программирование можно рассматривать в двух аспектах – как чисто математическую теорию и как аппарат решения прикладных задач. С теоретической точки зрения математическое программирование имеет дело с задачами определенного вида, а именно с оптимизационными (или экстремальными) задачами. Специфика этих задач определяет ряд интересных теоретических результатов. Представляется, что математические объекты данного типа выявлены еще не полностью и дальнейшее развитие их теории приведет к новым интересным результатам. Прикладная ценность методов математического программирования во многом определяется возможностью решать с их помощью большое число практических задач. Наличие средств численного решения этих задач позволяет принять хорошее решение в каждом конкретном случае и оценить его последствия. Современная вычислительная техника, отличающаяся высоким быстродействием и значительными объемами памяти запоминающих устройств, дает возможность применять методы математического программирования для решения задач большой размерности в условиях жестких ограничений по времени. Выявление новых задач, допускающих оптимизационную постановку, не только способствует расширению области применения методов математического программирования, но также стимулирует развитие теории оптимизации, делая это научное направление перспективным для дальнейших исследований.

Следует отметить, что универсального метода математического программирования, наилучшего во всех отношениях, не существует. Поэтому для эффективного решения конкретной задачи следует разумно сочетать различные методы с учетом всевозможной априорной информации о решаемой задаче (гладкость целевой функции, выпуклость, физические или какие-либо иные соображения об области возможного расположения оптимальной точки и т.д.), имеющихся вычислительных средств и т.п. В ситуациях, когда нет никакой априорной информации о задаче, полезно попробовать применить не очень точные, но простые методы ее решения (например, метод перебора значений функции на сетке с небольшим числом узловых точек, метод покоординатного спуска, метод случайного поиска), а затем на основе накопленной информации при необходимости перейти к более точным методам. В тех случаях, когда пользователь, проводящий расчеты, не является компетентным в области методов решения экстремальных задач, желательно иметь прикладные компьютерные программы оптимизации, работающие в автоматическом режиме. Для этого пакет программ оптимизации должен содержать управляющую программу, обеспечивающую автоматический выбор наиболее подходящей последовательности используемых методов, их параметров в зависимости от конкретной решаемой экстремальной задачи.

При сдаче лабораторной работы, студент делает вид, что все знает; преподаватель делает вид, что верит ему. ==> читать все изречения.

Характеристика математического программирования как отдельной дисциплины. Понятие линейного, нелинейного и динамического программирования. Методы решения задач: графический, симплексный методы; постановка двойственной задачи; метод множителей Лагранжа.

Рубрика	Математика
Вид	реферат
Язык	русский
Дата добавления	15.08.2014
Размер файла	71,5 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

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

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

1. Понятие математического программирования

2. Понятие линейного программирования. Виды задач линейного программирования

3. Понятие нелинейного программирования

4. Динамическое программирование

Пример (задача линейного программирования)

Введение

Переход от административных к экономическим методам управления производством, развитие рыночных отношений, распространение договорных цен - все это нацеливает экономические службы на поиск наилучших хозяйственных решений, обеспечивающих максимум результатов или минимум затрат. Необходимость поиска таких решений обуславливается, прежде всего, существованием ограничений на факторы производства, в пределах которых предприятия (отдельные производители) постоянно функционируют. Если бы эти ограничения отсутствовали, то нечего было бы выбирать, не было бы и вариантов решений.

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

Как лучше организовать производство, по каким ценам выгодно производить продукцию, как лучше всего использовать производственные ресурсы, которые высвобождаются и т.п.?

На все эти вопросы позволяет получить ответ математическое программирование, являющееся действенным инструментом принятия решений.

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

В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции f(x1, х2. xn) при условиях gi(x1, х2. xn) ? bi, где f и gi -- заданные функции, a bi -- некоторые действительные числа.

В зависимости от свойств функций f и gi математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач.

Прежде всего задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования. Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ. Среди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

В свою очередь, среди задач выпуклого программирования более подробно исследованы задачи квадратичного программирования. В результате решения таких задач требуется в общем случае найти максимум (или минимум) квадратичной функции при условии, что ее переменные удовлетворяют некоторой системе линейных неравенств или линейных уравнений либо некоторой системе, содержащей как линейные неравенства, так и линейные уравнения.

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

Задача, процесс нахождения решения которой является многоэтапным, относится к задаче динамического программирования.

математический программирование динамический лагранж

1. Понятие математического программирования

Математическое программирование - это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

· задачи линейного программирования,

· задачи нелинейного программирования;

· задачи динамического программирования.

Если целевая функция и функции ограничений - линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования.

2. Понятие линейного программирования. Виды задач линейного программирования

Линейное программирование (ЛП) - один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина "математическое программирование". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина "линейное программирование" возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач.

Термин "линейное программирование" возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не "линейное программирование", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены.

Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

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

Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.

Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях.

Существует несколько методов решения задач ЛП:

Ш Графический метод решения задачи ЛП;

Ш Симплексный метод;

Ш Решение задачи ЛП средствами табличного процессора Excel;

3. Понятие нелинейного программирования

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

Математические модели в задачах проектирования реальных объектов или технологических процессов должны отражать реальные протекающие в них физические и, как правило, нелинейные процессы. Переменные этих объектов или процессов связанны между собой физическими нелинейными законами, такими, как законы сохранения массы или энергии. Они ограничены предельными диапазонами, обеспечивающими физическую реализуемость данного объекта или процесса. В результате, большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования - это задачи нелинейного программирования (НП).

В данной работе будет рассматриваться такой метод решения задач НП, как метод множителей Лагранжа.

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

4. Динамическое программирование

Динамическое программирование представляет собой математические аппарат, позволяющий быстро находить оптимальное решение в случаях, когда анализируемая ситуация не содержит факторов неопределенности, но имеется большое количество вариантов поведения, приносящих различные результаты, среди которых необходимо выбрать наилучший. Динамическое программирование подходит к решению некоторого класса задач путем разложения на части, небольшие и менее сложные задачи. В принципе, задачи такого рода могут быть решены путем перебора всех возможных вариантов и выбора среди них наилучшего, однако часто такой перебор весьма затруднен. В этих случаях процесс принятия оптимального решения может быть разбит на шаги (этапы) и исследован с помощью метода динамического программирования.

Решение задач методами динамического программирования проводится на основе сформулированного Р.Э.Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

Таким образом, планирование каждого шага должно проводится с учетом общей выгоды, получаемой по завершении всего процесса, что и позволяет оптимизировать конечный результат по выбранному критерию.

Вместе с тем динамическое программирование не является универсальным методом решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации.

Динамическое программирование применяется для решения таких задач, как: распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом и запасами; составление календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети и т.д.

Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить два типа переменных - переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k-м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления X на k-м шаге приносит некоторый результат Wk(S,Xk) и переводит систему в некоторое новое состояние S'(S,Xk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление X*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый, производится второй этап решения задачи, который называется безусловной оптимизацией.

В общем виде задача динамического программирования формулируется следующим образом: требуется определить такое управление X*, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0,X*) принимает наибольшее (наименьшее) значение.

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

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

целевая функция является аддитивной и равна сумме целевых функций каждого шага

выбор управления Xk на каждом шаге зависит только от состояния системы к этому шагу Sk-1 и не влияет на предшествующие шаги (нет обратной связи);

состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk-1 и этого управляющего воздействия Xk (отсутствие последействия) и может быть записано в виде уравнения состояния:

на каждом шаге управление Xk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа переменных;

оптимальное управление X* представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений:

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

Условная оптимизация. Как уже отмечалось выше, на данном этапе отыскиваются функция Беллмана и оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем n-м шаге найти оптимальное управление X*n и значение функции Беллмана Fn(S) не сложно, так как

где максимум ищется по всем возможным значениям Xn.

Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге:

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Безусловная оптимизация. После того, как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k=1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого приведет систему в состояние S1(S,x1*), зная которое можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

Пример (задача линейного программирования)

Для заданной математической постановки задачи ЛП, приняв дополнительно условие неотрицательности переменных, выполнить следующие действия:

Решить задачу графическим методом;

Привести задачу к канонической форме записи;

Составить симплексную таблицу;

Произвести решение задачи симплексным методом ручным способом или с использование компьютера;

Осуществить постановку двойственной задачи ЛП;

Получить решение двойственной задачи из полученной ранее симплексной таблицы и произвести анализ полученных результатов;

Математическое программирование является большим разделом в исследовании операций. Он состоит из теории и методов решения задач о нахождении экстремумов функций на множествах, определяемых равенствами или неравенствами.
Целью дисциплины является изучение и освоение методов математического программирования наиболее часто используемых при решении оптимизационных задач в области экономики, планирования и проектирования.
Формирование практических навыков, применения методов и алгоритмов оптимизации в инженерной деятельности.
Цель реферативной работы- изучить математическое программирование.
Для реализации цели реферативной работы были поставлены следующие задачи:
1. Рассмотреть понятие математического программирования
2. Изучить понятие линейного программирования. Виды задач линейного программирования
3. Выявить прямую и обратную задачу линейного программирования
4. Проанализировать производственную, транспортную и задачу о смесях
5. Выполнить практическую задачу
1. Понятие математического программирования
Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями[5,c.165].
Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции.
Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.
Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.
Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач[3,c.90].
В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:
1) задачи линейного программирования,
2) задачи нелинейного программирования.
Если целевая функция и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования.
Если хотя бы одна из указанных функций нелинейна, то соответствующая задача поиска экстремума является задачей нелинейного программирования[8,c.101].
2. Понятие линейного программирования. Виды задач линейного программирования
Линейное программирование (ЛП) – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться сама дисциплина " математическое программирование ". Термин "программирование" в названии дисциплины ничего общего с термином "программирование (т.е. составление программы) для ЭВМ" не имеет, т.к. дисциплина " линейное программирование " возникла еще до того времени, когда ЭВМ стали широко применяться для решения математических, инженерных, экономических и др. задач[2,c.209].
Термин " линейное программирование " возник в результате неточного перевода английского "linear programming". Одно из значений слова "programming" - составление планов, планирование. Следовательно, правильным переводом английского "linear programming" было бы не " линейное программирование ", а "линейное планирование", что более точно отражает содержание дисциплины. Однако, термины линейное программирование, нелинейное программирование, математическое программирование и т.д. в нашей литературе стали общепринятыми и поэтому будут сохранены[1,c.109].
Итак, линейное программирование возникло после второй мировой войны и стало быстро развиваться, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.
Можно сказать, что линейное программирование применимо для решения математических моделей тех процессов и систем, в основу которых может быть положена гипотеза линейного представления реального мира.
Линейное программирование применяется при решении экономических задач, в таких задачах как управление и планирование производства; в задачах определения оптимального размещения оборудования на морских судах, в цехах; в задачах определения оптимального плана перевозок груза (транспортная задача); в задачах оптимального распределения кадров и т.д.
Задача линейного программирования (ЛП), как уже ясно из сказанного выше, состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях[7,c.90].
Общая форма задачи имеет вид: найти при условиях
(1)
, где
Здесь и далее нам удобнее считать с и аі вектор - строками, а x и b=(b1. bm)T - вектор столбцами.
Наряду с общей формой широко используются также каноническая и стандартная формы.
Как в канонической, так и в стандартной форме
(2)
т.е. все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (такие переменные принято называть неотрицательные в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается).
Отличие же между этими формами состоит в том, что в одном случае I2 = 0, а в другом - I1 = 0.
Задача ЛП в канонической форме: [8,c.201].
w=cx → min (3)
Ax=b (4)
x≥0 (5)
Задача ЛП в стандартной форме:
Задача ЛП в канонической форме:
w=cx → min
Ax>b
x≥0
В обоих случаях А есть матрица размерности m x n, i -я строка которой совпадает с вектором аi[3,c.70].
Задача ЛП в общей форме сводится (в определенном смысле) к задаче ЛП в канонической (стандартной) форме. Под этим понимается существование общего способа построения по исходной задаче (в общей форме) новой задачи ЛП (в нужной нам форме), любое оптимальное решение которой "легко" преобразуется в оптимальное решение исходной задачи и наоборот. (Фактически, связь между этими задачами оказывается еще более тесной).
Тем самым мы получаем возможность, не теряя общности, заниматься изучением задач ЛП, представленных либо в канонической, либо в стандартной форме[6,c.90].
Ввиду этого наши дальнейшие рассмотрения задач ЛП будут посвящены, главным образом, задачам в канонической форме.
3. Прямая и обратная задача линейного программирования
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой.
Связь исходной и двойственной задач заключается главным образом в том, что решение одной из них может быть получено непосредственно из решения другой. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования (таблица 1)[4,c.70].
Таблица 1- Связь прямой и обратной задачи линейного программирования
Правила составления двойственной задачи:
1. Каждому i-му ограничению исходной задачи соответствует переменная yj двойственной задачи и, наоборот, каждому j-му ограничению двойственной задачи соответствует переменная xj исходной задачи.
2. Матрицы А ограничений 1 – 2 и А' ограничений 3' – 4' (таблица 1) взаимно транспонированы.
Следовательно, строка коэффициентов aij в j-м ограничении двойственной задачи есть столбец коэффициентов при xj в ограничениях 1 – 2 исходной задачи, и наоборот[9,c.101].
3. Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи

Зарегистрируйся, чтобы продолжить изучение работы

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

Достижение этой цели предопределяет постановку и решение следующих задач:

1. Рассмотреть сущность математического программирования.

2. Раскрыть понятие линейного программирования.

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

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

Содержание

Глава 1. Сущность Математического программирования 5

Глава 2. Линейное программирование. Постановка задач 10

2.1. Общие сведения о линейном программировании 10

2.2. Примеры задач линейного программирования 13

Глава 3. Методы решения задач линейного программирования 17

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

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

Список литературы 33

Вложенные файлы: 1 файл

курсач.doc

Факультет инноватики и управления

Кафедра управления качеством, техники и технологий

Отметка о допуске к защите

Оценка за защиту

по дисциплине Системный анализ

студент факультета управления и инноватики, 4 курс, группа УО-04

студент (факультет, курс, группа)

Ульянкин Кирилл Юрьевич____________

фамилия, имя, отчество

Профессор КУКТТ, д.т.н________

ученое звание, ученая степень, должность

_Антипова Татьяна Николаевна _______________

фамилия, имя, отчество

СОДЕРЖАНИЕ

Настоящая работа подготовлена в Королевском институте управления, экономики и социологии на кафедре Управление качеством и техники и технологий

Актуальность темы курсовой работы. Актуальность линейного программирования и обусловила выбор темы данной курсовой работы. Значимость выбранного вопроса определяется также тем, что использование метода линейного программирования представляет собой важность и ценность - оптимальный вариант выбирается из достаточно значительного количества альтернативных вариантов. Также все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Проблема данного исследования носит актуальный характер в современных условиях. Об этом свидетельствует частое изучение поднятых вопросов.

Тема "Линейное программирование" изучается на стыке сразу нескольких взаимосвязанных дисциплин. Для современного состояния науки характерен переход к глобальному рассмотрению проблем тематики "Линейное программирование". Вопросам исследования посвящено множество работ. В основном материал, изложенный в учебной литературе, носит общий характер, а в многочисленных монографиях по данной тематике рассмотрены более узкие вопросы проблемы "Линейное программирование". Однако, требуется учет современных условий при исследовании проблематики обозначенной темы.

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

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

Эволюция научных представлений и формирование направлений в области теории и практики системного подхода во многом определяется разработками ученых: Л. В. Канторовича, В. С. Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, А. Г. Аганбегяна, Д. Б. Юдина, Е. Г. Гольдштейна, Дж. Данцигом, Г. Куна, А. Таккера, Чарнеса и др.

Объектом исследования является раздел математического программирования – линейное программирование.

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

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

Достижение этой цели предопределяет постановку и решение следующих задач:

Рассмотреть сущность математического программирования.
Раскрыть понятие линейного программирования.
Ознакомиться с видами задач линейного программирования.
Показать применение симплексного и графического метода решения задач линейного программирования.

Структура курсовой работы. В соответствии с целью, задачами и логикой исследования работа состоит из введения, 3 глав, заключения, списка литературы.

Глава 1. Сущность математического программирования

Процессы принятия решений лежат в основе любой целенаправленной деятельности. В экономике они предшествуют созданию производственных и хозяйственных организаций, обеспечивают их оптимальное функционирование и взаимодействие”. В научных исследованиях – позволяют выделить важнейшие научные проблемы, найти способы их изучения, предопределяют развитие экспериментальной базы и теоретического аппарата. При создании новой техники – составляют важный этап в проектировании машин, устройств, приборов, комплексов, зданий, в разработке технологии их построения и эксплуатации; в социальной сфере – используются для организации функционирования и развития социальных процессов, их координации с хозяйственными и экономическими процессами. Оптимальные (эффективные) решения позволяют достигать цели при минимальных затратах трудовых, материальных и сырьевых ресурсов.

В классической математике методы поиска оптимальных решений рассматривают в разделах классической математики, связанных с изучением экстремумов функций, в математическом программировании. Математическое программирование является одним из разделов исследования операций – прикладного направления кибернетики, используемого для решения практических организационных задач. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий).

Значительное число задач, возникающих в обществе, связано с управляемыми явлениями, т. е. с явлениями, регулируемыми на основе сознательно принимаемых решений. Притом ограниченном объеме информации, который был доступен на ранних этапах развития общества, принималось оптимальное в некотором смысле решение на основании интуиции и опыта, а затем, с возрастанием объема информации об изучаемом явлении, – с помощью ряда прямых расчетов. Так происходило, например, создание календарных планов работы промышленных предприятий.

Совершенно иная картина возникает на современном промышленном предприятии с многосерийным и многономеклатурным производством, когда объем входной информации столь велик, что его обработка с целью принятия определенного решения невозможна без применения современных электронных вычислительных машин. Еще большие трудности возникают в связи с задачей о принятии наилучшего решения.

Под принятием решений в исследовании операций понимают сложный процесс, в котором можно выделить следующие основные этапы:

1-й этап. Построение качественной модели рассматриваемой проблемы, т. е. выделение факторов, которые представляются наиболее важными, и установление закономерностей, которым они подчиняются. Обычно этот этап выходит за пределы математики.

2-й этап. Построение математической модели рассматриваемой проблемы, т. е. запись в математических терминах качественной модели. Таким образом, математическая модель – это записанная в математических символах абстракция реального явления, так конструируемая, чтобы анализ ее давал возможность проникнуть в сущность явления. Математическая модель устанавливает соотношения между совокупностью переменных – параметрами управления явлением. Этот этап включает также построение целевой функции переменных, т. е. такой числовой характеристики, большему (или меньшему) значению которой соответствует лучшая ситуация с точки зрения принимающего решения. Итак, в результате этих двух этапов формируется соответствующая математическая задача. Причем, второй этап уже требует привлечения математических знаний.

3-й этап. Исследование влияния переменных на значение целевой функции. Этот этап предусматривает владение математическим аппаратом для решения математических, задач, возникающих на втором этапе процесса принятия, решения.

Широкий класс задач управления составляют такие экстремальные задачи, в математических моделях которых условия на переменные задаются равенствами и неравенствами. Теория и методы решения этих задач как раз и составляют содержание математического программирования. На третьем этапе, пользуясь математическим аппаратом, находят решение соответствующих экстремальных задач. Обратим внимание на то, что задачи математического программирования, связанные с решением практических вопросов, как правило, имеют большое число переменных и ограничений. Объем вычислительных работ для нахождения соответствующих решений столь велик, что весь процесс не мыслится без применения современных электронных вычислительных машин (ЭВМ), а значит, требует либо создания программ для ЭВМ, реализующих те или иные алгоритмы, либо использования уже имеющихся стандартных программ.

4-й этап. Сопоставление результатов вычислений, полученных на 3-м этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации. Здесь возможны два случая:

1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса. При этом уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (1-й этап), уточняется или строится заново математическая модель (2-й этап), решается соответствующая математическая задача (3-й этап) и, наконец, снова проводится сопоставление (4-й этап).

2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.

В математическом программировании можно выделить два направления.

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

Ко второму направлению – так называемому стохастическому программированию – относятся задачи, в которых исходная информация содержит элементы неопределенности, либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из главных трудностей стохастического программирования состоит в самой постановке задач, главным образом из-за сложности анализа исходной информации.

Традиционно в математическом программировании выделяют следующие основные разделы.

Линейное программирование – целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так, в линейном программировании появился раздел транспортных задач.

Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950;1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму… Читать ещё >

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

Основные методы математического программирования ( реферат , курсовая , диплом , контрольная )

Задачи оптимального планирования, связанные с отысканием оптимума заданной целевой функции (линейной формы) при наличии ограничений в виде линейных уравнений или линейных неравенств относятся к задачам линейного программирования.

1) Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования. Это объясняется следующим:
- § математические модели очень большого числа экономических задач линейны относительно искомых переменных;
- § эти типы задач в настоящее время наиболее изучены;
- § для них разработаны специальные конечные методы, с помощью которых эти задачи решаются, и соответствующие стандартные программы для их решения на ЭВМ;
- § многие задачи линейного программирования, будучи решенными, нашли уже сейчас широкое практическое применение в народном хозяйстве;
- § некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования[18].
Итак, линейное программирование — это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием.

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

Сущность линейного программирования состоит в нахождении точек наибольшего или наименьшего значения некоторой функции при определенном наборе ограничений, налагаемых на аргументы и образующих систему ограничений, которая имеет, как правило, бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи. Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи.

Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов наиболее выгодного (оптимального).

Составление математической модели задачи линейного программирования включает:

a) Выбор переменных. Переменными задачи называются величины которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = () Причём).

b) Составляют системы ограничений. Система ограничений — это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.

c) Выбор целевой функции. Целевая функция — это функция Z (X) которая характеризует качество выполнения задачи, экстремум которой надо найти [4, 12 с].

В общем случае задача линейного программирования может быть записана в таком виде:

Данная запись означает следующее: найти экстремум целевой функции (1) и соответствующие ему переменные X=(X₁, X₂,…, X_n) при условии, что эти переменные удовлетворяют системе ограничений (2) и условиям неотрицательности (3).

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

Множество допустимых решений образует область допустимых решений задачи (ОДР).

Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума [16].

2) Нелинейное программирование — это раздел математического программирования, изучающий задачи, где требуется определить значение некоторых параметров, при которых заданные функции не превосходят фиксированных величин, а некоторая выделенная, так называемая целевая функция достигает глобального минимума (максимума). При этом в отличие от линейного программирования, рассматриваемые функции не обязательно являются линейными.

Возникновение нелинейного программирования связано с тем, что предположение о линейной зависимости показателей рассматриваемого процесса от планируемых параметров при исследовании многих практических вопросов, в том числе экономических, оказывается слишком грубым.

Пусть f (x₁, х₂, …, х_n), g₁(x₁, x₂,…, x_n), g₂(x₁, x₂,…, x_n),…g_m(x_1,x₂,…, x_n) — нелинейные функции. Основная задача нелинейного программирования может быть сформирована следующим образом: требуется найти n-мерный вектор (x₁, x₂,…, x_n), удовлетворяющий условиям:

x_j 0, j = 1, 2, …, n; (4) ["https://referat.bookap.info", 19].

здесь R — отношения вида (?, ?,).

и доставляющий глобальный максимум (минимум) целевой функции f (x), то есть:

Определение 1. Множество точек, удовлетворяющих ограничениям (4) называется допустимым множеством задачи или допустимым планом.

Определение 2. Допустимая точка, в которой целевая функция (5) достигает максимума или минимума, называется оптимальным решением или оптимальным планом.

Нелинейное программирование охватывает столь широкий класс задач математического программирования, что эффективные универсальные численные методы их решения до настоящего времени не созданы. В первую очередь это связано с тем, что в задачах нелинейного программирования, как правило, существуют такие допустимые наборы параметров (удовлетворяющие условиям (4)), которые являются наилучшими среди достаточно близких к ним допустимых наборов, но которые, тем не менее, не являются оптимальными, то есть доставляющими искомый экстремум целевой функции. Задачи такого типа называются многоэкстремальными.

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

Для решения разных задач нелинейного программирования, отличающихся видом целевой функции и системы ограничений, разработаны специальные методы решения. К основным из них относятся:
- § метод множителей Лагранжа;
- § выпуклое программирование;
- § квадратичное программирование;
- § сепарабельное программирование [12, 45с.].
- 3) Динамическое программирование — это вычислительный метод для решения задач определенной структуры. Возникло и сформировалось в 1950;1953 гг. благодаря работам Р. Беллмана над динамическими задачами управления запасами. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму.
Основные необходимые свойства задач, к которым возможно применить этот принцип:
- § Задача должна допускать интерпретацию как n-шаговый процесс принятия решений.
- § Задача должна быть определена для любого числа шагов и иметь структуру, не зависящую от их числа.
- § При рассмотрении k-шаговой задачи должно быть задано некоторое множество параметров, описывающих состояние системы, от которых зависят оптимальные значения переменных. Причем это множество не должно изменяться при увеличении числа шагов.
- § Выбор решения (управления) на k-м шаге не должен оказывать влияния на предыдущие решения, кроме необходимого пересчета переменных.
Задача о выборе траектории, задача последовательного принятия решения, задача об использовании рабочей силы, задача управления запасами — классические задачи динамического программирования.

При постановке задач динамического программирования следует руководствоваться следующими принципами:

5. Определить, как изменяется состояние S' системы S под влиянием управление x_i на i-ом шаге: оно переходит в новое состояние:

6. Записать основное рекуррентное уравнение динамического программирования, выражающее условный оптимальный выигрыш W_i(S) (начиная с i-го шага и до конца) через уже известную функцию W_i+1(S):

Этому выигрышу соответствует условное оптимальное управление на i-м шаге x_i(S) (причем в уже известную функцию W_i+1(S) надо вместо S подставить измененное состояние .

7. Произвести условную оптимизацию последнего (m-го) шага, задаваясь гаммой состояний S, из которых можно за один шаг дойти до конечного состояния, вычисляя для каждого из них условный оптимальный выигрыш по формуле:

8. Произвести условную оптимизацию (m-1)-го, (m-2)-го и т. д. шагов по формуле (6.2), полагая в ней i=(m-1),(m-2),…, и для каждого из шагов указать условное оптимальное управление x_i(S), при котором максимум достигается.

Заметим, что если состояние системы в начальный момент известно, то на первом шаге варьировать состояние системы не нужно — прямо находим оптимальный выигрыш для данного начального состояния S₀. Это и есть оптимальный выигрыш за всю операцию.

Таким образом, в данной главе была выявлена природа математического программирования и рассмотрены его основные методы. В следующей главе будет рассмотрено практическое применение одного из этих методов [6, 366с.].

Читайте также: