Практическая работа №8. Математическое программирование Общие положения, основные понятия Содержание

• Название: Математическое программирование Общие положения, основные понятия Содержание
• Дата: 15.11.2021
• Размер: 153.1 Kb.
• Имя файла: Практическая работа №8.pptx
• Тип: Документы; #272971

Математическое программирование

Общие положения, основные понятия

Содержание

• 1. Определение и примеры задач математического программирования.
• 2. Общая постановка задач линейного программирования и алгоритм их решения (симплекс метод)

Общая содержательная постановка задач математического программирования

Содержательная постановка задач:

Дано:

• 1. Цели.
• 2. Вектор переменных.
• 3. Ограничения, налагаемые на значения, принимаемые переменными.
• Требуется: определить такой вектор переменных, при котором:
• 1. Целевые функции принимали бы наилучшие значения.
• 2. Ограничения на значения, принимаемые переменными, не нарушались.

Общая формальная постановка задач математического программирования

Цели

Ограничения

Вектор переменных

КЛАССИФИКАЦИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

Задачи нелинейного программирования

Задачи линейного программирования

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

Математическое программирование

Многокритериальные задачи

Задачи с одним критерием

Задачи теории игр

h

h

r

Пример содержательной постановки многокритериальной задачи

Требуется определить оптимальные потоки i-го вида продуктов j-ому потребителю xi,j, если известны пропускные способности дуг ri,j и стоимости ci,j транспортировки по ним каждого вида продукта, а также возможности каждого i-го источника и каждого j-го стока по каждому виду продуктов.

Цели:

• Минимальные издержки на транспортировку.
• Максимальное удовлетворение запросов потребителей.

Транспортная задача

Частным случаем рассмотренной выше задачи является ТРАНСПОРТНАЯ ЗАДАЧА, основные отличия которой от сформулированной выше заключаются в:

• МИНИМИЗАЦИИ ТОЛЬКО ТРАНСПОРТНЫХ ИЗДЕРЖЕК (одна целевая функция);
• УДОВЛЕТВОРЕНИИ ПОТРЕБНОСТИ ВСЕХ «потребителей»;
• Как правило, речь идет об однопродуктовых потоках.

• Общая постановка задач линейного программирования и алгоритм их решения

Формальная постановка задачи ЛП

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

• Дж. Данциг, корпорация “RAND”

Целевая функция

Симплекс

Основные постулаты линейного программирования

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

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

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

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

Свойство 3. Множество решений задачи линейного программирования выпукло.

Свойство 4. Если допустимая область ограничена, то любая задача линейного программирования имеет оптимальное решение.

Свойство 5. Необходимым и достаточным условием существования решения задачи линейного программирования на максимум (минимум) является ограниченность

целевой функции сверху (соответственно снизу) в допустимой области.

Все перечисленные свойства справедливы и в общем случае (n≥2).

Схема решения ЛП задачи

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

Пример 1

Определить оптимальное решение задачи:

где: хi – непрерывная неотрицательная переменная;