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

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

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

2. Содержание

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

3.

Формулировка задачи
Симплекс-метод
Применение
О линейном программировании
Математическая формулировка задачи Л П
Графический метод решения
Что такое линейное программирование
Линейное программирование —математическая
дисциплина, посвящённая теории и методам решения
экстремальных задач на множествах n-мерного векторного
пространства, задаваемых системами линейных уравнений и
неравенств.
Создатели линейного программирования
Леонид Витальевич Канторович (1912-1986)
Джордж Бернард Данциг (1914-2005)

4.

Формулировка задачи
Симплекс-метод
Применение
О линейном программировании
Математическая формулировка задачи Л П
Графический метод решения
Три основных элемента задачи ЛП
Переменные
x¯= (x1, . . . , xn)
Система линейных ограничений
.n
j=1 a ij x j ≤ b i (i = 1 . . . m)
Целевая функция, которая подлежит оптимизации
.
f (x
¯) = nj =1 ci xj
Переменные в общем случае являются вещественными
числами.
В системе ограничений может также присутствовать знак ” =”.
Под оптимизацией понимается максимизация или минимизация
целевой функции.
Симплекс-метод
4 / 28

5.

Формулировка задачи
Симплекс-метод
Применение
О линейном программировании
Математическая формулировка задачи Л П
Графический метод решения
Основные теоремы ЛП
Теорема 1. Конечное оптимальное решение задачи ЛП должно
соответствовать экстремальной (крайней) точке пространства
решений.
Теорема 2. Базисные решения системы полностью
определяют все её экстремальные точки.
Базис — m независимых векторов из числа n.
Экстремальные точки могут быть найдены путем вычисления
допустимых базисных решений системы:
n!
m!(m−n)!
Симплекс-метод
5 / 28

6.

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

7.

Формулировка задачи
Симплекс-метод
Применение
О линейном программировании
Математическая формулировка задачи Л П
Графический метод решения
Общая линейная распределительная задача
Запишем данные задачи в таблицу.
Виды продукции
Виды сырья
I
II
1
5
9
2
3
3
3
2
1
Виды продукции
45
19
10
5x1 + 9x2 ≤45
3x1 + 3x2 ≤19
2x1 + 1x2 ≤ 10
при x1, x2 ≥ 0
f (˙x) = 5x1 + 6x2 →max
Симплекс-метод
7 / 28

8.

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

9.

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

10.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Дополнительные неизвестные
Необходимо привести систему к каноническому виду.
5x1 + 9x2 ≤45
3x1 + 3x2 ≤19
2x1 + 1x2 ≤ 10
при x1, x2 ≥ 0
f (˙x) = 5x1 + 6x2 →max

11.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Дополнительные неизвестные
Теперь система является канонической.
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
Мамошкин А . М . (СПбГУ И Т М О КТ)
Симплекс-метод
ht t p://rain. ifmo . r u /cat
11 / 28

12.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Основная идея
Решение общей распределительной задачи выполняется в два
этапа:
Находят любое решение (как правило, неоптимальное),
удовлетворяющее ограничениям, или убеждаются, что
решения не существует. Этот этап называется
определением опорного плана (базиса).
Производится последовательное улучшение данного плана до
получения оптимального. В некоторых задачах опорный план
определяется легко, в противном случае используют
специальные методы получения опорного плана (метод
искусственного базиса).

13.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Графическая интерпретация симплекс-метода
Выпуклая фигура, соответствующая области решений,
называется симплексом. Поиск оптимального решения
осуществляетсяс помощью переходов по её ребрам.

14.

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

15.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Описание алгоритма СМ
6.Выражение вводимой в базис переменной через
выводимую и другие небазисные переменные.
7.Выражение остальных базисных переменных и целевой
функции через новые небазисные переменные.
8.Повторение операций пунктов (2) - (7) до тех пор пока не
будет найдено оптимальное решение.
Мамошкин А . М . (СПбГУ И Т М О КТ)
Симплекс-метод
ht t p://rain. ifmo . r u /cat
15 / 28

16.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Табличный СМ
Первая таблица построена. Найдём ключевой столбец по
минимальному отрицательному значению в ключевой строке.
Столбец выбирается таким, чтобы переменная, ему
соответствующая, не лежала в базисе.

17.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Табличный СМ
В ключевом столбце необходимо найти ключевой элемент. Для этого
нужно найти минимум отношения базисного плана к элементу из
ключевого столбца той же строки.
В данном примере это соотношение равно 45/9.

18.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Табличный СМ
В базис вносится элемент из ключевого столбца. Ключевую стоку
необходимо поделить на ключевой элемент. Это нужно для того,
чтобы в следующим плане этот элемент являлся бы базисным, т. е.
входил только в одно уравнение с единичным коэффициентом.

19.

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

20.

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

21.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Табличный СМ
Условие оптимальности выполнено. Теперь известен ответ.
˙x∗ = (3, 3 13 )
f (˙x∗) = 35

22.

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

23.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Основные теоремы двойственности
Лемма 1. Если x —некоторый план исходной задачи, а y —
произвольный план двойственной задачи, то значение целевой
функции исходной задачи при плане , не превосходит значение
целевой функции двойственной задачи при плане y .
Лемма 2. Если f (x∗) = g (y∗) для некоторых планов x∗ и y∗
прямой и двойственной задач, то x∗ —это оптимальный план
исходной задачи, а y∗ —это оптимальный план двойственной
задачи.

24.

Формулировка задачи
Симплекс-метод
Применение
Теоретические основы
Графическая интерпретация
Алгоритм С М
Основные теоремы двойственности
Теорема двойственности.
Если одна из пары двойственных задач имеет оптимальный
план, то и другая имеет оптимальный план и значение целевой
функции задачи при их оптимальных планах равны между
собой.
Если же целевая функция одной из пары двойственных
задач не ограничена (для исходной задачи не ограничена
сверху, а для двойственной задачи не ограничена снизу), то
другая задача вообще не имеет планов.

25.

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

26.

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