Симплекс-метод для решения задач линейного программирования презентация

ЛП Графический метод решения
2.Cимплекс-метод (СМ)
Теоретические основы Геометрическая интерпретация Алгоритм СМ
3.Применение
СМ в различных типах задач ЛП
Реализация программы для решения симплекс-методом

метод решения

Что такое линейное программирование

Линейное программирование — математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

Создатели линейного программирования Леонид Витальевич Канторович (1912-1986) Джордж Бернард Данциг (1914-2005)

метод решения

Три основных элемента задачи ЛП

Переменные
x¯ = (x1, . . . , xn)
Система линейных ограничений
.n

j=1 aijxj ≤ bi (i = 1 . . . m)
Целевая функция, которая подлежит оптимизации

j=1

f (x¯) = .n ci xj

Переменные в общем случае являются вещественными числами.
В системе ограничений может также присутствовать знак ” =”. Под оптимизацией понимается максимизация или минимизация целевой функции.

Симплекс-метод

4 / 28

метод решения

Основные теоремы ЛП

Теорема 1. Конечное оптимальное решение задачи ЛП должно соответствовать экстремальной (крайней) точке пространства решений.

Теорема 2. Базисные решения системы полностью определяют все её экстремальные точки.

Базис — m независимых векторов из числа n.

Экстремальные точки могут быть найдены путем вычисления допустимых базисных решений системы:
n!
m!(m−n)!

Симплекс-метод

5 / 28

метод решения

Общая линейная распределительная задача

Далее рассмотрим построение математической модели на примере следующей задачи.

Пусть имеется 3 вида сырья в количестве 45, 19, 10 единиц соответственно. Нужно изготовить продукцию 2-х видов с затратами 1, 3, 2 единиц сырья для продукции первого вида и 9, 3, 1 – для продукции второго вида соответственно. Прибыль от реализации продукции составляет 5 денежных единиц для продукции 1-го вида и 6 — для второго. Требуется найти такой план выпуска продукции из имеющегося сырья, при котором суммарная прибыль будет наибольшей.

Симплекс-метод

6 / 28

метод решения

Общая линейная распределительная задача
Запишем данные задачи в таблицу.

5x1 + 9x2 ≤ 45

3x1 + 3x2 ≤ 19
2x1 + 1x2 ≤ 10 при x1, x2 ≥ 0

f (˙x ) = 5x1 + 6x2 → max

Симплекс-метод

7 / 28

метод решения

Графическое решение

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

называется канонической, если: cистема содержит только уравнения
cвободный член в правой части не отрицателен
каждое уравнение содержит своё базисное неизвестное (входит в уравнение с коэффициентом +1, а в других уравнениях отсутствует)

систему к каноническому виду.

5x1 + 9x2 ≤ 45

3x1 + 3x2 ≤ 19
2x1 + 1x2 ≤ 10 при x1, x2 ≥ 0

f (˙x ) = 5x1 + 6x2 → max

является канонической.

5x1 + 9x2 + x3 = 45

3x1 + 3x2 + x4 = 19
2x1 + 1x2 + x5 = 10
при x1, x2, x3, x4, x5 ≥ 0

f (˙x ) = 5x1 + 6x2 + 0 ∗ (x3 + x4 + x5) → max

Мамошкин А. М. (СПбГУ ИТМО КТ)

Симплекс-метод

http://rain.ifmo.ru/cat

11 / 28

распределительной задачи выполняется в два этапа:

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

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

целевой функции через небазисные
переменные: f (x ) = 5x1 + 6x2. Записать целевую функцию в форме Таккера: f (x ) = 0 − (−5x1 − 6x2).
2.Проверка базисного решения на оптимальность. 3.Проверка на наличие решения.
4.Выбор из небазисных переменных той, которая способна при введении её в базис увеличить значение целевой функции
5.Определение, какая из базисных переменных должна быть выведена из базиса.

вводимой в базис переменной через выводимую и другие небазисные переменные.
7.Выражение остальных базисных переменных и целевой функции через новые небазисные переменные.
8.Повторение операций пунктов (2) - (7) до тех пор пока не будет найдено оптимальное решение.

Мамошкин А. М. (СПбГУ ИТМО КТ)

Симплекс-метод

http://rain.ifmo.ru/cat

15 / 28

построена. Найдём ключевой столбец по минимальному отрицательному значению в ключевой строке. Столбец выбирается таким, чтобы переменная, ему соответствующая, не лежала в базисе.

столбце необходимо найти ключевой элемент. Для этого нужно найти минимум отношения базисного плана к элементу из ключевого столбца той же строки.
В данном примере это соотношение равно 45/9.

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

коэффициенты рассчитываются по преобразованию Гаусса-Жордана или правилу двух перпендикуляров (ar = a − b ∗ c, где b и c - соответствующие элементы ключевого столбца и новой ключевой строки).

построено. Значение функции увеличилось. Теперь нужно проверить условие оптимальности: отсутствие в целевой строке отрицательных элементов среди базисных неизвестных. Здесь присутствует число -5/3. Переходим к следующей таблице.

выполнено. Теперь известен ответ.

˙x ∗ = (3, 3 1 )

3
f (˙x ∗) = 35

зависит от: числа итераций
машинного времени
В результате численных экспериментов получены результаты.
Число итераций при решении задач ЛП в стандартной форме с M ограничениями и N переменными заключено между M и 3M . Среднее число итераций 2M . Верхняя граница числа итераций равна 2M + N .
Требуемое машинное время пропорционально M 3. Число ограничений больше влияет на вычислительную эффективность, чем число переменных, поэтому при формулировке задач ЛП нужно стремиться к уменьшению числа ограничений пусть даже путём роста числа переменных

1. Если x — некоторый план исходной задачи, а y — произвольный план двойственной задачи, то значение целевой функции исходной задачи при плане , не превосходит значение целевой функции двойственной задачи при плане y .

Лемма 2. Если f (x∗) = g (y∗) для некоторых планов x∗ и y∗ прямой и двойственной задач, то x∗ — это оптимальный план исходной задачи, а y∗ — это оптимальный план двойственной задачи.

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

в различных типах задач

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

источников

Хемди А. Таха. Введение в исследование операций. — 7-е изд. — М. : Вильямс, 2007.
Солодовников А.С., Бабайцев В.А., Браилов А.В. Математика в экономике. — М. : Финансы и статистика, 1998.
Хачатрян С.Р., Пинегина М.В., Буянов В.П. Методы и модели решения экономических задач. — М. : Экзамен, 2005.