microbik.ru
1 2 3 4
Задача 1. Для приведенной прямой задачи линейного программирования:

а) изобразить на плоскости XoY множество допустимых решений;

б) нарисовать вектор наискорейшего возрастания (нормаль) целевой функции;

в) найти решение прямой задачи (указать оптимальное решение и значение целевой функции);

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

д) найти ее оптимальное решение и значение целевой функции.
F = 15x1 + 6x2


Задача 2. Найти решение следующих задач, используя теорему равновесия.

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



(Лекции и пояснительный материал к задачам ниже)


МЕТОДЫ ОПТИМИЗАЦИИ (ИССЛЕДОВАНИЕ ОПЕРАЦИЙ).

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

С простейшим методом отыскания минимума или максимума функции одного переменного на заданном интервале Вы знакомились в курсе «Дифференциальное исчисление». Для этого в критической (стационарной) точке анализировали знаки, точнее смену знака первой производной. Или, используя второй признак экстремума, рассматривали знак второй производной в критической точке:

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

Эта же идея используется для отыскания минимума (максимума) функции от n переменных.

Сформулируем необходимый и достаточный признаки локального экстремума у функции f(x), зависящей от n переменных.

Необходимый признак:

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

Достаточный признак:

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

В случае, если в задаче кроме функции f(x), минимум которой требуется найти, заданы уравнения связи (условия)

,

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

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

,

таких, что

.

(здесь обходятся даже без нахождения стационарных точек). К таким методам относятся:

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

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

-метод секущих и т.д.

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

Такие задачи часто возникают в исследовании операций.

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

Приведем примеры задач исследования операций:

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

(например: -размеры контрольных партий,

-последовательность контрольных операций,

-правила отбраковки),

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

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

Целевая функция – это критерий эффективности.

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

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

Все факторы, входящие в описание операции разделим на:

  • постоянные факторы, на которые мы не можем влиять (),

  • зависимые факторы, которые в известных пределах можно выбирать по своему усмотрению ().

Критерий эффективности, выражаемый некоторой функцией, называется целевой функцией. Она зависит от факторов обеих групп:

).

Сформулируем оптимизационную задачу:

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

, i=1,2,…,m,

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

При этом – оптимальное решение.

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

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

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

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

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

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

В приведенной (довольно популярно изложенной) книге авторов Ильина и Солопанов описаны модели линейной оптимизации и прорешаны довольно подробно прямая и двойственная задачи. Приведены графическое решение таких задач (стр. 9–20) и решение с помощью симплекс-таблиц (стр. 21 –30).
В дополнение к указанной в книге литературе можно почитать еще и следующие:

  1. А.В.Пантелеев, Т.А.Летова Методы оптимизации в примерах и задачах М., В.школа. 2009г.

  2. Б.В.Соболь, Б.Ч.Месхи, Г.И.Каныгин Методы оптимизации. Практикум. 2009г.

  3. Г.И.Просветов Методы оптимизации. Задачи и решения. Альфа-Пресс. 2009г.

  4. Н.Ш.Кремер и др. Исследование операций в экономике. М., 1997г.




следующая страница >>