пгш. 1 линейные модели пр. реш. Лекция Линейные модели принятия решений

• Название: Лекция Линейные модели принятия решений
• Дата: 01.07.2021
• Размер: 395.56 Kb.
• Имя файла: 1 линейные модели пр. реш.pdf
• Тип: Лекция; #222848

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

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

1. ЗАДАЧИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ДЛЯ
ПРИНЯТИЯ РЕШЕНИЙ
1.1. Классификация решений
1. По принципам выработки решения бывают:
- алгоритмические, осуществляемые по определенным правилам;
- эвристические, выполняемые творческим путем без строгих правил.
2. По методам обоснования:
- аналитические,
- статистические,
- математического программирования,
- игровые
3. По характеру исходной информации:
- в условиях определенности,
- в условиях неопределенности.
4. В практике принятия решения:
- допустимые,
- оптимальные.
5. По типу принимаемых решений человеком:
- дедуктивные,
- абдуктивные,
- индуктивные.
Дедуктивные решения входят в класс строгих зависимостей, отличаются полной определенностью. Это обычная функциональная зависимость.
)
(
i
i
x
R
y


Абдуктивные решения – сочетание строгих и эвристических решений.
Строятся на основе прошлого опыта. Например, между некоторым множеством посылок x
i
и следствий y
i существует причинно-следственная связь
)
(
);
(
,
1
i
i
i
i
i
i
y
R
x
x
R
y
Y
y
X
x





Например, определение температуры тела t по длине столбика ртути l и наоборот:
)
(
),
(
1
l
R
t
t
R
l



Индуктивные решения входят в класс эвристических решений, отличаются большой неопределенностью. Здесь, как правило, известны входные и выходные данные, но неизвестен оператор преобразования.
Например, опытный врач, имея на руках анализы больного, должен решить какую технологию применить для успешного лечения пациента. Директор предприятия также решает, как организовать производство для выпуска нового изделия.
Наибольший класс принимаемых решений относятся к математическим методам. Существуют следующие математические методы.
Из математических моделей различают:
1) расчётная модель – прямая задача
y=f(x
1
,x
2
,…,x
n
);
2) оптимизационная модель – обратная задача: однокритериаль ные непрерывны е смешанны е линейные дискретны е нелинейн ые
Математические методы многокритериаль ные

найти x
1
, x
2
, . . .,x
n
, при которых
extr
X
x
y


В процессе принятия решений действуют контролируемые и неконтролируемые факторы (КФ, НФ).
Общая математическая модель формирования оптимальных решений записывается в виде
(1) z=f(c,x)

extr,
(2)
b
x
a

)
,
(

,
(3)
0

x
,
где c,a,b – неконтролируемые факторы.
Задача формулируется следующим образом: Найти значение вектора
Х=(x
1
,x
2
,…,x
n
)
доставляющее максимум (минимум) значению критерия оптимальных решений (1) и удовлетворяющее при этом условиям (2) и (3).
Если лицо, принимающее решение, должно учитывать достижение k различных целей, то в рассмотрение вводятся k оптимальностей вида:
z
1
=f
1
(c
1
,x)

max,
z
2
=f
2
(c
2
,x)

min,
. . . . . . . . . . . . .
z
k
=f
k
(c
k
,x)

max,
где с
1
, c
2
, . . . ,c
k
– векторы неконтролируемых факторов. Такая математическая модель называется многокритериальной моделью принятия решений. При этом необходимо учитывать, что при рассмотрении многокритериальных задач, могут возникать противоречия. Например, ставиться задача: «Получить максимальную прибыль при минимуме затрат».
Спрашивается, какая может быть прибыль, если минимум затрат сводится к нулю.
1.2.
Линейные модели
Данный класс математических моделей является наиболее распространенным в задачах принятия решений. Связано с тем, что линейные модели, за счет их простоты, обычно выступают в качестве первого этапа

применения математических моделей. Кроме того, они являются наиболее разработанными разделами математического программирования. Задача линейного программирования (ЛП) формулируется следующим образом:
Найти значения вектора X=(x
1
,x
2
,…x
n
), доставляющие максимум целевой функции: max
1 1




n
n
x
c
x
c
L
при выполнении условий вида:
1 1
2 12 1
11
b
x
a
x
a
x
a
n
n




2 2
2 22 1
21
b
x
a
x
a
x
a
n
n




…
m
n
mn
m
m
b
x
a
x
a
x
a




2 2
1 1
0
,...,
,
2 1

n
x
x
x
Сокращенная запись:




n
j
j
j
x
c
L
1
max



n
j
i
j
ij
b
x
a
1
,
m
i
,
1

0

j
x
,
n
j
,
1

Таким образом, задача линейного программирования состоит в минимизации (максимизации) линейной функции




n
j
j
j
n
x
c
x
x
x
L
1 2
1
min
)
,...,
,
(
на множестве, заданном системой линейных ограничений (равенств или неравенств) на координаты x
j
l
i
b
x
a
n
j
i
j
ij
,...,
2
,
1
,
1




m
l
i
b
x
a
n
j
i
j
ij
,...,
1
,
1





0

j
x
,
n
j
,
1


Если в условиях задачи линейного программирования (ЗЛП) не содержатся ограничения неравенства, т.е. l=m, то она называется ЗЛП в каноническом виде. Если требуется найти минимум функции L, то можно перейти к максимуму функции L
1
=-L, так как функция L принимает минимальное значение в той же точке, в которой функция L
1
принимает максимальное значение.
Ограничения - неравенства вида “≤” можно преобразовать в ограничения – равенства добавлением к его левой части дополнительной неотрицательной переменной
,
0


i
n
x
а ограничения –неравенств вида ≥ – в ограничения равенства вычитанием из его левой части дополнительной неотрицательной переменной. Таким образом, ограничения – неравенства преобразуются в ограничения равенства. Тогда любая ЗЛП может быть записана в каноническом виде




n
j
j
j
n
x
c
x
x
x
L
1 2
1
min
)
,...,
,
(
m
i
b
x
a
n
j
i
j
ij
,...,
1
,
1




0

j
x
Приведем ряд примеров, позволяющих сформулировать постановку в виде задачи линейного программирования
Пример 1.1. Задача о пищевом рационе.
Имеется 4 вида продуктов питания:
4 3
2 1
,
,
,
P
P
P
P
. Известна стоимость продуктов питания: соответственно
4 3
2 1
,
,
,
C
C
C
C
. Из этих продуктов необходимо составить пищевой рацион, который должен содержать: белков не менее
1
b
, углеводов не менее
2
b
, жиров не менее
3
b

При этом продукт P
j
содержит a
ij
белков, жиров и углеводов,
__
__
4
,
1
;
3
,
1


j
i
Все указанные данные сведены в таблице 1.1 «Продукты».
Таблица 1.1 1
P
2
P
3
P
4
P
i
b
белки
11
a
12
a
13
a
14
a
1
b
жиры
21
a
22
a
23
a
24
a
2
b
углеводы
31
a
32
a
33
a
34
a
3
b
Стоимость
1
C
2
C
3
C
4
C
Необходимо составить рацион, минимальный по стоимости, но содержащий достаточное количество белков, жиров и углеводов, при следующих ограничениях:




n
j
j
j
x
C
L
1
max


i
j
ij
b
x
a
,
3
,
1

i
0

j
x
,
4
,
1

j
4 3
2 1
,
,
,
x
x
x
x
- количество продуктов, включенных в пищевой рацион.
Пример 1.2.Формирование оптимальной производственной программы.
Производится выпуск двух видов продукции:
2 1
, P
P
. Для их производства используется три вида сырья:
3 2
1
,
,
S
S
S
. Исходные данные представлены в таблице 1.2. Необходимо наладить выпуск продукции таким образом, чтобы получить максимальную прибыль.

Таблица 1.2
Продукция
i
b
1
P
2
P
Сыр ье
1
S
11
a
12
a
1
b
2
S
21
a
22
a
2
b
3
S
31
a
32
a
3
b
Стоимость
1
C
2
C
ij
a
- нормативный запас каждого вида сырья. max
2 2
1 1



x
C
x
C
L
1 2
12 1
11
b
x
a
x
a


2 2
22 1
21
b
x
a
x
a


3 2
32 1
31
b
x
a
x
a


0
,
2 1

x
x
Иногда в качестве основного критерия выступают сроки выпуска продукции, тогда целевая функция будет учитывать временные параметры.
Выпуск продукции за минимальное время составит: min,
2 2
1 1



x
t
x
t
T
где t
j
- трудоемкость выпуска продукции.
Геометрическая интерпретация задач
линейного программирования.
Линейная функция в случае двух переменных
)
,
(
1
n
x
x
X

может быть представлена графически (рис.1.1).
1 2
12 1
11
b
x
a
x
a


2 2
22 1
21
b
x
a
x
a


…

m
m
m
b
x
a
x
a


2 2
1 1
max
2 2
1 1



x
C
x
C
L
Рис.1.1.
Область допустимых решений (ОДР) должен быть выпуклым многоугольником. Оптимальные значения находятся в углах многоугольника.
2 2
2 1
max
C
C
L
d


- определяет расстояние от начала координат до прямой
L, проходящей через точку оптимума.
2 2
2 1
1
cos
C
C
C



- определяет наклон прямой L.
Если необходимо найти минимальное значение, тогда L=-L.
Пример 1.3. Используя графический метод (рис.1.2), найти решение
ЗЛП. min
2 3
)
,
(
2 1
2 1




x
x
x
x
L
)
3
(
3
)
2
(
8 2
)
1
(
7 2
2 2
1 2
1





x
x
x
x
x

Решение.
Построим на графике линии, в соответствии с неравенствами 1,2,3.
Получим область допустимых решений. Затем построим линию L, обозначив
L
1
=-L. Присвоим условно сначала L=6, затем 12. Видим, что оптимальное значение будет находиться в точке С.
Найдем координаты этой точки x
1
=3, x
2
=2. Подставим в уравнение L, получим L=13. Минимальное значение будет равно: L=-L=-13 2
1 2
1 2
3 12 2
3 6
x
x
x
x




Рис.1.2. Графический способ решения
Контрольные вопросы
1.
Теория принятия решений представляет собой?
2.
Какова схема процесса принятия решений?
3.
Дайте классификацию методов принятия решений.
4.
Могут ли решения быть допустимыми?
5.
Укажите математические методы ПР.
6.
Какой класс математических моделей ПР является наиболее распространенным?
7.
В чем особенность линейных моделей ПР?
8.
Сформулируйте общую постановку задачи линейного программирования.
9.
Дайте геометрическую интерпретацию ЗЛП. x
x
D
C
B
A точка С – оптимальное значение
,