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

Размещено на http://www.allbest.ru/

Вопрос №1. Какие Вы знаете математические методы, которые помогают находить оптимальные решения в различных производственных процессах

Решение.

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

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

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

џ методы, основанные на использовании неопределенных множителей Лагранжа;

џ вариационное исчисление;

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

џ принцип максимума;

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

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

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

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

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

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

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

Вопрос №2. Какие вы знаете способы решения задач нелинейного программирования

Решение.

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

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

Основные методы решения задач нелинейного программирования:

Ш метод Лагранжа

Ш метод допустимых (возможных) направлений или метод Зойтендейка

Ш выбор оптимального шага

Ш методы безусловной оптимизации:

§ методы безусловной оптимизации первого порядка:

- метод прямого поиска (метод Хука - Дживса)

- метод деформируемого многогранника (метод Нелдера - Мида)

- метод вращающихся координат (метод Розенброка)

- метод параллельных касательных (метод Пауэлла)

§ методы безусловной оптимизации первого порядка:

- метод наискорейшего спуска

- метод сопряженных градиентов

§ методы безусловной оптимизации второго порядка:

- метод Ньютона

Вопрос №3. В чем суть методов динамического программирования

Решение.

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

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

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

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

Вопрос №4. Что такое случайный процесс? Что такое Марковский случайный процесс? Какие виды Марковских случайных процессов Вы знаете? Приведите хотя бы по одному примеру для каждого вида случайных процессов

Решение.

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

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

Виды Марковских случайных процессов.

Различают Марковские случайные процессы:

џ с дискретным множеством состояний (число состояний конечно или счетно, переходы из состояния в состояние происходит скачком)

џ с непрерывным множеством состояний

а также различают процессы:

* с дискретным временем (моменты переходов фик5сированы)

* с непрерывным временем (моменты переходов случайны)

Примеры для каждого вида случайных Марковских процессов.

1.) Случайный Марковский процесс с дискретным состоянием и дискретным временем:

Выборочный контроль продукции:

дискретное состояние: S1 - годная продукция, S2 - негодная продукция, дискретное время: t1, t2 - время проверки.

2.) Случайный Марковский процесс с дискретным состоянием и непрерывным временем:

Случай отказа станка, машины, оборудования.

3.) Случайный Марковский процесс с непрерывным состоянием и дискретным временем:

Проверки термометра через определенное время.

4.) Случайный Марковский процесс с непрерывным состоянием и непрерывным временем:

Процесс разливки металл при контролируемой температуре



Вопрос №5. В каком из методов исследования операций используется термин «седловая точка»? Что это такое? Всегда ли она существует

Решение.

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

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

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

Первый игрок имеет m стратегий i = 1,2,...,m, второй имеет n стратегий j = 1,2,...,n. Каждой паре стратегий (i,j) поставлено в соответствие число а_ij, выражающее выигрыш игрока 1 за счёт игрока 2, если первый игрок примет свою i-ю стратегию, а 2 - свою j-ю стратегию.

Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i=), 2 - свою j-ю стратегию (j=), после чего игрок 1 получает выигрыш а_ij за счёт игрока 2 (если а_ij<0, то это значит, что игрок 1 платит второму сумму | а_ij|). На этом игра заканчивается. Каждая стратегия игрока i=; j =  часто называется чистой стратегией.

Если рассмотреть матрицу,

А =

то проведение каждой партии матричной игры с матрицей А сводится к выбору игроком 1 i-й строки, а игроком 2 j-го столбца и получения игроком 1 (за счёт игрока 2) выигрыша а_ij. Если в игре с матрицей А =, то говорят, что эта игра имеет седловую точку в чистых стратегиях и чистую цену игры

u = =.

Седловая точка- это пара чистых стратегий (i_о,j_о) соответственно игроков 1 и 2, при которых достигается равенство  = . В это понятие вложен следующий смысл: если один из игроков придерживается стратегии, соответствующей седловой точке, то другой игрок не сможет поступить лучше, чем придерживаться стратегии, соответствующей седловой точке. Математически это можно записать и иначе:

где i, j- любые чистые стратегии соответственно игроков 1 и 2; (i_о,j_о)- стратегии, образующие седловую точку.

Седловая точка -

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

«Седловая точка» существует далеко не всегда. Так, например, для матрицы такой точки не существует.

Вопрос 6.

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

Для производства двух видов изделий А и В используются три типа технологического оборудования. На производство единицы изделия А используется 16 ч оборудования I типа, 8 ч оборудования II типа и 5 ч оборудования III типа. На производство единицы изделия В используется 4 ч оборудования I типа, 7 ч оборудования II типа и 9 ч оборудования III типа. На изготовление всех изделий администрация предприятия может представить оборудование первого типа не более чем на 784 часа, оборудование второго типа - не более чем на 552 часа, а оборудование третьего типа - не более чем на 567 часов. Прибыль от реализации готового изделия А составляет 4 рубля, а изделия В - 6 рублей.

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

Является ли она задачей целочисленного программирования? Почему?

Решите данную задачу любым известным Вам способом.

Дайте словесный ответ на вопрос: «При каком выпуске изделий А и В прибыль предприятия будет наибольшей?»

Решение.

Вид ресурса	Объем ресурса	Нормы расхода на одно изделие
		А	В
Оборудование 1	784	16	4
Оборудование 2	552	8	7
Оборудование 3	567	5	9

Пусть  - объем производства товара А (шт.);  - объем производства товара В (шт.).

Тогда доход от продажи товара А - (руб.), а от продажи товара В - (руб.). - целевая функции в виде суммы дохода от продажи товаров А и В.

Ограничения:

- Количество часов, которое может отработать оборудование 1, не превышает 784 часа.

- Количество часов, которое может отработать оборудование 2, не превышает 552 часа.

- Количество часов, которое может отработать оборудование 3, не превышает 567 часов.

- Объемы производств не могут быть отрицательными.

Следовательно:

(час.)

(час.)

(час.)

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

Для этого сначала определим координаты точек пересечения прямых ограничений с осями координат:



Построение прямых ограничений:

Подставив точку (0;0) в исходные ограничения получим истинные неравенства и определим допустимые полуплоскости для ограничений, указав их стрелками у соответствующих прямых ограничений. В результате общей областью, разрешенной всеми ограничениями является многоугольник ABCДЕ.

- целевая прямая, где L (произвольное число, например, кратное 3 и 8).

Следовательно,

>

Помимо целевой прямой строим вектор из точки (0;0) в точку (4;6). При поиске max целевой функции передвигаем целевую прямую в направлении вектора .

Точкой max ЦФ будет последняя по ходу движения вершина ОДР.

Точка пересечения прямых:

>

Итак, точки максимума целевой функции (27, 48). Следовательно, прибыль предприятия будет наибольшей при выпуске 27 изделий А и 48 изделий В.

Вопрос 7. Найдите верхнюю цену и нижнюю цену игры, заданной матрицей А. Укажите оптимальные стратегии игроков и седловую точку, если она существует. Опишите словесно, что означают полученные результаты

1. А =

2. А =

3. А =

Решение.

1. А =

	3	4	3
	2	5	2
	3	5

Следовательно,

(верхняя цена или минимакс)

Верхняя цена игры показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1: .

(нижняя цена или максимин)

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

(седловая точка),

и (оптимальные стратегии игроков 1 и 2).

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

2. А =



	5	1	1
	4	2	2
	2	3	2
	2	3

Следовательно,

(верхняя цена или минимакс)

Верхняя цена игры показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1: .

(нижняя цена или максимин)

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

(седловая точка),

и (оптимальные стратегии игроков 1 и 2).

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

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

3. А =



	2	-1	1	-1
	-2	1	-1	-2
	-2	1	-2	-2
	2	-2	3	-2
	2	1	3

Следовательно,

(верхняя цена или минимакс)

Верхняя цена игры показывает, какой максимальный выигрыш за счёт своих стратегий может себе гарантировать игрок 1: .

(нижняя цена или максимин)

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

Получили, , следовательно, матрица не имеет седловой точки.

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

Вопрос 8. Изготовление деталей А и В состоит из двух операций, происходящих последовательно на станках I и II, и прохождения ОТК на приборе III. Время работы каждого станка для изготовления одной детали указаны в таблице. С помощью диаграммы Ганта укажите оптимальный порядок прохождения деталей по указанным операциям.

	А	В
I	15	10
II	15	20
III	10	15

Решение.

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

Первый вариант:

Задача Начало Конец Обработка А на 1 0 15 Обработка В на 1 15 25 Обработка А на 2 15 30 Обработка В на 2 30 50 А на ОТК 30 40 В на ОТК 50 65

Размещено на http://www.allbest.ru/

общее время - 65 минут

Второй вариант:

Задача Начало Конец Обработка В на 1 0 10 Обработка А на 1 10 25 Обработка А на 2 30 45 Обработка В на 2 10 30 А на ОТК 45 55 В на ОТК 30 45
общее время - 55 минут

Следовательно, оптимальный порядок выполнения операций: обработка детали В на станке 1 > обработка детали А на станке 1 > обработка детали В на станке 2 > обработка детали А на станке 1> деталь В на ОТК > деталь А на ОТК.

Размещено на Allbest.ru