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




НазваниеЗадача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений
страница1/4
Дата конвертации07.02.2013
Размер307.13 Kb.
ТипЗадача
  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г.


  1   2   3   4

Похожие:

Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛабораторная работа №2 Многокритериальные задачи линейного и нелинейного программирования Цель работы
Исследование многокритериальных задач линейного и нелинейного программирования при различных компромиссных критериях [5]
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconМногоиндексные задачи распределения ресурсов в иерархических системах
Задача распределения ресурсов в иерархических системах формализуется в виде многоиндексной задачи линейного программирования с ограничениями...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛинейное программирование
Среди оптимизационных задач в теории принятия решений наиболее известны задачи линейного программирования, в которых максимизируемая...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛабораторная работа по дисциплине «Теория Игр и Исследование Операций» Тема: многокритериальные задачи линейного и нелинейного программирования
...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛабораторная работа №4 Решение прямой и обратной задач магниторазведки для тел простой формы Шар Решение прямой задачи
Прямая задача магниторазведки – это нахождение аномального магнитного поля, создаваемого объектом по известным геометрическим и физическим...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛабораторная работа №4 Использование Microsoft Office Excel для анализа данных и решение задач оптимизации
Цель работы: изучить встроенные в Excel возможности анализа данных на примере проведения регрессионного анализа. Ознакомиться со...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛекция №2 (Теорема 1, леммы 1, 2, следствия 1, 2), [2, 3, 5] Двойственные задачи линейного программирования. Лекция №2 ( включая теорему 2), [4]
Теория двойственности нелинейного программирования. Лекция №2 (Теорема 1, леммы 1, 2, следствия 1, 2), [2, 3, 5]
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconТема: Основы теории колебаний и волн (2ч)
Задача Некоторая точка движется вдоль оси x по закону x = a sin2 (ωt π/4). Найти: а) амплитуду и период колебаний; изобразить график...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconЛабораторная работа 4 Определение оптимального ассортимента тканей, вырабатываемого фабрикой
Задачами линейного программирования (ЛП) называются оптимизационные задачи, в которых ограничения и целевая функция линейны относительно...
Задача Для приведенной прямой задачи линейного программирования: а изобразить на плоскости XoY множество допустимых решений iconМатематика для экономистов в разделе «Аналитическая геометрия»
«Аналитическая геометрия» рассматриваются такие темы, как элементы векторной алгебры; уравнение линий на плоскости; общее и частичное...
Разместите кнопку на своём сайте:
kurs.znate.ru


База данных защищена авторским правом ©kurs.znate.ru 2012
обратиться к администрации
kurs.znate.ru
Главная страница