Отыскание экстремума функций многих переменных

Численные методы отыскания безусловного экстремума

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

Литература

Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.:Наука, 1978, 351 с.

С. Гасс. Линейное программирование. М. 1961, 300 с.

А. Кофман. Методы и модели исследования операций. М.: Мир, 1966, 523 с.

Д. Химмельблау. Прикладное нелинейное программирование. М: Мир, 1975, 522 с.

С. Гасс. Путешествие в страну линейного программирования. М.: Мир, 1973, 175 с.

Введение

* Математическое программирование ― раздел, математически направленный на решение оптимизационных задач.

(Термин введен в ≈ 1950 г. Робертом Дорфманом)

В настоящее время математическое программирование объединяет линейное программирование, выпуклое программирование, нелинейное программирование, целочисленное программирование, динамическое программирование, программирование при наличии неопределенности (стохастическое программирование) и т. д.

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

Задача, допускающая лишь одно решение, не требует оптимизации!

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

Можно (условно) провести следующую классификацию задач МП (математического программирования).

I

II

III

И т. д.

Классы задач МП определяются видом математических моделей, используемых в этих задачах.

2. Математические модели и методы их построения

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

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

Математические модели могут быть получены на основе:

- фундаментальных физических законов (закон Ома, всемирного тяготения и т.д.)

- на основе имеющихся данных об объекте (журналы работы участка и т.д.)

- на основе отдельно выполненных экспериментов (задачи обработки результатов измерений и т.д). (Курс "Методы обработки данных")

Предпочтительнее использование моделей 1-ого вида, т.к в них отражен (сконцентрирован) опыт многих поколений человечества.

Пример 1: детерминированная модель ― движение маятника

- гармоническое колебание с периодом

Пример 2:

получены следующие данные о расходах горючего:

y=kX, k=0,1л/км, y=0.1a, y=[л], x=[км]

3. Выбор целевой функции. Характер ограничений

При определении цели всегда встает вопрос: "Какой ценой эта цель будет достигнута?"

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

Подлежащая оптимизации экономическая функция должна быть единственной!

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

Пусть требуется производить два товара P1 и P2. Первый продается с прибылью 100р. за штуку, второй - 50 за штуку.
x1 и x2 - количество производимых товаров.

Общая средняя прибыль равна: B = 100x1 + 50x2

Изделия по мере производства подвергаются обработке, которая длится 5 сек для P1 и 1 сек для P2.