Классификация оптимизационных задач

Пахомова Наталья Алексеевна

История возникновения

1885г. Фредерик Тейлор – вывод о возможности применения научного анализа

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

Задачи управления запасами
Задачи распределения ресурсов
Задачи ремонта

Оптимальное математическое программирование

ЦЕЛЬ (критерий, целевая функция)
F(x1;x2;…;xn) → экстремум
ОГРАНИЧЕНИЯ (условия, требования)
Gj(x1;x2;…;xn) [>;≥;=;<;≤]

Полное решение поставленной задачи не найдено, но получены существенные результаты во

История линейного программирования

КАНТОРОВИЧ Леонид Витальевич
(1912-86),
российский математик и экономист,
академик

Задача линейного программирования имеет следующий вид

1) Целевая функция
Z= → экстремум

СПОСОБЫ РЕШЕНИЯ ЛИНЕЙНЫХ ЗАДАЧ

Графический способ
Средствами Excel (Поиск решения)
Средствами MathCAD (функция

Пример:

Графический способ

Найдем графическое решение неравенств

Графиком целевой функции является семейство параллельных прямых

Точка входа – точка минимума

2

2

Точка выхода – точка максимума

8

4

СПОСОБ ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ (СИМПЛЕКСНЫЙ)

Симплексный метод требует преобразования
имеющейся модели к каноническому

Последовательное преобразование Жордановой таблицы

Задача считается решенной, если коэффициенты при переменных

Правила выбора разрешающего элемента

Разрешающий элемент не может находиться в столбце свободных

Предыдущая таблица Последующая таблица

Предыдущая таблица Последующая таблица

Предыдущая таблица Последующая таблица

Меняем заголовки строки и столбца, соответствующие R

Предыдущая таблица Последующая таблица

На место R ставим обратную величину

Предыдущая таблица Последующая таблица

Разрешающий столбец делим на R

Предыдущая таблица Последующая таблица

Разрешающую строку делим на число, противоположное R

Предыдущая таблица Последующая таблица

Остальные элементы находим по правилу прямоугольника

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

Исходная форма Каноническая форма
Z=x1+x2→min Z=x1+x2→min
3x1+x2≥8 y1=3x1+x2-8
x1-4x2≤19

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

Исходная форма Каноническая форма
Z=x1+x2→min Z=x1+x2→min
3x1+x2≥8 y13x1

Исходная форма Каноническая форма
Z=x1+x2→min Z=x1+x2→min
3x1+x2≥8 y1 3x1+ x2-8 ≥0
x1-4x2≤19 y2 -x1+4x2+19 ≥0
2x1+3x2≤28

Исходная форма Каноническая форма
Z=x1+x2→min Z=x1+x2→min
3x1+x2≥8 y1=3x1+x2 ─ 8
x1-4x2≤19 y2= ─ x1+4x2+19
2x1+3x2≤28 y3=

Все коэффициенты канонической формы заносят в Жорданову таблицу

В заголовках столбцов этой

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Для нашей задачи таблица будет выглядеть следующим образом

Рассмотрим первую таблицу нашей задачи

Находим разрешающий элемент: -8/3, -8/1, -8/1,-8/3

Меняем заголовки

На место разрешающего элемента пишем обратный

Столбец делим на разрешающий элемент

Сроку делим на (– R)

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Остальные элементы находим по правилу прямоугольника

Вторая таблица:

Есть отрицательный элемент в последней строке

-8/3

Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам

-51/13, -8/3

Наибольшее из всех возможных отношений соответствующих свободных членов к

-12/4, -51/13, -8/3

Наибольшее из всех возможных отношений соответствующих свободных членов к

-16/8, -12/4, -51/13, -8/3; наибольшее число -16/8=-2

Наибольшее из всех возможных отношений

Разрешающий элемент (– 8 )

Третья таблица:

Третья таблица:

В последней таблице в столбце свободных членов нет отрицательных элементов,

Третья таблица:

В последней таблице в столбце свободных членов нет отрицательных элементов,

Третья таблица:

( 1* (-8) - 3* (-2))/(-8) = (-8+6)/(-8)=

Третья таблица:

Третья таблица:
В последней таблице в столбце свободных членов нет отрицательных элементов,

Оформление результата решения

Результат решения определяют из последней таблицы следующим образом:
переменная,

Проверка:

3*2+2=8, 8=8, различия левой и правой частей нет, значит Y1=0, и

Решение задач линейного программирования в Excel

В настоящее время наиболее мощным средством

Установка Поиска решения

Установка Поиска решения

Установка Поиска решения

Окно Поиска решения