Оптимизационные модели. Элементы линейного программирования. (Лекция 3. Тема 2)

1. Лекция 3 Тема2. Оптимизационные модели. Элементы линейного программирования (продолжение)

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

2. 2.4. Двойственная задача и ее решение. Целочисленное программирование

3.

Каждой задаче ЛП можно определенным образом
поставить в соответствие некоторую другую задачу ЛП,
называемую сопряженной или двойственной по
отношению к исходной (прямой).
Двойственная задача по отношению к общей задаче ЛП,
состоящей в нахождении максимального значения функции
при ограничениях «с недостатком»

4.

Свойства двойственных задач ЛП:
1) в одной задаче ищут максимум целевой функции, в другой
минимум;
2) обе задачи являются стандартными задачами линейного
программирования, причем в задаче о максимуме все
неравенства вида «≤», а в задаче о минимуме вида «≥»;
3) матрица системы ограничений одной задачи является
транспонированной к матрице системы ограничений другой;
4) коэффициенты при переменных целевой функции одной
задачи являются свободными членами ограничений другой;
5) число неравенств в системе ограничений одной задачи
совпадает с числом переменных в другой задаче;
6) условия неотрицательности имеются в обеих задачах.

5.

Значительная часть задач по смыслу может иметь решения
только в целых числах; например, число турбин, судов,
животных может быть только целым числом.
Такие задачи решаются методами целочисленного
программирования.
Общая постановка задачи линейного программирования
дополняется требованием о том, чтобы найденные переменные
в оптимальном плане были целыми.

6. 2.5. Симплекс-метод решения задач ЛП

7.

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

8.

Симплекс – это выпуклый многоугольник в n-мерном
пространстве с n+1 вершинами, не лежащими в одной
гиперплоскости (гиперплоскость делит пространство на два
полупространства).
Симплексный метод – это вычислительная процедура,
основанная на принципе последовательного улучшения
решений при переходе от одной базисной точки (базисного
решения) к другой. При этом значение целевой функции
улучшается.
Базисным решением является одно из допустимых
решений, находящихся в вершинах области допустимых
значений. Проверяя на оптимальность вершину за вершиной
симплекса, приходят к искомому оптимуму. На этом принципе
основан симплекс-метод.

9. 2.5.1. Стандартная форма задач линейного программирования

Переход от геометрического способа решения задачи ЛП к
симплекс-методу лежит через алгебраическое описание
крайних точек пространства решений. Для реализации
этого перехода сначала надо привести задачу ЛП к
стандартной форме, преобразовав неравенства
ограничений в равенства путем введения дополнительных
переменных.
2.5.1. Стандартная форма задач
линейного программирования

10.

11. Требования к ограничениям:

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

12.

Преобразование неравенств в равенства
Неравенства любого типа (со знаками неравенств « » или
« ») можно преобразовать в равенства путем добавления в
левую часть неравенств дополнительных (балансных)
переменных – остаточных или избыточных, которые связаны
с неравенствами типа « » или « »соответственно.
Для неравенств типа « » в левую часть неравенства вводится
неотрицательная переменная
Модель компании Mikks
6 х1 4 х2 24
6 х1 4 х2 s1 24, s 0
Для неравенств типа « » в левую часть неравенства вводится
неположительная переменная
Модели «диеты»
х1 х2 800
х1 х2 S1 800, S1 0

13.

Пример 2.4. Преобразовать следующую задачу ЛП в
стандартную форму:
при выполнении следующих условий:

14.

Действия:

15.

Получаем:
при выполнении следующих условий:

16. 2.5.2. Основы симплекс-метода

17.

Рассмотрим общую ЗЛП с m ограничениями и n
переменными, записанную в стандартной (канонической)
форме:
(2.1)

18.

Как правило, число уравнений задачи меньше числа
переменных (т. е. m<n), поэтому множество ее допустимых
решений равно .
Задача состоит в том, чтобы найти наилучшее решение в
смысле принятого критерия (минимума целевой функции).
Оптимальное решение представляет собой одну из вершин
многогранника допустимой области. Другими словами,
оптимальное решение - это одно из базисных решений.

19. Получение одного из базисных решений основано на методе решения систем линейных уравнений Гаусса–Жордана.

Основная идея: сведение системы m уравнений с n неизвестными
к ступенчатому виду при помощи элементарных операций над
строками:
1) умножение любого уравнения системы на
положительное или отрицательное число;
2) прибавление к любому уравнению другого уравнения
системы, умноженного на положительное или
отрицательное число.

20.

При использовании первых m переменных такая система
имеет следующий вид:
(2.2)
Переменные x1 ,..., xm , , входящие с единичными
коэффициентами в одно уравнение системы (2.2) и с нулевыми
в остальные, являются базисными. В канонической системе
каждому уравнению соответствует ровно одна базисная
переменная.
Остальные (n–m) переменные ( xm 1,..., xn )
небазисными переменными
называются

21.

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

22.

Базисное решение называется допустимым базисным
решением, если значения входящих в него базисных
переменных
x j 0, j 1, m,
что эквивалентно условию:
b0j 0, j 1, m
Так как различные базисные решения системы (2.2)
соответствуют различным вариантам выбора (m) из общего
числа (n) переменных хj, то число допустимых базисных
решений (угловых точек) не превышает

23.

Поэтому ЗЛП можно решать посредством перебора
конечного числа угловых точек допустимого множества S ,
сравнивая значения целевых функций в этих точках.
Наихудший вариант решения ЗЛП, так как требует огромного
объема вычислений.
Пример: если n=50, m=25 (задача небольшой
размерности), то количество переборов составит
1,26 1014 (количество вариантов).
Обычно
n 1500 2000; m 1000 1500.

24.

Идея симплекс-метода (СМ) состоит в направленном переборе
угловых точек допустимого множества S с последовательным
уменьшением целевой функции f(x).
СМ разработал
американский ученый
Дж. Данциг в 1947 г.
Этот метод называют также
методом последовательного
улучшения решения (плана).
Джордж Бернард Данциг
(1914-2005)

25.

Гарантии результативности СМ обеспечиваются
следующей теоремой.
Теорема (о конечности алгоритма симплекс-метода).
Если существует оптимальное решение ЗЛП, то
существует и базисное оптимальное решение.
Это решение может быть получено через конечное число
шагов симплекс-методом, причем начать можно с любого
исходного базиса.

26. 2.5.3. Вычислительный алгоритм симплекс-метода

27.

Рассмотрим работу алгоритма на примере компании
Mikks.
Математическая модель:

28.

Математическая модель:
В стандартной форме:

29.

Замечание. Если целевую функцию необходимо
максимизировать, то предварительно нужно умножить
ее на (–1)
В стандартной форме:
f 5 x1 4 x2 min

30.

f 5 x1 4 x2 min
Ручные вычисления по симплекс-методу удобно оформлять в виде
так называемых симплекс-таблиц (СТ):

31.

Алгоритм СМ (применительно к данным таблицы 2.5)
Шаг 1. Выяснить, имеются ли в последней строке таблицы
отрицательные числа (значение в последнем столбце не
принимается во внимание). Если все числа
неотрицательны, то процесс закончен; базисное решение
(0, 0, 24, 6, 1, 2) является оптимальным; Если в последней
строке имеются отрицательные числа, перейти к Шагу 2.

32.

Алгоритм СМ (применительно к данным таблицы 2.5)
Шаг 2. Просмотреть столбец, соответствующий
наименьшему отрицательному числу, и выяснить, имеются
ли в нем положительные числа. Если ни в одном из таких
столбцов нет положительных чисел, то оптимального
решения не существует.
Если найден столбец, содержащий хотя бы один
положительный элемент, отметить его и перейти к Шагу 3.

33.

Алгоритм СМ (применительно к данным таблицы 2.5)

34.

x1
x2
1/6
4/6
4
-1/6
1/6
0
5/6
Алгоритм СМ (применительно к данным таблицы 2.5)

35.

x1
x2
1/6
4/6
4
-1/6
1/6
0
5/6
Алгоритм СМ (применительно к данным таблицы 2.5)
2-1·4/6=1,33
6-1·4=2
1+1·4/6=1,67

36.

Алгоритм СМ (применительно к данным таблицы 2.5)

37.

38.

39.

1.
2.
3.
4.
5.
6.
7.
8.
9.
Контрольные вопросы:
Дайте определение двойственной задачи по отношению к
общей задаче линейного программирования.
Сформулируйте свойства двойственных задач линейного
программирования.
Какие задачи решаются методами целочисленного
программирования?
Как в канонической (стандартной) форме задается задача
линейного программирования?
Какие требования предъявляются к стандартной форме
записи задачи линейного программирования?
Перечислите действия необходимые для преобразования
задачи линейного программирования в стандартную форму.
В чем состоит основная идея симплекс-метода? Какое
решение называется базисным? Как следует поступить, если
целевую функцию необходимо максимизировать?
Сформулируйте теорему о конечности симплекс-метода.
Опишите алгоритм симплекс-метода.