Линейное и нелинейное программирование - OXFORDST.RU

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

Лекция 3: Математическое программирование. Линейное программирование. Виды задач линейного программирования. Постановка задач линейного программирования и исследование их структуры. Решение задач линейного программирования симплекс-методом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача ЛП в канонической форме:

( 2.1)
( 2.2)
( 2.3)

Задача ЛП в стандартной форме:

В обоих случаях А есть матрица размерности m x n , i -я строка которой совпадает с вектором аi .

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

Лабораторная работа № 3 Оптимизация Линейное и нелинейное программирование

Лабораторная работа № 3

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

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

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

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

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

где f – вектор коэффициентов, и удовлетворяет заданным линейным ограничениям: неравенствам

>> b = [250; 60; 100; 220];

>> % Определение коэффициентов целевой функции

>> % Задание ограничений снизу на переменные

>> % Решение и вывод результата в командное окно

>> x = linprog(f, A, b, [ ], [ ], lb)

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

>> [x, p] = linprog(f, A, b, [],[], lb, [ ]);

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

а ограничения в общем случае совпадают с ограничениями (16.2 – 16.4) в задаче линейного программирования. Для решения задач квадратичного программирования предназначена функция quadprog. Интерфейс quadprog практически не отличается от linprog, за исключением того, что первыми двумя входными параметрами являются массив н и вектор-столбец f, соответствующие матрице Н и вектору f целевой функции. Вместо матриц и векторов отсутствующих ограничений задаются пустые массивы.

Проиллюстрируем использование функции quadprog на примере задачи Марковица об определении состава инвестиционного портфеля рискованных ценных бумаг. Инвестор предполагает вложить свободные денежные средства в рыночные активы (ценные бумаги, акции) с целью получения дохода в будущем периоде. Для уменьшения рисков он выбрал для вложения четыре различных акции, которые обозначим А1, А2, A3, А4. Перед инвестором стоит задача определить, какую часть своих средств вложить в каждый актив так, чтобы получить желаемую доходность портфеля с наименьшим риском. Портфель определяется вектором долей от суммы инвестиций для покупки акций:

Читайте также  Лирика Александра Блока

x = (xl, x2, x3, x4)T, х1+х2+х3 + х4=1, хi > 0 (i = 1,2,3,4).

Риск оценивается как величина среднеквадратического отклонения ожидаемой доходности. Будем считать, что инвестор каким-либо способом произвел оценку ожидаемой доходности для каждой ценной бумаги, т. е. построил вектор доходностей у = (у1, y2, y3, y4)T и вычислил матрицу ковариации V.

Если вектор у и матрица V известны, то доходность портфеля и его дисперсия вычисляются по формулам:

Формальная постановка задачи Марковица приводит к задаче квадратичного программирования: найти минимум функции

Величина желаемой доходности портфеля а должна быть не меньше минимальной и не больше максимальной доходности выбранных для инвестирования ценных бумаг. Неравенство (16.9) – одностороннее покомпонентное ограничение типа (16.4). Ограничения (16.7) и (16.8) – это ограничения вида (16.3), поэтому их следует объединить в одно, построив матрицу

Пусть заданы следующие значения для матрицы V, вектора y и желаемой

доходности портфеля a:

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

Для решения задачи о формировании портфеля с фиксированной доходностью составьте файл-программу risk_asset. Возможный вариант исходного текста файл-программы risk_asset приведен в листинге 16.2.:

% Задание матрицы коэффициентов целевой функции

V =[102.0 27.1 -52.3 66.5;

27.1 148.8 42.1 -66.4;

-52.3 42.1 246.5 56.9;

66.5 -66.4 56.9 272.3];

% Задание ограничений типа равенств

Aeq = [11.3 13.2 16.1 17.4;

% Задание ограничений снизу на переменные

% Решение и вывод результата в командное окно

x = quadprog( V, [],[], [ ], Aeq, beq, lb)

Warning: Large-scale method does not currently solve this problem formulation, using medium-scale method instead.

> In quadprog at 262

In risk_asset at 13

При этом в командное окно вывелось сообщение о применении Medium-scale алгоритма вместо Large-scale, принятого по умолчанию (см. разд. »Параметры оптимизации»).

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

среди всех векторов х, удовлетворяющих системе линейных ограничений (16.2–16.4) и дополнительных неравенств и равенств

c(x) > x= fmincon (@myfun, [0.7 0.7], [], [], [],[],[],[],@mycon)

Warning: Large-scale (trust region) method does not currently solve this type of problem,

using medium-scale (line search) instead.

> In fmincon at 317

Optimization terminated: magnitude of directional derivative in search

direction less than 2*options. TolFun and maximum constraint violation

is less than options. TolCon.

No active inequalities.

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

>> [x, f,flag]= fmincon (@myfun, [0.7 0.7], [], [], [],[],[],[],@mycon)

Warning: Large-scale (trust region) method does not currently solve this type of problem,

using medium-scale (line search) instead.

> In fmincon at 317

Optimization terminated: magnitude of directional derivative in search

direction less than 2*options. TolFun and maximum constraint violation

is less than options. TolCon.

No active inequalities.

Значение flag большее нуля свидетельствует о том, что решение успешно найдено.

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

Математическое программирование (линейное, нелинейное, динамическое, теория графов). Сущность линейного программирования

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

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

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

— выпуклые: линейное и выпуклое программирование;

— динамические: динамическое программирование;

— дискретные: решение в целых числах; и

— стохастические: стохастическое программирование.

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

U = f(x) → max; x ∈ M,

где x = (x1, x2. xn); M — область допустимых значений переменных x1, . xn; f(x) — целевая функция.

Частный случай задачи М. п. — “классическая задача”. В ней область M представлена равенствами:

где g(x) — вектор функций ограничений; b — вектор констант ограничений.

Названные выше разнообразные дисциплины отличаются друг от друга видом целевой функции f(x) и области М. Напр., если f(x) линейна, а М — выпуклый многогранник, имеем задачу линейного программирования; если же дополнительно ставится условие, чтобы переменные были целочисленными, то имеем задачу целочисленного программирования; если зависимость U от x (т. е. форма f) носит нелинейный характер, то задачу нелинейного программирования.

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

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

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

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

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

Общий вид записи:

Найти переменные , удовлетворяющие системе уравнений:

V( )= i=1, 2..m

И обращающие в максимум (минимум) целевую функцию Z=f( ).

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

Свойства задач для этого метода:

— задача должна допускать интерпретацию как n-шаговый процесс принятия решений.

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

-должно быть заданное некоторое множество параметров, которое описывает состояние системы, от которых зависят оптимальные решения переменных

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

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

Теория графов: Графом G=(V,E) (или G=(p,q)) называется пара множеств, где V – непустое, конечное множество, состоящее из р элементов (вершин графа G), E – множество неупорядоченных пар элементов q (ребра).

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

Граф, состоящий из дуг, называется ориентированным (оргрфом). Граф образованный ребрами – неориентированный.

Читайте также  Аменорея (Отсутствие менструации)

Если Е – пустое множество, то граф G – пустой граф.

Мультиграф– между двумя вершинами можно нарисовать 2 и более ребра.

Если имеются вершины V1 и V2 и ребро е образовано ими, то говорят, что ребро е инцидентно вершинам V1 и V2. V1 и V2 – смежные.

Степенью вершины называется число ребер инцидентных данной вершине (количество выходящих из нее ребер).

Вершина, степень которой равна 1, называется висящей.

Вершина, степень которой равна 0, называется изолированной.

Последовательность ребер V, V1… называется маршрутом.

Если в маршруте не указаны ребра, то такой маршрут называется цепью.

Если V=Vn, то цепь называют циклом.

Если в цепи не повторяются вершины, то такая цепь называется простой.

Граф называется связным, если любая пара его вершин соединена маршрутом.

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

Связный граф, не имеющий циклов – дерево.

Дата добавления: 2015-04-20 ; просмотров: 21 | Нарушение авторских прав

ГОСы 2012

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

Математическая модель задачи нелинейного программиро­вания в общем виде формулируется следующим образом: найти вектор = 1, x2, …, xn), удовлетворяющий системе ограни­чений

и доставляющий экстремум (наибольшее или наименьшее зна­чение) целевой функции

Нелинейное программирование применяется при прогнози­ровании промышленного производства, управлении товарными ресурсами, планировании обслуживания и ремонта оборудова­ния и т.д.

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

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

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

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

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

  • выпуклое программирование,
  • квадратичное программирование,
  • целочисленное программирование,
  • стохастическое программирование,
  • динамическое программирование и др.

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

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

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

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

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

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

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

  • однокритериальные,
  • многокритериальные.

По длине вектора методы делятся на:

  • однопараметрические или одномерные (n=1),
  • многопараметрические или многомерные (n>1).

По наличию ограничений методы нелинейного программирования делятся на:

  • без ограничений (безусловная оптимизация),
  • с ограничениями (условная оптимизация).

По типу информации, используемой в алгоритме поиска экстремума методы делятся на:

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

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

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

Автор работы: Пользователь скрыл имя, 23 Мая 2013 в 23:36, реферат

Краткое описание

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

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

Доклад по социолог. исследованиям.docx

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

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

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

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

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

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

-максимум или минимум целевой функции (критерий оптимальности);

-систему ограничений в форме линейных уравнений и неравенств.

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

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

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

Читайте также  Быт, нравы и верования восточных славян

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

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

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

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

  1. Линейное программирование относится к сфере:

А) логических методов.

Б) математических методов.

В) теоретических методов.

2. Что является задачей динамического программирования?

А) Задачи, которые встречаются в научно-исследовательских проектах и в задачах проектирования.

Б) Распределение дефицитных капитальных вложений между новыми направлениями их использования.

В) Выбор из множества допустимых планов наиболее выгодного (оптимального).

3. Большинство задач математического программирования, которые встречаются в научно-исследовательских проектах и в задачах проектирования — это задачи

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: