Математическое программирование в технических и информационных системах (Лекция 5)

1.

Дисциплина «Теория систем и системный анализ»
Кафедра инфокоммуникаций
Л.5. Математическое
программирование в
технических и информационных
системах

2.

СОДЕРЖАНИЕ
1. Ключевые понятия
2. Учебный материал
3. Вопросы для самопроверки
4. Рекомендуемая литература
2

3.

КЛЮЧЕВЫЕ ПОНЯТИЯ
Линейное программирование
Нелинейное программирование
Симплекс-метод
Динамическое программирование
Принцип Беллмана
Принцип Парето
Правило Борда
3

4.

УЧЕБНЫЙ МАТЕРИАЛ
Основные задачи лекции
Раскрыть основные понятия линейного
программирования. Описать типовые задачи.
Раскрыть основные понятия динамического
программирования.
Описать принцип Парето.
4

5.

УЧЕБНЫЙ МАТЕРИАЛ
Линейное программирование (ЛП)
Для решения задач линейного
программирования разработано сложное
программное обеспечение, дающее
возможность эффективно и надежно решать
практические задачи больших объемов.
5
Эти программы и системы снабжены развитыми
системами подготовки исходных данных,
средствами их анализа и представления
полученных результатов.

6.

УЧЕБНЫЙ МАТЕРИАЛ
Процесс построения математической модели в линейном
программировании можно представить как ответы на
следующие три вопроса:
1. Для определения каких величин должна быть построена
модель?
2. Какие ограничения должны быть наложены на переменные,
чтобы выполнить условия, отраженные в содержательной
постановке задачи?
3. В чем состоит цель, для достижения которой из всех
допустимых значений переменных нужно выбрать те,
которые будут соответствовать оптимальному
(наилучшему) решению задачи?
6

7.

УЧЕБНЫЙ МАТЕРИАЛ
В зависимости от конкретной ситуации, описываемой
моделью, целевая функция и система ограничений
включает разнообразные по составу и количеству
выражения.
Любая произвольная задача ЛП может быть сведена к
одной из двух общепринятых форм записи модели ЛП
Стандартная
Каноническая
7

8.

УЧЕБНЫЙ МАТЕРИАЛ
Стандартная задача ЛП
Стандартной задачей называется следующая форма записи задачи
ЛП:
Среди всех неотрицательных решений, удовлетворяющих системе
линейных неравенств, выбрать такое, при котором линейная форма
принимает минимальное значение:
F = c0 + c1 x1 + c2 x2 + L + cn xn min
a11 x1 + a12 x2 + a13 x3 + L + a1n xn b1
a21 x1 + a22 x2 + a23 x3 + L + a2 n xn b2
.........
..............
......... .....
.......
am1 x1 + am 2 x2 + am3 x3 + L + amn xn bm
8

9.

УЧЕБНЫЙ МАТЕРИАЛ
Каноническая задача ЛП
Канонической задачей называется следующая форма записи
задачи ЛП:
Среди всех неотрицательных решений системы уравнений
выбрать такое, при котором линейная форма принимает
минимальное значение:
P = p0 + p1x1 + p2 x2 +L+ pt xt min
b11x1 + b12x2 + b13x3 +L + b1t xt = d1
b
21x1 + a22x2 + b23x3 +L + b2t xt = d2
....... ......... .............. ......... .....
b 1x1 + b 2 x2 + b 3x3 +L + b x = d
s
s
s
st t
s
9

10.

УЧЕБНЫЙ МАТЕРИАЛ
Решение задач графическим методом
1-й этап. Перейти к стандартной форме записи модели.
если число переменных в системе ограничений равно двум,
то такая задача ЛП может быть решена графически.
2-й этап. производится графическое построение области
допустимых решений ( ОДР ) системы ограничений задачи.
3-й этап. Дается геометрическая интерпретация целевой
функции и определяется оптимальное решение задачи.
10

11.

УЧЕБНЫЙ МАТЕРИАЛ
Симплекс-метод:
Решение задачи, если оно существует, лежит в одной из вершин
ОДР. Следовательно оно может быть найдено полным перебором
вершин ОДР. Решение, расположенное в вершине ОДР,
называется опорным.
В опорных вершинах k=n-m переменных равны нулю (n - чиcло
переменных задачи, m - число уравнений, k - число свободных
переменных).
Смежные опорные вершины отличаются только одной переменной
в каждой группе (нулевых и ненулевых переменных).
Следовательно, чтобы осуществить переход от одной вершины к
другой, необходимо произвести замену переменных.
11

12.

УЧЕБНЫЙ МАТЕРИАЛ
Транспортная задача (ТЗ) – одна из самых
распространенных задач ЛП.
Цель- разработка наиболее рациональных путей и
способов транспортирования товаров, устранение
чрезмерно дальних, повторных, встречных перевозок.
cij – стоимость перевозки единицы
продукта из i-го склада в j-й пункт
назначения
xij – количество продукта, которое
перевозится из i-го склада в j-й
пункт потребления
ai – количество единиц продукта на iскладе
bj – количество единиц продукции,
которое необходимо доставить на jсклад
12

13.

УЧЕБНЫЙ МАТЕРИАЛ
Свойства транспортной задачи:
Теорема 1. Для любой транспортной задачи существует
план (то есть для любой транспортной задачи допустимая
область не пуста).
Теорема 2. Транспортная задача всегда имеет оптимальный
план.
Теорема 3. Любой опорный план имеет не более n+m-1
положительных компонент.
13

14.

УЧЕБНЫЙ МАТЕРИАЛ
Методы определения первоначального опорного плана
1. Метод северо-западного угла – опорный план строится по диагонали
от левого верхнего угла.
2. Метод минимального (максимального) элемента - из всей таблицы
стоимостей выбирают наименьшую и уже от нее строят опорный план.
3. Метод аппроксимации Фогеля - находят разность по всем столбцам и
по всем строкам между двумя записанными в них минимальными
тарифами, среди указанных разностей выбирают минимальную. В
строке (или в столбце), которой данная разность соответствует,
определяют минимальная стоимость.
4. Метод двойного предпочтения - эффективен в случае больших
размерностей. В каждом столбце отмечают знаком клетку с наименьшей
стоимостью. Затем тоже проделывают в каждой строке. В результате
некоторые клетки имеют двойную отметку. В них находится
минимальная стоимость как по столбцу, так и по строке.
14

15.

УЧЕБНЫЙ МАТЕРИАЛ
Динамическое программирование (ДП)
особый метод, приспособленный для
оптимизации динамических задач, в которых
операция состоит из элементов, сильно
влияющих друг на друга.
ДП связано с именем Ричарда Беллмана,
сформулировавшего принцип, позволяющий
существенно сократить перебор решений в
многоэтапных нелинейных задачах.
15

16.

УЧЕБНЫЙ МАТЕРИАЛ
Принцип оптимальности Беллмана ставит
вопрос о том, что такое оптимальность
отдельного элемента системы с точки зрения
оптимальности всей системы.
Принимая решение на отдельном этапе, мы
должны выбирать управление на этом этапе с
прицелом на будущее, т. к. нас интересует
результат в целом за все шаги.
16

17.

УЧЕБНЫЙ МАТЕРИАЛ
Беллман предложил рассматривать величину
выигрыша от i-го шага и до конца, если i-ый шаг
начинается с некоторого состояния S.
Такую величину называют
условным оптимальным выигрышем Wi(S)
Тогда, принимая решение на i-ом шаге, мы
должны выбрать Xi так, чтобы условный
оптимальный выигрыш был максимальным от
i-го шага и до конца.
17

18.

УЧЕБНЫЙ МАТЕРИАЛ
Оптимальность в малом понимается через
оптимальность в большом
Любой процесс имеет где-то окончание, т. е. имеет
горизонт планирования. Тогда последний этап «не имеет
будущего». Вот именно его можно оптимизировать
только из условий данного этапа. После этого
приступают к оптимизации (m-1) - го этапа.
Выбирают такое Xm-1 чтобы при применении этого Xm-1 его
внести в управление последнего шага.
18

19.

УЧЕБНЫЙ МАТЕРИАЛ
Оптимальность в малом понимается через
оптимальность в большом
При этом мы задаём состояние, с которого начинается
(m-1)-ый шаг.
Поэтому функцию Wi(S) называют условным оптимальным
выигрышем.
Таким образом, процесс оптимизации разворачивается от
конца к началу, и начальное состояние становится известно.
Принцип Беллмана нашёл применение в методе программноцелевого планирования (любое действие планируется
некоторым проектом).
19

20.

УЧЕБНЫЙ МАТЕРИАЛ
Функциональное уравнение Беллмана
Назовём состоянием системы вектор координат:
S = (x1 ,x 2 ,...,x L )
В некоторых задачах состояние – одна величина.
Тогда работу системы можно представить как
движение в фазовом пространстве – пространстве
состояний.
Шаговое управление – управление на i-ом шаге.
20

21.

УЧЕБНЫЙ МАТЕРИАЛ
Задача распределения ресурсов
Под ресурсом в общем случае понимают физическую или
абстрактную величину, которую система использует для
производства полезного продукта.
Например: горючее, деньги, время, объём склада.
Как правило – ресурс ограничен, поэтому встаёт задача
так распределить ресурс между отдельными
элементами системы, чтобы суммарный эффект был
максимальным.
21

22.

УЧЕБНЫЙ МАТЕРИАЛ
Принцип Парето
двадцать процентов населения владеют
восьмьюдесятью процентами капиталов
log N = log A + m log x,
где N - число людей, получающих доход выше уровня х,
А и m - константы.
Гораздо менее правило Парето известно в такой
формулировке:
«Существует неизменное математическое соотношение
между численностью группы людей и долей богатств или
дохода, контролируемой этой группой».
22

23.

УЧЕБНЫЙ МАТЕРИАЛ
Доминирование по Парето
Математическую модель можно записать следующим
образом
D, f1 , f 2 ,..., f m
Здесь D – множество допустимых исходов;
fj – числовая функция, заданная на множестве D по j
критерию:
fj – позитивное, если лицо, принимающее
решения стремится увеличить его значение
fj – негативное, если лицо, принимающее
решения стремится уменьшить его значения
23

24.

УЧЕБНЫЙ МАТЕРИАЛ
Два подхода выбора оптимального решения по
Парето:
Для задачи находят множество оптимальных по Парето
исходов и представляют право выбора оптимального
исхода лицу принимающему решение.
Производится сужение множества оптимальных по Парето
исходов за счет дополнительной информации о критериях.
Данный подход включает в себя три способа:
•указание нижних границ критерия;
•субоптимизация;
•лексиграфическая оптимизация
24

25.

УЧЕБНЫЙ МАТЕРИАЛ
Ранжирование элементов заказа на основе
принципа Парето
Сущность заключается в том, что производится
классификация всех номенклатурных позиций, данные
о запасах которых поддерживаются по признаку
относительной важности этих позиций, и для каждой
выделенной категории формируются свои методики
управления запасами
Обычно прибегают к трехступенчатому ранжированию
номенклатурных позиций на классы А, В и С.
25

26.

УЧЕБНЫЙ МАТЕРИАЛ
Ранжирование элементов заказа на основе
принципа Парето
группа А: наиболее ценные изделия, на долю которых
приходится около 80% общей стоимости товаров,
выпускаемых фирмой, и они составляют лишь 15—20% от
всего объема готовой продукции, поступившей на склад.
группа В: средние по стоимости изделия, примерно 10—
15% общей стоимости, но в количественном отношении они
составляют 30% всего объема выпуска.
группа С: самые дешевые (примерно 5—10% общей
стоимости) и самые массовые (более 50% всего
производства) изделия.
26

27.

УЧЕБНЫЙ МАТЕРИАЛ
Парето-эффективность
Критерий Парето-эффективности (Парето-улучшения, Паретопревосходства), позволяет ранжировать размещения, хотя неполнота
получаемого при этом упорядочения является серьезным ограничением
его ценности
Этот принцип обосновывает необходимость концентрации всегда
ограниченных ресурсов предприятия на ограниченном участке «фронта»
вместо их привычного распыления по множеству направлений. Он
помогает определить именно тот участок, где можно рассчитывать на
максимальный результат от своих усилий.
Для критерия Парето имеет значение только одно свойство размещения –
его влияние на индивидуума в обществе. Так выпуск или комбинации
факторов отдельной фирмы не существенны для целей благосостояния.
27

28.

УЧЕБНЫЙ МАТЕРИАЛ
Проблема группового выбора. Правило Борда
Правила выбора по Парето нередко дают больше
выигрышных значений, чем это необходимо. В таких случаях
применяется более строгое правило выбора - правило
выбора по Борда.
Для применения правила Борда берется таблица
ранжирования проектов Парето и вводится специальный
столбец, значения в котором соответствуют рангу строки.
Таким образом, проект, имеющий наилучшее значение по
какому-либо показателю, имеет по данному показателю
больший ранг, а наименьший ранг соответствует наихудшему
значению.
28

29.

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ
Раскройте суть линейного программирования.
Опишите процесс создания модели линейного
программирования.
Опишите задачи линейного программирования.
Раскройте идею симплекс-метода.
Опишите транспортную задачу.
Раскройте суть динамического программирования.
Опишите принцип оптимальности Беллмана.
Раскройте принцип Парето.
29

30.

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА
Четыркин Е.М. Финансовая математика: Учебник / Е.М.
Четыркин – М.: Дело, 2006
Колемаев В.А. Математическая экономика: Учебник для
вузов. – М.: ЮНИТИ-ДАНА, 2002
Данилов Н.Н. Курс математической экономики: Учебное
пособие. – М.: Высш. шк., 2006
Альсевич В.В. Введение в математическую экономику.
Конструктивная теория: Учебное пособие. – М.
Издательство ЛКИ, 2007
30