Green-sell.info

Новые технологии
2 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

Дата добавления: 2013-12-23 ; просмотров: 3031 ; Нарушение авторских прав

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

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

U=f(X)→ max;X,W,

где X = (x1,x2,…,xn);

W — область допустимых значений переменных x1,x2,…,xn;

f(X) — целевая функция.

Для того чтобы решить эту оптимизационную задачу, достаточно указать XОW такое, что f(X) ≥f(X) при любом XОW, f(X) ≤f(X)при любом XОW. Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функциейn переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области W:

· задачи линейного программирования, если f(X) и W линейны;

· задачи целочисленного программирования, если ставится условие целочисленности переменных x1,x2,…,xn;

· задачи нелинейного программирования, если f(X) или W имеют нелинейный характер.

Общая постановка задачи нелинейного программирования выглядит следующим образом. Найти неотрицательные значения элементов решения x1,x2. xn,удовлетворяющие ограничениям произвольного вида и обращающие в максимум произвольную нелинейную функцию этих элементов решения:

W=f(x1,x2. xn)→ max.

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

Идея метода штрафных функций в том, что вместо наложения системы ограничений, налагается некоторый достаточно большой «штраф» за нарушение ограничений, который добавляется к целевой функции W. Штраф имеет общий вид: a(x1,x2. xn), где a — коэффициент пропорциональности (если W максимизируется он отрицателен, если минимизируется — положителен). Далее можно, увеличивая абсолютное значение a, посмотреть, как изменяется при этом оптимальное решение (x1°,x2°. xn°)и, когда оно практически перестанет меняться, остановиться на нем.

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

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

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

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

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

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

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

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

В процессе решения задачи оптимизации обычно необходимо найти оптимальные значения некоторых переменных, определяющих данную задачу. Примерами таких переменных являются: численность исполнителей, станков, машин и др. Число переменных (обозначим их X1, X2. Хn, где n — число переменных) характеризует степень сложности задачи оптимизации.

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

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

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

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

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

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

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

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

Сформулируем общую задачу математического программирования.

Дадим количественную, математическую постановку этой задачи.

Найти значения «n» переменных X1, X2. Хn , которые неотрицательны

Xi 0, i=1,2,…,n

удовлетворяют «m» ограничениям:

и максимизируют функцию:

Z=F(X1,X2,…,Xn) MAX

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

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

В основе той или иной классификации лежит признак, по которому объекты разделяются или объединяются в классы.

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

Если функция цели и ограничения являются линейными:

Z=F(X1,X2,…,Xn)=C1X1+C2X2+…CnXn MAX;

где (Ci),(Bj),(Aij) — известные постоянные, то данная задача является задачей линейного программирования.

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

Частным случаем задач нелинейного программирования являются задачи целочисленного программирования. От задач линейного программирования они отличаются только наличием условия целочисленности переменных X1, X2. Хn.

Если целевая функция задачи математического программирования квадратичная, но все её ограничения линейны, то такую задачу называют задачей квадратичного программирования. Линейные ограниче­ния, для данной задачи записываются так же как для задачи линейного программирования, а целевая функция имеет вид:

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

Z=F(X1,X2)=X1*X2 MAX;

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

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

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

Читать еще:  Подпрограммы в структурном программировании

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

— задача управления запасами;

— задачи замены оборудования;

— задача выбора оптимальных режимов движения;

— задача выбора оптимальной структуры.

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

Примерами распределительных задач являются:

транспортная задача, в которой рассматривается вопрос об оптимальном прикреплении пунктов производства и пунктам потребления;

задача о назначении, в которой рассматривается вопрос об опти­мальном прикреплении производителя работ к объекту производст­ва;

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

задача o выборе рациона;

задача выбора применения ресурсов;

задача выбора типажа и другие задачи.

Задача управления запасами формулируется следующими образом: имеется некоторое количество запасов, хранение которых связано с расходами. Однако и отсутствие запасов иногда недопустимо или при­водит к расходам. Требуется найти такой размер запасов(или порядок их пополнения), при котором расходы будут минимальными.

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

Задача замены оборудования — состоит в решении вопроса: продолжить производить или эксплуатировать старое оборудование или же заменить его новым, более совершенным, т.е. решается вопрос построения оптимального плана технического переоснащения производ­ства.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существует несколько методов решения задач ЛП. В данной работе будут рассмотрены некоторые из них, в частности:

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

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

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

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

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

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

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

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

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

Читать еще:  Дана задача линейного программирования

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

Пусть процесс оптимизации разбит на 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-го шага.

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

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

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

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

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

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

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

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

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

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

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

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

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

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

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

Читать еще:  Программирование 1с 7

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

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

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

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

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

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

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

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

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

Квадратичное программирование – целевая функция квадратичная, а ограничениями являются линейные равенства и неравенства.

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

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

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

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

ОБЩАЯ ПОСТАНОВКА И РАЗНОВИДНОСТИ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ;

Оптимальный план оптимальный план

Исходная ЗЦЛП №1

( оптимальный план )

оптимальный план ОДР пуста.

х1=1, х2=1, fmax=32 х1=, х2=2, fmax=37

оптимальный план ОДР пуста

х1=0, х2=, fmax=35,75

Оптимальный план ОДР пуста

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

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

и некоторая система ограничений , наложенных на переменные x1, x2, . . . , xn:

Требуется найти такой набор значений переменных x1, x2, . . . , xn, который удовлетворяет ограничениям (7.2), и при этом условии минимизирует или максимизирует функцию (7.1).

Если все фигурирующие в (7.1) и (7.2) функции линейны, то мы имеем ЗЛП. В противном случае получается задача нелинейного программирования.

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

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

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

Наконец отметим, что встречаются задачи математического программирования, в которых исходные данные являются случайными величинами. Такие задачи изучает стохастическое программирование. Стохастическое программирование использует теоретико-вероятностные, статистические и оптимизационные методы.

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

ЛИТЕРАТУРА

1. Крушевский А.В., Швецов К.М. Математическое программирование и моделирование в экономике.-К.: Вища шк., 1979

2. Кузнецов Ю.Н., Кузубов В.М., Волощенко А.Б. Математическое программирование.-М.: Высш.шк.,1980

3. Таха X. Введение в исследование операций. (В 2-х книгах).-
М.:Мир,1985

4. Мину М. Математическое программирование. Теория и
алгоритмы.-М.: Наука, 1990.

Содержание

1. РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ МЕТОДОМ ГАУССА – ЖОРДАНА.

1.1. Основные понятия .

1.2. Приведение системы линейных уравнений к жордановой форме.

1.3. Понятие общего, частного и базисного решений.

2.ОБЩИЕ СВОЙСТВА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ .

2.І. Пример задачи линейного программирования —

задача об использовании оборудования.

2.2. Задача об использовании сырья.

2.3. Задача составления рациона (задача о диете).

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

2.5. Геометрический метод решения ЗЛП.

2.6. Канонический вид ЗЛП.

2.7. Понятие опорного плана ЗЛП.

3. СИМПЛЕКСНЫЙ МЕТОД РЕШЕНИЯ ЗЛП

3.1. Общая характеристика и основные этапы симплекс –метода

3.2.Табличный вид ЗЛП. Симплекс — таблицы.

3.3. Условие оптимальности опорного плана.

3.4. Условие неразрешимости ЗЛП из-за неограниченности снизу на ОДР целевой функции.

3.5. Переход к новому опорному плану.

3.6. Табличный симплекс-алгоритм.

3.7. Отыскание исходного опорного плана ЗЛП методом искусственного базиса

3.8. Вырожденность опорного плана. Зацикливание.

4. Двойственность в линейном программировании . 70

4.1. Экономическая интерпретация двойственных задач . 70

4.2. Понятие двойственной задачи . 71

4.3. Теоремы двойственности . 72

5. Транспортная задача. . 50

5.1. Задача о перевозках . . 50

5.2. Общая постановка транспортной задачи . 51

5.3. Отыскание исходного опорного плана . 52

5.4. Циклы пересчета . 54

5.5. Потенциалы . 57

5.6. Алгоритм решения транспортной задачи методом потенциалов . 60

5.7. Открытые транспортные задачи . 63

6. ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ.. 70

6.1. Общая постановка задачи целочисленного линейного программирования (ЗЦЛП).

6.2. Целочисленная задача об использовании сырья.. 70

6.3. Задача о рюкзаке. . 71

6.4. Решение ЗЦЛП методом округления.

6.5. Метод ветвей и границ.

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

Ссылка на основную публикацию
Adblock
detector