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

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

История возникновения
1885г. Фредерик Тейлор – вывод о возможности применения научного анализа в сфере производства.
1916г. Фредерик Ланчестр – «квадратичный закон», который устанавливает связь между численным превосходством живой силы и эффективностью оружия.
20-е гг. Формулы Эрланга были приняты в качестве стандартов для расчета эффективности телефонных линий.

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

Оптимальное математическое программирование
ЦЕЛЬ (критерий, целевая функция)
F(x1;x2;…;xn) → экстремум
ОГРАНИЧЕНИЯ (условия, требования)
Gj(x1;x2;…;xn) [>;≥;=;<;≤] bj где j = 1,2,…,m
ТРЕБОВАНИЯ К ПЕРЕМЕННЫМ
xi≥0 не отрицательность
xi – целые,
xi – выражены через параметры,
xi – случайные и т.д.

Полное решение поставленной задачи не найдено, но получены существенные результаты во множестве частных случаев
Если функции F и Gj линейные, то в этом случае задача носит название задачи линейного программирования.
Если F дробно-линейная, а Gj – линейные, то это задача дробно-линейного программирования.
Если F квадратичная функция, а Gj линейные, то это задача квадратичного программирования.
Если xi – целые, то это задача целочисленного программирования.
Если xi – выражены через параметры, то это задача параметрического программирования.
Если хотя бы одна из xi - случайная величина, то это задача стохастического программирования.
Если результат многоэтапного решения зависит от оптимального выбора на каждом этапе, то это задача динамического программирования.

История линейного программирования
КАНТОРОВИЧ Леонид Витальевич
(1912-86),
российский математик и экономист,
академик АН СССР.
Положил начало линейному программированию. Один из создателей теории оптимального планирования и управления народным хозяйством, теории оптимального использования сырьевых ресурсов.

Задача линейного программирования имеет следующий вид
1) Целевая функция
Z= → экстремум (оптимум)
2) Ограничения [>≥=<≤] bj , где
j=1,2,…,m
3) Требования к переменным xi≥0
(не отрицательность).

СПОСОБЫ РЕШЕНИЯ ЛИНЕЙНЫХ ЗАДАЧ
Графический способ
Средствами Excel (Поиск решения)
Средствами MathCAD (функция Minimize)
Способ Жордановых исключений

Пример:

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

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

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

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

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

СПОСОБ ЖОРДАНОВЫХ ИСКЛЮЧЕНИЙ (СИМПЛЕКСНЫЙ)
Симплексный метод требует преобразования
имеющейся модели к каноническому виду.
каждое неравенство должно быть приведено к виду ≥0,
уравнение – приравнено к 0.
целевая функция должна стремиться к минимуму.

Последовательное преобразование Жордановой таблицы
Задача считается решенной, если коэффициенты при переменных в целевой строке не отрицательны, и при этом все свободные члены дополнительных переменных также не отрицательны.
Все преобразования таблиц основаны на так называемых разрешающих элементах.

Правила выбора
разрешающего элемента
Разрешающий элемент не может находиться в столбце свободных членов и в строке целевой функции. Он не может быть равным нулю.
Любой отрицательный элемент в столбце свободных членов определяет возможную разрешающую строку.
Наименьшее отношение соответствующего свободного элемента ко всем положительным элементам этой же строки определит разрешающий элемент. Следует учесть все такие строки, если их несколько.
3. Любой отрицательный элемент целевой строки определяет возможный разрешающий столбец. Наибольшее из всех возможных отношений соответствующих свободных членов к отрицательным элементам такого столбца и определит разрешающий элемент.
После выбора разрешающего элемента ячейки Жордановой таблицы пересчитывают также по определенным правилам и переходят к следующей таблице.

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

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

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

Предыдущая таблица Последующая таблица
На место R ставим обратную величину

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

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

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

Основная форма представления задачи линейного программирования
Исходная форма Каноническая форма
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=-2x1+3x2-28
x1-x2≤4 y4=-x1- x2 - 4
x1+3x2≥8 y5= x1+3x2-8

Основная форма представления задачи линейного программирования
Исходная форма Каноническая форма
Z=x1+x2→min Z=x1+x2→min
3x1+x2≥8 y13x1 + x2- 8 ≥0
x1-4x2≤19 y2=-x1- 4x2 -19 ≤0
2x1+3x2≤28 y3-2x1+3x2-28 ≤0
x1-x2≤4 y4=-x1 - x2 - 4 ≤0
x1+3x2≥8 y5= x1+3x2 - 8 ≥0

Исходная форма Каноническая форма
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 y3=-2x1-3x2+28 ≥0
x1-x2≤4 y4= -x1+x2+4 ≥0
x1+3x2≥8 y5= x1+3x2-8 ≥0
Основная форма представления задачи линейного программирования

Исходная форма Каноническая форма
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= ─ 2x1 ─ 3x2+28
x1-x2≤4 y4= ─ x1+x2+4
x1+3x2≥8 y5= x1+3x2 ─ 8
Основная форма представления задачи линейного программирования

Все коэффициенты канонической формы заносят в Жорданову таблицу
В заголовках столбцов этой таблицы ставят имена определяемых переменных: х1 , х2,
а также заголовок столбца свободных членов всех ограничений или, его еще называют столбцом единиц.
В заголовках строк таблицы записывают имена введенных, дополнительных переменных: y1, y2,y3, y4, y5 и имя целевой функции Z.
При заполнении таблицы обязательно учитывать знаки каждого коэффициента.

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

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

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

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

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

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

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

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

Рассмотрим первую таблицу нашей задачи
Находим разрешающий элемент: -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 )

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

Третья таблица:
В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение.
Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное.
Заметив этот факт, мы не стали заполнять все остальные клетки таблицы, т.к. ответ уже получен.

Третья таблица:
В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение.
Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное.
Заметив этот факт, мы не стали заполнять все остальные клетки таблицы, т.к. ответ уже получен.
-2 / (-8) = 2/8
столбец делим на разрешающий элемент

Третья таблица:
( 1* (-8) - 3* (-2))/(-8) = (-8+6)/(-8)= - 2/( - 8) = 2/8

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

Третья таблица:
В последней таблице в столбце свободных членов нет отрицательных элементов, поэтому она демонстрирует так называемое «допустимое» решение.
Кроме того, в последней таблице в строке целевой функции также нет отрицательных элементов, значит, имеющееся решение есть не только допустимое, но и оптимальное.

Оформление результата решения
Результат решения определяют из последней таблицы следующим образом:
переменная, стоящая в заголовке строки равна свободному члену этой строки,
переменная в заголовке столбца принимается равной нулю.
Таким образом, по нашей задаче решением будет следующий результат:
X1=2, X2=2,
Y1=0, Y2=25, Y3=18, Y4=4, Y5=0, Zmin=4.

Проверка:
3*2+2=8, 8=8, различия левой и правой частей нет, значит Y1=0, и в последней таблице Y1 стоит в заголовке столбца.
2-4*2=-6<19, Y2=25, но то же самое и по последней таблице.
2*2+3*2=10<28 на 18, следовательно, Y3=18, так же и в таблице.
2-2=0<4 на 4, Y4=4, что подтверждается таблицей.
2+3*2=8, 8=8, Y5=0.
Наконец, z=2+2=4, но и по таблице тот же результат.
Таким образом, полученное решение удовлетворяет всем ограничениям задачи и
обеспечивает минимум целевой функции равный 4.

Решение задач линейного программирования в Excel
В настоящее время наиболее мощным средством решения таких задач на компьютере является пакет Excel с его надстройкой «Поиск решения».
Для решения задачи в Excel необходимо правильно поместить математическую модель по ячейкам электронной таблицы при этом целесообразно придерживаться примерно следующей схемы заполнения ячеек

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

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

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

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